title: Is SHA-1 secure for password storage?
body: <p><strong>Conclusion:</strong> SHA-1 is as safe as anything against preimage attacks, however it is easy to compute, which means it is easier to mount a bruteforce or dictionary attack. (The same is true for successors like SHA-256.) Depending on the circumstances, a hash function which was designed to be computationally expensive (such as bcrypt) might be a better choice.</p>
  
  <hr>
  
  <p>Some people throw around remarks like "SHA-1 is broken" a lot, so I'm trying to understand what exactly that means. Let's assume I have a database of SHA-1 password hashes, and an attacker whith a state of the art SHA-1 breaking algorithm and a botnet with 100,000 machines gets access to it. (Having control over 100k home computers would mean they can do about 10^15 operations per second.) How much time would they need to</p>
  
  <ol>
  <li>find out the password of any one user?</li>
  <li>find out the password of a given user?</li>
  <li>find out the password of all users?</li>
  <li>find a way to log in as one of the users?</li>
  <li>find a way to log in as a specific user?</li>
  </ol>
  
  <p>How does that change if the passwords are salted? Does the method of salting (prefix, postfix, both, or something more complicated like xor-ing) matter?</p>
  
  <p>Here is my current understanding, after some googling. Please correct in the answers if I misunderstood something.</p>
  
  <ul>
  <li>If there is no salt, a rainbow attack will immediately find all passwords (except extremely long ones).</li>
  <li>If there is a sufficiently long random salt, the most effective way to find out the passwords is a brute force or dictionary attack. Neither collision nor preimage attacks are any help in finding out the actual password, so cryptographic attacks against SHA-1 are no help here. It doesn't even matter much what algorithm is used - one could even use MD5 or MD4 and the passwords would be just as safe (there is a slight difference because computing a SHA-1 hash is slower). </li>
  <li>To evaluate how safe "just as safe" is, let's assume that a single sha1 run takes 1000 operations and passwords contain uppercase, lowercase and digits (that is, 60 characters). That means the attacker can test 10<sup>15</sup>*60*60*24 / 1000 ~= 10<sup>17</sup> potential password a day. For a brute force attack, that would mean testing all passwords up to 9 characters in 3 hours, up to 10 characters in a week, up to 11 characters in a year. (It takes 60 times as much for every additional character.) A dictionary attack is much, much faster (even an attacker with a single computer could pull it off in hours), but only finds weak passwords.</li>
  <li>To log in as a user, the attacker does not need to find out the exact password; it is enough to find a string that results in the same hash. This is called a first preimage attack. As far as I could find, there are no preimage attacks against SHA-1. (A bruteforce attack would take 2<sup>160</sup> operations, which means our theoretical attacker would need 10<sup>30</sup> years to pull it off. Limits of theoretical possibility are around 2<sup>60</sup> operations, at which the attack would take a few years.) There are <a href="http://www.cosic.esat.kuleuven.be/publications/article-1146.pdf" rel="noreferrer">preimage attacks against reduced versions of SHA-1</a> with negligible effect (for the reduced SHA-1 which uses 44 steps instead of 80, attack time is down from 2<sup>160</sup> operations to 2<sup>157</sup>). There are collision attacks against SHA-1 which are well within theoretical possibility (<a href="http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252/" rel="noreferrer">the best I found</a> brings the time down from 2<sup>80</sup> to 2<sup>52</sup>), but those are useless against password hashes, even without salting.</li>
  </ul>
  
  <p>In short, storing passwords with SHA-1 seems perfectly safe. Did I miss something?</p>
  
  <p><strong>Update:</strong> Marcelo pointed out an article which mentions <a href="http://eprint.iacr.org/2004/304" rel="noreferrer">a second preimage attack in 2<sup>106</sup> operations</a>. (<em>Edit:</em> As <a href="https://stackoverflow.com/questions/2772014/is-sha-1-secure-for-password-storage/2774744#2774744">Thomas explains</a>, this attack is a hypothetical construct which does not apply to real-life scenarios.) I still don't see how this spells danger for the use of SHA-1 as a key derivation function, though. Are there generally good reasons to think that a collision attack or a second preimage attack can be eventually turned into a first preimage attack?</p>