Known-Plaintext Attack

In the world of secret communication, the ultimate challenge has always been to read a message not meant for you. While a cryptanalyst's most common struggle is deciphering an encrypted message in isolation, a far more powerful scenario arises when they possess a crucial advantage: a piece of the original message. This scenario, known as a known-plaintext attack, fundamentally changes the nature of the game. It is the cryptographer's Rosetta Stone, transforming the problem from guessing a message to reverse-engineering the secret process that created it. This article delves into this powerful attack model, revealing how predictable patterns and hidden mathematical structures can be turned into a weapon against the very ciphers they define.

First, in "Principles and Mechanisms," we will explore the fundamental mechanics of the attack. We will see how weaknesses like linearity in stream ciphers and block ciphers allow an attacker to use basic algebra to uncover the secret key. Following this, the chapter "Applications and Interdisciplinary Connections" will broaden our perspective, demonstrating that this attack is not merely a single technique but a profound scientific principle for probing any "black box" system, with surprising connections to linear algebra, physics, and the study of chaotic dynamics.

Imagine you’re an archaeologist who’s just found a new script, an unknown language carved into a stone tablet. It’s gibberish. But then, you find another tablet—a decree from a known king, written in both the familiar Greek and this mysterious new script. Suddenly, you have a key. You have the same message in two different forms. This is the Rosetta Stone. By comparing the known text with the unknown, you can begin to decipher the rules of the language.

The ​​known-plaintext attack​​ is the cryptographer's Rosetta Stone. It’s an attack scenario where the adversary has access not only to the encrypted message (the ciphertext) but also to some portion of the original, unencrypted message (the plaintext). This might seem like a generous assumption, but it’s surprisingly common. Messages often start with predictable headers ("Dear Sir,"), use standard file formats (like %PDF in a PDF document), or contain fixed protocol markers. If you have both the plaintext P and its corresponding ciphertext C, you hold a powerful lever. Your goal is no longer to guess the message, but to deduce the secret process—the key—that turns P into C. Once you have the key, all other messages sent with it are laid bare.

The fundamental principle is this: a known-plaintext attack exploits any discoverable structure or predictability in the encryption algorithm. The cipher's own rules become the tools of its undoing.

One of the most elegant methods of encryption is the ​​stream cipher​​. The idea is wonderfully simple. You generate a long sequence of random bits, called a ​​keystream​​ ($K$). To encrypt your plaintext message ($P$), you simply combine it with the keystream, usually with a bitwise exclusive-OR (XOR) operation. The result is the ciphertext, $C = P \oplus K$. To decrypt, the receiver, who has the same keystream generator, does the same thing: $P = C \oplus K$. It works because $A \oplus B \oplus B = A$.

If the keystream is truly random, never repeats, and is as long as the message, you have a ​​One-Time Pad (OTP)​​. Claude Shannon proved in 1949 that this system is perfectly, information-theoretically secure. It is unbreakable. The problem? Generating, distributing, and securing a truly random key as long as your data is incredibly difficult.

So, engineers had a clever idea: why not generate the keystream with an algorithm? We can use a short secret key as a "seed" for an algorithm that produces a very long, "random-looking" sequence of bits. This is a ​​pseudorandom number generator (PRNG)​​. It’s practical, efficient, and seems to solve the key distribution problem. But this is where danger lurks. By replacing true randomness with a deterministic algorithm, we have introduced a pattern. A ghost in the machine. And a known-plaintext attack is how you find that ghost.

If an attacker knows a piece of plaintext $P$ and sees the ciphertext $C$, they can instantly recover the corresponding part of the keystream: $K = P \oplus C$. Now, they are no longer looking at an encrypted message; they are looking at the direct output of the secret keystream generator. The question then becomes: can they use this small sample of the keystream to predict the rest? If the generator has a predictable structure, the answer is a resounding yes.

The most common and catastrophic structural weakness in a PRNG is ​​linearity​​. A linear system is one where the outputs are simple, proportional combinations of the inputs. They are beautiful in physics and engineering because they are easy to analyze. In cryptography, that same property makes them easy to break.

Let's look at two classic examples of generators that fall victim to their own linearity.

First, consider the ​​Linear Feedback Shift Register (LFSR)​​. An LFSR is a simple electronic device that generates a sequence of bits. The magic is in how it creates the next bit: it's just the XOR sum of a few previous bits from its internal state. The choice of which bits to tap is the secret key. For example, a 5-bit LFSR might compute the next bit $k_i$ using a rule like $k_i = k_{i-2} \oplus k_{i-5}$. This is a linear recurrence relation over the two-element field, $GF(2)$, where addition is XOR.

Suppose we use an LFSR of length $L$ to generate our keystream. An attacker performs a known-plaintext attack and recovers a stretch of this keystream. They now have a series of equations. For each bit $k_i$ they know (for $i \ge L$), they can write: $k_i = c_1 k_{i-1} \oplus c_2 k_{i-2} \oplus \dots \oplus c_L k_{i-L}$ Here, the keystream bits $k_j$ are known values (0 or 1), and the secret taps $c_j$ are the unknown variables we want to find. Each new bit gives us another linear equation. With just $2L$ consecutive bits of the keystream, we have enough equations to solve for all $L$ secret taps, a result formalized by the Berlekamp-Massey algorithm. Once the taps are known, the entire infinite keystream can be regenerated. The security of a system that was supposed to have a key space of $2^L$ possibilities collapses with just $2L$ bits of known plaintext. For a 64-bit LFSR, instead of trying $2^{64}$ keys, you only need 128 bits of known text—a trivial amount—to break the whole system.

Another prime example is the ​​Linear Congruential Generator (LCG)​​. LCGs are a workhorse for statistical simulations, defined by the simple recurrence: $x_{n+1} \equiv (a x_n + c) \pmod m$ If someone were to foolishly use the output of an LCG as a keystream, the result would be a cryptographic disaster. The linearity is right there in the formula. If an attacker recovers just one value of the keystream $K_i = x_i$, they can compute the next one $K_{i+1} = (a K_i + c) \pmod m$ if the parameters $(a, c, m)$ are known (which they often are). Even worse, they can run the equation in reverse to find the seed itself! This brings up a critical point: a sequence that looks random to a battery of statistical tests (it might have a good uniform distribution, for instance) can be utterly predictable from a cryptographic standpoint. Statistical randomness is not the same as cryptographic unpredictability.

Linearity can hide in more complex systems. Consider the ​​Hill cipher​​, an elegant cipher from 1929 that operates on blocks of letters. It treats a block of plaintext as a vector $\mathbf{p}$ and uses a secret matrix $K$ as the key. The encryption is simply matrix multiplication: $\mathbf{c} \equiv K \mathbf{p} \pmod{26}$. This scrambles the plaintext letters in a far more complex way than a simple shift or substitution. It seems formidable.

Yet, it too has a linear heart. Let's say we have a few pairs of plaintext and ciphertext blocks. For instance, we know HE encrypts to BL and LL encrypts to NC. We can convert these into numerical vectors and stack them into matrices, giving us a plaintext matrix $P$ and a ciphertext matrix $C$. The encryption process for all these blocks can be written in one go: $C \equiv K P \pmod{26}$ This is an equation where we know $C$ and $P$, and we want to find the secret key $K$. Anyone who has studied basic linear algebra knows the solution: just multiply by the inverse of $P$. $K \equiv C P^{-1} \pmod{26}$ As long as the plaintext matrix $P$ is invertible (which depends on the specific plaintext you've found), you can directly calculate the secret key matrix $K$. The seemingly complex mixing of letters is undone by the clean, powerful logic of matrix algebra. The structure that defines the cipher is precisely the structure that an adversary uses to dismantle it.

After seeing how linearity can be a fatal flaw, it’s natural to wonder if any simple, structured cipher can be safe. The answer, surprisingly, is yes—but it depends entirely on the game you're playing.

Let’s look at a simple ​​affine cipher​​, where the encryption rule is $C = (aM + K) \pmod{26}$. Here, $M$ is a single plaintext letter, $a$ is a fixed public constant (say, $a=3$), and $K$ is the secret key, chosen uniformly from $\{0, 1, \dots, 25\}$. This looks dangerously linear, much like the LCG. But what if the attacker only has the ciphertext? No known plaintext is available. Can they learn anything about the message?

According to Shannon's definition of ​​perfect secrecy​​, a system is secure if observing the ciphertext does not change the probability of any given plaintext. That is, $P(M|C) = P(M)$. Incredibly, this simple affine cipher achieves it.

Here is the beautiful reason why. Suppose you intercept the ciphertext letter 'Q' (which is 16). You don't know what the original letter was. Could it have been 'A' (0)? Yes, if the key $K$ was 16, since $(3 \times 0 + 16) \pmod{26} = 16$. Could it have been 'B' (1)? Yes, if the key $K$ was 13, since $(3 \times 1 + 13) \pmod{26} = 16$. For any possible plaintext letter you can imagine, there is exactly one unique secret key $K$ that would produce the ciphertext 'Q'. Since every key was chosen with equal probability ($1/26$), every single plaintext letter remains an equally plausible candidate (from the perspective of the cipher's structure). Seeing 'Q' tells you absolutely nothing.

This reveals a profound truth about security. A cipher is not inherently "secure" or "insecure" in a vacuum; its security is defined relative to an attack model. The affine cipher is perfectly secure against a ciphertext-only attack. But if an adversary had just one known-plaintext pair (say, they knew 'A' encrypts to 'G'), they could solve for the key instantly: $6 \equiv (3 \times 0 + K) \pmod{26}$, so $K=6$.

The known-plaintext attack, then, is a lens that focuses on the internal mechanics of a cipher. It turns the algorithm's own deterministic, predictable nature—its beautiful, rigid structure—into a weapon against itself. It is a reminder that in the world of secrets, any pattern, no matter how complex or well-hidden, is a potential vulnerability waiting for its Rosetta Stone.

Now that we have acquainted ourselves with the fundamental mechanics of a known-plaintext attack, we might be tempted to dismiss it as a brute-force, uninspired affair. We imagine an attacker with a ledger, tediously matching plaintexts to ciphertexts to find a key. But this picture misses the forest for the trees. The true power and beauty of this attack lie not in simple matching, but in its ability to act as a precision tool for probing the very soul of a secret system. It is a method of reverse-engineering, a way of asking a black box, "What are you made of?"

In this chapter, we will embark on a journey to see how this one principle—using known inputs and outputs to deduce a hidden mechanism—manifests across a spectacular range of scientific and mathematical disciplines. Like a physicist bombarding an atom with particles to map its internal structure, a cryptanalyst uses known plaintexts to "scatter" off a cipher and reveal the shape of its secret heart.

Let's begin with the simplest case. Imagine a stream cipher, where a secret keystream $Z$ is generated and combined with the plaintext $M$ to produce the ciphertext $C$. In the common binary case, this combination is the XOR operation: $c_i = m_i \oplus z_i$. If an attacker possesses a piece of plaintext and its corresponding ciphertext, they can instantly recover the keystream for that segment by a simple rearrangement: $z_i = m_i \oplus c_i$.

At first glance, this only reveals a piece of the keystream, not the underlying secret key $K$ that generated it. But what if the design of the cipher is flawed? What if the keystream generation is too simple, too predictable? For instance, suppose the $i$-th keystream bit $z_i$ is just a simple function of the $i$-th key bit $k_i$ and some other known values, such as previous plaintext bits $m_{i-1}$ and $m_{i-2}$. Once the attacker computes $z_i$, they can simply plug it into the generation formula and solve for the one remaining unknown: the secret key bit $k_i$. By sliding along the known message, they can peel away the layers of the cipher and recover the entire key, bit by methodical bit. This illustrates the first great lesson: any predictable relationship between the keystream and public information is a potential avenue for a complete break.

The situation becomes far more interesting when the secret key is not just a sequence of bits, but a rich mathematical object like a matrix. Consider the Hill cipher, where a block of plaintext, represented as a vector $\vec{p}$, is encrypted by multiplication with a secret key matrix $K$: $\vec{c} = K\vec{p}$.

Here, a single plaintext-ciphertext pair gives us a vector equation, which is a system of linear equations relating the known entries of $\vec{p}$ and $\vec{c}$ to the unknown entries of $K$. To uniquely determine a general $n \times n$ matrix $K$ with its $n^2$ unknown entries, we typically need $n$ linearly independent plaintext vectors and their corresponding ciphertexts. However, what if we have some prior knowledge about the structure of $K$? Suppose an intelligence source reveals that the key matrix is symmetric ($K = K^T$). A symmetric $n \times n$ matrix does not have $n^2$ independent entries; it has only $\frac{n(n+1)}{2}$. It has fewer "degrees of freedom." This means an attacker needs less information—fewer known plaintext-ciphertext pairs—to pin down the key. Information is the currency of cryptanalysis, and any prior knowledge about the key's structure is a windfall.

This is just the beginning. The true magic happens when the known plaintext has a special relationship with the secret key matrix.

Imagine the key matrix $K$ as a linear transformation, a machine that takes input vectors and stretches and rotates them into output vectors. What if an attacker could feed it a very special input vector—an eigenvector? An eigenvector of $K$ is a vector $\vec{p}$ that is not rotated by the transformation, only stretched by a factor $\lambda$, the eigenvalue. For such a vector, the encryption equation becomes wonderfully simple: $\vec{c} = K\vec{p} = \lambda\vec{p}$. If an attacker suspects (or can construct) a plaintext that is an eigenvector, they can immediately find an eigenvalue by simply comparing the ciphertext to the plaintext. They may not know the full matrix $K$, but they have discovered one of its fundamental properties, a "resonant frequency" of the cipher. This single piece of data severely constrains the possibilities for the secret key.

Let's push this idea further. What if the key matrix $K$ has a hidden "personality," an algebraic constraint it must obey? For example, it might be periodic, satisfying $K^m = I$ for some small integer $m$, where $I$ is the identity matrix. Or, even more subtly, it might be annihilated by a specific polynomial, satisfying an equation like $K^2 + \alpha K + \beta I = 0$. This knowledge is fantastically powerful. If an attacker has one known pair $(\vec{p}, \vec{c})$ where $\vec{c} = K\vec{p}$, they can use the polynomial to generate more information for free. For instance, if $K^2 = -\alpha K - \beta I$, the attacker can compute: $K\vec{c} = K(K\vec{p}) = K^2\vec{p} = (-\alpha K - \beta I)\vec{p} = -\alpha(K\vec{p}) - \beta\vec{p} = -\alpha\vec{c} - \beta\vec{p}$ Look at what has happened! From a single known input-output pair $(\vec{p}, \vec{c})$, the attacker has manufactured a second one, $(\vec{c}, K\vec{c})$, without needing any new intercepted data. This can provide the exact amount of extra information needed to solve for $K$ completely. It is a beautiful example of how abstract algebra hands the cryptanalyst a key to unlock a secret.

This principle of exploiting hidden structure extends to the deepest corners of mathematics. Some ciphers might be constructed such that the key matrix preserves a certain geometric structure, making it part of a so-called classical group like the symplectic group. In physics, such constraints correspond to conservation laws—like the conservation of energy or momentum. For the cryptanalyst, this "conservation law" provides an extra equation that the entries of $K$ must satisfy (for example, that its determinant must be 1), again reducing the search space and making the attack more efficient. Even if the cipher is dynamic, with the key changing at each step according to a rule like $A^i$ for the $i$-th block, the principle holds. A few known pairs from different time steps can be used to set up a system of equations to solve for the underlying generator matrix $A$.

Our journey so far has been through the elegant, structured world of linear algebra. But the principle of the known-plaintext attack is far more universal. It can even be used to tame the wild, unpredictable frontier of chaos.

Some modern communication systems propose using chaotic dynamics for security. The idea is to have a transmitter whose internal state evolves according to a deterministic but chaotic map, like the famous Hénon map. Its evolution appears completely random, but is governed by a set of secret parameters. A message signal $m_n$ can be "masked" by adding it to one of the system's state variables $x_n$ to produce the transmitted signal $s_n = x_n + m_n$.

To an outsider, the signal $s_n$ looks like pure noise. But an attacker with a known plaintext has a decisive advantage. They can simply subtract the known message from the transmitted signal to recover the "pure" internal state of the chaotic system: $x_n = s_n - m_n$. By doing this for a sequence of points in time, the attacker reconstructs a segment of the chaotic system's true trajectory. Since this trajectory must obey the system's equations of motion, the attacker can plug the sequence of recovered states $(x_n, x_{n+1}, x_{n+2}, \dots)$ back into the governing equations. This creates a system of equations where the only unknowns are the secret parameters of the map itself, which can then be solved for. This is a profound link between cryptanalysis and the field of system identification in physics and engineering, where one tries to deduce the governing laws of a system by observing its behavior.

From simple stream ciphers to evolving matrix systems to the heart of a chaotic attractor, the known-plaintext attack reveals itself not as a single technique, but as a deep and unifying scientific philosophy. It is the art of probing a black box. It teaches us a crucial lesson about security: for a system to be truly secure against this kind of analysis, its internal structure must be not only secret, but also free of any special properties, hidden symmetries, or predictable patterns. The art of modern cryptography is, in large part, the art of designing systems that have no such exploitable algebraic or dynamic skeleton for the prying eyes of an analyst to find.