New attack makes SHA1 password cracking 20% faster, easier than ever

[nsane.forums]

You're not still using SHA1 for password hashing, are you?

A slide from Steube's presentation outlining a more efficient way to crack passwords protected by the SHA1 cryptographic algorithm.

A researcher has devised a method that reduces the time and resources required to crack passwords that are protected by the SHA1 cryptographic algorithm.

The optimization, presented on Tuesday at the Passwords^12 conference in Oslo, Norway, can speed up password cracking by 21 percent. The optimization works by reducing the number of steps required to calculate SHA1 hashes, which are used to cryptographically represent strings of text so passwords aren't stored as plain text. Such one-way hashes—for example 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8 to represent "password" (minus the quotes) and e38ad214943daad1d64c102faec29de4afe9da3d for "password1"—can't be mathematically unscrambled, so the only way to reverse one is to run plaintext guesses through the same cryptographic function until an identical hash is generated.

Jens Steube—who is better known as Atom, as the pseudonymous developer of the popular Hashcat password-recovery program—figured out a way to remove identical computations that are performed multiple times from the process of generating of SHA1 hashes. By precalculating several steps ahead of time, he's able to skip the redundant steps, shaving 21 percent of the time required to crack large numbers of passwords. Slides from Tuesday's presentation are here.

"This technique reduces the computational cost of testing candidate passwords, when one is given the SHA1 hash of an unknown password," Jean-Philippe Aumasson, a Switzerland-based cryptography expert, wrote in an e-mail to Ars. "In mathematical terms, it does so by avoiding redundant operations, that is, operations that have to be performed regardless of the password tested."

Aumasson is the main designer of BLAKE, one of five finalist hash functions in the competition to designate the SHA3 algorithm. In October, it was edged out by another finalist function known as Keccak.

The optimization is only the latest reason architects of websites and networks should abandon SHA1 for password hashing. As Ars explained in a recent featured headlined Why passwords have never been weaker—and crackers have never been stronger, SHA1, MD5, and a variety of other algorithms widely used to protect passwords are grossly unsuited to the job because they were designed to generate hashes quickly using a minimal amount of computing resources. Underscoring the weakness of SHA1 was the June release of 6.5 million LinkedIn password hashes.

Because SHA1 uses a single iteration to generate hashes, it took security researcher Jeremi Gosney just six days to crack 90 percent of the list. Had the same passwords been hashed using an algorithm specifically designed to protect passwords—algorithms such as Bcrypt, PBKDF2, or SHA512crypt—it would have taken Gosney years or even centuries to accomplish the same feat. The latter three hashes are better suited to password storage because they require significantly more time and computation to convert plaintext into hashes.

"Note that using SHA1 for password storage (with or without a 'salt') is not a very good practice anyway," Aumasson wrote.

Steube's research is only the latest method for speeding up the process of generating SHA1 hashes. The official SHA1 specification calls for 1,448 distinct steps to calculate a hash. Before now, Gosney said, crackers had already figured out how to reduce the number to 1,372, and by using special hardware instructions supported by graphics cards manufactured by AMD, many crackers were further able to cut the steps to 868.

"This is where we have been for a few years now, and we all thought this was pretty damn good," Gosney told Ars.

Steube's optimization cuts an additional 134 steps out of the SHA1 hashing process. The method works by eliminating XOR logical operations during the expansion phase of generating a SHA1 hash. Expansion acts as an amplifier of sorts that allows a hash to contain more data than is found in the originating plaintext. Because many of the steps in the process don't rely on the plaintext, they can be carried out using precalculated data.

A 21 percent optimization is impressive, but it's modest when compared with the password-cracking gains that have been achieved in the past few years. The use of graphics cards alone allows inexpensive computers to work thousands of times faster than they did just a decade ago on similarly priced PCs that used traditional CPUs alone. As a result, a PC running a single AMD Radeon HD7970 GPU can try on average 8.2 billion password combinations each second, depending on the algorithm used to protect them. So while the technique unveiled on Tuesday is impressive, it's important to put it in perspective, cracking experts said.

"I don't want to downplay 20 percent, which is significant," Rob Graham, CEO of penetration testing firm Errata Security, told Ars. "But it's not on the order of, say, switching from a CPU to a GPU."

View: Original Article

[rudrax]

What about salted MD5s? anyone?

[brain_death]

SHA-3 ftw!

[irefay]

So, in other words, sites do a dis-service to users when they don't properly hash passwords.

BTW, what does Nsane use to hash user passwords?

[shought]

What about salted MD5s? anyone?

Adding a salt doesn't change the way the algorithm works, but it does offer additional protection.

I once wrote a password hashing function for a website which worked something like this:

Input: password, two salts (random, 8 chars, alphanumeric and some special chars).

Process: split password into two pieces (for instance 'password' would become 'pass' and 'word'). SHA256 hash of the combination (password2 ('word') + salt2 + password1 ('pass') + salt1).

Output: the SHA256 hash with salt2 in front of it and salt1 right after it.

-----

Why is this safer? Suppose the database was compromised and all hashed passwords together with the salts were leaked. In order to braek just one password someone would first need to find out that the salts are added to the string (this is pretty common, but still). After having found the salts this person would need to calculate specific rainbow tables based on these salts. A smart guy might calculate two rainbow tables; one with the order salt1.password.salt2 and another with the order salt2.password.salt2. Both of these rainbow tables would not yield any results.

These salts will of course be different for every user, so every user would require the process described above.

Basically: without having access to the code (which would allow the hacker to get to know how our password algorithm works) it is very difficult (however by no means impossible) to find just one password. Dictionary attacks are impossible because the password is split in half, so the only possibility is literally trying all password combinations with a minimum of 8 + 8 + (minimum password length) characters which contain alphanumerical and special characters.

I'll do the math for you: suppose the minimum length is 6, then there are (26 letters + 26 uppercase letters + 10 numbers + 16 specials)^(8 + 8 + 6) = 422.747.706.000.000.000.000.000.000.000.000.000.000.000 possible combinations for just the passwords with 6 characters. If we add the passwords with 7 characters we take the previous number and add that same number multiplied by 78 (26 + 26 + 10 + 16). If we add the 8 characters password we take both previous numbers and add that same number multiplied by 78 again, and so on.

Now suppose organized criminals got this hashed password. They'd have a lot of money so they might be able to calculate 10 billion SHA256 hashes a second. 10 billion, that's a lot. Because of that you might think it wouldn't take long to crack even the password strategy I mentioned above. Think again:

422.747.706.000.000.000.000.000.000.000.000.000.000.000 =~ 4 × 10^41.

4 × 10^41 / 10.000.000.000 = 4 × 10^31

We still need 4 × 10^31 seconds to calculate all hashes. Let's see how many days that is.

4 × 10^31 / 60 / 60 / 24 =~ 4,6 × 10^26

Quite a lot still. Let's see how many years.

4,6 × 10^26 / 365 =~ 1,26 × 10^24

So it would take 1.260.000.000.000.000.000.000.000 years to find all of these hashes (with current medium grade computer equipment).

So, in other words, sites do a dis-service to users when they don't properly hash passwords.

BTW, what does Nsane use to hash user passwords?

I'm not sure how IPB's password hashing process works. I'm fairly sure they employ at least SHA256 and add (a) salt(s) to the password ;)

[rudrax]

What about salted MD5s? anyone?

Adding a salt doesn't change the way the algorithm works, but it does offer additional protection.

I once wrote a password hashing function for a website which worked something like this:

Input: password, two salts (random, 8 chars, alphanumeric and some special chars).

Process: split password into two pieces (for instance 'password' would become 'pass' and 'word'). SHA256 hash of the combination (password2 ('word') + salt2 + password1 ('pass') + salt1).

Output: the SHA256 hash with salt2 in front of it and salt1 right after it.

-----

Why is this safer? Suppose the database was compromised and all hashed passwords together with the salts were leaked. In order to braek just one password someone would first need to find out that the salts are added to the string (this is pretty common, but still). After having found the salts this person would need to calculate specific rainbow tables based on these salts. A smart guy might calculate two rainbow tables; one with the order salt1.password.salt2 and another with the order salt2.password.salt2. Both of these rainbow tables would not yield any results.

These salts will of course be different for every user, so every user would require the process described above.

Basically: without having access to the code (which would allow the hacker to get to know how our password algorithm works) it is very difficult (however by no means impossible) to find just one password. Dictionary attacks are impossible because the password is split in half, so the only possibility is literally trying all password combinations with a minimum of 8 + 8 + (minimum password length) characters which contain alphanumerical and special characters.

I'll do the math for you: suppose the minimum length is 6, then there are (26 letters + 26 uppercase letters + 10 numbers + 16 specials)^(8 + 8 + 6) = 422.747.706.000.000.000.000.000.000.000.000.000.000.000 possible combinations for just the passwords with 6 characters. If we add the passwords with 7 characters we take the previous number and add that same number multiplied by 78 (26 + 26 + 10 + 16). If we add the 8 characters password we take both previous numbers and add that same number multiplied by 78 again, and so on.

Now suppose organized criminals got this hashed password. They'd have a lot of money so they might be able to calculate 10 billion SHA256 hashes a second. 10 billion, that's a lot. Because of that you might think it wouldn't take long to crack even the password strategy I mentioned above. Think again:

422.747.706.000.000.000.000.000.000.000.000.000.000.000 =~ 4 × 10^41.

4 × 10^41 / 10.000.000.000 = 4 × 10^31

We still need 4 × 10^31 seconds to calculate all hashes. Let's see how many days that is.

4 × 10^31 / 60 / 60 / 24 =~ 4,6 × 10^26

Quite a lot still. Let's see how many years.

4,6 × 10^26 / 365 =~ 1,26 × 10^24

So it would take 1.260.000.000.000.000.000.000.000 years to find all of these hashes (with current medium grade computer equipment).

Thank you very much fir this valuable information.

These salts will of course be different for every user, so every user would require the process described above.

I have heard that a particular site has a certain sets of salts which may differ from region to region and periodically updated but for every different user a different salt, won't it be difficult for a site like facebook who have aLOLtz of users?

[shought]

Thank you very much fir this valuable information.

These salts will of course be different for every user, so every user would require the process described above.

I have heard that a particular site has a certain sets of salts which may differ from region to region and periodically updated but for every different user a different salt, won't it be difficult for a site like facebook who have aLOLtz of users?

Nope, this should be common practice actually: when a new user is created the system should generate one or two unique salts which are added to the password and after that added to the hash as well (because the salt will be required to check whether the password matches the password configured when logging in).

The process I described above consists of very easy code. I'm willing to share it, send me a PM if you want it ;)

[dcs18]

What about salted MD5s? anyone?

In theory it means more-or-less the same thing that the NewsBot tried his best to explain:-

"take everything (including MD5) with a pinch of salt" :sneaky:

[rudrax]

What about salted MD5s? anyone?

In theory it means more-or-less the same thing that the NewsBot tried his best to explain:-

"take everything (including MD5) with a pinch of salt" :sneaky:

Remove the salt and MD5 so that I can directly understand the core meaning of what you said..My brain is like earlier intel 8085 thing..will take really long to crack it. :lol:

[lazzser]

(...)

So it would take 1.260.000.000.000.000.000.000.000 years to find all of these hashes (with current medium grade computer equipment).

(...)

Wow! That´s a lot of time, but if Moore´s law holds by a century more or so, I think that even that huge number won´t be enough.

In a few decades, quantum computers could be a game changer too. But anyways that password hashing scheme seems to be adequate for any practical purpose today.

[shought]

(...)

So it would take 1.260.000.000.000.000.000.000.000 years to find all of these hashes (with current medium grade computer equipment).

(...)

Wow! That´s a lot of time, but if Moore´s law holds by a century more or so, I think that even that huge number won´t be enough.

In a few decades, quantum computers could be a game changer too. But anyways that password hashing scheme seems to be adequate for any practical purpose today.

Moore's low works both ways though: computers get faster, so hashes can be cracked faster, but at the same time it becomes more reasonable to hash more times.

So if computers are 1000 times as fast in 100 years (or something) the hashing algorithms should also use 1000 times as much iterations, so the time to crack a hash should remain relatively stable. This of course only applies when you actually update the hashing algorithm every x years.

[lazzser]

Yes, if you update the algorithm from time to time you´ll will be on par with computers power growth. I think that using a longer hash (more bits) could be a more effective way than iterating over a fixed length hash.

If Moore's law holds, in a century more or less computers would be more than 1.200.000.000.000.000.000.000.000 times faster than current ones. That's a huge number too,and an almost perfect match to the pasword algorithm you were talking about.

This has two readings, one is that you can rest sure that your algorithm will be safe for many, many years to come (that´s what matter); but it could be cracked in some decades, not in a period that is many times the age of the universe as the calculations seemed to suggest at first sight.

[shought]

You're right there, I should have included 'with current processing power' to my short essay ;)

Do wonder how you got this number: 1.200.000.000.000.000.000.000.000.

Moore's law: doubling of transistor count every 2 years. Decade = 100 years, so 50 times.

2^50 = 1.100.000.000.000.000

So in 100 years it would still take 1.260.000.000.000.000.000.000.000 / 1.100.000.000.000.000 = 1.100.000.000 years. Safe enough for me :P

[lazzser]

Counted from a period of 18 months, but is true that most sources gives a period of two years. If power doubles each 18 months (a year and a half), ti grows roughly 1000 times each 15 years, 1.000.000 in 30 years, a trillon in 60 years... and so.

Anyways I don't think that Moore's law will hold unchanged for such period of time. In fact it´s showing signs to be slowing down.

[ck_kent]

Make it a habit to regularly change your password. ;)