Session UID might be predictable

[mthuurne]

Each Session object has a UID to identify it. This UID is generated by Site._mkuid() from a random number (from Python's Mersenne Twister) and a counter. Then an MD5 sum is computed over the string representation of both.

If the same Python process uses the same random generator (global instance from the "random" module) for outputting non-hashed values as well, an attacker would be able to learn the current state of the random generator and predict the next random number. Since the counter is also predictable, guessing the next session UID would be simple.

Is the UID intended to be secure, or is it only intended to have a low chance of collisions with other UIDs?

If it is not intended to be secure, please document this clearly, so programmers who require a secure ID know that they have to add it themselves.

If it is intended to be secure, one way of fixing it would be to use a secure random generator for generating the UID. Ticket #2685 describes a secure random generator for use by Twisted classes.

A possible way to reduce UID predictability is to instantiate a random generator which is used only for creating UIDs, instead of using a shared instance. Since all outputs based on these random numbers are hashed, it will be much harder to discover the state of the random generator. My crypto knowledge is not sufficient though to say whether this would make it secure or just less insecure, so the safer bet would be to use a secure random number.

[teratorn]

Replying to mthuurne:

Each Session object has a UID to identify it. This UID is generated by Site._mkuid() from a random number (from Python's Mersenne Twister) and a counter. Then an MD5 sum is computed over the string representation of both. If the same Python process uses the same random generator (global instance from the "random" module) for outputting non-hashed values as well, an attacker would be able to learn the current state of the random generator and predict the next random number.

This doesn't really have anything to do with twisted.web... I'm don't think we're really in the business of educating users about how to write secure applications. "Giving untrusted parties access to the raw output of the shared random number generator is a Bad Idea".

Since the counter is also predictable,

Well, the counter is only predictable if you can force or predict a server restart. Otherwise the current value is quite obscure... however it's likely to be relatively small, so if you can predict the random number generator, then you could quickly brute force the counter up from zero until you hit it.

guessing the next session UID would be simple. Is the UID intended to be secure, or is it only intended to have a low chance of collisions with other UIDs? If it is not intended to be secure, please document this clearly, so programmers who require a secure ID know that they have to add it themselves.

It is intended to be fairly secure, and it is.

MD5 has a known weakness, in that hash collisions may be generated with a pre-defined prefix value. The vulerability allows for mathematical shortcuts that cut down on the time required to generate these collisions.

This doesn't help anyone predict future UIDs, here.

If it is intended to be secure, one way of fixing it would be to use a secure random generator for generating the UID. Ticket #2685 describes a secure random generator for use by Twisted classes.

A high-traffic website would put a pretty big strain on the kernel entropy pool if it's being tapped for every new session ID.

I don't think there is anything fundamentally wrong with the current implementation. Other tasks are certainly more important in terms of developer time.

I'm gonna close the ticket, but feel free to re-open it with comments, if you think something really really needs to be done here.

[mthuurne]

Replying to teratorn:

This doesn't really have anything to do with twisted.web... I'm don't think we're really in the business of educating users about how to write secure applications. "Giving untrusted parties access to the raw output of the shared random number generator is a Bad Idea".

The user might not be aware that the random number generator is shared. In fact, if the first user of the RNG is twisted.web.server.Site and the second user of the RNG is a library used in the same application, none of the code the user has written contains a reference to the shared RNG. And even if the user is aware of it, eliminating the sharing would require patching Twisted or the library.

A high-traffic website would put a pretty big strain on the kernel entropy pool if it's being tapped for every new session ID.

Where do TCP sequence numbers get their randomness from? Typically there will be at least as many TCP streams opened as there will be sessions.

Even if we cannot use a secure random number for every session ID, using a non-shared RNG with an initial seed from a secure RNG would already be an improvement.

I don't think there is anything fundamentally wrong with the current implementation. Other tasks are certainly more important in terms of developer time.

I'll provide a patch if one of the developers has time to review it.

I'm gonna close the ticket, but feel free to re-open it with comments, if you think something really really needs to be done here.

The problem only occurs in applications that give an unprivileged or low-privileged user hints about the state of the shared RNG, which is not a common scenario. However, it is possible applications exist that fit this scenario. Since it can be solved with a very small change, I think it's worth fixing.

[teratorn]

Replying to mthuurne:

Replying to teratorn:

This doesn't really have anything to do with twisted.web... I'm don't think we're really in the business of educating users about how to write secure applications. "Giving untrusted parties access to the raw output of the shared random number generator is a Bad Idea".

The user might not be aware that the random number generator is shared. In fact, if the first user of the RNG is twisted.web.server.Site and the second user of the RNG is a library used in the same application, none of the code the user has written contains a reference to the shared RNG. And even if the user is aware of it, eliminating the sharing would require patching Twisted or the library.

A high-traffic website would put a pretty big strain on the kernel entropy pool if it's being tapped for every new session ID.

Where do TCP sequence numbers get their randomness from?

Certainly not from the high-quality entropy pool made avaialble at /dev/random.

Typically there will be at least as many TCP streams opened as there will be sessions.

Since you bring this up, why don't you tell us the answer also?

Even if we cannot use a secure random number for every session ID, using a non-shared RNG with an initial seed from a secure RNG would already be an improvement.

Python's RNG is already well-seeded.

I don't think there is anything fundamentally wrong with the current implementation. Other tasks are certainly more important in terms of developer time.

I'll provide a patch if one of the developers has time to review it.

Like I said, I think this is a waste of everyone's time. Nobody has any time to be doing, or reviewing, any unuseful work that doesn't solve any real problems.

I'm gonna close the ticket, but feel free to re-open it with comments, if you think something really really needs to be done here.

The problem only occurs in applications that give an unprivileged or low-privileged user hints about the state of the shared RNG, which is not a common scenario. However, it is possible applications exist that fit this scenario. Since it can be solved with a very small change, I think it's worth fixing.

If you're actually writing secure software, then you better damn well be aware of the cryptographic features of ALL the software you are using. I'm not holding out much hope for anyone that would actually have to be saved by a feature like this.

You're illustrating a *VERY* theoretical attack vector here. You need at least ~600 or so consecutive samples from a Meresene Twister before you can predict future values. Nothing in Twisted is going to be leaking those values. And wouldn't any leaked values be mixed up, chronologically, with the values used by twisted.web?

Please don't take my comments personally... I do thank you for the time you took to analyze this. Twisted, like most software, could certainly do with more security-conscious code-reviewing. I just don't see any reason to justify any work here. It wouldn't hurt to make the changes you're suggesting, but why do it unless there is some clearly quantifiable benefit?

If you really wish to do this, then please find someone else who has commit privileges to reopen the ticket and comment in its favor.

[mthuurne]

Use a dedicated random generator for session UIDs

[mthuurne]

Use a dedicated random generator for session UIDs, carefully seeded

[radix]

I don't see a problem with mthuurne's suggestions.

[mthuurne]

I added two patches, only one should be used.

The first patch allocates a random number generator which is only used for creating session UIDs, as opposed to using Python's shared generator. This generator is seeded by the "random" module, which (in Python 2.5) uses urandom if possible, but silently falls back to a non-secure seed otherwise.

The second patch is much like the first patch, except that it gets the seed using twisted.python.randbytes, which issues a warning if no secure random source is available.

I leave it up to you to decide which is better. Both are an improvement upon the current situation, in my opinion.

[mthuurne]

Replying to teratorn:

Where do TCP sequence numbers get their randomness from?

Certainly not from the high-quality entropy pool made avaialble at /dev/random.

Typically there will be at least as many TCP streams opened as there will be sessions.

Since you bring this up, why don't you tell us the answer also?

Because I was hoping you could tell me the answer :)

I wasn't trying to be a smartass, I am just curious how kernel programmers solved the problem of a frequent need for unpredictable numbers, since whatever solution they came up with would be sufficient for session UIDs as well.

You're illustrating a *VERY* theoretical attack vector here. You need at least ~600 or so consecutive samples from a Meresene Twister before you can predict future values. Nothing in Twisted is going to be leaking those values. And wouldn't any leaked values be mixed up, chronologically, with the values used by twisted.web?

If the shared RNG would be used for generating an image containing a lot of randomness (noise, clouds, CAPTCHA), a single image might leak enough information to deduce the RNG state from.

[glyph]

These patches will need some tests if they are to be used. Also, they should provide some explanation in docstrings.

In my opinion, the biggest problem with this code is that its motivations and security properties are completely un-explained. Let me try to explain the properties that I was originally, and quite naively, trying to provide here:

The session identifier is meant to have a few properties:

• It should be unpredictable. I originally thought that random.random was actually unpredictable, which is why it uses that.
• It should be unique, since obviously each session is its own entity. This is why it has a counter: to reduce the likelihood of collisions.
• It should be opaque. This means it shouldn't reveal any information about the server. That's why it uses a hash function: to obscure the counter.

I think that randbytes would be a reasonable way to improve that unpredictability, but adding the counter by no means guarantees a collision-free hash. It's vanishingly unlikely to have a collision already; perhaps a better way to ensure that property would be to simply test for a collision with the random data and generate some more in the highly unlikely case that it collides.

At any rate, the most important thing for such a change to do would be to provide some clear documentation of the security properties of the session key. The second most important thing would be to make sure that there is no unnecessary code here - unnecessary code is the enemy of security, since it makes it more difficult to analyze whether the desired properties are provided or not.

[mthuurne]

Replying to glyph:

These patches will need some tests if they are to be used. Also, they should provide some explanation in docstrings.

What kind of tests do you have in mind? I think it is impossible to test whether the session UID is predictable: you could demonstrate that a certain algorithm cannot predict the UID, but you can never demonstrate it for all algorithms. Also, demonstrating that one type of attack will not work says very little about other types of attack. So for unpredictability, I think we have to rely on documentation + code reviews instead of tests.

It would be possible to generate a lot of UIDs and check that there are no collisions. Are there other meaningful tests possible?

* It should be unique, since obviously each session is its own entity. This is why it has a counter: to reduce the likelihood of collisions.

An alternative would be to use more random bits.

* It should be opaque. This means it shouldn't reveal any information about the server. That's why it uses a hash function: to obscure the counter.

Fortunately, it also obscures the random generator output.

I think that randbytes would be a reasonable way to improve that unpredictability, but adding the counter by no means guarantees a collision-free hash. It's vanishingly unlikely to have a collision already; perhaps a better way to ensure that property would be to simply test for a collision with the random data and generate some more in the highly unlikely case that it collides.

The only way to have a hard guarantee that all session UIDs are unique is to persist all UIDs that were ever handed out. Unless you want to discard opaqueness, by adding a non-hashed counter or time stamp. However, "vanishingly unlikely" is good enough in practice.

A negligible chance of collisions is a requirement for a secure UID generation algorithm: if there was a non-negligible chance of collisions, a brute force attack of a client creating UIDs using the same algorithm as the server would have a practical chance of succeeding.

Using randbytes() for every UID instead of only for seeding the generator would only help if someone succeeds in getting hints about the generator state from the hashed value. The risk is draining the entropy pool of the OS urandom device, as teratorn described. I think this drain will not be a problem for light use, but during heavy use or during an attack it might be a problem; I don't know how fast an OS gathers entropy.

A balanced approach could be to use randbytes() periodically (for example, once a minute or once an hour) to modify the seed of the UID random generator. This might be overkill though.

At any rate, the most important thing for such a change to do would be to provide some clear documentation of the security properties of the session key.

You mentioned unpredictable, unique and opaque as requirements, are there more?

The second most important thing would be to make sure that there is no unnecessary code here - unnecessary code is the enemy of security, since it makes it more difficult to analyze whether the desired properties are provided or not.

Would the counter be considered unnecessary code? It does decrease predictability a tiny bit and decreases collision chances, but the random number alone would also be sufficient, especially if more random bits were used. On the other hand, the counter code is small and simple.

[exarkun]

Replying to mthuurne:

Replying to glyph:

These patches will need some tests if they are to be used. Also, they should provide some explanation in docstrings.

What kind of tests do you have in mind? I think it is impossible to test whether the session UID is predictable: you could demonstrate that a certain algorithm cannot predict the UID, but you can never demonstrate it for all algorithms. Also, demonstrating that one type of attack will not work says very little about other types of attack. So for unpredictability, I think we have to rely on documentation + code reviews instead of tests.

We don't have to choose between providing tests that demonstrate that no algorithm could ever predict the next UID and not providing any tests. Even having a simple test that makes sure two consecutively generated UID values are not equal is useful - it proves that at least the code isn't doing something trivially wrong (oops! called randbytes and dropped the result, returning just instead, etc).

It would be possible to generate a lot of UIDs and check that there are no collisions. Are there other meaningful tests possible?

No need to do "lots". 2 or 3 is sufficient. The point here isn't to test the random source for unpredictability or the hashing algorithm for lack of collisions. It's to make sure the implementation is at least using some random source or some hash. With proper factoring of the implementation, you might even invoke these two black box pieces separately, letting you test that the random source returns a different value each time and that the hash algorithm returns different outputs for different inputs. TDD really helps out here. If every part of the implementation is written to make some test pass, then you know that the tests are going to tell you if you break any part of the implementation. You still don't know if the random source is good or the hashing algorithm is good, but again - it's not the job of these tests to demonstrate either of those things.

* It should be unique, since obviously each session is its own entity. This is why it has a counter: to reduce the likelihood of collisions.

An alternative would be to use more random bits.

* It should be opaque. This means it shouldn't reveal any information about the server. That's why it uses a hash function: to obscure the counter.

Fortunately, it also obscures the random generator output.

I think that randbytes would be a reasonable way to improve that unpredictability, but adding the counter by no means guarantees a collision-free hash. It's vanishingly unlikely to have a collision already; perhaps a better way to ensure that property would be to simply test for a collision with the random data and generate some more in the highly unlikely case that it collides.

The only way to have a hard guarantee that all session UIDs are unique is to persist all UIDs that were ever handed out. Unless you want to discard opaqueness, by adding a non-hashed counter or time stamp. However, "vanishingly unlikely" is good enough in practice.

Is there a reason not to include a timestamp? It means leaking the server's notion of the time. Is there an attack vector based on that? What if it only has minute precision?

A negligible chance of collisions is a requirement for a secure UID generation algorithm: if there was a non-negligible chance of collisions, a brute force attack of a client creating UIDs using the same algorithm as the server would have a practical chance of succeeding. Using randbytes() for every UID instead of only for seeding the generator would only help if someone succeeds in getting hints about the generator state from the hashed value. The risk is draining the entropy pool of the OS urandom device, as teratorn described. I think this drain will not be a problem for light use, but during heavy use or during an attack it might be a problem; I don't know how fast an OS gathers entropy.

Even if urandom runs out of entropy, there are no known attacks, practical or theoretical, against the algorithm used by urandom to generate bytes. However, it does seem adequate to just seed a prng from urandom, rather than going to urandom each time. The potential attack here is that if the seed is discovered, the prng's future output can be predicted, or that if enough of the prng's output is learned, its state can be learned and its future output can be predicted. Using urandom for everything only helps the latter case, but the rest of the changes discussed in this ticket seem to be aimed at closing that attack vector.

A balanced approach could be to use randbytes() periodically (for example, once a minute or once an hour) to modify the seed of the UID random generator. This might be overkill though.

This is sensible, but if by "overkill" you mean that it isn't solving a realistic problem, that seems correct.

At any rate, the most important thing for such a change to do would be to provide some clear documentation of the security properties of the session key.

You mentioned unpredictable, unique and opaque as requirements, are there more?

The second most important thing would be to make sure that there is no unnecessary code here - unnecessary code is the enemy of security, since it makes it more difficult to analyze whether the desired properties are provided or not.

Would the counter be considered unnecessary code? It does decrease predictability a tiny bit and decreases collision chances, but the random number alone would also be sufficient, especially if more random bits were used. On the other hand, the counter code is small and simple.

The counter guarantees that the same value isn't given to the hash function twice. Since the hash is deterministic, providing it with the same input will generate the same output. None of the random number generators discussed guarantee they'll never generate the same output twice. So, the counter seems to serve some purpose. There are certainly other ways to accomplish this, and even by doing this, we don't guarantee that we won't generate the same session key twice (since two inputs could hash to the same output (but there are 256 ** 16 hash outputs and only 10 ** 11 possible str(random.random()) outputs)). Replacing the counter with more random bits is probably fine in practice, but there are probably other solutions too.

[mthuurne]

Replying to exarkun:

We don't have to choose between providing tests that demonstrate that no algorithm could ever predict the next UID and not providing any tests. Even having a simple test that makes sure two consecutively generated UID values are not equal is useful - it proves that at least the code isn't doing something trivially wrong (oops! called randbytes and dropped the result, returning just instead, etc).

Agreed.

What I was afraid of is getting a requirement "make a test that fails on the old code", which would be difficult to write and would not have much value against a different implementation (the test would most likely pass on predictable algorithms, as long as they are not predictable in the same way).

Is there a reason not to include a timestamp? It means leaking the server's notion of the time. Is there an attack vector based on that? What if it only has minute precision?

A high precision timer might reveal sensitive information about the server, a low precision timer will not. Most servers are expected to be synchronized via NTP anyway, so their clock is already relatively predictable.

Including an unhashed timestamp in the UID does mean that it is easy to see when a session was created by looking at the cookie. I cannot think of why that would be a problem, but it is a change compared to the current UID algorithm.

Even if urandom runs out of entropy, there are no known attacks, practical or theoretical, against the algorithm used by urandom to generate bytes.

On the other hand, if we don't care about entropy, we don't have to use urandom at all. Since urandom is an OS-wide resource, making it run out of entropy would impact other processes as well.

A balanced approach could be to use randbytes() periodically (for example, once a minute or once an hour) to modify the seed of the UID random generator. This might be overkill though.

This is sensible, but if by "overkill" you mean that it isn't solving a realistic problem, that seems correct.

It is hard for me to say what is realistic when it comes to security: I've read about attacks that I would never have thought of myself, such as the SSL hyperthreading timing issue.

Periodically inserting some entropy (for example from urandom) does not increase the theoretical strength of the algorithm, but it does mean that an attacker has a limited time window in which information about the random generator can be gathered. Also, any successful attack will be useful for a limited amount of time: only UIDs generated during the period the attack took place are compromised. Of course, if it is easy to repeat the attack, it could be done again and again for every period.

The counter guarantees that the same value isn't given to the hash function twice.

That is only true as long as the server is not restarted though.

Since the hash is deterministic, providing it with the same input will generate the same output. None of the random number generators discussed guarantee they'll never generate the same output twice.

True, but with enough random bits the chance of getting the same output twice is vanishingly small.

So, the counter seems to serve some purpose. There are certainly other ways to accomplish this, and even by doing this, we don't guarantee that we won't generate the same session key twice (since two inputs could hash to the same output (but there are 256 ** 16 hash outputs and only 10 ** 11 possible str(random.random()) outputs)). Replacing the counter with more random bits is probably fine in practice, but there are probably other solutions too.

It would be good to have at least as many different possible inputs as there are hash outputs. Using more random bits would be the simplest implementation that accomplishes that. However, it would only be secure if the hashing destroys all information about the random number. I did a bit more reading about secure hashing algorithms and it seems this property is not guaranteed. The requirement for a secure hash is weaker: it should be practically impossible to reconstruct the entire message if you know the hash. Since in our case leaking any information about the random generator state is a problem, adding more data to the hash as a kind of salt might make the whole stronger.

[exarkun]

Replying to mthuurne:

[snip] It is hard for me to say what is realistic when it comes to security: I've read about attacks that I would never have thought of myself, such as the SSL hyperthreading timing issue.

This is one aspect of the "don't have unnecessary code" thing. We can't defend against attacks we don't know about. We should avoid throwing in extra behavior because it might defend against an as yet unknown attack.

[mthuurne]

This  Wikipedia article contains a useful table with collision chances. Using the full 128 bits of the MD5 sum, chances of a random collision are small enough.

[itamar]

Could we just switch to randbytes and argue about the rest of it later? It's definitely superior to the very problematic code we have now.

[exarkun]

Could we just switch to randbytes and argue about the rest of it later? It's definitely superior to the very problematic code we have now.

Of course. I never said we shouldn't switch. Someone should write a couple unit tests and we can finally resolve this.