Electronic Thesis/Dissertation


Analysis of ARX Round Functions in Secure Hash Functions Open Access

Downloadable Content

Download PDF

A new design paradigm for symmetric-key design primitives, such as hash functions and block ciphers, is the Addition-Rotation-XOR (ARX) paradigm. ARX functions rely on the combination of addition modulo 2^n, word rotation and exclusive-or to increase the difficulty of applying traditional linearity-based attacks. This work provides contributions in the analysis of ARX functions. This dissertation introduces a new analytic technique, pseudo-linear cryptanalysis, which takes advantage of linear properties of ARX-functions over the groups Z_2^n and Z_{2^n}. This is in contrast to traditional linear analysis, which has largely focused on linearity over Z_2. Pseudo-linear cryptanalysis can be used on any ARX-based symmetric primitive, and is particularly useful for block ciphers and iterative hash functions containing round functions. The dissertation also presents a variant that can be used for differential attacks, and extends the branch number diffusion metric for ARX ciphers that use large words. Secure hash functions are among those primitives that may be built on ARX-functions. The National Institute of Standards and Technology is currently in the process of selecting the next US standard secure hash algorithm, SHA-3, which will be used in everyday applications such as secure online sessions and password-based authentication. Two of the five finalists in the SHA-3 competition are based on ARX functions. This dissertation applies pseudo-linear cryptanalysis, truncated differentials, and new ideas for computing branch numbers to SHA-3 finalist Skein. It also presents improved attacks on second-round SHA-3 candidate CubeHash as well as structural analysis of its symmetry classes.

Author Language Keyword Date created Type of Work Rights statement GW Unit Degree Advisor Committee Member(s) Persistent URL