Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / ARX, block ciphers, hash functions, cryptanalysis

Date: received 29 Oct 2014, last revised 30 Oct 2014

Contact author: kerry at gwmail gwu edu

Available format(s): PDF | BibTeX Citation

Version: 20141030:134319 (All versions of this report)

Short URL: ia.cr/2014/895

Discussion forum: Show discussion | Start new discussion