Since people are talking about something shorter and lighter weight than
SHA1 or MD5, and we are not trying to build a crypto system but merely have
an efficient hash that is not easily guessed, how about something like
CRC-16 or CRC-32 but with a random seed? Even if the CRC algorithm is fixed
and known, it's still very hard to invert and crack the random seed, as long
as you run more than a few non-zero bytes through it. Beyond that potential
weakness, which may not be a problem at all in this application, either of
the two common CRC's is a good hash. Since all the important CPU's today
have word widths that are at least 32-bits, I would propose simply using
CRC-32 with a randomly chosen seed as the initial CRC register value instead
of zero. If the data stream is extremely short, a slightly longer bit of
random salt could be prepended to the data stream instead. Considering the
birthday bound, which almost applies, you'd need around 64K random data
streams to expect one hash collision, so it would be appear to make open
relaying impractical. If people like, you could change the seed or salt
periodically, as long as the original time (or a key sequence number) were
preserved to tell which key to use later. If the key were changed twice per
day, a one-byte key sequence number would be good for 128 days of messages.
Having used CRC's in a number of applications, I know they are fairly
lightweight computationally, even with CPU's far less capable than the
Pentium class. Being a hardware guy, I personally prefer to do this with a
little silicon :) Seriously, though, the software calculation will still
take far less time than the disk access to store the result and it's not
very many total CPU cycles, depending on the length of the data stream.
Perhaps any crypto experts in the group could suggest a superior lightweight
function suitable for the range of data lengths to be hashed that is also
secure enough.
If people are interested, I would be willing to provide a couple of C
functions for people to evaluate. I haven't read the SRS draft, so I don't
know the details of what is to be hashed. My assumption is that it is a
null-terminated UTF-8 string, but if it is something different, please
educate me. I also need to know the lower bound on the length of the data
stream to be hashed, so I know whether to use a 32-bit random seed to
initialize the CRC register or a longer bit of random salt prepended to the
data.
Regards,
Seth Goodman
Goodman Associates, LLC