[3202] in cryptography@c2.net mail archive
Re: Announcement: Cryptanalysis of Frog (an AES Candidate)
daemon@ATHENA.MIT.EDU (Dianelos Georgoudis)
Tue Aug 18 11:54:51 1998
Date: Tue, 18 Aug 1998 09:52:50 -0500
From: Dianelos Georgoudis <dianelos@tecapro.com>
To: cryptography@c2.net
Reply-To: dianelos@tecapro.com
X-Return-Receipt-To: dianelos@tecapro.com
The paper of Wagner, Ferguson and Schneier is highly technical - I
shall need months to fully comprehend it, but this is my problem.
From a very superficial reading, what I understand they are doing,
very roughly, is this:
FROG creates S-boxes by a pseudo-random process as a function of
the user key, without any controls at all about their quality.
These S-boxes form the largest part of the internal key schedule.
I thought that traditional attacks are not possible because these
boxes are unknown to the attacker. What they do is posit S-boxes
that are weak and show how a traditional attack would work then.
So far so good - the bad news is that they show that the frequency
of "bad" keys is surprising large, about 2^(-30). As I understand
it they assume all values of the internal key are possible and
show that a fraction of these are weak; they are attacking the
internal key schedule not the user key itself. The internal key
space is much larger than the user key space which means that if
you find or construct a weak internal key then it is almost
certain that it will not correspond to any user key. So, it is not
obvious that the frequency of weak *user* keys will also be
2^(-30). Actually they haven't computed even one weak user key.
They also show that there are weak keys for which a ciphertext
only (!) attack is possible, as long as only English text is
encrypted. This is quite an amazing result that builds on the fact
that the most significant bit of each byte will be zero. I wonder
what would happen if only a few of the bytes encrypted did have a
one in the most significant bit (for example English text that
includes the symbol for Pound Sterling)?
They show that the FROG function at decryption direction has a
much weaker avalanche effect, a matter already pointed out by John
Savard. By now it is vox populi that encryption and decryption are
*not* like the two sides of the same coin.
At the end of the paper they estimate that FROG would need twice
as many rounds to resist their attack on weak keys - I understand
this in the sense that there wouldn't be any weak keys then. I
wonder how fast does the frequency of weak keys decrease by adding
individual rounds.
They do not describe other better solutions. As I understand it
the basic piece of information they use in their attack is that
the same S-box is used in each of the eight rounds of the cipher.
It would be a trivial matter (and much in accord to the FROG idea)
to make the S-box used for each byte key-dependent too. It would
hardly affect encryption speed - and maybe one could then afford
less rounds.
At the end of their paper they also make an estimate about the
theoretical maximum speed of FROG and show that it cannot be very
fast (compared to other ciphers including Twofish). One advantage
that FROG has though, is that it does not use any operations that
are broader than one byte and I think it is possible to program a
Pentium to do up to eight FROG encryptions in parallel.
At this point in time I have mixed feelings. By any measure they
are showing a weakness in FROG as submitted - assuming no error in
their paper is present. Their paper looks impressive and I am
amazed that they could manage to do so much work in so little time
(frankly I would rather have them work for a few more weeks and
publish their paper until after the Conference). On the other hand
FROG represents a different kind of cipher design methodology; as
George Barwood stated shortly after I announced the algorithm he
couldn't believe it would work because it would be like getting
"something for nothing, a free lunch, magic". Well it seems that a
cipher that appears to be based on thin air cost them an awful lot
of work just to show that for a small fraction of the keys an
attack exists - albeit one too complex to be carried out in
practice. If making the S-box choice key dependent invalidates
their attack, then their work may actually reinforce the basic
design principle of FROG: to deny the attacker as much knowledge
as possible about the operation of the cipher. In other words
it may be a better idea to construct a cipher that is as
structure-less as possible rather than one that has a carefully
hand-crafted but complicated structure.
Please, mark my words, I am not sure I understand their attack
correctly and I may very well be wrong in many of the points made
here.
BTW, the CAESAR group's observations on FROG are superficial
and I have contested them in a post to the sci.crypt group.
Dianelos Georgoudis
email: dianelos@tecapro.com
http://www.tecapro.com
