# 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.