Transcript Slides - School of Computer Science and Engineering

Pseudo-Random-Number-Generators
Security Perspective
Zvi Gutterman
[email protected]
Outline

Motivation

Who needs random numbers?

Requirements
 Numerical generators
 Physical generators
 Examples



Java Object.toString( )
Attacking the Apache Servlet engine
Join us (projects) !
2
Motivation

Numerical Algorithms
 Simulations
 “Monte-Carlo” Methods
example:

Calculating
using
Monte-Carlo simulations
3
Motivation (cont.)

Security

Example: One-Time Pad
Truly Random?
Alice and Bob meet once, and set a one-time pad K.
Alice encrypt plaintext P with K (using xor) and sends the
cipher text C to Bob.
To decrypt P, Bob xor K with C.

Perfect encryption! (Pad used once, same length as P)




As old as Computer-Science ..
Turing, Von-Neumann
4
Requirements

Utopia

True random generators
• Hard to find
• Hard to proof
• Complex implementation

Reality

Pseudo random number generators
• Sequence appears random
“Any one who consider arithmetical methods of producing random digits is,
of course, in a state of sin.”
John von Neumann [1951]
5
Requirements – PRNG
 Statistical


Uniform distribution
… (e.g., number of ‘0’ equals number of ‘1’)
 Non

tests
predictable
Long Period
 Fast
computing
 Low memory consumption
6
Numeric Generators

Linear Congruential Generator (LCG)
Xn+1 = (Xn * a + b) mod m
Where –
[ Lehmer, 1949 ]
Xn – current number [x0 – seed]
Xn+1 – next number
a - multiplier
b - increment
m – modulus
7
LCG
 Used
in -

rand() function in C / C++ (libc)
Java.util.Random

..

 The
period is at most m
 Knuth [TAOCP] study the LCG period
8
LCG – Prediction Algorithm

Boyar [1982] algorithm





Input: Xn-k, …, X0
Output: a,b,m
Complexity: Log2m iterations
Assumes generator corrections during iterations
Krawczyk [1992]
extended for generators of the form:


Xn = P(Xi-n, … ,Xi-1) (mod m)
P – polynomial of fixed degree in n variables.
9
BBS – Blum, Blum, Shub
 p,q
- large prime numbers, congruent to 3
modulo 4.
 m = p*q
 k – relatively prime to m
 Set: X0 = k2 mod m [x0 – seed]
 Xn+1 = Xn2 mod m
 least-significant-bit(Xn+1) is the ith pseudorandom-bit
10
Blum-Blum-Shub Properties
 Cryptographically



strong !
As long as the factoring problem remains
hard, the (n+1)-th bit is not predictable.
This is true even if n is published (As long as
Xn are kept secret)
Slow ..
11
Other PRNGS
MT – Mersenne Twister
(cycle = 219937-1)
 ANSI X9.17


Based on triple-DES




Capstone/Fortezza
DSA (Digital Signature Specification)
Yarrow-160
Fortuna

And many others
12
Physical (True?) RNG

Radioactive decay
 Air Turbulence in disk drives
 Lava lamp
e.g., http://www.lavarnd.org

http://www.random.org
 Intel i8xx chipset
13
Example – Java Object.toString()
public String toString() {
return
getClass().getName() +
"@“ +
Integer.toHexString(hashCode( ));
}
 Example:
java.lang.Object@3179c3
14
Java Object.hashCode( )

From the JavaDoc:
• “As much as is reasonably practical, the
hashCode method defined by class Object
does return distinct integers for distinct
objects. (This is typically implemented by
converting the internal address of the
object into an integer, but this
implementation technique is not required by
the JavaTM programming language.)”
15
hashCode( ) implementation ..
















void os::init_random(long initval) {
_rand_seed = initval;
}
long os::random() {
/* standard, well-known linear congruential random generator with
* next_rand = (16807*seed) mod (2**31-1)
* see
* (1) "Random Number Generators: Good Ones Are Hard to Find",
*
S.K. Park and K.W. Miller, Communications of the ACM 31:10 (Oct 1988),
* (2) "Two Fast Implementations of the 'Minimal Standard' Random
* Number Generator", David G. Carta, Comm. ACM 33, 1 (Jan 1990), pp. 87-88.
*/
const long a = 16807;
const long m = 2147483647;
const long q = m / a;
assert(q == 127773, "weird math");
const long r = m % a;
assert(r == 2836, "weird math");
next_rand = (16807*seed) mod (2**31-1)
// compute az=2^31p+q
unsigned long lo = a * (long)(_rand_seed & 0xFFFF);
unsigned long hi = a * (long)((unsigned long)_rand_seed >> 16);
lo += (hi & 0x7FFF) << 16;




// if q overflowed, ignore the overflow and increment q
if (lo > m) {
lo &= m;
++lo;
}
lo += hi >> 15;






// if (p+q) overflowed, ignore the overflow and increment (p+q)
if (lo > m) {
lo &= m;
++lo;
}
return (_rand_seed = lo);







}
16
Object.toString( )
 Actually:
getClass().getName() +
"@“ +
Integer.toHexString(

LCG
);
We need to “guess” the object order of calling toString( )
17
toString & hashCode remarks
 PRNG
used in many protocols & systems
 Documentation may mislead
 Reverse-engineering is important
 Can
be used for fingerprinting?
18
Example - HTTP 1.1
 Defined
in RFC 2068
 Main e-commerce protocol today
 Stateless !

But we need a state …
19
HTTP Server side
PHP
CGI
Java
HTTP
SOAP
ASP
20
21
HTTP
cookie
demo
National
car rental
22
Attack motivation
 Can
I get someone else profile in
Amazon?
 Can I use the Amazon one-click option to
order books for you?
 Can I change your car reservation?
23
Java Servlets
 JCP:



Servlet 2.4
released 24 November, 2003
Java Session Framework
Must use: jsessionid as parameter (url or
cookie)
 Implementation

Apache Tomcat (25% market share, Apr2003)
• J2EE 1.4 recommendation + Bundled in the SDK!

Commercial
• Resin, IBM WebSphere, Oracle
24
Catalina
 Java Apache
web server = Tomcat
 Tomcat Servlet Engine = Catalina
 Version 5.0.xx (November 2003)
25
Tomcat – Brute Force
 Session

id – 16 Bytes
16 bytes = 128 bit
 Brute-force


attack
2128 options
Very, very long
• 1022 CPU years ..
26
Tomcat SessionID Attack
 Open


source …
Good
And Bad ..
27
Catalina – new SessionID
1.
2.
3.
128 bits = RandomEngine.Get next
random bits
Hash bits = MD5 (Bits)
Sessionid = Bits  Ascii representation
28
Catalina Algorithm
 Seed




C = current time in milliseconds (64 bit)
Ent = Entropy (default: toString() of
org.apache.catalina.StandardManager)
Seed = f(C,Ent)
Random.setSeed(Seed)
 Or

Initialization
–
Open /dev/urandom if exists
29
Catalina Attack
 Get
valid session ID
 reverse ASCII back to bit
representation
 Check
session id against all possible
seeds
 A <240
attack when assuming the server
uptime is at most one year
30
Catalina Attack - Remarks
 Once
broken we can get all valid sessionid immediately!
 The server do not know about it !!
 The attack is valid until the next reset
 This is a non targeted attack
31
Additional
Security Steps ..
32
Projects & Research

Attacking existing PRNG based schemes. examples:




HTTP Servers – PHP, Apache, ASP
Linux kernel based PRNG
SSL (?)
..

Building better theoretical understandings

Preliminary reading list:
http://www.cs.huji.ac.il/~zvikag

Contact: [email protected]
33