The word 'cryptography' brings to mind various things for different people: some think of their WiFi password, the green padlock next to their favorite website, and the difficulty of hacking into someone else's email. Others recall the series of vulnerabilities from recent years characterized by memorable acronyms (DROWN, FREAK, POODLE…) and stylish logos, often accompanied by urgent prompts to update their browsers.

Cryptography encompasses all of this, but the essence lies elsewhere. The essence is in the fine line between simple and complex. Some things are straightforward to do but difficult to reverse: for example, breaking an egg. Other things are easy to execute but challenging to undo when a crucial piece is missing, like unlocking a door without the 'deciding piece,' which is the key. Cryptography studies these situations and the ways to practically utilize them.

In recent years, the collection of cryptographic attacks has turned into a zoo of eye-catching logos stuffed with formulas from scientific papers, giving rise to a prevailing gloomy feeling that everything is broken. However, many of these attacks are based on a few common principles, and the endless pages of formulas often boil down to easily understandable ideas.

In this series of articles, we will explore various types of cryptographic attacks, focusing on the core principles. Broadly speaking and not necessarily in this order, we will cover the following:

Basic strategies: brute force, frequency analysis, interpolation, downgrade, and cross-protocol attacks.
'Branded' vulnerabilities: FREAK, CRIME, POODLE, DROWN, Logjam.
Advanced strategies: oracle attacks (including the Watering Hole attack, Kelsey attack); meet-in-the-middle method, birthday attack, statistical bias (differential cryptanalysis, integral cryptanalysis, etc.).
Side-channel attacks and their close relatives, fault analysis methods.
Attacks on public key cryptography: cubic root, broadcast, related message, Coppersmith's attack, Pollard–Hellman algorithm, number sieve, Wiener attack, Bleichenbacher attack.

This specific article covers the aforementioned material up to the Kelsey attack.

Basic strategies

The following attacks are simple in the sense that they can be explained almost entirely without technical details. We will explain each type of attack in the simplest terms, avoiding complex examples or advanced use cases.

Some of these attacks have largely fallen out of relevance and haven’t been used for many years. Others are old-timers that still regularly catch unsuspecting cryptosystem developers off guard in the 21st century. One could say that the era of modern cryptography began with the advent of IBM DES—the first cipher that withstood all the attacks on this list.

Simple Brute Force

A ciphering scheme consists of two parts: 1) an encryption function that takes a message (plaintext) along with a key and then creates an encrypted message—ciphertext; 2) a decryption function that takes ciphertext and a key and produces plaintext. Both encryption and decryption should be easily computable with the key—and difficult without it.

Suppose we see the ciphertext and attempt to decrypt it without any additional information (this is called a 'ciphertext-only' attack). If we somehow magically find the correct key, we can easily verify that it is indeed correct if the result is a sensible message.

Note that there are two implicit assumptions here. First, that we know how to perform the decryption, i.e., how the cryptosystem works. This is a standard assumption when discussing cryptography. Hiding the details of the cipher's implementation from adversaries may seem like an additional security measure, but once an adversary learns those details, this extra security is quietly and irretrievably lost. Such is Kerckhoffs's principle: the system’s fall into enemy hands should not cause inconvenience.

Secondly, we assume that the correct key is the only key that will lead to a sensible decryption. This is also a reasonable assumption; it holds if the ciphertext is significantly longer than the key and is easily readable. Generally, this is the case in the real world, except for huge impractical keys or and other manipulations that are best left aside. (if you don't like that we skipped the explanations, please see theorem 3.8 here).

Given the above, a strategy arises: to check every possible key. This is called brute-forcing, and such an attack is guaranteed to work against all practical ciphers — eventually. For example, brute-forcing is sufficient to break the Caesar cipher, an ancient cipher where the key is one letter from the alphabet, which implies just over 20 possible keys.

Unfortunately for cryptanalysts, increasing the key size provides good protection against brute-forcing. As the key size increases, the number of possible keys grows exponentially. With modern key sizes, simple brute-forcing becomes completely impractical. To understand what we mean, let's take the fastest known supercomputer as of mid-2019: Summit by IBM, with a peak performance of about 10^17 operations per second. Today, a typical key length is 128 bits, which means 2^128 possible combinations. To iterate through all keys, the Summit supercomputer would require a time approximately 7800 times greater than the age of the Universe.

Should brute-forcing be considered a historical curiosity? Not at all: it's a necessary ingredient in the cookbook of cryptanalysis. Rarely do you encounter ciphers that can only be broken by clever attacks, without some degree of brute force. Many successful hacks first employ an algorithmic method to weaken the target cipher, and then initiate brute-forcing.

Frequency Analysis

Most texts are not gibberish. For example, English texts contain many 'e's and articles like 'the'; binary files have many null bytes as padding between fragments of information. Frequency analysis is any attack that leverages this fact.

A canonical example of a cipher vulnerable to this attack is a simple substitution cipher. In this cipher, the key is a table that replaces all letters. For example, 'g' is replaced with 'h', 'o' is replaced with 'j', so the word 'go' becomes 'hj'. This cipher is difficult to attack with simple brute force because there are so many possible substitution tables. If you're interested in the math, the effective key length is about 88 bits: this
However, frequency analysis usually handles the task quickly.

Let's consider the following ciphertext processed by a simple substitution cipher:

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

Since Y it occurs frequently, including at the end of many words, we can preliminarily assume that this is the letter e:

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

The pair XD repeats at the beginning of several words. In particular, the combination XDeLe clearly suggests the word these or there, so we continue:

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

Next, let's assume that L corresponds to r, A — a and so on. It might take several attempts, but compared to a full brute force, this attack recovers the original text in the shortest time possible:

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

For some, solving such "cryptograms" is an entertaining hobby.

The idea of frequency analysis is more fundamental than it seems at first glance. It applies to much more complex ciphers. Throughout history, various cipher constructions have attempted to counter such attacks using "polyalphabetic substitution." Here, during encryption, the substitution table of letters changes in complex but predictable ways that depend on the key. All these ciphers were once considered hard to crack; yet the humble frequency analysis ultimately overcame them all.

The most ambitious polyalphabetic cipher in history, and probably the most famous, was the "Enigma" cipher during World War II. It was relatively complex compared to its predecessors, but after long and persistent work, British cryptanalysts broke it using frequency analysis. Of course, they could not develop an elegant attack as shown above; they had to compare known pairs of plaintexts and ciphertexts (the so-called "known plaintext attack") and even coax users of the "Enigma" to encrypt certain messages to analyze the results (the "chosen plaintext attack"). But this did not ease the fate of the defeated enemy armies and sunk submarines.

After this triumph, frequency analysis vanished from the history of cryptanalysis. The ciphers of the modern digital age are designed to work with bits rather than letters. More importantly, these ciphers were developed with a grim understanding of what later became known as the Schneier's Law: anyone can create an encryption algorithm that they themselves cannot break. It is not enough for a cryptographic system to seem complex: to prove its worth, it must undergo a ruthless security review by many cryptanalysts who will do everything possible to break the cipher.

Precomputation

Let's take a hypothetical city of Precom Heights with a population of 200,000. In each house of the city, there are valuables averaging $30,000, but not exceeding $50,000. The security market in Precom is monopolized by ACME Industries, which produces the legendary Coyote ™ class door locks. According to expert analysis, the Coyote class lock can only be broken by a very complex hypothetical machine, the creation of which requires about five years and $50,000 in investment. Is the city safe?

Most likely not. Eventually, a sufficiently ambitious criminal will emerge. He will reason as follows: "Yes, I'll bear the high upfront costs. Five years of patient waiting, and $50,000. But once it’s done, I will have access to the entire wealth of this city. If I play my cards right, this investment will pay off many times over."

The same goes for cryptography. Attacks against a specific cipher undergo ruthless cost-benefit analysis. If the ratio is favorable, the attack does not happen. However, attacks that target many potential victims at once almost always pay off, and in this case, the best design practice is to assume that they began from day one. We essentially have a cryptographic version of Murphy's Law: "Anything that can break the system will break the system."

The simplest example of a cryptosystem vulnerable to precomputation attacks is a cipher with a constant algorithm that does not use a key. Such was the case with the Caesar cipher., which simply shifts each letter of the alphabet three places forward (the table is wrapped around, so the last letter in the alphabet is encrypted by the third). Here again, the Kerckhoffs principle demonstrates itself: once a system is broken, it is broken forever.

The concept is simple. Even a novice cryptography developer will likely understand the threat and prepare accordingly. Looking at the evolution of cryptography, such attacks were unwarranted against most ciphers, starting from the early enhanced versions of the Caesar cipher, up to the decline of polyalphabetic ciphers. Such attacks only returned with the advent of modern cryptography.

This resurgence is caused by two factors. First, sufficiently complex cryptosystems have finally emerged where the possibility of exploitation after a breach was not obvious. Second, cryptography has become so widespread that millions of non-professionals make decisions every day about where and which parts of cryptography to reuse. It took some time before experts recognized the emerging risks and raised the alarm.

Remember the precomputation attack: at the end of this article, we will look at two real-life cryptographic examples where it played a significant role.

Interpolation

Before you is the famous detective Sherlock Holmes performing an interpolation attack on the unsuspecting Doctor Watson:

I immediately guessed that you came from Afghanistan... My thoughts were as follows: 'This man resembles a doctor, but his posture is military. Therefore, he’s a military doctor. He has just arrived from the tropics—his face is tanned, but that’s not the natural hue of his skin since his wrists are much whiter. His face is haggard—clearly, he has endured quite a lot and suffered from illness. He was wounded in the left arm—holds it still and somewhat unnaturally. Where could a British military doctor in the tropics have endured hardships and received a wound? Of course, in Afghanistan.' The entire train of thought took less than a second. And so I said that you came from Afghanistan, and you were surprised.

From each hive, Holmes could extract very little information. He could only come to his conclusion by considering them all together. The interpolation attack works similarly, exploring known pairs of plaintext and ciphertext obtained through the application of the same key. Individual observations are extracted from each pair, allowing a general conclusion about the key to be made. All these deductions are vague and seem useless until they suddenly reach a critical mass and lead to the only possible conclusion: however incredible it may be, it must be true. After that, either the key is revealed, or the decryption process becomes so refined that it can be replicated.

Let's illustrate with a simple example how interpolation works. Suppose we want to read our enemy Bob's personal diary. He encrypts each number in his diary using a simple cryptosystem he learned from an advertisement in the "Mockery of Cryptography" magazine. The system works as follows: Bob chooses two numbers that he likes: and . From this point on, to encrypt any number , he calculates . For example, if Bob chose and , then the digit is encrypted as .

. Suppose on December 28, we noticed that Bob was scratching something in his diary. When he finishes, we discreetly take it and look at the last entry:

Date: 235/520
Dear diary,
Today was a good day. In 64 days, I have a date with Alice, who lives in apartment 843. I really think she might be 26!

. Since we are very serious about tracking Bob on his date (in this scenario, we are both 15 years old), it is critically important to find out the date and Alice's address. Fortunately, we notice that Bob's cryptosystem is vulnerable to interpolation attacks. We may not know and , but we know today's date, so we have two pairs of "plaintext - ciphertext". Specifically, we know that is encrypted as , and — in . We will record this:

Since we are 15 years old, we already know about the system of two equations with two unknowns, which in this situation is enough to find. and without too many problems. Each pair of 'plaintext-ciphertext' imposes a constraint on Bob's key, and two constraints together are sufficient to fully recover the key. In our example, the answer and (when , so that 26 in the diary corresponds to the phrase ‘the one,’ meaning ‘the very one’ — ed. note.

Interpolation attacks are certainly not limited to such simple examples. Every cryptosystem that can be reduced to a well-understood mathematical object and a list of parameters is at risk of an interpolation attack — the more comprehensible the object, the higher the risk.

Novices often complain that cryptography is 'the art of designing the ugliest possible things.' This is likely due in large part to interpolation attacks. Bob can either use elegant mathematical design or maintain the confidentiality of the meeting with Alice — but unfortunately, you usually cannot achieve both. This will become abundantly clear when we eventually turn to the topic of public key cryptography.

Cross-protocol/downgrade

In the film 'Now You See Me' (2013), a group of illusionists tries to con the entire fortune of corrupt insurance magnate Arthur Tressler. To gain access to Arthur's bank account, the illusionists must either provide his username and password or force him to personally appear at the bank and participate in the scheme.

Both options are very difficult; the guys are used to performing on stage, not engaging in intelligence operations. So they opt for a third possible option: their accomplice calls the bank and pretends to be Arthur. The bank asks a few verification questions, such as the name of his uncle and the name of his first pet; our heroes skillfully extract this information from Arthur through clever social engineering.. From this point on, excellent password security no longer matters.

(According to an urban legend that we personally verified and confirmed, cryptographer Eli Biham once encountered a bank teller who insisted on setting up a security question. When the teller asked for the name of the maternal grandmother, Biham began dictating: 'Capital X, lowercase y, three...').

Similarly in cryptography, if two cryptographic protocols are used in parallel to protect the same asset, and one is significantly weaker than the other, the overall system becomes vulnerable to a cross-protocol attack. In this case, the weaker protocol is targeted to reach the prize without touching the stronger one.

In some complex cases, it's not enough just to connect to the server using the weaker protocol; it requires the unwitting participation of a legitimate client. This can be organized through what is known as a downgrade attack. To understand this attack, let's assume our illusionists have a more complicated task than portrayed in the movie. Imagine a scenario where a bank employee (the teller) and Arthur encounter unforeseen circumstances, resulting in a dialogue like this:

Hacker: Hello? This is Arthur Tressler. I would like to reset my password.
Teller: Great. Please take a look at your personal book of secret codes, page 28, word 3. All subsequent messages will be encrypted using this specific word as a key. PQJGH. LOTJNAM PGGY MXVRL ZZLQ SRIU HHNMLPPPV…
Hacker: Hey, hey, wait a minute. Is this really necessary? Can’t we just talk like normal people?
Teller: I wouldn’t recommend that.
Hacker: I’m just… listen, I had a rough day, alright? I’m a VIP client and not in the mood to dig through these silly code books.
Teller: Alright. If you insist, Mr. Tressler. What can I do for you?
Hacker: Please, I would like to transfer all my money to the National Fund for Arthur Tressler Victims.
(Pause).
Teller: Okay, understood. Please provide your pin code for large transactions.
Hacker: My what?
Teller: At your personal request, transactions of that size require entering a pin code for large transactions. This code was given to you when you opened your account.
Hacker:...I've lost it. Is this really necessary? Can’t you just approve the transaction?
Teller: No. I’m sorry, Mr. Tressler. Again, this is a security measure you requested. If you like, we can send a new pin code to your mailbox.

Our heroes are postponing the operation. They are listening in on several significant transactions involving Tressler, hoping to catch a PIN code; but each time the conversation devolves into encrypted gibberish before anything interesting is revealed. Finally, one fine day, they put the plan into action. They patiently await the moment when Tressler is supposed to make a large transaction over the phone, he connects to the line, and then…

Tressler: Hello. I would like to make a remote transaction, please.
Teller: Great. Please look at your personal secret codes book, page…
(The hacker presses a button; the cashier's voice turns into indistinguishable noise).
Teller: — #@$#@$#*@$$@#* will be encrypted with this word as the key. AAAYRR PLRQRZ MMNJK LOJBAN…
Tressler: Excuse me, I didn’t quite catch that. Could you repeat? Which page? What word?
Teller: That's page @#$@#*$)#*#@()#@$(#@*$(#@*.
Tressler: What?
Teller: Word number twenty @$#@$#%#$.
Tressler: Seriously! Enough already! You and your security protocol—it’s a circus. I know you can just talk normally with me.
Teller: I wouldn't advise…
Tressler: And I advise you not to waste my time. I don’t want to hear about that again until you fix your phone line issues. Can we proceed with this transaction or not?
Teller:… yes. All right. What would you like?
Tressler: I would like to transfer $20,000 to Lord Business Investments, account number…
Teller: Hold on a moment, please. This is a big transaction. Please provide your PIN for large transactions.
Tressler: What? Oh, right. 1234.

Here’s a downgrade attack. The weaker 'just talk straight' protocol was intended as to move the navigation bar to the bottom or top of the screen. a last resort. And yet here we are.

You may ask the question, who in their right mind would design a real system like 'secure until asked otherwise', as described above. But just as the fictional bank takes risks to retain clients who dislike cryptography, real systems often bend to requirements that are indifferent or even outright hostile to security.

A similar story unfolded with the SSLv2 protocol in 1995. The U.S. government had long viewed cryptography as a weapon best kept away from both external and internal adversaries. Individual code fragments were approved for export from the U.S., often under the condition of deliberately weakening the algorithm. Companies like Netscape, the developer of the most popular browser, Netscape Navigator, were granted permission for SSLv2 only with an initially vulnerable 512-bit RSA key (and 40-bit for RC4).

By the turn of the millennium, regulations had softened and access to modern encryption became widely available. However, clients and servers maintained weakened 'export' cryptography for many years due to the same inertia that keeps older systems afloat. Clients believed they might encounter a server that supported nothing else. Servers did the same. Of course, the SSL protocol dictates that clients and servers should never use a weak protocol when a better one is available. But the same premise applied to Treschler and his bank.

This theory was demonstrated in two high-profile attacks that shook the security of the SSL protocol in 2015, both discovered by Microsoft researchers and INRIA. First, in February, details of the FREAK attack were disclosed, followed three months later by another similar attack called Logjam, which we will discuss in more detail as we move on to public key cryptography attacks.

The vulnerability FREAK (also known as 'Smack TLS') emerged when researchers analyzed TLS client/server implementations and discovered an intriguing flaw. In these implementations, if the client does not even request the use of weak export cryptography, but the server still responds with such keys – the client says, 'Alright then' and falls back to a weak cipher set.

At that time, everyone believed export cryptography was outdated and prohibited for use, so the attack came as a real shock and affected many important domains, including the websites of the White House, the U.S. Internal Revenue Service, and the NSA. Worse still, it turned out that many vulnerable servers optimized performance by reusing the same keys instead of generating new ones for each session. This allowed for a precomputation attack after lowering the protocol: cracking one key remained relatively expensive ($100 and 12 hours at the time of publication), but the practical cost of attacking a connection significantly decreased. If a server key was cracked once, decrypting for all subsequent connections from that point onward became trivial.

And before moving on, it's worth mentioning one advanced attack...

Oracle Attack

Moxie Marlinspike is best known as the father of the cross-platform cryptomessenger Signal; but personally, we appreciate one of his less known innovations— the Cryptographic Doom Principle. (Cryptographic Doom Principle). To paraphrase slightly, it can be stated as: "If a protocol performs any cryptographic operation on a message from a potentially malicious source and behaves differently depending on the outcome, it is doomed." Or more harshly: "Don’t take information from the enemy for processing, and if you must, at least don’t show the result."

Let’s set aside buffer overflows, command injections, and the like; they are beyond the scope of this discussion. Violating the 'Doom Principle' leads to serious cryptographic hacks because the protocol behaves exactly as it is supposed to.

For example, let’s take a fictional construction with a vulnerable substitution cipher and then demonstrate a possible attack. While we have seen an attack on a substitution cipher using frequency analysis, this is not just 'another way to break the same cipher.' On the contrary, oracle attacks are a much more modern invention applicable to many situations where frequency analysis fails, and we will see a demonstration of this in the next section. Here, a simple cipher is chosen only to make the example clearer.

So, Alice and Bob communicate using a simple substitution cipher, employing a key known only to them. They are very strict about the length of messages: it must be exactly 20 characters. Therefore, they agreed that if someone wants to send a shorter message, they must add some dummy text to the end of the message to make it exactly 20 characters long. After some discussion, they decided they would only accept the following dummy texts: a, bb, ccc, dddd etc. Thus, the dummy text of any necessary length is known.

When Alice or Bob receives a message, they first check that the message has the correct length (20 characters), and that the suffix is the correct dummy text. If not, they respond with an appropriate error message. If the text length and dummy text are in order, the receiver reads the message itself and sends an encrypted reply.

During the attack, the attacker impersonates Bob and sends fake messages to Alice. The messages are complete nonsense—the attacker does not have the key and therefore cannot forge a meaningful message. But since the protocol violates the principle of irrevocability, the attacker can still lure Alice into revealing key information, as shown below.

Hacker: PREWF ZHJKL MMMN. LA
Alice: Invalid dummy text.
Hacker: PREWF ZHJKL MMMN. LB
Alice: Invalid dummy text.
Hacker: PREWF ZHJKL MMMN. LC
Alice: ILCT? TLCT RUWO PUT KCAW CPS OWPOW!

The attacker has no idea what Alice just said, but notes that the character C must match a, since Alice accepted the dummy text.

Hacker: REWF ZHJKL MMMN. LAA
Alice: Invalid dummy text.
Hacker: REWF ZHJKL MMMN. LBB
Alice: Invalid dummy text.
After several attempts…
Hacker: REWF ZHJKL MMMN. LGG
Alice: Invalid dummy text.
Hacker: REWF ZHJKL MMMN. LHH
Alice: TLQO JWCRO FQAW SUY LCR C OWQXYJW. IW PWWR TU TCFA CHUYT TLQO JWFCTQUPOLQZ.

Again, the attacker has no idea what Alice just said, but notes that H should match b, since Alice accepted the dummy text.

And so on, until the attacker learns the meaning of each character.

At first glance, the method resembles a chosen plaintext attack. After all, the attacker selects ciphertexts, and the server obediently processes them. The main difference that makes these attacks viable in the real world is that the attacker does not need access to the actual decryption—they only need the server's response, even one as benign as 'Incorrect dummy text.'

While this particular attack is instructive, one should not get too caught up in the specifics of the 'dummy text' scheme, the specific cryptosystem used, or the exact sequence of messages sent by the attacker. The key idea is how Alice responds differently based on the properties of the plaintext, and she does so without verifying that the corresponding ciphertext was indeed received from a trusted party. Thus, Alice allows the attacker to extract secret information from her responses.

In this scenario, many elements can change. The symbols Alice responds to, her behavior changes, or even the cryptosystem used. But the principle will remain the same, and the attack will still be viable in some form. The basic implementation of this attack has helped uncover several security flaws that we will soon discuss; but first, some theoretical lessons need to be understood. How can this fictional 'Alice scenario' be utilized in an attack that can work on a modern cipher? Is this possible even in theory?

In 1998, Swiss cryptographer Daniel Bleichenbacher answered this question affirmatively. He demonstrated an oracle attack on the widely used RSA public key cryptosystem by using a specific message scheme. In some implementations of RSA, the server responds with different error messages depending on whether the plaintext conforms to the scheme or not; this was sufficient to carry out an attack.

Four years later, in 2002, French cryptographer Serge Vaudenay demonstrated an oracle attack, almost identical to the one described above in Alice's scenario—except that instead of a made-up cipher, he broke an entire respectable class of modern ciphers that people actually use. Specifically, Vaudenay's attack targets ciphers with a fixed input size ("block ciphers") when used in the so-called "CBC encryption mode" and with a certain popular padding scheme, primarily equivalent to that in Alice's scenario.

Also in 2002, American cryptographer John Kelsey—co-author Twofish —proposed various oracle attacks on systems that compress messages before encrypting them. The most notable among them was an attack that used the fact that the original plaintext length can often be inferred from the length of the ciphertext. In theory, this allows for an oracle attack that recovers parts of the original plaintext.

Next, we provide a more detailed description of the attacks by Vaudenay and Kelsey (we will give a more detailed description of Bleichenbacher's attack when we move on to attacks on public key cryptography). Despite all our efforts, the text becomes somewhat technical; therefore, if the above is sufficient for you, feel free to skip the next two sections.

Vaudenay's Attack

To understand Vaudenay's attack, we first need to discuss block ciphers and encryption modes in a bit more detail. A "block cipher" is, as mentioned, a cipher that takes a key and input of a certain fixed length ("block size") and outputs an encrypted block of the same length. Block ciphers are widely used and considered relatively secure. The now-retired DES, regarded as the first modern cipher, was a block cipher. The same is true for AES, which is widely used today.

Unfortunately, block ciphers have one glaring weakness. The typical block size is 128 bits, or 16 characters. It is clear that modern cryptography needs to work with input data of larger sizes, and this is where encryption modes come into play. An encryption mode is essentially a hack: it is a way to somehow apply a block cipher that only accepts input data of a specific size to input data of arbitrary length.

The Watern attack is focused on the popular CBC (Cipher Block Chaining) mode of operation. This attack treats the underlying block cipher as a magical impenetrable black box and completely bypasses its security.

Here is a diagram that shows how the CBC mode works:

The circled plus indicates an XOR operation (exclusive "OR"). For example, the second block of ciphertext is obtained by:

Performing the XOR operation on the second block of plaintext with the first block of ciphertext.
Encrypting the resulting block using the block cipher, with the key.

Since CBC makes heavy use of the binary XOR operation, let’s take this moment to recall some of its properties:

Idempotence:
Commutativity:
Associativity:
Self-inverseness:
Byte-wise: byte n of = (byte n of ) (byte n of )

Generally, these properties imply that if we have an equation involving XOR operations and one unknown, it can be solved. For example, if we know that with the unknown and the known and , we can rely on the above-mentioned properties to solve the equation for . By applying XOR to both sides of the equation with , we arrive at . In a moment, all of this will become very relevant.

There are two minor differences and one main difference between our Alice scenario and the Watern attack. The two minor differences are:

In Alice's scenario, she expected the plaintexts to end with characters a, bb, ccc and so on. In the Watern attack, the victim expects the plaintexts to end instead with N repetitions of byte N (i.e., hexadecimal 01 or 02 02, or 03 03 03, and so on). This is purely a cosmetic difference.
In Alice's scenario, it was easy to say whether Alice accepted the message by the response, "Incorrect dummy text." The Waterne attack requires more analysis and precise implementation on the victim's side; but for brevity, let's assume that this analysis is still feasible.

The main difference:

Since we are not using the same cryptosystem, the relationship between the bytes of the encrypted text controlled by the attacker and the secrets (key and plaintext) will obviously be different. Therefore, the attacker will have to use a different strategy for generating ciphertexts and interpreting the server's responses.

This main difference is the last piece of the puzzle needed to understand the Waterne attack, so let's take a moment to think about why and how one could even organize an oracle attack on CBC.

Suppose we have a CBC ciphertext of 247 blocks, and we want to decrypt it. We can send fake messages to the server, just as we could have sent fake messages to Alice. The server will decrypt the messages for us but will not show the decryption — instead, like in Alice's case, the server will only provide one bit of information: whether the plaintext has valid padding or not.

Note that in Alice's scenario we had the following relationships:

$$display$$text{SIMPLE_SUBSTITUTION}(text{ciphertext},text{key}) = text{plaintext}$$display$$

Let's call this "Alice's equation." We controlled the ciphertext; the server (Alice) leaked vague information about the received plaintext; and this allowed us to derive information about the last factor — the key. Analogously, if we can establish such a connection for the CBC scenario, we could extract some secret information there as well.

Fortunately, there are indeed relationships that we can exploit. Consider the outputs of the final decryption call to the block cipher and denote this data as . Let's also denote the plaintext blocks and the ciphertext blocks . Take another look at the CBC diagram and note what emerges:

Let's call this "CBC equation."

In Alice's scenario, controlling the ciphertext and observing the leakage of information about the corresponding plaintext, we were able to organize an attack that recovered the third element of the equation — the key. In the CBC scenario, we also control the ciphertext and observe information leaks regarding the corresponding plaintext. If the analogy holds, we can obtain information about .

Let's assume we have indeed recovered , what then? Well, then we can immediately output the entire last block of plaintext (), simply by inputting (which we have) and
the obtained in the CBC equation.

So, we are optimistic about the overall attack plan, and it is time to work out the details. We pay attention to exactly how information about the plaintext is leaking on the server. In Alice's scenario, the leakage occurred because Alice only responded with the correct message if $inline$text{SIMPLE_SUBSTITUTION}(text{ciphertext},text{key})$inline$ ended with the string a (or bb, and so forth, but the chances of randomly hitting these conditions were very low). Similarly, with CBC, the server accepts padding if and only if ends with a hexadecimal. 01So, let's try the same trick: sending fake ciphertexts with our own fake values , until the server accepts the padding.

When the server accepts padding for one of our fake messages, it means that:

Now we use the byte-wise property of XOR:

We know the first and third elements. And we have already seen that this allows us to recover the remaining element — the last byte from :

This also gives us the last byte of the final block of plaintext through the CBC equation and the byte-wise property.

We could stop here and be satisfied that we have attacked a theoretically secure cipher. But in reality, we can do much more: we can actually recover the entire text. This requires a certain trick that was not present in the original Alice scenario and it is not part of the mandatory conditions for the oracle attack, but the method is still worth investigating.

To understand it, first note that as a result of deriving the correct value of the last byte We have developed a new capability. Now, when forging ciphertexts, we can control the last byte of the corresponding plaintext. Again, this relates to the CBC equation and the property of byte-wise operations:

Since we now know the second member, we can use our control over the first to manipulate the third. We simply compute:

Previously, we couldn't do this because we did not yet have the last byte. .

How does this help us? Let's assume that we will now create all ciphertexts such that the corresponding plaintexts end with 02. Now the server accepts padding only if the plaintext ends with 02 02. Since we fixed the last byte, this will only happen if the second-to-last byte of the plaintext also equals 02. We continue to send forged ciphertext blocks, changing the second-to-last byte until the server accepts the padding for one of them. At this point, we obtain:

And we recover the second-to-last byte exactly as we restored the last one. We continue similarly: we fix the last two bytes of the plaintext to 03 03, repeat this attack for the third-to-last byte, and so forth, ultimately recovering completely .

What about the rest of the text? Note that the value is actually $inline$text{BLOCK_DECRYPT}(text{key},C_{247})$inline$. We can substitute any other block instead of , and the attack will still be successful. In fact, we can ask the server to perform $inline$text{BLOCK_DECRYPT}$inline$ for any data. At this moment, the game is over — we can decrypt any ciphertext (take another look at the CBC decryption diagram to verify this; and note that the IV vector is public).

This particular method plays a crucial role in the oracle attack that we will encounter later.

Kelsey Attack

The like-minded John Kelsey outlined the principles underlying many possible attacks, not just the detailed specifics of a specific attack on a specific cipher. His 2002 paper is a study on possible attacks on encrypted compressed data. Did you think that conducting an attack required more than just the information that the data was compressed before encryption? It turns out it is sufficient.

This remarkable result is based on two principles. First, there is a strong correlation between the length of the plaintext and the length of the ciphertext; for many ciphers, this is exactly equal. Second, when compression occurs, there is also a strong correlation between the length of the compressed message and the degree of 'noisiness' of the plaintext, meaning the share of non-repeating characters (a technical term — 'high entropy').

To see the principle in action, let's consider two plaintexts:

Plaintext 1: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Plaintext 2: ATVXCAGTRSVPTVVULSJQHGEYCMQPCRQBGCYIXCFJGJ

Suppose both plaintexts are compressed and then encrypted. You get two resulting ciphertexts and must guess which ciphertext corresponds to which plaintext:

Ciphertext 1: PVOVEYBPJDPVANEAWVGCIUWAABCIYIKOOURMYDTA
Ciphertext 2: DWKJZXYU

The answer is clear. Among the plaintexts, only plaintext 1 could have been compressed to the scant length of the second ciphertext. We figured this out without knowing anything about the compression algorithm, the encryption key, or even the cipher itself. Compared to the hierarchy of possible cryptographic attacks, this is kind of madness.

Kelsey further points out that under certain unusual circumstances, this principle can also be used to conduct an oracle attack. In particular, he describes how an attacker can recover the secret plaintext if they can make the server encrypt form data (the plaintext followed by , while they control and can somehow check the length of the encrypted result.

Again, as with other oracle attacks, we have a relationship:

Once more, we control one member (), see a slight leak of information about the other member (the ciphertext), and attempt to recover the latter (the plaintext). Despite the analogy, this is somewhat of an unusual situation compared to other oracle attacks we've seen.

To illustrate how such an attack might work, let's use a fictional compression scheme that we just came up with: TOYZIP. It looks for strings of text that have appeared earlier in the text and replaces them with three filler bytes indicating where to find an earlier instance of the string and how many times it occurs there. For example, the string helloworldhello can be compressed to helloworld[00][00][05] a length of 13 bytes compared to the original 15 bytes.

Let’s assume a hacker is trying to recover the plaintext of the form password=..., where the password itself is unknown. According to Kelsey’s attack model, the hacker can ask the server to compress, and then encrypt the messages of the form (the plaintext followed by ), where — arbitrary text. When the server has finished processing, it reports the length of the result. The attack works as follows:

Hacker: Please compress and encrypt the plaintext without any fillers.
Server: Result length 14.
Hacker: Please compress and encrypt the plaintext with password=a.
Server: Result length 18.

The hacker notes: [original 14] + [three bytes that replaced password=] + a

Hacker: Please compress and encrypt the plaintext with password=b.
Server: Result length 18.
Hacker: Please compress and encrypt the plaintext with password=c.
Server: Result length 17.

The hacker notes: [original 14] + [three bytes that replaced password=c]. This implies that the original plaintext contains the string password=c. That is, the password starts with the letter c

Hacker: Please compress and encrypt the plaintext with password=ca.
Server: Result length 18.

The hacker notes: [original 14] + [three bytes that replaced password=c] + a

Hacker: Please compress and encrypt the plaintext with password=cb.
Server: Result length 18.

(… some time later…)

Hacker: Please compress and encrypt the plaintext with password=co.
Server: Result length 17.

The hacker notes: [original 14] + [three bytes that replaced password=co]. By the same logic, the hacker concludes that the password starts with the letters co

And so on until the entire password is recovered.

The reader may be forgiven for thinking that this is purely an academic exercise and such an attack scenario would never arise in the real world. Unfortunately, as we will soon see, it is best not to make assumptions in cryptography.

Brand vulnerabilities: CRIME, POODLE, DROWN

Finally, after a detailed study of the theory, we can look at how these methods are applied in real cryptographic attacks.

CRIME

If the attack targets the victim's browser and network, some things will be easier, while others will be harder. For example, it is easy to see the victim's traffic: just sit in the same café with them with WiFi. For this reason, potential victims (i.e., everyone) are usually advised to use encrypted connections. It will be more difficult, but still possible, to execute HTTP requests on behalf of the victim to some third-party site (e.g., Google). The attacker must lure the victim to a malicious webpage with a script that will make the request. The web browser will automatically provide the appropriate session cookie.

This seems surprising. If Bob has visited evil.com, can this script on this website really just ask Google to send Bob's password via email to attacker@evil.com? Ну, в теории да, но на самом деле нет. Такой сценарий называется атакой на подделку межсайтовых запросов (Cross-Site Request Forgery, CSRF), and it was popular around the mid-90s. Today, if evil.com someone tries such a trick, Google (or any respectable site) usually responds: "Sure, but your CSRF token for this transaction will be... umm... three trillion and seven. Please repeat that number." Modern browsers implement something called the "same-origin policy," which states that scripts on site A cannot access information sent from website B. Therefore, a script on evil.com can send requests to mrkaran.dev, but cannot read responses or actually complete the transaction.

We should emphasize that if Bob is not using an encrypted connection, all of these protections are meaningless. The attacker can simply read Bob's traffic and recover his Google session cookie. With this cookie, he can just open a new Google tab without logging out of his own browser and impersonate Bob, bypassing the annoying same-origin policy. Unfortunately for the attacker, this is becoming increasingly rare. The internet at large has long declared war on unencrypted connections, and Bob's outgoing traffic is likely encrypted, whether he likes it or not. Moreover, since the protocol was introduced, traffic has also been compressed before encryption; this was a common practice to reduce latency.

This is where CRIME (Compression Ratio Infoleak Made Easy, a simple leak through compression ratio) comes into play. A vulnerability demonstrated in September 2012 by security researchers Juliano Rizzo and Thai Duong. We have already covered all the theoretical background that allows us to understand what they did and how. An attacker can make Bob's browser send requests to Google, and then eavesdrop on the responses over the local network in compressed, encrypted form. So we have:

Here the attacker controls the request and has access to the traffic sniffer, including the size of the packets. Kelsey's fictional scenario has come to life.

Understanding the theory, the authors of CRIME developed an exploit that can steal session cookies for a wide range of sites, including Gmail, Twitter, Dropbox, and Github. The vulnerability affected most modern web browsers, resulting in patches that quietly buried the compression feature in SSL so that it would not be used at all. The only browser protected from the vulnerability was the venerable Internet Explorer, which never used SSL compression at all.

POODLE

In October 2014, Google's security team made waves in the security community. They were able to exploit a vulnerability in the SSL protocol that had been patched over a decade earlier.

It turned out that while servers were running the shiny new TLSv1.2, many had left support for the outdated SSLv3 for backward compatibility with Internet Explorer 6. We have already discussed downgrade attacks, so you can imagine what happened. A well-organized sabotage of the handshake protocol—and servers were ready to revert to good old SSLv3, effectively undoing the last 15 years of research in the field of security.

For historical context, here's a brief summary of the history of SSL up to version 2 by Matthew Green.:

Transport Layer Security (TLS) is the most important security protocol on the internet. [..] Almost every transaction you make online relies on TLS. [..] But TLS has not always been 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 developers gathered all the code printouts and buried them in a secret dump in New Mexico. As a result, the first public version of SSL is actually SSL version 2. It is quite frightful, and [..] it was a product of the mid-90s, which contemporary cryptographers consider to be the “dark ages of cryptography.” Many of the most dreadful cryptographic attacks we know today had yet to be discovered. Consequently, the developers of SSLv2 had to essentially feel their way in the dark, encountering a host of terrible monsters —much to their dismay and our benefit, as the attacks on SSLv2 left invaluable lessons for the next generation of protocols.

After these events, in 1996, the disillusioned company Netscape reworked the SSL protocol from scratch. The result was SSL version 3, which addressed several known security issues of its predecessor.

Fortunately for attackers, "several" does not mean "all." Overall, SSLv3 provided all the necessary building blocks to launch a Vodeney attack. The protocol used a block cipher in CBC mode and an insecure padding scheme (this was fixed in TLS; hence the need for a downgrade attack). If you recall the padding scheme in our initial description of the Vodeney attack, the SSLv3 padding scheme is quite similar.

But, unfortunately for attackers, "similar" does not mean "identical." The SSLv3 padding scheme resembles "N arbitrary bytes followed by the number N." Try in such conditions to choose an imaginary block of encrypted text and go through all the stages of the original Vodeney scheme: you will find that the attack successfully extracts the last byte from the corresponding block of plaintext, but it does not go further. Decrypting every 16th byte of the encrypted text is a neat trick, but it is not a victory.

Faced with failure, the Google team resorted to a last resort: they switched to a more powerful threat model — the one used in CRIME. Assuming that the attacker is a script running in the victim's browser tab and can extract session cookies, the attack is still impressive. Although the broader threat model is less realistic, in the previous section, we already saw that this specific model is feasible.

Given such more powerful capabilities of the attacker, the attack can now continue. Note that the attacker knows where the encrypted session cookie file is displayed in the header and controls the length of the preceding HTTP request. Therefore, they are able to manipulate the HTTP request so that the last byte of the cookie aligns with the end of the block. Now this byte is suitable for decryption. One can simply add one character to the request, and the penultimate byte of the cookie will remain in place, allowing it to be brute-forced in the same way. The attack continues in this manner until the cookie file is fully restored. This is called POODLE: Padding Oracle on Downgraded Legacy Encryption.

DROWN

As we already mentioned, SSLv3 had its flaws, but it was radically different from its predecessor, as the leaky SSLv2 was a product of another era. There, a message could be interrupted midway: I will agree to this only over my dead body turned into I will agree to this; clients and servers could meet on the internet, establish trust, and share secrets in front of an attacker, who could then easily impersonate both parties. There was also an issue with export cryptography that we mentioned when discussing FREAK. It was a cryptographic Sodom and Gomorrah.

In March 2016, a team of researchers from various technical fields came together and made a startling discovery: SSLv2 is still used in security systems. Yes, attackers could no longer downgrade modern TLS sessions to SSLv2 as this vulnerability was closed after FREAK and POODLE, but they can still connect to servers and initiate SSLv2 sessions independently.

You might ask, what do we care about what they are doing? They have a vulnerable session, but it shouldn't affect other sessions or the server's security — right? Well, not exactly. Yes, that should be the case in theory. But no — because the generation of SSL certificates imposes a certain burden, resulting in many servers using the same certificates and, consequently, the same RSA keys for both TLS and SSLv2 connections. Even worse, due to a bug in OpenSSL in this popular SSL implementation, the 'Disable SSLv2' option was essentially not functioning.

This enabled a cross-protocol attack on TLS, which was named DROWN (Decrypting RSA with Obsolete and Weakened eNcryption). This should not be confused with a downgrade attack; the attacker does not need to act as a 'man in the middle' and does not require the client's involvement in an insecure session. Instead, the attackers initiate an insecure SSLv2 session with the server themselves, exploit the weak protocol, and recover the private RSA server key. This key is also valid for TLS connections, and from this point, no TLS security will save it from being compromised.

However, a working attack against SSLv2 is necessary to recover not only specific traffic but also the secret RSA server key. While it is a complicated proposition, researchers could leverage any vulnerability that had been completely patched since SSLv2. Ultimately, they found a suitable option: the Bleichenbacher attack, which we mentioned earlier and will explain in detail in the next article. SSL and TLS are protected from this attack, but certain random SSL features combined with short keys in export-grade cryptography made it possible to exploit a certain implementation of DROWN..

At the time of publication, DROWN vulnerabilities affected 25% of the top websites on the Internet, and the attack could be conducted with modest resources available even for mischievous lone hackers. Extracting the server's RSA key required eight hours of computation and $440, and SSLv2 changed its status from 'deprecated' to 'radioactive.'

Wait, what about Heartbleed?

This is not a cryptographic attack in the sense described above; it is a buffer overflow.

Let's take a break.

We started with some basic methods: brute force, interpolation, downgrade, cross-protocol, and pre-computation. We then looked at one advanced technique, possibly the main component of modern cryptographic attacks: the oracle attack. We spent quite a while understanding it—grasping not only the principle behind it but also the technical details of two specific implementations: the Vaudenay attack on the CBC encryption mode and the Kelsey attack on encryption protocols with pre-compression.

In our review of downgrade attacks with preliminary calculations, we briefly outlined the FREAK attack, which utilizes both methods as targeted websites revert to weak keys and then reuse the same keys. For the next article, we have left the (very similar) Logjam attack, which targets public key algorithms.

Next, we examined three more examples applying these principles. First, CRIME and POODLE: two attacks that relied on an attacker’s ability to inject arbitrary plaintext alongside the target plaintext, then analyze the server’s responses and then, using oracle attack methodology, exploit this scant information to partially recover plaintext. CRIME followed Kelsey’s SSL compression attack, while POODLE, instead, utilized a variant of the Bleichenbacher attack on CBC with the same effect.

We then turned our attention to the cross-protocol DROWN attack, which establishes a connection with the server over the outdated SSLv2 protocol and then recovers the server's secret keys using a Bleichenbacher attack. So far, we have skipped the technical details of this attack; like Logjam, it will have to wait until we have thoroughly studied public key cryptosystems and their vulnerabilities.

In the next article, we will talk about advanced attacks — such as the meet-in-the-middle method, differential cryptanalysis, and birthday attacks. We will take a brief look at attacks via side channels, and then dive into the most enticing topic — public key cryptosystems.

Source: habr.com