Generating Unique Keys

[Trevor Perrin]

Paul Rubin <phr-n2003b at NOSPAMnightsong.com> wrote in message news:<7xvg09c8bi.fsf at ruckus.brouhaha.com>...
> trevp at trevp.net (Trevor Perrin) writes:
> > I think that's a little iffy - SHA1 has a "length extension" property,
> > where if you know h(m) for some message m that's a multiple of the
> > block length (64 bytes in this case) you can compute h(m+x) (i.e. m
> > with x appended).  So if one of your unique integers was a prefix of
> > another, and your secret_prefix was the right size, you'd be in
> > trouble.  It would be better to use hmac-sha1 with the secret_prefix
> > as the key. 
> 
> We're talking about ordinary 32-bit integers, so it would take a
> difficult combination of circumstances to make that attack work,
> but yeah, using hmac would remove the issue.

you're right, with normal integers I don't think there's a
vulnerability, there would only be one if the appended values could
somehow have a prefix that matched a previous value's SHA1 padding. 
Still, hmac's cheap and easy, it's a good habit to always use it for
keyed hashing, so you don't have to worry about this sort of nuance
(I'm sure you know this, just for anyone following along)..
   
> 
> > And it would be better to generate the secret_prefix as a good
> > random number on system startup, not bake it into a configuration.
> 
> If you've got a source of good random numbers, you can just use them
> directly as tokens and not need this hashing stuff.

Sorry for being vague - by a "good random" value I meant one from egd,
or hardware, or from polling and mixing together a bunch of OS values,
thread timings, etc..  These "good random" values are usually
expensive to get or there's not that many of them, so if you needed
lots of them to use as session identifiers, you'd probably get one
once for use as a key, then use repeated hashing (your demonstration)
or ciphering (my demonstration) to get subsequent values, and reseed
with a "good random" value periodically.

As for getting these "good random" values on different systems, the
paper below has a pretty good discussion of the issues involved, and
the techniques are implemented in cryptlib so you can see what the
code looks like:

http://www.cs.auckland.ac.nz/~pgut001/pubs/usenix98.pdf
http://www.cs.auckland.ac.nz/~pgut001/cryptlib/


Trevor