Being a casual CTF crypto player, playing crypto CTFs was more of playing OSINT challenges. One’s approach was looking online for how people broke the system in hand and common misconfiguration and implementation issues, and just trying to remember as many attacks as possible. While this was fun at the beginning, solving hard challenges was a nightmare. Especially challenges where the cryptosystem in place was a toy or custom cryptosystem. Quickly realizing that, I figured out I needed a new approach that depended more on thinking critically than just randomly searching the web, and here came across the term: Cryptanalysis.
Cryptanalysis is the process of finding weaknesses in cryptographic algorithms and using these weaknesses to decipher the ciphertext without knowing the secret key
The core idea here is that we think of cryptosystems in terms of vulnerabilities and exploitation .For example, The same way we think of normal networking systems. Thinking this way requires that we know how to find weaknesses in systems that allow adversaries to know more information than needed.
In this post and a few upcoming ones, I will explain some of these vulnerabilities abstractly and how they can exist in many of our most used cryptosystems. Starting with arguably the most common and critical vulnerability: “something reuse“.
Something reuse
Be it keys like in OTP, nonce in AES, reused primes in RSA, or ephemeral keys like in DSA and Elgamal encryption …etc. This is probably the most important thing to consider while analyzing a cryptosystem. It is a ubiquitous and dangerous vulnerability that often leads to a complete system breakdown (a Total systems breakdown is when the private key can be deduced from public information which gives the adversary the ability to decrypt all ciphertexts). Although it might sometimes only give us information about the two messages that the key got reused on , like in OTP, It can still be significant information for an adversary.
Why would something get reused?
Generally, it’s for three things:
- Resources issue: Like with primes reusing, a developer might want to use fewer resources as prime generation is generally a resource-expensive operation.
- Implementation error: Errors of this type exist in the flow of the program itself. Like using a limited pool of nonce and rotating them once depleted.
- Bad nonce generation: a common example is that many people confuse nonce for being random numbers, nonce refers to “number once”. if a nonce is just a random number, it could be very possible that two numbers are reused, as using randomness in a limited pool leads to reusing as described in the birthday attack.
One more sophisticated vulnerability that is related to reusing something is relating something. Here, instead of reusing a key, the way the keys are generated is linearly related. While this generally leads to an attack we will discuss later on (spoiler: “reveal something”), relating something can lead to a reusing something attack. Like the infamous attack on the early security version of WiFi called WEP. This version used the RC4 encryption system, which is sensitive against key reuse. In this system, the RC4 keys consisted of WEP keys and a 24-bit initialization vector (IV). The actual problem stemmed from the fact that normally the WEP key didn’t change frequently, and a 24-bit is just a 17 million possibility space, and according to the birthday attack, we know that there are going to be two keys reused within just 4096 keys, which led to a complete system breakdown.
