CryptGenRandom

CryptGenRandom is a deprecated [1] cryptographically secure pseudorandom number generator function that is included in Microsoft CryptoAPI. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed. A 2007 paper from Hebrew University suggested security problems in the Windows 2000 implementation of CryptGenRandom (assuming the attacker has control of the machine). Microsoft later acknowledged that the same problems exist in Windows XP, but not in Vista. Microsoft released a fix for the bug with Windows XP Service Pack 3 in mid-2008.[2]

Background

The Win32 API includes comprehensive support for cryptographic security, including native TLS support (via the SCHANNEL API) and code signing. These capabilities are built on native Windows libraries for cryptographic operations, such as RSA and AES key generation. These libraries in turn rely on a cryptographically secure pseudorandom number generator (CSPRNG). CryptGenRandom is the standard CSPRNG for the Win32 programming environment.

Method of operation

Microsoft-provided cryptography providers share the same implementation of CryptGenRandom, currently based on an internal function called RtlGenRandom.[3] Only a general outline of the algorithm had been published as of 2007:

[RtlGenRandom] generates as specified in FIPS 186-2 appendix 3.1 with SHA-1 as the G function. And with entropy from:

  • The current process ID (GetCurrentProcessID).
  • The current thread ID (GetCurrentThreadID).
  • The tick count since boot time (GetTickCount).
  • The current time (GetLocalTime).
  • Various high-precision performance counters (QueryPerformanceCounter).
  • An MD4 hash of the user's environment block, which includes username, computer name, and search path. [...]
  • High-precision internal CPU counters, such as RDTSC, RDMSR, RDPMC

[omitted: long lists of low-level system information fields and performance counters] [4]

Security

The security of a cryptosystem's CSPRNG is significant because it is the origin for dynamic key material. Keys needed "on the fly", such as the AES TLS session keys that protect HTTPS sessions with bank websites, originate from CSPRNGs. If these pseudorandom numbers are predictable, session keys are predictable as well. Because CryptGenRandom is the de facto standard CSPRNG in Win32 environments, its security is critical for Windows users.

The specifics of CryptGenRandom's algorithm have not been officially published. As with any unpublished random number generation algorithm, it may be susceptible to theoretical weaknesses including the use of outdated algorithms, and a reliance for entropy gathering on several monotonically-increasing counters that might be estimated or controlled to an extent by an attacker with local access to the system.

Cryptanalysis

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.[5]

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.

Common Criteria

Windows 2000, XP and 2003 have all successfully undergone EAL4+ evaluations, including the CryptGenRandom() and FIPSGenRandom() implementations. The Security Target documentation is available at the Common Criteria Portal, and indicates compliance with the EAL4 requirements. Few conclusions can be drawn about the security of the algorithm as a result; EAL4 measures products against best practices and stated security objectives, but rarely involves in-depth cryptanalysis.

FIPS validation

Microsoft has obtained validation of its RNG implementations in the following environments:

  • Windows Vista RNG implementations (certificate 321)[6]
  • Windows 2003 Enhanced Cryptographic Provider (rsaenh.dll) (certificate 316)[6]
  • Windows 2003 Enhanced DSS and Diffie-Hellman Cryptographic Provider (dssenh.dll) (certificate 314)[6]
  • Windows 2003 Kernel Mode Cryptographic Module (fips.sys) (certificate 313)[6]
  • Windows CE and Windows Mobile Enhanced Cryptographic Provider (rsaenh.dll) (certificate 292)[6]
  • Windows CE and Windows Mobile Enhanced Cryptographic Provider (rsaenh.dll) (certificate 286)[6]
  • Windows CE Enhanced Cryptographic Provider (rsaenh.dll) (certificate 66)[6]

These tests are "designed to test conformance to the various approved RNG specifications rather than provide a measure of a product’s security. [...] Thus, validation should not be interpreted as an evaluation or endorsement of overall product security." Few conclusions can be drawn about the security of the algorithm as a result; FIPS evaluations do not necessarily inspect source code or evaluate the way RNG seeds are generated.[7]

Alternatives

API level

Windows developers have several alternative means of accessing the CryptGenRandom functionality; these alternatives invoke the same algorithm and share the same security characteristics, but may have other advantages.

Using RtlGenRandom

"Historically, we always told developers not to use functions such as rand to generate keys, nonces and passwords, rather they should use functions like CryptGenRandom, which creates cryptographically secure random numbers. The problem with CryptGenRandom is you need to pull in CryptoAPI (CryptAcquireContext and such) which is fine if you're using other crypto functions.

On a default Windows XP and later install, CryptGenRandom calls into a function named ADVAPI32!RtlGenRandom, which does not require you load all the CryptAPI stuff. In fact, the new Whidbey CRT function, rand_s calls RtlGenRandom".[8]

Using RNGCryptoServiceProvider

Programmers using .NET should use the RNGCryptoServiceProvider Class.[9]

Using Cryptography API: Next Generation (CNG)

The CNG [10] is a long term replacement for the deprecated Crypto API. It provides an equivalent function BCryptGenRandom[11] as well as dedicated functions for key generation.

Programming languages
  • the Microsoft C++ library function rand_s uses RtlGenRandom and is recommended by Microsoft for secure applications.[12]
  • the Python function urandom in the os module, which uses /dev/urandom on Unix-like systems, calls CryptGenRandom on Windows systems.[13]
  • the Java JCA Provider "SunMSCAPI" available with OpenJDK and Oracle distributions of the JRE on Windows provides a SecureRandom implementation with the algorithm name Windows-PRNG. This class forwards all queries for random or seed bytes as well as setting additional seed bytes to native CryptGenRandom.[14]
gollark: Due to something something cache locality.
gollark: The most performant way would probably be an array containing all the nodes, and each thing storing indices to its children and not actual pointers.
gollark: WRONG!
gollark: Although you might need a Box<> to avoid apiology there, hmm.
gollark: SmallVec, quite possibly.

See also

References
  1. CryptGenRandom Function (Windows)
  2. "Microsoft confirms that XP contains random number generator bug". Archived from the original on 2008-06-22.
  3. RtlGenRandom Function (Windows)
  4. Writing Secure Code, Second Edition. ISBN 0-7356-1722-8.
  5. Dorrendorf, Leo; Zvi Gutterman; Benny Pinkas. "Cryptanalysis of the Random Number Generator of the Windows Operating System" (PDF). Archived from the original (pdf) on 2012-09-06. Retrieved 2007-11-12.
  6. "RNG Validation List". NIST Computer Security Division. Retrieved 18 June 2013.
  7. "The Random Number Generator Validation System (RNGVS)" (PDF). National Institute of Standards and Technology Computer Security Division. 31 January 2005. Archived from the original (PDF) on 24 February 2013. Retrieved 18 June 2013.
  8. Michael Howard's Web Log : Cryptographically Secure Random number on Windows without using CryptoAPI
  9. "Archived copy". Archived from the original on 2006-09-08. Retrieved 2007-08-27.CS1 maint: archived copy as title (link)
  10. Crypto API Next Generation (Windows)
  11. BCryptGenRandom (Windows)
  12. http://msdn.microsoft.com/en-us/library/sxtz2fa8(VS.80).aspx Visual C++ Developer Center , rand_s
  13. https://docs.python.org/2/library/os.html#os.urandom Python Library Reference, OS module
  14. http://docs.oracle.com/javase/8/docs/technotes/guides/security/SunProviders.html#SunMSCAPI Oracle Java SE 8 technical documentation, Sun Providers
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.