Cryptanalysis of Full Sprout View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-08-01

AUTHORS

Virginie Lallemand , María Naya-Plasencia

ABSTRACT

A new method for reducing the internal state size of stream cipher registers has been proposed in FSE 2015, allowing to reduce the area in hardware implementations. Along with it, an instantiated proposal of a cipher was also proposed: Sprout. In this paper, we analyze the security of Sprout, and we propose an attack that recovers the whole key more than 210\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{10}$$\end{document} times faster than exhaustive search and has very low data complexity. The attack can be seen as a divide-and-conquer evolved technique, that exploits the non-linear influence of the key bits on the update function. We have implemented the attack on a toy version of Sprout, that conserves the main properties exploited in the attack. The attack completely matches the expected complexities predicted by our theoretical cryptanalysis, which proves its validity. We believe that our attack shows that a more careful analysis should be done in order to instantiate the proposed design method. More... »

PAGES

663-682

Book

TITLE

Advances in Cryptology -- CRYPTO 2015

ISBN

978-3-662-47988-9
978-3-662-47989-6

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-47989-6_32

DOI

http://dx.doi.org/10.1007/978-3-662-47989-6_32

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Inria, Bordeaux, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Inria, Bordeaux, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lallemand", 
        "givenName": "Virginie", 
        "id": "sg:person.011135275143.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011135275143.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Inria, Bordeaux, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Inria, Bordeaux, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naya-Plasencia", 
        "givenName": "Mar\u00eda", 
        "id": "sg:person.013206304341.94", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-08-01", 
    "datePublishedReg": "2015-08-01", 
    "description": "A new method for reducing the internal state size of stream cipher registers has been proposed in FSE 2015, allowing to reduce the area in hardware implementations. Along with it, an instantiated proposal of a cipher was also proposed: Sprout. In this paper, we analyze the security of Sprout, and we propose an attack that recovers the whole key more than 210\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{10}$$\\end{document} times faster than exhaustive search and has very low data complexity. The attack can be seen as a divide-and-conquer evolved technique, that exploits the non-linear influence of the key bits on the update function. We have implemented the attack on a toy version of Sprout, that conserves the main properties exploited in the attack. The attack completely matches the expected complexities predicted by our theoretical cryptanalysis, which proves its validity. We believe that our attack shows that a more careful analysis should be done in order to instantiate the proposed design method.", 
    "editor": [
      {
        "familyName": "Gennaro", 
        "givenName": "Rosario", 
        "type": "Person"
      }, 
      {
        "familyName": "Robshaw", 
        "givenName": "Matthew", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-47989-6_32", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-47988-9", 
        "978-3-662-47989-6"
      ], 
      "name": "Advances in Cryptology -- CRYPTO 2015", 
      "type": "Book"
    }, 
    "keywords": [
      "design method", 
      "hardware implementation", 
      "non-linear influence", 
      "new method", 
      "main properties", 
      "method", 
      "properties", 
      "exhaustive search", 
      "low data complexity", 
      "toy version", 
      "size", 
      "evolved technique", 
      "technique", 
      "influence", 
      "update function", 
      "internal state size", 
      "complexity", 
      "careful analysis", 
      "order", 
      "state size", 
      "implementation", 
      "attacks", 
      "time", 
      "data complexity", 
      "bits", 
      "area", 
      "validity", 
      "analysis", 
      "key", 
      "key bits", 
      "cryptanalysis", 
      "proposal", 
      "security", 
      "function", 
      "version", 
      "cipher", 
      "search", 
      "whole key", 
      "divide", 
      "sprouts", 
      "Register", 
      "paper", 
      "FSE 2015", 
      "theoretical cryptanalysis"
    ], 
    "name": "Cryptanalysis of Full Sprout", 
    "pagination": "663-682", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1023908343"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-47989-6_32"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-47989-6_32", 
      "https://app.dimensions.ai/details/publication/pub.1023908343"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_116.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-47989-6_32"
  }
]
 

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-662-47989-6_32'

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-662-47989-6_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-47989-6_32'

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-662-47989-6_32'


 

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

115 TRIPLES      22 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-47989-6_32 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N4eabf6a22c5b4e178e18f1d82ef8b08f
4 schema:datePublished 2015-08-01
5 schema:datePublishedReg 2015-08-01
6 schema:description A new method for reducing the internal state size of stream cipher registers has been proposed in FSE 2015, allowing to reduce the area in hardware implementations. Along with it, an instantiated proposal of a cipher was also proposed: Sprout. In this paper, we analyze the security of Sprout, and we propose an attack that recovers the whole key more than 210\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{10}$$\end{document} times faster than exhaustive search and has very low data complexity. The attack can be seen as a divide-and-conquer evolved technique, that exploits the non-linear influence of the key bits on the update function. We have implemented the attack on a toy version of Sprout, that conserves the main properties exploited in the attack. The attack completely matches the expected complexities predicted by our theoretical cryptanalysis, which proves its validity. We believe that our attack shows that a more careful analysis should be done in order to instantiate the proposed design method.
7 schema:editor N688d8e07f3c54e0792e61ad48a04adc9
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Naed658cef6944c5e87f0d51ed050294d
11 schema:keywords FSE 2015
12 Register
13 analysis
14 area
15 attacks
16 bits
17 careful analysis
18 cipher
19 complexity
20 cryptanalysis
21 data complexity
22 design method
23 divide
24 evolved technique
25 exhaustive search
26 function
27 hardware implementation
28 implementation
29 influence
30 internal state size
31 key
32 key bits
33 low data complexity
34 main properties
35 method
36 new method
37 non-linear influence
38 order
39 paper
40 properties
41 proposal
42 search
43 security
44 size
45 sprouts
46 state size
47 technique
48 theoretical cryptanalysis
49 time
50 toy version
51 update function
52 validity
53 version
54 whole key
55 schema:name Cryptanalysis of Full Sprout
56 schema:pagination 663-682
57 schema:productId Nb0880c0b0da6463cb778263bd6ff0fb0
58 Nc2580a83d7854d379e4a5499946006cb
59 schema:publisher Ndd5904298cef4285992f94c8e3e1d553
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023908343
61 https://doi.org/10.1007/978-3-662-47989-6_32
62 schema:sdDatePublished 2022-12-01T06:46
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N8a23981117294995b347971f238915a6
65 schema:url https://doi.org/10.1007/978-3-662-47989-6_32
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N13bd658ea93e4ecfa2193e6a791bb57a schema:familyName Robshaw
70 schema:givenName Matthew
71 rdf:type schema:Person
72 N2f9d51c4e990445c86379cc5e2855f79 rdf:first sg:person.013206304341.94
73 rdf:rest rdf:nil
74 N4eabf6a22c5b4e178e18f1d82ef8b08f rdf:first sg:person.011135275143.03
75 rdf:rest N2f9d51c4e990445c86379cc5e2855f79
76 N51fd3239c7bd425d9f319dcff6a90fa0 schema:familyName Gennaro
77 schema:givenName Rosario
78 rdf:type schema:Person
79 N688d8e07f3c54e0792e61ad48a04adc9 rdf:first N51fd3239c7bd425d9f319dcff6a90fa0
80 rdf:rest Nac5eeeca206c497dbd288ee392dc7711
81 N8a23981117294995b347971f238915a6 schema:name Springer Nature - SN SciGraph project
82 rdf:type schema:Organization
83 Nac5eeeca206c497dbd288ee392dc7711 rdf:first N13bd658ea93e4ecfa2193e6a791bb57a
84 rdf:rest rdf:nil
85 Naed658cef6944c5e87f0d51ed050294d schema:isbn 978-3-662-47988-9
86 978-3-662-47989-6
87 schema:name Advances in Cryptology -- CRYPTO 2015
88 rdf:type schema:Book
89 Nb0880c0b0da6463cb778263bd6ff0fb0 schema:name dimensions_id
90 schema:value pub.1023908343
91 rdf:type schema:PropertyValue
92 Nc2580a83d7854d379e4a5499946006cb schema:name doi
93 schema:value 10.1007/978-3-662-47989-6_32
94 rdf:type schema:PropertyValue
95 Ndd5904298cef4285992f94c8e3e1d553 schema:name Springer Nature
96 rdf:type schema:Organisation
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
101 schema:name Data Format
102 rdf:type schema:DefinedTerm
103 sg:person.011135275143.03 schema:affiliation grid-institutes:grid.5328.c
104 schema:familyName Lallemand
105 schema:givenName Virginie
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011135275143.03
107 rdf:type schema:Person
108 sg:person.013206304341.94 schema:affiliation grid-institutes:grid.5328.c
109 schema:familyName Naya-Plasencia
110 schema:givenName María
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94
112 rdf:type schema:Person
113 grid-institutes:grid.5328.c schema:alternateName Inria, Bordeaux, France
114 schema:name Inria, Bordeaux, France
115 rdf:type schema:Organization
 




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


...