New Applications of Dierential Bounds of the SDS Structure?

Abstract. In this paper, we present some new applications of the bounds for the dier-ential probability of a SDS (Substitution-Diusion-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 f0; 1g-matrices of size nn. These structures are useful because they can be eciently implemented in hardware. We prove a bound on f0; 1g-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 f0; 1g-matrices where n 5 are used because previous results only hold for MDS and almost-MDS diusion matrices. Based on our bound, we also show that the f0; 1g-matrix used in E2 is almost-optimal among f0; 1g-matrices. Using Park's result, we prove dierential 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