hex_entropy() produces same digest under forking server

[songofacandy@…]

I use Trac with customized forking server that imports imports trac before fork to reduce initialization time.

On that server, trac produces same cookie for many people.

I found Trac stores random number generator on global variable. This makes all of forked server produces same hexdigest.

I think RNG should not initialized at import time. Following patch fixes it.

--- a/trac/util/__init__.py
+++ b/trac/util/__init__.py
@@ -554,9 +554,9 @@
     return info
 
 # -- crypto utils
-_entropy = random.Random()
 
 def hex_entropy(bytes=32):
+    _entropy = random.Random()
     return sha1(str(_entropy.random())).hexdigest()[:bytes]

[Jun Omae]

The code, _entropy = random.Random(), has been committed in [10115] against a plugin which calls random.seed() (see comment:ticket:8969:16).

However, I understand that the code has a problem in your situation.

I think it would be better as the following.

trac/util/__init__.py

@@ -558 +558 @@
 _entropy = random.Random()
 
 def hex_entropy(bytes=32):
-    return sha1(str(_entropy.random())).hexdigest()[:bytes]
+    s = '%s/%s/%s' % (os.getpid(), time.time(), _entropy.random())
+    return sha1(s).hexdigest()[:bytes]
 
 
 # Original license for md5crypt:

[Remy Blank]

We could also use os.urandom() as an entropy source, with a fallback in case it raises NotImplementedError (as mentioned in the doc).

[songofacandy@…]

I believe os.urandom() is the best way to produce cookie. random.Random() uses os.urandom at __init__ and fallback to time.time if it raises NotImprementedError.

It is one reason for I against having _entropy as a global. Sharing one entropy between forked processes seems very bad at security point of view.

[Remy Blank]

Replying to songofacandy@…:

It is one reason for I against having _entropy as a global. Sharing one entropy between forked processes seems very bad at security point of view.

Well, your use case is somewhat special. The normal use case is for each process to fully initialize its environment. The issue comes from sharing an initialized environment.

Although… come to think of it, the Random instance isn't marked as thread-safe in the documentation, which suggests creating one instance per thread. So we actually have an issue also in the common multi-threaded case.

We could use a thread-local object, and instantiate a new Random instance in each thread on first use. This would ensure that each thread has its own independent and properly seeded generator. But it also sounds a bit complicated. Better ideas welcome.

[INADA Naoki <songofacandy@…>]

random.Random() is not a cryptographic RNG so reusing it repeatedly is also dangerous in normal web server like mod_wsgi.

[Remy Blank]

Replying to INADA Naoki <songofacandy@…>:

random.Random() is not a cryptographic RNG so reusing it repeatedly is also dangerous in normal web server like mod_wsgi.

We're passing its output through SHA1, so it should be fine.

[Remy Blank]

Heh, I had a bit of an over-engineering session here ;)

First, a small correction to what I wrote in comment:4. Python's random number generator is actually thread-safe. The documentation only suggests creating separate generators for each thread if the generators shouldn't share state.

I have implemented two rather complicated fixes for this issue:

• 10397-thread-safe-random-r10828.patch​ creates a separate generator for each thread on first use.
• 10397-lazy-random-r10828.patch​ keeps a single generator, but initializes it on first use, which hopefully is after forking.

And then, there's Jun's patch above, which is very simple, readable, and probably works just as well. So unless anyone objects, we're going to go with Jun's solution.

[Remy Blank]

Per-thread random generator.

[Remy Blank]

Single lazily-initialized generator.

[INADA Naoki <songofacandy@…>]

Replying to rblank:

Replying to INADA Naoki <songofacandy@…>:

random.Random() is not a cryptographic RNG so reusing it repeatedly is also dangerous in normal web server like mod_wsgi.

We're passing its output through SHA1, so it should be fine.

No! SHA1 is just a hash. It makes difficult to attack but not impossible.

Session key maker should take entropy repeatedly. Random() takes entropy only at initialization time.

[INADA Naoki <songofacandy@…>]

FYI: ​https://www.owasp.org/index.php/Guide_to_Cryptography#Reversible_Authentication_Tokens

The only way to generate secure authentication tokens is to ensure there is no way to
predict their sequence. In other words: true random numbers.
It could be argued that computers can not generate true random numbers, but using new
techniques such as reading mouse movements and key strokes to improve entropy has 
significantly increased the randomness of random number generators. It is critical 
that you do not try to implement this on your own; use of existing, proven implementations 
is highly desirable.

[Jun Omae]

Replying to INADA Naoki <songofacandy@…>:

FYI: ​https://www.owasp.org/index.php/Guide_to_Cryptography#Reversible_Authentication_Tokens […]

Thanks for the information! Our implemention for the token looks it is able to predict the sequence, in my patch also.

Another patch is here; Always use os.urandom() directly if available. Instead of 'Random()` class which isn't thread safe. When the method isn't available, it is probably still able to predict….

Thoughts?

trac/util/__init__.py

@@ -555 +555 @@
 
 # -- crypto utils
 
-_entropy = random.Random()
+try:
+    os.urandom(4)
+    def hex_entropy(bytes=32):
+        return sha1(os.urandom(8)).hexdigest()[:bytes]
+except NotImplementedError:
+    def hex_entropy(bytes=32):
+        s = '%s/%.16e/%s' % (os.getpid(), time.time(), id({}))
+        return sha1(s).hexdigest()[:bytes]
 
-def hex_entropy(bytes=32):
-    return sha1(str(_entropy.random())).hexdigest()[:bytes]
 
-
 # Original license for md5crypt:
 # Based on FreeBSD src/lib/libcrypt/crypt.c 1.2
 #

[Remy Blank]

Replying to INADA Naoki <songofacandy@…>:

No! SHA1 is just a hash. It makes difficult to attack but not impossible.

I defy you to predict the next session key, given only the current session key (in a reasonable time). You can't, because you would have to derive the current state of the random generator from the session key, which is computationally difficult because the hash is a (cryptographically secure) one-way function.

Our current implementation of hex_entropy() isn't broken. I'm not against using urandom(), which is indeed the safest way to go, provided:

• It's not massively slower than what we currently have. It shouldn't be, and a quick test should show that.
• The fallback if urandom() isn't available is at least as good as what we have today. Jun's implementation in comment:10 isn't, because it removes the entropy generator in that case, and only relies on os.getpid() and time.time(). This is insufficient, as the time can be predicted, and the other items are constant and could be leaked by other means.

Also, Jun, you could simply add os.getpid(), time.time() and _entropy.random(), and take the str() of the sum (saves a few string operations).

I'm also open to completely new implementations (for the fallback), provided they have been shown secure. That is, I only want to exchange our non-proven, but probably reasonably secure implementation with a new one if the latter has better characteristics.

[INADA Naoki <songofacandy@…>]

Replying to jomae:

I love your patch.

[INADA Naoki <songofacandy@…>]

Sorry, I may wrong. I don't know it's safe or not now.

Replying to rblank:

Replying to INADA Naoki <songofacandy@…>:

No! SHA1 is just a hash. It makes difficult to attack but not impossible.

I defy you to predict the next session key, given only the current session key (in a reasonable time). You can't, because you would have to derive the current state of the random generator from the session key, which is computationally difficult because the hash is a (cryptographically secure) one-way function.

Our current implementation of hex_entropy() isn't broken. I'm not against using urandom(), which is indeed the safest way to go, provided:

• It's not massively slower than what we currently have. It shouldn't be, and a quick test should show that.
• The fallback if urandom() isn't available is at least as good as what we have today. Jun's implementation in comment:10 isn't, because it removes the entropy generator in that case, and only relies on os.getpid() and time.time(). This is insufficient, as the time can be predicted, and the other items are constant and could be leaked by other means.

Also, Jun, you could simply add os.getpid(), time.time() and _entropy.random(), and take the str() of the sum (saves a few string operations).

I'm also open to completely new implementations (for the fallback), provided they have been shown secure. That is, I only want to exchange our non-proven, but probably reasonably secure implementation with a new one if the latter has better characteristics.

[Jun Omae]

Replying to comment:7:

First, a small correction to what I wrote in comment:4. Python's random number generator is actually thread-safe. The documentation only suggests creating separate generators for each thread if the generators shouldn't share state.

Sorry, now I just read it.

Replying to comment:11:

Our current implementation of hex_entropy() isn't broken. I'm not against using urandom(), which is indeed the safest way to go, provided:

Ok. I agree that the current implementation which uses Random.random() with SHA-1 makes it enough difficult to predict using a rainbow table and some other approachs.

Fixing the original issue; +1 for 10397-lazy-random-r10828.patch​, I think a same entropy should not be shared between forked processes.

BTW, hex_entropy() cannot generate a token longer than 40 bytes. But we pass 64 in the unit test at trac/util/tests/__init__.py. Should we fix the method?

[Remy Blank]

Replying to jomae:

Fixing the original issue; +1 for 10397-lazy-random-r10828.patch​, I think a same entropy should not be shared between forked processes.

Are you sure? Your patch in comment:1 is much simpler, and solves the issue as well.

To be honest, I would prefer using os.urandom() in hex_entropy(), and fall back to your impelmentation if the former isn't available. Path coming shortly.

BTW, hex_entropy() cannot generate a token longer than 40 bytes. But we pass 64 in the unit test at trac/util/tests/__init__.py. Should we fix the method?

Yes, we should. That was my fault, there.

[Remy Blank]

10397-use-urandom-r10832.patch​ is my last attempt. It uses os.urandom() if available, and falls back to a technique similar to comment:1 if not. It exposes the random sequence generator as urandom(), and should generate different sequences in different processes, therefore solving the original issue.

[Remy Blank]

Use os.urandom() if available.

[Remy Blank]

Yes, I'm pretty sure using os.urandom() is the best solution. Patch applied in [10834].