Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges
Hosein Hadipour, Maria Eichlseder
Institut für Angewandte Informationsverarbeitung und Kommunikationstechnologie (7050)
Publikation: Arbeitspapier › Working paper
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.
Veröffentlicht - 22 Nov 2021
Publikationsreihe
Cryptology ePrint Archive
Herausgeber (Verlag)
IACR
Theoretische Informatik und Mathematik
Zugriff auf Dokument
https://eprint.iacr.org/2021/1529Lizenz: CC BY
Hadipour, H., & Eichlseder, M. (2021). Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges. (Cryptology ePrint Archive). https://eprint.iacr.org/2021/1529
Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges. / Hadipour, Hosein; Eichlseder, Maria.
2021. (Cryptology ePrint Archive).
Hadipour, H & Eichlseder, M 2021 'Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges' Cryptology ePrint Archive. <https://eprint.iacr.org/2021/1529>
Hadipour H, Eichlseder M. Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges. 2021 Nov 22. (Cryptology ePrint Archive).
Hadipour, Hosein ; Eichlseder, Maria. / Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges. 2021. (Cryptology ePrint Archive).
@techreport{f712b92669ba4d0b8be918b171c44800,
title = "Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges",
abstract = "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{\"o}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.",
keywords = "Guess and Determine, secret-key cryptography, Groebner basis, MILP, Lightweight block cipher, SAT, CP, SMT, Key-Bridging",
author = "Hosein Hadipour and Maria Eichlseder",
series = "Cryptology ePrint Archive",
publisher = "IACR ",
institution = "IACR ",
T1 - Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges
AU - Hadipour, Hosein
AU - Eichlseder, Maria
N2 - 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.
AB - 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.
KW - Guess and Determine
KW - secret-key cryptography
KW - Groebner basis
KW - MILP
KW - Lightweight block cipher
KW - SAT
KW - CP
KW - SMT
KW - Key-Bridging
T3 - Cryptology ePrint Archive
BT - Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges