[Cryptography] Cryptanalysis: dealing with billions of data

[Pierre Abbat]

I'm currently cryptanalyzing the keyed hash function Twistree's compression 
function, to see if it's computationally feasible to do the following:

A and B are 32-byte blocks. f is the compression function, which takes A and B 
(and optionally a third block C) and an argument sboxalt in [0,1,2] which 
tells in which order to use the S-boxes, and compresses them to a 32-byte 
block D. If one can find A1!=A2 and B1!=B2 such that f(A1,B1,0)==f(A2,B2,0) and 
f(A1,B1,1)==f(A2,B2,1) using strong S-boxes, then the compression function is 
broken, and if in addition, B1 and B2 are well-formed padded blocks, then the 
hash function is broken.

I've thought of two ways to attack it. The first, which I'm working on, is a 
differential cryptanalysis of two rounds (the full compression function has 
eight rounds when given two blocks and sixteen when given three) in which I 
pick a random-looking plaintext, change one byte to all 256 possibilities, run 
them through two rounds, and take the difference of all pairs that were rotated 
by the same number of bits in each of the two rounds. I'm going to use twelve 
keys and three sets of S-boxes not made from keys (one is linear, the others 
have all three S-boxes the same). This produces a big amount of data, but I 
think I can keep it all in RAM. The total is a little less than 2 GB, and the 
main problem will be graphing them so that I can see what's going on.

The other is to run a round backward. A round consists of these steps:
* Split block in three parts and mix one byte from each part
* Run the bytes through the S-boxes
* Rotate the block by 37 times the number of one-bits
* Run the block backward through an LFSR
* Drop the last four bytes.
So to reverse a round, I'd append four bytes, undo the LFSR, rotate by -37 
times the number of one-bits, run the bytes through the inverse S-boxes, and 
mix the three parts (the first step is an involution). The hard part is the 
LFSR; the last three steps are the same as decrypting Wring, except for the 
factor 37.

Running through all the possibilities of the four bytes on the first round of 
compressing three blocks would give me 2^32*96 bytes, which is 384 GiB. This 
is just one round, one key, and one choice of the other 92 bytes. My laptop, 
on which I'd run this, has little more than 1 TiB free, 371 GiB on one 
filesystem and 741 GiB on another. How can I handle this huge amount of data?

Pierre
-- 
The gostak pelled at the fostin lutt for darfs for her martle plave.
The darfs had smibbed, the lutt was thale, and the pilter had nothing snave.