Discussion in 'Article Discussion' started by brumgrunt, 16 Jul 2012.
Oh for the love of God.
How hard can it be to secure your servers from attack?
Very, very hard.
It is very hard indeed. I'm guessing you don't know a lot about website development or server architecture?
There is always a smarter fish! Or in this case a sadder act.
Not a single thing I am afraid.
Don't feel bad - from the fact that Yahoo stored plain-text passwords, it wouldn't preclude you getting a job there...
The article states that random salts make brute forcing harder. That would be the case - but only if the hackers had been dumb enough to not dump the 'salt' field of the table at the same time as they dumped the 'password' field.
The goal of salting is to make using reverse lookup tables impractical, as well as stopping admins from realising that users have the same password. For example, if I set my password to 'password', the md5 hash would be '5f4dcc3b5aa765d61d8327deb882cf99', which can be easily looked up on almost any database (such as md5decrypter.co.uk) since 'password' is really common. If I set my password to 'password' and it's salted with 'd61d8' giving the full password 'd61d8password', it hashes to a value which is not found in the same md5 hash database. Furthermore, two users with the same password will have different salts, so the hashes will be unique, even if the passwords are not.
I use lastpass nowadays. Means that if any one password is compromised, people don't get access to any of my other accounts (Google Authenticator is used to provide 2-factor authentication).
I read the other day that Lastpass had a break in on their systems just recently (I think). I'd been looking at the options for password stuff after the yahoo thing.
I might start using PasswordMaker, just a bit of a hassle going through and changing stuff.
Not quite - the whole point of a salt is that it doesn't matter if the attacker knows the salt or not. If the salt is sufficiently random(ish,) then you could publish the salts publicly and still be perfectly secure.
Attacker wants to crack hashes with no salt: needs to hash dictionary or rainbow table once.
Attacker wants to crack hashes with 10 salts: needs to hash dictionary or rainbow table 10 times.
Attacker wants to crack hashes with 100,000 salts: needs to hash dictionary or rainbow table 100,000 times.
If an average rainbow table takes a powerful computer four months to calculate, then you've just made the attacker need 400,000 months of CPU time to exhaust the hashes. Doesn't matter if the hashes are secret or known to the attacker - he or she still needs to hash the rainbow table (or dictionary) once for each salt.
That's why you wouldn't use rainbow tables in such a case. Rainbow tables are at heart, merely shortcut devices. They're the cryptographical equivalent of a library.
If you have a million unsorted books and you're looking to see if you own a specific book, you just go through each box in turn and pray you find it quickly. (analog of brute force).
If you have a million books and you want to open a library, where each book can be taken out many times by many people, you sort the books first to make them easy to search through (rainbow tables). The sorting operation takes a lot of time, but each subsequent search is fast (rainbow tables).
If you knew passwords were salted, you simply wouldn't use a rainbow table. Generating would be totally impractical, since you'd be taking up terabytes - especially since each salt would only be used roughly once in a moderate to large user database.
Regenerating your rainbow tables thousands of times is akin to getting a million books, sorting them, looking for one book, binning all the books, then getting a million more books (repeat). It's totally impractical - and isn't really even valid as a process. Far better is to get a million books, just check in each box of books for your book, and then bin them.
Salting totally stops the use of rainbow tables - it makes them totally impractical, as you have said.
However, rainbow tables are not brute forcing, as mentioned in the article. Brute forcing is where you simply go through each possible combination of characters until you have a success (it's much faster than regenerating rainbow tables because you don't have to use system storage). A computer with two gtx580s in could test 20 million keys a second. If you knew the keys were salted, you could simply append the salt to the start or end of each trial password. It would not affect the process of brute forcing at all.
Stops rainbow table attacks in their tracks (precomputed lists of hash/password pairs)
Doesn't affect dictionary attacks (testing passwords against words in a predefined list)
Doesn't affect brute force attacks (testing all possible passwords).
You are correct that rainbow tables would be made useless - but that does not in any way affect the statement
I'm confused. You have a good grasp of this, but you're still failing to understand how salts work.
To brute force, the attacker needs to try every possible password combination - as you say. If you hash '0' as a password, you can compare it to every hash in the list. Hashes generated = one, hashes checked = all of them. Then you can move on to '1', then '2,' and so on.
If the hashes are salted, you still need to generate the hashes one at a time. Unlike the above example, however, you can only compare your attempt to the hashes in the list which have a matching salt. You hash '0' with the salt 'a' and get the hash for 'a0' - if someone has the password '0' with the hash 'a,' you'll get a hit, but not if they have the password '0' with the salt 'b' or 'c' or 'd' or... Hashes generated = one, hashes checked = only those with a matching salt.
If you have 10,000 salts, you make the brute force attack 10,000 times more difficult. *That's* why you salt.
For dictionary attacks, it's the same: if you have a 10,000-word dictionary, you need to generate 10,000 hashes to check an unsalted list. If there are 10,000 salts, you need to generate 100,000,000 hashes for a dictionary of the same size. So, as I said, salting "dramatically increase the complexity of a brute-force attack on the hashes."
I think we're disagreeing over the micro and macro scales. If one were attempting to bruteforce all of the hashes simultaneously, then yes, salting would provide a lot of protection. If one were attempting to bruteforce single passwords, then salting would not be at all effective, except against rainbow tables.
If I were attempting to retrieve the plaintext passwords of over a hundred thousand users, I wouldn't worry about getting the full passwords of everyone - because I'd likely be able to commit all the crime I needed to off just a few users. I'd just check each user with the thousand or so most popular passwords - a simple dictionary attack - and I'd likely get a whole bunch of matches over a large sample size. Since the salt must be stored, salting would provide no real additional protection due to the time involved.
So yes, I was wrong - I completely forgot about the case of someone simultaneously bruteforcing all of the passwords. If you're looking for the details of individual users, though, salting provideds no additional protection.
True (rainbow tables aside,) but that never happens. Think like an attacker: you are expending effort to crack hashes in your brute-force attack. If you target a single user, you have only one chance of getting the right hash. If you scan the entire list of hashes for a match, you have 400,000 chances (in this case) of finding the right answer. It's the hash generation that is computationally intensive; once you've generated the hash, trying to match it to an entry on the list takes a fraction of a fraction of a second whether you're comparing one hash or one million hashes. Therefore it's in the attacker's best interest to always target the entire list - it costs very little in the way of performance reduction, but vastly increases the attacker's chances of successfully cracking a user account.
This is exactly the sort of scenario that salting is designed to prevent.
I'll refer to md5 a lot in this post, but sha1 is equally applicable.
MD5 crackers are really fast, it turns out. A computer with 4x5970 graphics cards installed can hope to achieve around 33.1 billion keys tested per second.
If we assume that each core of the 5970s only has enough free registers to store one key, and that multiple cores cannot access the same part of memory (I know, I know, it's already unrealistic).
By testing one key at a time, we allow the key we're hoping to crack to be stored in the registers of the GPU. These are effectively instant access - we lose no time by using them - they can be accessed in the same instruction in which they are addressed.
Now, 33.1/3200*4 = about 2.5 million passwords tested per processor per second.
This is then gutted if you check each one against the four hundred thousand keys you bring up.
They must be loaded from the global memory - and at massive penalty - with CUDA it takes about 500 operations to load from memory. This means that you're taking about 250ms per key - managing a much more sedate 4 passwords per second tested per processor. It's not that bad - you have lots of registers, not just the one - but you'll still be restricted by those loads from memory.
2.5 million / 4 = 625000 > 400000 - it is more effective to run the brute forcing algorithm for each individual key than it is to run the brute forcing algorithm for all keys, since the act of loading each key from system memory is a massive drain on performance.
I'm not saying it's cut and dry - in fact I know my argument is pants because it's 5am and I'm not reasoning properly. I'm just saying that you shouldn't negate the time that needs to be spent accessing those 400000 keys - when you're testing 2.5 million keys per second per processor (Amdahl's law implies the task should be very much parallelizable (if that's a word), if you lose a millisecond per key, you've dropped a lot of time already.
Hashing is very, very cheap for small sources.
Separate names with a comma.