Subject: [Cfrg] counter mode vs feedback mode (Re: one question about hash)

From: Shai Halevi <[email-masked]>
Date: Fri, 11 Jul 2003 12:25:45 -0400

Hugo, I take issue with the following point: 

> [...]
> In addition, I personally do not like "counter mode" constructions where
> the only difference between two inputs to the function (as is the case
> with SHA1(k,1) and SHA(k,2)) is by one or two bits at most. In my opinion,
> robustness to cryptanalytical advances calls for more prudent designs.  
> In this sense, HMAC has a significant contribution via its "double hashing". 
> Moreover, as in the case of TLS and IKE, also here I'd recommend
> "feedback mode" for key derivation; in the above example we would have
> K1=HMAC-SHA1(k,1) and K2=HMAC-SHA1(k,K1)).

Building blocks such as block ciphers and hash functions are explicitly 
designed to be secure against "small variations" in their inputs. Indeed, 
much of the work involved in the design of such primitives is to analyze 
(and defend against) attacks that involve such "similar inputs". 

Hence, I feel quite confortable using these primitives in counter mode. 
In fact, more confortable than using them in the "feedback mode" that you 
describe. Such feedback mode may be suspetible to short cycles. Although 
extremely unlikely, I view short cycles as more likely than problems with 
counter mode. Simply because typically, the designers of such primitives 
spend (almost) no time thinking about short cycles, but lots and lots of 
time thinking about "similar inputs". 

-- Shai

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

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 11 Jul 2003 23:58:41 +0300 (IDT)

First, let's make clear that the discussion regarding the prf in
"counter mode" or "feedback mode" is fully based on ineherently heuristic
grounds (since no actual proof of the superiority of one over the other
exists for specific constructions such as SHA1). Therefore, personal
beliefs and feelings have a stronger role here than in other more
"scientific" discussions. 

Being a skeptical person (this is what being a cryptographer means: do not
trust anyone, not even yourself :) I doubt that the design tools
available today for building specific functions will stand the proof of
time. And if any weaknesses are eventually found in these functions it
will surprise me less if they apply to closely related inputs than to
randomized ones (see, for example, the MD5 case). 

The argument that short cycles are less studied than
diffusion/mixing/avalance properties is valid if you think of "short"
cycles whose size is in the order of billions (say 2^30) or more. But for
a prf in "feedback mode" to go wrong in the key derivation application
(which we are discussing here) you'll need to find cycles of length in the
two/three-digit range at most (that's how many times you will typically
apply the same function for deriving keys). If any of the prf families
that we are commonly using have such super-short cycles (with
non-negligible probability) then we better know about it earlier than
later, so we can stop using that prf.

Finally, regarding the mentioned example of MD5: what makes Dobbertin's
attack against MD5 work is (surprise surprise)  low hamming distance
between inputs. Remarkably, his first published collision had inputs X,X'
which difffer by exactly one bit... (To be fair to SHA1, its design does a
much better job in dealing with close inputs by applying an expansion
stage to the input; yet the example of MD5 where avalanche effects and the
like were main design principles shows that it is prudent not to build too
much on the perfectness of these principles.)
 
Hugo