Transcript PRNG

Security and Random Number
Generators
Benny Pinkas, University of Haifa
Zvi Gutterman, Leo Dorrendorf, Tzachy Reinman
Hebrew University
In this talk

What are PRNGs (pseudo-random number
generators)?


The generator used by Windows


Why are they important?
Its algorithm, and its weaknesses.
A little on the generator used by Linux


Its algorithm, and its weaknesses.
Security issues when using a generator in a systems
without a hard disk.
Why are random number
generators important?
Usage of random bits
 What
are random numbers?
 Many
applications need random bits for
their operation
 This
is particularly true for security
applications
Every encryption system needs a key
Alice
encrypted channel
Bob
K
K
must share a random key K


Cryptosystem designer writes
 “… Pick a key K at random …”
This is implemented as


CryptGenRandom(Key, 16)
This is relevant for all encryption protocols (SSL, SSH, etc.)
Usage of random bits: http session ids
id1
id2

Two users run sessions with the same web server. How can the
server distinguish between them?

The http protocol is stateless. The server therefore assigns a
different id to every session, which is used in every http message
(as a cookie, or part of the url).
Usage of random bits: http session ids
id1
id2

An attacker that knows the session id of a client can impersonate
it.

Session ids must therefore be random.

[GM05] showed how to guess session ids in the Apache Java
implementation for Servlet 2.4.
Security of random number
generators
Security


Applications are designed to be secure when using truly
random bits.
Truly random bits are hard to get
  instead use pseudo-random bits (from a pseudorandom number generator - PRNG)
 The PRNG is implemented in software



Input: a small random seed
Output: a long stream which should look random
Applications are now only secure if the output of the
PRNG cannot be distinguished from a random string.
(bad example: SSL in Netscape [GW96].)
Possible Random Number Generators

Pure hardware generator (of true randomness)


Application based PRNGs




Cost / portability / interface issues
Too little noise available for initialization (seeding)
Implementer can make mistakes
(The generators provided by most programming languages are
insecure for security related applications)
Operating system based PRNGs



Seeding can use system based noise/entropy (process
scheduling, hard disk timing, etc.)
PRNG can be implemented and hidden in the kernel
Implementer is less likely to make mistakes…
Why investigate the PRNGs of major
operating systems?

The security of all applications depends on the
PRNGs provided by the major operating systems




But…
The algorithms and code of these generators were
never published !
We don’t know how they are initialized !
Yet their output is crucial for almost every security
application !
Operating system based PRNGs


The PRNG keeps an internal state, which advances (in a
deterministic way) when output is generated.
The state is periodically refreshed with entropy generated by the
operating system.
OS
Operating system based PRNGs


When analyzing PRNG security, we assume that everything but the
initial seed (system entropy) is known to the attacker
The OS manufacturer might try to hide the algorithm, but reverse
engineering can find it…
secret
OS
secret
Desired security properties
Desired property 1: Pseudo-randomness
OS
From the outside, the output looks random.
(Therefore, it can be used instead of truly random bits)
Desired property 2: Forward security

An attacker which learns a future state of the PRNG will
not be able to compute the current state.

A mandatory requirement of the German evaluation guidance for
PRNGs.
HARD
compromised
Desired property 3: Backward security (breakin recovery)

An attacker that learned an internal state in the past
cannot learn the current state, assuming that sufficient
entropy is used to refresh the state.
system entropy
compromised
Statei-1
outputi-1
Statei
outputi
Statei+1
outputi+1
Statei+2
outputj
Statei+3
outputi+3
Statei+4
outputi+4
Cryptanalysis of the Windows
random number generator
With Leo Dorrendorf, Zvi Gutterman
Hebrew University
ACM CCS 2007
CryptGenRandom

The only API provided by Windows OS for
getting secure random numbers

The world’s most common PRNG ?

Used by Internet Explorer to generate SSL keys

Its exact design and code were unknown

Security by obscurity?
Our research

Examined the binary code of Windows 2000



Identified the algorithm used by the PRNG




Windows 2000 is still the 2nd/3rd most popular OS
PRNGs of all Windows systems are said to be similar
Did not have access to the source code.
Used static and dynamic reverse engineering. This was
not easy.
Verified the algorithm by writing a user-mode simulator
which outputs the same values as the OS.
Showed attacks on forward and backward security
The main loop (never before published!)
CryptGenRandom (Buffer , Len)
// output Len bytes to buffer
while (Len >0) {
R := R  get_next_20_rc4_bytes ()
State := State  R
RC4 is a stream cipher
T := SHA-1’( State )
SHA-1 is a hash function
Buffer := Buffer | T
// | denotes concatenation
R[0..4] := T[0..4]
// copy 5 least significant bytes
State := State + R + 1
Len := Len − 20
}
CryptGenRandom

Scoping: a different state is kept for every process/thread

State is stored in static DLL space and in the stack (not in the
kernel).

Initialization is based on hashing 3584 bytes of system
data (most of this data is predictable).

Reseeding: after a process reads 128 Kbytes of output
from CryptGenRandom initialization is repeated.

This might never happen.
Attacks
We do not know how to attack the pseudorandomness of the generator

The main loop uses strong cryptographic functions (RC4
and SHA1)
RC4, SHA1

We do not know how to distinguish the PRNG’s output from
random, or compute state from output.
Attack on backward security (learning
future outputs)


Since we now know the algorithm, an attacker that learns
the state can compute future states and outputs until the
next entropy refresh.
 Entropy refreshes are very rare, and therefore the
attack is very severe.
The generator should have been refreshed more often.
EASY
EASY
Attack on forward security (learning
previous states)
Main result: given Statei+1 it is possible to compute
Statei with 223 work.
RC4, SHA1
Also easy!!!
Implications

Microsoft: “this is a local information disclosure
vulnerability and has no possibility of code
execution and cannot be accessed remotely.”

But,


New remote execution attacks (e.g., buffer overflows)
are found every week.
Our attack can be used to amplify their effect.
Implications: possible attack scenario

Attacker gets access to the machine


Buffer overflow, temporary physical access (@ café).
Attacker learns a single state.

Does not need to control the machine afterwards.
The new attack

Attacker can now compute all states and outputs (in the
past and in the future). from the previous to the next
entropy refreshes


Does not need any more interaction with the system
Can now, e.g., decrypt all SSL connections of this machine.
hundreds of SSL sessions
Previously known attacks - key loggers

Attacker can only learn about the machine in the period
of time it owns it


Cannot learn about the past
To learn about the future it needs a long-lived channel with the
attacked machine
What about XP

The external layer of the PRNG in XP is identical
More complex than
while (Len >0) {
Windows 2000
R := R  SystemFunction036()
No forward security
State := State  R
here means no
T := SHA-1’( State )
forward security for
Buffer := Buffer | T
the entire PRNG
// | denotes concatenation
R[0..4] := T[0..4]
// copy 5 least significant bytes
State := State + R + 1
Len := Len − 20
}
News Flash!

MSFT’s first answer:
“…(later versions of Windows) contain various changes
and enhancements to the random number generator.”

MSFT’s later answer:


XP is vulnerable to the attack.
Vista, Windows Server 2008 and Windows Server 2003
SP2 are not affected by the attack.


Even tough they claimed that the Vista PRNG is secure, it has
been changed in SP1.
The XP vulnerability will be fixed in SP3.
Analysis of the Linux
random number generator
With Zvi Gutterman, Tzachy Reinman
Hebrew University
IEEE Symposium on Security and Privacy, 2006
Black Hat 2006
The PRNG of Linux
Engineering: Implemented in the kernel.
Complex structure, hundreds of patches to date,
changes on a weekly base.
 Used by many applications



TCP, PGP, SSL, S/MIME, …
Two interfaces


Kernel interface – get_random_bytes (non-blocking)
User interfaces –
/dev/random
(blocking)
“extremely
secure”
/dev/urandom
(non-blocking)
On reverse engineering




The Linux PRNG is part of the Linux kernel and hence its
source is open
The entire code is 2500 lines written in C.
The code is unclear and is constantly being patched.
There was no clear description of it.
Tools we used to analyze the code:



Static analysis
Kernel modification: required many kernel builds, while ensuring
that kernel changes do not affect generator entropy usage.
We implemented and confirmed our findings with a user
mode simulator.
LRNG structure
A
A
keyboard
Primary
Entropy Sources
interrupts
/dev/random
Secondary
mouse
C
A
E
A
Entropy
Pool
512 bytes
128 Bytes
E
Urandom
E
disk
A
128 Bytes
E
blocking
/dev/urandom
get_random_bytes
non-blocking
A
A



Entropy is constantly gathered and added to the pools (unlike
Windows).
Most entropy comes from Hard Disk reads/writes.
Actual entropy in every event is very limited. But there are many
events.
Comparison to Windows

We showed an attack on forward security in Linux, but it is
less efficient than in Windows (264 time vs. 223 in W2K)
The implications of the attack are less severe (frequent
entropy updates in Linux vs. infrequent updates in
Windows)

Also, in Linux



Generator is in kernel space 
Blocking interface (/dev/random) 
It is easy to run a DoS attack (even by remote attackers).
Implications to disk-less systems

More and more systems are using solid state
(flash) based storage instead of hard disks.



Other sources of entropy are quite limited (user
input, system interrupts).


The timing of HD r/w operations is unpredictable, but
solid state operations always have the same timing.
HD timing is the major source of entropy for the Linux
PRNG.
They might be guessed by an attacker.
Possible threat to the security of the Linux PRNG
in many future systems.
Analysis of a certain Linux based device

A surprising finding: The device always boots with one of 6
possible values of the PRNG state (therefore it is easy to
listen to encrypted communication to/from this device!).



During reboot, the PRNG



The device uses solid state storage and no HD.
The PRNG does not save its state at shutdown.
Reads values from a hardware based noise generator.
Copies the system clock onto its state.
But, at that time


Hardware noise generator does not affect output of PRNG.
System clock is not yet initialized.
Conclusions
The quality of the output of pseudo-random
generators is crucial for security.
 It is hard to examine OS based PRNGs




The algorithms are not published. One must examine
the code. This is not easy.
Intricate dependencies with the OS – analyzing the
algorithm alone is not enough.
The generators of both Windows and Linux do
not provide forward security

and have additional design issues
Conclusions

Most severe findings

The PRNGs of Windows XP/2000 do not provide
forward security


Affecting > 90% of all PCs
Disk-less Linux systems