Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges

Hossein Hadipour*, Maria Eichlseder

*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in Buch/Bericht/KonferenzbandBeitrag in einem KonferenzbandBegutachtung


The guess-and-determine technique is one of the most widely used techniques in cryptanalysis to recover unknown variables in a given system of relations. In such attacks, a subset of the unknown variables is guessed such that the remaining unknowns can be deduced using the information from the guessed variables and the given relations. This idea can be applied in various areas of cryptanalysis such as finding the internal state of stream ciphers when a sufficient amount of output data is available, or recovering the internal state and the secret key of a block cipher from very few known plaintexts. Another important application is the key-bridging technique in key-recovery attacks on block ciphers, where the attacker aims to find the minimum number of required sub-key guesses to deduce all involved sub-keys via the key schedule. Since the complexity of the guess-and-determine technique directly depends on the number of guessed variables, it is essential to find the smallest possible guess basis, i.e., the subset of guessed variables from which the remaining variables can be deduced. In this paper, we present Autoguess, an easy-to-use general tool to search for a minimal guess basis. We propose several new modeling techniques to harness SAT/SMT, MILP, and Gröbner basis solvers. We demonstrate their usefulness in guess-and-determine attacks on stream ciphers and block ciphers, as well as finding key-bridges in key recovery attacks on block ciphers. Moreover, integrating our CP models for the key-bridging technique into the previous CP-based frameworks to search for distinguishers, we propose a unified and general CP model to search for key recovery friendly distinguishers which supports both linear and nonlinear key schedules.
TitelApplied Cryptography and Network Security - 20th International Conference, ACNS 2022, Proceedings
Redakteure/-innenGiuseppe Ateniese, Daniele Venturi
Herausgeber (Verlag)Springer
ISBN (Print)9783031092336
PublikationsstatusVeröffentlicht - 2022
Veranstaltung20th International Conference on Applied Cryptography and Network Security: ACNS 2022 - Italy, Roma, Italien
Dauer: 20 Juni 202223 Juni 2022
Konferenznummer: 20


NameLecture Notes in Computer Science


Konferenz20th International Conference on Applied Cryptography and Network Security
KurztitelACNS 2022

ASJC Scopus subject areas

  • Theoretische Informatik und Mathematik
  • Theoretische Informatik
  • Allgemeine Computerwissenschaft

Fields of Expertise

  • Information, Communication & Computing


Untersuchen Sie die Forschungsthemen von „Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren