kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An efficient SAT-based algorithm for finding short cycles in cryptographic algorithms
KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.ORCID iD: 0000-0001-7382-9408
2018 (English)In: Proceedings of the 2018 IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2018, Institute of Electrical and Electronics Engineers (IEEE), 2018, p. 65-72Conference paper, Published paper (Refereed)
Abstract [en]

The absence of short cycles is a desirable property for cryptographic algorithms that are iterated. Furthermore, as demonstrated by the cryptanalysis of A5, short cycles can be exploited to reduce the complexity of an attack. We present an algorithm which uses a SAT-based bounded model checking for finding all short cycles of a given length. The existing Boolean Decision Diagram (BDD) based algorithms for finding cycles have limited capacity due to the excessive memory requirements of BDDs. The simulation-based algorithms can be applied to larger problem instances, however, they cannot guarantee the detection of all cycles of a given length. The same holds for general-purpose SAT-based model checkers. The presented algorithm can handle cryptographic algorithms with very large state spaces, including important ciphers such as Trivium and Grain-128. We found that these ciphers contain short cycles whose existence, to our best knowledge, was previously unknown. This potentially opens new possibilities for cryptanalysis.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018. p. 65-72
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-238200DOI: 10.1109/HST.2018.8383892ISI: 000436024900009Scopus ID: 2-s2.0-85049955585ISBN: 9781538647318 (print)OAI: oai:DiVA.org:kth-238200DiVA, id: diva2:1264844
Conference
2018 IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2018, The Ritz-CarltonWashington, United States, 30 April 2018 through 4 May 2018
Note

QC 20181121

Available from: 2018-11-21 Created: 2018-11-21 Last updated: 2022-06-26Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Dubrova, Elena

Search in DiVA

By author/editor
Dubrova, Elena
By organisation
Electronic and embedded systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 400 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf