Cryptology ePrint Archive: Report 2021/442

How to Backdoor a Cipher

Raluca Posteuca and Tomer Ashur

Abstract: Newly designed block ciphers are required to show resistance against known attacks, e.g., linear and differential cryptanalysis. Two widely used methods to do this are to employ an automated search tool (e.g., MILP, SAT/SMT, etc.) and/or provide a wide-trail argument. In both cases, the core of the argument consists of bounding the transition probability of the statistical property over an isolated non-linear operation, then multiply it by the number of such operations (e.g., number of active S-boxes). In this paper we show that in the case of linear cryptanalysis such strategies can sometimes lead to a gap between the claimed security and the actual one, and that this gap can be exploited by a malicious designer. We introduce RooD, a block cipher with a carefully crafted backdoor. By using the means of the wide-trail strategy, we argue the resistance of the cipher against linear and differential cryptanalysis. However, the cipher has a key-dependent iterative linear approximation over 12 rounds, holding with probability 1. This property is based on the linear hull effect although any linear trail underlying the linear hull has probability smaller than 1.

Category / Keywords: secret-key cryptography / Block cipher Design, 0-correlation linear hulls, linear hull effect, Kleptography, backdoorgraphy

Date: received 5 Apr 2021

Contact author: raluca posteuca at esat kuleuven be, tomer ashur at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20210406:072901 (All versions of this report)

Short URL: ia.cr/2021/442


[ Cryptology ePrint archive ]