classification
Title: Attack against the pseudorandom number generator
Type: security Stage: resolved
Components: Library (Lib) Versions: Python 3.3
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: christian.heimes, georg.brandl, maker, ymaryshev
Priority: normal Keywords:

Created on 2012-10-10 11:18 by ymaryshev, last changed 2012-10-11 05:12 by christian.heimes. This issue is now closed.

Files
File name Uploaded Description Edit
POC.zip ymaryshev, 2012-10-10 11:18
Messages (5)
msg172566 - (view) Author: Yury (ymaryshev) Date: 2012-10-10 11:18
---[ Vulnerability description]

Positive Research experts have detected a vulnerability "Predictable pseudorandom numbers in Python" caused by random.random() output in Python.

By default, Mersenne Twister initialization is done during random module import and then after 312 random.random() calls that allows attackers to predict 313 random number with 2^8 accuracy based on 1, 2, 199, 200, 511, 625 random numbers.

--[Solution]
 
We recommend you to initialize random.seed() after every 312 calls that guarantees enough entropy of Mersenne Twister element statuses.

---[Credits]

Vulnerability was detected by Timur Yunusov, Positive Research Center (Positive Technologies Company)

---

1. In spite of the fact that MT states are initialized correctly, there is a practical method to exploit the vulnerability because of Python web framework peculiarities.
2. The possibility that a random number is among described 256 variants is 12,5% because there are two methods to round off numbers to the certain accuracy. This provides 8 possible variants of existing state_1[2], state_1[397], state_2[397].
You can find the code necessary to demonstrate the vulnerability (vuln.py) and exploit it (brute.py) attached.
msg172568 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2012-10-10 11:39
I don't see a problem here. It's a well known and documented fact that a PRNG like a Mersenne-Twister must not be used for any cryptographic purpose. The most of the random module is designed to be deterministic. The global instance even keeps its state after fork(). It's really not a security issue but a feature.

http://docs.python.org/library/random.html
---
The Mersenne Twister is one of the most extensively tested random number generators in existence. However, being completely deterministic, it is not suitable for all purposes, and is completely unsuitable for cryptographic purposes.
---

The os.urandom() function and random.SystemRandom class are desigend to create cryptographically strong random data that can be for most purposes except for long lived crypto keys like SSL certs.
msg172583 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2012-10-10 15:04
> 1. In spite of the fact that MT states are initialized correctly,
> there is a practical method to exploit the vulnerability because of
> Python web framework peculiarities.

What does this mean exactly?  If it means that this predictability can
be used for attacks on web frameworks because they assume cryptographic
strength of random numbers, please report it to those frameworks' 
security channels, e.g. security@djangoproject.com.
msg172619 - (view) Author: Yury (ymaryshev) Date: 2012-10-11 04:50
Thank you, you are right. Please close the issue.
msg172620 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2012-10-11 05:12
I'm closing the issue as suggested.

I created #16190 in the hope that a documentation update is going to raise awareness.
History
Date User Action Args
2012-10-11 05:12:09christian.heimessetstatus: open -> closed
resolution: rejected
messages: + msg172620

stage: resolved
2012-10-11 04:50:35ymaryshevsetmessages: + msg172619
2012-10-10 16:21:00makersetnosy: + maker
2012-10-10 15:04:41georg.brandlsetnosy: + georg.brandl
messages: + msg172583
2012-10-10 11:39:28christian.heimessetnosy: + christian.heimes
messages: + msg172568
components: + Library (Lib), - None
2012-10-10 11:18:48ymaryshevcreate