13

According to https://www.owasp.org/index.php/Insufficient_Session-ID_Length:

Assuming that the session identifiers are being generated using a good source of random numbers, we will estimate the number of bits of entropy in a session identifier to be half the total number of bits in the session identifier.

How does one determine how many bits of entropy a particular implementation actually contains? For example, if I execute new BigInteger(130, new SecureRandom() under Java do I actually end up with 130 bits of entropy?

14

The entropy in a session identifier is the entropy of the underlying number source; a PRNG might yield good random words of 32 bits, each of them having 32 bits of entropy (however, as @forrest pointed out, entropy doesn't "carry" - it will grow until it reaches the size of the PRNG's internal state, and theoretically that state could be back-calculated given sufficient output. From then on, the PRNG output is predictable, with an entropy of zero. A "truly random" generator has an internal state of infinite size).

This means that each bit is more or less completely unpredictable (the 'more or less' stems from the PRNG being a (P)seudo random number generator).

When this 32 bit number is encoded in a string identifier, usually by hex encoding in ascii or utf8, it becomes something like "1A9F72EF". Now these are eight bytes, so 64 bits, yet they still contain the same entropy as before, which was 32 bits.

If we had used base64 encoding, our identifier would have had 6 bits of entropy for each character, i.e. 8 bits; so the entropy would be 3/4ths of the length in bits of the identifier (or the identifier would be 8/6ths the length of its binary representation).

That's where OWASP's "1/2" came from.

Now, the entropy of a source cannot be determined by observing a single instance; usually you need to know with a certainty how the source works. A random source is by definition pure entropy. A constant source (always returns 42) has an entropy of zero even when "42" is represented by six or eight bits.

Using a very rough and untrustworthy approximation, the entropy is twice the number of bits that change on average from one representation to the next, provided that the changes are random and nonrepeating. A sequence of [ 00FF, FF00, 00FF, FF00 ... ] would have all its bits changing, but there's only two symbols in the sequence, so one bit is sufficient to describe it fully; the internal state of the generator is one bit wide.

The big problem is determining whether a source is "truly" (pseudo-)random.

If you can trust SecureRandom (you probably can!), then yes, BigInteger(130, new SecureRandom()) will give you a number with 130 bits of entropy. You can encode it as a 260-bit hex sequence, or a 176-bit Base64 sequence.

Only be sure that the entropy pool feeding SecureRandom is refreshed frequently enough with some true randomness, or your identifier might become predictable. An (in)famous case is the Mersenne Twister, where having some 624 sequential values out of the generator allows recostructing the 19967 bits of its internal state via linear algebra, and thence predicting with certainty all its future values.

  • -1 for being technically incorrect. A PRNG with a good entropy source will not yield random words of 32 bits with 32 bits of entropy each. Entropy is not the same as unpredictability, so while each of those 32 bits are fully unpredictable, they do not have 32 bits of entropy each. – forest Mar 2 '18 at 23:27
  • @forest excuse me; while true that entropy is not the same as unpredictability, I believe that for truly unpredictable values (which, granted, for a PRNG isn't strictly true), it should require at least 32 bits on average to encode each 32 bits value. To quote Wikipedia, a 128-bit key that is uniformly randomly generated has 128 bits of entropy [en.wikipedia.org/wiki/… – LSerni Mar 2 '18 at 23:44
  • That is correct, however each 128 bit output of a CSPRNG does not have 128 bits of entropy. If I take AES-CTR keyed with a 128 bit key and output a gigabit of data, that whole gigabit output has "only" 128 bits of entropy, not a billion bits. While a layman or simplified answer is fine, it's better to be technically correct (i.e. to say that a CSPRNG with an n-bit seed has an output that has n bits of entropy total). – forest Mar 2 '18 at 23:46
  • @forrest yes, of course. I didn't think that could be read in my answer, but if so I need to correct it. – LSerni Mar 2 '18 at 23:47
  • I'd say that a truly random PRNG has an internal state that cannot be deduced from the output (it's not infinite. Even RC4 which is a decent CSPRNG has an internal state of a little more than a kilobit). Maybe just say that the output is as unpredictable as the key, and that both have the same entropy (which is accurate), and that a good CSPRNG's output cannot lead to deducing the key. I'll +1 if that is done cause it's still a bit confusing. – forest Mar 2 '18 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.