[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Sip] Good Hash: draft-ietf-sip-fork-loop-fix-03
Cullen Jennings wrote:
The only knock in my mind is that it may be slower than something else,
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.
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.
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.
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.
hmm, malloc (tablesize/2); hashvalue /= 2; and it's all of a sudden not so
embarassing :)
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.
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
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.
_______________________________________________
Sip mailing list https://www1.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use sip-implementors at cs.columbia.edu for questions on current sip
Use sipping at ietf.org for new developments on the application of sip