Related-Key Linear Hull Distinguishers for Key-Alternating Block Ciphers

Abstract : In this paper, we describe work in progress on novel related-key distinguishers applicable to key-alternating block ciphers, a wide class of symmetric-key primitives. This class includes the AES finalists Rijndael and Serpent as well as many other block ciphers having SPN structure, including many Feistel networks. Unlike the known differential related-key techniques, our distinguishers are essentially of linear nature and make use of how exactly that linear hulls of key-alternating ciphers are structured when encrypting under different keys. By partitioning the linear trails contained in these hulls into a " signal " part (known enumerated trails) and a " noise " part (the unknown remainder of the hull), we develop statistical models for differences and sums of linear hull correlations when evaluated under different keys. We then observe that for concrete key-alternating ciphers, the differences or sums of correlations tend to differ from the ideal behaviour, admitting a structural distinguisher. Unlike the key-difference invariant bias technique from ASIACRYPT 2013, our models allow for an intersection of the key difference with active bits of trails contained in the linear hull under consideration. This opens up possibilities for more powerful and generally applicable distinguish-ers.