2
$\begingroup$

The Python secrets module claims to produce cryptographically secure random numbers. I did some research on which random number generator is used when you call the secrets module on Windows. I found the following:

->secrets uses random

->random uses os.urandom

->os.urandom uses _PyOS_URandom() from Python/bootstrap_hash.c

->_PyOS_URandom() uses the Windows CryptGenRandom algorithm.

However, Leo Dorrendorf stated in his article that the design of the CryptGenRandom algorithm is flawed. In principle, an attacker can `predict all random values, such as SSL keys, used by a process in all its past and future operation'.

Wikipedia has the following to say about it:

A cryptanalysis of CryptGenRandom, published in November 2007 by Leo Dorrendorf and others from the Hebrew University of Jerusalem and University of Haifa, found significant weaknesses in the Windows 2000 implementation of the algorithm.

To take advantage of the vulnerability, an attacker would first need to compromise the program running the random number generator. The weaknesses in the paper all depend on an attacker siphoning the state bits out of the generator. An attacker in a position to carry out this attack would typically already be in a position to defeat any random number generator (for instance, they can simply sniff the outputs of the generator, or fix them in memory to known values). However, the Hebrew University team notes that an attacker only need steal the state bits once in order to persistently violate the security of a CryptGenRandom instance. They can also use the information they glean to determine past random numbers that were generated, potentially compromising information, such as credit card numbers, already sent.

The paper's attacks are based on the fact that CryptGenRandom uses the stream cipher RC4, which can be run backwards once its state is known. They also take advantage of the fact that CryptGenRandom runs in user mode, allowing anyone who gains access to the operating system at user level, for example by exploiting a buffer overflow, to get CryptGenRandom's state information for that process. Finally, CryptGenRandom refreshes its seed from entropy infrequently. This problem is aggravated by the fact that each Win32 process has its own instance of CryptGenRandom state; while this means that a compromise of one process does not transitively compromise every other process, it may also increase the longevity of any successful break.

Because the details of the CryptGenRandom algorithm are not public, Dorrendorf's team used reverse engineering tools to discern how the algorithm works. Their paper is the first published record of how the Windows cryptographic random number generator operates.

Does this mean that on Windows, the random numbers produced by the Python secrets module (and other modules that use CryptGenRandom) are not cryptographically secure?

$\endgroup$
1
  • 1
    $\begingroup$ From the same Wikipedia link - Microsoft released a fix for the bug with Windows XP Service Pack 3 in mid-2008. $\endgroup$
    – user93353
    Jul 12, 2023 at 7:30

1 Answer 1

3
$\begingroup$

No. CryptGenRandom on Windows is deprecated as an API, but not for security reasons, rather because the whole cryptography API has been redesigned.

The 2007 Dorrendorf et al. paper is about a weakness in the implementation of CryptGenRandom at the time. As any serious provider of cryptography implementations would do, Microsoft eventually remedied the weakness found by the researchers. It seems they weren't quick to do it (article cited in the introduction of the Wikipedia article), and I don't know if they actually improved all old Windows versions, but certainly CryptGenRandom today does not use the same mechanisms as back then. From the documentation:

In Windows Vista with Service Pack 1 (SP1) and later, an implementation of the AES counter-mode based PRNG specified in NIST Special Publication 800-90 is used. In Windows Vista, Windows Storage Server 2003, and Windows XP, the PRNG specified in Federal Information Processing Standard (FIPS) 186-2 is used.

This is a change from RC4 which was used in the Windows 2000 version that Dorrendorf et al. analyzed.

Even so, the RC4-based mechanism may have been cryptographically secure (depending on exactly how RC4 was used: RC4 itself has weaknesses that were known at the time, but at the time it was generally believed that you could avoid those weaknesses by discarding the beginning of the keystream). The problem was that the way in which the RNG operated did very little more than provide cryptographic-quality random numbers, with not much operational security.

Dorrendorf et al. show that the RNG implementation lack two properties which are unrelated to the quality of the output stream: prediction resistance and backtracking resistance. Your summary is missing a very important thing: an attacker can ”predict all random values (…)” only if the process has already been compromised. A the paper explains, if the process is fully compromised, this is moot, since the attacker has full control anyway. But their observations show that it's possible to escalate a partial compromise that leads to a disclosure of the state of the RNG. For example, if the attacker finds a flaw that leads to the RNG state being copied to an output buffer because of a buffer overread.

Because of the RC4-based design, from the RNG state at a given time, it's possible to calculate previous RNG states from the current state. The RNG lacks backtracking resistance. Modern RNG designs such as CTR_DRBG used by Windows Vista have backtracking resistance because the state transformation that produces output also transforms the RNG state in a non-invertible way.

Because the RNG does not reseed often, it is possible to predict future RNG states from the current state. The RNG lacks prediction resistance. The only way to achieve prediction resistance is to inject entropy each time the RNG is called. This was hard to achieve on older hardware due to the paucity of entropy sources, but is not hard with modern PC or smartphone hardware (it's another matter with many classes of embedded devices) whose processor has a built-in hardware random generator (e.g. RDRAND on Intel processors).

$\endgroup$
1
  • $\begingroup$ Given computational indistinguishability and the impossibility of physical audit, how do you know that RDRAND is indeed RANDom? Or exists at all? $\endgroup$
    – Paul Uszak
    Jul 12, 2023 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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