Cryptology ePrint Archive: Report 2012/085

Study of the invariant coset attack on PRINTcipher: more weak keys with practical key recovery

Stanislav Bulygin and Michael Walter

Abstract: In this paper we investigate the invariant property of PRINTcipher first discovered by Leander et al. in their CRYPTO 2011 paper. We provide a thorough study and show that there exist 64 families of weak keys for PRINTcipher--48 and many more for PRINTcipher--96. Moreover, we show that searching the weak key space may be substantially sped up by splitting the search into two consecutive steps. We show that for many classes of weak keys key recovery can be done in a matter of minutes in the chosen/known plaintext scenario. In fact, at least $2^{45}$ weak keys can be recovered in less than 20 minutes per key on a single PC using only a few chosen and one known plaintext(s). We provide detailed treatment of the methods and put them in a more general context that opens new interesting directions of research for PRESENT-like ciphers.

Category / Keywords: secret-key cryptography / PRINTcipher, invariant coset attack, mixed integer linear programming, weak keys, chosen plaintext attack, key recovery

Date: received 23 Feb 2012, last revised 15 May 2012

Contact author: Stanislav Bulygin at cased de

Available format(s): PDF | BibTeX Citation

Note: Section 3.3 on finding sizes of weak key families and key recovery complexity is substantially revised; data for PRINTcipher-96 is added.

Version: 20120515:143609 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]