A Key-Recovery Attack on 855-round Trivium View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-07-24

AUTHORS

Ximing Fu , Xiaoyun Wang , Xiaoyang Dong , Willi Meier

ABSTRACT

In this paper, we propose a key-recovery attack on Trivium reduced to 855 rounds. As the output is a complex Boolean polynomial over secret key and IV bits and it is hard to find the solution of the secret keys, we propose a novel nullification technique of the Boolean polynomial to reduce the output Boolean polynomial of 855-round Trivium. Then we determine the degree upper bound of the reduced nonlinear boolean polynomial and detect the right keys. These techniques can be applicable to most stream ciphers based on nonlinear feedback shift registers (NFSR). Our attack on 855-round Trivium costs time complexity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{77}$$\end{document}. As far as we know, this is the best key-recovery attack on round-reduced Trivium. To verify our attack, we also give some experimental data on 721-round reduced Trivium. More... »

PAGES

160-184

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-96881-0_6

DOI

http://dx.doi.org/10.1007/978-3-319-96881-0_6

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fu", 
        "givenName": "Ximing", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, 250100, Jinan, China", 
          "id": "http://www.grid.ac/institutes/grid.27255.37", 
          "name": [
            "Institute for Advanced Study, Tsinghua University, 100084, Beijing, China", 
            "School of Mathematics, Shandong University, 250100, Jinan, China", 
            "Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, 250100, Jinan, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Xiaoyun", 
        "id": "sg:person.013413342077.87", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013413342077.87"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute for Advanced Study, Tsinghua University, 100084, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "Institute for Advanced Study, Tsinghua University, 100084, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dong", 
        "givenName": "Xiaoyang", 
        "id": "sg:person.013311564675.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013311564675.26"
        ], 
        "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": "2018-07-24", 
    "datePublishedReg": "2018-07-24", 
    "description": "In this paper, we propose a key-recovery attack on Trivium reduced to 855 rounds. As the output is a complex Boolean polynomial over secret key and IV bits and it is hard to find the solution of the secret keys, we propose a novel nullification technique of the Boolean polynomial to reduce the output Boolean polynomial of 855-round Trivium. Then we determine the degree upper bound of the reduced nonlinear boolean polynomial and detect the right keys. These techniques can be applicable to most stream ciphers based on nonlinear feedback shift registers (NFSR). Our attack on 855-round Trivium costs time complexity \\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^{77}$$\\end{document}. As far as we know, this is the best key-recovery attack on round-reduced Trivium. To verify our attack, we also give some experimental data on 721-round reduced Trivium.", 
    "editor": [
      {
        "familyName": "Shacham", 
        "givenName": "Hovav", 
        "type": "Person"
      }, 
      {
        "familyName": "Boldyreva", 
        "givenName": "Alexandra", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-96881-0_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-96880-3", 
        "978-3-319-96881-0"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2018", 
      "type": "Book"
    }, 
    "keywords": [
      "key-recovery attack", 
      "Boolean polynomials", 
      "secret key", 
      "most stream ciphers", 
      "time complexity", 
      "stream cipher", 
      "feedback shift registers", 
      "attacks", 
      "nonlinear feedback shift registers", 
      "Trivium", 
      "key", 
      "shift register", 
      "right key", 
      "cipher", 
      "bits", 
      "complexity", 
      "technique", 
      "polynomials", 
      "output", 
      "solution", 
      "data", 
      "rounds", 
      "Register", 
      "degree", 
      "experimental data", 
      "paper", 
      "complex Boolean polynomial", 
      "novel nullification technique", 
      "nullification technique", 
      "output Boolean polynomial", 
      "nonlinear boolean polynomial", 
      "Trivium costs time complexity", 
      "costs time complexity", 
      "best key-recovery attack"
    ], 
    "name": "A Key-Recovery Attack on 855-round Trivium", 
    "pagination": "160-184", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1105780992"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-96881-0_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-96881-0_6", 
      "https://app.dimensions.ai/details/publication/pub.1105780992"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:13", 
    "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_231.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-96881-0_6"
  }
]
 

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-319-96881-0_6'

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-319-96881-0_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-96881-0_6'

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-319-96881-0_6'


 

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

129 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-96881-0_6 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N68be91d55dcd4747a15615bbc775e387
4 schema:datePublished 2018-07-24
5 schema:datePublishedReg 2018-07-24
6 schema:description In this paper, we propose a key-recovery attack on Trivium reduced to 855 rounds. As the output is a complex Boolean polynomial over secret key and IV bits and it is hard to find the solution of the secret keys, we propose a novel nullification technique of the Boolean polynomial to reduce the output Boolean polynomial of 855-round Trivium. Then we determine the degree upper bound of the reduced nonlinear boolean polynomial and detect the right keys. These techniques can be applicable to most stream ciphers based on nonlinear feedback shift registers (NFSR). Our attack on 855-round Trivium costs time complexity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{77}$$\end{document}. As far as we know, this is the best key-recovery attack on round-reduced Trivium. To verify our attack, we also give some experimental data on 721-round reduced Trivium.
7 schema:editor Nc60532f6005d49c58e03424319e636d1
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N7c11530b870d405bb8a2fe6c4893d35b
12 schema:keywords Boolean polynomials
13 Register
14 Trivium
15 Trivium costs time complexity
16 attacks
17 best key-recovery attack
18 bits
19 cipher
20 complex Boolean polynomial
21 complexity
22 costs time complexity
23 data
24 degree
25 experimental data
26 feedback shift registers
27 key
28 key-recovery attack
29 most stream ciphers
30 nonlinear boolean polynomial
31 nonlinear feedback shift registers
32 novel nullification technique
33 nullification technique
34 output
35 output Boolean polynomial
36 paper
37 polynomials
38 right key
39 rounds
40 secret key
41 shift register
42 solution
43 stream cipher
44 technique
45 time complexity
46 schema:name A Key-Recovery Attack on 855-round Trivium
47 schema:pagination 160-184
48 schema:productId N46c63a3f29914328b1fc8e32d5b30e87
49 Nbfd2bbdb8ad94c42966defa70858bf4b
50 schema:publisher N3ba5aeffc67b44659f26d190bb358b04
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105780992
52 https://doi.org/10.1007/978-3-319-96881-0_6
53 schema:sdDatePublished 2022-01-01T19:13
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher Nf364aeed1e92485a8366f64ad0a029b5
56 schema:url https://doi.org/10.1007/978-3-319-96881-0_6
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N3ba5aeffc67b44659f26d190bb358b04 schema:name Springer Nature
61 rdf:type schema:Organisation
62 N46c63a3f29914328b1fc8e32d5b30e87 schema:name dimensions_id
63 schema:value pub.1105780992
64 rdf:type schema:PropertyValue
65 N50317cd4407f46ae881f07ea606c30a3 rdf:first sg:person.013311564675.26
66 rdf:rest N642632386df847fca233edbdcb17d9b9
67 N54c431a8d6f84136b6f533dc72cc42f1 rdf:first N70b23a9e59814ed680acd2e87c2b14f6
68 rdf:rest rdf:nil
69 N642632386df847fca233edbdcb17d9b9 rdf:first sg:person.07653531142.18
70 rdf:rest rdf:nil
71 N6573fddae94e47a2908a45338f1081bc schema:familyName Shacham
72 schema:givenName Hovav
73 rdf:type schema:Person
74 N68be91d55dcd4747a15615bbc775e387 rdf:first Nb435f43a0e774fc1afc93edf45e6e06e
75 rdf:rest N80d2dcc89f88460da9f70734a62fbe60
76 N70b23a9e59814ed680acd2e87c2b14f6 schema:familyName Boldyreva
77 schema:givenName Alexandra
78 rdf:type schema:Person
79 N7c11530b870d405bb8a2fe6c4893d35b schema:isbn 978-3-319-96880-3
80 978-3-319-96881-0
81 schema:name Advances in Cryptology – CRYPTO 2018
82 rdf:type schema:Book
83 N80d2dcc89f88460da9f70734a62fbe60 rdf:first sg:person.013413342077.87
84 rdf:rest N50317cd4407f46ae881f07ea606c30a3
85 Nb435f43a0e774fc1afc93edf45e6e06e schema:affiliation grid-institutes:grid.12527.33
86 schema:familyName Fu
87 schema:givenName Ximing
88 rdf:type schema:Person
89 Nbfd2bbdb8ad94c42966defa70858bf4b schema:name doi
90 schema:value 10.1007/978-3-319-96881-0_6
91 rdf:type schema:PropertyValue
92 Nc60532f6005d49c58e03424319e636d1 rdf:first N6573fddae94e47a2908a45338f1081bc
93 rdf:rest N54c431a8d6f84136b6f533dc72cc42f1
94 Nf364aeed1e92485a8366f64ad0a029b5 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
100 schema:name Computation Theory and Mathematics
101 rdf:type schema:DefinedTerm
102 sg:person.013311564675.26 schema:affiliation grid-institutes:grid.12527.33
103 schema:familyName Dong
104 schema:givenName Xiaoyang
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013311564675.26
106 rdf:type schema:Person
107 sg:person.013413342077.87 schema:affiliation grid-institutes:grid.27255.37
108 schema:familyName Wang
109 schema:givenName Xiaoyun
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013413342077.87
111 rdf:type schema:Person
112 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
113 schema:familyName Meier
114 schema:givenName Willi
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
116 rdf:type schema:Person
117 grid-institutes:grid.12527.33 schema:alternateName Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, China
118 Institute for Advanced Study, Tsinghua University, 100084, Beijing, China
119 schema:name Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, China
120 Institute for Advanced Study, Tsinghua University, 100084, Beijing, China
121 rdf:type schema:Organization
122 grid-institutes:grid.27255.37 schema:alternateName Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, 250100, Jinan, China
123 schema:name Institute for Advanced Study, Tsinghua University, 100084, Beijing, China
124 Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, 250100, Jinan, China
125 School of Mathematics, Shandong University, 250100, Jinan, China
126 rdf:type schema:Organization
127 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
128 schema:name FHNW, Windisch, Switzerland
129 rdf:type schema:Organization
 




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


...