The differential analysis of S-functions. (English) Zbl 1290.94112

Biryukov, Alex (ed.) et al., Selected areas in cryptography. 17th international workshop, SAC 2010, Waterloo, Ontario, Canada, August 12–13, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-19573-0/pbk). Lecture Notes in Computer Science 6544, 36-56 (2011).
Summary: An increasing number of cryptographic primitives use operations such as addition modulo \(2^n\), multiplication by a constant and bitwise Boolean functions as a source of non-linearity. In NIST’s SHA-3 competition, this applies to 6 out of the 14 second-round candidates. In this paper, we generalize such constructions by introducing the concept of S-functions. An S-function is a function that calculates the \(i\)-th output bit using only the inputs of the \(i\)-th bit position and a finite state \(S[i]\). Although S-functions have been analyzed before, this paper is the first to present a fully general and efficient framework to determine their differential properties. A precursor of this framework was used in the cryptanalysis of SHA-1. We show how to calculate the probability that given input differences lead to given output differences, as well as how to count the number of output differences with non-zero probability. Our methods are rooted in graph theory, and the calculations can be efficiently performed using matrix multiplications.
For the entire collection see [Zbl 1208.94008].


94A60 Cryptography
Full Text: DOI


[1] Anderson, R.J. (ed.): FSE 1993. LNCS, vol. 809. Springer, Heidelberg (1994)
[2] Aumasson, J.-P., Calik, C., Meier, W., Ozen, O., Phan, R.C.-W., Varıcı, K.: Improved Cryptanalysis of Skein. Cryptology ePrint Archive, Report 2009/438 (2009), http://eprint.iacr.org/
[3] Aumasson, J.-P., Calik, C., Meier, W., Özen, O., Phan, R.C.-W., Varıcı, K.: Improved Cryptanalysis of Skein. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 542–559. Springer, Heidelberg (2009) · Zbl 1267.94034
[4] Aumasson, J.-P., Henzen, L., Meier, W., Phan, R.C.-W.: SHA-3 proposal BLAKE. Submission to the NIST SHA-3 Competition (Round 2) (2008)
[5] Bernstein, D.J.: The Salsa20 Family of Stream Ciphers. In: Robshaw, M.J.B., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol. 4986, pp. 84–97. Springer, Heidelberg (2008) · Zbl 05297172
[6] Bernstein, D.J.: CubeHash specification (2.B.1). Submission to the NIST SHA-3 Competition (Round 2) (2009)
[7] Biham, E., Shamir, A.: Differential Cryptanalysis of DES-like Cryptosystems. J. Cryptology 4(1), 3–72 (1991) · Zbl 0729.68017
[8] Bresson, E., Canteaut, A., Chevallier-Mames, B., Clavier, C., Fuhr, T., Gouget, A., Icart, T., Misarsky, J.-F., Naya-Plasencia, M., Paillier, P., Pornin, T., Reinhard, J.-R., Thuillet, C., Videau, M.: Shabal, a Submission to NIST’s Cryptographic Hash Algorithm Competition. Submission to the NIST SHA-3 Competition (Round 2) (2008)
[9] Chittenden, E.W.: On the number of paths in a finite partially ordered set. The American Mathematical Monthly 54(7), 404–405 (1947) · Zbl 0030.08204
[10] Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, Heidelberg (2002) · Zbl 1065.94005
[11] Daum, M.: Narrow T-Functions. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 50–67. Springer, Heidelberg (2005)
[12] De Cannière, C., Rechberger, C.: Finding SHA-1 Characteristics: General Results and Applications. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 1–20. Springer, Heidelberg (2006) · Zbl 1172.94572
[13] Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: The Skein Hash Function Family. Submission to the NIST SHA-3 Competition (Round 2) (2009)
[14] Gligoroski, D., Klima, V., Knapskog, S.J., El-Hadedy, M., Amundsen, J., Mjølsnes, S.F.: Cryptographic Hash Function BLUE MIDNIGHT WISH. Submission to the NIST SHA-3 Competition (Round 2) (2009)
[15] Hong, S., Hong, D., Ko, Y., Chang, D., Lee, W., Lee, S.: Differential Cryptanalysis of TEA and XTEA. In: Lim, J.I., Lee, D.H. (eds.) ICISC 2003. LNCS, vol. 2971, pp. 402–417. Springer, Heidelberg (2004) · Zbl 1092.94507
[16] Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley, Reading (2006) · Zbl 0847.68065
[17] Huffman, D.: The synthesis of sequential switching circuits. Journal of the Franklin Institute 257(3), 161–190 (1954) · Zbl 0166.27201
[18] Indesteege, S., Preneel, B.: Practical Collisions for EnRUPT. Journal of Cryptology 23(3) (2010) (to appear) · Zbl 1209.68221
[19] Klimov, A., Shamir, A.: Cryptographic Applications of T-Functions. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 248–261. Springer, Heidelberg (2004) · Zbl 1081.94030
[20] Leurent, G., Bouillaguet, C., Fouque, P.-A.: SIMD Is a Message Digest. Submission to the NIST SHA-3 Competition (Round 2) (2009)
[21] Lipmaa, H.: On Differential Properties of Pseudo-Hadamard Transform and Related Mappings. In: Menezes, A., Sarkar, P. (eds.) INDOCRYPT 2002. LNCS, vol. 2551, pp. 48–61. Springer, Heidelberg (2002) · Zbl 1033.94532
[22] Lipmaa, H., Moriai, S.: Efficient Algorithms for Computing Differential Properties of Addition. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 336–350. Springer, Heidelberg (2002) · Zbl 1073.68635
[23] Lipmaa, H., Wallén, J., Dumas, P.: On the Additive Differential Probability of Exclusive-Or. In: Roy, B.K., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 317–331. Springer, Heidelberg (2004) · Zbl 1079.68551
[24] Lyon, R.F.: Two’s Complement Pipeline Multipliers. IEEE Transactions on Communications 24(4), 418–425 (1976)
[25] Lyon, R.F.: A bit-serial architectural methodology for signal processing. In: Gray, J.P. (ed.) VLSI 1981, pp. 131–140. Academic Press, London (1981)
[26] Matsui, M., Yamagishi, A.: A New Method for Known Plaintext Attack of FEAL Cipher. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 81–91. Springer, Heidelberg (1993) · Zbl 0787.94019
[27] Mealy, G.H.: A method for synthesizing sequential circuits. Bell Systems Technical Journal 34, 1045–1079 (1955)
[28] Menezes, A., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996) · Zbl 0868.94001
[29] Moore, E.F.: Gedanken experiments on sequential machines. Automata Studies, 129–153 (1956)
[30] Mouha, N., De Cannière, C., Indesteege, S., Preneel, B.: Finding Collisions for a 45-Step Simplified HAS-V. In: Youm, H.Y., Yung, M. (eds.) WISA 2009. LNCS, vol. 5932, pp. 206–225. Springer, Heidelberg (2009) · Zbl 05649645
[31] National Institute of Standards and Technology. Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family. Federal Register 27(212), 62212–62220 (2007), http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf (October 17, 2008)
[32] Needham, R.M., Wheeler, D.J.: Tea extensions. Computer Laboratory, Cambridge University, England (1997), http://www.movable-type.co.uk/scripts/xtea.pdf
[33] O’Neil, S., Nohl, K., Henzen, L.: EnRUPT Hash Function Specification. Submission to the NIST SHA-3 Competition (Round 1) (2008)
[34] Schneier, B., Kelsey, J., Whiting, D., Wagner, D., Hall, C., Ferguson, N.: The Twofish encryption algorithm: a 128-bit block cipher. John Wiley & Sons, Inc., New York (1999) · Zbl 0929.94018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.