Password Hashing

Keith A. Watson, CISSP, CISA

CERIAS, Purdue University

Overview

• History of Password Hashing
• Generating
• Cracking
• Goals in Password Hashing
• Issues in Password Hashing
• Cryptographic Hashes vs. Password Hashes
• Better Techniques
• Authentication Outsourcing

Definitions

• Password - a secret that must be used to gain access or admission
• Password hash function - a one-way transformation of a password into a stored value
• Cryptographic hash function - a one-way transformation of plaintext into unique value
• Password cracking - the recovery of passwords from a system

History

• Creating and storing password hashes
• Cracking password hashes
• Issues with password hashing & passwords

History of Password Hashing

• Passwords were stored in plaintext
• Administrators (and users) could view the file
• In 1978, Robert Morris published CRYPT
• Encoded passwords stored in the world readable /etc/passwd file
• In 1990, Alec Muffett created Crack for Unix
• SVR4 (1988) and BSD (1990) use shadow password systems to protect hashes

More History of Password Hashing

• As computing power increases, modifications were made to the traditional crypt(3) scheme
• configurable number of rounds used
• selection of cryptographic algorithms
• large salt range
• longer passwords
• In 1997, Microsoft introduces NT LANMAN
• In 2001, Sun released the Solaris Pluggable Crypt Framework
• BSD derivatives, Linux use modular crypt(3)
• bcrypt and scrypt

Unix

• crypt(3) Unix library function
• eight character, 7-bit ASCII input
• additional characters truncated quietly
• used a DES variation
• not real DES because DES hardware devices existed which could favor the attacker
• iterated over input 25 times through feedback
• applied a 12-bit random "salt"
• 4096 (2¹²) permutations per password possible
• designed for PDP-11 hardware
• took more than one second to compute

Solaris, BSD, Linux, Others

• Some vendors replaced crypt(3) with crypto16(3) or bigcrypt(3)
• Vendors extended crypt(3) to support more algorithms, extend the number of salts
• Modular Crypt Format (MCF)
• added DES Extended, Blowfish, MD5, SHA-256/512
• field #1: algorithm
• field #2: salt
• field #3: hash

$1$Dfhck4Sz$R3AdHbg7339gHtdgF0MBJ/

Cracking UNIX Passwords

• Password cracking envisioned in Robert Morris's paper on the CRYPT algorithm
• In 1991, Crack for Unix was released by �Alec Muffett
• Alec's purpose was the elimination of passwords as an authentication scheme
• Demonstrated that brute-force attacks can be effective when selecting reasonable password guesses
• Programmable dictionary
• Distributed computation over the network

Cracking All Kinds of Password

• John the Ripper is an improved cracker
• runs on a variety of systems
• cracks multiple types of system hashes
• Rainbow tables use modern capabilities
• based on Philippe Oechslin's work on faster time-memory trade-off techniques
• exploit advances in computation and storage
• create a precomputed table of password hash chains
• shortens time needed to find password
• requires significant pre-computation and storage
• RainbowCrack, ophcrack, Free Rainbow Tables

Shadow Password Systems

• A flawed response to password cracking
• hides the password hashes
• does not correct the algorithmic issue
• Only processes with administrative privilege can read the shadow password file

​

-r-------- 1 root sys 453 Jan 27 2008 /etc/shadow

Past (Current) Issues with �Password Hashing

• It was not done
• stored cleartext passwords
• It was not done well
• used cryptographic hashes
• It was not done really well
• used salt
• It was not done really, really well
• used a password hash algorithm

Issues with Passwords

• User education is still needed
• choice of password, where it's used and re-used
• Most sites have weak password complexity requirements
• complex passwords are also difficult to remember
• Most sites still do not ask users to pick better passwords
• sites do not want to annoy users either, sadly
• Significant concern over trusted third-party authentication solutions

Password Hashes

• Properties in password hashing
• Cryptographic vs. password hash techniques
• Password Hash techniques

Properties of Good�Password Hashing

• The original password is not stored
• The password hash cannot be reversed into the original password
• No two passwords should create the same hash
• There exist many possible password hashes for a unique password
• The creation of a password hash from a password is not a computationally fast nor memory efficient process

Ad Hoc Techniques for Password Hashing

Note: Do NOT do the following!

• Invent your own password hashing method
• Use a cryptographic hash by itself
• Use a cryptographic hash with a single or too few iterations
• Skimp on the salt
• Think that all password hashing should be fast and efficient

Cryptographic Hashes

• The use of cryptographic hashes in password hashing schemes is a mixed bag
• use without a salt, it's easy to brute force
• use with or without iterations, it doesn't matter
• The problem is that crypto hashes are designed to be fast and memory efficient
• great for crypto applications, IPsec, and hardware-based password cracking
• speed is actually the problem
• Using crypto hashes by themselves is not a great solution

Password Hashes

• A password hash is not a crypto hash
• though a password hash may use a crypto hash
• A password hash "stretches" a password, to be resistant to brute force attacks
• increases the amount of time it take to test each possible key
• Password hashing takes more resources than a standard crypto hash
• raises the cost of brute force attacks

PBKDF2

• Password-based Key Derivation Function
• RFC 2898 and RSA PKCS #5, v2.0
• published in 2000
• PBKDF2 (PRF, P, S, c, dkLen)
• Recommends 1000 iterations and 64-bit salt
• adjust as needed to increase resistance to attack
• Pseudorandom function and the length of the derived key can be specified
• Used in a variety of file system encryption and password storage tools

Bcrypt

• Algorithm by Niels Provos and David Mazières, published in 1999
• Uses Blowfish with a modified key schedule for setup and standard Blowfish in hashing
• Has an adjustable "cost"
• slows performance to remain resistant to brute force
• Implemented in OpenBSD 2.1 crypt(3)
• Software libraries available
• PHP, Python, Perl, Ruby, C#, Java, Javascript

Scrypt

• Algorithm by Colin Percival in 2009
• Attempts to make hardware-based cracking solutions prohibitively expensive
• based on memory-hard functions which require lots of storage and cannot be parallelized
• No other review found of security claims
• Software libraries available
• C, Python, Java, C#, Ruby

Performance Considerations

user system total real

MD5: 0.000000 0.000000 0.000000 ( 0.000773)

SHA1: 0.000000 0.000000 0.000000 ( 0.000648)

SHA512: 0.000000 0.000000 0.000000 ( 0.000759)

BCrypt cost = 2: 0.130000 0.000000 0.130000 ( 0.124469)

BCrypt cost = 10: 6.290000 0.000000 6.290000 ( 6.294274)

Scrypt: 11.670000 0.050000 11.720000 ( 11.719417)

​

​

​

​

​

​

​

​

​

​

​

Based on code from http://www.binarylogic.com/2008/11/22/storing-nuclear-launch-codes-in-your-app-enter-bcrypt-for-authlogic

Software Libraries

• CryptSharp (C# .NET)
• phpass (PHP)
• pbkdf2-ruby, ruby-bcrypt, scrypt (Ruby)
• scrypt, pbkdf2, py-bcrypt (Python)
• Crypt-PBKDF2, Digest-Bcrypt, Crypt-Scrypt (Perl)

Frameworks

Django: PBKDF2 with SHA-256

Rails: Bcrypt

.NET 4 Framework: PBKDF2

PHP: confusing info, use phpass

​

Avoiding the Issue?

• Should a developer avoid the issue of managing password and user accounts?
• Can a developer off-load the management of user accounts to third-parties?
• What security risks would be avoided?
• Does this help protect the user?

Authentication Outsourcing

• Outsourcing user account management can be accomplished using OpenID, OAuth
• Login with Facebook, Twitter, Google, etc
• Developers allow third-party management of the user account
• no password resets, changes
• no verification email infrastructure
• no close ties to users, limited interaction
• Users choose the provider that offers reasonable services and methods
• two-factor authentication, reliability

Summary

• Password hashing has evolved over time to address Moore's law and security concerns
• Developers should avoid inventing new password hashing mechanisms
• Use established algorithms and techniques
• PBKDF2 and Bcrypt are well-regarded
• Scrypt is the new upstart and appears promising
• Outsourcing authentication and account management is possible and attractive
• Business, marketing, security issues must be addressed

References

• https://krebsonsecurity.com/2012/06/how-companies-can-beef-up-password-security
• http://en.wikipedia.org/wiki/Key_stretching
• http://en.wikipedia.org/wiki/Bcrypt
• http://en.wikipedia.org/wiki/Crypt_(Unix)
• http://dropsafe.crypticide.com/article/1389
• http://en.wikipedia.org/wiki/Password_cracking
• http://en.wikipedia.org/wiki/Rainbow_table

More References

• R. Morris and Ken Thompson, "Password Security: A Case History", Communications of the ACM, vol. 22, pp. 594-597, Nov. 1979.
• http://www.tarsnap.com/scrypt/scrypt-slides.pdf
• RFC2898