Date: Mon, 26 Apr 2010 23:24:25 -0400
From: Charanjit Jutla
To: Multiple recipients of list
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