Subject: Re: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03

From: Dean Willis <[email-masked]>
Date: Tue, 03 Oct 2006 13:21:19 -0500

Cullen Jennings wrote:
> 
> I don't think we should require any specific hash but I think it would 
> be nice to give implementors some advice on what might be a reasonable 
> choice.

So does this mean we need a change to the draft, or did we decide to 
stand with the current text?

--
Dean

_______________________________________________
Sip mailing list  https://www1.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use [email-masked] for questions on current sip
Use [email-masked] for new developments on the application of sip

---

From: Robert Sparks <[email-masked]>
Date: Tue, 3 Oct 2006 13:36:57 -0500

There are other changes to the draft that I've agreed to make, so  
there will be a new version (shortly).

This question isn't pinned down yet though. The draft _doesn't_  
require any specific hash. It gives advice on a reasonable choice.
It goes further to characterize properties of other choices an  
implementation might make, where it trips over this bit-count that gave
people different kinds of heatburn.

I propose just pulling the bit-length description and instead point  
to the lack-of-collision property that folks need to take into account.
We are already careful not to say "cryptographic", but I'll probably  
add a comment making the lack-of-cryptographic-requirement
more explicit.

RjS

On Oct 3, 2006, at 1:21 PM, Dean Willis wrote:

> Cullen Jennings wrote:
>> I don't think we should require any specific hash but I think it  
>> would be nice to give implementors some advice on what might be a  
>> reasonable choice.
>
> So does this mean we need a change to the draft, or did we decide  
> to stand with the current text?
>
> --
> Dean

---

From: Cullen Jennings <[email-masked]>
Date: Tue, 3 Oct 2006 12:34:45 -0700

So my vague recollection of where we are:

1) we all agree cryptographic hash would likely not be a good choice
2) we agree the spec does not need to mandate any particular hash or  
length
3) it would help implementors if we gave advice of what a reasonable  
choice might be (in a non normative way)

So far, I have not see a suggestion of what a good choice should be,  
I don't have a specific one to recommend, but I think the draft  
should propose a reasonable choice and a reasonable bit length  
because every implementer I know is going to do exactly whatever the  
draft shows in it's examples.

On Oct 3, 2006, at 11:36 AM, Robert Sparks wrote:

> We are already careful not to say "cryptographic", but I'll  
> probably add a comment making the lack-of-cryptographic-requirement
> more explicit.
>
> RjS
>

---

From: Robert Sparks <[email-masked]>
Date: Tue, 3 Oct 2006 14:52:44 -0500

To make this a little less vague - what the draft has right now is:

>   A common way to create the second part of the branch parameter value
>    when forking a request is to compute a hash over the  
> concatenation of
>    the Request-URI, any Route header field values used during  
> processing
>    the request and any other values used by the location service logic
>    while processing this request.  An MD5 [RFC1321] hash expressed in
>    hexadecimal (base64 is not permissible for a token) is a reasonable
>    choice of a hash function.  Any hash function chosen should have  
> the
>    property of very low probability of collision.  Hashes resulting in
>    fewer than 128 bits are not recommended.

I take it you are explicitly objecting to the statement that MD5 is a  
reasonable non-normatively specified choice?
You have also clearly objected to 128 as a suggestion (The text does  
NOT mandate a length).

RjS

On Oct 3, 2006, at 2:34 PM, Cullen Jennings wrote:

> 2) we agree the spec does not need to mandate any particular hash  
> or length
> 3) it would help implementors if we gave advice of what a  
> reasonable choice might be (in a non normative way)
>
> So far, I have not see a suggestion of what a good choice should  
> be, I don't have a specific one to recommend, but I think the draft  
> because every implementer I know is going to do exactly whatever  
> the draft shows in it's examples.
>
>
>
>> I propose just pulling the bit-length description and instead  
>> point to the lack-of-collision property that folks need to take  
>> into account.
>>>> would be nice to give implementors some advice on what might be  
>>>> a reasonable choice.
>>>

---

From: Cullen Jennings <[email-masked]>
Date: Tue, 3 Oct 2006 14:35:27 -0700

On Oct 3, 2006, at 12:52 PM, Robert Sparks wrote:

>
> I take it you are explicitly objecting to the statement that MD5 is  
> a reasonable non-normatively specified choice?
> You have also clearly objected to 128 as a suggestion (The text  
> does NOT mandate a length).
>
> RjS

Yes - MD5 is a cryptographic hash and I thought we all agreed that  
use off cryptographic hash was not the best choice. If we think  
cryptographic hash ideas are a good idea, then we need to explain why.

Using a cryptographic hash, even in an example, is a huge red flag  
for any security person reviewing this. The fact that we used this  
particular one which has significant security issues, is a even  
bigger issue. Partially I think MD5 is totally lame to use here  
because it is slow and offer no advantages over better things and  
partially I am trying to avoid any delays due to security review  
where someone points out we should not be using MD5 in new protocols.  
If the we can't figure out a reasonable hash to suggest, how should  
an implementer figure out what to use. I've been trying to say, I  
don't care what but don't choose a cryptographic one. If people have  
a good reason for wanting MD5, I'm glad to listen but I just had not  
heard the reason yet.

---

From: Robert Sparks <[email-masked]>
Date: Tue, 3 Oct 2006 16:42:26 -0500

The only reason it is here is that it was what was called out for  
this job in 3261.

So - Give me an alternative.

RjS

On Oct 3, 2006, at 4:35 PM, Cullen Jennings wrote:

>> I take it you are explicitly objecting to the statement that MD5  
>> is a reasonable non-normatively specified choice?
> where someone points out we should not be using MD5 in new  
> protocols. If the we can't figure out a reasonable hash to suggest,  
> how should an implementer figure out what to use. I've been trying  
> to say, I don't care what but don't choose a cryptographic one. If  
> people have a good reason for wanting MD5, I'm glad to listen but I  
> just had not heard the reason yet.
>
>
>

---

From: Robert Sparks <[email-masked]>
Date: Tue, 3 Oct 2006 17:04:47 -0500

ok - based on an off-line conversation with cullen, lets suggest  
CRC32 as specified in RFC3309.

If nobody screams, that's what the next rev will say.

RjS

On Oct 3, 2006, at 4:42 PM, Robert Sparks wrote:

>> protocols. If the we can't figure out a reasonable hash to  
>> suggest, how should an implementer figure out what to use. I've  
>> been trying to say, I don't care what but don't choose a  
>> cryptographic one. If people have a good reason for wanting MD5,  
>> I'm glad to listen but I just had not heard the reason yet.
>>
>>
>>
>

---

From: Michael Thomas <[email-masked]>
Date: Wed, 04 Oct 2006 11:35:27 -0700

Cullen Jennings wrote:

> bigger issue. 

Uh, no. These aren't even remotely comparable. I'm going to make a big 
leap here
and guess that people aren't trying to actively _attack_ these forking 
hashes. _That's_
the problem with MD5 with security. If you're just using it as a 
_hashing_ algorithm
that has a low probability of collisions, it's just fine. That is: 
unless you're going to
say that the forking hash needs to be resisitant to collisions from an 
attacker's chosen
text to do something nefarious, the problems with MD5 (or SHA1) don't apply.

> Partially I think MD5 is totally lame to use here  because it is slow 
> and offer no advantages over better things and  partially I am trying 
> to avoid any delays due to security review  where someone points out 
> we should not be using MD5 in new protocols.

The only knock in my mind is that it may be slower than something else, 
but I'd
worry a great deal about the "something else" if collisions are a 
problem. Just randomly
inventing a good hashing algorithm with good collision properties 
especially with
similar chosen text is not exactly the easiest thing to do. Since you're 
relying on this
for carrying state, I think it's a bad idea to not at least do a SHOULD 
level algorithm(s)
and be very certain that the algorithm you choose actual has the 
collision resistance
needed. I'm not an expert here by any means, but my recollection is that 
CRC does
NOT have very good properties that way.

       Mike

---

From: Cullen Jennings <[email-masked]>
Date: Wed, 4 Oct 2006 19:24:39 -0400

inline but yes basically agree with you ...

On Oct 4, 2006, at 2:35 PM, Michael Thomas wrote:

>> Yes - MD5 is a cryptographic hash and I thought we all agreed  
>> that  use off cryptographic hash was not the best choice. If we  
>> think  cryptographic hash ideas are a good idea, then we need to  
>> explain why.
>>
>> Using a cryptographic hash, even in an example, is a huge red  
>> flag  for any security person reviewing this. The fact that we  
>> used this  particular one which has significant security issues,  
>> is a even  bigger issue.
>
> Uh, no. These aren't even remotely comparable. I'm going to make a  
> big leap here
> and guess that people aren't trying to actively _attack_ these  
> forking hashes. _That's_
> say that the forking hash needs to be resisitant to collisions from  
> an attacker's chosen

yes - agree - all we need is something with low probability of  
collision, and the value of  "low" is based on probability of call  
failing and having to be retried, not some security violation

>
>> Partially I think MD5 is totally lame to use here  because it is  
>> slow and offer no advantages over better things and  partially I  
>> am trying to avoid any delays due to security review  where  
>> someone points out we should not be using MD5 in new protocols.
>

Yes - I should have been clearer - that was my only concern. And even  
with that, I've never been a believer that the performance mattered  
much but many people in the WG have expressed that we have to do O 
(N^2) where N=30  or 70 depending on who you follow and this was a  
huge deal. I just wanted to take this performance argument off the  
table.

> similar chosen text is not exactly the easiest thing to do.

100% agree - I'm not a fan of roll your own solution to hashes.  
Actually people still make fun of me for a project where I created in  
a hash table that only generated even numbers. Since then I have  
always been concerned about getting burned from things I rolled myself.

> Since you're relying on this
> for carrying state, I think it's a bad idea to not at least do a  
> SHOULD level algorithm(s)
> needed. I'm not an expert here by any means, but my recollection is  
> that CRC does

CRC has poor whitening characteristics but it collision distribution  
if fairly uniform. All of this is weighted off against how many bits  
collision detection do we use. Keep in min that we have up to 70  
things that we don't want to collide with a something like 1 in fives  
nines probability of collision. WIth a good hash we could likely do  
this in something like 15 bits (WAG), with a crappy hash we need a  
few more bits. We are talking about using insanely more bits than  
this (32 bits) so I'm not that worried. I would be worried with a  
CRC16. Also, as you point out, we are not trying to protect against a  
case where an attacker deliberately generates a collision in which  
case CRC would be a very bad choice.

I think there are a huge number of things that could work fine and  
don't care what we choose - but since people are claiming that we  
should not use this loop detection because it is slow, I want the  
some reasonable fast hash to compare to.

>
>       Mike
>
>
>>   If the we can't figure out a reasonable hash to suggest, how  
>> should  an implementer figure out what to use. I've been trying to  
>> say, I  don't care what but don't choose a cryptographic one. If  
>> people have  a good reason for wanting MD5, I'm glad to listen but  
>> I just had not  heard the reason yet.
>>
>>
>>
>>

---

From: Michael Thomas <[email-masked]>
Date: Wed, 04 Oct 2006 21:45:58 -0700

> huge deal. I just wanted to take this performance argument off the  

   It's probably not worth belaboring this too much, but I do worry 
about not
   constraining this such that roll your own is a likely outcome. Which 
is why
   I said that a SHOULD strength algorithm(s) seems pretty reasonable.

> always been concerned about getting burned from things I rolled myself.

hmm, malloc (tablesize/2); hashvalue /= 2; and it's all of a sudden not so
embarassing :)

> case CRC would be a very bad choice.

   I'm good for whatever is appropriate here -- my main point is that 
using things
   like md5 for non-crypto strength hashes shouldn't be dismissed if 
you're using
   it just as a _hash_ algorithm. And if that causes knee-jerks on the 
IESG, etc, it
   would be good to get that out of the way. My suspicion is that it 
wouldn't though
   once it was clear that it was just being used as a hash for 
non-crypto reasons.

       Mike, rehabilitaton-R-us.

---

From: Robert Sparks <[email-masked]>
Date: Wed, 11 Oct 2006 13:16:21 -0500

So, I read this to say the proposed recommendation of CRC32 as  
specified in rfc3309 is ok to go forward with.

Based on the discussion, I think I will also point out that MD5 can  
be used (and has been used in the past),
that its use would rely only on its collision properties, not any  
cryptographic properties, and point out that it
is much slower than the alternative above.

Any objection?

RjS

On Oct 4, 2006, at 11:45 PM, Michael Thomas wrote:

>> Yes - I should have been clearer - that was my only concern. And  
>> even  with that, I've never been a believer that the performance  
>> mattered  much but many people in the WG have expressed that we  
>> have to do O (N^2) where N=30  or 70 depending on who you follow  
>> and this was a  huge deal. I just wanted to take this performance  
>> argument off the  table.
>
>
>   constraining this such that roll your own is a likely outcome.  
> Which is why
>>> worry a great deal about the "something else" if collisions are  
>>> a  problem. Just randomly
>>> inventing a good hashing algorithm with good collision  
>>> properties  especially with
>> Actually people still make fun of me for a project where I created  
>> in  a hash table that only generated even numbers. Since then I  
>> have  always been concerned about getting burned from things I  
>> rolled myself.
>
>>> needed. I'm not an expert here by any means, but my recollection  
>>> is  that CRC does
>> CRC has poor whitening characteristics but it collision  
>> distribution  if fairly uniform. All of this is weighted off  
>> against how many bits  collision detection do we use. Keep in min  
>> that we have up to 70  things that we don't want to collide with a  
>> something like 1 in fives  nines probability of collision. WIth a  
>> good hash we could likely do  this in something like 15 bits  
>> (WAG), with a crappy hash we need a  few more bits. We are talking  
>> about using insanely more bits than  this (32 bits) so I'm not  
>> that worried. I would be worried with a  CRC16. Also, as you point  
>> out, we are not trying to protect against a  case where an  
>> attacker deliberately generates a collision in which  case CRC  
>> would be a very bad choice.
>
>
>   I'm good for whatever is appropriate here -- my main point is  
> that using things
>   it just as a _hash_ algorithm. And if that causes knee-jerks on  
> the IESG, etc, it
>   once it was clear that it was just being used as a hash for non- 
> crypto reasons.
>

---

From: Cullen Jennings <[email-masked]>
Date: Wed, 11 Oct 2006 12:22:58 -0700

> is much slower than the alternative above.

works for me

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 11 Oct 2006 13:53:44 -0700

> specified in rfc3309 is ok to go forward with.

I think this is fine.

> is much slower than the alternative above.

No to the choice of CRC32, but yes to the language you suggest
above. Collision-resistance is a technical term in cryptography,
the text above is quite confusing. 

Informally, the property you want is that two hashes of the
input values have a 2^(-b) chance of having the same hash
value. Formalizing this turns out to be a really knotty problem
especially if you assume (as is true in this case) that the
input strings are non-uniform. (universal hashing is one 
way around this problem).

Anyway, I think the correct language ought to be something
like this:

   A common way to create the second part of the branch parameter
   value when forking a request is to compute a hash over the
   concatenation of the Request-URI, any Route header field values
   used during processing the request and any other values used by the
   location service logic while processing this request. The hash
   should be chosen so that there is a low probability that two
   distinct sets of these parameters will collide. Because the maximum
   number of messages which need to be compared is 70 [is this right],
   the chance of a collision is low even with a relatively small hash
   value, such as 32 bits. CRC-32 [REF] is a specific acceptable
   function, as is MD5 [REF].  Note that MD5 is being chosen purely
   for non-cryptographic properties.  An attacker who can control the
   inputs in order to produce a hash collision can attack the
   connection in a variety of other ways.

-Ekr

---

From: Robert Sparks <[email-masked]>
Date: Wed, 11 Oct 2006 16:05:57 -0500

Thanks Ekr!

inline.

> the text above is quite confusing.
I was being too sloppy - sorry.

>    number of messages which need to be compared is 70 [is this right],
yes, but I'll replace messages with a phrase that says
"via branch parameters in a given message" but with better wordsmithing.
>    connection in a variety of other ways.
_Thank you_ for the text!

RjS

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 11 Oct 2006 14:16:02 -0700

> "via branch parameters in a given message" but with better wordsmithing.

Right. I actually meant "inputs" :)

-Ekr

---

From: Michael Thomas <[email-masked]>
Date: Wed, 11 Oct 2006 15:14:46 -0700

Is it just me, or do others think that this warrents a SHOULD level set 
of choices?
The cost of a collision is probably some pretty weird behavior, and 
given no real
constraint we can be pretty well assured that somebody will use the lack 
of normative
language to do the wrong thing. Or am I being all too net-nannyish?

       Mike

---

From: Robert Sparks <[email-masked]>
Date: Thu, 12 Oct 2006 13:36:02 -0500

There's been a lot of pushback in the past about any normative  
strength in this recommendation.

On Oct 11, 2006, at 5:14 PM, Michael Thomas wrote:

> Is it just me, or do others think that this warrents a SHOULD level  
> set of choices?
> constraint we can be pretty well assured that somebody will use the  
> lack of normative

---

From: [email-masked]
Date: Thu, 12 Oct 2006 15:29:24 -0400

From: Robert Sparks <[email-masked]>

   On Oct 11, 2006, at 5:14 PM, Michael Thomas wrote:

   > Is it just me, or do others think that this warrents a SHOULD
   > level set of choices?  The cost of a collision is probably some
   > pretty weird behavior, and given no real constraint we can be
   > pretty well assured that somebody will use the lack of normative

Someone pointed out that since the call-ID and/or branch parameter (I
forget which) is included in the hash, if a call fails due to a hash
collision, a retry of the call will fail (or rather, it will fail
independently, which is unlikely).  So the penalty for a deficient
hash function is small.

Dale