CryptGenRandom
Encyclopedia
CryptGenRandom is a cryptographically secure pseudorandom number generator function that is included in Microsoft
's Cryptographic Application Programming Interface
. 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.
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.
providers share the same implementation of CryptGenRandom, currently based on an internal function called RtlGenRandom. Only a general outline of the algorithm
had been published :
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.
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 Hebrew University 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 (including Ollydbg
and IDA Pro) to discern how the algorithm works. Their paper is the first published record of how the Windows cryptographic random number generator operates.
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.
should use the RNGCryptoServiceProvider Class.
Microsoft
Microsoft Corporation is an American public multinational corporation headquartered in Redmond, Washington, USA that develops, manufactures, licenses, and supports a wide range of products and services predominantly related to computing through its various product divisions...
's Cryptographic Application Programming Interface
Cryptographic Application Programming Interface
The Cryptographic Application Programming Interface is an application programming interface included with Microsoft Windows operating systems that provides services to enable developers to secure Windows-based applications using cryptography...
. 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
Windows 2000
Windows 2000 is a line of operating systems produced by Microsoft for use on personal computers, business desktops, laptops, and servers. Windows 2000 was released to manufacturing on 15 December 1999 and launched to retail on 17 February 2000. It is the successor to Windows NT 4.0, and is the...
implementation of CryptGenRandom (assuming the attacker has control of the machine). Microsoft later acknowledged that the same problems exist in Windows XP
Windows XP
Windows XP is an operating system produced by Microsoft for use on personal computers, including home and business desktops, laptops and media centers. First released to computer manufacturers on August 24, 2001, it is the second most popular version of Windows, based on installed user base...
, but not in Vista
Windows Vista
Windows Vista is an operating system released in several variations developed by Microsoft for use on personal computers, including home and business desktops, laptops, tablet PCs, and media center PCs...
. Microsoft released a fix for the bug with Windows XP Service Pack 3 in mid-2008.
Background
The Win32 API includes comprehensive support for cryptographic security, including native TLSTransport Layer Security
Transport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet...
support (via the SCHANNEL API) and Code signing
Code signing
Code signing is the process of digitally signing executables and scripts to confirm the software author and guarantee that the code has not been altered or corrupted since it was signed by use of a cryptographic hash....
. These capabilities are built on native Windows libraries for cryptographic operations, such as RSA and AES
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
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 cryptographyCryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
providers share the same implementation of CryptGenRandom, currently based on an internal function called RtlGenRandom. Only a general outline of the algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
had been published :
[RtlGenRandom] generates as specified in FIPSFederal Information Processing StandardA Federal Information Processing Standard is a publicly announced standardization developed by the United States federal government for use in computer systems by all non-military government agencies and by government contractors, when properly invoked and tailored on a contract...
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
MD4The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms....
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]
Source:
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 HTTPSHttps
Hypertext Transfer Protocol Secure is a combination of the Hypertext Transfer Protocol with SSL/TLS protocol to provide encrypted communication and secure identification of a network web server...
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
Information entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...
gathering on several monotonically-increasing counters that might be estimated or controlled to an extent by an attacker with local access to the system.
Hebrew University Cryptanalysis
A cryptanalysisCryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
of CryptGenRandom, published in November 2007 by Leo Dorrendorf and others from the Hebrew University of Jerusalem
Hebrew University of Jerusalem
The Hebrew University of Jerusalem ; ; abbreviated HUJI) is Israel's second-oldest university, after the Technion – Israel Institute of Technology. The Hebrew University has three campuses in Jerusalem and one in Rehovot. The world's largest Jewish studies library is located on its Edmond J...
and University of Haifa
University of Haifa
The University of Haifa is a university in Haifa, Israel.The University of Haifa was founded in 1963 by Haifa mayor Abba Hushi, to operate under the academic auspices of the Hebrew University of Jerusalem....
, found significant weaknesses in the Windows 2000
Windows 2000
Windows 2000 is a line of operating systems produced by Microsoft for use on personal computers, business desktops, laptops, and servers. Windows 2000 was released to manufacturing on 15 December 1999 and launched to retail on 17 February 2000. It is the successor to Windows NT 4.0, and is the...
implementation of the algorithm.
To take advantage of the Hebrew University 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
RC4
In cryptography, RC4 is the most widely used software stream cipher and is used in popular protocols such as Secure Sockets Layer and WEP...
, 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
Buffer overflow
In computer security and programming, a buffer overflow, or buffer overrun, is an anomaly where a program, while writing data to a buffer, overruns the buffer's boundary and overwrites adjacent memory. This is a special case of violation of memory safety....
, to get CryptGenRandom's state information for that process. Finally, CryptGenRandom refreshes its seed from entropy
Information entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...
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
Reverse engineering
Reverse engineering is the process of discovering the technological principles of a device, object, or system through analysis of its structure, function, and operation...
tools (including Ollydbg
OllyDbg
OllyDbg is an x86 debugger that emphasizes binary code analysis, which is useful when source code is not available. It traces registers, recognizes procedures, API calls, switches, tables, constants and strings, as well as locates routines from object files and libraries. Version 1.10 is the final...
and IDA Pro) 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)
- Windows 2003 Enhanced Cryptographic Provider (rsaenh.dll) (certificate 316)
- Windows 2003 Enhanced DSS and Diffie-Hellman Cryptographic Provider (dssenh.dll) (certificate 314)
- Windows 2003 Kernel Mode Cryptographic Module (fips.sys) (certificate 313)
- Windows CE and Windows Mobile Enhanced Cryptographic Provider (rsaenh.dll) (certificate 292)
- Windows CE and Windows Mobile Enhanced Cryptographic Provider (rsaenh.dll) (certificate 286)
- Windows CE Enhanced Cryptographic Provider (rsaenh.dll) (certificate 66)
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.
Source Code Access programs
There are a number of source code access programs offered by Microsoft (usually protected by very explicit EULAs) that provide access to source code not otherwise shared with the general public.Disassembly
The runtime libraries for Windows platforms can be disassembled by off-the-shelf tools such as IDA Pro and objdump. Additionally, unlike most closed-source vendors, Microsoft provides debug symbols for their release binaries. As a result, Microsoft binaries are often evaluated by third-party security practitioners. The cryptanalysis by Dorrendorf et al., mentioned above, is based on such a disassembly.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".
Using RNGCryptoServiceProvider
Programmers using .NET.NET Framework
The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...
should use the RNGCryptoServiceProvider Class.
Programming languages
- the Microsoft C++ library function rand_s uses RtlGenRandom and is recommended by Microsoft for secure applications.
- the PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
function urandom in the os module, which uses /dev/urandom on Unix-based systems, calls CryptGenRandom on Windows systems.
See also
- /dev/random/dev/randomIn Unix-like operating systems, /dev/random is a special file that serves as a random number generator or as a pseudorandom number generator. It allows access to environmental noise collected from device drivers and other sources. Not all operating systems implement the same semantics for /dev/random...
-- the Linux kernel's CSPRNG - Cryptographically secure pseudorandom number generatorCryptographically secure pseudorandom number generatorA cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
- Random number generator attackRandom number generator attackThe security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed...