Cryptanalysis of FORK-256

This page is dedicated to the hash function FORK-256 and its cryptanalysis. It is meant as an online supplementary resource to our research on the security of FORK-256.

What is FORK-256?

FORK-256 is a dedicated hash function designed by Deukjo Hong, Donghoon Chang, Jaechul Sung, Sangjin Lee, Seokhie Hong, Jaesang Lee, Dukjae Moon and Sungtaek Chee.

It was meant as a replacement for SHA-256 and so it is an iterated hash based on Merkle-Damgard principle. In each iteration a compression function that updates 256 bits of chaining variables based on 512 bits of the message is called.

The main differences between FORK-256 and SHA family can be summarised as

• FORK-256 is built using target-heavy Unbalanced Feistel Networks
• FORK-256 uses four short (8 steps) parallel branches

Documentation for FORK-256 was presented at

• 2005 NIST Hash Workshop
• FSE'2006

Implementation based on the reference code included in the paper is here:

• implementation of the compression function [view or download fork.c]
• test program [view or download testfork.c] (requires fork.c)

Cryptanalysis of FORK-256

Theory Our security analysis of FORK-256 is presented in the IACR e-print paper Weaknesses of the FORK-256 compression function. The foundation of our analysis is the observation that in some special circumstances we can prevent differences from propagating to other registers in a single step and this allows us to build a differential path with very restricted propagation of differences.

Summarizing, our analysis shows that

1. it is straightforward to obtain collisions for a variant of FORK-256 reduced to two rounds,
2. it is very easy (computationally) to find a common IV value and pairs of messages that result in the difference confined to only 108 bits (registers C,D,E and part of B contain differences, registers A,F,G,H and part of B are equal). This may be an important weakness if one wants to use truncated FORK hashes,
3. weights of differences in registers B,C,D,E have distribution close to binomial with mean equal 54,
4. it is possible to practically get very low weight differences (using modest computational resources we were able to find a common IV and a pair of messages that yield outputs differing on only 28 bits)
5. it is theoretically possible to find collisions for the compression function of FORK-256 in around 2^126.6 evaluations of the compression function (possibly even 2^125) using only small amount of memory (around 2^23 32-bit words)

You can also see slides of our Asiacrypt'2006 Rump Session presentation

Practice We wrote a C program that implements the algorithm described in sections 7.2-7.3 of the paper and used it to run some tests.

The program is available for download or it can be viewed online.

Below are some comments on technical details of the program.

• When compiled with the flag -DUSE_HASH_TABLE, the program follows quite closely the description of the algorithm given in sections 7.2-7.3. However, certain machines that have slower access to large memory that doesn't fit into cache (e.g. Intel) often do not benefit from this, so sometimes it is faster to use the version without hash table, which, although theoretically slower, may work faster on your machine in practice.
• To minimize memory requirements, the hash table is not implemented exactly as how it is described in the paper: the hash table only does a quick check to eliminate some things that definitely don't lead to an allowable A_6 (this is different than our paper where the hash table eliminates *all* values that don't lead to an allowable A_6). There are some false reports that get through and are only eliminated in the "if (E7_1 == E7_2)" check (around the line 437). With a hash table size of 2^25, about 1 out 10 false reports get by our hash table check. We had to do it this way to optimize speed because otherwise the memory requirements are larger and the memory access time incurs a significant speed penalty.
• We have tested our code with gcc and Intel C Compiler and for Pentium 4 we have observed a significant speed difference, so if you have a Linux machine, it is worth to download and use ICC for better results.

Our best computational result so far is the pair of messages yielding outputs different by 28 bits.

  IV 6a09e667 db1bb914 3c6ef372 a54ff53a 510e527f 767b0824 66410f7d 90f7ce64

   M 85a83e55 91d3ca9d a6c2facb 027afd32 000000cb 00000000 9d4a6aba 00000000
     e649c148 4606ae35 6efb18d8 2d6ade8f 1dcb6936 ec995db1 d2ad257b 730f5bb4

  M' 85a83e55 91d3ca9d a6c2facb 027afd32 000000cb 00000000 9d4a6aba 00000000
     e649c148 4606ae35 6efb18d8 2d6ade8f 40c36936 ec995db1 d2ad257b 730f5bb4
 
diff 00000000 8c300000 1d010204 52520104 c0908122 00000000 00000000 00000000

We plan to run more searches in the near future. If you happen to find anything better than this, we would love to know!

Contact us...

If you have any questions, comments or suggestions about the webpage, program or paper, feel free to contact us:

• Scott Contini scontini at ics.mq.edu.au
• Krystian Matusiewicz kmatus at ics.mq.edu.au
• Josef Pieprzyk josef at ics.mq.edu.au

• Olivier Billet olivier.billet at orange-ftgroup.com
• Thomas Peyrin thomas.peyrin at orange-ftgroup.com