Experiments on the Distribution of Offsets of Collisions

This program check the distribution of offsets of collisions on the computation chains when searching for collisions. The setting is as follows: we evaluate 2^t chains of length 2^s by iterating an n-bit random mapping f. At each offset on the computation chain, there might be some collisions. A question is "How is the collisions distributed along the chains". To answer this question, we perform experiments counting the number of collisions on each offset.

Experiments

We simulate the n-bit random mapping f using chopped AES-128 (obtained by fixing an arbitrary key and 128-n bits of the input and take n bits as the output, where n is in {12, ..., 32}). We check the distribution of collision offsets in the following cases:

• Case 1: t + 2s > n, in particular
  • #define s ((n + 3) / 4)
  • #define t (2 * (n + 2) / 3)
• Case 2: t + 2s < n, in particular
  • #define s ((n + 7) / 8)
  • #define t ((n + 2) / 3)
    (in this particular case, no collisions is found because it requires 2t + s >= n to find the same-offset collision)
• Case 3: t + 2s slightly larger or less than n, in particular
  • #define s ((n + 7) / 8)
  • #define t (5 * s)
• Case 4: t + 2s almost equals to n, in particular
  • #define s ((n + 3) / 4)
  • #define t ((n + 1) / 2)

We directly use implementations of AES-128 included in IPPCP (Cryptography for Intel Intergrated Performance Primitives) in IPP (Intel Integrated Performance Primitives). Thus, one may need to install IPP and IPPCP to compile and run this experiment.

• This program has been tested on the following platforms:

  • Ubuntu 16.04.3 LTS (GNU/Linux 4.10.0-33-generic x86_64) + g++ (GCC) 5.4.0 + icpc (ICC) 17.0.4

• Compiling:

  • two parameters can be defined manually during compiling:
    • nmin: the minimum value of n (default 12)
    • nmax: the maximum value of n (default 32)
  • two parameters must be defined in the source file declares.h
    • t: the binary logarithm of the number of evaluated chains
    • s: the binary logarithm of the length of evaluated chains
  • example:

    • make

    • make nmin=12 nmax=28

Results

As pointed out by authors in DL16, when t + 2s <= n, each evaluated chain is not expected to collide with more than one different chain. In this case, the collision offset is roughly uniformly distributed in the interval [0, 2^s]. On the other hand, when t + 2s > n, there is an obvious decrease on the number of collisions with the increase of offsets. Note that, there is a more obvious decrease on the number of images with the increase of offsets (due to the entropy loss phenomenon).

The following figures show examples of the results obtained in Case 1: t + 2s > n, from which we can see the obvious decrease on the number of collisions with the increase of offsets when t + 2s is larger than n (plotted using matplotlib):

The following figures show examples of the results obtained in Case 3: t + 2s slightly larger or less than n, from which we can see the decrease (resp. roughly uniformly distribution) of the number of collisions with the increase of offsets when t + 2s is slightly larger than (resp. less than) n (plotted using matplotlib):

References

[DL16] Itai Dinur and Gaëtan Leurent. Improved Generic Attacks Against Hash-Based MACs and HAIFA. Algorithmica, November 2016. https://hal.inria.fr/hal-01407953/document

[BGW18] Zhenzhen Bao, Jian Guo, and Lei Wang. Functional Graphs and Their Applications in Generic Attacks on Iterated Hash Constructions. IACR Trans. Symmetric Cryptol. 2018(1): 201-253 (2018). https://eprint.iacr.org/2018/374.pdf