Paper 2014/895

Analysis of ARX Functions: Pseudo-linear Methods for Approximation, Differentials, and Evaluating Diffusion

Kerry A. McKay and Poorvi L. Vora

Abstract

This paper explores the approximation of addition mod $2^n$ by addition mod $2^w$, where $1\le w\le n$, in ARX functions that use large words (e.g., 32-bit words or 64-bit words). Three main areas are explored. First, \emph{pseudo-linear approximations} aim to approximate the bits of a $w$-bit window of the state after some rounds. Second, the methods used in these approximations are also used to construct truncated differentials. Third, branch number metrics for diffusion are examined for ARX functions with large words, and variants of the differential and linear branch number characteristics based on pseudo-linear methods are introduced. These variants are called \emph{effective differential branch number} and \emph{effective linear branch number}, respectively. Applications of these approximation, differential, and diffusion evaluation techniques are demonstrated on Threefish-256 and Threefish-512.