Jump to content



Photo

Why Can't You Hash a Password Multiple Times

password hashing md5 multiple sha1 sha256 php

  • Please log in to reply
56 replies to this topic

#31 srbeen

srbeen

    Neowinian

  • Joined: 30-November 11

Posted 18 July 2013 - 21:28

I disagree with your simple notion that the key to encryption is to not rely one thing on another; in cryptography this seems to me to be prevalent. Most if not all crypto relies on the discreet logarithm problem for instance. HTTPS relies on both public-key (asymmetric) and symmetric crypto. I could go on, but I'm just nit-picking :p

 

The more secure things are, the more obfuscated they are. Thats really what crypto is. obfuscation.




#32 ShadowMajestic

ShadowMajestic

    Neowinian Senior

  • Joined: 16-April 10
  • Location: Netherlands
  • OS: Windows 8 Pro 64bit
  • Phone: Nokia Lumia 920

Posted 18 July 2013 - 21:45

Just as a matter of interest, the idea of password generating is that every time the password is entered, it generates the same hash. With a "random"  salt as random as a preset salt, just random to those that don't know it.

So how would one have a fully random salt which generates a different hash each time that can actually be used?

Or this in the trend of hash(password+salt+password/username) ? Cause I cant see it working if it isn't easily reproduceable.

 

I personally made my own hashing function using a little used encryption method Whirlpool together with from what I think is a lesser used sha, as it  usually seems sha1, 256 or 512 and im going with 384 as I'm hoping it helps being a bit unpredictable in the hashes you use.



#33 +theblazingangel

theblazingangel

    Software Engineer

  • Tech Issues Solved: 6
  • Joined: 25-March 04
  • Location: England, UK

Posted 19 July 2013 - 00:13

Just as a matter of interest, the idea of password generating is that every time the password is entered, it generates the same hash. With a "random"  salt as random as a preset salt, just random to those that don't know it.
So how would one have a fully random salt which generates a different hash each time that can actually be used?
Or this in the trend of hash(password+salt+password/username) ? Cause I cant see it working if it isn't easily reproduceable.
 
I personally made my own hashing function using a little used encryption method Whirlpool together with from what I think is a lesser used sha, as it  usually seems sha1, 256 or 512 and im going with 384 as I'm hoping it helps being a bit unpredictable in the hashes you use.

I'm finding it a little hard to follow you, but I'll try and respond...
When a user registers a new account on your web application, they provide their desired username and password. You should use a secure CSPRNG (Cryptographically Secure Pseudo-Random Number Generator) in the generation of a salt. You hash the password and the salt together to encrypt the provided password. This could be done something like the following:
$salt = bin2hex(mcrypt_create_iv(20, MCRYPT_DEV_URANDOM));
$passwordHash = hash('sha256', $password . $salt);
You would then store the salt and the hash in the database. A good suggestion made here is that you might like to store the hash method too (and if using PBKDF2/bcrypt the number of iterations also), which will help in getting your application to cleanly handle migration to a different hash function (and/or alternate number of iterations) at a future date. You could concatenate these pieces of data together as a string in the form of HashMethod:Salt:Hash and store it in a single field in the database table if you wished.

The salt above has been generated with a cryptographically secure random generator and it is unique to that user. If the user's password is ever changed, you can generate a new salt for them.

Your own hashing algorithm involving chaining of whirlpool and sha384 is precisely the same kind of thing this entire thread has been discussing. It is doing very little to nothing at all to enhance your security. Furthermore the idea of hiding behind the "lesser used" sha384 in the hope of being "unpredictable" is frankly ridiculous, I'm sorry but it is :/

#34 Salutary7

Salutary7

    Neowinian

  • Joined: 05-March 12

Posted 19 July 2013 - 01:27

I'm interested in N_K's challenge. So usually, it's to be assumed that the rules of passwords are known. If passwords are limited to something like alphanumerics of 8 characters or less, then it's not too hard...

 

52 possible characters (upper and lower), 10 possible digits, and length of 0 to 8 means there are at most 62^8 tasks to carry out (basically the comparison, MD5(MD5(PasswordGuess)) == KnownHash). Sure, 200 trillion of those sounds like a lot, but

MD5 is popular because it is not slow. Fast implementations take advantage of SSE or even better, CUDA, which means you can generate hundreds of millions keys per second. Some rough math shows that (depending on your hardware), it is possible to go through all 200 trillion in less than a week.

 

Still I wouldn't trust my own coding skills to create a program that's really that fast :p



#35 ZakO

ZakO

    Neowinian

  • Tech Issues Solved: 2
  • Joined: 21-September 07
  • Location: Finland

Posted 19 July 2013 - 02:13

I'm interested in N_K's challenge. So usually, it's to be assumed that the rules of passwords are known. If passwords are limited to something like alphanumerics of 8 characters or less, then it's not too hard...

 

52 possible characters (upper and lower), 10 possible digits, and length of 0 to 8 means there are at most 62^8 tasks to carry out (basically the comparison, MD5(MD5(PasswordGuess)) == KnownHash). Sure, 200 trillion of those sounds like a lot, but

MD5 is popular because it is not slow. Fast implementations take advantage of SSE or even better, CUDA, which means you can generate hundreds of millions keys per second. Some rough math shows that (depending on your hardware), it is possible to go through all 200 trillion in less than a week.

 

Still I wouldn't trust my own coding skills to create a program that's really that fast :p

 

Indeed, a single high-end GPU (7970) can generate/compare around 6 billion MD5 hashes per second, worst case 3 billion of md5(md5(text)) per secondif you were to assume the password was alpha-numeric of only 8 characters it would only take (62^8 + 62^7 + 62^6 + 62^5 + 62^4 + 62^3 + 62^2 + 62) / (3 * 10^9) seconds ≈ 20.5 hours. So yeah, if it was 8 alpha-numeric characters or less you could definitely crack it in less than a week (or a day even).

 

Also, since services like Amazon EC2 offer on-demand access to servers with high-end GPUs priced at only $2/hour you could do it much quicker too by simply spinning up a few instances for an hour or two. 



#36 jkenn99

jkenn99

    Neowinian

  • Joined: 04-October 05
  • Location: British Columbia, Canada

Posted 19 July 2013 - 03:54

52 possible characters (upper and lower), 10 possible digits, and length of 0 to 8 means there are at most 62^8 tasks to carry out (basically the comparison, MD5(MD5(PasswordGuess)) == KnownHash). Sure, 200 trillion of those sounds like a lot, but

MD5 is popular because it is not slow. Fast implementations take advantage of SSE or even better, CUDA, which means you can generate hundreds of millions keys per second. Some rough math shows that (depending on your hardware), it is possible to go through all 200 trillion in less than a week.

 

Out of curiosity, I just checked what rate my 5yo computer can compute md5(md5()) at with hashcat, and it was 3GHash/sec. With a newer GPU, I imagine you could compute them at least 2x faster.



#37 Mike

Mike

    Neowinian Senior

  • Joined: 11-August 02

Posted 19 July 2013 - 07:37

Err, no.

 

facepalm.png



#38 articuno1au

articuno1au

    Neowinian Senior

  • Tech Issues Solved: 2
  • Joined: 20-March 11
  • Location: Brisbane, Australia

Posted 19 July 2013 - 07:53

Even worse than that, you guys just calculated the full compute time.

 

Most attacks begin with dictionaries that will obtain 70% or so of passwords and take about an hour to run. On top of that, chances of your password laying at the very end of the that 20.5 hour run are (on average) nearly 0.

 

MD5 is a fast password hash. It's not something you should be using for storing passwords. The same is true of SHA1. If you are looking to hash passwords, you should be using bcrypt or one of the other slow chain hash methodologies.

 

Also, salting doesn't note-worthily increase the compute time for a single password. The benefit of hashing is that you need to recalculate the hashes for every single user name (due to their differing salts).

 

Running MD5 repeatedly, or chaining multiple algorithms only helps you in increasing the compute time, in which case there are better ways to do it >.< When I was starting Crypto at uni, I wondered that myself. The simple answer is that you must at all times assume that an attack is aware of how the encryption scheme works. Security through obscurity (that is hiding how the scheme works) is not security at all. You need it to be publicly known and computationally impractical to attack.

 

Yep..


Out of curiosity, I just checked what rate my 5yo computer can compute md5(md5()) at with hashcat, and it was 3GHash/sec. With a newer GPU, I imagine you could compute them at least 2x faster.

So much worse than that if you have a dedicated chip. There's a dedicated MD5 hashing chip that will scream through them about 200 times faster than that >.<



#39 The_Decryptor

The_Decryptor

    STEAL THE DECLARATION OF INDEPENDENCE

  • Tech Issues Solved: 5
  • Joined: 28-September 02
  • Location: Sol System
  • OS: iSymbian 9.2 SP24.8 Mars Bar

Posted 19 July 2013 - 11:35

Yeah, I was playing around with hashcat last night and I was getting around 1.6 billion MD5 hashes a second on my GTX 570, and that was probably with bad settings.

With the double MD5 case I was only getting 600 million hashes a second.

...
To be clear, salting does NOT "defeat" rainbow tables in any case, it simply requires new ones be generated that incorporate the salt in the computation.

Using usernames for salts isn't a great idea. Usernames are reused and may be publicly known, reducing lookup-table storage requirements for an attacker and allowing them to pre-compute lookup tables in advance of breaching a database. With random salts, which an attacker should presumably only gain access to at the same time as the hashes, i.e. upon breaching the database, lookup-tables must be generated at that point and passwords cracked before the breach is discovered and passwords changed. Using the username as a salt isn't terrible, but its not as good as a proper random salt.
...


What I meant by "defeating" rainbow tables, was that you'd have to re-generate the table for each user (and only that user), so you're spending a lot of time pre-generating a single use dataset, when you could just compare the hashes as you're generating them against the hash you have instead (So if you hit a match, you don't waste time by generating the rest of the table)

Although with my earlier comment about GPU based hash computation, maybe that isn't such a big deal.

Question though, what makes a random per user salt stronger than salting with the username? Is it just that the username would contain "less randomness" compared to a random salt? You're storing them both in the database so I don't see that as the weakness.

#40 Salutary7

Salutary7

    Neowinian

  • Joined: 05-March 12

Posted 19 July 2013 - 12:45

Question though, what makes a random per user salt stronger than salting with the username? Is it just that the username would contain "less randomness" compared to a random salt? You're storing them both in the database so I don't see that as the weakness.

 

I don't think there is any significant difference. They accomplish the same goal of having a unique salt per user account.



#41 primexx

primexx

    Neowinian Senior

  • Tech Issues Solved: 6
  • Joined: 24-April 05

Posted 19 July 2013 - 14:26

The more secure things are, the more obfuscated they are. Thats really what crypto is. obfuscation.

uh... what? guess you've never heard of one-time pads...

 

I don't think there is any significant difference. They accomplish the same goal of having a unique salt per user account.

does length or entropy matter for a salt given that it's known anyway?



#42 Salutary7

Salutary7

    Neowinian

  • Joined: 05-March 12

Posted 19 July 2013 - 17:17

does length or entropy matter for a salt given that it's known anyway?

 

One of the desirable traits of hash algorithms is that small changes to the input will result in seemingly unpredictable changes to the output. The two hashes for "abc" and "abc1" will look just as different from each other as the hashes for "abc" and "abc2". So the 'randomness', length, or any other quality of the salt shouldn't make a difference, so long as the same salt isn't repeatedly used. Obviously, though, in other cryptographic scenarios, entropy and length of keys does play a big part in security.



#43 +theblazingangel

theblazingangel

    Software Engineer

  • Tech Issues Solved: 6
  • Joined: 25-March 04
  • Location: England, UK

Posted 20 July 2013 - 00:00

<snip - palm-face image a bit large...>

Let me give you a better reply :p (Though I'm just going to be repeating myself a bit and I'm not sure you're actually after one...)
...>

You do realise that the md5 hashes have a small number of characters and a fixed length. The original MD5 (the hash of the password) is trivial to find because you know its exact length and what characters are in it!

Yes, we know that an md5 hash is exactly 32 characters long and made up of hexadecimal digits only (case in-sensitive), i.e. it's 128-bits long. Knowing this does not help us at all though in doing a reverse iterative lookup with lookup/rainbow tables to get to the first hash, as I've already pointed out. There are 2^128 (3.40282366920938463463374607431768211456 × 10^38) possible permutations (unique md5 hashes). In order to *guarantee* being able to do such an iterative reverse lookup, for absolutely any password string imaginable, you would need every single one of these hashes in a lookup table and beside each the corresponding output hash of hashing them. Never mind the time required to compile it and later search it, without any overhead (or compression), you would need 128bits * 2 * (2^128) = 8.7112285931760246646623899502532662132736 × 10^40 bits = 9.903520314283042199192993792 × 10^27 TERABYTES of storage. You can reduce this requirement significantly if you instead have a much smaller set of passwords that you're wanting to be able to crack, in which case you only need all of the intermediate and final hashes of chain-hashing those for as many iterations as the algorithm used. But then this trade off makes it much less certain that you're going to be successful.
 

What I meant by "defeating" rainbow tables, was that you'd have to re-generate the table for each user (and only that user), so you're spending a lot of time pre-generating a single use dataset, when you could just compare the hashes as you're generating them against the hash you have instead (So if you hit a match, you don't waste time by generating the rest of the table)

Although with my earlier comment about GPU based hash computation, maybe that isn't such a big deal.

Sure, it may very well be more efficient to compare as you go along in such a case, therefore turning it into a brute-force type attack. So now I'm just being pedantic about lookup/rainbow tables being "defeated" when they're still perfectly viable, just not necessarily the best option. (Y)
 

Question though, what makes a random per user salt stronger than salting with the username? Is it just that the username would contain "less randomness" compared to a random salt? You're storing them both in the database so I don't see that as the weakness.

I don't think there is any significant difference. They accomplish the same goal of having a unique salt per user account.

does length or entropy matter for a salt given that it's known anyway?

One of the desirable traits of hash algorithms is that small changes to the input will result in seemingly unpredictable changes to the output. The two hashes for "abc" and "abc1" will look just as different from each other as the hashes for "abc" and "abc2". So the 'randomness', length, or any other quality of the salt shouldn't make a difference, so long as the same salt isn't repeatedly used. Obviously, though, in other cryptographic scenarios, entropy and length of keys does play a big part in security.

If usernames were acceptable salts here then surely the output of any random number generator would also suffice. So why then is it that articles such as this one recommend that a CSPRNG must be used? (Admittedly I don't believe that article to have been written by an "expert" cryptographer, and it itself doesn't give an explanation). The only logical explanation that comes to my mind is that the use of a decently unpredictable method of salt generation makes it much more difficult for an attacker, *PRIOR* to breaching your system and obtaining the actual salts, to create pre-computed lookup/rainbow tables incorporating salts actually in use in your system. An attacker is at an advantage if he can generate such tables in advance of breaching your security.

#44 +Xinok

Xinok

    Resident Reresident

  • Joined: 28-May 04
  • Location: Shikaka
  • OS: Windows 7 x64
  • Phone: Galaxy S3

Posted 20 July 2013 - 00:35

One of the desirable traits of hash algorithms is that small changes to the input will result in seemingly unpredictable changes to the output. The two hashes for "abc" and "abc1" will look just as different from each other as the hashes for "abc" and "abc2". So the 'randomness', length, or any other quality of the salt shouldn't make a difference, so long as the same salt isn't repeatedly used. Obviously, though, in other cryptographic scenarios, entropy and length of keys does play a big part in security.

I understand what you're saying and don't necessarily disagree with you, but in most cases, there simply isn't any good reason to compromise on security. It often comes down to laziness or incompetence. When a web service stores user passwords without salt (or even worse, as plain text), it makes you question the quality of their service as a whole.

 

In the end, it really is best to stick to standard cryptographic protocols rather than making up your own. Do a little research into the encryption used by MEGA to understand why; you'll find that security researchers quickly pointed out several issues with it.



#45 SuperKid

SuperKid

    Im no superman

  • Joined: 21-April 08
  • OS: Windows 8.1, OS X 10.10, iOS 8
  • Phone: iPhone 6 Plus

Posted 21 July 2013 - 12:07

Is bcrypt hashing secure?