At CoreLabs, we spend our time thinking a lot about how to improve different aspects of the computer security, and how to advance the state of the art. Sometimes, our ideas become part of the Core family of products. Sometimes, we investigate theoretical state-of-the-art advances to see what shakes out.
This blog post is about one of those advances.
Password cracking tables have been known and used for 30 years. Using them allows an attacker to pre-compute a lot of cryptographically strong hash pre-images and store them, using far less storage than what it would require to store all the (hash, plaintext) pairs. Using this technique, lots of tables have been calculated, some collaboratively.
But there is a problem with all of them. If you query a server with a hash, looking for the plaintext, both the server and the client know the resulting (hash, plaintext) pair. If this hash was derived from a password, now this password is known by a third-party (the server).
We asked ourselves, how can we solve this issue? Until now, the only known solution was to host the tables oneself, but that solution means each attacker has to host his own tables.
In a paper we published at the 41st JAIIO, we offer a solution. By combining Hellman tables with distinguished endpoints and a private information retrieval scheme we were able to theoretically prove a method that would enable password cracking using hash-reversing tables without having all the tables stored by the password cracker, without revealing the hash or password to a third-party (the server) and without transferring the entire database.
We propose to keep each Hellman table in a different PIR database, as a closed hash table, using the end point as key. When a client wants to retrieve the pre-image of a hash it calculates the end-point for each of the Hellman tables.
Then it calculates each bucket position in the closed hash table and requests the corresponding buckets in all of the tables. Once it retrieves the (chain_start, end_point) pairs, if one of those matches the end-point calculated, it traverses the chain from the start, and if the pre-image of the original hash is found then we succeed. If no end-point matches or the original hash is not found in a chain, the hash cannot be successfully reversed.
While this is an interesting advance, unfortunately it is not fast enough to be of practical use, at this time. But we will keep working, looking for new advances in computer security that may solve this issue, as we always do.
--Aureliano Calvo, Researcher