Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

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.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

How Passwords Are Cracked

No description
by

Gaten Makrosd

on 28 July 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of How Passwords Are Cracked

Cracking Passwords For Fun And Profit
Background
How Hashes Are Cracked
There are several methods attackers can employ when trying to crack hashed passwords.
Storing Passwords - The "Clear Text" Method
"Heartbleed" is a security vulnerability found in the OpenSSL cryptographic software library.
Does that mean hackers have all our passwords?
It allows an attacker to remotely read a system's application memory, accessing encryption keys,
user credentials
, and any other critical business data.
"Heartbleed" was introduced into OpenSLL during 2012, and was discovered only in 2014.
During this time period,
any data stored/exchanged on an affected website may have been compromised.
Due to OpenSSL's widespread use, it is estimated that nearly half a million websites were affected, including Google, Yahoo, Amazon, Flickr, Netflix, and many more.
No.
Maybe.
To understand why they're all true,
let's look at how passwords are stored.
Yes.
# Password Database

agantz: "IC_Dead_Packets"

byifat: "can!bake"

ajolondz: "kamikaza"

arabin: "2muchPastaBasta"

# and so on...
Pros:

Fast - each user's password is directly stored as plain text.

User authentication is trivial - simply compare the user's entered password to the stored plain text.

Is there a better way?
Store a hash.
Input
"The quick brown fox
jumps over the lazy dog"
Result (digest)
MD5: 9e107d9d372bb6826bd81d3542a419d6

CRC32: 9FF19F1B

SHA-256: d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592

RIPEMD-160:
37f332f68db77bd9d7edd4969571ad671cf9dd3b
Hash Algorithms
MDx (MD2, MD4, MD5)

CRC (CRC8, CRC32, etc.)

SHA-X (SHA-1, SHA-2, SHA-256, etc.)

RIPEMD-X (RIPEMD-128, RIPEMD-160, etc.)
Hash functions
A hash algorithm is a one way function. It turns an
arbitrary length data into a fixed length value.
Hash functions can be divided into two categories:
Regular Hash Functions
Cryptographic Hash Functions
Generally Fast

The input cannot be inferred from the Hash (non-invertible)

Deterministic - The same input will yield the exact same output every time.

Different inputs may yield identical hashes (i.e.
"Hash Collision"
)

Examples: Checksums, CRC, CityHash
Non-invertible, Deterministic.

Any change in the input will yield a significantly different hash.

It is highly unlikely that different inputs will produce identical hashes,
but not impossible.

Examples: MDx, SHA-X, WHIRLPOOL
Yes.
Don't store the password.
For the purposes of password hashing,
only cryptographic hash functions should be used.
# Hashed Password Database

agantz: DF8933FA
byifat: 8499B2C7
ajolondz: 2FFB490E
arabin: EA58069C

# and so on...
Account Creation
A new account is created by the user.
The user selects a user name and specifies a password.
Password Hashing
The password is immediately hashed, and the original password is discarded.
User name/Password storage
The user name/hash pair is added to the accounts database.
Authentication
When a user tries to log in, the entered password is hashed and then compared to the user's stored hash.

Access is granted only if both hashes match.
Storing Passwords - The "Hash" Method
What happens if the hashed database is compromised?
Nope.
The common goal in all attacks is trying to find
a plaintext that will compute to a compromised hash.

If a password is long enough and allows non-alphanumeric characters, this attack method quickly becomes unfeasible.

However, given enough time (e.g. 100 years), this method will always find a matching plaintext.
Brute Force Attack
A brute force attack will try every possible plaintext combination that can be a used as a password.

It will create a plaintext, hash it, and will then search for a matching hash in the password databse.

If such a match is found, the created plaintext is the password. Otherwise, it will create a new plaintext.

Example:
Searching for hash('a') :
Failed!
Searching for hash('aa') :
Failed!
Searching for hash('aaa'):
Failed
.......
.......
Searching for hash('anibaboon') :
Success!
username 'alori'
A dictionary attack takes advantage of the human tendency to pick passwords that are easy to remember: English words, names of places, and other strings that are commonly used as passwords (e.g. 'password123')
Dictionary Attacks
The attack uses a file containing meaningful words and frequently used password combinations.
# Dictionary Attack

Trying apple : failed
Trying blueberry : failed
Trying justinbeiber : failed
...
Trying letmein : failed
Trying s3cr3t : success!
Searching: 5f4dcc3b5aa765d61d8327deb882cf99: FOUND: password5
Searching: 6cbe615c106f422d23669b610b564800: not in database
Searching: 630bf032efe4507f2c57b280995925a9: FOUND: letMEin12
Searching: 386f43fab5d096a7a66d67c8f213e5ec: FOUND: mcd0nalds
Searching: d5ec75d5fe70d428685510fae36492d9: FOUND: p@ssw0rd!
Lookup tables
Lookup tables are a
pre-computed
variant of the dictionary attack.
A reverse lookup table allows an attacker to apply a dictionary or brute force attack against several hashes simultaneously.
Reverse Lookup Tables
The attacker first iterates over every entry in the compromised database, and creates a lookup table where every hash is matched to all the users who have that hash in common.
The attacker can then initiate a brute force or a dictionary attack on every hash, and get a list of all users using that same password.
Searching for hash(apple) in users' hash list... : Matches [alice3, 0bob0, charles8]
Searching for hash(blueberry) in users' hash list... : Matches [usr10101, timmy, john91]
Searching for hash(letmein) in users' hash list... : Matches [wilson10, dragonslayerX, joe1984]
Searching for hash(s3cr3t) in users' hash list... : Matches [bruce19, knuth1337, john87]
Searching for hash(z@29hjja) in users' hash list... : No users used this password
This attack is extremely efficient since many users share identical passwords
Rainbow Tables
Cons:

If the database is compromised, the attacker immediately gains every user's password.

Also, because users tend to use the same password on multiple services, other accounts may be compromised.
Does that mean we're safe?
The attacker will only have hashes, and we already know our passwords can't be inferred from those.
The attack succeeds when a matching hash is found.
Each word is then hashed in turn,
and its hash is compared to the attacked hash.
A good implementation of a lookup table can process hundreds of hash lookups per second, even when they contain many billions of hashes.
The hash of every entry in the dictionary file is calculated and then stored with its corresponding string in a lookup table data structure. The attacker then needs only search the compromised hash in the lookup table.
Recall what we discussed previously:

Hash functions map arbitrary data (i.e. passwords) into a fixed length value (also called the hash "digest").
To infer a password from its hash, a hacker needs to find a string that when hashed, produces the same digest.
Brute Force/Dictionary attacks hash and compare each plaintext (thorough, but slow)
Lookup Table attacks pre-compute and store the hashes of many plaintexts in an easy to search data structure (fast, but requires considerable memory resources when used.
Plaintext
"I really like squirrels"
Hash (Digest)
8EF6378311ABCF20399A
Hash Function
In a regular lookup table, we pre-compute the hash for each plaintext
Plaintext 0
(start)
"Hear Me Roar"
Hash 0
6e68aa2201ae26053e55ce3013616863
Plaintext 1
"A Lannister always pays his debts"
Hash 1
cfe0b71286fee4a72e420518cd4569ee
The resulting lookup table may look something like this:

# My Lookup Table
--------------------------------------------
8EF6378311ABCF20399A : "I really like squirrels"
5ECB7377684760EFC9B7 : "HaX0rE1337"
...
...
...
Entry n-1
Entry n
Rainbow Tables are very much like lookup tables.
However, in addition to using a hash function, they also employ a "Reduction" function.
Hash
8EF6378311ABCF20399A
Plaintext
"Winter Is Coming"
Reduction Function
Reduction
It's important to note that a Reduction function is the
opposite
of a Hash function (it creates plaintexts from hashes), but it is not the direct
inverse
of a Hash function - if that operation was possible, cryptographic hashes would become useless.
So how does a Rainbow Table utilize both hash and reduction functions?
Plaintext 2
"Fire and Blood"
Hash 2
cee2ad29bf6d5231b4a4afea3a8ce7ee
Plaintext N
"As High as Honor"
Hash N
(End)
d420ec34d681fca46b923b9b8a4e7f8f
More Hash/Reduce Iterations...
H
R
H
R
H
H
By creating what is called a "Hash Chain".
Instead of storing {Plaintext: Hash} pairs where the file size increases as more pairs are added, "Hash Chains" allow an attacker to pre-compute many hashes while significantly reducing the required storage space.
Passwords are converted to hashes using hash functions.
Rainbow Tables
The key point here is that the attacker only needs to store the starting plaintext (Plaintext 0) and the ending hash (Hash N) of each chain.
PlainText 0
"Hear Me Roar"
Hash N
d420ec34d681fca46b923b9b8a4e7f8f
Hold on...
Where did the rest of the {Plaintext: Hash} pairs go?
How do we use this to find a matching hash?
Let's see how a Rainbow table is built and how an attack works.
Plaintext 0
"Everybody likes eggplants"
Hash N
f0cb4da6d9706a81ecd2538c3742619f
Plaintext 0
"s3cr3tpasswords1234"
Hash N
5f4dcc3b5aa765d61d8327deb882cf99
Plaintext 0
"ReadingBooksWithTea"
Hash N
ecf65a5d41056d7dd4d548e3ef200476
Plaintext 0
"my_safe_codes"
Hash N
386971413fa566441c66f66f068e016c
Chain 0
Chain 1
Chain 2
Chain N
More computed chains...
...
...
Rainbow Table Example
Attack Method
Compare Hashes
Loop over every hash chain and compare the required hash with each chain's Hash-N (last calculated hash).
Break Loop And Calculate The Chain
Take the plaintext at the start of the matching chain and apply Hash/Reduce operations until the matching Hash is found.

The password is the plaintext yielding this hash


Calculate Prior Hash
Matching Hash Found
No Matching
Hash Found
Assume the required Hash is at place N-(i)
(i = iteration number).

Apply [i] Reduce/Hash operations to the original hash.

Use the resulted hash in the next step.
Check
Hash Chains
Key points:

- This allows an attacker to pre-compute and store many {plaintext:hash}pairs without actually needing to allocate storage for every pair.

- Reduce/hash/compare operations are fairly cheap. However, pre-computing Rainbow Tables for a specific hash algorithm / plaintext requirements may be time consuming.

- Rainbow Tables can also suffer collisions, which reduce their overall effectiveness (Example?, if time permits...)
Using Salt
Why are these attacks so successful?
The main problem is that all passwords are hashed the same way, causing identical plaintexts to yield identical hashes.
There's also a strong tendency to select passwords that are easy to remember, and If many users share the same password, they'll share the same hash.
This makes dictionary attacks, lookup tables, and rainbow tables extremely useful, especially when attacking large password databases.
The Solution?
A "Salt" is a
random
string that's appended to the user's password before it is hashed.
A secure system will generate a unique string for every password
stored/changed

Due to its randomness, lookup tables, dictionaries, and rainbow table attacks become ineffective. An attacker cannot pre-compute hashes based on an unknown salt.
The salt doesn't have to be a secret (unlike the password), and it is usually stored alongside the hash.
Because every password salt is random, identical passwords will yield completely different hashes.
hash("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
hash("hello" + "QxLUF1bgIAdeQX") = 9e209040c863f84a31e719795b2577523954739fe5ed3b58a75cff2127075ed1
hash("hello" + "bv5PehSMfV11Cd") = d1d3ec2e6f20fd420d50e2642992841d8338a314b8ea157c9e18477aaef226ab
hash("hello" + "YYLmfY6IehjZMQ") = a49670c3c18b9e079b9cfaf51634f563dc8ae3070db2c4a8544305df1b60f007
- Password Database Example-

User: agantz salt: shfh898238hd3 hash: ef2cb44d5e89a1c7
User: alori salt: 79893fihufjhfk hash: 480dc67772caccf
User Login
The password is entered by the user
Password Validity Check
The resulting hash is then compared to the stored hash.
Hash Calculation
The stored salt is appended to the entered password. The concatenated result is hashed.
In Conclusion:

- Stolen passwords are not the end of the world.

- However, this shouldn't be an excuse to use simple / easy to guess passwords. You don't know how secure the password implementation is on any given website.

- If your account is compromised, it may be smart to reset the passwords on all your other accounts.
Thank You :-)
Let's see how a single Hash Chain is created:
The longer a chain is, the more {Plaintext: hash} pairs are stored.
This takes time to compute, and therefore there's a tradeoff between a chain length and the number of total chains in a specific Rainbow Table.
Only this is stored.
Add Salt.
To make it impossible for an attacker to create a lookup table for every possible salt, the salt must be long. A good rule of thumb is to use a salt that is the same size as the output of the hash function. For example, the output of SHA256 is 256 bits (32 bytes), so the salt should be at least 32 random bytes.
Full transcript