# Cryptographic attacks: an explanation for confused minds

At the word "cryptography", some remember their WiFi password, a green lock 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 of recent years with speaking abbreviations (DROWN, FREAK, POODLE ...), stylish logos and a warning urgently update the browser.

Cryptography covers all of this, but the essence is different. The bottom line is between simple and complex. Some things are easy to do, but hard to get back: for example, breaking an egg. Other things are easy to do, but hard to get back when a small, crucial crucial part is missing: for example, to open a locked door when the “critical part” is the key. Cryptography studies these situations and how to use them in practice.

Over the past years, the collection of cryptographic attacks has turned into a zoo of flashy logos full of scientific article formulas and has created a general gloomy feeling that everything is broken. But in fact, many of the attacks are based on several general principles, and the endless pages of formulas often come down to easy-to-understand ideas.

In this series of articles, we will look at various types of cryptographic attacks, with an emphasis on basic principles. In general terms and not quite in that order, but we will tell the following:

• Basic strategies: brute force, frequency analysis, interpolation, downgrade and cross-protocols.
• Brand Vulnerabilities: FREAK, CRIME, POODLE, DROWN, Logjam.
• Advanced strategies: Oracle attacks (Woden attack, Kelsey attack); meet-in-the-middle method, birthday attack, statistical bias (differential cryptanalysis, integral cryptanalysis, etc.).
• Third-party attacks and their close relatives, failure analysis methods.
• Attacks on public-key cryptography: cubic root, Broadcast, related message, Coppersmith attack, Polyg - Hellman algorithm, numerical sieve, Wiener attack, Bleichenbacher attack.

This particular article covers the above material up to Kelsey's attack.

# Basic strategies

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

Some of these attacks have mostly lost relevance and have not been used for many years. Others are old-timers, they still regularly sneak up on unsuspecting cryptosystem developers in the 21st century. We can assume 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

The encryption scheme consists of two parts: 1) the encryption function, which receives 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 creates plaintext. Both encryption and decryption should be easy to compute with the key - and hard without it.

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

Note that there are two implicit assumptions. Firstly, that we know how to perform decryption, that is, how the cryptosystem works. This is a standard assumption when discussing cryptography. Hiding the details of the cipher implementation from intruders may seem like an additional security measure, but as soon as the intruder finds out these details, this extra security is invisibly and irreversibly lost. This is the principle of Kerchhoffs : falling into the hands of the enemy should not cause inconvenience.

Secondly, we assume that the correct key is the only key that will lead to a reasonable decryption. This is also a reasonable assumption; it is executed if the ciphertext is much longer than the key and is well read. As a rule, this happens in the real world, with the exception of huge impractical keys or other frauds, which are better left aside (if you do not like that we have dismissed the explanations, please see Theorem 3.8 here ).

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 - in the end. For example, brute force is enough to crack Caesar 's cipher , an ancient cipher where the key is one letter from the alphabet, which implies a little more than 20 possible keys.

Unfortunately for cryptanalysts, increasing the key size protects against brute force. As the key size grows, the number of possible keys increases exponentially. With modern key sizes, a simple brute force is not at all practical. To understand what we mean, take the fastest known supercomputer in mid-2019: IBM's Summit , with peak performance on the order of 10 17 operations per second. Today, a typical key length is 128 bits, which means 2,128 possible combinations. Enumerating all the keys requires Summit supercomputer to take about 7800 times the age of the universe.

Should brute force be considered a historical curiosity? Not at all: it is an essential ingredient in the cryptanalysis cookbook. Rarely so weak ciphers are found that they can be cracked only with a smart attack, without the use of force to one degree or another. Many successful hacks use the algorithmic method first to weaken the target cipher, and then run brute force.

## Frequency analysis

Most texts are not gibberish. For example, in English texts there are many letters 'e' and articles 'the'; in binary files - a lot of null bytes as a placeholder between pieces of information. Frequency analysis is any attack that exploits 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 with the replacement of all letters. For example, 'g' is replaced by 'h', 'o' by j, Therefore, the word 'go' turns into 'hj'. This cipher is difficult to simple brute force, since there are so many possible lookup tables. If you are interested in math, the effective key length is about 88 bits: this
$log_2 (26!)$ . But frequency analysis usually does the job 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 is common, including at the end of many words, we can tentatively assume that this is the letter e :

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

The XD pair is repeated at the beginning of a few words. In particular, the combination of XDeLe explicitly 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

Further, suppose that L corresponds to r , A - a and so on. You will probably have to make several attempts, but compared to full brute force, this attack restores the source text in the shortest possible time:

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

For some, the solution to such “cryptograms” is a fascinating 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 withstand such an attack using "polyalphabetic substitution." Here, in the encryption process, the letter replacement table changes in complex, but predictable, key-dependent ways. All these ciphers were once considered difficult to crack; and yet a modest frequency analysis ended up defeating 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 could not develop an elegant attack, as shown above; they had to compare well-known pairs of open and encrypted texts (the so-called “plaintext attack”) and even provoking Enigma users to encrypt certain messages with analysis of the result (“attack based on selected plaintext”). But this did not facilitate the fate of the defeated armies of enemies and sunk submarines.

After this triumph, frequency analysis disappeared from the history of cryptanalysis. The ciphers of the modern digital era are designed to work with bits, not letters. More importantly, these ciphers are designed with a gloomy understanding of what later became known as Schneier’s law : anyone can create an encryption algorithm that he himself can’t crack. It is not enough that the encryption system seems complicated: in order to prove its worth, it must go through a ruthless security review from many cryptanalysts who will do everything possible to crack the cipher.

## Preliminary calculations

Take the hypothetical city of Precom Heights with a population of 200,000. In each house of the city there are valuables on average of $30,000, but not more than$ 50,000. The security market in Precom was monopolized by ACME Industries, which produces the legendary Coyote (tm) class door locks. According to expert analysis, only a very complex hypothetical machine can break a Coyote-class lock, the creation of which requires about five years and $50,000 investment. Is the city safe? Most likely no. In the end, a rather ambitious criminal will appear. He will reason like this: “Yes, I will incur large upfront costs. Five years of patient expectation, and$ 50,000. But after finishing work I will have access to all the wealth of this city . If I play my cards correctly, this investment will pay off many times. ”

Similarly, in cryptography. Attacks against a specific cipher are subjected to a ruthless analysis of costs and benefits. If the ratio is favorable, the attack will not occur. But the attacks that immediately attack many potential victims almost always pay off, and in this case, the best design practice is to assume that they started from day one. We have essentially a cryptographic version of Murphy’s law: “Everything that can really break the system will break the system.”

The simplest example of a cryptosystem vulnerable to an attack with preliminary calculations is a cipher with a constant algorithm without using a key. This was the case with the Caesar cipher , which simply shifts each letter of the alphabet three letters forward (the table is looped, so the last letter in the alphabet is encrypted with the third). Here again, the Kerchhoffs principle is manifested: as soon as the system is hacked, it is hacked forever.

The concept is simple. Even a novice cryptosystem developer is likely to be aware of the threat and prepare accordingly. If you look at the evolution of cryptography, such attacks were inappropriate for most ciphers, starting with the first improved versions of Caesar's cipher, right up to the decline of polyalphabetic ciphers. Such attacks returned only with the advent of the modern era of cryptography.

This return is due to two factors. Firstly, finally, quite complex cryptosystems appeared, where the possibility of exploitation after hacking was not obvious. Secondly, cryptography is so widespread that millions of lay people make decisions every day on where and which parts of cryptography to reuse. Some time passed before the experts realized the risks and raised the alarm.

Remember the precomputed attack: at the end of the article we will consider two cryptographic examples from real life, where it played an important role.

## Interpolation

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

I immediately guessed that you came from Afghanistan ... My thoughts were as follows: “This person is a doctor by type, but he has a military bearing. So a military doctor. He had just arrived from the tropics - his face is swarthy, but this is not a natural shade of his skin, since his wrists are much whiter. The emaciated face, obviously, suffered a lot and suffered the disease. He was wounded in his left hand - holds it motionless and a little unnatural. Where, under the tropics, could a British medical doctor suffer hardships and be injured? 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.

From each evidence individually, Holmes could extract very little information. He could come to his conclusion only by examining them all together. The interpolation attack works in a similar way, exploring the known pairs of open and encrypted texts obtained as a result of applying the same key. Separate observations are extracted from each pair, which allow us to draw a general conclusion about the key. All these conclusions are vague and useless until they suddenly reach a critical mass and lead to the only possible conclusion: no matter how incredible it may be, it must be true. After that, either the key is opened, or the decryption process becomes so mature that it can be duplicated.

We 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 the help of a simple cryptosystem, which he learned about from an advertisement in the magazine “Mockery of cryptography”. The system works as follows: Bob selects two numbers that he likes: $M$ and $N$ . From now on, to encrypt any number $x$ he calculates $Mx + N$ . For example, if Bob chose $M = 3$ and $N = 4$ then the figure $2$ encrypted as $3 * 2 + 4 = 10$ .

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

Date: 235/520

Dear Diary,

Today was a good day. After 64 days, I have a date with Alice, who lives in apartment 843 . I really think she can be 26 !

Since we very seriously intend to follow Bob on his date (in this scenario, we are 15 years old), it is crucial to find out 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 $M$ and $N$ , but we know today's date, so we have two pairs of “plaintext - ciphertext”. Namely, we know that $12$ encrypted in $235$ , but $27$ - at $520$ . What we write:





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 $M$ and $N$ without any problems. Each “plaintext-ciphertext” pair imposes a constraint on Bob's key, and two constraints together are enough to completely restore the key. In our example, the answer $M = 19$ and $N = 7$ (at $19x + 7 = 26$ $x = 1$ , so 26 in the diary corresponds to the word 'the one', that is, “the same” - approx. per.) .

Interpolation attacks, of course, are not limited to such simple examples. Each cryptosystem, which comes down 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 as ugly things as possible." Interpolation attacks are probably largely to blame. Bob can either use an elegant mathematical design, or keep the confidentiality of a date with Alice - but alas, usually you can not get both. This will become very clear when we finally move on to the topic of public key cryptography.

In the film “The Illusion of Deception” (2013), a group of illusionists try to trick the entire state of the corrupt insurance magnate Arthur Tressler. To gain access to Arthur's bank account, illusionists must either provide his username and password, or make him personally appear in the bank and take part in the scheme.

Both options are very difficult; the guys are used to performing on stage, and not to participate in intelligence operations. Therefore, they choose the third option: their accomplice calls the bank and pretends to be Arthur. The bank asks several questions for verification of identity, such as the name of the uncle and the name of the first pet; our heroes in advance easily get this information from Arthur with the help of clever social engineering . From now on, excellent password security no longer matters.

(According to a city legend, which we personally checked and confirmed, cryptographer Eli Behem once came across a bank teller who insisted on setting a secret question. When the cashier asked her mother’s grandmother’s name, Beekham began to dictate: “Capital X, little y, three ... ").

It is the same in cryptography if two cryptographic protocols are used in parallel to protect the same asset, while one is much weaker than the other. The resulting system becomes vulnerable to a cross-protocol attack when a weaker protocol is attacked to get to the prize without touching a stronger one.

In some complex cases, it is not enough just to contact the server using a weaker protocol, and the involuntary participation of a legitimate client is required. This can be organized using a so-called downgrade attack. To understand this attack, suppose our illusionists have a more difficult task than in the film. Suppose that a bank employee (cashier) and Arthur had some unforeseen circumstances, as a result of which there was such a dialogue:

Cracker: Hello? This is Arthur Tressler. I would like to reset my password.

Cashier: Great. Please take a look at your personal secret code book, page 28, word 3. All of the following messages will be encrypted with this particular word as a key. PQJGH. LOTJNAM PGGY MXVRL ZZLQ SRIU HHNMLPPPV ...

Cracker: Hey hey, wait a minute. Is it really necessary? Can't we just talk like normal people?

Cashier: I do not advise doing this.

Cracker: I just ... listen, I had a lousy day, okay? I am a VIP client and not in the mood to delve into these stupid code books.

Cashier: Good. If you insist, Mr. Tressler. What do you want?

Cracker: Please, I would like to transfer all my money to the Arthur Tressler National Victims Fund.

(Pause).

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 opening an account.

Cracker: ... I lost him. Is it really necessary? Can't you just approve the deal?

Cashier: None. I'm sorry, Mr. Tressler. Again, this is the security measure you requested. If you want, we can send a new PIN code to the mailbox.

Our heroes postpone the operation. They are listening to several major Tressler transactions, hoping to hear a pin; but each time the conversation turns into an encrypted gibberish before something interesting sounds there. Finally, one day the plan is put into effect. They patiently wait for the moment when Tressler must complete a major transaction by phone, he connects to the line, and then ...

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

Cashier: Great. Please take a look at your personal secret code book, page ...

(The cracker presses a button; the cashier’s voice turns into an inaudible noise).

Cashier: - # @ $# @$ # * @  @ # * will be encrypted with this word as a key. AAAYRR PLRQRZ MMNJK LOJBAN ...

Thressler: Sorry, I did not quite understand. Again? On what page? What is the word?

Cashier: This is the page @ # $@ # *$) # * # @ () # @ $(# @ *$ (# @ *.

Thressler: What?

Cashier: Word number twenty @ $# @$ #% # $. Thressler: Seriously! Enough is enough! You and your security protocol are some kind of circus. I know that you can just talk normally with me. Cashier: I do not advise ... Thressler: And I do not advise you to waste my time. I don’t want to hear more about this until I fix the problems with my telephone line. Can we arrange this deal or not? Cashier: ... yes. Good. What do you want? Thressler: I would like to transfer$ 20,000 to Lord Business Investments, account number ...

Cashier: Just a moment, please. This is a big deal. Please provide your PIN code for large transactions.

Thressler: What? Oh, for sure. 1234.

Here is the fall attack. The weaker protocol, “just speak plainly,” was intended as an option in extreme cases. And yet we are here.

You can ask a question who, in their right mind, will design a real system of the type “safe until asked otherwise”, which is described above. But just as a fictitious bank takes risks to save customers who do not like cryptography, so systems in general often tend to requirements that are indifferent or even openly hostile to security.

This is exactly the story that happened with SSLv2 in 1995. The US government has long begun to consider cryptography as a weapon that is best kept away from external and internal enemies. The code fragments were individually approved for export from the United States, often subject to an intentional weakening of the algorithm. Netscape, the developer of the most popular browser, Netscape Navigator, was given SSLv2 permission only with an initially vulnerable RSA key of 512 bits (and 40 bits for RC4).

By the end of the millennium, the rules had softened and access to modern encryption became widely available. However, clients and servers have for many years supported weakened “export” cryptography due to the same inertia that maintains support for any legacy system. Clients thought they might encounter a server that does not support anything else. Servers did the same. Of course, the SSL protocol dictates that clients and servers should never use a weak protocol when the best is available. But the same premise was valid for Tressler and his bank.

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

The FREAK (also known as "Smack TLS") vulnerability appeared when researchers analyzed the implementation of the client / server TLS and found a curious error. 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 set of ciphers.

, ; .

# C

: , , , - . , , : . — , : CBC .

FREAK, , , . ( ) Logjam, .

. -, CRIME POODLE: , , , , . CRIME SSL, POODLE CBC .

- DROWN, SSLv2, . ; Logjam, , .

— (meet-in-the-middle), « ». , — .

All Articles