Cryptanalysis explained

Cryptology can be split into two parts, cryptography, and cryptanalysis. Cryptography focuses on creating encryption protocols, while cryptanalysis analyzes the cryptographic algorithms in an attempt to break them. Cryptanalysis isn’t necessarily used to mount an attack, per se. Cryptanalysis is a bit like the Force in Star Wars in that one can use it for good or evil. It has a dark side and a light side.

The dark side would use cryptanalysis to access and exploit encrypted messages or data by “breaking” the encryption. On the other hand, the light side will use cryptanalysis to determine whether encryption protocols and ciphers are secure and to identify vulnerabilities to strengthen the system rather than break it.

In this article, we will look at what cryptanalysis is, how it works, and the different methods used.

What is cryptography?

To understand how cryptanalysis works, we first need to familiarize ourselves with certain concepts.

Cryptography is essentially the process of converting ordinary text (plain text) into unreadable text (ciphertext) and vice-versa. It rewrites data in an unintelligible form that only the sender and the receiver can decrypt and read. Cryptography protects data from theft or alteration and is also used for user authentication.

While that’s pretty much the lowdown on cryptography, modern cryptography goes beyond simply converting plain text into ciphertext and needs to account for the following:

Confidentiality: The messages cannot be read by anyone aside from the sender and the receiver.

Integrity: The information contained in the messages cannot be altered.

Non-repudiation: Once a message is sent, the sender cannot deny that they transmitted the message at a later time.

Authentication: The sender and the receiver can confirm each other’s identity.

Main types of cryptography

There are three main types of cryptography used today:

• Symmetric key cryptography
• Asymmetric key cryptography
• Hash functions

Let’s take a quick look at each of these.

Symmetric key cryptography

Symmetric key cryptography is an encryption protocol in which both the sender and the receiver use a single shared key for both the encryption and the decryption of messages. This system is also referred to as private or secret-key cryptography. AES (Advanced Encryption System) is the most widely used symmetric-key encryption protocol.

The major drawback of symmetric key encryption is that the two parties must exchange the key through secure means. If the key is compromised, the entire protocol is compromised as the one key can be used for encryption and decryption.

Symmetric key protocols:

• AES
• DES
• Triple DES
• RC2
• RC4
• RC5
• IDEA
• Blowfish

Asymmetric key cryptography

Asymmetric Key Cryptography is a more secure approach to encryption than symmetric key cryptography. Each user possesses a pair of keys in this protocol: a private key and a public key.

As its name implies, the private key is kept secret, but the public key is distributed to the other users. Using an intended recipient’s public key, any user can encrypt a message and send it to the owner of that key. From that point, that encrypted message can only be decrypted with the receiver’s (the intended recipient) private key.

Asymmetric key cryptography is also referred to as public-key cryptography and is much more secure than symmetric key cryptography. RSA is the most popular and widely used asymmetric algorithm.

Asymmetric key protocols:

• RSA
• DSA
• PKCs
• Elliptic curve cryptography

Hash functions

A Hash function is a cryptography algorithm that takes an arbitrary length input and produces a fixed-length output. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes.

Hashing is a one-way operation, meaning that you cannot convert the hash or digest back to its original input. Hashing itself doesn’t use any keys, but it is used within symmetric and asymmetric key cryptography to store temporary values—hashing is one of the building blocks of modern cryptography. MD5 and SHA are the most widely used hash functions, though SHA1 and MD5 are now deprecated and shouldn’t be used anymore.

Hashing algorithms:

• Message Digest 5 (MD5)
• SHA (Secure Hash Algorithm)
• RIPEMD
• Whirlpool

A straightforward illustration of cryptanalysis

To understand the modus operandi of cryptanalysis, here’s an elementary example, using a basic substitution cipher.

Say we want to perform cryptanalysis on the following ciphertext: W STNB XTV. The first thing a cryptanalyst would look for is frequency: frequency of words and frequency of letters.

Word frequency

If you’re given a phrase in which one of the words is one letter long, it’s reasonable to assume that the corresponding word is a popular one-letter word like “I” or “a”. Likewise, a frequent two-letter word has a good chance of being “on,” “it,” or “as” etc. And a frequent three-letter word could be “the.”

Letter frequency

The most common letters in the English language are e, t, a, o, i, n. The least common letters in English are j, x, q, z.

If we have ciphertext in which the letter X is the most frequent letter, we can reasonably assume X stands for E. We may be wrong, so this will involve some trial and error. And that trial and error is cryptanalysis.

If we assume that W stands for the common word I, the following word has an excellent chance of being a verb. That further limits the possibilities of what the next word might be. By trying different substitutions until you can deduce word sequences that make sense, you’ll eventually go from W STNB XTV to I LOVE YOU. And once you’ve done that, you’ve performed cryptanalysis.

Cryptanalysis attack examples

There are different ways to weaponize cryptanalysis into an attack. Here are some of the most notable cryptanalysis techniques that cybersecurity analysts should know.

Known-plaintext attack (KPA)

In a known-plaintext attack, the attacker has access to the ciphertext and its corresponding plain text. The attacker uses this knowledge in an attempt to guess the secret keys or codebooks, allowing the attacker to decrypt the rest of the messages.

Known-plaintext attacks are most effective when used on less complex ciphers, such as simple substitution ciphers, in which each letter is substituted with a fixed substitute character, as in our example above.

Given that most modern ciphers are much more complex than simple substitution, odds are this cryptanalysis attack won’t get you very far.

Chosen-plaintext attack (CPA)

In a chosen-plaintext attack, the attacker sends plain text to be encrypted and analyzes the returned ciphertext in an attempt to deduce the private key used for decryption. This attack is feasible against asymmetric key cryptography because the public key, the key used for encrypting the messages, is, as its name states, public.

Ciphertext-only attack (COA)

A ciphertext-only attack (COA) or known ciphertext attack is a cryptanalysis attack in which the attacker only has access only to ciphertext. Even without access to the plaintext, the attacker can still know something about the plaintext. This could be the language of the plaintext, for example. In many encryption protocols, standard protocol data and messages are included in the plaintext. These can be guessed or deduced using a ciphertext-only attack.

Even a partial break, as in the example above in which the attacker does not obtain the key or the plaintext but can get information about the plaintext, can reveal extremely sensitive information and is still considered a success in cryptanalysis.

Man-in-the-middle attack (MITM)

While not a cryptanalysis attack, per se, a successful man-in-the-middle attack can compromise your encryption scheme. In a MITM attack, the attacker sits between you and your recipient and can intercept the messages you send to your recipient.

In the case of encrypted messages being sent, you would first have to send your public key to your recipient (assuming they don’t have it yet). When you send your public key, the attacker could intercept it and substitute it with their key and forward the message with the swapped key to your recipient. From then on, the attacker would be able to read all of your encrypted communications between you and your recipient.

Side-channel attacks

Side-channel attacks, as their name implies, don’t try to break encryption directly. They exploit the auxiliary information that computers continually output. These are things like the electrical emissions that your screen or hard drive puts out, which change based on the task the computer is performing. Or it could be the amount of power your computer draws, which also varies according to the task being performed.

Spectre and Meltdown, which rocked our computer world in 2018, are two variations of the same underlying vulnerability that affects nearly every computer chip manufactured in the last 20 years.

Both Spectre and Meltdown take advantage of a time-based side-channel attack. They each use a different technique to fool the processor into accessing and encoding secret information to the processor’s cache. Then, by forcing the processor to search for specific information in memory and measuring how much time it takes to access the requested information, the attacker can analyze the processor’s response times and obtain the secret information from the cache.

Results

The thing with cryptanalysis attacks is that they can be very damaging, even if only partially successful. Cryptographers have classified the break-ins that are considered as being successful cryptanalysis attacks. Most of them are partial.

Total break: The attacker can deduce the entire secret key. With the private key, the attacker can decrypt all intercepted messages.

Global deduction: The attacker can produce an algorithm that is functionally equivalent to the encryption and decryption scheme they are trying to break without knowing the key. This enables the attacker to encrypt and decrypt messages as if they had the key.

Instance deduction: When an attacker can discover additional plain or cipher text that they previously did not know. They may not have broken the code, but just that fragment of additional plain or ciphertext may be all the attacker needs to cause trouble.

Information deduction: The attacker obtains some information (i.e., the number of bits that make up the message) about plain or cipher text not previously known. This could lead to other breaks on the encryption scheme.

Distinguishing algorithm: The attacker can differentiate the cipher from a random alteration. This reveals clues about the encryption algorithm and can lead to more significant breaks.

The partial breaks listed above enable the attacker to “move up the ladder,” if you will. As they glean more and more information from your messages, they move closer and closer to a total break. And the amount of damage they could do grows as well.

Popular tools used for cryptanalysis

CryptoSMT

CryptoSMT is a tool used to perform the cryptanalysis of symmetric primitives like block ciphers and hash functions. It is based on SMT/SAT solvers like STP, Boolector, CryptoMiniSat and was developed by Stefan Kölbl.

Cryptanalysis of an image scrambling encryption algorithm (ISEA)

“Cryptanalysis of an image scrambling encryption algorithm” is a repository of cryptanalysis tools. The repo contains codes for ciphertext-only attacks and known-plaintext attacks on ISEA. It also includes codes for calculating the Structural Similarity Index (SSIM) of an image, based on the paper Cryptanalyzing an Image-Scrambling Encryption Algorithm of Pixel Bits. It was developed by Dongdong Lin.

Protecting against cryptanalysis

There doesn’t seem to be much you can do to defend against cryptanalysis attacks, aside from making sure you’re using secure encryption schemes and ciphers across your digital infrastructure and keeping your software updated. However, that does imply the following:

• Use up-to-date encryption and hashing algorithms. SHA1 and MD5, for example, are no longer considered secure and should not be used
• Use sufficiently long encryption keys. For example, RSA keys should be at least 2048 bits long for VPN handshakes
• Remember to destroy superseded keys
• Use strong passwords and use a tried and tested random number generator to generate your keys
• Salt your hashes (add random noise). Like passwords, salts should be long, unique, and as close to random as possible
• Use perfect forward secrecy (PFS) to prevent your past or future sessions from being decrypted if your current key is ever compromised. Most VPN providers use PFS today
• Try and obfuscate your encrypted traffic to make it look like regular traffic and avoid advertising the fact that you’re using encryption. Obfsproxy is an example of an obfuscating tool that can be used with the Tor network
• An intrusion detection system (IDS) will notify you in case of a breach but won’t prevent the breach. Still, cutting down your response time can limit the damage, so a good IDS is recommended

Conclusion

So that’s what cryptanalysis is, in a nutshell. It’s more of a means to an attack than an attack in itself. But insofar as it leads to and enables an attack, it’s an attack. The cryptanalyst garners a little more information at each step of the game until they reach the payload: the decryption of your secrets. Once the attacker has your secrets, it opens up a whole new world of possible exploits and attacks. So make sure you follow the above advice.

Stay safe.