8

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
1
  • 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
    Commented Dec 13, 2017 at 7:16

1 Answer 1

12
\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 and acknowledge you have read our privacy policy.

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