Dirk-Willem van Gulik wrote:
Unfortunately, hashing blows away guaranteed uniqueness ("one-way" => not 1-1), so if your last step is a hash, you will need to keep the meteor helmets handy. The "uniqueness bits" need to be either left alone or encrypted to preserve uniqueness of the result.On 10 Jan 2003, Eric Rescorla wrote:There's nothing wrong with what you propose, but it's sort of like saying "maybe I should wear a helmet at all times because a meteor might drop on my head". Sure, it could happen, btu it's not the thing I'd worry about.Except that hash( i++ . secret).i is generally a lot cheaper and easier to code cross platform than using a true cryptographic random generator with the right tie in with hardware. And it happens to have a hard-hat aspect thrown in as a freebee. Dw
I strongly agree with Eric, however, that it is *incredibly* unlikely that the multiple reports of apparent collisions are in fact due to Tomcat's (unpatched) session key generation algorithm. I ran some tests last year on an algorithm very similar to what Tomcat uses (using SHA-1 instead of MD5 after adding some other stuff to the bytes from SecureRandom) and I found that the empirical probablility distribution of the number of matching bytes in pairs of generated strings followed the expected binomial distribution almost exactly. Among other things, this implies that the probability of an exact match among two such strings really is 1/2^n where n is the number of bits in the strings. It also supports the expectation that if you generate m strings, the probability that any two of them are identical is less than C(m,2)/2^n (where C(m,2) = m(m-1)/2 -- the number of pairs that you can make among the m strings). To illustrate how silly the helmets look, here are some examples:
n = 128, m = 10000 => p(collision) < 1.5 E-31
n = 128, m = 100000 => p(collision) < 1.5 E-29
n = 128, m = 1000000 => p(collision) < 1.5 E-27
n = 64, m = 1000000 => p(collision) < 2.7 E-8
...
n = 128, m = 2^64 ~ 3.4 E+38 => p(collision) < .5
(Eric's "reasonable chance" threshold)
If end users are reporting session collisions, this means that they must be happening with frequency too large to reasonably attribute to chance. Therefore, either the applications or Tomcat itself must have some concurrency problems independent of the session ID generation.
-Phil
-- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
-- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
