Advanced Techniques in Symmetric Key Cryptanalysis

Abstract

Symmetric key cryptographic primitives are essential tools used extensively in daily digital interactions. These primitives are mainly designed to provide three key services: ensuring data confidentiality, maintaining data integrity, and verifying the authenticity of data sources. The primary types of symmetric key primitives that deliver these services include block ciphers, stream ciphers, hash functions, message authentication codes, and authenticated encryption with associated data. This thesis mainly explores the security analysis of hash functions, several block ciphers, and stream ciphers using some advanced cryptanalytic techniques.

We begin by examining the collision security of a hash function, specifically under the assumption that the underlying compression functions are collision-resistant. This characteristic is termed the collision-resistance preserving property of a hash function. Notably, both the Merkle-Damgård and Merkle tree hash structures exhibit this property, prompting the question of whether it is possible to reduce the number of underlying compression function calls while maintaining the collision-resistance preserving property. In pursuit of this question, we prove that for an ℓn-to-sn-bit collision-preserving hash function, designed using r tn-to-n-bit compression function calls, it must hold that r ≥ ⌈(ℓ − s)/(t − 1)⌉, assuming all operations other than the compression function are linear. Shifting our focus, we delve into advanced techniques for enhanced cryptanalysis of block and stream ciphers. Initially, we concentrate on the impossible differential (ID) and zero correlation (ZC) attacks, which are pivotal cryptanalytic methods for block ciphers. We introduce an advanced, unified constraint programming (CP) approach based on satisfiability for identifying ID distinguishers in ARX and AndRX ciphers alongside a similar method for identifying ZC distinguishers. Furthermore, we extend our novel model to formulate a unified optimization problem that incorporates the distinguisher and key recovery for AndRX designs. Our approach not only enhances ID attacks but also unveils new distinguishers for various ciphers, including SIMON, SPECK, Simeck, ChaCha, Chaskey, LEA, and SipHash. Another significant cryptanalytic technique, particularly applicable to the analysis of block and stream ciphers, is the division property—an advanced version of integral cryptanalysis. Here, we explore the feasibility of the MILP method for the bit-based division property using three subsets

(BDPT) propagation in ciphers with complex linear layers. We apply our novel method to discover integral distinguishers based on BDPT for the SIMON, SIMON(102), PRINCE, MANTIS, PRIDE, and KLEIN block ciphers. The integral distinguishers identified by our method are superior to or consistent with the longest existing distinguishers. Finally, we investigate the cube attack, a powerful cryptanalytic technique against stream ciphers. We study the NIST lightweight 3rd round candidate Grain-128AEAD through the lens of division property-based cube attacks. Initially, we introduce some effective cubes and construct an algorithm to identify conditional key bits for these cubes in Grain-128AEAD. Subsequently, we employ the three-subset division property without unknown subsets based cube attacks to recover exact superpolies for Grain-128AEAD in the weak-key setting, yielding improved results.