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:


Will there be no collisions as long as the username &lt;= 128 bits, i.e. the total input is never longer than 256 bits?
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)?
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.