Re: 2006/467 Chang Yung: silly?

D. J. Bernstein skrev:
One can build a cryptographic hash function by starting from a ``good''
block cipher with the same output size and running it in one of the 12
Preneel-Govaerts-Vandewalle modes. The conventional wisdom is that this
is a robust design procedure: ``good'' is stronger than the conventional
indistinguishability notion for block ciphers, but it nevertheless seems
to be achieved by the standard cipher-design techniques.

In http://eprint.iacr.org/2006/467, Chang and Yung assert that this
procedure isn't robust and needs to be revised. At first glance, their
argument seems to boil down to the following:

(1) Differential and linear cryptanalysis don't depend on the choice
of AES constants, or on the mixing in the final AES round.

(2) Standard block-cipher cryptanalysis doesn't depend on the choice
of AES constants, or on the final mixing. (Proof: See #1.)

(3) Let's replace the AES constants by 0, and add a final mixing.
Standard block-cipher design could have produced this variant.
(Proof: See #2.)

(4) The resulting hash function allows collisions in time 2^49. Thus
standard block-cipher design can lead to a bad hash.

I find this argument completely unconvincing. Anyone who knows about
slide attacks will see #2 as a wild exaggeration of #1. I haven't
checked whether the Chang-Yung cipher is breakable by a slide attack,
but I have checked that the original Rijndael documentation already
documented the ``usage of round constants'' in Rijndael ``to eliminate
symmetries,'' so the Chang-Yung cipher was specifically barred by the
Rijndael design principles. Obviously #3 is wrong.

Am I missing something here? Do Chang and Yung actually have a serious
argument?

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

Eliminating round keys from AES indeed produces a different cipher than
AES. Round constants are important part of design for protecting
against rounds symmetry. It looks that Chang and Yung exploited round
symmetry that they introduced by removing round constants to reduce
work factor from 2^64 to 2^49. I think that the point they are making
is valid, however they should have made a stronger distinction of
analyzed cipher from the AES.

-Valery.
http://www.harper.no/valery

.

Relevant Pages

  • Re: AES design - can you help me to understand
    ... I may have incorrectly assumed that the first was the strategy used in AES? ... And this one may be a key dependant scrambling round similar ... Both AES and DES take your secret key and stretch it with a key ... If you really want to compare DES to another cipher compare it to CAST5 ...
    (sci.crypt)
  • Re: Only people who originally frequent sci.crypt reply to this
    ... The mode of a cipher is one of the many, ... you need to get right in order to turn a secure algorithm into a secure ... there are no known attacks against AES. ... attack of any kind against a cipher, ...
    (sci.crypt)
  • Re: Is a cryptographic monoculture hurting us all?
    ... AES may well remain secure for a while but it could be broken in the ... Or worse you get protocol attacks like the GSM. ... centeralisation means that the cipher has gotta be damn tough to break. ... safe that are roughly equal in strength. ...
    (sci.crypt)
  • Quadruple Algorithms
    ... occurring" (a fatal flaw being found in AES, ... the most likely attack on your entire system, ... Threat one: Your implementation of AES has an undiscovered ... with the output of one cipher feeding ...
    (sci.crypt)
  • Re: Crypto problems in Vista
    ... I managed to call AES and SHA-1 functions from the "Microsoft Enhanced RSA ... and AES Cryptographic Provider" CSP in Vista. ... AES is a block cipher with a 16 byte block-length. ... support Output Feedback Mode." ...
    (microsoft.public.platformsdk.security)