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

1. find out the password of any one user?
2. find out the password of a given user?
3. find out the password of all users?
4. find a way to log in as one of the users?
5. find a way to log in as a specific user?

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?

Here is my current understanding, after some googling. Please correct in the answers if I misunderstood something.

• If there is no salt, a rainbow attack will immediately find all passwords (except extremely long ones).
• 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).
• 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¹⁵*60*60*24 / 1000 ~= 10¹⁷ 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.
• 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¹⁶⁰ operations, which means our theoretical attacker would need 10³⁰ years to pull it off. Limits of theoretical possibility are around 2⁶⁰ operations, at which the attack would take a few years.) There are preimage attacks against reduced versions of SHA-1 with negligible effect (for the reduced SHA-1 which uses 44 steps instead of 80, attack time is down from 2¹⁶⁰ operations to 2¹⁵⁷). There are collision attacks against SHA-1 which are well within theoretical possibility (the best I found brings the time down from 2⁸⁰ to 2⁵²), but those are useless against password hashes, even without salting.

In short, storing passwords with SHA-1 seems perfectly safe. Did I miss something?