This document discusses password cracking using rainbow tables. It begins with an introduction that outlines how passwords are stored on different operating systems and describes hashing algorithms like LM hash, NTLM hash, and salted hashes. It then discusses secure password practices like length, complexity, and changing passwords regularly. The document demonstrates password cracking with a demo and discusses classical rainbow table methods developed by Hellman. It explains how rainbow tables store hashed values in chains to efficiently crack passwords without brute forcing the entire key space. The document concludes with discussions around optimizing rainbow table parameters like memory usage and cryptanalysis time.
This document discusses password cracking using rainbow tables. It begins with an introduction that outlines how passwords are stored on different operating systems and describes hashing algorithms like LM hash, NTLM hash, and salted hashes. It then discusses secure password practices like length, complexity, and changing passwords regularly. The document demonstrates password cracking with a demo and discusses classical rainbow table methods developed by Hellman. It explains how rainbow tables store hashed values in chains to efficiently crack passwords without brute forcing the entire key space. The document concludes with discussions around optimizing rainbow table parameters like memory usage and cryptanalysis time.
This document discusses password cracking using rainbow tables. It begins with an introduction that outlines how passwords are stored on different operating systems and describes hashing algorithms like LM hash, NTLM hash, and salted hashes. It then discusses secure password practices like length, complexity, and changing passwords regularly. The document demonstrates password cracking with a demo and discusses classical rainbow table methods developed by Hellman. It explains how rainbow tables store hashed values in chains to efficiently crack passwords without brute forcing the entire key space. The document concludes with discussions around optimizing rainbow table parameters like memory usage and cryptanalysis time.
This document discusses password cracking using rainbow tables. It begins with an introduction that outlines how passwords are stored on different operating systems and describes hashing algorithms like LM hash, NTLM hash, and salted hashes. It then discusses secure password practices like length, complexity, and changing passwords regularly. The document demonstrates password cracking with a demo and discusses classical rainbow table methods developed by Hellman. It explains how rainbow tables store hashed values in chains to efficiently crack passwords without brute forcing the entire key space. The document concludes with discussions around optimizing rainbow table parameters like memory usage and cryptanalysis time.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 41
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:
{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
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
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
