In February this year, a team of researchers both from Google and CWI Institute in Amsterdam announced that they were able to generate two PDFs documents with different content that would hash into the same SHA-1 digest. This may lead to a big problem in security that I will try to explain to you but first let’s put ourselves in context.

What is a hash?

The hash functions are one of the most flexible tools used by modern cryptography, they are used in a wide variety of fields and solutions, such as in browser security, checking the integrity of data, managing code repositories, etc. What does a hash function do? In simple words, it takes data of any size as input and maps it to an output value of fixed size, called digest. They have several properties and requirements, such as to be sure that from the digest nothing about the original data can be known or that the same input data will always produce the same digest. The most interesting and complicated requirement is that finding two or more files with the same digest should be computationally infeasible.

Why is this an issue, and why should we be concerned about this?

When using hash functions we have a method to distinguish two different files, even if the difference is minimal. We can be sure that if an attacker takes our file and replaces it with a malicious code, the hash value would be different, therefore we can detect that something has happened with our data. But what if somebody can generate one pair of files with the same digest?

Although finding two files or pieces of data with the same digest is computationally infeasible, it doesn’t mean that it is impossible. In fact, it means that the amount of time to find them would be enormous, but it will only be a matter of time for somebody to find them. That’s what is called a collision. Until February this year, we relied on the amount of time that it would take somebody to find a collision.

Time is on our side, or it is not?

Much of the tools and mathematical approaches which are used in the security field, relay on the idea of the huge amount of processor time that it would take to find out an inconsistency or solution to a problem. It can be fairly easy to see if those mathematically approaches are correct, and the way to go, but it is naive to follow them blindfolded and never change them. Due to the pace of electronics evolution, and the researchers that try to find those holes, new methods and inconsistencies to break those tools, those amounts of time, decrease rapidly.

There is a story that fits perfectly with the false perception of time, one that may let us take a peek into the necessity of continual growth that should be linked to software security. The story of the RSA-129 challenge.

One of the fathers of RSA, Ron Rivest, published back in 1977, in a Scientific American issue that year, a challenge said to take 40 quadrillion years to be solved. They released a RSA-129 number and challenged the readers to find the pair of prime numbers that factorize that RSA-129 number. It only took 17 years to be solved.

What about SHA-1, and what should be done?

SHA-1 was the evolution of the Secure Hash Algorithm, published by the NSA (National Security Agency) in 1995, more than 20 years ago. Things have changed enormously since those days. New GPUs are thousands of times faster, the methods to attack the hash functions have changed from brute-force to more complex ones. With that said, it was quite probable that any of the teams involved in finding holes in the SHA-1, would find something sooner than later.

The main problem here is to be confident, and to assume that it will take a lot of time to break the tools we use for security, but as we have seen that’s not the case. We should always be concerned about software security, and lately maybe even more, and always be prepared to climb the security stair, having always the new implementations of old protocols, migrating to SHA-256 or SHA-3.

At Teldat we work hard and invest resources in order to implement and use the most secure protocols, because for Teldat, as it should be for everyone, security is an extremely important issue.