Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes

Thomas Ptacek | September 10th, 2007 | Filed Under: Defenses, Uncategorized

The socialbookmarkosphere is abuzz with talk of “rainbow tables”, what they mean for password security, and why they prove that Microsoft did a shoddy job of securing Windows for Workgroups 15 years ago. This really freaks me out. If the “advanced” pole of your threat model is “rainbow tables”, stop working on your social shopping cart calendar application right now: I can’t trust you with my Reddit karma score, let alone my credit card number.

.

To begin, password storage 101: servers don’t usually store actual passwords. Instead, they hash the password, store the hash, and discard the password. The hash can verify a password from a login page, but can’t be reversed back to the text of the password. So when you inevitably lose your SQL password table, you haven’t exposed all the passwords; just the crappy ones.

Now let’s re-explain rainbow tables:

  1. take a “dictionary” —- say, of all combinations of alphanumerics less than 15 characters

  2. hash all of them

  3. burn the results onto a DVD.

You now have several hundred billion hash values that you can reverse back to text —- a “rainbow table”. To use,

  1. take your stolen table of hashes

  2. for each hash

  3. find it in the rainbow table.

If it’s there, you cracked it.

.

Here’s what you need to know about rainbow tables: no modern password scheme is vulnerable to them.

Rainbow tables are easy to beat. For each password, generate a random number (a nonce). Hash the password with the nonce, and store both the hash and the nonce. The server has enough information to verify passwords (the nonce is stored in the clear). But even with a small random value, say, 16 bits, rainbow tables are infeasible: there are now 65,536 “variants” of each hash, and instead of 300 billion rainbow table entries, you need quadrillions. The nonce in this scheme is called a “salt”.

Cool, huh? Yeah, and Unix crypt —- almost the lowest common denominator in security systems —- has had this feature since 1976. If this is news to you, you shouldn’t be designing password systems. Use someone else’s good one.

.

No, really. Use someone else’s password system. Don’t build your own.

Most of the industry’s worst security problems (like the famously bad LANMAN hash) happened because smart developers approached security code the same way they did the rest of their code. The difference between security code and application code is, when application code fails, you find out right away. When security code fails, you find out 4 years from now, when a DVD with all your customer’s credit card and CVV2 information starts circulating in Estonia.

.

Here’s a “state of the art” scheme from a recent blog post on rainbow tables and salts:

hash = md5('deliciously-salty-' + password)

There are at least two problems with this code. Yeah, the author doesn’t know what a salt is; “deliciously-salty-” is not a nonce (also, Jeff, your computer really doesn’t care if you seperate the password from the nonce with a dash; it’s a computer, not a 2nd grade teacher).

But there’s a much bigger problem with this code: the letters “md5”.

Two reasons.

1.

You’re expecting me to go off on a rant about how there is no redeeming quality to justify using MD5 in 2007. That’s true (MD5 is broken; it’s too slow to use as a general purpose hash; etc). But that’s not the problem.

2.

The problem is that MD5 is fast. So are its modern competitors, like SHA1 and SHA256. Speed is a design goal of a modern secure hash, because hashes are a building block of almost every cryptosystem, and usually get demand-executed on a per-packet or per-message basis.

Speed is exactly what you don’t want in a password hash function.

Modern password schemes are attacked with incremental password crackers.

Incremental crackers don’t precalculate all possible cracked passwords. They consider each password hash individually, and they feed their dictionary through the password hash function the same way your PHP login page would. Rainbow table crackers like Ophcrack use space to attack passwords; incremental crackers like John the Ripper, Crack, and LC5 work with time: statistics and compute.

The password attack game is scored in time taken to crack password X. With rainbow tables, that time depends on how big your table needs to be and how fast you can search it. With incremental crackers, the time depends on how fast you can make the password hash function run.

The better you can optimize your password hash function, the faster your password hash function gets, the weaker your scheme is. MD5 and SHA1, even conventional block ciphers like DES, are designed to be fast. MD5, SHA1, and DES are weak password hashes. On modern CPUs, raw crypto building blocks like DES and MD5 can be bitsliced, vectorized, and parallelized to make password searches lightning fast. Game-over FPGA implementations cost only hundreds of dollars.

Using raw hash functions to authenticate passwords is as naive as using unsalted hash functions. Don’t.

.

What is the state of the art here?

1.

First, what your operating system already gives you: a password scheme “optimized” to be computationally expensive. The most famous of these is PHK’s FreeBSD MD5 scheme.

The difference between PHK’s scheme and the one you were about to use for your social shopping cart 2.0 application is simple. You were just going to run MD5 on a salt and a password and store the hash. PHK runs MD5 for thousands of iterations. That’s called “stretching”.

PHK’s MD5 scheme is straightforward to code and comes with Linux and BSD operating systems. If you have to choose between the PHP code you have now and PHK’s scheme, you choose PHK’s scheme or you fail your PCI audit. [∗]

2.

The best simple answer is “adaptive hashing”, which Neils Provos and David Mazieres invented for OpenBSD in 1999. Their original scheme is called “bcrypt”, but the idea is more important than the algorithm.

There are three big differences between Provos-Mazieres and PHK’s scheme:

  1. Bcrypt was invented by two smart guys and PHK’s was only invented by one smart guy. That’s literally twice the smart.

  2. Bcrypt uses Blowfish instead of MD5. Blowfish is a block cipher with a notoriously expensive setup time. To optimize Blowfish to run much faster, you’d have to contribute a major advance to cryptography. We security practioners are all “betting people”, and we usually like to place our bets on the side that “demands major advances in cryptography”.

  3. Provos and Mazieres extended Blowfish. They call theirs “Eksblowfish”. Eksblowfish is pessimized: the setup time takes even longer than Blowfish. How long? Your call. You can make a single password trial take milliseconds, or you can make it take hours.

Why is bcrypt such a huge win? Think of the problem from two perspectives: the server, and the attacker.

First, the server: you get tens of thousands of logins per hour, or tens per second. Compared to the database hits and page refreshes and IO, the password check is negligable. You don’t care if password tests take twice as long, or even ten times as long, because password hashes aren’t in the 80/20 hot spot.

Now the attacker. This is easy. The attacker cares a lot if password tests take twice as long. If one password test takes twice as long, the total password cracking time takes twice as long.

Get it?

The major advantage of adaptive hashing is that you get to tune it. As computers get faster, the same block of code continues to produce passwords that are hard to crack.

3.

Finally, as your attorney in this matter, I am required to inform you about SRP.

SRP is the Stanford Secure Remote Password protocol. It is a public key cryptosystem designed to securely store and validate passwords without storing them in the clear or transmitting them in the clear.

That design goal is cooler than it sounds, because there’s usually a tradeoff in designing password systems:

  1. You can store a hash of the password. Now if you lose the password database, you haven’t exposed the good passwords. However, you also don’t know the password cleartext, which means that to validate passwords, your customers need to send them to you in the clear.

  2. You can use a challenge-response scheme, where both sides use a math problem to prove to each other that they know the password, but neither side sends the password over the wire. These schemes are great, but they don’t work unless both sides have access to the cleartext password —- in other words, the server has to store them in the clear.

Most practitioners will select the hashing scheme. Both attacks —- stolen databases and phished passwords —- happen all the time. But stolen databases compromise more passwords.

SRP resolves the tradeoff. It’s an extension of Diffie-Hellman. The salient detail for this post: instead of storing a salted password hash, you store a “verifier”, which is a number raised to the (obviously very large) power of the password hash modulo N.

If you understand DH, SRP is just going to make sense to you. If you don’t, the Wikipedia will do a better job explaining it than I will. For the test next Wednesday, you need to know:

  • SRP is related to Diffie-Hellman.

  • SRP is a challenge-response protocol that lets a server prove you know your password without your password ever hitting the wire.

  • SRP doesn’t require you to store plaintext passwords; you store non-reversable cryptographic verifiers.

  • “Cracking” SRP verifiers quickly would involve a significant advancement to cryptography.

  • SRP is simple enough to run out of browser Javascript.

Awesome! Why aren’t you using SRP right now? I’ll give you three reasons:

  • SRP is patented.

  • To make it work securely in a browser, you have to feed the login page over SSL; otherwise, like Meebo, you wind up with a scheme that can be beaten by anyone who can phish a web page.

  • SRP is easy to fuck up, so the first N mainstream Rails or PHP or Pylons SRP implementations are going to be trivially bypassable for at least the first year after they’re deployed.

.

What have we learned?

We learned that if it’s 1975, you can set the ARPANet on fire with rainbow table attacks. If it’s 2007, and rainbow table attacks set you on fire, we learned that you should go back to 1975 and wait 30 years before trying to design a password hashing scheme.

We learned that if we had learned anything from this blog post, we should be consulting our friends and neighbors in the security field for help with our password schemes, because nobody is going to find the game-over bugs in our MD5 schemes until after my Mom’s credit card number is being traded out of a curbside stall in Tallinn, Estonia.

We learned that in a password hashing scheme, speed is the enemy. We learned that MD5 was designed for speed. So, we learned that MD5 is the enemy. Also Jeff Atwood and Richard Skrenta.

Finally, we learned that if we want to store passwords securely we have three reasonable options: PHK’s MD5 scheme, Provos-Maziere’s Bcrypt scheme, and SRP. We learned that the correct choice is Bcrypt.

This blog post was brought to you in part by a grant from the Jon M. Olin Foundation. Major underwriting for Matasano Chargen is provided by Archer Daniel Midland Company. ADM: Feeding A Hungry World. And of course, readers like you!

[∗] Disclaimer: I cannot actually flunk your PCI audit.

121 Comments so far

  • Skywing

    September 10th, 2007 1:25 pm

    Ironically, Blizzard Entertainment has still yet to produce a correct SRP implementation (the versions they use for password security in Warcraft III / World of Warcraft are littered with bugs; endian inconsistencies being some of the more common problems with their implementation, though there are other problems with theirs). I didn’t know that it was patented, though.

  • Thomas Ptacek

    September 10th, 2007 1:42 pm

    I had planned to check this for awhile — and even bought a copy of WoW to do it — but did they catch the multiply-by-zero-mod-N bug?

  • Jeff Atwood

    September 10th, 2007 2:13 pm

    Really fantastic post.

    > So, we learned that MD5 is the enemy. Also Jeff Atwood and Richard Skrenta.

    To be fair to Rich, I copy-pasted his salting example, which was *not* for passwords, into my post, which *was* about passwords. So that was my mistake, not his. And yes, I completely agree that we want to use a secure crypto hash for our passwords. And a per-row salt, which I didn’t do a good job of explaining.

    Still, I think publicizing hashes, salts, and rainbow tables is a good thing. Just look at Reddit, who stored their passwords in PLAIN TEXT– I swear I am not making this up– less than a year ago (!)

    http://blog.moertel.com/articles/2006/12/15/never-store-passwords-in-a-database

    The resulting discussion is where I find I learn the most about subjects.

  • Thomas Ptacek

    September 10th, 2007 2:21 pm

    I’m sorry I called you the enemy.

  • Jeremiah Blatz

    September 10th, 2007 2:40 pm

    Technically, if you’re paranoid, you’ll use bcrypt, then hash the result with SHA-256. That way, your hash is provably no weaker than the stronger of either method. Or so Schnier (whose tears factor composites in constant time) tells me.

  • Ted

    September 10th, 2007 2:53 pm

    This maybe a stupid question but where do you store the salt? Do you append the salt to the hashed value and strip it off to re-hash the clear text password? Do you store it in a seperate field? Does it matter?

  • Thomas Ptacek

    September 10th, 2007 2:58 pm

    It doesn’t matter where you store it, but the scheme won’t work unless you do store it, in the clear. The system doesn’t depend on the confidentiality of the salt for security; it depends on the uniqueness of it.

    In a web app, you’d probably put the salt in a seperate column from the hash.

    Again: if you’re just MD5′ing passwords and sticking hashes in a database, don’t bother. It’s really that bad.

  • Thomas Ptacek

    September 10th, 2007 2:59 pm

    (Not a stupid question, by the way).

  • Jeff Atwood

    September 10th, 2007 3:13 pm

    > I’m sorry I called you the enemy.

    No need to apologize — it made me laugh. I do want to defend Rich here, though. His great MD5 post I cribbed from specifically said that he supports using MD5 for *non*-secure use cases only. MD5 has a thousand and one uses, but security isn’t one of them any more. That was sort of the whole point of Rich’s post so I apologize for accidentally subverting that.

    Usually I’m just my own worst enemy, but when I blog, I can be yours too!

    > It doesn’t matter where you store it, but the scheme won’t work unless you do store it, in the clear.

    I was definitely unclear on whether the salt should be a secret or not when I wrote that post. Storing the salts as a column in the table makes sense in retrospect.

    However, based on the comments to my blog entry, it seems that you could opt to “hide” the salt in the code as well. Say, I could opt to run MD5 on the username, then Blowfish on the row id + the resulting username MD5, then Triple-Lutz-PHK-MD5 that plus the password. That per-row unique salting formula would only be known to someone who had the code *and* the database.

    An attacker who obtained the user/hashpass table wouldn’t have any idea what my per-row salts were, because they aren’t stored in the table.

    What are your thoughts on this? Does it matter?

  • Matt

    September 10th, 2007 3:27 pm

    Say, I could opt to run MD5 on the username, then Blowfish on the row id + the resulting username MD5, then Triple-Lutz-PHK-MD5 that plus the password. That per-row unique salting formula would only be known to someone who had the code *and* the database.

    This is a classic instance of attempting to use security through obscurity. Design your system assuming the attacker has the source code. See also Kerckhoffs’ Principle.

  • Jeff Atwood

    September 10th, 2007 3:38 pm

    Allow me to play Devil’s Advocate for a moment.

    I *am* already assuming the attacker can get the source code.

    There is no practical difference between “put the salt in the table next to the hash” and “put the salt formula in the code”. In the worst case, we have the *same exact outcome*: hashed passwords with salts right next to them.

    However, when I put the salt formula in the code, that means the attacker has to do extra work. Having the table is no longer enough. S/he needs the code, too.

    Why would we consciously choose to remove another potential hurdle we can put in front of attackers?

    As I see it, this not a question of “security through obscurity”; it’s an example of defense in depth. Sure, we could keep the two in the same place (in the hashpass/salt table), but instead we could choose to put the salt in the code, which is secured differently.

    I guess it’s the “let’s launch a nuclear ICBM missile” theory of security. You know how in all those movies, they show two people working in the underground silo, both of whom have keys that have to be inserted and turned before the missile will launch?

    I dunno, maybe I’m crazy, but it makes a modicum of sense to me.

  • Chuff

    September 10th, 2007 3:54 pm

    Question:

    I want to store data in cookies and be sure it hasn’t been tampered with when it gets sent back by the browser.

    I need a hash-mac, right?

    Set-Cookie: foo=hash(secret, bar):bar

    Do I also need a nonce?

    What determines the strength of this, a really long/random secret?

    Does the secret need to be changed frequently?

    It needs to be fast.

    Don’t let me fuck this up.

  • Antonio

    September 10th, 2007 3:59 pm

    Or just throw the salt away also… That gives you another ’stretching’ parameter. Really sort of pointless if your using a good algorithm to begin with though.

  • Thomas Ptacek

    September 10th, 2007 4:01 pm

    Throw away the salt and iterate until you find the right hash?

  • Thomas Ptacek

    September 10th, 2007 4:02 pm

    Chuff: if it needs to not be tampered with, don’t sent it to the client. Store it in the session.

  • Thomas Ptacek

    September 10th, 2007 4:03 pm

    Jeff, regarding salt storage, you can put the salt wherever you want. It’s a public value. Storing it the source code doesn’t make it more or less secure than storing it in the database. If knowing the salt values makes your password system less secure, something is wrong with the system.

  • Douglas

    September 10th, 2007 4:04 pm

    > I didn’t know that it was patented, though.

    Wikipedia says it is expired though.

  • Thomas Ptacek

    September 10th, 2007 4:11 pm
  • Chuff

    September 10th, 2007 4:11 pm

    Storing (all) session state server-side is costly (for me).

    So using hmac-sha1 for this is not stupid, right?

    A good, long, random secret; sha1 or sha256; and no one’s going to be writing blog post about how incredibly stupid I am..?

  • Ted

    September 10th, 2007 4:14 pm

    Can you explain a little more on adaptive hashing? Is using blowfish or AES with a salt alone sufficient or is this where the adaptive hashing enters?

  • Thomas Ptacek

    September 10th, 2007 4:17 pm

    Yes, they will. There are lots of moving parts in your proposed system: how keys for the cookies are generated, how they’re stored, whether old cookie values will be replayable, how the cookies will be timestamped, and how data will be canonicalized and verified.

    You are going to go through a lot more effort to get this right and probably fail than you will in solving the problem of storing stuff server-side. I highly recommend you go that route.

  • Thomas Ptacek

    September 10th, 2007 4:21 pm

    (I know this is annoying; the literature is full of all these crypto tools that should help you solve problems, and then effete security practitioners start yelling that you can’t use any of them because you’re not good enough.

    The problem is, crypto usually makes things less secure, not more secure. You almost never use crypto when you don’t need it. You’re always depending on it. You want your security to depend on as few things as you can manage.

    The answer is: if you know what you’re doing, crypto starts solving problems for you once you’re confident that every line of the rest of your system is bug-free and secure. Before that point, crypto causes more problems.)

  • Chuff

    September 10th, 2007 4:22 pm

    What is the state of the art for browser-based sessions?

  • Thomas Ptacek

    September 10th, 2007 4:28 pm

    JSESSIONID, ASPSESSIONID, PHPSESSIONID. On the mainstream platforms, session cookies have had the crap kicked out of them. Use what your framework provides.

  • Jeff Atwood

    September 10th, 2007 6:21 pm

    > If knowing the salt values makes your password system less secure, something is wrong with the system

    Doesn’t knowing the salt make the hashes more vulnerable to attack, at least in theory? Doesn’t the visibility of a salt plus the hash make a rainbow table attack *feasible* on a hash value, at least at the cost of generating a unique rainbow table for each user?

    Whereas a hash with an unknown salt seems completely immune, to me, to any kind of rainbow table attack (assuming the salt is long enough).

    Let me know if I’m misunderstanding this, which is entirely possible..

  • Coda Hale

    September 10th, 2007 6:24 pm

    Yeah, it’s 2007. No jetpack, just some more slosh and noise about how to screw up less while verifying passwords. Woof.

    FWIW, I wrote a simple, portable Ruby gem for doing exactly this kind of thing without worrying too much about it.

    http://bcrypt-ruby.rubyforge.org/

  • Dan Weber

    September 10th, 2007 6:26 pm

    This is an awesome post. It’s going in my list of frequent bookmarks, so I don’t have to explain to everyone what salted passwords are anymore.

    One question, though: since the login to my social lolograms tagging.NET website has to be available to essentially everyone, doesn’t an intense password-guessing function open me to a serious DoS?

    Or I may not have the scale of numbers right; would a scheme that takes .01 seconds to calculate still make brute-forcing it impossible, while requiring attackers to mount a hundred attacks on me a second?

  • Coda Hale

    September 10th, 2007 6:32 pm

    Jeff: Without a salted password hash, an attacker can download and use a rainbow table. With a non-unique “salt” (i.e., a constant string prepended to the password), an attacker can compute a rainbow table for that common salt. With a unique salt, the attacker must perform a dictionary or brute force attack for each individual password.

    If you throw away the salt, you have to guess it each time you want to verify a password, which is kind of a strange construction for key stretching.

  • Dan Weber

    September 10th, 2007 6:36 pm

    > Doesn’t knowing the salt make the hashes more vulnerable to attack, at least in theory?

    Well, it reduces the search space from 2^10000 to 2^1000, so, yes, if someone is determined to brute-force your password, then knowing the salt will help.

    The thing about “rainbow tables” is that a whole bunch of someone elses have already precomputed the list for you. People have just barely managed this for passwords in the commonly used space. If your salt has even a dozen bits, those people would’ve needed to make over 4000 rainbow tables. That’s beyond their resources, at least for now. Even a “constant” salt, like suggested in your column, would break this.

    In some cases, you may even be able to use Google as the store for your rainbow table. Google up the md5 of “password” (5f4dcc3b5aa765d61d8327deb882cf99) for some fun.

    Crazy idea: after your password-verifying script generates a hash, Google for it and make sure that no pages are returned.

    Fun game: after you change away from an old password that you used for a while, put it into Google to see if it ended up anywhere.

  • Sean

    September 10th, 2007 7:09 pm

    “1. take a “dictionary” —- say, of all combinations of alphanumerics less than 15 characters
    2. hash all of them
    3. burn the results onto a DVD.”

    Where do you get your dvds?! By my calculations, you would have 62^14 password hashes. Even if we miraculously collided 999,999 out of 1,000,000 passwords (so you only have to store 1 hash out of every million passwords hashed), you’re still looking at 12 exabytes of data. Do you have 12,000 terabyte DVDs?

    In every discussion on this that I’ve read on this subject, people have drastically underestimated the search space involved.

  • mjo

    September 10th, 2007 9:31 pm

    In response to the keep-the-salt-hidden comments:

    The reason that salt values work is not because they make the password “more secret.” They work because they increase the search space, making an exhaustive search infeasible.

    If your passwords are one character long (for the sake of the example), and the salt is 16 characters *AND RANDOM*, the final hash will be based on a string that is 17 characters long. These 17 characters can be *anything* because the salt is random. Let’s say an attacker has a rainbow table. To have calculated any given password’s hash with certainty, he or she would have to had calculated *all* hashes for strings of length 17, not just those hashes for passwords of length 1.

    The attacker could still brute force the part of the password that isn’t the salt, but this, again, should be infeasible if your password isn’t crap. You’ve basically removed the rainbow table from the equation.

    Furthermore, if you try to “hide” the way that you generate the salt, all you’re doing is shooting yourself in the foot. True, a real attacker probably would not know any of the details beforehand, making the point moot; but, if there’s any order (read: un-randomness) in the way you generate your salt, it will actually REDUCE the size of the resulting search space, which weakens the scheme in theory.

  • Richard Bejtlich

    September 10th, 2007 9:39 pm

    Posts and comments like these are the reason why Matasano is the King of Technical Blogs.

  • Chris

    September 11th, 2007 12:59 am

    I practically shat myself when I saw reference to this “news” (was it on Slashdot? It’s all a blur). Glad I didn’t blog my rant (executive summary: “Damn kids! Get off my lawn!”). This is way, way better than what I had in mind.

    Note: “5″ is not a letter. ;^)

  • Thomas Ptacek

    September 11th, 2007 1:44 am

    typedef char letter;

  • Ted

    September 11th, 2007 1:59 am

    Why not using SPAWKE instead of SRP?
    http://www.toolcrypt.org/index.html?spapwke

  • Dominic White's .tHE pRODUCT

    September 11th, 2007 2:23 am

    Storing Passwords Explained

    Matsano has a great write up on storing/cracking passwords and how salts defeat rainbow tables. Keep a copy to hand out to anyone who asks about salts or when you have to explain to developers how to implement secure password storage.

  • Tech Per

    September 11th, 2007 3:06 am

    *Great* post! Thank you for the information. It sure taught me something, that I will remember next time I has passwords for the database. Great job.

  • Tomas Zellerin

    September 11th, 2007 9:16 am

    Sorry, I do not think you understand (or at least describe correctly) what rainbow tables are. They are space-time tradeoff: you do NOT store all of the hashes, but only (simply said) endpoints of chains of hash-password-hash-password type. So you still burn lot of CPU cycles when recovering the password, but the storage required is not SO big.

    This does not make other points of the article - usefullness of salting and slowness of the algorithm - less valid.

  • Hernan Ochoa

    September 11th, 2007 9:53 am

    Awesome post :). And when it comes to NTLM authentication, forget the freaking rainbow tables and carrying around DVDs, instead use this (unless you really want the cleartext password to test on some other service not using NTLM authentication):

    source code/binaries:
    http://oss.coresecurity.com/projects/pshtoolkit.htm

    docs:
    http://oss.coresecurity.com/pshtoolkit/doc/index.html

    horrible plug, although it is an open source and free tool :); but delete the post if it is inappropriate, I’m just frustrated from being ignored by the ‘Tools’ section and editorial staff of securityfocus after 5 email messages and 10 ‘tool submissions’ :), sorry :).

  • Skywing

    September 11th, 2007 10:08 am

    Thomas: I’m not certain offhand (and the issue you mentioned isn’t familiar to me; I’m hardly a crypto expert). However, drop me a mail off-list (don’t have an address for you presently) and I can fill you in with what I know so far. For various reasons I am not all that comfortable with posting that publicly. The mail attached to the post should work, or skywing valhallalegends _dot_ [com].

  • Nate

    September 11th, 2007 12:46 pm

    Please re-edit your post. While there are patents in the SRP area, the IETF working group on TLS-SRP has decided this is not a blocking issue and thus has moved forward with publishing it. This is a big change from a few years ago when the TLS-SRP draft was stalled due to IP concerns.

    On 2007/8/30, the draft was sent to the RFC editor and it will be published as an RFC if nothing else changes. Of course, I’m not an IETF insider so no guarantees, it just seems like your position of “stay away” is a bit extreme, given the circumstances.
    https://datatracker.ietf.org/idtracker/draft-ietf-tls-srp/

  • Jeff Atwood

    September 11th, 2007 6:46 pm

    Thanks mjo. Great summary. That definitely clears up my confusion over whether the salt should be hidden or not!

    > The reason that salt values work is not because they make the password “more secret.”

    That’s odd, because it feels like that’s exactly what salts are doing for us– taking the user’s password, say “myspace1″, and making it far more secure by smushing (clump of random unicode data) + “myspace1″ together.

    > They work because they increase the search space, making an exhaustive search infeasible

    I agree, but don’t very long passwords accomplish the same thing? I’ve been a long time advocate of passphrases for this reason. Even a trivial passphrase like “myquickbrownfoxjumpsoverthelazydog” would be pretty hard to brute force– even if I told you in advance it was lower-case alpha only.

  • Jason Watkins

    September 11th, 2007 7:24 pm

    As you describe them, rainbow tables are a simple dictionary attack. Perhaps I’ve misunderstood it, but as I understand them, they store a dictionary of hash chains. This means they’re considerably more useful than described in your post against salted values, allowing you leverage a time space tradeoff for whatever amount of storage you have. The same argument about hash speed also applies to walking down the chains.

  • Nate

    September 11th, 2007 8:00 pm

    Jeff, your problem is that you aren’t thinking from an attacker’s perspective. To attack a single account’s password, the strength of the password itself is the only important factor. Adding a random salt only helps when more than one account is being attacked.

    For the case of other accounts on the same machine — the changing salt (unique per user) means that a single pre-processed dictionary can’t be reused between accounts. The attacker’s hash of “apple” under seed “XXXX” is useless to compare against account #2’s password hashed with seed “YYYY”.

    For the case of other accounts all over the Internet (in this case, “all Windows machines”), even if YOU only have a single account, you need a salt to distinguish that password hash from every other Windows system out there, even ones that have the same password as you. Hence adding a salt.

    None of this changes the strength of the password, just the feasibility of attackers reusing information against multiple accounts or multiple systems. A single pre-computed dictionary table that works against “all Windows machines” is obviously a huge population that needs some subdivision, hence salts.

    Let me reiterate that everyone needs a security review, even systems designed by security experts. “Applied Cryptography” actually made this harder since suddenly everyone was an expert, without the hard lesson of learning the need for outside review. Unlike functionality bugs, security bugs are happy to lay dormant for years.

  • kestasjk

    September 11th, 2007 10:14 pm

    Hi, you posted your article in a response to a reddit link to my article on how rainbow tables work. (http://kestas.kuliukas.com/RainbowTables/)

    “make a “dictionary” —- say, of all combinations of alphanumerics less than 15 characters
    hash all of them
    burn the results onto a DVD. “
    I hope you didn’t read about Rainbow Tables from my article, if so I seem to have failed in explaining it.
    It actually computes long “chains” of hash->password->hash->password, and only stores the start and then end. The hashes in the middle of the chain, that aren’t stored, can still be searched. (I won’t go into the details because I already wrote an article on it and linked to it)
    It’s a clever, elegant technique that’s worth learning about for that reason alone.

    “Here’s what you need to know about rainbow tables: no modern password scheme is vulnerable to them.”
    True. No modern password scheme is. Unfortunately most modern software doesn’t use a modern password scheme. Take Windows XP/2000/NT, phpBB, the majority of custom password schemes; they’re all vulnerable to precomputation attacks.

    “Cool, huh? Yeah, and Unix crypt —- almost the lowest common denominator in security systems —- has had this feature since 1976.”
    Yes, but the majority of software since then hasn’t had that feature, and doesn’t have it to this day. Unix crypt is actually quite exceptional for a custom scheme in that it salts hashes.
    Also early UNIX systems only used a 2 character salt, which doesn’t protect it from a precomputation attack.

    “Here’s a “state of the art” scheme from a recent blog post on rainbow tables and salts:

    hash = md5(’deliciously-salty-’ + password)

    There are at least two problems with this code. Yeah, the author doesn’t know what a salt is; “deliciously-salty-” is not a nonce”
    When you deride someone for not knowing what a salt is it’s a pretty good idea to know what a salt is yourself.
    ‘deliciously-salty-’ is a salt, and it will do the trick in protecting against precomputation attacks (though something a little harder to guess would definitely be better).
    Nonces and salts are similar, but nonces are used as a salt and then appended to the hash, while salts are kept secret and are the same for all the hashes.
    ‘deliciously-salty’ is not a nonce, but it is a salt.

    “MD5 is broken”
    MD5 isn’t broken for use with passwords. For digital signatures it’s not recommended, but it’s still perfectly fine to use for passwords.

    “Speed is exactly what you don’t want in a password hash function.”
    It hardly matters. If you have a hash with a salt or nonce, the salt or nonce is say 15 characters = 120 bits long, the password is 5 characters = 40 bits, that’s 2^160 passwords to try (let’s call it 2^130, adjusting for the lack of entropy in most passwords, and let’s reduce it to 2^100 to adjust for collisions).
    Say you have 1000 computers that can try 100 trillion hashes per second each (for reference most modern computers can do a few billion MD5 hashes per second). It’ll take ((2^100)/(100*10^12*1000)) seconds = 400 millenia.

    “Modern password schemes are attacked with incremental password crackers.”
    The programs you make reference to just use a brute-force attack. (This seems to be what you mean by “incremental”). Unless you’re only after one specific hash a pre-computation attack is far more efficient than a brute-force attack.
    Depending on your desired success rate a rainbow table is typically around 60% wasted time, but because you can re-use the computed table you quickly make that time back. A brute force attack doesn’t waste time, but you need to re-do the brute force attack when you have another hash to break.

    “The password attack game is scored in time taken to crack password X. With rainbow tables, that time depends on how big your table needs to be and how fast you can search it. With incremental crackers, the time depends on how fast you can make the password hash function run.”
    The table generation relies on how fast you can run the password hash function too. Also the table size can be grown or shrunk by varying the chain length in the rainbow table, but as you increase chain length you increase collision chance and time taken to search the table.
    Given a pre-computed table, the generation of which can also be parallelized, you will definitely be able to find a given hash faster than using the brute-force method.
    Also “lightening-fast” doesn’t cut it. See the 400 millenia calculation above.

    You’re really suggesting here that brute-force attacks are better than pre-computation attacks in all cases, and that brute-force attacks can be effective where pre-computation isn’t. Very strange..

    “How long? Your call. You can make a single password trial take milliseconds, or you can make it take hours.”
    This is a nice feature for allowing unsalted hash schemes to be used, but as the above calculation showed you don’t need a hash trial to take more than 1 trillionth of a second to be secure, if you have a sufficiently large salt/nonce.

    I’m not sure what you have against Rainbow Tables (it seems like a rather hostile article for something written in opposition to an algorithm), but at least get a better idea of what you’re arguing against first.

    Regards,
    Kestas

  • mjo

    September 11th, 2007 10:37 pm

    You’re correct, Jeff, to think that long passwords also solve the problem. A password of length 30 is much more secure than a password of length 10 with a 20-character salt, because the salt only helps thwart a rainbow table or related attack.

    I should actually qualify that by saying a long password is more secure *if you don’t write it on a post-it and stick it to your monitor.*

    A long password prevents rainbow table attacks just by virtue of being long. In addition, it *also* thwarts brute forcing of any particular password.

    So, how long are your most important passwords? Mine are pretty short, too. As the referenced articles show, you can fit a *ton* of hashed values on a couple of DVDs. Enough to crack any password you’re likely to see in the wild. The salt’s purpose is to make this infeasible by requiring an attacker to bring e.g. millions of DVDs with them.

    Hiding the method used to calculate the salt might make you more confident that an attacker won’t determine a particular salt value, but:
    a) You can’t count on that.
    b) Even if the attacker knows the salt value, it still serves its purpose. You could give it away, and it would still prevent rainbow-table-style attacks.

    Knowing the salt used does make it easier to brute force a particular password, since you’re brute forcing a shorter string; but, hiding the salt is not the way to fix that. Bcrypt for example, does the same thing, and you *can* count on it.

    While I’m here, I’ve got to nitpick Nate’s first paragraph. Salting does help, even when you’re only considering one password. Let’s say you’ve got a rainbow table that contains hashes for all passwords up to length 14. If my salt is 20 characters, guess what? You’re going home. Same with *any* password in the system.

    You can take that salt, and stick it into your algorithm, and begin calculating the hash of every password that begins with my salt, but this is essentially brute forcing the password portion, and takes forever when the values are not pre-computed. It will take extra forever if you use a slow hash function like the article suggests.

  • Andrew

    September 11th, 2007 11:07 pm

    One of the two reasons you supply for not using MD5 does not expose security weaknesses in password hash implementations. Attacks against MD5 (and SHA-1 for that matter) are collision attacks, not pre-image attacks. No attack exists to derive the input to an MD5 hash any quicker than running through all possible inputs, when you are given only the output to work with.

    I would also hesitate to recommend anything other than the SHA-2 series of hashes for new implementations. There are two reasons for this;

    1) It carries with it the significant weight of analysis that has been performed on the SHA series of hashes over the last decade or so. Over all of this time, no pre-image attacks have been found - which is what you need to be concerned about with regard to password security.

    2) Nobody ever got fired for buying IBM. As a general rule, you should always stick to industry standards when implementing crypto-primitives. When you use a hash that is endorsed by NIST and was created by the NSA, you have some recourse to shrug off new attacks by pointing at all the smart people who are efforcing its use. When you use a different crypto primitive, you don’t have this recourse, and you may very well fall foul of actual requirements that dictate the use of specific functions (eg NIST SP 800 57). I am reasonably sure that even Bruce-y baby himself (the creator of Blowfish) would not recommend Blowfish for new designs (although I am happy for Bruce to correct me in this regard).

    However, I whole-heartedly agree with the idea that password hash functions should be computationally intensive. However, this can be done easily enough using multiple iterations of standard hash functions. The number of iterations is really a trade-off between your computational resources and the time budget in which you are working, and those of the attacker identified in your risk profile. Projects such as http://nsa.unaligned.org/ show why this sort of thing is necessary.

    If you wanted to do something really wacky, you could modulo-exponentiate the input|salt using a modulus sized exponent before hashing it to get the final result. This would not be encryption so much as translating the input from pre-image_space to pre-image_space’ using a computationally costly algorithm (but one that you will still find in normal crypto-accelerators if you find you need to scale up the login speed).

    Finally, let me commend the statement:
    “Let me reiterate that everyone needs a security review, even systems designed by security experts.”

    This is a fundamental truth that I find is well understood by people who ‘grok’ security, but is not well understood by most else. The initial entrants to the AES competition are excellent examples of why even smart, experienced, knowledgeable people still need others to look over their work.

  • Thomas Ptacek

    September 11th, 2007 11:16 pm

    I’ll post a correction on the rainbow table attack description. I’m using the word “rainbow table” to describe the generic dictonary attack; I don’t know why I had gotten it into my head that they were all “rainbow tables”, but I did a quick Scholar search and yeah it’s a new term. Weird.

    I don’t think it really impacts the article at all, though: the point is, web app developers read these rainbow table articles and say, “oh, I’ll just use MD5 with a salt” (read the reddit and blog post comments). That’s a really bad answer.

  • Thomas Ptacek

    September 11th, 2007 11:18 pm

    Andrew: you have to place a bet; nobody knows which is going to break first, AES or the next standard hash function. You bet the hash function wins? That seems like a bad bet, given what’s been happening over the last few years, and what’s continuing to happen.

  • Thomas Ptacek

    September 11th, 2007 11:21 pm

    Kestas, “deliciously-salty-” is not a salt. It’s a weird variant of the MD5 hash that prepends “deliciously-salty-” to the input.

    Salts are not kept secret; the original Unix crypt() implementation, where the term originates from, was public data. Shadow passwords were an innovation in the early ’90s.

    What I have against non-practitioners talking about rainbow tables is that the discussion ignores the real threat these applications face, which is that brute force attacks on raw MD5 are *substantially* faster than JtR runs against Unix passwords, which are already extremely fast. If you use salted raw MD5 as your scheme, you are insecure.

  • Thomas Ptacek

    September 11th, 2007 11:25 pm

    Nate, regarding SRP patents: I’m echoing Ferguson’s advice from Practical Cryptography, and noting that there’s an actual issued patent that is still in effect. If you think that the SRP patent isn’t a danger, even if it’s just based on the IETF decision, that’s a topic worth its own post.

  • Andrew

    September 12th, 2007 12:16 am

    “Andrew: you have to place a bet; nobody knows which is going to break first, AES or the next standard hash function. You bet the hash function wins?”

    Errrr …. I’m confused. Where in my post did I imply that AES and hash functions are even comparable, let alone that one is stronger than the other? I would agree that an academic (collision) attack on the SHA-2 series of algorithms is more likely to happen before an academic attack on full round AES, but that is neither here nor there.

    I would happily recommend the use of AES as a cryptographic primitive (along with NIST, the NSA, PCI, and pretty much every western government) - but if you are going to use it as a primitive for a hash function, I’d want to seriously examine the method you are using to turn an invertible algorithm into a non-invertible one-way-function.

  • Thomas Ptacek

    September 12th, 2007 12:48 am

    Uh, by using the password to schedule a block cipher key and encrypting a fixed known plaintext? I refer you back to 1976, or to 1999 for the Provos-Mazieres algorithm that extends it?

  • mjo

    September 12th, 2007 2:49 am

    Andrew:

    When a system attempts to authenticate you, it checks the hash that’s stored in the database against the hash of whatever you type in the equivalent of a “password” box.

    If I find a collision, I now know a value that will hash to the same thing as your real password. As far as the system is concerned, the password that I entered is correct, since it hashes to the value that’s stored in the database.

  • Jason Watkins

    September 12th, 2007 3:43 am

    kestasjk:

    i’m going to pick a fight with your numbers. correct me if i’ve misunderstood something.

    if you have the hash, you likely have the salt. it adds no entropy to the search. what it does do is prevent the size of the password database from decreasing the search time by forcing you to brute force individually.

    while 5 bytes may cover 40 bits, for passwords we’re likely limited to a typical keyboard: that means (26+10+11)*2=94 per character, for ~32.7 bits of entropy. that’s being extremely generous and assuming full strength letters chosen randomly.

    using your figures, we’re likely to brute force the password in under 10 seconds on a single computer.

    i only pick this out, because i don’t want someone to read your otherwise very informative post and conclude that big salts make short passwords safer.

  • Andrew

    September 12th, 2007 4:36 am

    @ Thomas

    There are a number of ways in which block ciphers can be made to provide hash-like functionality. There are also a number of reasons why we do not do away with hash functions altogether and just use block ciphers. Your article (and the algorithm you reference) discusses the value in using Blowfish for the one way transformation from pre-image space (ie plaintext) to image space (ie ‘hashed’) specifically because it has a ‘costly’ key schedule.

    How does this apply to AES?

    @ mjo

    The problem with collision attacks is that you (generally) have no control over the output of the collision - you just get either a block of data that hashes to the same value, or a data subset that you can place within an altered pre-image to produce the same hash.

    When applied to password schemes such results are not often useful unless you can enter arbitrary binary data through the keyboard. This is not a real-world problem for password schemes, and therefore collision attacks do not reduce the security of password hashing schemes (as a pre-image attack would).

  • Nik

    September 12th, 2007 5:57 am

    Thomas, that was excellent and extremely amusing. Nice one!

  • Thomas Ptacek

    September 12th, 2007 8:51 am

    Andrew: AES is slower than SHA256, but that’s besides the point. You argue, “anything is fine, just iterate it lots of times”. Sure. But if you’re going to choose between a block cipher and a SHA-family hash, on purely theoretical terms, the block cipher seems safer.

    We seem to be talking past each other, or arguing for the sake of arguing, so I’ll let you have the last word.

  • calyeo

    September 12th, 2007 3:25 pm

    Does it make sense to do the following?

    whenever a password is created-
    1) generate have a ‘fixed’ seed table for each password char (random seeds per char… can be 2-20 seeds for a 1 char password)
    2) append seed to password (in any variation)
    3) generate hash, append the number of seeds used per char in clear.
    4) hash with MD5 for the fun of it.

    so whenever the server has to decrypt, it has to recreate the table based on number of seeds and do a brute force itself to derive at the password. }:)

    Then we can simulate the web version of “Windows Loading”.

  • Thomas Ptacek

    September 12th, 2007 3:38 pm

    No, because that would be you inventing your own new weird password hashing scheme, when we already have one that works really well.

  • dre

    September 12th, 2007 5:11 pm

    wow… you guys made InfoQ

    RESTEKPA

  • Thomas Ptacek

    September 12th, 2007 6:12 pm

    What’s InfoQ?

  • dre

    September 12th, 2007 6:44 pm

    my favorite feed that replaced curphey, who replaced you, who replaced taosecurity - all of which i still read with fervor

    it’s kind of like my favorite smiths songs, but i eventually stuck with one. although i’m open to the idea of it changing again, but it hasn’t changed in about 10 years

  • Kevin Devine

    September 13th, 2007 8:35 am

    ‘bcrypt’ is indeed a well designed algorithm, and i think using CBC mode instead of ECB would make it more secure..because with ECB, an attacker only has to compute the first 8 bytes to check if he has found a match.

    the advance in cryptography i guess would have something to do with precalculating the setup..?

    i did something like that with SHA-1, see http://packetstorm.linuxsecurity.com/filedesc/sha1.zip.html

  • GDizzle

    September 13th, 2007 10:40 am

    Great explanation. Here’s a question though… If someone can access your user table to see all the hashes/salts, isn’t it most likely that they’ve already compromised the entire system? And if that’s the case, what do they care about passwords, when they can theoretically see your encryption code, and reset any particular hash/salt combo manually? Or couldn’t they just add a back door to the authentication system? Or couldn’t they just execute arbitrary code to do whatever they want? I can see how a nice complete password list for all users is still valuable, but I don’t see how it’s much more valuable than the access they probably already have.

  • RLB3.COM

    September 13th, 2007 1:04 pm

    Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes

    An interesting article on why you shouldn’t build your own password scheme……

  • Henry

    September 13th, 2007 3:19 pm

    What is considered to be a good ’salt’ value? How long should it be? Should it always consists of some sort of symbol or non-alphanumeric char?

    Thanks.

  • Coding Horror

    September 13th, 2007 5:14 pm

    Rainbow Hash Cracking

    The multi-platform password cracker Ophcrack is incredibly fast. How fast? It can crack the password “Fgpyyih804423″ in 160 seconds. Most people would consider that password fairly secure. The Microsoft password strength checker rates it “strong”….

  • Thomas Ptacek

    September 13th, 2007 6:16 pm

    GDizzle: yes, you’re right. The problem is, there is a very high likelihood that for 40% of your users, their password on your application is the same as is on their bank account. You have to protect user passwords carefully.

    Thank you for bringing that up.

  • Thomas Ptacek

    September 13th, 2007 6:17 pm

    Henry: A nonce is always a cryptographically strong random number, the longer the better. But if you’re asking yourself that question, you’re probably doing something wrong: you don’t want to build your own password storage system. You want to use PHK’s MD5 scheme if that’s all you have, or Bcrypt if you can get an implementation for your web stack.

  • Matt

    September 13th, 2007 6:41 pm

    GDizzle:

    I agree 100% with Thomas’s response. However, I wouldn’t want to assume “attacker can read password hashes” == “attacker has 0wned the system”. In particular, any “read-only” attack, e.g. a local file disclosure vuln or maybe some kinds of SQL injection, will give the attacker the password hashes without (or at least before) he 0wns the system.

  • Richard Johnson

    September 13th, 2007 10:40 pm

    GDizzle: In addition to the fact that the users will employ the same passwords on other services [1], and hashes might be obtainable without a previous superuser compromise, consider further user behavior: some users, even if forced to change passwords, will persistently return to the same passwords. Thus an attacker who compromises a system once to the point where he gets the junky hashes, will have a set of credentials for later re-entry as a regular user.

    [1]

  • x

    September 13th, 2007 10:53 pm

    Your Estonian visa application has been denied.

  • add

    September 14th, 2007 7:08 pm

    Good Lord,

    Given enough Cray’s and, any and I mean any p/w is cracked. I would like to thank Tom Cruise and The Church of Scientologi_crap for this inspired moment. You guys spend waaaaaay too much time debating arcana. Go for the weakest link.

    p.s I am trying to take over as the kook du_jour, ffs, give me some propz

  • ryan

    September 14th, 2007 10:40 pm

    In reply to the author’s comment saying that “deliciously-salty-” is not a salt:
    It IS a salt. And so is the password. Every input that determines the resulting hash IS a salt. Um, isn’t it?

  • ryan

    September 14th, 2007 10:41 pm

    or rather, every input is PART of the salt.

  • Thomas Ptacek

    September 15th, 2007 1:11 pm

    Even the Wikipedia (or 51% of people reading it) know that’s wrong, ryan.

  • M. Hamrick

    September 15th, 2007 11:10 pm

    A couple of issues:

    a. I’m surprised no one’s mentioned PKCS#5 as a standard for generating hashes of passwords. The PKCS#5 PBKDF (Password Based Key Derivation Function) says you’re supposed to pick an 8 octet salt and choose some arbitrarily large “iteration count.” The algorithm hashes the password and the salt, then hashes the result of that hash, then hashes that hash again and again, hashing “iteration count” number of times. It also mentions the ASN.1 for storing / communicating iteration counts and salts and algorithms used to hash and it specifies a limited number of hashing algorithms that are suitable. Personally, I think that ASN.1 and BER are a pain in the keester and their only saving grace is that they could be worse. (So what I’m saying is look at PKCS#5 and RFC2898 for inspiration and guidance rather than an implementation template; but after you implement it yourself, always get a competent third party to check out the code. Or better yet, get a competent third party to design and implement the code.

    b. The security of schemes like PKCS#5’s PBKDF comes from the fact that if the server chooses a random 64 bit salt, the dictionary will be expanded 2^64 times. Iterating pass-phrases helps increase the time it takes to find a hit in the rainbow table, but yeah, iterating once isn’t that great. Iterating 10,000 is a little better.

    c. Salts and nonces _are_ effectively the same thing. My experience seems to be that when people are talking about octet strings they’ll say “salt” and when they talk about random bit strings or numbers between 0 and N where N is some large number, the word “nonce” gets used a lot.

    d. SRP _is_ covered by a patent, but Stanford’s Office of Technology licensing says you can use SRP royalty free in commercial or non-commercial applications ( see http://otlportal.stanford.edu/techfinder/technology/ID%3D1724 .) I believe this means you still have to get a license, but that if you don’t use SRP for bidirectional authentication (SRP-Z) you don’t have to pay anything. But… I don’t work for Stanford and I’m not an IP lawyer, so please contact Stanford directly if you have questions.

    e. Collisions in MD5 _are_ a big deal. Well.. they can be a big deal. Consider a situation where you’re an attacker with the password file for 1,000,000 accounts. You may not care which account you get into, only that you get into at least one.

    f. Blowfish still scares me. No offense to Bruce, but Blowfish was designed to be a drop-in replacement for DES. It even has a 64 bit block size. If you create a password hashing scheme like crypt, but it uses Blowfish instead, you’ll still have the problem that it’s feasible to create a look-up table with 2^40 outputs (8 TiB). This reduces your “real” search space to 2^16, which may be practical given that since you’re a bad guy you probably have a bot-net with at least 2^16 machines. I think what I’m trying to say is you can make a bad system with Blowfish. (Twofish or AES on the other hand might be a better choice…)

  • andrew

    September 16th, 2007 5:05 pm

    “e. Collisions in MD5 _are_ a big deal.”

    Collisions in MD5 _are_ a big deal … but not for implementations that use it to secure passwords. These situations are where pre-image attacks are a problem.

    The current state of the art in MD5 collisions provides a collision given two different inputs, such that two different outputs are generated that produce the same MD5 value. See http://cryptography.hyperlink.cz/MD5_collisions.html and http://www.win.tue.nl/hashclash/EC07v2.0.pdf for the most recent research in this area.

    An important step in producing such collisions is the knowledge of the intermediate values produced during the MD5 calculations. These values cannot be known for the password, as the attacker only has access to the final output of the MD5 calculation. Therefore, given the current mathematical knowledge, it is not possible to construct a pre-image that produces a collision with an arbitrary output hash.

    Added to this is the fact that to produce a collision requires adding a value to the pre-image - and this value is generally too large to be considered for a password input. For example, in the recently published paper http://www.win.tue.nl/hashclash/EC07v2.0.pdf (which has been accepted to Eurocrypt 2007, providing some evidence of its pedigree), the production of a collision required appending 4196 bits to each of the certificates to produce the collision. Ignoring the fact that knowledge of both pre-images are required to produce such a collision, how many password systems allow for the entry of such binary strings of such length?

    I agree that new systems should not use MD5 - but making links between current MD5 collision attacks and insecurity in MD5 password schemes is just plain wrong.

  • Coding Horror

    September 17th, 2007 7:27 am

    You’re Probably Storing Passwords Incorrectly

    In Rainbow Hash Cracking, I described an emerging class of password attacks known as Rainbow Tables. But I wasn’t very clear exactly why the attack is so dangerous. The web is nothing if not a maze of user accounts…

  • Bert

    September 17th, 2007 1:29 pm

    Forget Rainbow tables - they are not needed. Forget ever needing to know what the password is; it only tells you something about the user (kids birthday or wife’s name). If you have the hashes to Rainbow table against then you have everything. Pass-the-Hash has been perfected.

    http://oss.coresecurity.com/projects/pshtoolkit.htm

    Along with gsecdump.exe by johannes.gumbel@truesec.se you have one of the best threats to Windows security. Gsecdump -u will dump all the hashes of previously logged in people that have used the computer and didn’t reboot after they logged out. With these hashes you can pass the hash to their systems and gain full access without ever needing to know their passord.

    Yes, there was a better way to store the Windows passwords but that road was not taken so you have to live with the results.

    Many of your unix admins don’t know how to stop a ypcat passwd anyway or else they would stop that from leaking the unix hashes.

  • padawan.info

    September 17th, 2007 1:43 pm

    On storing passwords securely

    Fascinating stuff to read if you’re in the business of handling login credentials on a server: Never store passwords in…

  • greg

    September 17th, 2007 6:53 pm

    One thing I haven’t seen anyone mention relative to trying to crack into web sites is three strikes handling.

    After 3 (or whatever) tries, lock the account for 5-15 minutes. Seems like this would be a severe deterrent to brute force/rainbow attacks. Especially if you don’t inform them that the account is locked, you just keep sending “not recognized” messages.

    Doesn’t such a defense factor in to how “easy” these attacks are in practice vs theory?

  • HMK's Spurious Thoughts

    September 18th, 2007 4:05 am

    Password / Rainbow Tables / Hashes

    Excellent - Required reading: Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes….

  • Jay

    September 18th, 2007 4:34 am

    This is a great thread, and convinced me to not play being I’m a cryptographer. So lets say I’m sold and want to use bcrypt in my next web application. How do I actually do that? Any recommendations of good bcrypt solutions for php and asp?

  • skaffman

    September 18th, 2007 9:16 am

    I’m missing something:

    “To make it work securely in a browser, you have to feed the login page over SSL”

    How is this any different to sending the cleartext password over the same SSL connection?

  • Eivind Uggedal

    September 18th, 2007 12:19 pm

    For those interested I wrote (read: patched together) a Rails plugin that handles authentication using Coda Hale’s bcrypt library:

    http://acts-as-authentable.googlecode.com/

  • Thomas Ptacek

    September 18th, 2007 1:18 pm

    skaffman: that’s the problem with using SRP over the web. You have trust SSL, and if you do, SRP isn’t adding a whole lot. I think Nate might have a cogent rebuttal, but I agree.

  • FiSh

    September 19th, 2007 12:45 am

    This has convinced of what I already suspected - that I don’t know jack when it comes to cryptography. Great post, keep ‘em coming ;)

  • Gregory Magarshak

    September 19th, 2007 9:40 am

    Now, I ain’t no crypto expert (I just enjoy designing websites), but I am sure that password hashing by itself cant be the be-all scheme of 2007.

    While reading your post, I thought of something . . . can someone who is more well versed in things than me tell me whether it’s a good solution?

    Basically — generate hashes of, say, 4x as many characters as you do now. Create 3 or 4 salts and chain them together. Then, put the salts around the password before hashing.

    Then — and here’s the important part: MAKE MORE THAN ONE HASH OF THE RESULT. I mean, if your hash only handles smallish strings, or if it sucks in some other way, you can still hash the strings that are formed by every second letter, letters 4-8, or some other combination. Now the attacker needs to

    1) get your verification code as well as your db
    2) generate rainbow tables for . . . oh wait, there are too many combinations now!! :)

    Is this good?
    Greg

  • Thomas Ptacek

    September 19th, 2007 10:10 am

    No.

  • Gregory Magarshak

    September 19th, 2007 10:22 am

    I knew it. I told ya I’m no crypto expert. But why not? It seems that hashing a bunch of intersecting subsets of your string would increase the complexity of the concatenated hash. It’s no longer a matter of solving the hashes independently of each other, leading to a constant complexity increase. It’s like making a great hash out of a sucky one.

    XXXXXPasswordYYYYYY

    Hash a bunch of subsets of this string, make sure they intersect pairwise.

    The password has to pass ALL these hash tests. How can a rainbow table attack defeat this without growing to prohibitive proportions? I am not a security expert, but I’m a math phd guy :) So I should have SOME intuition about this :-P

    -Greg

  • Thomas Ptacek

    September 19th, 2007 2:54 pm

    The mistake you’re making is not just using bcrypt.

  • Luis Bruno

    September 19th, 2007 6:12 pm

    Care to expand on PBKDF2? I — one of the idiots on reddit talking about cryptographic hashes like they were all the same — just stumbled upon PBKDF2, via Wikipedia.

    AFAICT, I can replace your advice to “use bcrypt” with “use PBKDF2″ and it’s still the same, right?

    Or is PBKDF2 used in a different scenario?

    Many thanks for a great article!

  • Scrod

    September 22nd, 2007 1:57 pm

    I concur. What’s wrong with PBKDF2 to compute an iterated, salted key with SHA1 as the message digest algorithm? This combination seems like the most obvious solution to me, as both are widely-used standards and have received the most attention from security experts. And if SHA1 is of concern, I would suggest Whirlpool, which is nice and slow.

  • Matthew

    September 29th, 2007 3:41 pm

    Okay guys, I know absolutely nothing about cryptography, I have only heard the words md5, blowfish, etc. No research done what so ever.

    I am only here because I came across a rar 3.x file with a password on it, but gained interest in the thread and read well 9/10th’s of it anyways.

    But what got me thinking was when someone said “Think like the attacker”.

    I keep hearing iterations and hashes and rainbow tables for keysets, etc.

    like 15 character passwords and the like but what I don’t understand is this, expand the base character set. Umm, okay don’t flame me because I admit i truly don’t have any idea what i’m talking about, (really I don’t).

    But in my mind you could have a password of 1 character, and i have no idea how many characters are in like unicode or whatever. But say this.

    Build yourself a Brute force program, and Dictionary program and 100 petabyte rainbow table dictionary “thing” and i guess use your standard keyboard as I saw someone put it, like 0123456789abcdefgh…

    But if your password was iluvĈăŖŚ, they’d never get it cuz they dont’ figure anyone uses ascii symbols BUT if they did, there rainbow tables would have to include all ascii symbols same with brute force attacks and the like and then things would be SEVERELY timely for them.

    ok, ok, ok, I know no one is going to type ascii symbols into there password but I would (do when allowed)

    Why I don’t know, but a Suse Linux guru I used to work with did it and I thought it was a great idea.

    Sorry for dumbing the current running IQ of your board down, but I didn’t hear anyone talk about charsets enough so I thought I might say something, keep the thread going, you know :)

    Have Fun everyone

    Matt :-þ

  • Pawprints of the Mind

    October 1st, 2007 10:45 pm

    Need… more… TIME.

    Gödel, Escher, Bach
    I have extremely mixed feelings about this book at this point. Mostly, it’s good; but I’m not sure yet that I agree with certain proofs related to theory of computation. While it’s probably the case that I misunderstand, I need…

  • Ben

    October 15th, 2007 3:35 pm

    Matt,

    The reason character sets aren’t discussed is because they aren’t vitally different from a somewhat longer password. After all, you could always think “iluvCgraveaacute”… instead of using the fancy ASCII characters you typed.

    In the end you discuss number of bits of information content, and a larger character set simply means those bits are stored more compactly.

  • Sam

    October 24th, 2007 3:16 am

    Couldn’t you just do a little constructive coding and make MD5 work for you.

    1. Reverse the hash before storing.
    2. Salt the hash using say 100 unique salts, then server brute-force the password with those salts when validating. (Wouldn’t require storing the salt)
    3. Hash the password, and loop on the result as many times as you wanted, though once would suffice.

    I would think that doing any one of these things would negate the flaws of MD5.

  • davorin

    November 4th, 2007 5:13 pm

    well, from what i think i know, hashes only protect you from someone stealing your db and reading your passwords. if you store hashes instead of passwords you’re safe because they can not invert hashes back to passwords. but hashes aren’t protecting you from brute force or any other attacks, just from someone looking at your stored passwords should they gain access to your db.

    salt makes passwords stronger (more variation) and also unique (eg a rand() hashed, concated to the password and everything hashed again, then finally salt is appended to the hash so you can extract it for comparing).

    and if you don’t want passwords to be seen in plaint text between client and server you must use https.

    well, at least that’s how i see it…

  • Aran

    November 6th, 2007 12:41 pm

    davorin, the point of this article is that some popular hashes DO NOT protect you from someone stealing your DB and reading passwords. If your passwords are stored in a weaker encryption scheme, then someone who gains access to your DB table data could possibly figure out what your password is based on the hashed string. They could use a brute force attack, or use precomputed rainbow tables for a faster attack.

    The point of salting, is to make it more inconvenient for a person trying to decrypt a long series of hashed passwords.

  • davorin

    November 6th, 2007 3:37 pm

    aran, of course, i’ve read the article. but all the comments left me a bit confused so i wanted to clarify ;-)

  • sbell

    November 21st, 2007 9:40 pm

    > Thomas Ptacek September 11th, 2007 11:16 pm: I’ll post a correction on the rainbow table attack description.

    But you haven’t?

  • Flutschkopfblubber

    December 10th, 2007 2:31 pm

    links for 2007-12-10

    Matasano Chargen » Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes
    Sollte JEDER lesen, der auch nur entfernt mit Paßwörtern zu tun hat
    (tags: security php verschlüsselung)

    heise online - IT-Branche fo

  • Patrick

    January 19th, 2008 2:05 pm

    The sole reason you store a hash instead of the password in clear-text in the database, is as everybody knows, because it shouldn’t pose any danger even if the data were to leak. Why wouldn’t md5 hashes do the job?

    The only ways to crack these hashes are by bruteforce since dictionary attacks and rainbow tables are only used to get ridicously easy passwords. If you use good salt, there is no way to bruteforce the password. Consider the following:

    MD5(MD5(PASSWORD)+PASSWORD)

    This would make it impossible to bruteforce, since it will contain more than 20 different characters. And since you were mentioning that MD5 is too fast, well you can always do the following.

    DO 50 Times:
    PASSWORD += MD5(PASSWORD)

    PASSWORD = MD5(PASSWORD)+PASSWORD

    Please explain to me how that is possible..

  • Stephan Wehner

    January 24th, 2008 2:53 am

    I’m looking for references/comments about storing two hashes of the same password.

    If f1, f2 are two one-way-functions in the sense that one is satisfied they cannot be inverted within reasonable time. Then it seems to me the function x->( f1(x), f2(x) ) will not necessarily have that property.

    In other words , it is dangerous to store two differently generated hashes of the same password —

    Is that “true”? Are there examples from real-life?

    – Stephan

  • […] aqui um artigo bastante elucidativo sobre criptografia e como os algoritmos rápidos não são os mais indicados […]

  • […] Thomas Ptacek has written a great post on how you can really protect your passwords. Basically his advice boils down to “don’t write your own security algorithms”. […]

  • davorin

    March 7th, 2008 7:20 pm

    “In other words , it is dangerous to store two differently generated hashes of the same password —”

    if you are using the same algorithm to get the hashes, i can’t see how you can get different hashes for the same password. Hashes would be useless then. However, you could get the same hash for two different passwords, but that is highly unlikely (even more when using salts).

  • […] The Rainbow Tables: What You Need tTo Know About Secure Password Schemes. Thomas Ptacek. 10.9.2007. http://www.matasano.com/log/958/enough-with-the-rainbow-tables-what-you-need-to-know-about-secure-pa... [13] NSA@home. Raudalla toteutettu MD5 ja SHA1 läpikäyntijärjestelmä. […]

  • […] Dies haben andere natürlich auch schon wesentlich genauer und auf englisch beschrieben. […]

  • […] you dont’ believe me, and hell why should you, take it from someone who can tell. A security expert blogging about rainbox tables and general password security (via). Now that’s a post you should definitely read if you have anything to do with a system […]

  • Tyler

    April 10th, 2008 10:33 pm

    I am doing some work on a login system. Could someone point me in the direction of some adaptive hashing resources? I have been doing a little research and I can’t seem to find much. In fact, I made a thread on devShed and it’s already the #2 in a google search for ‘adaptive hashing.’ Unfortunately, no one has even replied yet.

  • Tyler

    April 10th, 2008 10:34 pm

    Oh, and awesome article by the way. I’m not self-absorbed, I swear.

  • vaughan

    May 3rd, 2008 6:32 am

    so how would you rate this system for storing passwords?

    example code below.

    when installing the software (this is web software programmed in PHP, not a PC application). a unique 64 character random string is generated. we store this as $mainSalt, and it is then written to a file with a unique encrypted filename & stored outside of the document root.

    $salt is also generated with a randomly generated 64 character string.

    so yes we use 2 salt keys, 1 stored outside the web root in a file with a randomly generated filename.

    the 2nd salt is stored alongside the hash in the db for that particular user.

    the 2nd salt key ‘$salt’ is unique to that particular user. and is regenerated on each change of password.

    so then we have our encrypt function.

    function icms_encryptPass($pass, $salt)
    {
    $mainSalt = ICMS_DB_SALT;

    $pass_hash = hash(’sha256′, $salt.md5($pass).$mainSalt);

    unset($mainSalt);
    return $pass_hash;
    }

    $pass = plaintext password entered by user.

    $salt = a random 64 character key uniquely generated for that user (stored in the users DB table, regenerated on each change password)

    $mainSalt = a randomly generated 64 character seed that is stored in a file outside of the web root in a file that has a randomly generated filename.

    ICMS_DB_SALT is defined as the 64 character seed that is generated and stored in file outside the web root.

    by using 2 salts (1 which is stored in a file outside web root), the 2nd being unique to each user, makes it that no 2 users will ever have the same password hash even if they have exactly the same plaintext password.

    the salt keys can be upto 255 characters each.

  • CJ

    May 21st, 2008 8:51 am

    Sorry Vaughn, as you’ve put plenty of effort into that evidently. I have no authority to comment on it, but (as above in reply to others) even a pro can only make one quick (or alternatively, cost-effective) judgment: there’s a better (more dependable) choice.
    One of the number of points the author made on which there seems full agreement is: it doesn’t matter how nifty one’s newly invented algorithm seems, because you’re not going to know for sure until it’s too late. What matters is you have a strongly reviewed system using best-practices and (in case the password is valuable elsewhere) known very secure algorithms implemented with well-proven components.

  • Jörn Zaefferer

    June 26th, 2008 9:05 am

    I’m currently evaluating jBCrypt for my Java web application password storage. What I find confusing is that the checkpw-method uses the hashed password as the salt to hash the plaintext password.

    I guess it stores the salt as part of the hash, which contradicts what I’ve read here (eg. store the salt in a different DB column).

    Can someone explain that, maybe recommend a better alternative?

  • […] the reason behind not storing passwords as plain-text I’ll take the stance of security expert Matasano Chargen and advise you to use someone else’s security system (Redux, for […]

  • Kari Pätilä

    July 3rd, 2008 2:54 pm

    Any opinions on http://www.openwall.com/phpass/ version of bcrypt?

  • […] it simple. Ophcrack can crack the password “Fgpyyih804423″ in 160 seconds (or for more here for Thomas Ptacek’s work on the subject or here where Darknet talks about its history). […]

  • […] della propria macchina… Ma all’atto pratico servono a ben poco, perchè come dice Thomas Ptacek: Here’s what you need to know about rainbow tables: no modern password scheme is vulnerable to […]

  • Leave a reply