Subject: Hashing (Re: [manet] Need for DPD header (SMF document discussion))

From: "Charles E. Perkins" <[email-masked]>
Date: Tue, 01 May 2007 08:56:55 -0700

Hello Joe,

I've done some more testing, enough to be
satisfied with the results at least for the
current purposes.

I have tested thousands of random IP
addresses.  For all the addresses I have
tested, I supplied every possible combination
of 16 bits as payload.  I am pretty sure the
results would be almost identical for 65,536
different payloads of almost any description,
but my payloads turned out to be very fast
to implement :-)

For these payloads, 44 bits of MD5 hash
did not produce even one single instance of
duplication, for any of the IP addresses
I tested.

If I run the same test with 40 bits of MD5
hash, over the thousands of IP addresses,
I get duplication for only three of the random
IP addresses.

I think that, practically speaking, 40 bits
is enough, but we might want to go for
overkill and use 48 bits anyway.  I also
think that MD5 can be modified to do a lot
less work and still produce 48 bits.  Now, it
works hard enough to produce 128 bits, and
two-thirds of that result will be wasted; we
might want to use a much simpler hash
function.  Maybe we could get the processor
expense down into the tens of microseconds.

And, again, time per trial is about 1 millisecond,
from which we could guesstimate the number
of processor instructions per data block.

The very fast speed of MD5 on today's processors
exposes a bug in the RFC 1321 code, since the start
time equals the end time.  Unless you fix the problem,
the speed computation then involves dividing by zero.
I found some other bugs as well, sigh...

Regards,
Charlie P.

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