\n

\n

Research by: Ben Herzog

\n

Introduction

\n

When some people hear “Cryptography”, they think of their Wifi password, of the little green lock icon next to the address of their favorite website, and of the difficulty they’d face trying to snoop in other people’s email. Others may recall the litany of vulnerabilities of recent years that boasted a pithy acronym (DROWN, FREAK, POODLE…), a stylish logo and an urgent warning to update their web browser.

\n

Cryptography is all these things, but it’s not about these things. It’s about the thin line between easy and difficult. Some things are easy to do, but difficult to undo: for instance, breaking an egg. Other things are easy to do, but difficult to do when a small, crucial piece is missing: for instance, unlocking your front door, with the crucial piece being the key. Cryptography studies these situations and the ways they can be used to obtain guarantees.

\n

Over the years, the landscape of cryptographic attacks has become a kudzu plant of flashy logos, formula-dense whitepapers and a general gloomy feeling that everything is broken. But in truth, many of the attacks revolve around the same few unifying principles, and many of the interminable pages of formulas have a bottom line that doesn’t require a PhD to understand.

\n

In this article series, we’ll consider various types of cryptographic attacks, with a focus on the attacks’ underlying principles. In broad strokes, and not exactly in that order, we’ll cover:

\n\n

This specific article covers the above material up until Kelsey’s attack.

\n

Basic Attack Strategies

\n

The following attacks are simple, in the sense that they can be explained without many technical details, and without much of the substance being lost. We’ll explain each type of attack in the simplest terms possible, without delving into complicated examples or advanced use cases.

\n

Some of these attacks have mostly lost their relevance, and have not seen a successful mainstream application for many years. Others are perennials — they still routinely sneak up on unsuspecting cryptosystem designers in the 21st century. The modern era of cryptography can be considered to have begun with IBM’s DES, the first cipher to withstand every attack on this list.

\n

Simple Brute-Force Attack

\n

\"\"An encryption scheme is made up of two parts: an encryption function, which takes a message (plaintext) in conjunction with a key, then produces an encrypted message (ciphertext); and a decryption function, which takes a ciphertext and a key, and produces a plaintext. Both encryption and decryption should be easy to compute, given the key – and difficult otherwise.

\n

So, suppose we are looking at a ciphertext, and attempting to decrypt it without any additional information (this is called a “ciphertext only” attack). If we were somehow magically handed the correct encryption key, we would be able to easily verify that it is indeed the correct key: we’d decrypt the ciphertext using the proposed key, and then check whether the result is a reasonable message.

\n

Note that we’ve made two implicit assumptions here. First, we assume that we know how to perform the decryption – that is, that we know how the cryptosystem works. This is a standard assumption when discussing cryptography. Hiding the cipher implementation details from attackers might seem to confer extra security, but once the attackers figure out these details, this extra security will be silently and irreversibly lost. That’s Kerckhoffs’ principle: “The enemy knows the system.”

\n

Second, we assume that the correct key is the only key that will result in a reasonable decryption. That is also a reasonable assumption; it holds if the ciphertext is fairly long relatively to the key, and fairly legible. Generally, this is true in the real world, barring the use of a huge and impractical key or other shenanigans we had best leave out of this article. (If the reader is unsatisfied with this hand-waving, please refer to theorem 3.8 here).

\n

Given the above, a strategy emerges: iterate over every single key, and verify whether it is the correct key or not. This is called a brute-force attack, and it is guaranteed to work against all practical ciphers — eventually. For instance, a brute-force attack was powerful enough to defeat the shift cipher, an early cipher for which the key was a single letter out of the alphabet, which implies only twenty-something possible keys.

\n

Unfortunately for cryptanalysts, a mitigation quickly presents itself: increasing the key size. As the size of the key grows, the number of possible keys increases exponentially. With modern key sizes, the naked brute-force attack is completely impractical. To understand what we mean by that, consider that the fastest known supercomputer as of mid-2019, IBM’s summit, has a peak speed on the order of \\( 10^{17} \\) operations per second, whereas a typical modern key length is 128 bits which translates to \\( 2^{128} \\) possible keys. Plugging in the numbers, if Summit were instructed to brute-force a modern key, the feat would require over 5,000 times the age of the universe.

\n

Is the brute-force attack a historical curiosity? Far from it; it is a necessary ingredient in the cryptanalytic cookbook. Very few ciphers are so catastrophically weak that a clever attack completely breaks them, without requiring some elbow grease. Many successful breaks make use of a clever attack to weaken the targeted cipher, and then deliver a brute-force as the coup de grâce.

\n

Frequency Analysis

\n

\"\"Most texts are not gibberish. For instance, in English messages, you see a lot of the letter e, and a lot of the word the; in binary files, you see a lot of zero bytes, put there as filler between one chunk of information and the next. A frequency analysis is any attack that takes advantage of this fact.

\n

The canonical example of a cipher vulnerable to this attack is the simple substitution cipher. In this cipher, the key is a table that, for each letter in the English alphabet, designates a letter to replace it with. For instance, g can be replaced with h, and o with j, so the word go becomes hj. This cipher resists a simple brute-force attack, as there are very many possible substitution tables (if you’re interested in the math, the effective key length is about 88 bits — that’s \\(\\text{log}_2(26!)\\)). But a frequency analysis typically makes short work of this cipher.

\n

For example, consider the following ciphertext, encrypted with a simple substitution:

\n
XDYLY ALY UGLY XDWNKE WN DYAJYN ANF YALXD DGLAXWG XDAN ALY FLYAUX GR WN OGQL ZDWBGEGZDO
\n

As Y appears frequently and at the end many words, we can tentatively guess that its plaintext counterpart is the letter e:

\n
XDeLe ALe UGLe XDWNKE WN DeAJeN ANF eALXD DGLAXWG XDAN ALe FLeAUX GR WN OGQL ZDWBGEGZDO
\n

The pair XD repeats at the beginning of several words, and in particular the term XDeLe is strongly suggestive of a word such as these or there, and so we proceed:

\n
theLe ALe UGLe thWNKE WN heAJeN ANF eALth DGLAtWG thAN ALe FLeAUt GR WN OGQL ZDWBGEGZDO
\n

Next, we’ll guess that L translates to r, A to a, and so on. Some trial-and-error will probably be involved, but compared to a full brute-force attack, this attack recovers the original plaintext in no time at all:

\n
there are more things in heaven and earth horatio than are dreamt of in your philosophy
\n

For some people, solving “cryptograms” such as the one above is a hobby.

\n

The basic idea behind frequency analysis is more powerful than it appears at first sight, and is applicable to much more complex ciphers than the simple substitution above. Various cipher designs throughout history tried to counter the attack above via “polyalphabetic substitution” —   that is, changing the letter substitution table mid-encryption in complex but predictable ways that depend on the key. These ciphers were all considered difficult to break in their time; and yet the humble frequency analysis attack eventually caught up with every single one.

\n

The most ambitious polyalphabetic substitution cipher in history, and probably the most famous, was the Enigma cipher used in World War II. Its design was complex compared to those that came before it, but after much hand-wringing and toil, British cryptanalysts were able to break it using frequency analysis. Granted, they couldn’t mount an elegant ciphertext-only attack such as the one used to defeat the simple substitution above; they had to resort to comparing known pairs of plaintext-ciphertext (called a “known plaintext attack”) and even to baiting Enigma users into encrypting specific messages, and observing the result (a “chosen plaintext attack”). But this distinction was of little comfort to their enemies’ defeated armies and sunk submarines.

\n

From that high point in its history, frequency analysis just kind of faded away. Modern ciphers, inspired by the needs of the information age, were designed to operate with individual bits, not letters. More importantly, these ciphers were designed with a somber understanding of what later came to be known as Schneier’s Law: anyone can create an encryption algorithm that they themselves can’t break. It’s not enough for the cipher machinery to appear complex — to prove its worth, it must resist a ruthless security review by many cryptanalysts doing their best to break the cipher.

\n

Precomputation Attack

\n

\"\"Consider the hypothetical city of Precom Heights, population 200,000. An apartment in Precom contains about $30,000 worth of valuables on average, and no more than $50,000.  The security market in Precom is monopolized by ACME Industries, which produces the fabled Coyote Class(tm) door locks. According to expert analysis, the only thing that can break a Coyote Class lock is a “meeper” — a very complex hypothetical machine that would require an investment of about 5 years and $50,000 to construct. Is the city secure?

\n

Probably not. Eventually an ambitious enough criminal will come along. They’ll reason thus: “Yes, I’m eating a large up-front cost. Five years of waiting patiently, and $50,000 spent on top of that. But when the work is done, I’ll have access to the entire fortune of this city. If I play my cards right, this investment will pay for itself many times over.”

\n

A similar dynamic applies in cryptography. Attacks against a specific cipher are subject to a ruthless cost-benefit analysis; if the analysis is not favorable, the attack won’t happen. But attacks that apply to many potential victims almost always pay off, and if they do, the best design practice is to assume them to be going on from day one. We basically have a Murphy’s Law of Cryptography: “Anything that feasibly could break the system, will break the system.”

\n

The simplest example of a cryptosystem vulnerable to a precomputation attack is one where the encryption algorithm is constant, and no key is used. This was the case with the Caesar Cipher, which simply shifted each letter of the alphabet 3 letters ahead (looping around, so the last letter in the alphabet was encrypted as the third). Kerckhoffs’ principle rears its head again; once the system is broken, it is broken forever.

\n

Precomputation attacks are a simple concept. Even the most amateur cryptosystem designer is likely to see them coming, and prepare accordingly. As a result, if you look at the timeline of the evolution of cryptography, precomputation attacks were irrelevant through most of it — starting with the first improvements on the Caesar cipher, all the way up to the decline of polyalphabetic ciphers. These attacks only saw a comeback after the rise of the modern era of cryptography.

\n

This comeback was fueled by two factors. First, cryptosystems finally emerged that were complex enough to contain “break once, use later” opportunities that weren’t obvious. Second, cryptography reached such wide use that millions of laymen were making decisions every day about what pieces of cryptography to reuse, and where. It was a while until experts realized the resulting risks, and raised the alarm.

\n

Keep precomputation attacks in mind; by the end of this article, we’ll see two separate real-life cryptographic breaches where this type of attack played an important part.

\n

Interpolation Attack

\n

Here is the famous detective, Sherlock Holmes, performing an interpolation attack on the hapless Dr. Watson:

\n

I knew you came from Afghanistan. [..] The train of reasoning ran, ‘Here is a gentleman of the medical type, but with the air of a military man. Clearly an army doctor, then. He has just come from the tropics, for his face is dark, and that is not the natural tint of his skin, for his wrists are fair. He has undergone hardship and sickness, as his haggard face says clearly. His left arm has been injured: He holds it in a stiff and unnatural manner. Where in the tropics could an English army doctor have seen much hardship and got his arm wounded? Clearly in Afghanistan.’ The whole train of thought did not occupy a second. I then remarked that you came from Afghanistan, and you were astonished.

\n

Holmes could extract very little information from any of the clues individually; he was only able to come to his conclusion by considering them all together. Similarly, an interpolation attack works by examining known pairs of plaintext and ciphertext, all derived from the same key; and from each pair, making a broad deduction about the key. The deductions are all vague and apparently useless, until suddenly they reach a critical mass and lead to a single conclusion that, however improbable, must be the truth. The key is revealed, or else the process of decryption is understood so thoroughly that it can be replicated.

\n

We’ll illustrate the way the attack works with a simple example. Suppose that we are attempting to read the private journal of our frenemy, Bob. Bob encrypts every number in his journal with a simple cryptosystem he’s read about in a blurb in Mock Crypto Magazine. The system works as follows: Bob picks two numbers close to his heart \\(M\\) and \\(N\\). From then on, to encrypt any number \\(x\\), he computes \\(Mx+N\\). For example, if Bob picked \\(M=3\\) and \\(N=4\\), then under encryption, \\(2\\) would become \\(3*2+4 = 10\\).

\n

Suppose on December 27, we witness Bob writing in his journal. When Bob is done, we discreetly pick up the journal and examine the latest entry:

\n

Date: 235/520
\nDear Diary,
\nToday was a good day. In 64 days I have a date with Alice, who lives down at number 843. I really think she could be the 26!

\n

Since we are really anxious to stalk Bob during his date (in this scenario we are 15 years old), we are interested in finding out the day of Bob’s date, as well as Alice’s address. Happily, we notice that the cryptosystem Bob is using is vulnerable to an interpolation attack. We may not know \\(M\\) and \\(N\\), but we do know the date today, and therefore we have two plaintext-ciphertext pairs. To wit, we know that \\(12\\) encrypted is \\(235\\), and furthermore, that \\(27\\) encrypted is \\(520\\). We can therefore write:

\n

$$M*12+N = 235$$ $$M*27+N = 520$$

\n

Now, since we are 15 years old we also know that this is what’s called “2 equations with 2 unknowns”, and that in this situation, it is possible to solve for \\(M\\) and \\(N\\) without too much trouble. Each plaintext-ciphertext pair created a constraint on Bob’s key, and the combined 2 constraints were enough to recover the key completely. In the example above, the solution is \\(M=19\\) and \\(N=7\\).

\n

Interpolation attacks are, of course, not limited to such simple examples. Every cryptosystem that boils down to a well-understood mathematical object and a list of parameters is at risk of an interpolation attack — the better understood the object, the higher the risk.

\n

People studying cryptography have been known to complain about it being “the art of designing things to be as ugly as possible”, and interpolation attacks probably carry much of the blame for this. Bob can either have a cryptosystem with mathematically elegant design, or he can have privacy on his date with Alice — but alas, he typically cannot have both. This will become startlingly clear when we eventually get to the subject of public-key cryptography.

\n

Cross Protocol / Downgrade Attack

\n

\"\"In the 2013 film Now You See Me, an entourage of stage magicians called the “Horsemen” endeavor to swindle corrupt insurance mogul Arthur Tressler out of his entire fortune. To access Arthur’s bank account, the Horsemen have to either present his username and password, or have him show up at the bank in person and cooperate with their scheme.

\n

Both of these are very difficult feats; the Horsemen are stage magicians, not the Mossad. So, instead, they target a third possible protocol — they have an accomplice call the bank and pretend to be Arthur. The bank asks for several personal details to verify Arthur’s identity, such as his Uncle’s name and his first pet’s name; the Horsemen extract this information from Arthur in advance easily, via deft social engineering. At that point, the excellent security of the password does not matter any more.

\n

(According to an urban legend that we have verified independently, cryptographer Eli Biham was once confronted by a bank teller who insisted on installing password recovery questions of this type. When the teller asked Biham for the latter’s maternal grandmother’s name, Biham started reading out: “Capital X, small y, three, …”)

\n

Similarly to the above, it sometimes happens that two cryptographic protocols are employed side-by-side to secure the same asset, while one protocol is much weaker than the other. The resulting setup is then vulnerable to a cross-protocol attack, where features in the weaker protocol are abused in order to compromise the stronger protocol.

\n

In some more complicated cases, the attack can’t succeed just by contacting a server with the weaker protocol, and requires the unwitting participation of a legitimate client. This can still be arranged using something called a downgrade attack. To understand how such an attack works, suppose the Horsemen were dealing with a more difficult challenge than the one in the movie; specifically, suppose the Bank teller and Arthur had some contingencies in place, resulting in this dialogue:

\n

ATTACKER: Hello? This is Arthur Tressler. I would like to recover my password.

\n

TELLER: Excellent. Please look at your personally issued secret code book, page 28, word 3. All the following communication will be encrypted with this specific word as the key. PQJGH. LOTJNAM PGGY MXVRL ZZLQ SRIU HHNMLPPPV

\n

ATTACKER: Wait, wait, wait. Is this really necessary? Can’t we just speak to each other like normal human beings?

\n

TELLER: I advise against it.

\n

ATTACKER: I’m just — listen, I’ve had a lousy day, okay? I’m a paying customer, and I am not in the mood for fancy complicated code books.

\n

TELLER: Fine. If you insist, Mr. Tressler. What is your request?

\n

ATTACKER: I would like to please transfer all my money to the Victims of Arthur Tressler National Fund.

\n

(There is a pause.)

\n

TELLER: I see. Please provide your large transaction PIN code.

\n

ATTACKER: My what now?

\n

TELLER: Per your personal request, transactions of this magnitude require that you provide your large transaction PIN code. This code was issued to you when you first opened your account.

\n

ATTACKER: …I’ve lost the code. Is this really necessary? Can’t you just approve the transaction?

\n

TELLER: No. Apologies, Mr. Tressler. Again, this is a security measure you requested. We can issue you a new PIN, sent to your PO box, if you’d like.

\n

The Horsemen ponder the challenge for a long while. They listen in on several of Tressler’s big transactions, hoping to hear the PIN; but every time, the conversation turns into encrypted gibberish before they can hear anything interesting. Finally, one day, they put a plan in motion. They patiently wait until Tressler has to make a large transaction by phone, tap into the line, and then…

\n

TRESSLER: Hello. I would like to issue a remote transaction, please.

\n

TELLER: Excellent. Please look at your personally issued secret code book, page –

\n

(The ATTACKER presses a button; the TELLER’s voice turns into indecipherable noise.)

\n

TELLER: #@$#@$#&#*@$$@#* will be encrypted with this word as the key. AAAYRR PLRQRZ MMNJK LOJBAN

\n

TRESSLER: Sorry, I didn’t quite catch that. Come again? What page? What word?

\n

TELLER: It’s page @#$@#*$)#*#@()#@$(#@*$(#@*.

\n

TRESSLER: What?

\n

TELLER: Word number twenty @$#@$#%#$.

\n

TRESSLER: Seriously! Come off it! You and your security protocol are a blight. I KNOW you can just normally talk to me.

\n

TELLER: I advise against —

\n

TRESSLER: I advise you stop wasting my time. I don’t want to hear any more of it until you fix your phone line issues. Can we do this transaction or not?

\n

TELLER: …yes. Fine. What is your request?

\n

TRESSLER: I would like to transfer $20,000 to Lord Business Investments, account number –

\n

TELLER: A moment please. That is a large transaction. Please provide your large transaction PIN.

\n

TRESSLER: What? Oh, right. It is 1234.

\n

And that’s a downgrade attack. The weaker protocol, “just speak plainly”, was supposed to be an optional addition to be used as a last resort. And yet, here we are.

\n

You might wonder who in their right mind would design a real-world system analogous to a “secure, unless you come in sideways” system, or a “secure, unless you insist otherwise” system, as described above. But much like the fictional bank would rather take the risk and retain its crypto-averse customers, systems in general often bow to requirements that are indifferent, or even overtly hostile, to security needs.

\n

Exactly such a story surrounded the release of SSL protocol version 2 in the year 1995. The United States government had long since come to view cryptography as a weapon, best left out of the hands of geopolitical enemies and domestic threats. Pieces of code were approved on a case-by-case basis for leaving the US, often conditional on the algorithm being weakened deliberately. Netscape, then the main vendor of web browsers, was able to obtain a permit for SSLv2 (and by extension, Netscape Navigator) to support a vulnerable-by-design RSA with a key length of 512 bits (and similarly 40 bits for RC4).

\n

By the turn of the millennium, regulations had been relaxed and access to state-of-the-art encryption became widely available. Still, clients and servers supported export-grade crypto for years, due to the same inertia that preserves support for any legacy system. Clients figured they might encounter a server which doesn’t support anything else, so they hung on to optional support for it, as a last resort. Servers did the same. Of course, SSL protocol dictates that clients and servers should never use a weak protocol when a better one is available — but then again, neither should Tressler and his bank.

\n

The theory we have discussed so far came to a head in two consecutive high-profile attacks that rattled the security of SSL protocol in 2015, each discovered by researchers at Microsoft and INRIA. First was the FREAK attack, announced in February of that year; three months later it was followed by another similar attack called Logjam, which we’ll discuss in more detail when we get to attacks on public-key cryptography.

\n

\"\"The FREAK attack (also “Smack TLS”) resulted when the research team analyzed TLS client/server implementations and found a curious bug. In these implementations, if the client never asks to use export-grade weak cryptography, but the server responds with such keys anyway — the client says “oh well” and complies, carrying out the entire conversation using the weak cipher suite.

\n

At the time, public perception on export-grade cryptography held that deprecated equals irrelevant; the attack came as quite a shock, and affected many high-profile domains — including some belonging to the White House, the IRS and the NSA. Worse, it turned out that many vulnerable servers had a performance optimization where the same keys were used over and over, instead of new keys being generated for each session. This allowed a precomputation attack on top of the downgrade attack: breaking a single key was still somewhat costly ($100 and 12 hours at the time of the publication), but the practical cost of the attack per connection was drastically lower. The key could be broken once, and then the break used for every connection made by the server from that point on.

\n

And one advanced attack we need to know before we go any further…

\n

Oracle Attack

\n

\"\"Moxie Marlinspike may be best known as the father of the cross-platform encrypted messaging service, Signal; but personally, we are fond of one of his lesser-known innovations — the cryptographic doom principle. Slightly paraphrased, it states: “If a protocol performs any cryptographic operation on a message with a possibly malicious origin, and behaves differently based on the result, this will inevitably lead to doom.” Or, put more abruptly — “Don’t chew on enemy input, and if you must, at least don’t spit any of it back out.”

\n

Never mind the buffer overflows, command injections and the like; they’re beyond the scope of this discussion. Violating the doom principle leads to fair and square cryptographic breaks, which result from the protocol behaving exactly like it was supposed to.

\n

To demonstrate how, we’ll present a toy setup — based on a simple substitution cipher — which violates the doom principle; and then demonstrate an attack made possible by the violation. While we’ve already seen an attack on the simple substitution cipher based on frequency analysis, this isn’t merely “another way to break the same cipher.” To the contrary: oracle attacks are a much more modern invention, applicable to plenty of situations where frequency analysis will fail, and we’ll see a demonstration of this in the next section. This simpler cipher was picked just to make the exposition smoother.

\n

On with the example. Alice and Bob communicate using a simple substitution cipher, using a key known only to them. They are very strict with message lengths, and only willing to deal with messages that are exactly 20 characters long. Therefore, they’ve agreed that if someone wants to send a shorter message, they have to append some dummy text to the end of the message to get it to be exactly 20 characters. After some discussion, they’ve decided they will only accept the following dummy texts: a, bb, ccc, dddd, and so forth and so on. That way, there is an available dummy text of every possible required length.

\n

When Alice or Bob receive a message, after decrypting it, they first check that the plaintext is the proper length (20 characters), and the suffix is a proper dummy text. If it isn’t, they reply with an appropriate error message. If the text length and dummy text are both OK, the recipient reads the message itself and sends an encrypted reply.

\n

The attack proceeds by impersonating Bob, and sending forged messages to Alice. The messages are complete nonsense — the attacker does not have the key, and so cannot forge a meaningful message. But since the protocol violates the doom principle, the attacker can still bait Alice into disclosing information about the key, as follows.

\n

ATTACKER: PREWF ZHJKL MMMN. LA

\n

ALICE: Incorrect dummy text.

\n

ATTACKER: PREWF ZHJKL MMMN. LB

\n

ALICE: Incorrect dummy text.

\n

ATTACKER: PREWF ZHJKL MMMN. LC

\n

ALICE: ILCT? TLCT RUWO PUT KCAW CPS OWPOW!

\n

(The attacker has no idea what Alice just said, but notes that C must map to a, since Alice accepted the dummy text.)

\n

ATTACKER: REWF ZHJKL MMMN. LAA

\n

ALICE: Incorrect dummy text.

\n

ATTACKER: REWF ZHJKL MMMN. LBB

\n

ALICE: Incorrect dummy text.

\n

(Some trials later…)

\n

ATTACKER: REWF ZHJKL MMMN. LGG

\n

ALICE: Incorrect dummy text.

\n

ATTACKER: REWF ZHJKL MMMN. LHH

\n

ALICE: TLQO JWCRO FQAW SUY LCR C OWQXYJW. IW PWWR TU TCFA CHUYT TLQO JWFCTQUPOLQZ.

\n

(The attacker, again, has no idea what Alice just said, but notes that H must map to b, since Alice accepted the dummy text.)

\n

And so on, until the attacker knows the plaintext counterpart of every letter.

\n

This may appear superficially similar to a chosen ciphertext attack. After all, the attacker gets to choose ciphertexts and the server dutifully processes them. The major difference, which makes attacks like these viable in the real world, is that the attacker does not require access to the actual decryption — the server’s response is enough, even something as innocuous as “incorrect dummy text.”

\n

While it’s instructive to understand how this specific attack took place, one shouldn’t get too hung up on the specifics of the “dummy text” scheme, the specific cryptosystem used, or the exact sequence of messages sent by the attacker. The main idea here is how Alice reacts differently based on properties of the plaintext, and does so without verifying that the corresponding ciphertext really originated with a trusted party. By doing so, Alice makes it possible for an attacker to squeeze secret information out of her responses.

\n

We could change many things about the scenario, such as the plaintext property that triggers the difference in Alice’s behavior, or the difference in behavior itself, or even the cryptosystem used — but the principle would remain the same, and the attack would generally remain viable, in one form or another. This dawning realization was responsible for the discovery of several security bugs, which we’ll delve into in a moment; but before that could happen, some theoretical seeds had to be planted. How do we take this toy “Alice Scenario” and mold it into an attack that can work on an actual modern cipher? Is that possible at all, even in theory?

\n

In 1998, Swiss cryptographer Daniel Bleichenbacher answered that question in the positive. He demonstrated an oracle attack against the widely-used public-key cryptosystem, RSA, when used with a certain message scheme. In some RSA implementations, the server replied with a different error message, depending on whether the plaintext matched the scheme or not; this was enough to enable the attack.

\n

Four years later, in 2002, French cryptographer Serge Vaudenay demonstrated an oracle attack almost identical to the one in the Alice scenario above — except instead of a toy cipher, he broke a whole respectable class of modern ciphers that people actually use. Specifically, Vaudenay’s attack targeted ciphers with a fixed input size (“block ciphers”) when used in a specific way called the “CBC mode of operation” and with a certain popular padding scheme basically equivalent to the one in the Alice scenario.

\n

Also in 2002, American cryptographer John Kelsey — co-author of Twofish — proposed a variety of oracle attacks on systems that compress messages and then encrypt them. The most notable among those was an attack that took advantage of the fact that it is often possible to tell the original plaintext length from the ciphertext length. This, in theory, enabled an oracle attack that recovers portions of the original plaintext.

\n

We follow with a more detailed exposition of Vaudenay’s and Kelsey’s attacks (we’ll give a more detailed exposition of Bleichenbacher’s attack when we get to attacks on public-key cryptography). The text gets somewhat technical, despite the best of our efforts; so if the above is enough detail for you, skip down past the following two sections.

\n

Vaudenay’s Attack

\n

To understand Vaudenay’s attack, we first need to talk about block ciphers and modes of operation in a little bit more detail. A “block cipher” is, as mentioned, a cipher which takes a key and input of a certain fixed length (the “block length”), and outputs an encrypted block of the same length. Block ciphers are widely used and are considered relatively secure. The now-retired DES, widely considered the first modern cipher, was a block cipher; as mentioned above, the same is true for AES, which is in extensive use today.

\n

Unfortunately, block ciphers have one glaring weakness. The typical block size is 128 bits, or 16 characters. Obviously modern uses of cryptography require that we work with inputs longer than that, and this is where modes of operation come in. A mode of operation is basically a hack — an algorithm for taking a block cipher, which can only take a fixed amount of input, and somehow applying it to inputs of arbitrary lengths.

\n

Vaudenay’s attack targets a popular mode of operation, called CBC (Cipher Block Chaining). The attack treats the underlying block cipher as a magical unassailable black box, and bypasses its security entirely.

\n

Here is a diagram that illustrates how CBC mode operates:

\n

\"\"

\n

\"\"

\n

The circled plus signs stand for XOR operations. So, for example, the second ciphertext block is obtained by:

\n
    \n
  1. XORing the second plaintext block with the first ciphertext block.
  2. \n
  3. Encrypting the resulting block with the block cipher, using the key.
  4. \n
\n

As CBC makes such heavy use of the XOR operation, let us take a moment to recall its following useful properties.

\n\n

These properties imply, as a rule of thumb, that if we have an equation involving XORs and one unknown, it’s possible to solve for the unknown. For example, if we know that \\(A \\oplus X = B\\) with \\(X\\) the unknown and \\(A\\), \\(B\\)  known, we can rely on the properties above to solve for \\(X\\). XORing both sides of the equation with \\(A\\), we obtain \\(X = A \\oplus B\\). This will all become very relevant in a moment.

\n

There are two minor differences, and one major difference, between the Alice scenario we saw in the last section and Vaudenay’s attack. The two minor differences are:

\n\n

The one major difference is:

\n\n

This last difference is the final piece missing to understand Vaudenay’s attack, so let’s take a moment to think about why and how it should be possible to mount an oracle attack on CBC at all.

\n

Suppose we are given a CBC ciphertext composed of (let’s say) 247 blocks, and we want to decrypt it. We can send forged messages to the server, just as earlier we were able to send forged messages to Alice. The server will decrypt messages for us, but will not provide us with the decryption — instead, again like with  Alice, the server will tell us whether the resulting plaintext has valid padding or not.

\n

Consider that in the Alice scenario, we had the following relationship: $$\\text{SIMPLE_SUBSTITUTION}(\\text{ciphertext},\\text{key}) = \\text{plaintext}$$

\n

Let’s call this the “Alice equation.” We controlled the ciphertext; the server (Alice) leaked vague information about the resulting plaintext; and this allowed us to deduce information about the remaining term — the key. By analogy, it stands to reason that if we can find a similar relationship for the CBC scenario, we might be able to extract some secret information there, too.

\n

Happily, a relationship does exist for us to exploit. Consider the output of the final invocation of the “block cipher decryption” box, and denote that output \\(W\\). Also denote plaintext blocks \\(P_1, P_2, \\ldots\\), and ciphertext blocks \\(C_1, C_2, \\ldots\\). Take a look again at the CBC diagram, and note that we have: $$C_{246} \\oplus W = P_{247}$$

\n

Let’s call this the “CBC equation.”

\n

In the Alice scenario, by controlling the ciphertext and watching Alice leak information about the corresponding plaintext, we were able to mount an attack that recovered the third term in the equation — the key. In the CBC scenario, we also control the ciphertext and observe information leaks regarding the corresponding plaintext. If the analogy carries, we should be able to gain information about \\(W\\).

\n

Suppose we do recover \\(W\\); what then? Well, we can then immediately deduce the entire last block of plaintext (\\(P_{247}\\)) simply by plugging in \\(C_{246}\\) (which we have) and \\(W\\) (which we would also have) into the CBC equation.

\n

So, we have an optimistic intuition about a general outline for an attack, and it’s time to work out the details. We turn our attention to the exact manner in which the server leaks information about the plaintext. In the Alice scenario, the leak resulted from Alice responding with a proper message if and only if \\(\\text{SIMPLE_SUBSTITUTION}(\\text{ciphertext},\\text{key})\\) ended in the string a (or bb, et cetera, but the chances of randomly triggering these conditions were very small). Similarly with CBC, the server accepts the padding if and only if \\(C_{246} \\oplus W\\) ends in hexadecimal 01. So let’s try the same trick — sending forged ciphertexts, with our own forged values of \\(C_{246}\\), until the server accepts the padding.

\n

When the server does accept the padding for one of our forged messages, this implies that: $$C_{246} \\oplus W = \\text{something ending in hex 01}$$

\n

We now use the bytewise property of XOR: $$(\\text{final byte of } C_{246}) \\oplus (\\text{final byte of }W) = \\text{hex 01}$$

\n

We know both the first and third term, and we have already seen that this allows us to recover the remaining term – the final byte of \\(W\\): $$ (\\text{Final byte of } W) = (\\text{Final byte of } C_{246}) \\oplus (\\text{hex 01})$$
\nThis also gives us the final byte of the final plaintext block via the CBC equation and the bytewise property.

\n

We might call the attack off now and be content that we’ve succeeded in doing something that should be impossible. But actually, we can do much better: we can recover the entire plaintext. This does require a certain trick that did not appear in the original Alice scenario and is not a necessary feature of oracle attacks — but the method is worthwhile to understand all the same.

\n

To see how this larger feat might be accomplished, first note that by deducing the correct value of the last byte of \\(W\\), we have also gained a new ability. From now on, when we forge ciphertexts, we can control the last byte of the corresponding plaintext. This is, again, due to the CBC equation and the bytewise property: $$(\\text{final byte of } C_{246}) \\oplus (\\text{final byte of } W) = \\text{Final byte of } P_{247}$$

\n

Since we now know the second term, we can use our control of the first term to control the third. We just compute: $$ (\\text{Final byte of forged } C_{246}) = (\\text{Desired final byte of } P_{247}) \\oplus (\\text{Final byte of } W)$$

\n

Earlier we couldn’t do this, because we didn’t yet have the final byte of \\(W\\).

\n

How does this help us? Suppose we now rig all our future ciphertexts so that in the corresponding plaintexts, the final byte is 02. The server will now only accept the padding if the plaintext ends with 02 02. As we fixed the last byte, this will only happen if the second-to-last plaintext byte is also 02. We keep sending forged ciphertext blocks, varying the second-to-last byte, until the server accepts the padding for one of them. At that point we have: $$(\\text{Second-to-final byte of forged } C_{246}) \\oplus (\\text{Second-to-final byte of } W) = \\text{hex 02}$$

\n

And we recover the second-to-final byte of \\(W\\) in exactly the same way that we recovered the final byte earlier. From there, we continue in the same fashion. We fix the last two plaintext bytes to 03 03 and repeat this same attack for the third-to-last byte, and so on, eventually recovering \\(W\\) in its entirety.

\n

What about the rest of the plaintext? Well, note that the value \\(W\\) that we have recovered is actually \\(\\text{BLOCK_DECRYPT}(\\text{key},C_{247})\\). We could have put any other block there instead of \\(C_{247}\\), and the attack would have still been successful. Effectively, we can get the server to \\(\\text{BLOCK_DECRYPT}\\) anything for us. At that point, it’s game over – we can decrypt any ciphertext we want (take another look at the CBC decryption diagram to become convinced of this; and note that the IV is public).

\n

This particular technique of bootstrapping to a block-decryption oracle is worth paying attention to, as it plays a crucial role in an attack we’ll come across later.

\n

Kelsey’s Attack

\n

Kelsey, a man after our own hearts, outlined the principles behind many different possible attacks, rather than the finer details of one specific attack on one specific cipher. His 2002 paper is a study of possible attacks on encrypted compressed data. You’d think that to mount an attack, you’d need more to go on than “the data was compressed and then encrypted”, but apparently that’s enough.

\n

This surprising result is due to two principles at work. First, there tends to be a strong correlation between plaintext length and ciphertext length; for many ciphers, these two are exactly equal. Second, when compression is performed, there tends to also be a strong correlation between the compressed length and the degree to which the original text was “noisy” and non-repetitive (the technical term is “high-entropy”).

\n

To see this principle in action, consider the following two plaintexts:

\n

Plaintext 1: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

\n

Plaintext 2: ATVXCAGTRSVPTVVULSJQHGEYCMQPCRQBGCYIXCFJGJ

\n

Suppose both these plaintexts are compressed, then encrypted. You are given the two resulting ciphertexts, possibly out of order, and must guess which ciphertext corresponds to which plaintext:

\n

Ciphertext A: PVOVEYBPJDPVANEAWVGCIUWAABCIYIKOOURMYDTA

\n

Ciphertext B: DWKJZXYU

\n

The answer is clear. Among the plaintexts, only plaintext 1 could have been compressed to the meager length of ciphertext B. We figured this out without knowing anything about the compression algorithm, the cipher key or even the cipher itself; compared to the hierarchy of possible cryptographic attacks, that’s kind of insane.

\n

Kelsey goes on to point out that, under certain unusual circumstances, this principle could also be used to launch oracle attacks. To be specific, he outlines how an attacker can recover a secret plaintext if they can get the server to compress-then-encrypt data of the form (plaintext followed by \\(X\\)), as long as the attacker controls \\(X\\), and can somehow observe the length of the encrypted result.

\n

Again, as in other oracle attacks, we have a relationship: $$ \\text{Encrypt}(\\text{Compress}(\\text{Plaintext followed by} X)) = \\text{Ciphertext} $$

\n

Again, we control one term (\\(X\\)), receive a small information leak about another term (the ciphertext), and seek to recover the remaining term (the plaintext). Despite the valid analogy, you’ll note that this is an unusual setup, compared to the other oracle attacks we’ve seen.

\n

To illustrate how such an attack might work, we use a toy compression scheme that we just made up: TOYZIP. TOYZIP looks for strings of text that already appear earlier in the text, and replaces them with 3 “placeholder” bytes that indicate where to find the earlier instance of the string, and how long it is. So, for example, the string helloworldhello might be compressed to helloworld[00][00][05], which has a length of 13 bytes compared to the original’s 15.

\n

Suppose an attacker is trying to recover a plaintext of the form password=..., where the password itself is unknown. In line with Kelsey’s attack model, the attacker can ask the server to compress-then-encrypt messages of the form (plaintext followed by \\(X\\)), where \\(X\\) is any text of the attacker’s choice. When the server is done, it reports the length of the result. The attack proceeds as follows:

\n

Attacker: Please compress & encrypt the plaintext with no additions.

\n

Server: Result has length 14.

\n

Attacker: Please compress & encrypt the plaintext, followed by password=a.

\n

Server: Result has length 18.

\n

(Attacker notes: [original 14] + [3 bytes that replaced password=] + a)

\n

Attacker: Please compress & encrypt the plaintext followed by password=b.

\n

Server: Result has length 18.

\n

Attacker: Please compress & encrypt the plaintext followed by password=c.

\n

Server: Result has length 17.

\n

(Attacker notes: [original 14] + [3 bytes that replaced password=c]. This implies that the original plaintext contains the string password=c. Meaning, the password starts with the letter c.)

\n

Attacker: Please compress & encrypt the plaintext followed by password=ca.

\n

Server: Result has length 18.

\n

(Attacker notes: [original 14] + [3 bytes that replaced password=c] + a)

\n

Attacker: Please compress & encrypt the plaintext followed by password=cb.

\n

Server: Result has length 18.

\n

(…some time later…)

\n

Attacker: Please compress & encrypt the plaintext followed by password=co.

\n

Server: Result has length 17.

\n

(Attacker notes: [original 14] + [3 bytes that replaced password=co]. By the same logic that gave us the first letter, the password must start with the letters co.)

\n

And so forth and so on, until the whole password is recovered.

\n

The reader would be forgiven for thinking that this is a purely academic exercise, and that such an attack scenario would never arise in the real world. Alas, as we’ll see in a short moment, it’s best to never say “never” in cryptography.

\n

\n

Brand-Name Vulnerabilities: CRIME, POODLE, DROWN

\n

Finally, after persevering through all the above theory, we can now see how these principles of offense played out in real-world cryptographic vulnerabilities.

\n

CRIME

\n

\"\"When you are an attacker preying on a victim’s browser and network, some things are supposed to be easy, and others difficult. For instance, seeing the victim’s web traffic is easy; it’s enough for the two of you to be seated at the same Starbucks. For this reason, it’s usually recommended for potential victims (i.e. everyone) to use an encrypted connection. Less easy, but still possible, is making HTTP requests on the victim’s behalf to some third-party site (e.g. Google). The attacker has to entice the victim into visiting a malicious webpage, which contains a script that will make the request. The web browser will automagically endow the request with the appropriate session cookie.

\n

This might seem surprising; it apparently implies that if Bob visits evil.com, a script on that website can just ask Google to email Bob’s password to attacker@evil.com. Can that really happen? Well, yes in theory, but actually no in practice. That scenario is called a Cross-Site Request Forgery attack (CSRF), and it was more relevant around the mid-nineties. Today, if evil.com tries that trick, Google (or any self-respecting website) will typically respond: “excellent, but before we proceed, your CSRF token for this transaction is… mmm… three trillion and seven. Please repeat that back to me.” Modern browsers enforce something called the “same-origin policy”, according to which scripts running on website A do not get to access information sent by website B. The evil.com script can therefore send requests to google.com, but not read any responses, or actually complete a transaction.

\n

We should stress that if Bob is not using an encrypted connection, all of these defenses are meaningless. The attacker can simply read Bob’s traffic and recover the Google session cookie. Armed with the cookie, the attacker can just start a new Google tab from the comfort of their own browser, and impersonate Bob without having to deal with pesky same-origin policies. But, unfortunately for the attacker, that’s a pretty big if. The internet at large has long since declared war on plain-text connections, and Bob’s outgoing traffic is probably encrypted, whether he likes it or not. In fact, back in the day, the traffic would also first be compressed before being encrypted; this was routine practice by web clients to improve latency.

\n

Enter CRIME. The initials stand for Compression Ratio Infoleak Made Easy, and the attack was unveiled in September of 2012 by security researchers Juliano Rizzo and Thai Duong. We already have all the pieces in place to understand what they were able to pull off, and how. An attacker can make Bob’s browser send requests to Google, and then eavesdrop on the LAN to recover the resulting requests in their compressed, encrypted form. We therefore have: $$ \\text{Web traffic} = \\text{Encrypt}(\\text{Compress}(\\text{request followed by cookie})) $$

\n

Where the attacker controls the request, and has access to the sniffed web traffic in its entirety, including its length. Kelsey’s pipe-dream scenario had come to life.

\n

Based on this insight, the authors of CRIME crafted an exploit that could steal session cookies associated with a wide variety of sites, including Gmail, Twitter, Dropbox and Github. CRIME affected most modern web browsers, and in response to this attack, patches had to be issued that silently buried the feature of SSL compression, never again to see the light of day. The one notable exception was the venerable Internet Explorer, which had never implemented the feature in the first place.

\n

POODLE

\n

\"\"In October of 2014, a Google security team caused great alarm by exploiting a vulnerability in the SSL protocol that had already been patched for over a decade.

\n

It turned out that while servers were running the shiny and updated TLSv1.2, many of them included support for the antiquated SSLv3, put there for the sake of backwards compatibility with Internet Explorer 6. We’ve already spoken about downgrade attacks, so you can already see where this is going. A bit of well-placed sabotage of the protocol handshake, and these servers were eager to fall back on the old SSLv3 protocol, effectively setting back the security clock by 15 years.

\n

To put this in its proper historical context, here’s Matthew Green with a short summary of the history of SSL up until version 2:

\n

Transport Layer Security (TLS) is the most important security protocol on the Internet. [..] nearly every transaction you conduct on the internet relies on TLS. [..] But TLS wasn’t always TLS. The protocol began its life at Netscape Communications under the name “Secure Sockets Layer”, or SSL. Rumor has it that the first version of SSL was so awful that the protocol designers collected every printed copy and buried them in a secret New Mexico landfill site. As a consequence, the first public version of SSL is actually SSL version 2. It’s pretty terrible as well [..] it was a product of the mid-1990s, which modern cryptographers view as the “dark ages of cryptography”. Many of the nastier cryptographic attacks we know about today had not yet been discovered. As a result, the SSLv2 protocol designers were forced to essentially grope their way in the dark, and so were frequently devoured by grues – to their chagrin and our benefit, since the attacks on SSLv2 offered priceless lessons for the next generation of protocols.

\n

Following these events, in 1996, a disillusioned Netscape redesigned the SSL protocol from the ground up. The result was SSL version 3, which fixed several of its predecessor’s known security issues.

\n

Happily for attackers, “several” does not mean “all.” Broadly speaking, SSLv3 included all the necessary building blocks to launch Vaudenay’s attack. The protocol performed encryption using a block cipher in CBC mode, and used a padding scheme that was not designed with security in mind (this was fixed when SSL became TLS; hence the need for the downgrade attack). If you’ll recall the padding scheme we discussed in our original description of Vaudenay’s attack, the scheme used by SSLv3 was pretty similar.

\n

But, unhappily for attackers, “similar” does not mean “identical.” SSLv3’s padding scheme is of the form (N arbitrary bytes followed by the number N). Try to pick an imaginary ciphertext block and work through the stages of Vaudenay’s original method under these conditions; you’ll find that the attack does successfully extract the rightmost byte out of the corresponding plaintext block, but cannot proceed past that initial win. Decrypting every 16th byte of a ciphertext is a nifty parlor trick, but it’s not capital-V Victory.

\n

Faced with this setback, the Google team opted for a solution of last resort: they switched to a more powerful threat model — the one used in the CRIME attack. If we assume the attacker is a script running inside the victim’s browser tab, and prove it can extract the victim’s session cookie, that’s still a respectable feat. While it’s true that a more powerful threat model is a less feasible one, we’ve already seen in the previous section that this specific model is feasible enough.

\n

Given this more capable adversary, the attack can now finally proceed. Consider that the attacker knows where the encrypted session cookie appears in the header, and controls the length of the HTTP request that precedes it. They can, therefore, manipulate the HTTP request so that the final byte of the session cookie is aligned with the end of a block. That byte is now ripe for decryption. When that’s done, the attacker can simply add a single character to the request; now the second-to-final byte of the session cookie will sit in the same spot, and be ripe for picking using the same method. The attack continues in this fashion until the cookie is recovered in full. That’s POODLE – the Padding Oracle on Downgraded Legacy Encryption.

\n

DROWN

\n

\"\"As we’ve touched on previously, SSLv3 may have had its kinks, but it had nothing on its predecessor; SSLv2 was a hole-riddled protocol, a product of a different era. Attacks that were possible against it are now included in the security 101 syllabus. Victims would have their messages cut in mid-sentence, with I'll agree to that over my dead body turning into I'll agree to that; client and server would meet online, grow to trust each other, exchange secrets, and then find out that they were both catfished by some malicious agent who impersonated each one in front of the other. Then there was the issue of export-grade cryptography, which we covered earlier during the exposition of FREAK. It was cryptographic Sodom and Gomorrah.

\n

In March of 2016, a team of researchers from diverse technical backgrounds came together to make a startling realization: for security purposes, SSLv2 was still not dead. Yes, attackers could no longer downgrade modern TLS sessions to SSLv2, as that hole had been patched in the aftermath of FREAK and POODLE, but they could still approach servers and initiate SSLv2 sessions of their own.

\n

You might ask, what do we care if they do? They’ll have a vulnerable session, but this shouldn’t affect other sessions, or the security of the server — right? Well, yes and no. Yes — that’s how it should be in theory. No — because obtaining valid SSL certificates is a bother and a financial burden, resulting in many servers using the same certificates, and by extension the same RSA keys, for both TLS and SSLv2 connections. To make matters worse, due to a bug, the “disable SSLv2” option did not actually work in OpenSSL, a popular SSL implementation.

\n

This enabled a cross-protocol attack on TLS, called DROWN (Decrypting RSA with Obsolete and Weakened eNcryption). Recall that this is not the same thing as a downgrade attack; the attacker does not need to act as a “man in the middle”, and the client does not need to be manipulated into participating in an insecure session. The attackers, at their leisure, initiate an insecure SSLv2 session with the server, attack the weak protocol and recover the server’s private RSA key. This key is also valid for TLS connections, and at that point, all the security of TLS won’t save it from being compromised.

\n

To seal the deal, attackers still needed a working attack against SSLv2 that allowed them to recover not only some specific communication, but the server’s private RSA key. While this is a tall order, they could take their pick from any attack that was fully mitigated later than the release of SSLv2, and eventually found an attack to suit their needs: Bleichenbacher’s attack, which we had mentioned in passing earlier, and of which we’ll later see a full technical exposition. Both SSL and TLS contain counter-measures to obstruct Bleichenbacher’s attack, but some incidental features of SSL, combined with the short keys used in export-grade cryptography, made a version of the attack possible.

\n

At the time of its publication, DROWN affected the servers of about a quarter of the top million domains, and was possible to implement with modest resources, more in the ballpark of mischievous individuals than nation-states. Extracting a server’s RSA key was possible using an investment of eight hours and $440, and SSLv2 went from “deprecated” to “radioactive.”

\n

Wait, what about Heartbleed?

\n

\"\"That’s not a cryptographic attack in the same sense of the other attacks we’ve seen here; it’s a buffer overread.

\n

 

\n

Let’s take a break

\n

We started off by introducing some basic maneuvers: brute-force, interpolation, downgrade, cross-protocol and precomputation. This was followed by a single advanced technique, perhaps the most salient ingredient in modern cryptographic offense: the oracle attack. We spent quite a while with the oracle attack, understanding not only the principle behind it, but also the technical details behind two specific instances: Vaudenay’s attack on the CBC mode of operation, and Kelsey’s attack on compress-then-encrypt protocols.

\n

During our survey of Downgrade and Precomputation, we gave a short exposition of the FREAK attack, which made use of both these principles, as targeted websites were reduced to using weak keys, and then on top of that, opted to use the same keys again and again. We saved for later the full exposition of the (very similar) Logjam attack, which targeted a public-key algorithm.

\n

We then saw three more examples of cryptographic attack principles put into action. First, we took stock of CRIME and POODLE: two attacks which relied on an attacker’s ability to inject plaintext side-by-side with the targeted plaintext, then view the server’s response to the result, and then — using oracle attack methodology — pivot off this meager information to recover parts of the plaintext. CRIME went the route of Kelsey’s attack on SSL compression, while POODLE instead used a variant of Vaudenay’s attack on CBC to achieve the same effect.

\n

We then turned out attention to DROWN — a cross-protocol attack which spoke to servers in obsolete SSLv2, then recovered their private encryption keys using Bleichenbacher’s attack. For the time being, we skipped the technical details of that attack; like Logjam, it’ll have to wait until we are more comfortable with public-key encryption and its attack landscape.

\n

In the next blog post of this series, we’ll talk about advanced attacks — such as meet-in-the-middle, differential cryptanalysis, and the birthday attack. We’ll take a short foray into the land of side-channel attacks, and then we’ll finally delve into the exquisite realm of attacks on public-key cryptography.

\n","status":"PUBLISHED","fileName":null,"link":"https://research.checkpoint.com/2019/cryptographic-attacks-a-guide-for-the-perplexed/","tags":[],"score":0.17382857203483582,"topStoryDate":null},{"id":"RS-23335","type":"Research_Publications","name":"The Inside Scoop on a Six-Figure Nigerian Fraud Campaign","author":null,"date":1584468043000,"description":"Cybercrime is usually a one-way street. Shady types send their malicious documents and Trojans downstream to us innocent folk. Worst-case scenario, we get infected. Best-case scenario, we smirk, hit “delete” and move on with our lives. Either way, we’re left with many lingering questions. Who sends these out? Where did they get our email address?… Click to Read More","content":"

Cybercrime is usually a one-way street. Shady types send their malicious documents and Trojans downstream to us innocent folk. Worst-case scenario, we get infected. Best-case scenario, we smirk, hit “delete” and move on with our lives. Either way, we’re left with many lingering questions. Who sends these out? Where did they get our email address? Do they really make money doing this? How much?

\n

If you’ve asked yourself these questions too many times, today is your lucky day. Meet A██████████ A███████ D██████ton, who we’ll call Dton for short:

\n

\"\"

\n

 

\n

\"\"

\n

 

\n

Dton is an upstanding Nigerian citizen. He believes in professionalism, hard work and excellence. He’s a leader, a content creator, an entrepreneur and an innovator; an accomplished business administrator; a renaissance man who is adored by his colleagues. Even his primary school teacher is willing to sing his praises on a phone call’s notice.

\n

But behind this positive persona hides a dark secret. In the best comic book villain tradition, Dton leads a double life:

\n

\"\"

\n

 

\n

By day, he is Dton, administrator of businesses and achiever of organizational goals. But by night, he is Bill Henry, Cybercriminal Entrepreneur.

\n

Bill is a regular customer at the Ferrum shop – a fine business that stocks north of 2,500,000 stolen credit card credentials. During the years 2013-2020, the account he regularly logs into has been used to purchase over $13,000 worth in stolen credit card credentials.

\n

\"\"

\n

\"\"

\n

 

\n

Once Bill gets his hand on stolen credit card credentials, he is quick to monetize his new asset:

\n

\"\"

\n

 

\n

This typical charge is for 200,000 Nigerian Naira (NAN), the equivalent of about $550 USD. Luckily for whoever owns the original credit card used here, the transaction does not go through; but Bill is patient. He tries another merchant, and if that fails, he buys another credit card for another $4 or $16 and tries again. Eventually a transaction goes through. A back-of-the-envelope calculation shows that during the years 2013-2020, the $13,000 spent by this account were converted into about 1,000 credit cards, which were then fraudulently charged for a total easily exceeding $100,000 — probably several times that.

\n

You might object that the above story is a violation of basic economics. If a stolen credit card can be fraudulently charged for $500, why would anyone sell it for only $10? Well, stealing credit card credentials is easy and anonymous, given that banking malware and point-of-sale malware is everywhere and is notoriously difficult to trace back to whoever wrote and deployed it. Making credit card charges is something else entirely; it carries a whole additional set of risks and requires a distinct set of skills. Chief among those skills is sheer audacity — which Dton has no lack of, as you’ll see soon.

\n

Dton’s business has always been his pride, but one thing he could never get to like was having to constantly pay up at the Ferrum shop. He knew that true blood cybercriminals harvest their stolen credentials with their own two hands, fresh from the spam fields covered in morning dew; he longed to have that life. Some times, he would spend the $10 at the Ferrum shop and the transactions wouldn’t even go through. His resentment grew. He was an entrepreneur, not a gambler.

\n

No longer content to just buy, sell and monetize victim data, it was a matter of time before Dton dove head-first into the world of DIY stolen credentials. He was buying “leads” – email addresses of potential marks – in bulk.

\n

\"\"

\n

 

\n

But most of his attention went into buying malicious tools of the trade: Packers and crypters, infostealers and keyloggers, exploits and remote VMs. He had a true passion to play the field and see what worked best for him. Just for malware alone, he purchased and tried out AspireLogger:

\n

\"\"

\n

And Nanocore:

\n

\"\"

\n

And OriginLogger:

\n

\"\"

\n

And many, many other software of the kind that Windows Defender warns you about. Soon, Dton had a complete spamming staging ground — an army of remote, anonymized VMs that he could connect to with a VPN, and were equipped with the necessary tools for his work. On these machines he would take his hand-picked malicious binaries and run them through packers:

\n

\"\"

\n

Wrap them in an appealing malicious document:

\n

\"\"

\n

Carefully pick a message and subject line – then send the result out to a long, long list of potential victims.

\n

\"\"

\n

 

\n

Shortly after, the victim credentials came pouring in. Nanocore and its ilk delivered. Dton was ecstatic.

\n

\"\"

\n

\"\"

\n

 

\n

For Dton, this was a career milestone — but still, not everything was sunshine and rainbows. Sometimes Dton’s tool suppliers would make exaggerated financial demands:

\n

\"\"

\n

 

\n

In Dton’s place, would you pay $800 to have 3 binaries packed so that they have 0 VirusTotal detections? You probably shouldn’t. VT detection statistics aren’t always up-to-date, and aren’t guaranteed to reflect the full range of protections offered by the vendors involved.

\n

Worse yet, Dton wouldn’t always see eye-to-eye with his manager when discussing goals:

\n

\"\"

\n

 

\n

Yes – Dton has a manager. Possibly his manager also has a manager, and so on for eight tiers, but it grieves us to speculate on that. As you can see, Dton’s manager – “A” for short — periodically sends venture capital and expects handsome returns. If a project is not going well, The Boss gets angry, and as he says, you wouldn’t like him when he’s angry. Dton’s boss rules the workplace with an iron fist, and Dton’s terms of employment apparently demand that he install a Remote Administration Tool (RAT) on his own machine, which his boss can access freely. This leads to some very strange conversations:

\n

\"\"

\n

 

\n

\"\"

\n

 

\n

Yes, Mr. A, relax. Relax about the cybercriminal whose every movement you monitor obsessively, and who just logged in to your Yandex account. Chill.

\n

Why would Dton’s boss share his Yandex credentials with his underling so freely? That’s a very good question. Then again, why would they both use the same inbox for stolen victim data and for routine RAT-based workplace monitoring of Dton’s work? Take another look at the stream of incoming victim data:

\n

\"\"

\n

 

\n

All the recovered data tagged “HP-PC” is monitored data from Dton’s machine, aggregated with the rest of the victim data. In a certain poetic sense, Dton is just another victim.  (A famous quote from the social media site, reddit, goes: “I work as a dishwasher, and I come home after hours of work in which I get covered in filth, then I take a shower only to realize… I am the final dish”. This kind of reminded us of that).

\n

So: Dton’s career has a promising future, and his RAT-spamming operation is alive and kicking. But conversion rates are not what they could be and Dton’s boss is unhappy. Packing the malware to improve conversion rates comes at an overbearing premium. Dton begins to doubt the validity of the entire setup. He uses brand-name malware, and therefore gets burned by security solutions, since the vendors have a special incentive to go after “household name” malware; if he tries to stave off the detection with artisanal packing / crypting services, he has to pay out the nose. The free-to-use packers on his staging ground VMs just don’t cut it.

\n

It then occurs to Dton that there is technically one way out of this bind: write his own RAT. If it’s written from scratch, then it’s novel, and can therefore get around for exactly the same reasons as the novel coronavirus. No one has a signature, no one has a vaccine, none of the existing immune systems have ever seen it before. By the time they figure it out, a lot of damage will already be done.

\n

Of course, Dton is no coder. He has to get someone else to do it for him. He receives a recommendation for such a person who hangs out at a certain discord and goes by the name “RATs &exploits”. Mr. &exploits has spoken with many customers before, and has a canned reply for those interested in his services:

\n

\"\"

\n

 

\n

Dton engages this person, and a deal begins to take shape.

\n

\"\"

\n

 

\n

RATs&exploits also offers personal one-on-one technical support and hands-on demonstration of how to use the RAT. Here he is demonstrating his use of “Azorult”, a well-known piece of malware, on a virtual machine:

\n

\"\"

\n

 

\n

Mutual impressions are good, and soon money exchanges hands. Dton’s toolkit has reached the next level. He now has his own personalized, hand-crafted RAT as well as a personalized web client to monitor his victims. He leans back, smiles and surveys his domain.

\n

 

\n

\"\"

\n

In fact, Dton has not only found a professional contact in this RAT developer, but a true kindred spirit:

\n

\"\"

\n

 

\n

Or has he?

\n

Not much later, Dton is remotely viewing fresh screenshots — taken from the personal machine of the developer he has just done business with.

\n

\"\"

\n

 

\n

Let us repeat that: Dton, whose business model is infecting many innocent victims with RATs, and whose work is subject to strict surveillance by infecting his own machine with a RAT, commissioned a malware developer to write a personalized RAT for him and then had that developer’s machine compromised with a RAT. There is a decent chance that your brain just got infected with a RAT by reading this sentence.

\n

Not one to put all his eggs in one basket, Dton kept pursuing the dream of having his malware packed without having to pay “packing rent”. He soon became interested in dataprotector (datap.pro), a packer which offers a “lifetime package”:

\n

\"\"

\n

Of course, you don’t just purchase something like datap out of the blue. You need to know who to talk to. Dton soon reached his contact person for purchasing datap, who goes by “n0$f3ratu$” (That’s “Nosferatus”, for those in the audience who don’t speak l33t). Wary about investing such a large sum up front, Dton opted for the 45 days package, which is about a tenth of the price.

\n

\"\"

\n

\"\"

\n

Dton paid up, tried using the product a few times, and soon he was angry.

\n

He was not pleased with the product, or the price, or something at any rate. He felt that he should pull a power play to get a better deal, or else that n0$f3ratu$ should have just let him have the lifetime package for $36.50 – and that since he did not, there should be consequences. And then Dton had an idea.

\n

\"\"

\n

 

\n

Welp. Let’s look at that YouTube link:

\n

\"\"

\n

 

\n

That’s our friend n0$f3ratu$– teaching people how to bypass Windows Defender using the very same crypter he had just sold Dton. One moment, Dton was working together with this guy; the next, he was stabbing him in the back. Again.

\n

Dton does not immediately submit this anonymous report. Instead he uses it to taunt n0$f3ratu$ – who reacts about as positively as you’d expect:

\n

\"\"

\n

 

\n

We can only speculate on what n0$f3ratu$ means by that. Probably he and Dton got into a very heated debate about the price of the dataprotector lifetime package, and found that their differences were irreconcilable. And thus Dton reached the crowning achievement of his career – majorly angering the technical people on whose work his entire livelihood depended. Way to go, Dton.

\n

 

\n

So, what have we learned?

\n

On some level, we know that cybercriminals are flesh and blood. They have feelings, wants and needs; they hold grudges, they make mistakes. But some cybercriminals are much more flesh and blood than others. We can’t put enough emphasis on the absurd contrast between the more professional operations that we have been watching on the one hand, and this absolute train wreck on the other.

\n

Somewhere in Russia, as you are reading this, a well-coordinated gang is rotating their C&C servers on a daily basis and signing their malware with a rogue certificate authority. Bugs are corrected, features are introduced, security vendors are watched with a keen eye. Meanwhile, halfway across the earth in Nigeria, Dton is spamming out RATs that all contain hard-coded credentials for the single Gmail inbox the RATs all report to – then purposefully gets himself infected with a copy as well. When business with someone goes well, Dton infects them with a RAT just in case it later turns out to be useful; when business with someone goes less than well, Dton resolves the dispute by reporting them to the Interpol.

\n

And you know what? Dton is fine. Dton is living the good life.

\n

\"\"

\n

This is technically a picture of Dton’s colleague, but the point still stands.

\n

We don’t need to tell you how to defend yourself against Dton’s RATs, because if you’re reading this, you already know how. Update your web browser. Before clicking a web link, ask yourself who put it there and check out the actual target domain, starting from the top level. Don’t open that unsolicited “invoice” or “shipment notice”; if you do open it, don’t open the attached document; if you do open that, don’t click “enable macros”.

\n

It’s all trite advice that’s been repeated a million times – but the people who need to hear it aren’t reading this blog post. That’s how even Dton, a YOLO cybercriminal if we ever saw one, gets plenty of victims and rolls in cash.

\n

Talk to your friends about low-effort cybercrime. Tell them that whenever they open an email, they should take a long, hard look at the picture above, and imagine the person pictured there composing that email in a Turbomailer window. And that if the image fits too well, they should think about their next click very carefully.

\n

 

\n

*Note: All personal details have been blurred for the sake of this publication. The full details have been reported to relevant law enforcement officials

\n

 

\n","status":"PUBLISHED","fileName":null,"link":"https://research.checkpoint.com/2020/the-inside-scoop-on-a-six-figure-nigerian-fraud-campaign/","tags":[],"score":0.14360058307647705,"topStoryDate":null}],"mapData":null,"topMalwareFamilies":null};