Password Cracking with GPUs

Kyle Rankin

Sr. Systems Administrator

Cyan Inc.

Author of The Official Ubuntu Server Book, Ubuntu Hacks, and Knoppix Hacks

http://greenfly.org/talks/security/gpu.html

Agenda

• An Introduction to Password Hashes
• How Password Cracking Works
• Legitimate Reasons to Crack Passwords
• Don't Taste the Rainbow (Tables)
• A Salt
• Why Use a GPU?
• The Hardware
• The Software
• Dictionary Attacks
• Calculating Cracking Speeds
• Brute-force Attacks
• Tuning Attacks
• Questions

An Introduction to Password Hashes

• The Problem: Safely store passwords on a system
• The Solution: Encrypt the password as a one-way hash
• Features of a one-way hash:
  • Easy to convert password to hash
  • Almost impossible* to convert hash to password
• Examples: MD5, SHA(1,256,512)
• At login, typed password gets converted to hash, compared with stored hash
• For instance, '123456' becomes $P$BPlIiO5xdHmThnjjSyJ1jBICfPkpay1

How Password Cracking Works

• First, you need the password hash
• /etc/passwd vs. /etc/shadow
• Web apps: often on a DB or the file system
• Next, you need the hashing algorithm used
• For /etc/shadow, stored in the hash:

$id $salt $encrypted

• 1 = MD5, 5 = SHA-256, 6 = SHA-512
• More on salts later

How Password Cracking Works

• Basic Password Cracking Algorithm:
• 1. Run password guesses through the hashing algorithm
• 2. Compare the result with the hash
• 3. If the hashes match, you found the password
• Two main ways to guess
• Dictionary Attacks: fast, catches weak passwords
• Brute-force Attacks: slow, catches all* passwords
• Refinements to Dictionary Attacks

Legitimate Reasons to Crack Passwords

Let's put on a white hat...

• Testing local users' password strength
• Prove users follow password policy
• Linux passwd often does this automatically
• Bitcoin mining no longer profitable
• Understand what modern password policies to use

Don't Taste the Rainbow (Tables)

• Problem: Brute force attacks are very time consuming
• Solution: Pre-compute all possible password/hash pairs
• Sacrifices disk space for CPU time
• Can distribute computation among many computers
• To crack a password, grep for the hash
• Great for old password hashes, old Windows passwords, old PHP passwords
• Rendered inpractical with password salts

A Salt

• Salt: An extra random input added to the hashing algorithm
• Inpractical to generate all combinations of passwords + salts
• Salt stored somewhere on the system so one-way hash still fast
• In /etc/shadow, salt is part of the hash

Why Use a GPU?

• Cracking passwords is a lot like mining Bitcoins
• Same reason to use GPU for Bitcoins
• https://en.bitcoin.it/wiki/Why_a_GPU_mines_faster_than_a_CPU

The Hardware

• Pick a GPU that mines Bitcoin well:
• https://en.bitcoin.it/wiki/Mining_hardware_comparison
• AMD vs. Nvidia
• AMD Radeon 6950 ~ $250, can be chained
• "Reference boards" can become 6970 with firmware flash
• Have a case with good cooling and a strong (700W+) power supply

The Hardware

My Exact Setup

• Motherboard: ASUS M4A88T-V: $95
• GPU: SAPPHIRE FleX 100312FLEX Radeon HD 6950 2GB: $280
• Power Supply: RAIDMAX HYBRID 2 RX-730SS 730W: $60
• CPU: AMD Phenom II X6 1090T Black Edition Thuban 3.2GHz: $170
• RAM: Corsair CMX4GX3M2B2000C9 4Gb 240-pin DDR3: $55
• Storage: Seagate ST95005620AS 500GB 7200 RPM Hybrid Drive: $100
• Case: Already owned
• Total: $760, $930 w/ monitor, $340 just GPU + PS

The Software

Proprietary Video Drivers

• If you are setup for Bitcoin mining, halfway there
• Otherwise, follow Bitcoin mining howto for AMD/Nvidia software:
• Install "restricted" proprietary video drivers for your card
• For AMD, get AMD APP SDK (I used AMD-APP-SDK-v2.5-lnx32.tgz)
• For NVidia get CUDA libraries

The Software

Hashcat

• Family of cracking software at http://hashcat.net
• hashcat
• Supports widest range of hashing algorithms
• CPU-based, so slower
• oclHashcat
• GPU-based cracker for brute or dictionary attacks
• Combines dictionary attacks with mask attack
• Supports brute-force attacks

The Software

Hashcat continued

• oclHashcat-plus
• GPU-based cracker optimized for dictionary attacks
• Supports more algorithms (like phpass) than oclhashcat
• Can pause/resume, supports dictionary input from pipe
• Can be combined with maskprocessor for brute force
• oclHashcat-lite
• GPU-based cracker optimized for recovering single password hash
• Designed to be very fast, but limited password hash support
• maskprocessor
• Designed to generate words for a mask attack
• Pipe output to oclHashcat-plus for brute force
• The winner: oclHashcat-plus
• In all cases, download and use 7za to extract software

Dictionary Attacks

• Dictionary attacks get weakest passwords first
• Way fewer password combinations = faster than brute force
• Start with dictionary attacks first before brute force
• Example dictionary attack against phpass:

/path/to/oclHashcat-plus64.bin -m 400 -o recovered_hashes \
 example400.hash example.dict

Calculating Cracking Speeds

• Before you start brute force, figure out how long it should take
• Comparison speeds vary based on hash type
• Run a sample brute force attack long enough to see progress output:

Status.......: Running
Input.Mode...: Piped
Hash.Type....: phpass, MD5(Wordpress), MD5(phpBB3)
Time.Running.: 6 hours, 55 mins
Time.Util....: 24932825.6ms/288387.3ms Real/CPU, 1.2% idle
Speed........:   341.2k c/s Real,   351.3k c/s GPU
Recovered....: 1/6 Digests, 1/6 Salts
Progress.....: 9072025600
Rejected.....: 565452800
HW.Monitor.#1: 96% GPU, 68c Temp

• ~350,000 phpass comparisons per second

Calculating Cracking Speeds

• Good site for cracking estimates: http://www.lockdown.co.uk/?pg=combi
• Or: number of characters ^ password length = total combinations
• Mixed-case Alphanumeric (A-Za-z0-9) = 62 characters
• 6-character password = 62 ^ 6 = 57 Billion combinations
• 57 Billion / 350k/sec = ~ 45 hours
• 8-character password = 62 ^ 8 = 218 Trillion combinations
• 218 Trillion / 350k/sec = ~ 7200 days or ~ 19 years
• 8-character mixed-case alnum + symbols = 7.2 Quadrillion combinations
• 7.2 Quadrillion / 350k/s = ~652 years

Brute-force Attacks

• Example brute force attack against 6-character alphanumeric mixed-case phpass hashes
• Pipe maskprocessor output to oclHashcat-plus:

/path/to/mp32.bin -1 ?d?l?u ?1?1?1?1?1?1 | \
/path/to/oclHashcat-plus32.bin -m 400 -n 80 \
-o recovered_hashes phpass-hashes

• -1 defines a special mask:
• ?d = decimals
• ?l = lower-case
• ?u = upper-case
• ?s = symbols
• ?1 = the mask I defined with -1
• ?1?1?1?1?1?1 = six -1 masks in a row

Tuning Attacks

Mask Attacks

• Dictionary attacks great for weak passwords, fast
• Brute force attacks find all passwords, slow or impossible
• Mask attacks combine best of both words
• oclhashcat ideal for mask attacks, or maskprocessor + oclhashcat-plus
• Example: Password policy of at least one upper-case letter and number
• User will likely use upper case as first character, and add numbers to the end
• First letter search for mixed-case, rest lower case, end of password lower + numbers
• -1 ?u?l -2 ?d?l ?1?l?l?l?2?2?2?2

Tuning Attacks

Rules

• Admit it, you use dictionary words with leet speak.
• oclhashcat supports rules to modify/tweak dictionary words
• "leet speak" rule simple to create
• See -r and -g options in oclhashcat for rules
• Software includes some predefined rules in rules/ directory

Questions?

• http://greenfly.org/talks/security/gpu.html
• http://hashcat.net
• Password Recovery Speeds: http://www.lockdown.co.uk/?pg=combi