Subject: [Gen-art] Gen-ART Telechat Review of draft-ietf-csi-hash-threat-09

From: "McCann Peter-A001034" <[email-masked]>
Date: Tue, 9 Mar 2010 17:32:18 -0500

I have been selected as the General Area Review Team (Gen-ART) reviewer
for this draft (for background on Gen-ART, please see
http://www.alvestrand.no/ietf/gen/art/gen-art-FAQ.html).

Please wait for direction from your document shepherd or AD before
posting a new version of the draft.

Document: draft-ietf-csi-hash-threat-09
Reviewer: Pete McCann
Review Date: 09 March 2010
IESG Telechat date: 11 March 2010

Summary:  A couple of minor issues, 
          and numerous editorial fixes are needed before publication.

Major issues:  None.

Minor issues:

Introduction:
   There is a great variaty of hash functions, but only MD5 and SHA-1
   are in the wide use, which is also the case for SEND
This sentence makes a statement about MD5 and SHA-1 being the only
widely
used hash functions, but I can't figure out what it is saying about
SEND.
Is it saying that SEND is widely used?  Or did you mean to say that SEND
implementations typically only implement MD5 and SHA-1?

Section 3:
   Supposing that the hash function
   produces an n-bit long output, since each output is equally likely,
   an attack takes an order of 2^n operations to be successful.
SHOULD SAY: "on the order of".  But this sentence is just plain
incorrect (see below).
  Due to
   the birthday attack, if the hash function is supplied with a random
   input, it returns one of the k equally-likely values, and the number
   of operations can be reduced to the number of 1.2*2^(n/2) operations.
There is no "birthday attack."  And I think you meant 2^n instead of k.
The result you give is due to an equation that is commonly illustrated
with
a problem known as the "birthday paradox."

Nits/editorial comments:

Abstract:
   possible threats
   and the impact of recent
SHOULD BE:
   possible threats,
   and the impact of recent

   Current SEND specification
SHOULD BE:
   The current SEND specification

   support for the hash algorithm agility
SHOULD BE:
   support for hash algorithm agility

   The purpose of the document
SHOULD BE:
   The purpose of this document

   encode the hash agility
SHOULD BE:
   encode hash agility

Introduction:
   Key Hash field and
SHOULD BE:
   Key Hash field, and

   variaty
SHOULD BE:
   variety

   in the wide use
SHOULD BE:
   in wide use

   which has been well known for its weaknesses.
SHOULD BE:
   which has well known weaknesses.

   First
   hash attacks affected the compression function of MD5
SHOULD BE:
   Early
   hash attacks affected the compression function of MD5

   significantlly
SHOULD BE:
   a significantly

   on the way how
SHOULD BE:
   on the way in which

   underlaying
SHOULD BE:
   underlying
(repeated twice)

   way of use
SHOULD BE:
   use

   keep the protocol
   immune,
SHOULD BE:
   keep the protocol
   secure,

   matter of the hash
SHOULD BE:
   matter the hash

   with shared secrets, fingerprints,
SHOULD BE:
   with shared secrets, and fingerprints,

   The rest of the
   section
SHOULD BE:
   The rest of this
   section

   on SEND by the cases of use.
SHOULD BE:
   on SEND by each use case.

   the hash agility
SHOULD BE:
   hash agility

Section 3.1:
   the CGA hash agility
SHOULD BE:
   CGA hash agility

Section 3.2:
   allowe
SHOULD BE:
   allow

   biggest concer are
SHOULD BE:
   the biggest concerns are

   (if the IP prefix range
   used),
SHOULD BE:
   (if the IP prefix range were
   used);

   although, not broader than the prefix range
SHOULD BE:
   although, it could not be broader than the prefix range

   to the
   such human-readble data such 
SHOULD BE:
   to
   such human-readble data

   attack improve
SHOULD BE:
   attack improves

Section 3.3:
   ND message and other fields, e.g. the Message
   Type Tag and ND options,
SHOULD BE:
   ND message, and other fields (e.g. the Message
   Type Tag and ND options),

   field the example of the non-repudiation digital singature,
SHOULD BE:
   field is an example of a digital singature that needs
non-repudiation,

   more then
SHOULD BE:
   more than

   but in real-world situation is to achieve it.
SHOULD BE:
   but in a real-world situation it would be difficult to achieve it.

Section 3.4:
   provides the integrity
SHOULD BE:
   provides integrity

4. Support for the hash agility in SEND
SHOULD BE:
4. Support for hash agility in SEND

   Previous section showed
SHOULD BE:
   The previous section showed

   SEND context prevents those attacks of
   almost any use
SHOULD BE:
   The SEND context prevents these attacks from
   being of almost any use

   for the future
SHOULD BE:
   for future

   suggest the support for the hash and algorithm
   agility in SEND.
SHOULD BE:
   suggest support for hash and algorithm
   agility be added to SEND.

   secure would
SHOULD BE:
   secure method would

   then defining
SHOULD BE:
   than defining

   Possible solution is also the hybrid
SHOULD BE:
   Another possible solution is a hybrid

   One of possible solutions is the negotiation
      approach for the SEND hash agility
SHOULD BE:
   One possible solution is the negotiation
      approach for SEND hash agility

Section 6:
   offeres
SHOULD BE:
   offers

   providing solution for the hash
SHOULD BE:
   providing a solution for hash

   for the hash agility
SHOULD BE:
   for hash agility

---

From: Suresh Krishnan <[email-masked]>
Date: Tue, 9 Mar 2010 22:56:16 -0500

Hi Pete,
   Thanks for the comments. Please see responses inline.

> implementations typically only implement MD5 and SHA-1?

The latter. I propose changing the text to

"There is a great variety of hash functions, but only MD5 and SHA-1
are widely used. SEND implementations also typically use these two hash 
algorithms."

> SHOULD SAY: "on the order of".  

OK.

> But this sentence is just plain
> incorrect (see below).
>   Due to

Right. A birthday attack is an attack that exploits the mathematics 
behind the birthday paradox. It is a fairly commonly used term. Would 
you like me to change something?

> Nits/editorial comments:

Agree with you on all these comments. Will fix all these.

Thanks
Suresh

---

From: Ana Kukec <[email-masked]>
Date: Wed, 10 Mar 2010 07:56:49 +0100

Hi all,

Pete, thank you for the comments.

I've changed the draft and took into account all the comments from this 
email. Some comments are below, inline.

Suresh Krishnan wrote:
> are widely used. SEND implementations also typically use these two 
> hash algorithms."
>

I've changed the text according to your suggestion Suresh.

> you like me to change something?

That's right -- birthday attack is common term, but only in 
cryptography. I was relying on Bruce Schneier's  book "Applied 
cryptography" where he uses both the term "birthday attack" and the 
equation. Maybe i can make the sentence more clear:

"Due to the birthday attack, if the hash function is supplied with a 
random input, it returns one of the  equally-likely n-bit hash values, 
and the number of operations can be reduced to the number of 1.2*2^(n/2) 
operations."

Other comments are fixed.

Ana

---

From: "McCann Peter-A001034" <[email-masked]>
Date: Wed, 10 Mar 2010 10:51:12 -0500

Hi, Ana,

Ana Kukec wrote:
> I've changed the draft and took into account all the comments from
> this email. Some comments are below, inline. 
> 
> 
> 
> Suresh Krishnan wrote:
>> 
>>> 
>>> 
>>> Introduction:
>>>    There is a great variaty of hash functions, but only MD5 and
>>>    SHA-1 are in the wide use, which is also the case for SEND
>>> widely used hash functions, but I can't figure out what it is
>>> saying about SEND. Is it saying that SEND is widely used?  Or did
>>> you mean to say that SEND implementations typically only implement
>>> MD5 and SHA-1? 
>> 

Ok, thanks.
 
>>>    the birthday attack, if the hash function is supplied with a
>>>    random input, it returns one of the k equally-likely values, and
>>>    the number of operations can be reduced to the number of
>>> 1.2*2^(n/2) operations. There is no "birthday attack."  And I think
>>> you meant 2^n instead of k. The result you give is due to an
>>> equation that is commonly illustrated with a problem known as the
>>> "birthday paradox." 
>> 

I would propose replacing all of this:

   an attack takes an order of 2^n operations to be successful.  Due to

With this:

   If the hash function produces an n-bit long output, then each of the
   2^n outputs can be considered equally likely.  An attacker searching
   randomly or pseudo-randomly through the space of input messages can
be 
   expected to find a hash collision after approximately 1.25 * 2^(n/2)
   trials, due to the mathematics of the birthday problem [ref].

Perhaps find a good reference for "birthday problem."  Schneier might
be good, but wikipedia also suggests this one:

E. H. McKinney (1966) Generalized Birthday Problem, American
Mathematical Monthly 73, 385-387.

> Other comments are fixed.

Thanks,

-Pete