7
$\begingroup$

I have been trying to understand the ROCA attack described here as the "First Attack" and I cannot follow the explaination.

I have been trying to generate a 512-bits key and crack it. As far as I can understand, $p$ and $q$ are $65537^a \bmod L$ where $a$ is random and $L = 2\cdot3\cdot5\cdot7\cdot\dots$. If at one point, I find out what $p$ or $q$ is, than I can find the other one easily and then compute the private key.

Is this correct? I am sorry if I do not make any sense and any hint to the right solution is greatly appreciated.

$\endgroup$
  • 2
    $\begingroup$ My reading is that $p=k\;L+(65537^a\bmod L)$ where $L=P_n\#=\displaystyle\prod_{i=1}^n p_i$. But that only makes things harder. $\endgroup$ – fgrieu Dec 13 '17 at 7:16
10
$\begingroup$

In the ROCA paper the authors define an integer $M$ (which they call a primorial) as follows:

$$M = \prod_{i=1}^{n} P_i = 2 * 3 * ... * P_n$$

Said another way, $M$ is the product of the first $n$ primes. What the authors observed is that the factors of a vulnerable RSA modulus $N$ have the following form:

$$p = k*M + (65537^a \text{ mod } M)$$

The $65537 (= \mathtt{0x10001})$ might look a little odd hardcoded, but it's a common choice for the public exponent of an RSA key as it has a low hamming weight and thus allows some speed gains in common public key operations.

In the case you are interested in, where $|N| = 512$ bits, we have $n = 39$ and thus $|M| = 219$ bits. Since the size of the prime factors of $N$ is $\frac{|N|}{2} = 256$ bits this implies:

$$|k| = \frac{|N|}{2} - |M| = 256 - 219 = 37$$ $$|a| = \mathbb{log}_{2}(\mathbb{order}_M(65537)) = 62$$


So to generate a vulnerable $512$ bit RSA public key do the following:

  1. Randomly sample a $62$ bit value $a'$ and a $37$ bit value $k'$.
  2. Compute $p' = k'*M + (65537^{a'} \text{ mod } M)$.
  3. Check that $p'$ is prime, if yes it is one of your factors $p$, if not go back to step 1.
  4. Sample another prime $q$ using steps 1-3.

Your vulnerable RSA public key $(N, e) = (p*q, 65537)$.


On to the attack. If $M$ is known, our prime factor $p$ now only has $|k| + |a| = 37 + 62 = 99$ bits of entropy rather than the $256$ bits of entropy that it should. This is not good. The "naive" ROCA attack works in the following way:

  1. Select a guess for the value of $a$ and compute $65537^{a} \text{ mod } M$.
  2. Given $65537^{a} \text{ mod } M$ and the relationship $p = k*M + (65537^a \text{ mod } M)$ use Coppersmith's Algorithm to recover $k$.
  3. Compute $p$ using the recovered $k$ and check if $N \text{ mod } p = 0$. If so, $p$ is a factor of $N$. If not,go back to step 1. and select the next guess for $a$.

The time complexity for this attack is $\mathcal{O}(2^{|a|}) = \mathcal{O}(2^{62})$ since in the worst case we have to check every possible value of $a$. Note that the search space of $a$ is the size of the group that $65537$ generates $\text{ mod } M$.


Now I said "naive" ROCA attack above because the authors optimize this attack by finding a value $M'$ such that the following relationship still holds:

$$p = k*M' + (65537^a \text{ mod } M')$$

But they find $M'$ in such a way that the size of the group $65537$ generates $\text{ mod } M'$ is much smaller than $\text{ mod }M$. Thus the search space for $a$ is also much smaller, and ends up bringing the time complexity down to $\mathcal{O}(2^{20})$. The actual process for finding $M'$ is rather involved, if you'd like to know the details I'd suggest diving into the paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.