The last of the original crypto challenges… here we go!
Challenge 41 Implement unpadded message recovery oracle
Unpadded RSA is homomorphic, meaning that, if operations like multiplication and addition are carried out on ciphertext, it is as if the same operation were applied to the plaintext.
This can have many useful properties, but also produces some consequences. This challenge is analogous to a “security game” that tests for a property known as INDCCA2 — indistinguishability under Chosen Ciphertext Attack, where the adversary has access to a decryption oracle. The challenger gives the adversary a ciphertext, and the adversary can ask for the encryption and decryption of anything he wants — except the challenge ciphertext, of course! If the adversary can learn any information about the ciphertext’s plaintext, then he wins the game.
A fully homomorphic scheme fails INDCCA2 — the adversary can completely recover the message! The adversary can’t ask for the decryption of the challenge ciphertext, but he can ask for the decryption of 2ciphertext, or 3ciphertext, etc. and he knows that the result will be 2plaintext, 3plaintext. Just divide out the scaling factor, and you have the plaintext.
Challenge 42 Bleichenbacher’s e=3 RSA Attack
Another worry with low public exponent is that the message block, when encrypted, will not be large enough to wrap the modulus.
This blog illustrates an attack on the padding scheme PKCS#1 1.5. When signing a message using RSA, the keyholder generates m ^ d mod N
, and the recipient uses (N, e)
to check that (m ^ d) ^ e = m mod N
. But, instead of signing the message, you sign the PKCS1.5 encoding of the message’s HASH
.
In PKCS#1 1.5, you take the hash of the message you want to sign, and then you encode it like this:
00 01 FF FF ... FF FF 00 ASN.1 HASH
A faulty PKCS 1.5 padding verifier might not check that all the \xff
bytes in the middle are present.
Here’s an example of two faulty verifier versions:


Looking at the weaker version, it’s very simple to construct a message block meeting those parameters.


and then, we simply take the cube root of this forged sig, which undoes the encryption (a cubing).


The cube root will verify to a valid signature in the faulty padding verifier.
Challenge 43 DSA key recovery from nonce
The DSA signature scheme uses two cyclic groups.
One large cyclic group, $Z_p^{*}$, has an order of a 1024 bit prime. Another cyclic group, $Z_q^{*}$, has an order of a 160 bit prime.
The key generation is:
 Generate a 1024bit prime $p$.
 Find a 160bit prime divisor $q$ of $p1$.
 Find an element $\alpha$ which generates the subgroup of $p$ with $q$ elements; i.e., $ord(\alpha) = q$.
 Choose a random $d$ with $0 < d < q$.
 Compute $\beta \equiv \alpha^{d}\bmod p$
The keys are now:
pub = $(p,q,\alpha,\beta)$
priv = $(d)$
A DSA signature is generated and verified as follows:
Signing:
 Choose a random ephemeral key $0 < k_e < q$
 Compute $r \equiv \alpha^{k_e} \bmod q$
 Compute $s \equiv (SHA(x) + d\cdot r) k_e^{1}\bmod q$
Verifying:
 Compute aux value $w \equiv s^{1} \bmod q$
 Compute aux value $u_1 \equiv w \cdot SHA(x) \bmod q$
 Compute aux value $u_2 \equiv w \cdot r \bmod q$
 Compute $v \equiv (\alpha^{u_1}\cdot \beta ^{u_2} \bmod p) \bmod q$
 Verify $v \equiv r \bmod q$


To recover the private key if we know $k$, we just solve for $x$ in the equation for $s$:
$d = \frac{s\cdot k_e  SHA(x)}{r} \bmod q$
Challenge 44 DSA nonce recovery from repeated nonce
Let’s work out how we can recover the k given a pair of messages that use repeated k.
$\begin{aligned} s_1  s_2 &= (m_1 + dr)k^{1}  (m_2 + dr)k^{1} \\\\ &= (m_1  m_2)k^{1} \\\\ k &= \frac{m_1  m_2}{s_1  s_2} \end{aligned}$
Challenge 45 DSA parameter tampering
If we make the generator equal to $p+1$, then raising it to any power mod p will be 1.
This allows us to forge a signature for any message.
Challenge 46 RSA parity oracle
The idea is to multiply the message by successive powers of 2, and using our parity oracle to check whether the result is even or odd. This allows us to update the upper or lower bound — if odd, the multiplication wrapped the modulus, and we update the lower bound. If even, we didn’t wrap the modulus, and we have a tighter higher bound.
The answer at this StackExchange post allows us to see why. Briefly, when we multiply by 2 and then 4, if we get (even, even) then we haven’t wrapped the modulus, and the message is < N/4. If we get (odd, odd), then we know that we’ve wrapped the modulus twice — only possible if 3/4N < P < N. Make sure you see why: the result of the first doubling will be between 1/2N and N, so the second doubling will again wrap the modulus.
Do this iteratively, until you tighten the bounds enough to get every byte of the message, which will be discovered bytebybyte.
Challenge 4748 Bleichenbacher’s attack
Bleichenbacher’s attack shows how we can break RSA+PKCS1 padding using an adaptive chosenciphertext attack and a PKCS oracle. The PKCS oracle will tell you whether a ciphertext decrypts to a plaintext with the following structure:
 The first two bytes are
\x00\x02
 There is at least one null byte after the first null byte
Here’s the attack — the description in the original paper is good:
The attacker tries to find small values $s_i$ for which the ciphertext $c_0(s_i)^e \bmod n$ is PKCS conforming. For each successful value for $s_i$, the attacker computes, using previous knowledge about $m_0$, a set of intervals that must contain $m_0$… The third phase starts when only one interval remains. Then, the attacker has sufficient information about $m_0$ to choose $s_i$ such that $c_0(s_i)^e \bmod n$ is much more likely to be PKCS conforming than is a randomly chosen message. The size of $s_i$ is increased gradually, narrowing the possible range of $m_0$ until only one possible value remains.
The paper splits this up into four steps, which we can each implement as separate functions directly. The first step, blinding, is not really that important — it asks you to choose random integers $s_0$ until you find one s.t. $c(s_0)^e \bmod n$ is PKCSconforming. But, you can just make sure that $c$ is already PKCSconforming (by PKCSpadding the corresponding plaintext $p$), so $s_0$ is trivially 1.
Most difficulties you might encounter when implementing this attack are with regards to the bounds. You have to be very careful about correctly handling all the $\leq$ and interval bounds.
Other things to note when reading the four steps to implement in the paper:
 As the prompt says, “a PKCS#1v1.5 conformant plaintext, one that starts with 00:02, must be a number between 02:00:00…00 and 02:FF:FF…FF — in other words, 2B and 3B1, where B is the bit size of the modulus minus the first 16 bits”. You must see why this is true.
 In step 2c, you just need to find one next $s_i$. Iterate over each $r_i$, and then iterate over all $s_i$'s possible for that $r_i$.
 In step 3, the most important step, you narrow the intervals in which the message can exist. Each interval is a pair $(a,b)$, and you iterate over all $r$ for each $(a,b)$ pair.
Finally, once we have just one interval with one value $a$ left, we’re done! We can recover the original plaintext from the answer $a \equiv c\cdot s_0 \bmod n$ and $m \equiv a\cdot s_0^{1} \bmod n$.



