Optimizing guessing strategies for algebraic cryptanalysis with applications to EPCBC. (English) Zbl 1311.94100

Walter, Michael; Bulygin, Stanislav; Buchmann, Johannes

Kutyłowski, Mirosław (ed.) et al., Information security and cryptology. 8th international conference, Inscrypt 2012, Beijing, China, November 28–30, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-38518-6/pbk). Lecture Notes in Computer Science 7763, 175-197 (2013).

Summary: In this paper we demonstrate how to use mixed integer linear programming to optimize guessing strategies for algebraic cryptanalysis with applications to the block cipher EPCBC. Using our optimized guessing strategy we are able to attack 5 rounds of EPCBC-96 and 8 rounds of EPCBC-48 faster than brute force using one and two known plaintexts resp. Finally, we are able to identify a class of weak keys for which the attack is faster than brute force for up to 7 rounds of EPCBC-96. Alongside results on EPCBC we believe that the proposed technique of optimized guessing is a useful tool in a more general context of algebraic cryptanalysis.
For the entire collection see [Zbl 1263.94006].

MSC:

94A60	Cryptography
90C11	Mixed integer programming

Keywords:

algebraic cryptanalysis; lightweight cryptography; guessing strategies; mixed integer linear programming

Software:

LBlock; SageMath; spongent ; EPCBC; CryptoMiniSat