Cryptanalysis

A sophisticated adversary might want to try to access the plaintext of an encrypted message by using various techniques to break the encryption – a process known as cryptanalysis. In this lesson, we will review a few of these techniques, including non-technical approaches, brute force decryption, dictionary attacks, algorithm weaknesses, and the potential future use of quantum computers.

Rubber Hoses and Social Engineering

Encryption works on the premise that it is computationally expensive to try to decrypt ciphertext back into its original plaintext without access to the encryption key. While there are technical ways to try to find the encryption key, it is often more convenient to use a non-technical approach that exploits the weakest link in any encryption system: the carbon-based life form sitting at the keyboard. Let’s consider two different approaches that are designed to get a person to reveal their encryption key.

The first approach is called rubber-hose cryptanalysis (Figure 1) and is highly effective if an adversary has physical access to either party in an encrypted message exchange. With this technique, the adversary simply forces the party to give up the private encryption key. In the simplest case, this force can be applied by means of physical violence – literally beating the person with a rubber hose (and the origin of the term). It is also possible to compel a person using other means, such as imprisoning them until they reveal the key. In the United Kingdom, for example, the Regulation of Investigatory Powers Act of 2000 provides the police with a legal rubber hose to use when they want to decrypt any encrypted data, since a person refusing to decrypt the data on demand can be imprisoned for up to 5 years and fined.¹

A second technique for obtaining a private key is to use a social engineering attack. In this type of attack, the adversary poses as someone who has some legitimate reason to access the secret message. The adversary then tricks one of the parties in the secret message exchange into revealing either the key or the original plaintext. If an encryption key has been shared with a third party, a social engineering attack could be directed toward that third party instead of to one of the people who are directly communicating with each other. Systems that use key escrow, in which a third party keeps a copy of an encryption key, are especially vulnerable to this type of attack.³

Brute-Force Decryption

If an adversary cannot extract a key using human intelligence, there are techniques for recovering an original plaintext message when only the ciphertext is known. One of these techniques is brute-force decryption, which simply takes the ciphertext and runs a decryption algorithm against it repeatedly. Each time, the attacker guesses a different possible value for the key. If the encryption key is weak, the adversary will eventually guess the correct key, allowing the ciphertext to be decrypted back into plaintext.

Good encryption keys and well-designed encryption systems that are resistant to brute-force attacks can be used to mitigate this threat. For example, if we consider just the “correct horse battery staple” phrase from Figure 1, we have an example of an encryption key that is drawn from a set of 27 possible values: the 26 lowercase letters a-z and a space. Since the phrase is 28 characters long, the number of possible combinations is 27²⁸ or 1.197 x 10⁴⁰. An attacker trying to brute-force this password while trying 1 billion (10⁹) passwords per second would have a 50% chance of guessing it correctly in 5.986 x 10³⁰ seconds or 1.898 x 10²³ years. For comparison, a human who lives to be 90 years old lives a total of 9 x 10¹ years, and the Sun might consume the Earth in another 1 x 10⁹ years or so.

Dictionary Attacks

In actuality, using the phrase “correct horse battery staple” from Figure 1 would be a terrible choice for an encryption passphrase (or a password, for that matter). The reason is that the typical adversary isn’t going to use a brute-force attack, owing to its lack of feasibility. Instead, the adversary is going to use whatever open-source intelligence (OSINT) and human intelligence (HUMINT) is available to develop a more targeted type of attack. In the case of a symmetric encryption algorithm, where the key might be made of human language words, the adversary will employ a dictionary attack.

In a dictionary attack, whole words are rearranged into different orders to reduce the total search space for the encryption key. If the dictionary is large enough and sufficiently accurate, breaking the encryption in a reasonable amount of time becomes feasible, especially if fast hardware is used to try multiple combinations in parallel.⁴

Cryptographic Vulnerabilities

Another way to attack encryption is to try to break the encryption algorithm itself. If a weakness in the algorithm can be found, it becomes possible for an adversary to decrypt messages without having to use brute-force or dictionary attacks to try to guess the encryption key. When the algorithm itself is broken in some way, finding out the key might not be necessary. Instead, the encryption might be reversed directly, yielding the plaintext.

Some encryption systems designed with input from government agencies have been found to contain intentional weaknesses to make them vulnerable to certain exploits.⁵ The United States National Security Agency is known to have “improved” the commercial security of IBM’s Data Encryption Standard (DES) while plausibly leaving themselves a back door to decrypt traffic by reducing the default key size.⁶

Post-Quantum Cryptography

Our computer systems today are really giant collections of digital switches, where each switch is either on (1) or off (0). Each of these digital switches forms a single bit inside the computer, and a bit is the smallest unit of data on which a computer operates. Researchers are working on another kind of computer called a quantum computer, which operates on quantum bits (or qubits) that store some combination of 0 and 1 at the same time. When put into connected groups, qubits exist in a state of superposition, in which multiple possible combinations of 0 and 1 can be represented at the same time. Due to the phenomenon of quantum entanglement, members of the group change state in a predictable way if the state of a single qubit is changed. As a consequence, the addition of qubits to a quantum computer exponentially increases its power.⁷

If quantum computers can be made reliable and practical enough in the future (which is not a guarantee), they could be used to brute-force encryption keys of conventional encryption algorithms quickly enough to recover the plaintext within a practical amount of time. Standard encryption algorithms in use today are generally thought to be vulnerable to quantum computers, and information stored with today’s algorithms might one day be decrypted this way. For this reason, researchers are working to develop post-quantum cryptography, which contains set of cryptographic algorithms designed to resist quantum attacks. Switching to post-quantum algorithms will be necessary in the relatively near future, since harvest now, decrypt later attacks against encrypted data already exist and work on the principle of collecting ciphertext now with the expectation of having more practical tools to attack it in the future.⁸

Notes and References