New Results on Generalization of Roos-Type Biases and Related Keystreams of RC4 View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Subhamoy Maitra , Goutam Paul , Santanu Sarkar , Michael Lehmann , Willi Meier

ABSTRACT

The first known result on RC4 cryptanalysis (presented by Roos in 1995) points out that the most likely value of the y-th element of the permutation after the key scheduling algorithm (KSA) for the first few values of y is given by SN[y] = fy, some linear combinations of the secret keys. While it should have been quite natural to study the association SN[y] = fy ±t for small positive integers t (e.g., t ≤ 4), surprisingly that had never been tried before. In this paper, we study that problem for the first time and show that though the event SN[y] = fy + t occurs with random association, there is a significantly high probability for the event SN[y] = fy − t. We also present several related non-randomness behaviour for the event SN[SN[y]] = fy − t of RC4 KSA in this direction. Further, we investigate near-colliding keys that lead to related states after the KSA and related keystream bytes. Our investigation reveals that near-colliding states do not necessarily lead to near-colliding keystreams. From this motivation, we present a heuristic to find a related key pair with differences in two bytes, that lead to significant matches in the initial keystream. In the process, we discover a class of related key distinguishers for RC4. The best one of these shows that given a random key and a related one to that (the last two bytes increased and decreased by 1 respectively), the first pair of bytes corresponding to the related keys are same with very high probability (e.g., approximately 0.011 for 16-byte keys to 0.044 for 30-byte keys). More... »

PAGES

222-239

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-38553-7_13

DOI

http://dx.doi.org/10.1007/978-3-642-38553-7_13

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1040296259


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Applied Statistics Unit, Indian Statistical Institute, 700 108, Kolkata, India", 
          "id": "http://www.grid.ac/institutes/grid.39953.35", 
          "name": [
            "Applied Statistics Unit, Indian Statistical Institute, 700 108, Kolkata, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maitra", 
        "givenName": "Subhamoy", 
        "id": "sg:person.013667777721.90", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013667777721.90"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Jadavpur University, 700 032, Kolkata, India", 
          "id": "http://www.grid.ac/institutes/grid.216499.1", 
          "name": [
            "Department of Computer Science and Engineering, Jadavpur University, 700 032, Kolkata, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Paul", 
        "givenName": "Goutam", 
        "id": "sg:person.012131006407.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012131006407.38"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Chennai Mathematical Institute, 603 103, Chennai, India", 
          "id": "http://www.grid.ac/institutes/grid.444722.3", 
          "name": [
            "Chennai Mathematical Institute, 603 103, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sarkar", 
        "givenName": "Santanu", 
        "id": "sg:person.013316030122.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013316030122.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "FHNW, Windisch, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.410380.e", 
          "name": [
            "FHNW, Windisch, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lehmann", 
        "givenName": "Michael", 
        "id": "sg:person.014250441271.87", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014250441271.87"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "FHNW, Windisch, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.410380.e", 
          "name": [
            "FHNW, Windisch, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Meier", 
        "givenName": "Willi", 
        "id": "sg:person.07653531142.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "The first known result on RC4 cryptanalysis (presented by Roos in 1995) points out that the most likely value of the y-th element of the permutation after the key scheduling algorithm (KSA) for the first few values of y is given by SN[y]\u2009=\u2009fy, some linear combinations of the secret keys. While it should have been quite natural to study the association SN[y]\u2009=\u2009fy \u00b1t for small positive integers t (e.g., t\u2009\u2264\u20094), surprisingly that had never been tried before. In this paper, we study that problem for the first time and show that though the event SN[y]\u2009=\u2009fy\u2009+\u2009t occurs with random association, there is a significantly high probability for the event SN[y]\u2009=\u2009fy\u2009\u2212\u2009t. We also present several related non-randomness behaviour for the event SN[SN[y]]\u2009=\u2009fy\u2009\u2212\u2009t of RC4 KSA in this direction. Further, we investigate near-colliding keys that lead to related states after the KSA and related keystream bytes. Our investigation reveals that near-colliding states do not necessarily lead to near-colliding keystreams. From this motivation, we present a heuristic to find a related key pair with differences in two bytes, that lead to significant matches in the initial keystream. In the process, we discover a class of related key distinguishers for RC4. The best one of these shows that given a random key and a related one to that (the last two bytes increased and decreased by 1 respectively), the first pair of bytes corresponding to the related keys are same with very high probability (e.g., approximately 0.011 for 16-byte keys to 0.044 for 30-byte keys).", 
    "editor": [
      {
        "familyName": "Youssef", 
        "givenName": "Amr", 
        "type": "Person"
      }, 
      {
        "familyName": "Nitaj", 
        "givenName": "Abderrahmane", 
        "type": "Person"
      }, 
      {
        "familyName": "Hassanien", 
        "givenName": "Aboul Ella", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-38553-7_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-38552-0", 
        "978-3-642-38553-7"
      ], 
      "name": "Progress in Cryptology \u2013 AFRICACRYPT 2013", 
      "type": "Book"
    }, 
    "keywords": [
      "likely value", 
      "scheduling algorithm", 
      "linear combination", 
      "smallest positive integer t", 
      "positive integer t", 
      "integer t", 
      "high probability", 
      "random keys", 
      "new results", 
      "results", 
      "cryptanalysis", 
      "values", 
      "elements", 
      "permutations", 
      "key scheduling algorithm", 
      "algorithm", 
      "FY", 
      "secret key", 
      "association", 
      "problem", 
      "events", 
      "probability", 
      "related state", 
      "state", 
      "keystream bytes", 
      "bytes", 
      "keystream", 
      "heuristics", 
      "pairs", 
      "differences", 
      "match", 
      "class", 
      "distinguisher", 
      "RC4", 
      "generalization", 
      "combination", 
      "key", 
      "paper", 
      "first time", 
      "time", 
      "random association", 
      "behavior", 
      "direction", 
      "investigation", 
      "motivation", 
      "key pair", 
      "significant matches", 
      "process", 
      "key distinguisher", 
      "show", 
      "first pair", 
      "related keys", 
      "biases", 
      "RC4 cryptanalysis", 
      "related non-randomness behaviour", 
      "non-randomness behaviour", 
      "RC4 Key Scheduling Algorithm", 
      "colliding keystreams", 
      "related key pair", 
      "initial keystream", 
      "related key distinguishers", 
      "Roos-Type Biases", 
      "Related Keystreams"
    ], 
    "name": "New Results on Generalization of Roos-Type Biases and Related Keystreams of RC4", 
    "pagination": "222-239", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040296259"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-38553-7_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-38553-7_13", 
      "https://app.dimensions.ai/details/publication/pub.1040296259"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:25", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_432.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-38553-7_13"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38553-7_13'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38553-7_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38553-7_13'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38553-7_13'


 

This table displays all metadata directly associated to this object as RDF triples.

170 TRIPLES      23 PREDICATES      89 URIs      82 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-38553-7_13 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N299e275b8e484392a6b8d876ade802a5
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description The first known result on RC4 cryptanalysis (presented by Roos in 1995) points out that the most likely value of the y-th element of the permutation after the key scheduling algorithm (KSA) for the first few values of y is given by SN[y] = fy, some linear combinations of the secret keys. While it should have been quite natural to study the association SN[y] = fy ±t for small positive integers t (e.g., t ≤ 4), surprisingly that had never been tried before. In this paper, we study that problem for the first time and show that though the event SN[y] = fy + t occurs with random association, there is a significantly high probability for the event SN[y] = fy − t. We also present several related non-randomness behaviour for the event SN[SN[y]] = fy − t of RC4 KSA in this direction. Further, we investigate near-colliding keys that lead to related states after the KSA and related keystream bytes. Our investigation reveals that near-colliding states do not necessarily lead to near-colliding keystreams. From this motivation, we present a heuristic to find a related key pair with differences in two bytes, that lead to significant matches in the initial keystream. In the process, we discover a class of related key distinguishers for RC4. The best one of these shows that given a random key and a related one to that (the last two bytes increased and decreased by 1 respectively), the first pair of bytes corresponding to the related keys are same with very high probability (e.g., approximately 0.011 for 16-byte keys to 0.044 for 30-byte keys).
7 schema:editor N0a0a9c586488422383d5164850137f1c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne99d5d2f81e74ffbbb0944827473404c
12 schema:keywords FY
13 RC4
14 RC4 Key Scheduling Algorithm
15 RC4 cryptanalysis
16 Related Keystreams
17 Roos-Type Biases
18 algorithm
19 association
20 behavior
21 biases
22 bytes
23 class
24 colliding keystreams
25 combination
26 cryptanalysis
27 differences
28 direction
29 distinguisher
30 elements
31 events
32 first pair
33 first time
34 generalization
35 heuristics
36 high probability
37 initial keystream
38 integer t
39 investigation
40 key
41 key distinguisher
42 key pair
43 key scheduling algorithm
44 keystream
45 keystream bytes
46 likely value
47 linear combination
48 match
49 motivation
50 new results
51 non-randomness behaviour
52 pairs
53 paper
54 permutations
55 positive integer t
56 probability
57 problem
58 process
59 random association
60 random keys
61 related key distinguishers
62 related key pair
63 related keys
64 related non-randomness behaviour
65 related state
66 results
67 scheduling algorithm
68 secret key
69 show
70 significant matches
71 smallest positive integer t
72 state
73 time
74 values
75 schema:name New Results on Generalization of Roos-Type Biases and Related Keystreams of RC4
76 schema:pagination 222-239
77 schema:productId N1aee31c3bd474c74b291973b5d8e390e
78 Na6e60d38ce784abd916b055db24642aa
79 schema:publisher Nfd84e34a42834c06a26a2ffe03af15d7
80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040296259
81 https://doi.org/10.1007/978-3-642-38553-7_13
82 schema:sdDatePublished 2022-01-01T19:25
83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
84 schema:sdPublisher N4ea7f2868a0247c5a4bf08f38481c21c
85 schema:url https://doi.org/10.1007/978-3-642-38553-7_13
86 sgo:license sg:explorer/license/
87 sgo:sdDataset chapters
88 rdf:type schema:Chapter
89 N0a0a9c586488422383d5164850137f1c rdf:first N44056e399733469c9916f649df121ca9
90 rdf:rest Nafe7a9fc7ae74d6d92aac9e0f99b9e22
91 N18b9ee26eea34c89b15f1bbd5b423a65 schema:familyName Hassanien
92 schema:givenName Aboul Ella
93 rdf:type schema:Person
94 N1aee31c3bd474c74b291973b5d8e390e schema:name doi
95 schema:value 10.1007/978-3-642-38553-7_13
96 rdf:type schema:PropertyValue
97 N299e275b8e484392a6b8d876ade802a5 rdf:first sg:person.013667777721.90
98 rdf:rest Nf05c4de8ee604ce0845fe8e4c3e64ea7
99 N398a5f05ae9b4156bc71b6f9c2a82d37 schema:familyName Nitaj
100 schema:givenName Abderrahmane
101 rdf:type schema:Person
102 N3c6838b5ed0249ad8ad59c27c8205147 rdf:first N18b9ee26eea34c89b15f1bbd5b423a65
103 rdf:rest rdf:nil
104 N44056e399733469c9916f649df121ca9 schema:familyName Youssef
105 schema:givenName Amr
106 rdf:type schema:Person
107 N4ea7f2868a0247c5a4bf08f38481c21c schema:name Springer Nature - SN SciGraph project
108 rdf:type schema:Organization
109 N4ffbcf0e0f1e45bcbdf8d6391c9f85ec rdf:first sg:person.07653531142.18
110 rdf:rest rdf:nil
111 N61d4a72afd8548f484710b35b20b1e95 rdf:first sg:person.014250441271.87
112 rdf:rest N4ffbcf0e0f1e45bcbdf8d6391c9f85ec
113 Na6e60d38ce784abd916b055db24642aa schema:name dimensions_id
114 schema:value pub.1040296259
115 rdf:type schema:PropertyValue
116 Nafe7a9fc7ae74d6d92aac9e0f99b9e22 rdf:first N398a5f05ae9b4156bc71b6f9c2a82d37
117 rdf:rest N3c6838b5ed0249ad8ad59c27c8205147
118 Ncee10773b4c74e46aac5dc2b600ac22e rdf:first sg:person.013316030122.96
119 rdf:rest N61d4a72afd8548f484710b35b20b1e95
120 Ne99d5d2f81e74ffbbb0944827473404c schema:isbn 978-3-642-38552-0
121 978-3-642-38553-7
122 schema:name Progress in Cryptology – AFRICACRYPT 2013
123 rdf:type schema:Book
124 Nf05c4de8ee604ce0845fe8e4c3e64ea7 rdf:first sg:person.012131006407.38
125 rdf:rest Ncee10773b4c74e46aac5dc2b600ac22e
126 Nfd84e34a42834c06a26a2ffe03af15d7 schema:name Springer Nature
127 rdf:type schema:Organisation
128 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
129 schema:name Psychology and Cognitive Sciences
130 rdf:type schema:DefinedTerm
131 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
132 schema:name Psychology
133 rdf:type schema:DefinedTerm
134 sg:person.012131006407.38 schema:affiliation grid-institutes:grid.216499.1
135 schema:familyName Paul
136 schema:givenName Goutam
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012131006407.38
138 rdf:type schema:Person
139 sg:person.013316030122.96 schema:affiliation grid-institutes:grid.444722.3
140 schema:familyName Sarkar
141 schema:givenName Santanu
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013316030122.96
143 rdf:type schema:Person
144 sg:person.013667777721.90 schema:affiliation grid-institutes:grid.39953.35
145 schema:familyName Maitra
146 schema:givenName Subhamoy
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013667777721.90
148 rdf:type schema:Person
149 sg:person.014250441271.87 schema:affiliation grid-institutes:grid.410380.e
150 schema:familyName Lehmann
151 schema:givenName Michael
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014250441271.87
153 rdf:type schema:Person
154 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
155 schema:familyName Meier
156 schema:givenName Willi
157 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
158 rdf:type schema:Person
159 grid-institutes:grid.216499.1 schema:alternateName Department of Computer Science and Engineering, Jadavpur University, 700 032, Kolkata, India
160 schema:name Department of Computer Science and Engineering, Jadavpur University, 700 032, Kolkata, India
161 rdf:type schema:Organization
162 grid-institutes:grid.39953.35 schema:alternateName Applied Statistics Unit, Indian Statistical Institute, 700 108, Kolkata, India
163 schema:name Applied Statistics Unit, Indian Statistical Institute, 700 108, Kolkata, India
164 rdf:type schema:Organization
165 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
166 schema:name FHNW, Windisch, Switzerland
167 rdf:type schema:Organization
168 grid-institutes:grid.444722.3 schema:alternateName Chennai Mathematical Institute, 603 103, Chennai, India
169 schema:name Chennai Mathematical Institute, 603 103, Chennai, India
170 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...