The probability of finding a limited set of collisions for HMACSHA256

I need some input on the use of HMAC-SHA256 in an open source project, any help appreciated.

The problem I'm solving is session fixation. We have a username, for that username we'd like to generate a session ID that would only be valid for that particular username so that it cannot be reused across users.

The session ID is calculated in the following manner:

|| denotes concatenation
key = 256 random bits from a cryptographically strong RNG
randomID = 128 random bits from a cryptographically strong RNG
username = some UTF-8 encoded string
sessionID = Base64Encode(randomID || HMACSHA256(key, username || randomID))


A few questions:

1. Will there be no collisions as long as the username <= 128 bits, i.e. the total input is never longer than 256 bits?
2. When usernames are longer than 256 bits, I assume the birthday paradox applies and you could expect a collision after 2128 distinct inputs (that's when probability reaches ~0.5)?
3. If we assume 231 valid usernames, what would the probability be that the attackers session ID would also be valid for another user and hence could be used in a session fixation attack? (A collision that does not map to another user would be useless to the attacker)

If there's anything else I should be worried about, I'd appreciate a comment on that.

If anyone's interested in the whole background on this, I'll include a pointer to the draft documentation.

-

I think most would agree that 2^128 is not plausible without UFO space alien technology (i.e., wildly successful quantum computers).

There is no currently known way to find collisions over SHA-2-256 in any plausible amount of time, with any plausible number of inputs.

As long as the key is secret, there is no known way to someone to find a username or randomID that produces a target HMAC value, or to predict the HMAC value for one username+randomID given the value for another (length extension attack).

However, another thing to be concerned about is timing leaks if you ever compare an expected HMAC value and a value received by a potential attacker. If you use a naive strcmp(), timing will tell the attacker how many initial bytes he got right and he can use that to work out the value he needs to send without even knowing the key, username, or randomID.

-
Thx! So I did understand this correctly then, pts 1 and 2? I have taken care to not leak timing information, if you'd want to look at it it's the ValidateMac function here: nwebsec.codeplex.com/SourceControl/latest#Source/… All statements should execute independent of input. Since this is .NET I'll try to get a .NET JIT compiler ninja to look at it, so the JIT compilation doesn't bite me. –  klings Jul 12 '13 at 20:15
There's a bug at codeplex, you'll need to switch to the "Session" branch to see it. But thanks for pointing out the timing issue! I'm doing my best to avoid being the subject of open source lulz tweets that have been plentiful lately. :) –  klings Jul 12 '13 at 20:24
I beleive the latest best consensus among hash function cryptographers is that SHA-2-256 or HMAC[SHA-2-256] is secure against collisions for all practical work and for the forseeable future, with the possible exception of some major major breakthroughs in quantum computing. If you want to be even more conservative, you could use SHA-2-512/256 which is an even more recent NIST standard. –  Marsh Ray Jul 12 '13 at 21:20
Thank you for your feedback, I believe HMAC-SHA256 more than covers our security needs at the moment. :) –  klings Jul 14 '13 at 22:12