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

Hossein Hadipour*, Maria Eichlseder

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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.
Original languageEnglish
Title of host publicationApplied Cryptography and Network Security - 20th International Conference, ACNS 2022, Proceedings
EditorsGiuseppe Ateniese, Daniele Venturi
Place of PublicationCham
Number of pages21
ISBN (Print)9783031092336
Publication statusPublished - 2022
Event20th International Conference on Applied Cryptography and Network Security: ACNS 2022 - Italy, Roma, Italy
Duration: 20 Jun 202223 Jun 2022
Conference number: 20

Publication series

NameLecture Notes in Computer Science


Conference20th International Conference on Applied Cryptography and Network Security
Abbreviated titleACNS 2022
Internet address


  • Guess and Determine
  • secret-key cryptography
  • Groebner basis
  • MILP
  • Lightweight block cipher
  • SAT
  • CP
  • SMT
  • Key-Bridging
  • AES Block Cipher
  • SKINNY Block Cipher
  • ZUC Stream Cipher
  • Stream Ciphers
  • Gröbner basis
  • Guess & determine

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science
  • Computer Science(all)

Fields of Expertise

  • Information, Communication & Computing


Dive into the research topics of 'Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges'. Together they form a unique fingerprint.

Cite this