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-09-02T16:13", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_277.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 Nea118c675f494c46a219e00d6ea0b81f
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 Nb175b9a8c7f745c0b0e89d0ff2a6782c
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N4f80040399fe4b3c8d1ef9f4aae87e3e
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 N2d56c1a4bef44f64a010faf0275ef012
58 Nc2c163bcb7174e7daa192dc056c4cbd8
59 schema:publisher N2b42ba214e9949d1bdc0df0839f244d4
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-09-02T16:13
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N037df474e78347889e434c94f213785f
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 N037df474e78347889e434c94f213785f schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N2b42ba214e9949d1bdc0df0839f244d4 schema:name Springer Nature
72 rdf:type schema:Organisation
73 N2d56c1a4bef44f64a010faf0275ef012 schema:name doi
74 schema:value 10.1007/978-3-662-47989-6_32
75 rdf:type schema:PropertyValue
76 N4f80040399fe4b3c8d1ef9f4aae87e3e schema:isbn 978-3-662-47988-9
77 978-3-662-47989-6
78 schema:name Advances in Cryptology -- CRYPTO 2015
79 rdf:type schema:Book
80 N844b53b927c045b09acbe11b229e8518 schema:familyName Gennaro
81 schema:givenName Rosario
82 rdf:type schema:Person
83 Nad86f36e84034a5b9189504ec9b9d2ab rdf:first sg:person.013206304341.94
84 rdf:rest rdf:nil
85 Nb175b9a8c7f745c0b0e89d0ff2a6782c rdf:first N844b53b927c045b09acbe11b229e8518
86 rdf:rest Nc9b27bf53c344dad8cb05f4329c65b04
87 Nc2c163bcb7174e7daa192dc056c4cbd8 schema:name dimensions_id
88 schema:value pub.1023908343
89 rdf:type schema:PropertyValue
90 Nc9b27bf53c344dad8cb05f4329c65b04 rdf:first Neb090c0611a84df3b1a813d29de737b6
91 rdf:rest rdf:nil
92 Nea118c675f494c46a219e00d6ea0b81f rdf:first sg:person.011135275143.03
93 rdf:rest Nad86f36e84034a5b9189504ec9b9d2ab
94 Neb090c0611a84df3b1a813d29de737b6 schema:familyName Robshaw
95 schema:givenName Matthew
96 rdf:type schema:Person
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)


...