Paper 2008/395

New Applications of Differential Bounds of the SDS Structure

Jiali Choy and Khoongming Khoo

Abstract

In this paper, we present some new applications of the bounds for the differential probability of a SDS (Substitution-Diffusion-Substitution) structure by Park et al. at FSE 2003. Park et al. have applied their result on the AES cipher which uses the SDS structure based on MDS matrices. We shall apply their result to practical ciphers that use SDS structures based on {0,1}-matrices of size n times n. These structures are useful because they can be efficiently implemented in hardware. We prove a bound on {0,1}-matrices to show that they cannot be MDS and are almost-MDS only when n=2,3 or 4. Thus we have to apply Park's result whenever {0,1}-matrices where $n \geq 5$ are used because previous results only hold for MDS and almost-MDS diffusion matrices. Based on our bound, we also show that the {0,1}-matrix used in E2 is almost-optimal among {0,1}-matrices. Using Park's result, we prove differential bounds for E2 and an MCrypton-like cipher, from which we can deduce their security against boomerang attack and some of its variants. At ICCSA 2006, Khoo and Heng constructed block cipher-based universal hash functions, from which they derived Message Authentication Codes (MACs) which are faster than CBC-MAC. Park's result provides us with the means to obtain a more accurate bound for their universal hash function. With this bound, we can restrict the number of MAC's performed before a change of MAC key is needed.

Note: This is a corrected version of a paper presented at the ISC 2008 conference. It was claimed in the conference paper that we proved the security of MCrypton against boomerang attack. In this paper, we corrected the claim to say that we prove the security of a variant of MCrypton, which we call MCrypton-x, against boomerang attack. Moreover, some typos were also corrected.