PasswordPasswords are the keys to our online identities, and as a result, they’re also near the top of the target list for attackers. There have been countless breaches in the last few years in which unencrypted passwords have been stolen from a database and leaked online, and security experts often shake their heads at the lack of use of encryption or even hashing for passwords. Now, a group of cryptographers is sponsoring a competition to come up with a new password hash algorithm to help improve the state of the art.

Hashing algorithms are used to secure passwords by taking the plaintext password, passing it through the cryptographic hash algorithm, and then storing the resulting digest, rather than the plaintext password itself. That way, if attackers are able to compromise the database of passwords, what they get are the hashes and not the actual passwords.

However, the algorithms used to hash passwords in most cases are functions such as SHA-1 and MD5, which have known weaknesses that open them up to brute-force attacks. So if an attacker is able to access a database of hashed passwords, he may be able to crack them, given enough time and compute power. When these algorithms were designed years ago, the hardware needed to crack a hash produced by one of them was not commonly available. But now, powerful GPUs and FPGAs are widely available and can be used by an attacker to crack hashes relatively quickly.

Matthew Green, one of the panel that’s organizing the new Password Hashing Competition, said that the group is focusing its efforts on passwords because that’s where the biggest problem lies.

“Password hashing is important because it’s where we have a problem. NIST has given us some great standard hashing algorithms. The problem is that these hashes aren’t necessarily designed for the specific problem of password hashing — where you need something that’s fast enough to hash on a server at login time, but slow enough that a GPU can’t crack ten million of them,” Green said.

“We have a few functions for this purpose, but we don’t have a consistent recommendation to give implementers. NIST says to use PBKDF2, which is probably the most vulnerable to GPU cracking. We just learned that Twitter uses bcrypt — a nice algorithm, but designed 11 years ago when FPGAs and GPUs weren’t as common as they are today. Others recommend scrypt because it was explicitly designed to deal with these threats. Unfortunately that claim hasn’t really been reviewed by cryptographers.”

The National Institute of Standards and Technology (NIST) sets standards for cryptographic hash functions and encryption standards and the agency recently approved a new hash function, SHA-3, to replace the existing SHA family of algorithms. Green said that the PHC team has spoken with NIST about the new hashing competition and that the agency will paying attention to the competition.

“My hope is that this competition gives us one or two really solid algorithms to recommend, so folks don’t have to guess anymore. But I’ll be happy if it just gets cryptographers interested in the area. That kind of research all by itself will make us safer,” Green said.

“I would love to have this sponsored by NIST, but they’re full up with competitions right now. However, we’ve spoken to them about this and they’re following our progress. We’re pretty confident the results of the competition will impact future NIST recommendations.”

The panel of judges who will evaluate the hash submissions includes Jean-Philippe Aumasson of Kudelski Security, Green, of Johns Hopkins University, Marsh Ray of Microsoft, Jens Steube of the Hashcat Project, Meltem Sonmez Turan of NIST and Peter Gutmann of the University of Auckland, as well as many others. The details of the call for submissions and technical requirements are on the PHC site.

Categories: Cryptography

Comments (24)

  1. Anonymous
    1

    How would I encrypt a password and then how would I use it when needed?  Is it stored somewhere and I can retrieve it or how does this work?

  2. pogue
    2

    @Anonymous: The type of encryption they’re describing in the article is meant to be used in back end databases for storage on sites that use a login and password system to authenticate a user.  If that database is compromised (stolen) and publicly exposed, it can be vulnerable to people to break those passwords and then login to the site using the user and password combinations.

    I think what you’re looking for is just a password saving system for your own personal computer, in which case something like Lastpass or KeePass would ideally work for you. I use Roboform myself, which is paid software, but it works well and has cloud support on multiple OSes.

  3. Turner
    3

    @Anonymous, The idea behind hashing a password is to have a function h(m) such that if you’re given h(m), recovering m is extremely difficult. Therefore, if I store my password as h(p), and then later present p’, if h(p) == h(p’), then I have offered the correct password and will be allowed on to the site.

    There are of course, lots details associated with this, for example, how do you stop someone simply compiling a long list of all h(m) -> m by searching through all m and pre-computing h(m). Then I simply have to look up the associated values to break the system.

  4. Scott O
    4

    Turner asks a good question, which I’m sure has been thought of: if the hashing algorithm is deterministic, then one who obtained the hashed password file could just find the hashes of the most commonly used passwords to “break” them.

    Can anyone tell us how this basic problem is dealt with in existing algorithms?

  5. Jan van Niekerk
    5

    Assuming the hash algorithm does not have some fatal flaw in it, the only question is how much CPU time you can stand to invest in checking a password’s correctness. Password cracking is done by brute force – there’s nothing to it – if you can do the hash any faster, you can crack it faster too. If you want a password hash 20 times “stronger”, increase the rounds, so that the checking computation takes 20 times longer. It’s not going to help when the password is p@ssw0rd, no matter what that hashes to.

  6. Fobz
    6

    Turner and Scott O.  Google “Password Salt” for how they stop simple dictionary attacks of known hashes for known passwords.

     

  7. 3hasher
    7

    No need to create a new hash algorithm.

    Just use the uncrackable One Time Pad (OTP) ,  even Quantum computers won’t break this crypto.

    The system works like this,  the server stores a very huge file,  say 8TB file or bigger, lets call this Hasher file. Hasher file contains random trash or garbage and its random data inside must not have more than two continous null ‘0x00′.   Once the the user enters a password that password will be calculated in some form and the result of the calculation will be the [offset] for the 8TB file Hasher file.  Then grab the 20-byte data in [offset] of Hasher file, and store that data as the hash of the password in a DB, like what those servers are doing.  

    This will be uncrackable and the DB with hashes will be useless if grabbed by hackers,  unless if the hackers themselves has the 8TB file and the algorithm on how offset was calculated from passwords.

    So did I just win the competition?

  8. 3hasher
    8

    No need to create a new hash algorithm.

    Just use the uncrackable One Time Pad (OTP) ,  even Quantum computers won’t break this crypto.

    The system works like this,  the server stores a very huge file,  say 8TB file or bigger, lets call
    this Hasher file. Hasher file contains random trash or garbage and its random data inside must not have more than two continous null ‘0x00′.   Once the the user enters a password that password will be calculated in some form and the result of the calculation will be the [offset] for the 8TB file Hasher file.  Then grab the 20-byte data in [offset] of Hasher file, and store that data as the hash of the password in a DB, like what those servers are doing. 

    This will be uncrackable and the DB with hashes will be useless if grabbed by hackers,  unless if the hackers themselves has the 8TB file and the algorithm on how offset was calculated from passwords.

    So did I just win the competition?

  9. carp
    13

    3hasher, they are just internet trolls :) except beag, he doesn’t even understand what otp is and how it is being used here..

  10. 3hasher
    14

    My colleague behind me made an improvement on my above post and suggested that the grabbed 20-byte data from Hasher file will then be encrypted (using AES or equivalent)  with the original password,  and the resulting ciphertext will be stored as the hash. 

  11. Gail Ayres
    15

    Interesting you say that, we have the program that goes along with this idea.  We had to create a new RNG and method to support the OTP, cipher. We hold a provisional patent to this program’s method! 

  12. blahblahblah666
    16

    “and its random data inside must not have more than two continous null ‘0x00′. “

    If your 8TB of random data does not contain two contiguous nulls then your random number generator has significant issues.

  13. Anonymous
    17

    This is not encryption, this is hashing. Understand how these two are different (encryption vs hashing) and you’ll answer your own question.

    Basically your password is not encrypted(two-way function) it is hashed (one way function) so no one should know your password but you, not even the application. It is not stored in the db as a hash of your password. So when you log in with your password it is hashed by the application and then matched with the hash stored in the db. This is at a very basic level.

  14. Anonymous
    18

    But the article is not taking about encryption at all! Understand the difference between encryption and hashing. They are not the same.

  15. beag
    19

    You can’t just throw something in that you’ve read about and have no understanding of it’s practical use! For pen and paper yes use a one-time pad but as Schneier put’s it himself;

    ” …doesn’t scale well, doesn’t lend itself to mass-market distribution, is singularly ill-suited to computer networks, and just plain doesn’t work.”

    - schneier.com/blog/archives/2009/09/the_history_of.html

    It’s not the solution, you lose!

  16. 3hasher
    20

    @beag,  I have not read about this somewhere, this comes from my own imagination.  What’s ironic is what you’ve posted and your belief is something you have _read_ about,  a belief that it’s not practical, and you yourself have not applied OTP yourself.

     I have implemented one time pad and has built one utility similar to what i’ve written, and I wrote it using C and a part of it written in hand-crafted x86 asm just to refresh my asm knowledge.  I have the source code (it is private) and I can easily implement it in any server.

     OTP was popular to be difficult to implement because the ‘pad’ must be heavily secured, else everything encrypted using the ‘pad’  will be easily cracked.

      

  17. 3hasher
    23

    I didn’t claim it is a hash algorithm,  it is a hybrid,  both a hash and an encryption for storing server side passwords.

    But any other new hash algorithm that you’ll suggest, will be cracked assuming we have infinite computing power.  While the one I suggested will still be impossible.

  18. 3hasher
    24

    I think I know the flaw in my post,  it is with AES, because it will have different ciphertext:

    AES_cipher(“plain”,key1,IV1)  !=  AES_cipher(“Plain”,key1,IV2)

    the stored hash in db will not be equal the second time AES is used.

    Then I won’t use AES, just that simple.

    Just replace with: SHA1(“20byte_data” + “password as the salt”)

Comments are closed.