Subject: Re: [Cfrg] AES-based PRF - comment please

From: Ran Canetti <[email-masked]>
Date: Thu, 10 Apr 2003 01:07:13 -0400

Uri,

> From: Uri Blumenthal <[email-masked]>
> 
> ...
> 
> > Of course for sufficiently large k, this is effectively the same thing as
> > "all bets are off". For k < 8, say, it is probably harmless. Anyway, this
> > argument does not in any way justify using non-secret or non-random keys,
> > unless you know that they are only "slightly" non-random.
> 
> In pratice - but not in theory, right? Because the theory deals with
> the degradation - which is quantifiable? So if only 8 out of 128 key
> bits are random - it still means degradation by 2^120, not "all bets
> are off"?
> 
> Thanks!
> 
> Regards,
> Uri.

Wouldnt it be great if life were that easy...

In an ideal world, with ideal ciphers, you would be 100% correct. Each
non-random bit of the key reduces the work of the attacker by exactly a
half, no more, no less.

Problem is that we're not dealing with ideal ciphers, and we don't know for
sure what is the actual strength of AES (or any other block cipher for that
matter). In particular we only assume that it is "secure" for uniform keys.

So it may well be, in principle, that if you fix the first, say, 64 bits of the
key to some value (say all zeroes) then AES becomes breakable in much less
than 2^64 operations. This would not contradict the security of AES with
totally uniform keys. (You would have a bad event occuring with probability
1/2^64, but as long as this event does not happen AES remains "fully secure".)

Maybe this happens, maybe it doesnt. We dont know. So I think it's best to 
stick to what we can prove based on the requirements for which AES was designed
(ie, to be an invertible PRP).

Ran

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: John Viega <[email-masked]>
Date: Thu, 10 Apr 2003 01:22:42 -0400

Ok, sure.  Now that I see that you're back on the ideal cipher issue, I 
agree with you, and I said the same thing much earlier in the thread.  
I personally suspect that we're unlikely to see a hash construct from a 
PRP in the near future, but I'd love to be proven wrong.

In the mean time, I'm happy using SHA1, and I think, in practice, 
assuming AES has the properties of an ideal cipher isn't even close to 
the most unreasonable thing the average person will do in his or her 
designs.

John

---

From: "David A. Mcgrew" <[email-masked]>
Date: Thu, 10 Apr 2003 09:21:24 -0700

John,

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On Behalf Of John
> Viega
> Sent: Wednesday, April 09, 2003 10:23 PM
> To: Ran Canetti
> Cc: [email-masked]
> Subject: Re: [Cfrg] AES-based PRF - comment please
>
>

It would be neat if there were some assumption in between that of
indistinguishability from a PRP and that of the ideal cipher that could be used
to make a collision-resistant hash out of AES.  But it's not obvious to me :-)

My $0.02 on AES-hashes: depending on how the hash function is used, it may be
acceptable for it to be relatively inefficient.  For example, if it is used in
conjunction with a public-key operation, it could require loads of invocations
of the PRP and still not change the order of magnitude of the total amount of
computation done.  But for sure computational inefficiency would impact utility.
It would be nice if we could eliminate SHA from our implementations in favor of
an AES mode, but in practice it is probably not so important.  I think that a
good case can be made for getting SHA out of the data-plane (that is, replacing
HMAC-SHA with something that can be pipelined), but I'm not sure that there's
much need to eliminate it from key derivation.

David