Algebraic Attacks on Combiners with Memory View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003

AUTHORS

Frederik Armknecht , Matthias Krause

ABSTRACT

Recently, algebraic attacks were proposed to attack several cryptosystems, e.g. AES, LILI-128 and Toyocrypt. This paper extends the use of algebraic attacks to combiners with memory. A (k,l)-combiner consists of k parallel linear feedback shift registers (LFSRs), and the nonlinear filtering is done via a finite automaton with k input bits and l memory bits. It is shown that for (k,l)-combiners, nontrivial canceling relations of degree at most ⌈k(l+1)/2⌉ exist. This makes algebraic attacks possible. Also, a general method is presented to check for such relations with an even lower degree. This allows to show the invulnerability of certain (k,l)-combiners against this kind of algebraic attacks. On the other hand, this can also be used as a tool to find improved algebraic attacks.Inspired by this method, the E0 keystream generator from the Bluetooth standard is analyzed. As it turns out, a secret key can be recovered by solving a system of linear equations with 223.07 unknowns. To our knowledge, this is the best published attack on the E0 keystream generator yet. More... »

PAGES

162-175

Book

TITLE

Advances in Cryptology - CRYPTO 2003

ISBN

978-3-540-40674-7
978-3-540-45146-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-45146-4_10

DOI

http://dx.doi.org/10.1007/978-3-540-45146-4_10

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Theoretische Informatik, Universit\u00e4t Mannheim, 68131, Mannheim, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5601.2", 
          "name": [
            "Theoretische Informatik, Universit\u00e4t Mannheim, 68131, Mannheim, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Armknecht", 
        "givenName": "Frederik", 
        "id": "sg:person.010715073032.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010715073032.95"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Theoretische Informatik, Universit\u00e4t Mannheim, 68131, Mannheim, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5601.2", 
          "name": [
            "Theoretische Informatik, Universit\u00e4t Mannheim, 68131, Mannheim, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Krause", 
        "givenName": "Matthias", 
        "id": "sg:person.014033162131.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014033162131.95"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "Recently, algebraic attacks were proposed to attack several cryptosystems, e.g. AES, LILI-128 and Toyocrypt. This paper extends the use of algebraic attacks to combiners with memory. A (k,l)-combiner consists of k parallel linear feedback shift registers (LFSRs), and the nonlinear filtering is done via a finite automaton with k input bits and l memory bits. It is shown that for (k,l)-combiners, nontrivial canceling relations of degree at most \u2308k(l+1)/2\u2309 exist. This makes algebraic attacks possible. Also, a general method is presented to check for such relations with an even lower degree. This allows to show the invulnerability of certain (k,l)-combiners against this kind of algebraic attacks. On the other hand, this can also be used as a tool to find improved algebraic attacks.Inspired by this method, the E0 keystream generator from the Bluetooth standard is analyzed. As it turns out, a secret key can be recovered by solving a system of linear equations with 223.07 unknowns. To our knowledge, this is the best published attack on the E0 keystream generator yet.", 
    "editor": [
      {
        "familyName": "Boneh", 
        "givenName": "Dan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-45146-4_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-40674-7", 
        "978-3-540-45146-4"
      ], 
      "name": "Advances in Cryptology - CRYPTO 2003", 
      "type": "Book"
    }, 
    "keywords": [
      "algebraic attacks", 
      "nonlinear filtering", 
      "keystream generator", 
      "linear equations", 
      "linear feedback shift register", 
      "parallel linear feedback shift registers", 
      "general method", 
      "finite automata", 
      "feedback shift registers", 
      "Toyocrypt", 
      "equations", 
      "generator", 
      "unknowns", 
      "Bluetooth standard", 
      "filtering", 
      "input bits", 
      "such relations", 
      "automata", 
      "shift register", 
      "combiner", 
      "cryptosystem", 
      "LILI-128", 
      "bits", 
      "system", 
      "invulnerability", 
      "tool", 
      "kind", 
      "secret key", 
      "relation", 
      "degree", 
      "attacks", 
      "memory", 
      "use", 
      "low degree", 
      "hand", 
      "key", 
      "knowledge", 
      "memory bits", 
      "standards", 
      "AES", 
      "Register", 
      "method", 
      "paper", 
      "nontrivial canceling relations", 
      "canceling relations", 
      "improved algebraic attacks", 
      "E0 keystream generator"
    ], 
    "name": "Algebraic Attacks on Combiners with Memory", 
    "pagination": "162-175", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049850905"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-45146-4_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-45146-4_10", 
      "https://app.dimensions.ai/details/publication/pub.1049850905"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T19:01", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_52.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-45146-4_10"
  }
]
 

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-540-45146-4_10'

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-540-45146-4_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-45146-4_10'

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-540-45146-4_10'


 

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

114 TRIPLES      23 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-45146-4_10 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N0b4f291c2ba942299aebf1da04230653
4 schema:datePublished 2003
5 schema:datePublishedReg 2003-01-01
6 schema:description Recently, algebraic attacks were proposed to attack several cryptosystems, e.g. AES, LILI-128 and Toyocrypt. This paper extends the use of algebraic attacks to combiners with memory. A (k,l)-combiner consists of k parallel linear feedback shift registers (LFSRs), and the nonlinear filtering is done via a finite automaton with k input bits and l memory bits. It is shown that for (k,l)-combiners, nontrivial canceling relations of degree at most ⌈k(l+1)/2⌉ exist. This makes algebraic attacks possible. Also, a general method is presented to check for such relations with an even lower degree. This allows to show the invulnerability of certain (k,l)-combiners against this kind of algebraic attacks. On the other hand, this can also be used as a tool to find improved algebraic attacks.Inspired by this method, the E0 keystream generator from the Bluetooth standard is analyzed. As it turns out, a secret key can be recovered by solving a system of linear equations with 223.07 unknowns. To our knowledge, this is the best published attack on the E0 keystream generator yet.
7 schema:editor N4c86b8393e0c40c5af0d78ddb58a6b73
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ncabad696e02f498e95ebe2dcc76d44df
12 schema:keywords AES
13 Bluetooth standard
14 E0 keystream generator
15 LILI-128
16 Register
17 Toyocrypt
18 algebraic attacks
19 attacks
20 automata
21 bits
22 canceling relations
23 combiner
24 cryptosystem
25 degree
26 equations
27 feedback shift registers
28 filtering
29 finite automata
30 general method
31 generator
32 hand
33 improved algebraic attacks
34 input bits
35 invulnerability
36 key
37 keystream generator
38 kind
39 knowledge
40 linear equations
41 linear feedback shift register
42 low degree
43 memory
44 memory bits
45 method
46 nonlinear filtering
47 nontrivial canceling relations
48 paper
49 parallel linear feedback shift registers
50 relation
51 secret key
52 shift register
53 standards
54 such relations
55 system
56 tool
57 unknowns
58 use
59 schema:name Algebraic Attacks on Combiners with Memory
60 schema:pagination 162-175
61 schema:productId Na4375629f7ce495ea2a5891b28191a3a
62 Nf4a433e0183a44a79dd3aba915dae294
63 schema:publisher N5d504c79daef423cb54932b32e9dd7da
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049850905
65 https://doi.org/10.1007/978-3-540-45146-4_10
66 schema:sdDatePublished 2021-11-01T19:01
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher N399ef6f89b3747e8acfcd16be990f739
69 schema:url https://doi.org/10.1007/978-3-540-45146-4_10
70 sgo:license sg:explorer/license/
71 sgo:sdDataset chapters
72 rdf:type schema:Chapter
73 N0b4f291c2ba942299aebf1da04230653 rdf:first sg:person.010715073032.95
74 rdf:rest N4641ea585dd7427fbe5be4e3a0a6adff
75 N399ef6f89b3747e8acfcd16be990f739 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N4641ea585dd7427fbe5be4e3a0a6adff rdf:first sg:person.014033162131.95
78 rdf:rest rdf:nil
79 N4c86b8393e0c40c5af0d78ddb58a6b73 rdf:first N55621c4ba7344a5d9f345c805a06681c
80 rdf:rest rdf:nil
81 N55621c4ba7344a5d9f345c805a06681c schema:familyName Boneh
82 schema:givenName Dan
83 rdf:type schema:Person
84 N5d504c79daef423cb54932b32e9dd7da schema:name Springer Nature
85 rdf:type schema:Organisation
86 Na4375629f7ce495ea2a5891b28191a3a schema:name dimensions_id
87 schema:value pub.1049850905
88 rdf:type schema:PropertyValue
89 Ncabad696e02f498e95ebe2dcc76d44df schema:isbn 978-3-540-40674-7
90 978-3-540-45146-4
91 schema:name Advances in Cryptology - CRYPTO 2003
92 rdf:type schema:Book
93 Nf4a433e0183a44a79dd3aba915dae294 schema:name doi
94 schema:value 10.1007/978-3-540-45146-4_10
95 rdf:type schema:PropertyValue
96 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
97 schema:name Mathematical Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
100 schema:name Pure Mathematics
101 rdf:type schema:DefinedTerm
102 sg:person.010715073032.95 schema:affiliation grid-institutes:grid.5601.2
103 schema:familyName Armknecht
104 schema:givenName Frederik
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010715073032.95
106 rdf:type schema:Person
107 sg:person.014033162131.95 schema:affiliation grid-institutes:grid.5601.2
108 schema:familyName Krause
109 schema:givenName Matthias
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014033162131.95
111 rdf:type schema:Person
112 grid-institutes:grid.5601.2 schema:alternateName Theoretische Informatik, Universität Mannheim, 68131, Mannheim, Germany
113 schema:name Theoretische Informatik, Universität Mannheim, 68131, Mannheim, Germany
114 rdf:type schema:Organization
 




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


...