Coppersmith's Attack 2: The Short Pad Attack

In the previous post, we explored Coppersmith's attack framework, and kind of realised knowing 'some' part of the 'secret' is enough in case of RSA.

Now let's put that realisation to work.

Imagine encrypting two different messages using the same RSA public key. You add random padding to each message, because randomness is supposed to make cryptanalysis harder. :)

Standard. Nothing wrong with it.

Except your random padding is... a little too short.

An attacker notices that both messages share a predictable structure. They don't know either plaintext, but say they somehow know how the two plaintexts are related.

And suddenly, instead of two enormous RSA problems, they have one polynomial with a small unknown.

Welcome to the Short Pad Attack.

1. First, why do we need padding in RSA? (In case you don't already know... I bet you do, but just in case)

Let's start with a small detour. What is padding doing here, anyway?

RSA's core encryption operation is

$$c \equiv m^e \pmod N$$

where $m$ is the encoded message, $e$ is the public exponent, and $N$ is the RSA modulus.

Textbook RSA applies this operation directly to the message integer. That creates a few problems.

Problem 1: RSA is deterministic

Encrypt the same message twice using the same public key, and you get the same ciphertext:

$$E(m)=m^e\bmod N$$

No randomness means an attacker can recognize repeated messages.

Problem 2: RSA preserves algebraic structure

Suppose two messages are related by a simple mathematical relationship. With textbook RSA, their ciphertexts may expose equations that an attacker can exploit.

This is exactly the kind of structure exploited by attacks such as the Franklin–Reiter attack.

So, what does padding do?

Instead of encrypting the raw message directly, an RSA encryption scheme encodes it first.

Conceptually:

$$m \longrightarrow \operatorname{Encode}(m;r) \longrightarrow \operatorname{RSA\ encryption}$$

Here, $r$ represents random input used by the encoding scheme.

A proper randomized encoding scheme such as RSA-OAEP is designed to prevent the simple deterministic and algebraic attacks that affect textbook RSA.

The random input helps ensure that encrypting the same application-level message twice produces different encoded representatives.

Padding is not merely decorative bytes attached to a message. It is part of the cryptographic construction.

---

And this brings us to our attack.

What happens if the padding introduces randomness, but not enough of it?

2. The setup: Two messages, one public key

Suppose Alice encrypts two messages using the same RSA public key $(N,e)$.

For this attack, assume textbook RSA with a simple padding construction:

$$m_1 = M \cdot 2^k + r_1$$

$$m_2 = M \cdot 2^k + r_2$$

where:

• $M$ is the common message portion.
• \(r_1\) and \(r_2\) are random padding values.
• \(0\le r_1,r_2<2^k\).
• Both messages use the same public exponent $e$ and modulus $N$.

The important assumption is that both messages share the same known structure, while their padding values differ.

The ciphertexts are

$$c_1\equiv m_1^e\pmod N$$

$$c_2\equiv m_2^e\pmod N$$

An attacker knows \(N,e,c_1,c_2\), but doesn't know \(M,r_1,r_2\).

At first glance, this looks like two separate RSA plaintext-recovery problems.

But notice something interesting.

Subtract the two plaintexts:

$$m_1-m_2=r_1-r_2$$

Since both padding values are smaller than \(2^k\),

$$|m_1-m_2|<2^k$$

The plaintexts are close to each other.

More precisely, their difference is small compared with the RSA modulus.

That's the weakness we're going to exploit.

3. Let's try

Step 1: Turning the problem into a polynomial

We know the ciphertexts satisfy

$$m_1^e\equiv c_1\pmod N$$

$$m_2^e\equiv c_2\pmod N$$

Let

$$x=m_1-m_2$$

Then

$$m_1=m_2+x$$

Substituting into the first ciphertext equation gives

$$(m_2+x)^e\equiv c_1\pmod N$$

The second ciphertext equation is

$$m_2^e\equiv c_2\pmod N$$

Subtracting these congruences:

$$(m_2+x)^e-m_2^e \equiv c_1-c_2\pmod N$$

Define the polynomial

$$f(x)=(x+m_2)^e-m_2^e-(c_1-c_2)$$

Then

$$f(x)\equiv0\pmod N$$

The actual unknown difference \(x=m_1-m_2\) is a root of this polynomial modulo $N$.

And we already know that

$$|x|<2^k$$

We have converted our problem into finding a small root of a polynomial modulo $N$.

Sound familiar?

This is exactly where Coppersmith enters the picture.

There is one remaining problem: our polynomial still contains the unknown \(m_2\).

We cannot simply construct $f(x)$ from the public information yet.

Step 2: Eliminating the unknown plaintext

Let's examine the polynomial more closely.

Expanding the difference of powers gives

$$(m_2+x)^e-m_2^e = \sum_{i=1}^{e} \binom{e}{i}m_2^{e-i}x^i$$

For example, if \(e=3\),

$$(m_2+x)^3-m_2^3 = 3m_2^2x+3m_2x^2+x^3$$

This equation still contains \(m_2\), which we don't know.

But the two ciphertexts give us another way to describe the relationship between the messages.

Since

$$m_1=m_2+x$$

we have

$$c_1\equiv(m_2+x)^e\pmod N$$

and

$$c_2\equiv m_2^e\pmod N$$

The Short Pad Attack uses Coppersmith's method to exploit the small difference between \(m_1\) and \(m_2\), constructing a polynomial in that difference alone.

For a known public exponent $e$, the resultant technique can eliminate \(m_2\) from the two polynomial equations.

The resulting polynomial has $x$ as a root modulo $N$, and its degree is at most \(e^2\) in the standard construction.

For the common case \(e=3\), this gives a polynomial of degree at most nine.

That's the key transformation:

$$\begin{aligned} &\text{Two ciphertext equations}\ &\qquad\downarrow\ &\text{Eliminate unknown plaintext}\ &\qquad\downarrow\ &f(x)\equiv0\pmod N\ &\qquad\downarrow\ &\text{Recover small root }x \end{aligned}$$

The exact polynomial depends on the construction and elimination procedure. The important property is that it can be constructed from public information and has the small plaintext difference as a root.

Or, simply, we converted it to a proper Coppersmith and let it handle the rest.

4. Why Coppersmith can recover the difference

skip/skim this part if you're already read last post or you don't really need the internal working rn.

We now have a polynomial equation

$$f(x)\equiv0\pmod N$$

and a known bound

$$|x|<X$$

where \(X=2^k\).

Coppersmith's method finds sufficiently small roots of suitable monic polynomials modulo $N$.

For a monic polynomial of degree $d$, the familiar univariate bound is approximately

$$|x|<N^{1/d}$$

For the polynomial produced by the resultant construction, the degree can be as large as \(e^2\). Thus, a useful sufficient scale for the small-root condition is

$$|x|<N^{1/e^2}$$

under the corresponding assumptions.

Since the difference between the plaintexts is bounded by the padding size, the attack can work when the padding is sufficiently short.

For example, with \(e=3\), the relevant scale is

$$|x|<N^{1/9}$$

This is why the Short Pad Attack is particularly associated with small public exponents.

The exact practical limit depends on the polynomial construction, parameter choices, and implementation. The bound is not a claim that every padding length below some universal number is vulnerable.

A subtle point

The degree-\(e^2\) resultant polynomial is not the only way to formulate the attack. Different constructions can yield different polynomial degrees and bounds.

The important lesson is not to memorize one exponent. It's to understand the mechanism:

1. The plaintexts differ by a small amount.
2. Their ciphertext equations allow us to eliminate the unknown plaintext.
3. The resulting polynomial has a small root.
4. Coppersmith's method recovers that root.

6. Recovering the messages

Once we recover

$$x=m_1-m_2$$

we know the difference between the two plaintexts.

But does knowing their difference immediately reveal both messages?

Not by itself.

We still need to recover one of the plaintexts. Once $x$ is known, the original ciphertext equations and the algebraic structure of the attack provide the information needed to recover the underlying message under the attack's assumptions.

After recovering \(m_1\) and \(m_2\), we can verify the candidates using

$$m_1^e\bmod N=c_1$$

and

$$m_2^e\bmod N=c_2$$

We can then check that

$$|m_1-m_2|<2^k$$

and confirm that the recovered plaintexts have the expected common structure.

A successful candidate must satisfy the original RSA equations, not merely the derived polynomial.

7. What does this mean for RSA padding?

The attack demonstrates why adding some random bytes to textbook RSA is not enough to make it secure.

The problem isn't simply that the random padding is short in isolation. The attack relies on a particular construction that leaves the two encoded plaintexts related by a small difference.

If the encoding instead uses a suitable randomized scheme such as RSA-OAEP, the simple relationship exploited here does not automatically carry over to the encoded RSA representatives.

That distinction is important.

The Short Pad Attack is not a general attack against RSA-OAEP. It targets specific weak padding constructions under particular conditions.

RSA-OAEP has its own security requirements and implementation considerations, but it is designed to avoid this kind of straightforward related-message vulnerability.

In practice, use a vetted RSA encryption scheme rather than designing custom padding.

8. Connecting this to the implementation

I implemented the Short Pad Attack in RsaCtfTool PR #564, alongside a factoring attack that uses known high bits of a prime and changes to the shared Coppersmith backend.

The implementation work is a useful reminder that translating the mathematical attack into code involves more than calling a small-root routine.

You can check out the implementation there, it's opensource, or maybe checkout the tool RsaCtfTool too. It's really good.

What's next?

In the next post, we'll explore another attack from the implementation work: factoring an RSA modulus when the high bits of one prime are already known.

We'll see how knowing part of a prime turns factoring into another small-root problem.