Full analysis of PRINTcipher with respect to invariant subspace attack: efficient key recovery and countermeasures
In this paper we investigate the invariant property of PRINTcipher initially discovered by Leander et al. in their CRYPTO 2011 paper. We provide a complete study of the attack and show that there exist 64 families of weak keys for PRINTcipher48 and as many as 115,669 for PRINTcipher96. Moreover, we show that searching the weak key space may be substantially sped up by splitting the search process into two consecutive steps. We show that for many classes of weak keys, key recovery can be done with very small time complexity in the chosen/known plaintext scenario. In fact, at least \(2^{45}\) weak keys can be recovered in less than 10s per key on a single PC. Still, effective countermeasures exist against the attack. On the methodological level, the method of finding all weak key families has value on its own. It is based on Mixed Integer Linear Programming and can be adapted to solving other interesting problems on similar ciphers.
printcipher key recovery weak keys mixed integer linear programming invariant coset attack chosen plaintext attack 94a60 68p25 90c10