Password Cracking

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 LM NTLM MD5 SHA1

hash/sec 1,300,728 2,623,294 3,401,360 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 i =1 7

i 36 ∑ = 80.6G

{ 36 chars, passwd length <= 7

i =1 7

{ 256 chars, passwd length <= 7

∑ 256

i

LM

NTLM

MD5

SHA1

10.7min

5.3min

4.1min

15.1min

LM

NTLM

MD5

SHA1

17.2 hr

8.5 hr

6.6 hr

1.0 day

= 7.2 x10 7 G = 72 P

i =1

LM

NTLM

MD5

SHA1

1755.3 years

870.3 years

671.2 years

2468.5 years

14

{ 26 chars, passwd length <=14

∑ 26

i

= 6.7 x1010 G = 67 E

i =1

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

T = t × l × t0

M = m × l × m0

M: bounds on memory T: cryptanalysis time m: number of chains per table l: number of tables t: average chain length Password Cracking with Rainbow Tables

m0 : starting point + end point = 8B t0 : time to encrypt a plaintext 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