What algorithms are best being attacked by a GPU powered password cracker? For example, I heard that md5crypt that is being used in unix shadow file, is not the best choice for GPU cracking because it is practically md5 being utilized 1,000 times over the original password to get a hash...
Asked
Active
Viewed 3,951 times
7
-
2Are you searching algorithms which are easily attacked, or algorithms which resist best? There is no reason while MD5^1000 should be really harder to crack in parallel than MD5 itself - it just takes 1000 the time, but you can still try it on different passwords in parallel. – Paŭlo Ebermann Nov 20 '11 at 18:02
2 Answers
12
Thousands of iterations of MD5 make the password hashing harder for everybody, regardless of the type of hardware used. It does not make things specifically worse for a GPU. What makes things harder for a GPU (compared to a generic purpose CPU) is anything which uses lots of RAM: a GPU can access much RAM, but not with full parallelism.
Algorithms which rely on 32-bit integer operations (arithmetic and logical) are very efficiently implemented on GPU. This includes MD5, SHA-1, and the "small" SHA-2 (SHA-224 and SHA-256). SHA-384 and SHA-512 use 64-bit operations, and GPU have trouble with that -- so a GPU will give you a lesser boost when cracking a SHA-512 based password hash than a SHA-256 based function. Bcrypt uses a lot of memory accesses to a mutating 4 kB array, and GPU will suffer on that, to the point that basic CPU may be a better choice for trying to crack bcrypt passwords than a GPU. Theoretically, scrypt is even more hostile to GPU.
This is why bcrypt can be viewed as a better choice for password hashing than PBKDF2 (the standard way of doing multiple nested hashing with a generic hash function like SHA-1)(see this answer for details). Still, the configurable number of iterations can make password cracking quite difficult even for a huge GPU, and PBKDF2/SHA-256 with one million iterations will be tremendously more secure against attacks than a single call to SHA-512.
Thomas Pornin
- 322,884
- 58
- 787
- 955
3
GPU's are fast only when you can do a lot of operations in parallel. Hash 'stretching' by feeding a result of a single round of a hash into another iteration as a salt definitely makes the whole process slower. Not only by default you get to do 1000 rounds of MD5, but you cannot do them in parallel, as round 2 must wait for round 1 to get done.
Salted passwords are another 'obstacle' to GPU cracking. If you have a hashing scheme with no salt, the calculated hash can be compared against ALL the different hashes you're trying to crack. With a proper salt (high entropy), if you calculate a hash, all you can compare it to is the hash with the same salt you just used to calculate your hash. Usually that's just one, unless you got lucky (or have a very large set of passwords, or short salts), and no you can compare your value against a few hashes, not just one.
Another aspect of GPU cracking I have not seen discussed is single password cracking vs many. To make a long story short, cracking many passwords can be A LOT faster than if you're trying to crack just one, given that you're using right software for it. So before you're going to run a crack-job, make a short run on your data first, observe the speed. If it's a lot slower than the usual, you probably need to use a different program, or tweak the parameters to bring up performance.
Marcin
- 2,528
- 1
- 16
- 14
-
2Neither salting nor a high iteration count helps specifically against parallel cracking on GPUs - it just makes the whole process proportionally slower (and not applicable for multiple passwords at once, in the case of salting). A GPU (or series of such) still speed up the cracking proportionally to the number of cores. – Paŭlo Ebermann Nov 20 '11 at 18:08
-
_"Salted passwords are another 'obstacle' to GPU cracking."_ - salt make any bruteforce harder, changing the complexity from O(log n) to O(n) regardless if it's CPU, GPU or IdkPU. – Smit Johnth Nov 26 '13 at 19:29