The higher-order meet-in-the-middle attack and its application to the Camellia block cipher

The Camellia block cipher has a 128-bit block length, a user key of 128, 192 or 256 bits long, and a total of 18 rounds for a 128-bit key and 24 rounds for a 192 or 256-bit key. It is a Japanese CRYPTREC-recommended e-government cipher, a European NESSIE selected cipher and an ISO international standard. The meet-in-the-middle attack is a technique for analysing the security of a block cipher. In this paper, we propose an extension of the meet-in-the-middle attack, which we call the higher-order meet-in-the-middle (HO-MitM) attack; the core idea of the HO-MitM attack is to use multiple plaintexts to cancel some key-dependent component(s) or parameter(s) when constructing a basic unit of “value-in-the-middle”. Then we introduce a novel approach, which combines integral cryptanalysis with the meet-in-the-middle attack, to construct HO-MitM attacks on 10-round Camellia with the FL/FL−1FL/FL−1 functions under 128 key bits, 11-round Camellia with the FL/FL−1FL/FL−1 functions under 192 key bits and 12-round Camellia with the FL/FL−1FL/FL−1 functions under 256 key bits. Finally, we apply an existing approach to construct HO-MitM attacks on 14-round Camellia without the FL/FL−1FL/FL−1 functions under 192 key bits and 16-round Camellia without the FL/FL−1FL/FL−1 functions under 256 key bits. The HO-MitM attack can potentially be used to cryptanalyse other block ciphers.