What is Password Hashing (and How Does It Work)?

If you are a frequent denizen of the Internet like myself, there is a good chance you have received an email that goes something like this:

Dear valued customer,

Recently, our website fell victim to a cyberattack on our corporate network. All passwords were encrypted, but as a precaution we are requiring all of our customers to reset their passwords immediately.

Thank you.

So, there was a breach, some of your information, including your encrypted password, was leaked. Is your account at risk?

Short answer: YES, but why?

To understand this, you must understand the concept of “password hashing.”

A hash is just a way to represent any data as a unique string of characters. You can hash anything: music, movies, your name, or this article. Metaphorically speaking, hashing is a way of assigning a “name” to your data. It allows you to take an input of any length and turn it into a string of characters that is always the same length. Obviously, there are many methods (algorithms) to do this.

A few of the most popular hashing algorithms:

  • MD5 – Given any data will return a unique 32 character hash.
  • SHA1 – Given any data will return a unique 40 character hash.
  • SHA256 – Given any data will return a unique 64 character hash; designed by the National Security Agency.

Lets look at a simple example:

My name is “Jamin Becker”

The MD5 hash representation of my name is:

hashing-diagram-illustration1

The SHA1 hash representation of my name is:

The SHA256 hash representation of my name is:

The reason hashing is secure is simple: hashing is a one way operation. They cannot be reversed. Given a string “eeb7048c69b088739908f5f5144cd1f5”, there is no way to reverse the MD5 hash to return “Jamin Becker”. This is because of the way the mathematicians and programmers structured the MD5 hashing algorithm, and it comes back to a fundamental computer science problem called “P vs NP.” P and NP are just two classes of algorithms.

Most hashing algorithms fall under NP which means they can be quickly calculated. However, the un-hashing algorithms (i.e “eeb7048c69b088739908f5f5144cd1f5” -> “Jamin Becker”) fall under the P class and can only efficiently be solved in polynomial time (i.e using a quantum computer significantly more advanced then the ones available today).

So why is this good for security?

hashing-diagram-illustration2

Say you subscribe to a website and choose password “12345”. Immediately, that website will hash your password, probably with SHA1, and store it in a database. Now every time you login, the website will rehash your password and compare it to the one stored in the database. If they match, you will be successfully authenticated. If the website is ever breached, and the password database is leaked your password will appear as “8cb2237d0679ca88db6464eac60da96345513964” and not “12345”.

So, the attacker has the hashed version of my password and there is no way to reverse it to 12345. I have nothing to worry about, right? WRONG!

One method that is commonly used to get the plain text password from a hash is called a brute force attack. In this attack, the attacker will run through a giant wordlist and hash each word with the appropriate hashing algorithm. They can then compare the hashes in the wordlist to the ones they have obtained from the database. If a hash from the wordlist matches the one in the database, they can simply find the corresponding plain text password in the original wordlist they hashed. Experienced attackers will use extremely large wordlists combined with powerful software to run through millions of password possibilities a second.

wordlist-bruteforce-hash-cracking

Another method of attack attempts to exploit the hashing algorithm itself by creating a hash collision. A hash collision occurs when two different sets of data resolve to the same hash, and while this is rare, it can be deadly. This would allow the attacker to generate a string of characters that is not your password, but still able to log in to your account since it generates the same hash.

Hashing algorithms are becoming more and more advanced. Mathematicians and computer scientists are constantly designing cryptographic hashing algorithms with lower probabilities of collisions. However, it is important to remember that no matter how strong the hashing algorithm is, it can always be cracked using a brute force attack. The good news is that you can easily defend against these attacks as well by simply following best-practice password policy.

  1. Size does matter – the longer the original password the less likely it will appear on a wordlist
  2. Do not be predictable – avoid using words like “password” and “myname123”
  3. Use a mixture of special characters, numbers, upper and lowercase letters

What’s your thoughts on hashing? Share your views in the comment below.

Image credit: Magnifying Glass Online Fingerprint byBigStockPhot

16 comments

    • Yep, I was waiting for this :) I made a mistake in defining the problem, and am glad you pointed it out. Let me amend it here. Cryptographic hashing algorithms fall under the NP class because their hashes can be quickly verified, but not quickly solved. If a P=NP solution exists then many of these algorithms will be obsolete and no longer secure. However, if a solution does not exist then an actual reversal attack on these algorithms is impossible.

  1. Most hash algorithms are not that suitable for hashing passwords. And that is because password -> hash are to fast. If the time to go from password -> hash value take considerat time, brute force cracking will take way to long time. If it is fast, then brute force would be resonable, if not it is to bad to use.

    So slow algorithms are good for security. The fast hash algoritms are still usable for search in tables if their clustering of values are not high.

    • Correct, and really the only one up there that would be suitable is SHA256, the rest are really there to illustrate the concept. For example MD5 is super flawed and shouldn’t be used for password hashing anymore, mostly just file-verification. And even with SHA256 a lot of developers would want to salt and run through several iterations of the hashing algorithm.

  2. > no matter how strong the hashing algorithm is, it can always be cracked using a brute force attack

    This is technically true, but it’s misleading. If your password is strong enough, it will take many years to brute-force.

    • “If your password is strong enough”
      “IF” is a very small word with very big implications. Any password, no matter how complicated, when cracked, is by definition not strong enough. However, by the time you find out, it may be too late.

  3. Also, using more words for password, phrase like “I am going swimming now”, makes brute force attack almost helpless (needs years to calculate). Especially if you use wildcards like “1 @m g0ing …..”. And it is not too difficult to remember. Right?!

    • That completely depends on the password policy. Some websites/software applications allow spaces and special characters some do not.

  4. I have known for some time now, that the longer the password, the usage of special characters like, @, %, !, * , _, and using numbers for letters does work for protection of your password. Of course, brute force can be used, however, when you use all of these protective methods, they will look for easier passwords to break.

    Now, my question to you Jamin … Why, do so many, many companies will NOT allow you to use the longer password and the usage of special characters??? It makes no sense to me, that these companies limit your protection. I do mean, big companies like many financial institutions, major phone companies, so on and so forth. AT&T is one who limits, what you can use for your password. Your password for AT&T must be at least, 6 or more characters long and you can only use letters, numbers, underscore and hyphen. To me, this is very limiting. Oh, AT&T has a graphic bar next to the building of your password, to tell you if, the password is strong enough … Sorry, that just doesn’t “cut it”, with me.

    • Yep, I’ve wondered this many times myself. Here is my theory for why this is so often the case. Most companies operate in a Windows domain environment or if not a Windows domain some environment that facilitates a central place to login. So when you login into your computer at work you are really authenticating to a server on the domain. However, many other applications besides just your login prompt will allow you to authenticate to the domain as well. For example the application you use to clock-in you may use the same credentials as you would to login to your computer. This is because it’s all authentication is happening on a central server.

      These applications such as your “clock-in webpage” have their own security controls to prevent someone hogging resources. For example that particular application may limit the password to only 15 characters, because imagine how long it would take to process (hash) a password of say eight-hundred-million characters. So rather than modify every applications password policy they set a standard one break any of the third party applications.

      The reason most companies limit you to a very small subset of special characters is because of a common vulnerability in many applications (especially web-applications) called SQL/LDAP injection. Where instead of entering a username they enter a value which actually performs some operation on the database that they shouldn’t be able to do.

      Simple example of LDAP injection:

      When prompted for a username and password:

      Username = jamin)(&))

      Password = “”

      On an un-patched application this technique could be used to gain access, because it would be parsed as two separate arguments and return True on the LDAP server. However, this could easily be prevented if the “&”, “(“, “)” were not allowed.

      • After reading Bob Rankin’s – AskBobRankin article, today … That over 1 Billion passwords have been “stolen”, due to “SQL injection” usage. You would think, these companies, many of them Fortune 500 brands, as well as Mom and Pop companies would better protect, their clientele.

        As Bob Rankin stated – “Outrageously simple, isn’t it? But what’s simply outrageous is that the “SQL injection” vulnerability has been well-known for many years, patches have been available nearly as long, and still hundreds of thousands of sites, large and small, remain vulnerable to it!”

        This was why I commented, as I did. I still don’t get it. Many of these same companies are telling their customers, to update their passwords, but, the same companies, still insist upon using “SQL injection”, instead of updating or upgrading to a better method.

        I understand, what you are saying and I think, you do agree with me … These companies are really stupid and dumb, to continually “trust” a very bad method of password protection, just because, they do not want to go through all of the hassell necessary, to update or upgrade.

        Just a note, Bob Rankin feels that most of this “hacking” business, will result in SPAMMING e-Mails. But, he does advise to change your passwords, like we all should do, periodically anyways. :)

    • Thanks for the informative article. I have heard of hashes many times, but never considered what they really are.

      I have run into websites that are surprisingly restrictive in what they would allow in a password, even more so than the AT&T situation mentioned above. This is quite frustrating, because even the ‘formula’ passwords I use have at least one special character in them, and uncommon ones at that. So, when a site allowed only uppercase, owercase and numbers, I did not like this, and had to create a special (and easy to forget) password just for them. Oh, and BTW, I do not like password managers, because even a slight vulnerability in a password manager is many times less secure than simply remembering your passwords and always entering them. Password managers also make it really easy to forget passwords, especially if you do not write them down somewhere.

      • I can absolutely sympathize, a part of me dies every time I have to enter in weak password. Imagine a password that is limited to only upper and lowercase letters and numbers and must be larger than 6 characters long. Many people will have a password that falls between 6 to 10 characters. This means the number of hash possibilities is approximately (number of uppercase + number of lowercase + zero to 9 + blank character) ^ upper bound of password length. So if you wanted to generate all combinations of passwords between 6 and 8 characters this could be done by generating approximately (63^8) – (63^6) or 248 trillion 93 billion 256 million 765 thousand 312 password combinations. Easily cracked in a matter of days/weeks depending on your hardware. However, add in another character set such as symbols you increase the number of permutations needed exponentially.

  5. After reading Bob Rankin’s – AskBobRankin article, today … That over 1 Billion passwords have been “stolen”, due to “SQL injection” usage. You would think, these companies, many of them Fortune 500 brands, as well as Mom and Pop companies would better protect, their clientele.

    As Bob Rankin stated – “Outrageously simple, isn’t it? But what’s simply outrageous is that the “SQL injection” vulnerability has been well-known for many years, patches have been available nearly as long, and still hundreds of thousands of sites, large and small, remain vulnerable to it!”

    This was why I commented, as I did. I still don’t get it. Many of these same companies are telling their customers, to update their passwords, but, the same companies, still insist upon using “SQL injection”, instead of updating or upgrading to a better method.

    I understand, what you are saying and I think, you do agree with me … These companies are really stupid and dumb, to continually “trust” a very bad method of password protection, just because, they do not want to go through all of the hassell necessary, to update or upgrade.

    Just a note, Bob Rankin feels that most of this “hacking” business, will result in SPAMMING e-Mails. But, he does advise to change your passwords, like we all should do, periodically anyways. :)

Comments are closed.

Sponsored Stories