Trust No One
Two weeks after being promoted from Junior to Intermediate Programmer at Paranoid Software Ltd. you've been tasked with implementing a secure sign-in system for the company's new up-and-coming website. Due to "government conspiracies" and myriad other reasons, your tinfoil-hat-wearing boss has mandated that you use no third-party libraries for passwords and authentication. Only his most trusted and loyal employees are qualified to create something so important and sensitive. He'll be reviewing your work at a later time in his secure bunker...
Not being allowed to research industry best practices on this subject via the corporate internet connection (again, "conspiracies"), you sit down to draw up designs for a new database table as follows:
UserName | Password |
---|---|
WayneGretzky | Gr8One99 |
SidneyCrosby | SidTheKid87 |
Each user will sign using a unique user name and corresponding password. When the user submits the sign in form, the submitted credentials will be compared against the database values found in the table and access will be granted or denied accordingly. This design allows for passwords to be verified while remaining flexible enough to allow for additional new columns for features such as temporary passwords, expiration, and more.
Plain Text Woes
You set to work building a new sign in page based on this design. Everything is coming along fine until forgetful Tom drops by your desk after your coffee break. "Looking for something, Tom?", you ask casually. "Maybe...", says Tom, "... I can't remember what I'm looking for, but that's not the only reason I'm here..." Tom scratches his head for a moment before his face changes in a moment of sudden recollection. He begins to explain how he can only remember one password for everything, and he's afraid of what certain other employees might do if they copied his password out of the new database table. They could potentially use it to access his account on another system.
Tom's a nice enough guy with some serious clout and connections around the office. You don't want to upset him, so you revise your design as follows:
UserName | EncryptedPassword |
---|---|
WayneGretzky | Te8Bar99 |
SidneyCrosby | FvqGurXvq87 |
In this revised design, the passwords are stored encrypted using the "ultra secure" ROT-13 algorithm. When a user's sign in credentials are submitted, the database value is decrypted and compared against the submitted password to authenticate the user and grant or deny access to the system.
Clever Estelle
As your project nears completion it needs to pass a review from Estelle, the company's oldest programmer. Estelle got her start in the industry working with VAX machines in the '70s. Nobody knows the details of her top-secret projects, but her office is strewn with archaic servers and mainframes cobbled together with assorted wires and duct tape. She left a barely-legible handwritten note on your desk asking you to stop by for a review of your project.
A light blue haze of smoke oozes out from under the door as you approach and knock briskly. You hear a loud cough before Estelle's unusually deep and raspy voice beckons you to enter. As you enter, you notice the yellow-brown stained walls of her private office. Distracted, you trip over an old server, yanking loose a bundle of wires. "Don't worry", Estelle reassures you, "that machine deserves it!"
Estelle likes your design, but due to her advanced technical savvy, she's figured out how to decrypt the passwords stored in your database and suggests that you use one-way hashes instead. She hands you a ream of fan-fold paper retrieved from an old dot-matrix printer. "Here's some materials I've prepared for you," see grunts as she urges you towards the exit.
After reading her notes about a wide variety of one-way hash algorithms, you once again draft up a design for your database table:
UserName | HashedPassword |
---|---|
WayneGretzky | $2a$12$/Ox24ETwuRKwqCASxD40x.O 7Y1HOuaLzVp7nwf6FwUQjnRGnJok0m |
SidneyCrosby | $2a$12$o7chUYiQh0htw463/m5df.o lmVQzkIjINY9CyyQmtC7xHV53OxtEC |
This time there is a subtle change to the password verification logic. Instead of decrypting the stored password, the submitted password is passed through a one-way hash (in this case bcrypt with 12 iterations) and the hashed values are compared to see if they match.
A good hash algorithm is easy to calculate, but nearly impossible to reverse. They also distribute hashes effectively to avoid collisions (two similar strings hashing to the same value), which makes them statistically secure for use in verifying that you have a matching password.
Tom's Back!
Having passed Estelle's second review, your project is mere days away from being installed. You're enjoying a well-earned break in the lunch room when Tom pokes his head in looking confused. "I'm looking for someone," says Tom, "but I can't quite remember who... Oh yeah, it's you!" You notice that Tom is holding the same dot-matrix print-out about hashes in his hand. He explains that he's found a way to break your password system. He's created a script to generate every string up to an arbitrary length, calculate its corresponding bcrypt hash, and store those in a new indexed database. With this upfront work complete, he can use the newly indexed table to perform a reverse password look-up from the hash of any password short enough to be covered by the script. He calls this generated table a "rainbow table". This could potentially be used to reveal thousands of user's passwords.
After racking your brain late into the evening, you modify your design one last time:
UserName | RandomSalt | HashedSaltedPassword |
---|---|---|
WayneGretzky | PQw#{hC*bDvyHnhVeOGaVOnG dcsiAYETeNBbannZbdtu?kLN dDXjbfDe?slovDjJfw$m2uGf ZRneg-7bDJeeVwSwDGEsonI4 Cini1p*zuJ&HwJRgC 3grzzU c!EKxrSt | $2a$12$tasiR59CA7uefis0. 4r4CuTjo2gD7MkP3Mzzn77yr /QWuRbV8kyf. |
SidneyCrosby | ;ZjmYbJeNMstnqu\q|gbLpfs zb@6PVyOoglbBuLUb-Hulgau nwCR.qvCUikOEkEQroqi8lRY J4gVA{VwlWwh0nyQnZG5JYCm k.cStNNyy|hzgiIqPjSdTlkh zxaZIi_C | $2a$12$o3aiDUMmSDqX9/fpA SJ/VOB483GsYvtfESeZbrON. Gz080gVtlBqW |
In this final incarnation, each password gets assigned its own unique random "salt" value. This value is first concatenated with the password. This "salted" password value is then run through the hashing algorithm to populate the database. When the a user submits a password at sign in, this process is repeated with the submitted password. It is first concatenated ("salted") with the stored random salt, then hashed. The final result is compared the hash stored in the database to grant or deny access.
Your tinfoil-hat-wearing boss emerges from his bunker to shake your hand for a job well done and asks you if you wouldn't mind helping him recover his password...
Transition
The best way to secure your users' passwords is to protect them in such a way that even a programmer with full knowledge and access to the system cannot get at them. A corollary of this is that if you ever submit a lost password request to a website that returns your password in plain text, you know they're doing something wrong.
Several years ago I came across a collection of sites with multiple sign in systems that were at various stages of progression from the story above. Some were storing passwords in plain text, some were storing them using different forms of simple encryption, and others were hashing the passwords (using varying strengths of hashing algorithms) without salting them first. It was my job to bring these all up to snuff without breaking live systems with active users.
The plain-text passwords were the simplest. I already had the passwords -- I salted and hashed them and moved along.
The encrypted passwords were almost as simple. I decrypted the passwords to their plain text form, then treated them as in the plain-text case above.
The hashed passwords were the most challenging. I created an extra database column to list the hash algorithm and imported the hash values into the database with no salt value. When one of these users signed in and was authenticated, I could then use their submitted password value to populate a strong salted hash value on their very first visit under my new system.
There were also some accounts that were not so active. We conveniently had a 90-day password expiration policy. After 90 days, I ran a script to reset all of the remaining passwords to new temporary values and purge our system of all insecurely stored user credentials. Any users who had not signed in within 90 days would have to use our password recovery system to regain access to their accounts.
Take It Away
If there's one thing you should take away from this episode it's that you should do your best to store passwords such that they cannot even be recovered by someone with inside knowledge.
If you know of any code that stores passwords without securely salting and hashing them, please do your best to correct the situation. If that code belongs to you, please go fix it. If not, please write a friendly but firm reminder to get those passwords under control and securely stored.
Cheers,
Joshua Ganes
P.S. In case you missed the joke, ROT-13 just rotates the letters through the alphabet by 13 characters. Please don't use this for any form of security.
Very nice write up. One thing I would do is to differentiate password hashing/key expansion hash functions such as scrypt/bcrypt which are designed to be slow to prevent brute force attacks from such crypto hash functions as SHA2 which are designed to be fast.
ReplyDeletePeople might think that hashing and salting with SHA-256 is a good idea, when it is not.