Algebraic and Correlation Attacks against Linearly Filtered Non Linear Feedback Shift Registers View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Côme Berbain , Henri Gilbert , Antoine Joux

ABSTRACT

The filter generator is a well known and extensively studied stream cipher construction. It consists of a Linear Feedback Shift Register (LFSR) filtered by a non linear Boolean function. In this paper we focus on the dual construction, namely a linearly filtered Non linear Feedback Shift Register (NFSR). We show that the existing algebraic and correlation attacks against the filter generator can be transposed to mount algebraic or correlation attacks against this dual construction. We investigate such attacks and extend them to the case where a linearly filtered NFSR is combined linearly with one or more non linearly filtered LFSRs. We apply our algebraic attack to a modified version of Grain-128, resulting in an attack requiring 2105 computations and 239 keystream bits. Even though this attack does not apply to the original Grain-128, it shows that the use of a NFSR is not sufficient to avoid all algebraic attacks. More... »

PAGES

184-198

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-04159-4_12

DOI

http://dx.doi.org/10.1007/978-3-642-04159-4_12

DIMENSIONS

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


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": "Orange Labs, 38-40 rue du G\u00e9n\u00e9ral Leclerc, 92794, Issy-les-Moulineaux, France", 
          "id": "http://www.grid.ac/institutes/grid.89485.38", 
          "name": [
            "Orange Labs, 38-40 rue du G\u00e9n\u00e9ral Leclerc, 92794, Issy-les-Moulineaux, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berbain", 
        "givenName": "C\u00f4me", 
        "id": "sg:person.011123560622.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011123560622.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Orange Labs, 38-40 rue du G\u00e9n\u00e9ral Leclerc, 92794, Issy-les-Moulineaux, France", 
          "id": "http://www.grid.ac/institutes/grid.89485.38", 
          "name": [
            "Orange Labs, 38-40 rue du G\u00e9n\u00e9ral Leclerc, 92794, Issy-les-Moulineaux, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gilbert", 
        "givenName": "Henri", 
        "id": "sg:person.012771236207.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012771236207.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DGA and Universit\u00e9 de Versailles, 45 avenue des Etats-Unis, 78035, Versailles Cedex, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "DGA and Universit\u00e9 de Versailles, 45 avenue des Etats-Unis, 78035, Versailles Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Joux", 
        "givenName": "Antoine", 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "The filter generator is a well known and extensively studied stream cipher construction. It consists of a Linear Feedback Shift Register (LFSR) filtered by a non linear Boolean function. In this paper we focus on the dual construction, namely a linearly filtered Non linear Feedback Shift Register (NFSR). We show that the existing algebraic and correlation attacks against the filter generator can be transposed to mount algebraic or correlation attacks against this dual construction. We investigate such attacks and extend them to the case where a linearly filtered NFSR is combined linearly with one or more non linearly filtered LFSRs. We apply our algebraic attack to a modified version of Grain-128, resulting in an attack requiring 2105 computations and 239 keystream bits. Even though this attack does not apply to the original Grain-128, it shows that the use of a NFSR is not sufficient to avoid all algebraic attacks.", 
    "editor": [
      {
        "familyName": "Avanzi", 
        "givenName": "Roberto Maria", 
        "type": "Person"
      }, 
      {
        "familyName": "Keliher", 
        "givenName": "Liam", 
        "type": "Person"
      }, 
      {
        "familyName": "Sica", 
        "givenName": "Francesco", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-04159-4_12", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-04158-7", 
        "978-3-642-04159-4"
      ], 
      "name": "Selected Areas in Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "linear feedback shift register", 
      "feedback shift registers", 
      "non-linear feedback shift registers", 
      "algebraic attacks", 
      "filter generator", 
      "dual construction", 
      "correlation attacks", 
      "shift register", 
      "algebraic", 
      "Boolean functions", 
      "non-linear Boolean functions", 
      "computation", 
      "generator", 
      "keystream bits", 
      "Linearly", 
      "construction", 
      "Grain-128", 
      "linear Boolean functions", 
      "version", 
      "function", 
      "such attacks", 
      "cases", 
      "bits", 
      "attacks", 
      "use", 
      "Register", 
      "paper", 
      "stream cipher construction"
    ], 
    "name": "Algebraic and Correlation Attacks against Linearly Filtered Non Linear Feedback Shift Registers", 
    "pagination": "184-198", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052522397"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-04159-4_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-04159-4_12", 
      "https://app.dimensions.ai/details/publication/pub.1052522397"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_6.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-04159-4_12"
  }
]
 

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-04159-4_12'

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-04159-4_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-04159-4_12'

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-04159-4_12'


 

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

113 TRIPLES      22 PREDICATES      53 URIs      46 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-04159-4_12 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nfd31ee9b6ca6456795a28a2967628ef3
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description The filter generator is a well known and extensively studied stream cipher construction. It consists of a Linear Feedback Shift Register (LFSR) filtered by a non linear Boolean function. In this paper we focus on the dual construction, namely a linearly filtered Non linear Feedback Shift Register (NFSR). We show that the existing algebraic and correlation attacks against the filter generator can be transposed to mount algebraic or correlation attacks against this dual construction. We investigate such attacks and extend them to the case where a linearly filtered NFSR is combined linearly with one or more non linearly filtered LFSRs. We apply our algebraic attack to a modified version of Grain-128, resulting in an attack requiring 2105 computations and 239 keystream bits. Even though this attack does not apply to the original Grain-128, it shows that the use of a NFSR is not sufficient to avoid all algebraic attacks.
7 schema:editor Nf7794b377ea1482585c6a9c8ca4ea39e
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N4c65cb7e6892474da73f8e51d19d5e9a
11 schema:keywords Boolean functions
12 Grain-128
13 Linearly
14 Register
15 algebraic
16 algebraic attacks
17 attacks
18 bits
19 cases
20 computation
21 construction
22 correlation attacks
23 dual construction
24 feedback shift registers
25 filter generator
26 function
27 generator
28 keystream bits
29 linear Boolean functions
30 linear feedback shift register
31 non-linear Boolean functions
32 non-linear feedback shift registers
33 paper
34 shift register
35 stream cipher construction
36 such attacks
37 use
38 version
39 schema:name Algebraic and Correlation Attacks against Linearly Filtered Non Linear Feedback Shift Registers
40 schema:pagination 184-198
41 schema:productId N2dd60a87eef542e0ab7d1b59aabb1bb4
42 N77143994c0e74f7c99a30e304036fc68
43 schema:publisher N7796ee29b97b4d6fb162a85a9cd91657
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052522397
45 https://doi.org/10.1007/978-3-642-04159-4_12
46 schema:sdDatePublished 2022-11-24T21:20
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N1fd19329d1a74eefa50bbd75fc1dff87
49 schema:url https://doi.org/10.1007/978-3-642-04159-4_12
50 sgo:license sg:explorer/license/
51 sgo:sdDataset chapters
52 rdf:type schema:Chapter
53 N023e9bcd0d46429aab73a51290b69094 rdf:first Nb9e34d2404ac4d25a32c19909d0ff748
54 rdf:rest N8311f05fdc0a4861aeec28d5a0de011e
55 N146407ebba8b4ded9d66b722aeb2e543 rdf:first sg:person.012771236207.08
56 rdf:rest N5bfac26ec441406bb6908ae0353f2e9e
57 N1fd19329d1a74eefa50bbd75fc1dff87 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N2dd60a87eef542e0ab7d1b59aabb1bb4 schema:name dimensions_id
60 schema:value pub.1052522397
61 rdf:type schema:PropertyValue
62 N467ff041ad29411a9b3008e8c770c1a3 schema:familyName Sica
63 schema:givenName Francesco
64 rdf:type schema:Person
65 N4c65cb7e6892474da73f8e51d19d5e9a schema:isbn 978-3-642-04158-7
66 978-3-642-04159-4
67 schema:name Selected Areas in Cryptography
68 rdf:type schema:Book
69 N5bfac26ec441406bb6908ae0353f2e9e rdf:first Necba7972d15e4097b7a3c679398b9dae
70 rdf:rest rdf:nil
71 N77143994c0e74f7c99a30e304036fc68 schema:name doi
72 schema:value 10.1007/978-3-642-04159-4_12
73 rdf:type schema:PropertyValue
74 N7796ee29b97b4d6fb162a85a9cd91657 schema:name Springer Nature
75 rdf:type schema:Organisation
76 N8311f05fdc0a4861aeec28d5a0de011e rdf:first N467ff041ad29411a9b3008e8c770c1a3
77 rdf:rest rdf:nil
78 Nb9e34d2404ac4d25a32c19909d0ff748 schema:familyName Keliher
79 schema:givenName Liam
80 rdf:type schema:Person
81 Ncd0949889d7c41c0add4225df7c02640 schema:familyName Avanzi
82 schema:givenName Roberto Maria
83 rdf:type schema:Person
84 Necba7972d15e4097b7a3c679398b9dae schema:affiliation grid-institutes:None
85 schema:familyName Joux
86 schema:givenName Antoine
87 rdf:type schema:Person
88 Nf7794b377ea1482585c6a9c8ca4ea39e rdf:first Ncd0949889d7c41c0add4225df7c02640
89 rdf:rest N023e9bcd0d46429aab73a51290b69094
90 Nfd31ee9b6ca6456795a28a2967628ef3 rdf:first sg:person.011123560622.27
91 rdf:rest N146407ebba8b4ded9d66b722aeb2e543
92 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
93 schema:name Mathematical Sciences
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
96 schema:name Pure Mathematics
97 rdf:type schema:DefinedTerm
98 sg:person.011123560622.27 schema:affiliation grid-institutes:grid.89485.38
99 schema:familyName Berbain
100 schema:givenName Côme
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011123560622.27
102 rdf:type schema:Person
103 sg:person.012771236207.08 schema:affiliation grid-institutes:grid.89485.38
104 schema:familyName Gilbert
105 schema:givenName Henri
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012771236207.08
107 rdf:type schema:Person
108 grid-institutes:None schema:alternateName DGA and Université de Versailles, 45 avenue des Etats-Unis, 78035, Versailles Cedex, France
109 schema:name DGA and Université de Versailles, 45 avenue des Etats-Unis, 78035, Versailles Cedex, France
110 rdf:type schema:Organization
111 grid-institutes:grid.89485.38 schema:alternateName Orange Labs, 38-40 rue du Général Leclerc, 92794, Issy-les-Moulineaux, France
112 schema:name Orange Labs, 38-40 rue du Général Leclerc, 92794, Issy-les-Moulineaux, France
113 rdf:type schema:Organization
 




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


...