[Cryptography] Response to weak RNGs in Taiwanese and Estonian digital ID cards?

[Peter Gutmann]

Ondrej Mikle <ondrej.mikle at gmail.com> writes:

>The PDF of ROCA is finally available and the RNG in question is on page 3 of
>the pdf. Does not look like the ANSI RNGs, though it's unlike any RNG I've
>seen so far.
>
>Link: https://dl.acm.org/citation.cfm?id=3133969
>Direct to pdf:
>https://dl.acm.org/ft_gateway.cfm?id=3133969&ftid=1916330&dwn=1&CFID=824223213&CFTOKEN=62928332

That's not the RNG, it's the prime/RSA keygen.  However, as you say, if the
primes have the form given in section 2.1 then they can't have been generated
using the X9.31 mechanism, which first defines Miller-Rabin and Lucas tests
(B.2 and B.3) and then defines how to use those to generate the RSA values
(B.4).  An attempt at providing it as ASCII is (for comparison with the
Infineon method):

  To generate a prime p (or q) of 512 + 128s bits,  for some s = 0, 1, 2, 3…,
  perform the following steps.  First p will be generated, followed by the
  generation of q.

  Step 1: To generate p, set Xp = a random number in the range [  2 (2511 +
  128s),  (2512+128s) - 1].  This shall be done using a random number
  generator (RNG) or pseudo random number generator (PRNG) algorithm specified
  in an ANSI X9 standard (see Appendix A: Random Number Generation), along
  with an appropriate seed.  Likewise, to generate q, set Xq = a random number
  in the same range.  If the absolute value of the difference |Xp - Xq|
  exceeds 2412+128s, proceed to Step 2.  If the absolute value does not exceed
  2412+128s, keep regenerating new values of Xq until the difference does
  exceed 2412+128s.  This ensures that |p - q| is sufficiently large to guard
  against Fermat style factoring attacks, (see Appendix C: Security
  Considerations for details).

  Step 2: Randomly generate four 101-bit primes, p1, p2, q1, and q2 by
  randomly generating four positive 101-bit integers Xp1, Xp2, Xq1, and Xq2.
  Sequentially search successive odd integers starting at Xp1 until the first
  prime, p1, is found by using A.2 to do the primality testing. Repeat this
  process to find p2 starting the search at Xp2, q1 starting at Xq1, and q2
  starting at Xq2.  Thus, p1 is the first prime larger than Xp1, p2 is the
  first prime larger than Xp2, q1 is the first prime larger than Xq1, and q2
  is the first prime larger than Xq2.

  Step 3: Apply the Chinese Remainder Theorem (twice) to compute:

  R1 = (p2-1 mod p1) p2  - (p1-1 mod p2) p1 .  Let  Yp0 = Xp + (R1 - Xp mod p1
  p2).  Yp0 is now the first integer greater than Xp  such that p1 is a large
  prime factor of YP0-1 and p2 is a large prime factor of Yp0+1.

  R2 = (q2-1 mod q1) q2  - (q1-1 mod q2) q1 .  Let  Yq0 = Xq + (R2 - Xq mod q1
  q2).  Yq0 is now the first integer greater than Xq  such that q1 is a large
  prime factor of Yq0-1 and p2 is a large prime factor of Yq0+1.

  Step 4: Check the sequence of p and q candidates such that:

  If e is odd:

  ? check the sequence of p candidates Yp0, Yp0+p1 p2, Yp0+2p1 p2, Yp0 + 3p1
  p2 … to see if the public key exponent GCD(e, p-1) = 1.   If so, apply the
  primality tests in Appendix B: Generation of Parameters for rDSA until the
  first prime is found.  This shall be p.

  ? check the sequence of q candidates Yq0, Yq0+q1 q2, Yq0+2q1 q2, Yq0 + 3q1
  q2 … to see if the public key exponent GCD(e, q-1) = 1.   If so, apply the
  primality tests in Appendix B: Generation of Parameters for rDSA until the
  first prime is found.  This shall be q.

  If e is even:

  ? check the sequence of p candidates Yp0, Yp0+(8p1 p2), Yp+2(8p1 p2),
  Yp0+3(8p1 p2) … to see if the public key exponent GCD(e, p-1 2 ) = 1.   If
  so, apply the primality tests in Appendix B: Generation of Parameters for
  rDSA until the first prime is found.  This shall be p.

  ? check the sequence of q candidates Yq0, Yq0+(8q1 q2), Yq+2(8q1 q2),
  Yq0+3(8q1 q2) … to see if the public key exponent GCD(e, q-1 2 ) = 1.   If
  so, apply the primality tests in Appendix B: Generation of Parameters for
  rDSA until the first prime is found.  This shall be q.

As you point out, based on the form of their output this is nothing like what
the Infineon devices are doing.

Which leads (again) to the obvious question, how did these devices repeatedly
pass their security evaluations?

Peter.