Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Exploiting weak randomness in web applications

Presentation prepared for real world cryptography 2013

Aggelos Kiayias

on 11 January 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Exploiting weak randomness in web applications

The Problem A small Challenge Our Goal in this work:
Provide practical techniques for the exploitation of randomness vulnerabilities in PHP applications Exploiting weak randomness in web applications <?php
echo mt_rand();

$bet = $_GET['bet'];
if ($bet == mt_rand()) {
?> Would you put this code on your server? Can you exploit this code on a target server? Attack Template Randomness Generation in PHP mt_rand()/mt_srand(): PRNG based on the Mersenne Twister generator.
mt_srand() seeds the generator with a 32 bit value.
mt_rand() produces a 31 bit output.
Can return a number in a smaller range. rand()/srand() Uses the rand() function from the OS
seeded with a 32 bit value and produces 31 bit outputs.
Can return a number in a smaller range. php_combined_lcg()/lcg_value() php_combined_lcg() is used internally by the PHP system.
lcg_value is its public interface.
Combines two 32 bit LCGs and produces a 64 bit output.
Seeded only once the first time it is called. uniqid(prefix, extra_entropy) When called without arguments produces a timestamp with seconds and microseconds since unix epoch.
The first argument adds a user supplied prefix to the timestamp.
The second argument adds an output of php_combined_lcg() as suffix. Process management Apache handler (mod_php):
PHP runs as an Apache web server module.
There is a new PHP process spawned for each request and terminated after the request is served.
Fast CGI:
There are a number of PHP processes serving requests repeatedly. They are usually killed after they served a predefined number of requests. We will focus here! The Entropy Of Time Measurements Timestamps Facts:
Epoch (time up to seconds accuracy) is leaked to the client through the HTTP Date Header.
Microseconds range from 0 to 10^6
Therefore a trivial bruteforce will succeed after 2^(20) requests on average. Can we do better than 2^20 ? Adversarial Time Synchronization (ATS) Request Twins token = H(microtime()) attacker admin Web Server reset admin's password reset attacker's password admin token attacker's token [Interval] Experiment Predict the output of the following script: <?php
echo microtime();
?> Results : reducing entropy of time Attacking PRNGs Seed Attacks State Recovery Attacks In order to attack the seed it helps to interact with newly seeded generators. This usually happens when a fresh process is created. Technique Create a large number of connections using the Keep-Alive HTTP header.
While keeping these connections alive make a new connection to the server.
The new connection is very likely to be handled by a fresh PHP process. Hacking your own PHP session identifier session_id = MD5(client IP address || time_of_day() || php_combined_lcg()) If the total entropy is "small" then we can obtain a preimage by bruteforce.
This gives us control of php_combined_lcg(). session_id = MD5(client IP address || time_of_day() || php_combined_lcg()) Known since its the attacker's IP address. Provides up to 20 bits of entropy which can be reduced using the ATS algorithm. php_combined_lcg has a 64 bits output so bruteforcing the output is not feasible. Since we can generate fresh processes we can try to predict the first output which is simply one round of the generator with the seed. php_combined_lcg has two 32 bit registers s1, s2.

T1, T2: two subsequent timestamps
pid: PHP process identifier. By bruteforcing the session identifier of a fresh process we can obtain:
the seed of php_combined_lcg
the process identifier of the PHP process. What about the other PRNGs? Seeding in rand()/mt_rand() These generators can be seeded with the respective functions mt_srand() and srand().
If the generator is not seeded somehow else, then the following 32 bit seed is produced:

seed = (time()*pid) ^ (10^{6}*php_combined_lcg()) seed = (time()*pid) ^ (10^{6}*php_combined_lcg()) Assume we have a preimage for a session identifier. Leaked by the Date
HTTP Header Obtained through the
session id preimage Obtained through the
session id preimage A session identifier preimage completely determines the seed of the mt_rand() and rand() PRNGs! ..or if you have outputs go bruteforce as before.. the process can be further optimized using an application specific rainbow table. Suhosin Hardening extension for PHP.
Replace rand() with a Mersenne Twister generator with different state than mt_rand().
Disables srand() and mt_srand() functions.
Seeds the generators once at process startup with a secure seed.
Entropy gathered from the operating system. All PRNGs in the PHP core are linear! ...trivial? Truncation:
The output may be truncated to a smaller range.
This may introduce non linearity to the generator. there are many processes!
... but we want to get all outputs from the same generator.
... Keep-Alive limit ==> the server might close the connection before the necessary number of leaks are collected. Truncation in PHP Process Distinguisher
we can try to reconnect when
the server drops our connection How can we find the correct process? We need a process specific leak... Idea:
Recall: the session id preimage contains the pid! Algorithm:
Connect to a fresh process and obtain a session id preimage.
Obtain PRNG leaks until the server closes the connection.
reconnect to server and request session id.
For each session check if it is generated using the next round of php_combined_lcg
If a match is found then we have connected to our process. state recovery for rand() rand() implementation depends on the OS:
> On windows a 15 bit LCG is used

> On *nix systems an additive feedback generator is used:

> Truncation introduces non linearity. Hastad-Shamir Framework Solves the problem of uniquely solving an underdetermined system of linear modular equations when part of the variables is known. High level description
Define a lattice over the coefficients of the equations
Find a reduced basis of the lattice using the LLL algorithm.
Use the fact that the basis vectors are small to uniquely solve the system over the integers. Bottleneck point:
Lattice base reduction of a lattice with dimension equal to the number of leaks needed.
Public LLL algorithm implementations have complexity O(d^5).
A O(d^3 logd) variant exists (Koy-Schnorr-02), but without any public implementation. Summary:
LCGs can be efficiently recovered unless we have extremely large truncation levels.
Similar behavior was observed in the glibc generator however the LLL complexity did not allow to recover state for more than 6 bits truncation. Implementation experiments State recovery for mt_rand() Mersenne Twister:
Based on a linear recurrence over GF(2):

Huge state of 19937 bits. (a Mersenne Prime)

To improve randomness properties the output of the recurrence is multiplied by an invertible matrix:
z = xT
T is called the tempering matrix. Notice:
Truncation does not introduce non linearity
to the generator.
However, the actual linear system depends
on truncation behavior. Each output bit can be expressed as a linear equation to the internal state.
Take each output bit obtained and create a linear system.
If the system has a unique solution the solution will give the internal state of the generator. How can we know that the system has a unique solution in advance? Employ an online Gaussian solver:
As equations are obtained from the server add them to the system.
Stop when the system becomes uniquely solvable. Tools of the Trade George Argyros Aggelos Kiayias University of Athens
University of Connecticut Implementation experiments Adversarial Time Synchronization
Request Twins Time is in microseconds Date: Sun, 10 Jul 2012 08:59:27 GMT Date: Sun, 10 Jul 2012 08:59:28 GMT 08:59:27 08:59:28 Web Server attacker 15 bits 0 bits < 20 bits Calculated as Δ = T2-T1.
Entropy =~ 3 bits. Total entropy of session identifier in a fresh process is about 40 bits. PHP Core PHP extensions openssl_random_pseudo_bytes() Interface to the openssl function with the same name.
Returns a number of pseudorandom bytes.
A flag is used to tell if the bytes are crypto strong.
Requires openssl extension. mcrypt_create_iv() Gathers entropy from the operating system generators
/dev/random, /dev/urandom
Requires mcrypt extension. The attack does not require any outputs from the targetted PRNGs! Equations vs truncation. Time vs Truncation. A set of tools with a python interface in order to exploit randomness attacks:
Online Gaussian solver.
Lightweight rainbow tables implementation.
Programmable web bruteforcing tool.
check http://crypto.di.uoa.gr for a release. Randomness Attacks Mitigation PHP 5.4 added extra entropy to the session identifier.
session.entropy_length enabled by default.
Suggested to add secure seeding to all PRNGs in the PHP core.
PHP security team: "This is an application specific problem".
Secure PRGs from extensions are rarely used right now.
A drop in replacement for any token generator can be found in http://crypto.di.uoa.gr
Checks for crypto strong PRGs in the PHP system
Otherwise collects entropy from various sources. Summary Randomness attacks affect a very large number of PHP applications.
Exploit mitigations are needed for these attacks.
Crypto bugs are becoming a trend for exploitation. Related Work Stefan Esser
mt_srand and not so random numbers.

Samy Kamkar
How I met your girlfriend.

Gregor Kopf
Non obvious bugs by example. Thank You!


Exploiting weak randomness
in web applications George Argyros Aggelos Kiayias y: number of leaks, x: number of bits truncated y: time (s), x: number of bits truncated In more detail The Cryptanalytic Framework Given: Find: (underdefined) Define Lattice : find a basis : observe: transform this to a determined system
(taking advantage of a short basis) solvability : LCG Additive Feedback Shift
Register (glibc) (adversarial...) we will deal with this problem first...
Full transcript