Date: Mon, 26 Apr 2010 23:24:25 -0400
From: Charanjit Jutla <csjutla@us.ibm.com>
To: Multiple recipients of list <hash-forum@nist.gov>
Subject: Re: Analysis of Fugue-256

Dear all,

We are happy to see cryptanalysts looking in depth at Fugue-256. Indeed,
the characteristics pointed out by Jean-Phillipe and Raphael (see below) 
confirm our observation that these particular characteristics can be 
found, as we explained in the Fugue submissions document on page 73 
(section 12.4.2), and we quote:

"[...] Thus, at first glance, one strategy that may be beneficial for
the adversary is to have nonzero  differential {\em only} in the last
few columns of the state as depicted in Figure 7, after the first one or
two SMIX steps of the final round G (i.e. the top right most SMIX steps). 
If this can be accomplished, then there are no active bytes in the next 
eight SMIX steps of the first loop of G, and no active bytes in most of 
the SMIX steps of the second loop of G. However, obtaining such a 
differential state after the first one or two SMIX steps of G is an
extremely low probability event, as explained next. [...]"

Then, we go on to prove an upper bound of 2^{-140} on this probability
(but in reality this probability could possibly be much lower). Although
our proof is in the PRF model, the same argument holds as well for known 
or chosen key/IV model.

Figure 7 is attached as a pdf to this note, for your convenience.

In general we prove that INTERNAL collisions are extremely unlikely to
be obtained by differential attacks, and this we prove under a very
general model where the adversary can do message modification, early
stopping, etc., i.e. the adversary has access to the internal state.

We also prove that internal PARTIAL collisions which could be of any 
relevance are extremely unlikely to be obtained by differential attacks, 
but here under a model where early stopping is not allowed, i.e. there is 
no access to the internal state. However, we remark that with some more 
work, we can show that even with message modification it is unlikely to 
obtain such partial collisions.

Another minor comment: In the text posted by Jean-Phillipe and Raphael,
they consider a hypothetical case in Figure 3 and they note that state 
words S4 and S19 are not affected at the end of final round. However, S4 
and S19 are not even output as the hash. What is output is

 S1, S2, S3, (S0 xor S4), (S0 xor S15), S16, S17, S18.

In fact, the fact that S4 has not been affected by last umpteen rounds
is desired, since S4 works as a feed forward.


We are very encouraged to see independent research into the security of
Fugue, which seems to confirm our expectations for the type of approaches 
that can be brought to bear on the security of Fugue. We think that a good 
way of assessing the relevance of these (and other) structural properties 
to the overall security of Fugue is to try and apply them to the "toy 
example" weak-Fugue, which is well defined in the document, to see if they 
lead to any attacks.

--Fugue Team