At the word “cryptography,” some people remember their WiFi password, the green padlock next to the address of their favorite site, and how difficult it is to get into someone else’s mail. Others recall a series of vulnerabilities in recent years with speaking abbreviations (DROWN, FREAK, POODLE ...), stylish logos and a warning to urgently update the browser.
Cryptography covers it all, but heart in another. It's a fine line between simple and complex. Some things are easy to do but hard to put back, like cracking an egg. Other things are easy to do but hard to put back when a small critical piece is missing: like opening a locked door when the "critical piece" is the key. Cryptography studies these situations and how they can be put to practical use.
In recent years, the collection of cryptographic attacks has become a zoo of flashy logos stuffed with formulas from scientific papers, and has given rise to a general grim feeling that everything is broken. But in fact, many of the attacks are based on a few general principles, and endless pages of formulas often boil down to easy-to-understand ideas.
In this series of articles, we will look at the different types of cryptographic attacks, with a focus on the basic principles. In general terms and not quite in that order, but we will cover the following:
- Basic Strategies: brute force, frequency analysis, interpolation, downgrading and cross protocols.
- "Branded" vulnerabilities: FREAK, CRIME, POODLE, DROWN, Logjam.
- Advanced Strategies: oracle attacks (Waudenay attack, Kelsey attack); meeting-in-the-middle method, birthday attack, statistical bias (differential cryptanalysis, integral cryptanalysis, etc.).
- Side channel attacks and their close relatives, failure analysis methods.
- Attacks on public key cryptography: cube root, broadcast, linked message, Coppersmith attack, Polig-Hellman algorithm, numerical sieve, Wiener attack, Bleichenbacher attack.
This particular article covers the above material up to and including the Kelsey attack.
Basic Strategies
The following attacks are simple in the sense that they can be almost completely explained without too much technical detail. Let's explain each type of attack in the simplest terms, without going into complex examples or advanced use cases.
Some of these attacks are largely obsolete and have not been used for many years. Others are old-timers, still regularly sneaking up on unsuspecting cryptosystem developers in the 21st century. We can consider that the era of modern cryptography began with the advent of IBM DES - the first cipher that withstood all the attacks in this list.
Simple brute force
The encryption scheme consists of two parts: 1) an encryption function that takes a message (plaintext) in combination with a key, and then creates an encrypted message - ciphertext; 2) a decryption function that takes a ciphertext and a key and produces the plaintext. Both encryption and decryption must be easy to compute with the key - and difficult without it.
Suppose we see a ciphertext and try 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 reasonable message.
Note that there are two implicit assumptions here. First, that we know how to perform decryption, that is, how a cryptosystem works. This is a standard assumption when discussing cryptography. Hiding the implementation details of a cipher from attackers may seem like an additional security measure, but once an attacker learns these details, this additional security is imperceptibly and irreversibly lost. Such : falling into the hands of the enemy should not cause inconvenience.
Second, we assume that the correct key is the only key that will lead to a reasonable decryption. This is also a reasonable assumption; it holds if the ciphertext is much longer than the key and is well readable. As a rule, this is what happens in the real world, with the exception of or (if you don't like that we shrugged off explanations, please see Theorem 3.8 ).
Given the above, a strategy arises: check every possible key. This is called brute force, and such an attack is guaranteed to work against all practical ciphers - eventually. For example, brute force is enough to hack , 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 is a good defense against brute force. As the key size grows, the number of possible keys increases exponentially. With today's key sizes, simple brute force is completely impractical. To see what we mean, let's take the fastest known supercomputer as of mid-2019: from IBM, with a peak performance of about 1017 operations per second. Today, the typical key length is 128 bits, which means 2128 possible combinations. It would take the Summit supercomputer about 7800 times the age of the universe to sort through all the keys.
Should brute force be considered a historical curiosity? Not at all: it is a necessary ingredient in the cryptanalysis cookbook. Rarely are ciphers so weak that they can only be broken by a smart attack, without the use of force to some extent. Many successful hacks use an algorithmic method first to weaken the target cipher and then brute force it.
frequency analysis
Most of the lyrics are not gibberish. For example, in English texts there are many letters 'e' and articles 'the'; in binary files, many null bytes as a placeholder between pieces of information. Frequency analysis is any attack that exploits this fact.
The canonical example of a cipher vulnerable to this attack is a simple substitution cipher. In this cipher, the key is a table with the replacement of all letters. For example, 'g' becomes 'h', 'o' becomes j, so the word 'go' becomes 'hj'. This cipher is difficult to brute-force because there are so many possible substitution tables. If you're interested in math, the effective key length is about 88 bits: it's
. But frequency analysis usually gets the job done quickly.
Consider the following ciphertext processed with a simple substitution cipher:
XDYLY ALY UGLY XDWNKE WN DYAJYN ANF YALXD DGLAXWG XDAN ALY FLYAUX GR WN OGQL ZDWBGEGZDO
Since Y occurs frequently, including at the end of many words, we can tentatively assume that this is a letter e:
XDeLe ALe UGLe XDWNKE WN DeAJeN ANF eALXD DGLAXWG XDAN ALe FLeAUX GR WN OGQL ZDWBGEGZDO
Couple XD repeated at the beginning of several words. In particular, the combination XDeLe clearly implies the word these or thereso let's continue:
theLe ALe UGLe thWNKE WN heAJeN ANF eALth DGLAtWG thAN ALe FLeAUt GR WN OGQL ZDWBGEGZDO
Next, suppose that L соответствует r, A — a and so on. It will probably take several attempts, but compared to a full brute force attack, this attack restores the original text in the shortest possible time:
there are more things in heaven and earth horatio than are dream of in your philosophy
For some, solving such “cryptograms” is an exciting hobby.
The idea of frequency analysis is more fundamental than it seems at first glance. And it applies to much more complex ciphers. Throughout history, various cipher designs have attempted to counter such an attack with "polyalphabetic substitution". Here, during the encryption process, the letter replacement table is modified in complex but predictable ways that depend on the key. All of these ciphers were once considered difficult to crack; and yet a modest frequency analysis eventually overpowered them all.
The most ambitious polyalphabetic cipher in history, and probably the most famous, was the Enigma cipher in World War II. It was relatively complex compared to its predecessors, but as a result of long and hard work, British cryptanalysts cracked it using frequency analysis. Of course, they failed to develop an elegant attack like the one shown above; they had to compare known pairs of plaintexts and ciphertexts (the so-called “plaintext attack”) and even provoke Enigma users to encrypt certain messages and analyze the result (“chosen plaintext attack”). But this did not alleviate the fate of the defeated enemy armies and sunk submarines.
After this triumph, frequency analysis disappeared from the history of cryptanalysis. The ciphers of the modern digital age are designed to work with bits, not letters. More importantly, these ciphers were designed with the grim understanding of what later became known as : anyone can create an encryption algorithm that they themselves cannot crack. It is not enough that the encryption system seemed difficult: to prove its worth, it must pass a ruthless security review by many cryptanalysts who will do their best to break the cipher.
Precalculations
Take the hypothetical city of Precom Heights, with a population of 200. Every home in the city holds valuables worth an average of $000, but no more than $30. The security market in Precom has been monopolized by ACME Industries, which makes the legendary Coyote™ class door locks. According to expert analysis, only a very complex hypothetical machine, which requires about five years and a $000 investment, can break a Coyote-class lock. Is the city safe?
Most likely no. In the end, a sufficiently ambitious criminal will appear. He will reason like this: “Yes, I will incur large upfront costs. Five years of patient waiting, and $50. But at the end of the job, I will have access to to all the wealth of this city. If I play my cards right, this investment will pay off many times over.”
The same is true for cryptography. Attacks against a particular cipher are subjected to ruthless cost-benefit analysis. If the ratio is favorable, the attack will not occur. But attacks that act against many potential victims at once almost always pay off, in which case the best design practice is to assume they started from day one. We have essentially a cryptographic version of Murphy's law: "Anything that can really break the system will break the system."
The simplest example of a cryptosystem vulnerable to a precomputation attack is a cipher with a constant algorithm without using a key. This was the case with , which simply shifts each letter of the alphabet three letters forward (the table is looped, so the last letter in the alphabet is encrypted as the third). Here again, the principle of Kerchhoffs comes into play: once a system is broken, it is broken forever.
The concept is simple. Even a novice cryptosystem developer is likely to recognize the threat and prepare accordingly. Looking at the evolution of cryptography, such attacks were out of place for most ciphers, from the first improved versions of the Caesar cipher to the decline of polyalphabetic ciphers. Such attacks only returned with the advent of the modern era of cryptography.
This return is due to two factors. First, finally, quite complex cryptosystems appeared, where the possibility of exploitation after hacking was not obvious. Secondly, cryptography has become so widespread that millions of non-professionals every day decide where and what parts of cryptography to reuse. It took some time before the experts realized the risks and raised the alarm.
Remember the precomputation attack: at the end of the article, we will look at two real-life cryptographic examples where it played an important role.
Interpolation
Here is the famous detective Sherlock Holmes, performing an interpolation attack on the hapless Dr. Watson:
I immediately guessed that you had come from Afghanistan... The course of my thoughts was as follows: “This person is a doctor by type, but he has a military bearing. So, a military doctor. He has just arrived from the tropics - his face is dark, but this is not the natural shade of his skin, since his wrists are much whiter. His face is emaciated - obviously, he has suffered a lot and endured the disease. He was wounded in his left hand - he holds it motionless and a little unnaturally. Where, under the tropics, could an English military doctor suffer hardships and get a wound? Of course, in Afghanistan. The whole train of thought did not take even a second. And so I said that you came from Afghanistan, and you were surprised.
Holmes could extract very little information from each piece of evidence. He could only come to his conclusion by considering them all together. An interpolation attack works similarly by examining known plaintext and ciphertext pairs obtained by applying the same key. Individual observations are extracted from each pair, which allow us to draw a general conclusion about the key. All these inferences are vague and seem useless until they suddenly reach a critical mass and lead to the only possible conclusion: however improbable it may be, it must be true. After that, either the key is revealed, or the decryption process becomes so mature that it can be replicated.
Let's illustrate with a simple example how interpolation works. Suppose we want to read the personal diary of our enemy, Bob. He encrypts every number in his diary with a simple cryptosystem he learned about from an advertisement in a mockery of cryptography magazine. The system works like this: Bob chooses two numbers that he likes: и . From now on, to encrypt any number , it calculates . For example, if Bob chose и , then the number encrypted as .
Suppose we notice on December 28 that Bob is scribbling something in his diary. When he finishes, we discreetly take him and look at the last entry:
Date:
235/520Dear Diary,
Today was a good day. Through
64day I have a date with Alice, who lives in an apartment843. I really think she might be26!
Since we are very serious about following Bob on his date (we are 15 years old in this scenario), it is critical to know the date as well as Alice's address. Fortunately, we notice that Bob's cryptosystem is vulnerable to an interpolation attack. We may not know и , but we know today's date, so we have two plaintext-ciphertext pairs. Namely, we know that encrypted in , - In . What we will write:
Since we are 15 years old, we already know about the system of two equations in two unknowns, which in this situation is enough to find и without too much trouble. Each plaintext-ciphertext pair puts a constraint on Bob's key, and the two constraints together are enough to completely recover the key. In our example, the answer и (at , so that 26 in the diary corresponds to the word 'the one', that is, "the one" - approx. per.).
Interpolation attacks are of course not limited to such simple examples. Every cryptosystem that is reduced to a well-understood mathematical object and a list of parameters is at risk of an interpolation attack - the more understandable the object, the higher the risk.
Beginners often complain that cryptography is “the art of designing things as ugly as possible.” Interpolation attacks are probably largely to blame. Bob can either use elegant mathematical design or keep his date with Alice private - but alas, you usually can't get both. This will become crystal clear when we finally get to the topic of public-key cryptography.
Cross protocol/downgrade
In The Illusion of Deception (2013), a group of illusionists attempt to swindle the entire fortune of corrupt insurance tycoon Arthur Tressler. In order to gain access to Arthur's bank account, the illusionists must either provide his username and password, or have him personally appear at the bank and take part in the scheme.
Both options are very difficult; the guys are used to performing on stage, and not participating in special services operations. So they choose the third possible option: their accomplice calls the bank and pretends to be Arthur. The bank asks several questions to verify identity, such as the name of the uncle and the name of the first pet; our heroes in advance . From this point on, excellent password security no longer matters.
(According to an urban legend that we have personally verified and verified, cryptographer Eli Beeham once encountered a bank teller who insisted on setting up a security question. When the teller asked for his maternal grandmother's name, Beeham began dictating: "Capital X, small y, three... ").
It is the same in cryptography, if two cryptographic protocols are used in parallel to protect the same asset, and one is much weaker than the other. The resulting system becomes vulnerable to a cross-protocol attack when a weaker protocol is attacked in order to get to the prize without touching the stronger one.
In some complex cases, it is not enough just to contact the server using a weaker protocol, but the unwitting participation of a legitimate client is required. This can be done with a so-called downgrade attack. To understand this attack, let's assume that our illusionists have a more difficult task than in the movie. Suppose that a bank employee (cashier) and Arthur had some unforeseen circumstances, as a result of which the following dialogue took place:
Cracker: Hello? This is Arthur Tressler. I would like to recover my password.
Cashier: Great. Please take a look at your personal secret code book, page 28, word 3. All the following messages will be encrypted with this particular word as the key. PQJGH. LOTJNAM PGGY MXVRL ZZLQ SRIU HHNMLPPPV…
Cracker: Hey hey, wait, wait. Is it really necessary? Can't we just talk like normal people?
Cashier: I don't recommend doing this.
Cracker: I just... look, I had a lousy day, okay? I'm a VIP customer and not in the mood to dig through those stupid codebooks.
Cashier: Fine. If you insist, Mr. Tressler. What do you want?
Cracker: Please, I'd like to donate all my money to the Arthur Tressler National Victims Fund.
(Pause).
Cashier: Is it clear now. Please enter your PIN for large transactions.
Cracker: My what?
Cashier: At your personal request, transactions of this size require a PIN for large transactions. This code was given to you when you opened your account.
Cracker:… I lost it. Is it really necessary? Can't you just approve the deal?
Cashier: No. I'm sorry, Mr. Tressler. Again, this is the security measure you asked for. If you want, we can send a new pin code to the mailbox.
Our heroes postpone the operation. They listen in on several of Tressler's large transactions, hoping to hear the pin; but every time the conversation turns into encrypted gibberish before anything interesting is heard. Finally, one day the plan is put into action. They patiently wait for the moment when Tressler has to make a large transaction on the phone, he connects to the line, and then ...
Tressler: Hello. I would like to execute a remote transaction, please.
Cashier: Great. Please take a look at your personal book of secret codes, page...
(The burglar presses the button; the cashier's voice turns into unintelligible noise).
Cashier: — #@$#@$#*@$$@#* will be encrypted with this word as the key. AAAYRR PLRQRZ MMNJK LOJBAN…
Tressler: Sorry, I didn't quite understand. Again? On what page? What word?
Cashier: This page is @#$@#*$)#*#@()#@$(#@*$(#@*.
Tressler: What?
Cashier: Word number twenty @$#@$#%#$.
Tressler: Seriously! Enough already! You with your security protocol are some kind of circus. I know you can just talk to me normally.
Cashier: I do not recommend…
Tressler: I don't advise you to waste my time. I don't want to hear about it anymore until you fix your phone line problems. Can we make this deal or not?
Cashier:… Yes. Fine. What do you want?
Tressler: I would like to transfer $20 to Lord Business Investments, account number…
Cashier: One minute, please. This is a big deal. Please enter your PIN for large transactions.
Tressler: What? Ah, right. 1234.
Here is a downgrade attack. The weaker "just talk straight" protocol was envisioned as option in case of emergency. And yet we are here.
You might be wondering who in their right mind would design a real "safe until you ask otherwise" type of system as described above. But just as a fictitious bank takes risks to keep customers who don't like crypto, so systems in general often lean towards requirements that are indifferent or even outright hostile to security.
This is exactly what happened with the SSLv2 protocol in 1995. The US government has long begun to view cryptography as a weapon best kept away from external and internal enemies. Code snippets have been individually approved for export from the US, often with intentional relaxation of the algorithm. Netscape, the developer of the most popular Netscape Navigator browser, was given permission for SSLv2 only with an inherently vulnerable RSA key of 512 bits (and 40 bits for RC4).
By the end of the millennium, the rules were relaxed and access to modern encryption became widely available. However, clients and servers have supported weakened "export" cryptography for years due to the same inertia that maintains support for any legacy system. Clients thought they might encounter a server that didn't support anything else. The servers did the same. Of course, the SSL protocol dictates that clients and servers should never use a weaker protocol when a better one is available. But the same premise worked for Tressler and his bank.
This theory found its way into two high-profile attacks that shook the security of the SSL protocol one after the other in 2015, both discovered by Microsoft researchers and . First, in February, the details of the FREAK attack were divulged, and three months later, another similar attack called Logjam, which we will discuss in more detail when we move on to attacks on public key cryptography.
Vulnerability (also known as "Smack TLS") emerged when researchers analyzed TLS client/server implementations and found a curious bug. In these implementations, if the client does not even ask to use weak export cryptography, but the server still responds with such keys, the client says “Okay” and switches to a weak cipher suite.
At that time, everyone considered export cryptography to be obsolete and forbidden to use, so the attack came as a real shock and affected many important domains, including the websites of the White House, the US IRS and the NSA. Even worse, it turned out that many vulnerable servers optimized performance by reusing the same keys rather than creating new ones for each session. This made it possible to carry out a precomputation attack after the protocol downgrade: cracking a single key remained relatively expensive ($100 and 12 hours at the time of publication), but the practical cost of attacking a connection was significantly reduced. It is enough to pick up the server key once - and crack the ciphers for all subsequent connections from that moment on.
And before moving on, one advanced attack needs to be mentioned…
Oracle Attack
best known as the father of the cross-platform crypto messenger Signal; but personally we like one of his lesser known innovations - (Cryptographic Doom Principle). Slightly paraphrased, we can say this: "If the protocol performs any cryptographic operation on a message from a potentially malicious source and behaves differently depending on the result, it is doomed." Or in a sharper form: "Do not take information from the enemy for processing, and if you had to, then at least do not show the result."
Leaving aside buffer overflows, command injections, and the like; they are outside the scope of this discussion. Violation of the "doom principle" leads to serious breaks in cryptography due to the fact that the protocol behaves exactly as expected.
For example, let's take a fictitious construct with a vulnerable substitution cipher, and then demonstrate a possible attack. Although we have already seen the attack on the substitution cipher using frequency analysis, it 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. The simple cipher is chosen here only to make the example clearer.
So, Alice and Bob communicate using a simple substitution cipher using a key known only to them. They are very strict about the length of messages: they are exactly 20 characters long. So they agreed that if someone wanted to send a shorter message, they should add some dummy text to the end of the message to make it exactly 20 characters long. After some discussion, they decided that they would only accept the following dummy texts: a, bb, ccc, dddd and so on. Thus, a fictitious text of any required length is known.
When Alice or Bob receives a message, they first check that the message is the correct length (20 characters) and that the suffix is the correct dummy text. If this is not the case, then they respond with an appropriate error message. If the text length and dummy text are OK, the recipient reads the message itself and sends an encrypted response.
During the attack, the attacker impersonates Bob and sends fake messages to Alice. Messages are complete nonsense - the attacker does not have the key, and therefore cannot forge a meaningful message. But since the protocol violates the doom principle, an attacker can still trap Alice so that she reveals the key information, as shown below.
Cracker:
PREWF ZHJKL MMMN. LAAlice: Invalid dummy text.
Cracker:
PREWF ZHJKL MMMN. LBAlice: Invalid dummy text.
Cracker:
PREWF ZHJKL MMMN. LCAlice:
ILCT? TLCT RUWO PUT KCAW CPS OWPOW!
The burglar has no idea what Alice just said, but notes that the symbol C must match abecause Alice received a dummy text.
Cracker:
REWF ZHJKL MMMN. LAAAlice: Invalid dummy text.
Cracker:
REWF ZHJKL MMMN. LBBAlice: Invalid dummy text.
After a number of attempts...
Cracker:
REWF ZHJKL MMMN. LGGAlice: Invalid dummy text.
Cracker:
REWF ZHJKL MMMN. LHHAlice:
TLQO JWCRO FQAW SUY LCR C OWQXYJW. IW PWWR TU TCFA CHUYT TLQO JWFCTQUPOLQZ.
Again, the cracker has no idea what Alice just said, but notes that H must match b because Alice assumed dummy text.
And so on, until the attacker knows the meaning of each character.
At first glance, the method resembles a matched-plaintext attack. In the end, the attacker picks up the ciphertexts, and the server obediently processes them. The main difference that makes these attacks viable in the real world is that the attacker doesn't need access to the actual decryption - a server response, even one as innocuous as "Incorrect dummy text", is sufficient.
While this particular attack is instructive, one should not 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 is how Alice reacts differently based on the properties of the plaintext, and does so without verifying that the corresponding ciphertext is actually received from a trusted party. Thus, Alice allows an attacker to squeeze secret information from her answers.
There are many things that can be changed in this scenario. The symbols that Alice reacts to, or the very difference in her behavior, or even the cryptosystem used. But the principle will remain the same, and the attack as a whole will remain viable in one form or another. The underlying implementation of this attack helped uncover several security bugs, which we'll look at shortly; but first there are some theoretical lessons to be learned. How to use this fictitious "Alice scenario" in an attack that can work on a real modern cipher? Is it possible at all, even in theory?
In 1998, the Swiss cryptographer Daniel Bleichenbacher answered this question in the affirmative. He demonstrated an oracle attack on the widely used RSA public key cryptosystem using a specific message scheme. In some implementations of RSA, the server responds with different error messages, depending on whether the plaintext matches the scheme or not; this was enough to carry out the attack.
Four years later, in 2002, French cryptographer Serge Vaudenay demonstrated an oracle attack almost identical to that described in Alice's scenario above - except that instead of a fictitious cipher, he cracked a whole respectable class of modern ciphers that people really use. In particular, Vaudeney's attack targets ciphers with a fixed input size ("block ciphers") when they are used in the so-called "CBC cipher mode" and with a certain popular padding scheme basically equivalent to that of Alice's scenario.
Also in 2002, American cryptographer John Kelsey co-authored - proposed various oracle attacks on systems that compress messages and then encrypt them. Most notable among these was an attack that exploited the fact that it is often possible to deduce the original plaintext length from the ciphertext length. In theory, this allows for an oracle attack that recovers portions of the original plaintext.
Next, we provide a more detailed description of the Vaudeney and Kelsey attacks (we will give a more detailed description of the Bleichenbacher attack when we move on to attacks on public key cryptography). Despite our best efforts, the text becomes somewhat technical; so if the above is enough for you, skip the next two sections.
Vaudeney's attack
To understand the Vaudeney attack, we first need to talk a little more about block ciphers and cipher modes. A "block cipher" is, as already mentioned, a cipher that takes a key and an input of a certain fixed length ("block length") and produces an encrypted block of the same length. Block ciphers are widely used and are considered relatively secure. Considered the first modern cipher, the now retired DES was a block cipher. As mentioned above, 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. Obviously, modern cryptography requires you to work with larger inputs, and this is where encryption modes come in. The encryption mode is essentially a hack: it's a way to somehow apply a block cipher that only takes input of a certain size to an input of arbitrary length.
Vaudeney's attack targets the popular CBC (Cipher Block Chaining) mode of operation. The 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 signifies the XOR (exclusive OR) operation. For example, the second ciphertext block is received:
- By XORing the second block of plaintext with the first block of ciphertext.
- Encrypting the received block with a block cipher using the key.
Since CBC uses the binary XOR operation so heavily, let's take a moment to recall some of its properties:
- Idempotency:
- Commutability:
- Associativity:
- Self-reversibility:
- Byte: byte n of = (byte n from ) (byte n from )
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 famous и , then we can rely on the aforementioned properties above to solve the equation for . By XORing both sides of the equation with , we get . In a moment it will all become very relevant.
There are two minor differences and one major difference between our Alice scenario and Vaudeney's attack. Two minor ones:
- In the script, Alice expected the plaintexts to end with the characters
a,bb,cccand so on. In a Vaudeney attack, the victim instead expects plaintexts to end N times with the N byte (i.e. hexadecimal 01 or 02 02 or 03 03 03 and so on). This is a purely cosmetic difference. - In Alice's script, it was easy to tell if Alice accepted the message by the response "Incorrect dummy text". In Vaudeney's attack, more analysis is required and precise implementation on the victim's side is important; but for the sake of brevity, let's take it for granted that this analysis is still possible.
Main difference:
- Since we are not using the same cryptosystem, the relationship between attacker-controlled ciphertext bytes and secrets (key and plaintext) will obviously be different. Therefore, an attacker will have to use a different strategy when creating ciphertexts and interpreting server responses.
This major difference is the last piece of the puzzle to understand Vaudeney's attack, so let's think for a moment about why and how an oracle attack on the CBC could even be staged.
Suppose we are given a CBC ciphertext of 247 blocks and we want to decrypt it. We can send fake messages to the server, just like we used to send fake messages to Alice. The server will decrypt messages for us, but will not show the decryption - instead, again, as in the case of Alice, the server will report only one bit of information: does the plaintext have valid padding or not.
Consider 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. By analogy, if we can find such a connection for the CBC script, we could extract some secret information there as well.
Luckily, there are indeed relationships that we can use. Consider the output of the block cipher decryption end call and denote this data as . We also denote plaintext blocks and ciphertext blocks . Take another look at the CBC chart and notice what happens:
Let's call this the "CBC equation".
In Alice's scenario, by controlling the ciphertext and observing that information about the corresponding plaintext was leaked, we were able to mount an attack that restored the third term of the equation, the key. In the CBC scenario, we also control the ciphertext and observe information leaks on the corresponding plaintext. If the analogy holds, we can get information about .
Let's assume we did restore what then? Well, then we can output the entire last block of plaintext at once () by simply entering (which we have) and
received into the CBC equation.
So, we are optimistic about the overall plan of attack, and it's time to work out the details. Pay attention to exactly how information about the plaintext is leaked on the server. In Alice's scenario, the leak was due to Alice responding with the correct message only if $inline$text{SIMPLE_SUBSTITUTION}(text{ciphertext},text{key})$inline$ ended with the line a (or bb, and so on, but the chances of these conditions being randomly triggered were very small). Similar to CBC, the server accepts padding if and only if ends in hexadecimal 01. So 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 XOR byte property:
We know the first and third term. And we have already seen that this allows you to restore the remaining member - the last byte from :
This also gives us the last byte of the final plaintext block via the CBC equation and the byte-wise property.
We could end there and be content with attacking a theoretically strong cipher. But in fact, we can do much more: we can actually restore the entire text. This requires a certain trick that was not in Alice's original script and is not a prerequisite for an oracle attack, but the method is still worth learning.
To understand it, first note that as a result of deriving the correct value of the last byte we have a new ability. Now, when forging ciphertexts, we can control the last byte of the corresponding plaintext. Again, this is due to the CBC equation and the byte-wise property:
Since we now know the second term, we can use our control over the first to control the third. We just calculate:
Previously, we couldn't do this because we didn't have the last byte yet. .
How will this help us? Let's assume that now we will create all ciphertexts so that in the corresponding plaintexts the last byte is equal to 02. Now the server only accepts padding if the plaintext ends with 02 02. Since we fixed the last byte, this will only happen if the penultimate byte of the plaintext is also 02. We keep sending fake ciphertext blocks, changing the penultimate byte, until the server accepts padding for one of them. At this point we get:
And we restore the penultimate byte just like the last one restored. We continue in the same spirit: we correct the last two bytes of the plaintext to 03 03, repeat this attack for the third byte from the end, and so on, eventually completely restoring .
What about the rest of the text? Note that the value is actually $inline$text{BLOCK_DECRYPT}(text{key},C_{247})$inline$. We can put any other block instead , and the attack will still be successful. In fact, we can ask the server to make $inline$text{BLOCK_DECRYPT}$inline$ for any data. At this point, the game is over - we can decrypt any ciphertext (look again at the CBC decryption diagram to see this; and note that the IV vector is publicly available).
This particular method plays a crucial role in the oracle attack that we will encounter later.
Kelsey attack
The congenial John Kelsey laid out the principles behind many possible attacks, not just the details of a particular attack on a particular cipher. His is a study of possible attacks on encrypted compressed data. Did you think that information alone was not enough to carry out an attack, that the data was compressed before encryption? It turns out that's enough.
This surprising result is due to two principles. First, there is a strong correlation between the length of the plaintext and the length of the ciphertext; for many ciphers exact equality. Secondly, when compression is performed, there is also a strong correlation between the length of the compressed message and the degree of "noisiness" of the plaintext, that is, the proportion of non-repeating characters (the technical term is "large entropy").
To see the principle in action, consider two plain texts:
Plaintext 1:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAPlaintext 2:
ATVXCAGTRSVPTVVULSJQHGEYCMQPCRQBGCYIXCFJGJ
Suppose both plaintexts are compressed and then encrypted. You get two resulting ciphertexts and have to guess which ciphertext corresponds to which plaintext:
Ciphertext 1:
PVOVEYBPJDPVANEAWVGCIUWAABCIYIKOOURMYDTACiphertext 2:
DWKJZXYU
The answer is clear. Among the plaintexts, only plaintext 1 could be compressed to the meager 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 insane.
Kelsey further points out that under certain unusual circumstances this principle can also be used to launch an oracle attack. Specifically, it describes how an attacker can recover the secret plaintext if they can get the server to encrypt the form data (the plaintext followed by as long as he controls and can somehow check the length of the encrypted result.
Again, as in other oracle attacks, we have a ratio:
Again, we control one member (), we see a small leak of information about another member (ciphertext) and try to recover the last one (plaintext). Despite the analogy, this is a somewhat unusual situation compared to other oracle attacks we've seen.
To illustrate how such an attack could work, let's use a fictitious compression scheme we just came up with: TOYZIP. It looks for lines of text that have already appeared before in the text and replaces them with three placeholder bytes that indicate where to find the earlier instance of the line and how many times it occurs there. For example, the line helloworldhello can be compressed into helloworld[00][00][05] 13 bytes long compared to the original 15 bytes.
Suppose an attacker is trying to recover the plaintext of a form password=..., where the password itself is unknown. According to the Kelsey attack model, an attacker could ask the server to compress and then encrypt messages of the form (plaintext followed by ), Where - arbitrary text. When the server is done, it reports the length of the result. The attack goes like this:
Cracker: Please compress and encrypt the plaintext without any padding.
Server: The length of the result is 14.
Cracker: Please compress and encrypt the plaintext to which is added
password=a.Server: The length of the result is 18.
The cracker notes: [original 14] + [three bytes that replaced password=🇧🇷 a
Cracker: Please compress and encrypt the plaintext to which is added
password=b.Server: The length of the result is 18.
Cracker: Please compress and encrypt the plaintext to which is added
password=с.Server: The length of the result is 17.
The cracker notes: [original 14] + [three bytes that replaced password=c]. This assumes that the original plaintext contains the string password=c. That is, the password starts with a letter c
Cracker: Please compress and encrypt the plaintext to which is added
password=сa.Server: The length of the result is 18.
The cracker notes: [original 14] + [three bytes that replaced password=с🇧🇷 a
Cracker: Please compress and encrypt the plaintext to which is added
password=сb.Server: The length of the result is 18.
(… Some time later…)
Cracker: Please compress and encrypt the plaintext to which is added
password=со.Server: The length of the result is 17.
The cracker notes: [original 14] + [three bytes that replaced password=co]. By the same logic, the attacker concludes that the password begins with the letters co
And so on until the entire password is recovered.
It is pardonable for the reader to think that this is a purely academic exercise and that such an attack scenario would never occur in the real world. Alas, as we will soon see, it is better not to promise cryptography.
Brand vulnerabilities: CRIME, POODLE, DROWN
Finally, after a detailed study of the theory, we can see how these methods are applied in real cryptographic attacks.
CRIME
If the attack targets the victim's browser and network, some will be easier and some more difficult. For example, it is easy to see the traffic of the victim: it is enough to sit with her in the same cafe with WiFi. For this reason, potential victims (i.e. everyone) are generally advised to use an encrypted connection. It will be more difficult, but still possible, to make HTTP requests on behalf of the victim to some third-party site (for example, Google). The attacker needs to lure the victim to a malicious web page with a script that will make the request. The web browser will automatically provide the appropriate session cookie.
It seems amazing. If Bob went to evil.com, can the script on this site just ask Google to email Bob's password to [email protected]? Well, in theory yes, but in reality no. This scenario is called a cross-site request forgery attack (, CSRF), and it was popular around the mid-90s. Today if evil.com tries such a trick, Google (or any self-respecting site) will usually respond with “Great, but your CSRF token for this transaction will be… mmm… три триллиона и семь. Please repeat this number." Modern browsers enforce something called a "same-origin policy" whereby scripts on site A do not have access to information sent by site B. Therefore, the script on evil.com can send requests to google.com, but cannot read responses or actually complete the transaction.
We must emphasize that if Bob is not using an encrypted connection, all these protections are meaningless. The attacker can simply read Bob's traffic and recover the Google session cookie. With this cookie, he will simply open a new Google tab without leaving his own browser and impersonate Bob without encountering the annoying same-origin policies. But, unfortunately for the cracker, this is becoming less and less common. The Internet as a whole has long declared war on unencrypted connections, and Bob's outgoing traffic is probably encrypted whether he likes it or not. In addition, from the very beginning of the implementation of the protocol, traffic also shrank before encryption; this was a common practice to reduce latency.
Here comes into play (Compression Ratio Infoleak Made Easy, simple leak through compression ratio). A vulnerability that was shown in September 2012 by security researchers Giuliano Rizzo and Thai Duong. We have already analyzed the entire theoretical base, which allows us to understand what they did and how. An attacker could have Bob's browser send requests to Google and then listen to the responses on the local network in a compressed, encrypted form. Therefore we have:
Here the attacker controls the request and has access to the traffic sniffer, including the size of the packets. Kelsey's fictional script came to life.
Understanding the theory, the authors of CRIME created 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 the release of patches that silently buried the compression feature in SSL so that it was not used at all. The only one protected from the vulnerability was the venerable Internet Explorer, which never used SSL compression at all.
POODLE
In October 2014, the Google security team caused a stir in the security community. They were able to exploit a vulnerability in the SSL protocol that was patched over a decade ago.
It turns out that while the servers are running the great new TLSv1.2, many have left support for the legacy SSLv3 for backwards compatibility with Internet Explorer 6. We've already talked about downgrade attacks, so you can imagine what's going on. A well-organized sabotage of the handshake protocol and the servers are ready to go back to the good old SSLv3, essentially canceling the last 15 years of security research.
For historical context, :
Transport Layer Security (TLS) is the most important security protocol on the Internet. [..] almost every transaction you make on the internet depends on TLS. [..] But TLS wasn't always TLS. The protocol began its life in called "Secure Sockets Layer" or SSL. Rumor has it that the first version of SSL turned out to be so terrible that the developers collected all the printouts of the code and buried it in a secret dump in New Mexico. As a consequence, the first public version of SSL is actually . It's pretty ugly, and [..] it was a product of the mid-90s, which modern cryptographers consider as "". Many of the most heinous cryptographic attacks we know about today have yet to be discovered. As a result, the developers of the SSLv2 protocol had to essentially grope their way in the dark, and they ran into — to their chagrin and to our benefit, as the attacks on SSLv2 left invaluable lessons for the next generation of protocols.
After these events, in 1996, a frustrated Netscape company redesigned the SSL protocol from scratch. The result was SSL version 3, which .
Fortunately for crackers, "a few" does not mean "all". Overall, SSLv3 provided all the necessary building blocks to launch a Wodenay 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 remember the padding scheme in our original description of Vaudeney's attack, the SSLv3 scheme is very similar.
But, unfortunately for crackers, "similar" does not mean "identical". The SSLv3 padding scheme is "random N bytes followed by a number N". Try under such conditions to choose an imaginary ciphertext block and go through all the steps of Vaudeney's original scheme: you will find that the attack successfully extracts the last byte from the corresponding plaintext block, but does not go any further. Deciphering every 16th byte of the ciphertext is a great trick, but it's not a win.
Faced with failure, the Google team resorted to an extreme option: they switched to a more powerful threat model - the one used in CRIME. Assuming the attacker is a script running on the victim's browser tab and can extract session cookies, the attack is still impressive. Although the broader threat model is less realistic, we have already seen in the previous section that this particular model is feasible.
Given these more powerful cracker capabilities, the attack can now continue. Note that the attacker knows where the encrypted session cookie appears in the header and controls the length of the HTTP request that precedes it. Therefore, it is able to manipulate the HTTP request to align the last byte of the cookie according to the end of the block. Now this byte is suitable for decryption. You can simply add one character to the request, and the penultimate byte of the cookie will remain in the same place and is suitable for selection by the same method. The attack continues in this way until the cookie is completely restored. It's called POODLE: Padding Oracle on Downgraded Legacy Encryption.
DROWN
As we already mentioned, SSLv3 had flaws, but it was fundamentally different from its predecessor, since the leaky SSLv2 was a product of another era. There it was possible to interrupt the message in the middle: соглашусь на это только через мой труп turned into соглашусь на это; the client and server could meet on the Internet, establish trust, and exchange secrets in front of the attacker, who then easily impersonated both. There is also the problem with export cryptography, which we mentioned when reviewing FREAK. These were the cryptographic Sodom and Gomorrah.
In March 2016, a team of researchers from various technical fields got together and made a startling discovery: SSLv2 is still used in security systems. Yes, attackers could no longer downgrade modern TLS sessions to SSLv2 since that hole was closed after FREAK and POODLE, but they can still connect to servers and initiate SSLv2 sessions on their own.
You ask, what do we care what they do there? They have a vulnerable session, but that shouldn't affect other sessions or server security - right? Well, not quite. Yes, that's how it should be in theory. But no - because generating SSL certificates imposes a certain burden, as a result of which many servers use the same certificates and, as a result, the same RSA keys for TLS and SSLv2 connections. To make matters worse, due to an OpenSSL bug, the "Disable SSLv2" option was actually not working in this popular SSL implementation.
This made possible a cross-protocol attack on TLS, which was called (Decrypting RSA with Obsolete and Weakened eNcryption). Recall that this is not the same as a short attack; the cracker does not need to act like a "man in the middle" and does not need to involve the client in order to participate in an insecure session. Attackers simply initiate an insecure SSLv2 session with the server themselves, attack the weak protocol, and recover the server's private RSA key. This key is also valid for TLS connections, and from now on, no amount of TLS security will save it from being hacked.
But to crack, you need a working attack against SSLv2, which allows you to recover not only specific traffic, but also the secret RSA server key. Although this is a difficult setup, the researchers could have chosen any vulnerability that was completely closed after SSLv2. Ultimately, they found a suitable option: the Bleichenbacher attack, which we mentioned earlier and which we will explain in detail in the next article. SSL and TLS are immune to this attack, but some random SSL features, combined with short keys in export class cryptography, have made it possible .
At the time of publication, DROWN vulnerabilities affected 25% of the Internet's top sites, and the attack could be carried out with modest resources available even to mischievous lone hackers. It took eight hours of computing and $440 to extract the server's RSA key, and SSLv2 changed its status from "obsolete" to "radioactive".
Wait, what about Heartbleed?
This is not a cryptographic attack in the sense described above; it's a buffer overflow.
Let's take a break
We started with some basic methods: brute force, interpolation, downgrading, cross protocol, and precomputation. We then looked at one advanced technique, perhaps the main component of modern cryptographic attacks: the oracle attack. We dealt with it for quite a long time - and understood not only the principle at the core, but also the technical details of two specific implementations: Vaudeney's attacks on the CBC encryption mode and Kelsey's attacks on precompression encryption protocols.
In an overview of downgrade and precomputation attacks, we briefly outlined the FREAK attack, which uses both methods as the target sites downgrade to weak keys and then reuse the same keys. For the next article, we left the (very similar) Logjam attack, which targets public key algorithms.
We then looked at three more examples of the application of these principles. First, CRIME and POODLE: two attacks that relied on the attacker's ability to inject arbitrary plaintext alongside the target plaintext, then examine the server's responses and then, using oracle attack methodology, use this meager information to partially recover the plaintext. CRIME went the route of attacking Kelsey on SSL compression, while POODLE instead used a variant of Vaudeney's attack on CBC with the same effect.
Then we turned our attention to the cross-protocol DROWN attack, which establishes a connection with the server using the outdated SSLv2 protocol, and then recovers the server's secret keys using the Bleichenbacher attack. For now, we have skipped the technical details of this attack; like Logjam, it will have to wait until we have a good understanding of public key cryptosystems and their vulnerabilities.
In the next article, we'll talk about advanced attacks such as the meet-in-the-middle method, differential cryptanalysis, and the birthday attack. Let's make a short foray into side-channel attacks, and then we'll get to the yummy part, public-key cryptosystems.
Source: habr.com