Password Cracking with

Rainbow Tables
Korhan Bircan
April 23rd, 2008
Introduction to Computer System Security

1
Outline
zIntroduction
zSecure passwords
zDemo
zHellman’s original method
zRainbow tables
zCracking Windows Passwords
zPassword crackers
zProtection mechanisms
zConclusion
Password Cracking with Rainbow Tables 2
Introduction

zHow passwords are stored

zWhere passwords are stored
{Windows: C:\WINDOWS\system32\config\SAM
{Linux: /etc/passwd
{MacOS: /var/db/shadow/hash/
zShadow passwords
{/etc/shadow only readable by root
{/etc/passwd file shows a character such as '*',
or x' instead of the hashed password

Password Cracking with Rainbow Tables 3

Introduction

Password Cracking with Rainbow Tables 4

Introduction
z LanManager Hash
{password converted to uppercase, null-padded or
truncated to 14B
{password split into two 7B halves, a zero bit is
inserted after every 7th bit, the resulting 8B halves
are used to create two DES keys
{each of these keys is used to DES-encrypt
“KGS!@#$%”, resulting in two 8B ciphertext values
{concatenation the two to get 16B LM Hash.
z supported by all versions of Windows for
backwards compatibility
Password Cracking with Rainbow Tables 5
Introduction

zNTLM Hash: challenge-response

sequence
{Client sends supported or requested features
(eg. encryption key size, mutual authentication
etc.)
{Server replies with similar flags plus a random
challenge
{Client uses challenge and its credentials to
calculate the response

Password Cracking with Rainbow Tables 6

Introduction
z Salted hashes: For each password, generate a random
number (a nonce). Hash the password with the nonce,
and store both the hash and the nonce.
{ usual approach
z hash = md5(“deliciously salty” + password)
• MD5 is broken
• Its modern competitors, like SHA1 and SHA256 are fast, which is a
problem.
z With 16b hash, there are 2^16 = 65,536 variations to the
same password
z Speed is exactly what you don’t want in a password
hash function.
z Using raw hash functions to authenticate passwords is
as naive as using unsalted hash functions. Don’t.

Password Cracking with Rainbow Tables 7

Introduction
z How passwords are cracked
{brute force: online vs offline attack. Given
enough time and CPU power password
eventually gets cracked
{dictionary: list of words, encrypt them one at a
time and check if hashes are equal
{hybrid: dictionary with mutation filters

Password Cracking with Rainbow Tables 8

Secure Passwords
z Password Strength
{bit-strength
z[a-z][A-Z][0-9] and symbols = 95 variations per
character = log(95) ~ 6.6b
z8 character password x 6.6b = 53b
{cracking 72b key using current equipment is
estimated to take about 1,453 years
{no digital computer is capable of breaking 128b or
256b encryption
{NIST recommends 80b for most secure passwords ~
12 character random password from 95 character
domain
Password Cracking with Rainbow Tables 9
Secure Passwords
zA strong Windows password includes
characters from at least three of the
following groups:

zUse pass phrases eg. "I re@lly want to

buy 11 Dogs!"
Password Cracking with Rainbow Tables 10
Secure Passwords

zUse >14 characters

{it is the limit that DOS network boot disks,
Microsoft Remote Installation Services (RIS)
Pre eXecutable Environment (PXE) boot disks,
and older LAN Manager clients (Win9x) utilizes
zUse Alt characters eg. Alt+0709 = Å
zChange passwords often

Password Cracking with Rainbow Tables 11

Secure Passwords

z Intel Pentium M 1.60GHz, 512MB RAM

algorithm hash/sec
LM 1,300,728
NTLM 2,623,294
MD5 3,401,360
SHA1 924,898

Password Cracking with Rainbow Tables 12

Secure Passwords
z key space, N, plain dictionary attack
{ 26 chars, passwd length <= 7 7

∑ 26i = 835.3M
LM NTLM MD5 SHA1
10.7min 5.3min 4.1min 15.1min
i =1
7

{ 36 chars, passwd length <= 7 ∑ = 80.6G

36 i

i =1
LM

17.2 hr
NTLM

8.5 hr
MD5

6.6 hr
SHA1

1.0 day

{ 256 chars, passwd length <= 7 ∑ 256

i =1
i
= 7.2 x10 7 G = 72 P
LM NTLM MD5 SHA1
1755.3 years 870.3 years 671.2 years 2468.5 years

14

{ 26 chars, passwd length <=14 ∑ 26

i =1
i
= 6.7 x1010 G = 67 E

LM NTLM MD5 SHA1

1,633,359.2 years 809,881.0 years 624,619.6 years 2,297,070.7 years
Password Cracking with Rainbow Tables 13
Secure Passwords

zsecpol.msc

Password Cracking with Rainbow Tables 14

Secure Passwords

zdon’t
{ use personal information
{ use any word in any language spelled forward
or backward
{ tie passwords to the month
{ create new passwords that are substantially
similar to ones you've previously used
{ use the same password for different systems

Password Cracking with Rainbow Tables 15

Secure Passwords

zDisable LM Hash

Password Cracking with Rainbow Tables 16

Demo Setup

zCreate guest account for each student

zPasswords need to be alphanumeric and
<15 characters long
zCrack them!

Password Cracking with Rainbow Tables 17

Classical Tables
z 1980 Martin Hellman: N keys, N 2 / 3 operations&memory
{ ciphertexts are organised in chains, only first and last element
stored; k:key, S:cipher, C:ciphertext P:plaintext, R:reduction
function

{ = and generates a key from another key to form

a chain:

{ m chains of length t are created, first and last elements are

stored in a table.

Password Cracking with Rainbow Tables 18

Classical Tables
z To find a key, generate a chain of keys starting with
R(C) and up to length t
z If C was indeed obtained with a key used while
creating the table then we will eventually
generate the key that matches the last key of the
corresponding chain
z Using the first key of the chain, whole chain is
regenerated
z The key right before R(C) is the key we are
looking for
Password Cracking with Rainbow Tables 19
Classical Tables

z There is a chance that chains starting at different

keys collide and merge
z Probability of finding a key, m rows and t keys:

z Probability of finding a key, l tables with

different reduction functions:

Password Cracking with Rainbow Tables 20

Classical Tables

zFalse alarms:
{key may be a part of a chain which has the
same endpoint but is not in the table
{key is in a chain that is part of the table but
which merges with other chains of the table
zMerges correspond to same endpoint,
detected during sort. They are replaced
with new chains

Password Cracking with Rainbow Tables 21

Bounds and Parameters
Memory

M = m × l × m0 m0

Time

M: bounds on memory

T = t × l × t0 T: cryptanalysis time
m: number of chains per table

M = m × l × m0
l: number of tables m0 : starting point + end point = 8B
t: average chain length t0 : time to encrypt a plaintext
Password Cracking with Rainbow Tables 22
Bounds and Parameters

zWinrtgen Benchmarks:

Password Cracking with Rainbow Tables 23

Rainbow Tables

zA rainbow table is a compact

representation of related plaintext
password chains

Password Cracking with Rainbow Tables 24

Rainbow Tables

zRecovering a password

Password Cracking with Rainbow Tables 25

Rainbow Tables

z Probability of success in an m x t size table:

{start with m1 = m distinct keys in the first column
{in the second column the m1 keys are randomly
distributed over the key space of size N, generating m2
keys:

{each column i has mi distinct keys. Success rate of

table:

Password Cracking with Rainbow Tables 26

Rainbow Tables

zAdvantages over classical tables:

{t(t-1)/2 look-ups as opposed to t^2
{merges result in identical endpoints and are
thus detectable
{no loops since each reduction function appears
once
{constant length rainbow chains

Password Cracking with Rainbow Tables 27

 Rainbow Tables
zAdvantages over classical tables:
{When two chains collide in a single table they
merge
{Instead use successive reduction functions 1 to t
{If two chains can collide they merge iff collision
appears at the same position in both chains
(probability is 1/t)
{If key is found early, gain can be up to a factor of
t because while the rainbow table is searched,
the amount of calculation increases quadritically
to (t^2-1)/2 whereas in classical tables it
increases linearly to t^2.
Password Cracking with Rainbow Tables 28
Rainbow Tables: Parameter Optimization
charset [ABCDEFGHIJKLMNOPQRSTUVWXYZ]

keyspace 8353082582
table size 610 MB
success probability 0.9990

charset [ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789]
keyspace 80603140212
table size 3 GB
success probability 0.9904

charset [ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-_+= ]
keyspace 915358891407 (2^39.7)
table size 24 GB
success probability 0.99909

charset [ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-_+=~`[]{}|\:;"'<>,.?/ ]
keyspace 7555858447479 (2^42.8)
table size 64 GB
success probability 0.999

Last table would take 41.3 years to generate on my laptop.

Password Cracking with Rainbow Tables 29
Rainbow Tables: Parameter Optimization

hash charset len_min len_max table index len_chain num_chains

lm alpha[numeric] 1 7 0:4 2100 8000000,

40000000

Password Cracking with Rainbow Tables 30

Password Crackers: RainbowCrack

zextract password hashes using pwdump or

fgdump

Password Cracking with Rainbow Tables 31

Password Crackers: RainbowCrack
zcreate rainbow tables

zsort the tables

Password Cracking with Rainbow Tables 32

Password Crackers: RainbowCrack

zRun the cracker

Password Cracking with Rainbow Tables 33

Password Crackers: Cain&Abel

zGo to “Cracker”, right click to import

hashes from pwdump file

Password Cracking with Rainbow Tables 34

Password Crackers: Ophcrack

Password Cracking with Rainbow Tables 35

Password Crackers: Ophcrack
zLive CD: dumps the hashes from the SAM
and SYSTEM files and you don’t need to
be admin

Password Cracking with Rainbow Tables 36

Limitations of Rainbow Tables

ztable generation takes a long time

zfalse alarms occur often
zsimple salting algorithm nullifies rainbow
tables

Password Cracking with Rainbow Tables 37

Protection Mechanisms

zLimiting physical access

zContinue to force the use of special
characters
zKeep up with updates
zUse Multi-factor authentication
zsalted hashes
zUse NTLM
zUse secure passwords
Password Cracking with Rainbow Tables 38
Protection Mechanisms

zUse state of the art password schemes

{Use what your operating system gives you (eg.
PHK’s FreeBSD MD5)
{Stanford Secure Remote Password
{Adaptive hashing: bcrypt
zuses pessimized Blowfish

Password Cracking with Rainbow Tables 39

Conclusion

zRainbow tables reduce the number of

table look-ups by length of chains
zComputations reduced by 2, average case
performance even greater
zSome cryptographic systems believed to
be secure when implemented can be
cracked by anyone today
zBe smart about choosing passwords and
storing them
Password Cracking with Rainbow Tables 40
References
z “Making a Faster Cryptanalytic Time-Memory Trade-Off”, Philipppe
Oechslin, CRYPTO 2003: pp617–630
z “Top 10 Password Crackers”, http://sectools.org/crackers.html
z “Cain&Abel”, http://www.oxid.it/cain.html
z “PWDump”, http://www.foofus.net/fizzgig/pwdump/
z “RainbowCrack”, http://www.antsight.com/zsl/rainbowcrack/
z “Ophcrack”, http://lasecwww.epfl.ch/~oechslin/projects/ophcrack/
z “Winrtgen”, http://www.oxid.it/projects.html
z “Hacking dei Sistemi: Password”, Cardinale, Giacchetti, Giovannetti
z “Mac OS X password hashes”,
http://www.macshadows.com/kb/index.php?title=Mac_OS_X_password_has
hes
z “Shadow Password”, http://en.wikipedia.org/wiki/Shadow_password
z “Password Cracking”,http://en.wikipedia.org/wiki/Password_cracking
z “Selecting Secure Passwords”,
http://www.microsoft.com/smallbusiness/support/articles/select_sec_passw
ords.mspx

Password Cracking with Rainbow Tables 41