The SLOTH attacks: why laziness about cryptography puts security at risk

The big “cryptographic cracking” story so far in 2016 is SLOTH, which is not only interesting and important, but also a VUWACONA, making it eye-catching as well.

VUWACONA is short for Vulnerability With A Cool Name, our new acronym for bugs like LOGJAM, FREAK and Poodle.

Like those three previous security problems, SLOTH is the result of modern cryptographic protocols continuing to use superannuated cryptographic algorithms, and needlessly being less trustworthy as a result.

Indeed, the name is both an acronym, short for Security Losses from Obsolete and Truncated Transcript Hashes, and a metaphor.

In the words of the authors of the paper, SLOTH is “a not-so-subtle reference to laziness in the protocol design community with regard to removing legacy cryptographic constructions.”

The SLOTH paper is fairly technical, and relies on quite a lot of cryptographic jargon, making it hard to penetrate if you aren’t a cryptographer already.

Here, we’ll just give a general overview of the problems that were exploited by the SLOTH authors, and what that tells us about our attitudes to cryptography in particular, and security in general.

Why have secure protocols?

Secure internet protocols such as TLS, previously known as SSL, are designed to provide encryption (keep your conversation secret), authentication (know you are talking to the right person) and integrity (be sure that you are reading exactly what the other guy sent).

Secure HTTPS web pages that were protected only by encryption would give you a dreadfully false sense of security when doing online banking: there’s no point in being on a strongly-encrypted internet connection if you’re talking to a crook at the other end.

Authentication over the internet is usually achieved using what are known as digital signatures, based on public-key cryptography, for example using the RSA algorithm.

The other end “locks”, or signs, a message in such a way that when you try to “unlock” it to validate its signature, the unlocking process will fail unless it really was locked by the person you expected.

But using RSA for unlocking and locking is problematic, because the RSA algorithm is very slow, and is usually used only to encrypt very short messages.

Enter the hash

Instead of working on the entire message, which might be a detailed and quite lengthy exchange of cryptographic parameters, cryptographic protocols usually create a cryptographic checksum, or hash, of the message, and sign the hash instead.

Hashing algorithms such as MD5, SHA-1, SHA-256 and SHA-3 produce a fixed-length output that acts as a sort of “digital fingerprint”, so whether your message is one character or 1GB in size, you know in advance how big the hash will be, and can plan, and program, accordingly.

In other words, the authentication process depends on the hash being a reliable placeholder for the message.

If you can fake the hash, you have effectively faked the whole message.

Generally speaking, then, hash functions are judged by how well they mix up their input data to produce the final output, which is usually a lot shorter than the input.

In particular, a hash, denoted here as a mathematical function H(), should have at least these characteristics:

1. If you deliberately create two messages M1 and M2 (any two messages; you get to choose both of them) such that H(M1) = H(M2), you have a collision, which undermines the value of H as a digital fingerprint. Therefore you should not be able to construct a collision, other than by trying over and over with different inputs until you hit the jackpot by chance.
2. If you know that H(M) = X, but you don’t know my message M, then you should not be able to “go backwards” from X to M, other than by trying different messages over and over until you hit the jackpot by chance.
3. If I choose M and tell you what it is, so you can compute H(M) = X for yourself, you should not be able to come up with a different message M’ that also has H(M’) = X, other than by guesswork. (This is much tougher than case 1 because you don’t get to choose any matching pair of hashes from a giant pool of messages. You have to match my hash, not any hash, which squares the effort needed.)

As you can imagine, if a hash function is found to have poor collision resistance (weakness 1 above), then it is prudent to assume that the function is generally flawed, and simply doesn’t mix-and-mince-and-shred-and-liquidise its input well enough to be safe against the other weaknesses, either.

But weaknesses of type 1 are generally much easier to find than the other sorts, and even for a hash function where tricks already exist to produce collisions at will, there may not yet be any practical way of pulling off the other two tricks, which are known in the literature as pre-image resistance.

We are at already that point with MD5.

And we are close to it with SHA-1, at least for attackers with lots of money or computers, so those two algorithms are now banned from many uses, such as signing digital certificates.

She’ll be right…

However, it’s easy to fall into the trap of saying, “Well, if we’re careful, we can still get away with using MD5 and SHA-1, provided that we use them only when an attacker would have to use weakness 3, and provided that we only use it to authenticate short-term data, for example when setting up each connection.”

If you will pardon the analogy, that’s a bit like borrowing a car where the steering has been so badly maintained that it pulls to the left unpredictably, and then driving it anyway.

You could assume that the shoddy steering tells no story at all about how well the rest of vehicle has been cared for; that the brakes are probably OK; and that as long as you keep the speed down, and remember to aim a bit to the right of where you want to go, you’ll be fine…

SLOTH proves a point

The SLOTH authors, and many other cryptographers, begged to differ with those who took the “she’ll be right” approach and were therefore continuing to use MD5 and SHA-1 selectively.

Until now, however, they couldn’t prove that MD5 and SHA-1 were too weak for all uses just because they could be exploited for some sorts of attack.

But all that has changed, because the SLOTH paper shows a number of weak-hash-based attack techniques against TLS that are already either practical, or dangerously close to it.

They also show similar attacks against SSH and IKE that, if not yet practicable, are nevertheless worryingly far from the security that the mathematics claims you should enjoy.

Don’t worry if this table doesn’t make a lot of sense to you, but the deal is that the column labelled “Preimage Cost” gives the number of hash calculations you would need to do in order to guarantee a successful attack by chance, while the “Work/connection” column shows the number of calculations needed to pull off an attack using the SLOTH techniques:

To be sure, cracking SSH sessions by doing 2⁷⁷ calculations in real time per connection is nowhere near practical, at least today, so it’s tempting to say, “So why not keep on using SHA-1 in this context, at least for a bit?”

On the other hand, the “Security loss” column tells you the SLOTH attacks prove that the security you get by allowing SHA-1 in SSH2 key exchanges is a whopping 2⁸³ times weaker than it’s supposed to be.

The SLOTH attacks aren’t easy, some of them would be very expensive, and many of them are still currently impossible…

…but, as the saying goes, attacks only ever get faster.

What to do?

Don’t use MD5 and SHA-1. It’s that easy!

Their steering pulls to the left, and that simply isn’t good enough.

Baby sloth courtesy of Shutterstock.