What is “Fast Prime”?

In this note, the manufacturer of a RSA key generation gizmo vulnerable to the new ROCA attack (see second section) explains that

it is common practice to employ acceleration algorithms in order to generate key pairs, especially if time resources are sparse. (We) also utilizes such an acceleration algorithm in time-restricted cases, called “Fast Prime”. This algorithm is software-based..

The foundations of “Fast Prime” date back to the year 2000. Its use started around ten years later after thorough reviews. As a sub-part of one cryptographic software library which is supplied to customers as a basis for their own development, this software function was certified by the BSI (Federal Office for Information Security) in Germany. No mathematical weaknesses were known, nor have been discovered during the certification processes.

What is “Fast Prime” and where was it suggested?

The following (likely) tells a property of primes generated by this method; but not how it really works, if that's a deliberate and/or following some article/method, if there was some goof at some point; which I ask.

The ROCA vulnerability/attack targets some RSA keys generated using “Fast Prime”. Details are in the paper: Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, Vashek Matyas; The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli published at CCS 2017 (in a slightly earlier version).

Paraphrasing that article: the factors making the attack possible (presumably, those generated by “Fast Prime” ) are of the form $$p=k\;M+(65537^a\bmod M) \ \ \text{ where } M=P_n\#=\prod_{i=1}^n p_i$$ with $p_i$ is the $i^\text{th}$ prime.

It follows that any public modulus $N$ made from primes generated in this way is such that $N\equiv65537^a\pmod{P_n\#}$ for some integer $a$.

The integer $n$ is chosen according to the desired bit size of $p$ (which is always multiple of 16), by discrete steps, in a way such that $P_n\#$ is a large fraction of the size of $p$ $$\begin{array}{c|ccc} \text{bits in }p & n & p_n & \text{bits in }P_n\#\\ \hline 256 \dots 480 & 39 & 167 & 220 \\ 496 \dots 976 & 71 & 353 & 475 \\ 992 \dots 1968 & 126 & 701 & 971 \\ 1984 \dots 2048 & 225 & 1427 & 1963 \\ \end{array}$$

A former version of this question discussed the first published ROCA test for vulnerable keys. However that's obsolete: it turns out this test was intentionally simplified to limit disclosure about the vulnerability; the full test has even lower odds of false detection.

• This looks structurally similar to the Miller-Rabin Witness test for primality. Are these two approaches mathematically different? Can Miller-Rabin identify these weak keys as well? Going forward, should prime generators use both Miller-Rabin and this to test for primality? – Russ Oct 18 '17 at 10:54
• @Russ: in Miller-Rabin, the modulus is the (typically large) number tested, when here the modulus is a small prime; that's a huge difference. Also, it seems the issue in the faulty library is not with the Miller-Rabin test, but in the generation of the prime candidates. My tentative conclusion (without having read the forthcoming paper, or having any insider information whatsoever) is that key generators in general, and the (difficult) RSA ones in particular, must be carefully proofread by multiple eyeballs, in source, object, and debugger; not tested as black boxes. – fgrieu Oct 18 '17 at 11:34
• The last three paragraphs of the conclusions in the Roca paper suggest that Infineon's algorithm is secret. – otus Nov 3 '17 at 5:33
• Don't mix up the German term "fast Prim" with the English term "fast prime" (which is short for "fast prime functionality"). While both are related to near-prime numbers, the "fast prime" functionality the Q asks about is about more than just being "fast eine Primzahl" ("almost a prime number" aka "near-prime"). So, rather think of "fast prime functionality" as "speedy prime generation functionality based on near-primes" instead of trying to interpret things with an incorrect attempt at direct translation based upon erroneous interpretation that "fast prime" might not be EN. – e-sushi Nov 5 '17 at 1:44
• Given the timing (2000) and exact title, Maurer's FastPrime method from 1995 and 1999 came to mind. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2151. But you're probably more on track with the CHES2000 reference. – DanaJ Nov 7 '17 at 20:19

This is a tentative guess at answering my own question.

Perhaps the "Fast Prime" method alluded to in the question's citation is that of these two papers (the second polishing the first):

Several things match:

• The objective of the articles is clearly the one pursued by the technique used.
• "Fast Prime" is two words from the title of [JP2006].
• "date back to the year 2000" is matched by the publication of [JPV2000].
• "use started around ten years later after thorough reviews" allows [JP2006] to get published and reviewed.
• From what we know, the prime generator makes heavy use of an $$M=P_n\#=\displaystyle\prod_{i=1}^n p_i$$, essentially as [JPV2000] and [JP2006] do (their $$\Pi$$ is $$M/2$$).

However, the technique in [JP2006] is proven to generate almost random primes, and is not susceptible to the ROCA attack. Hence if my theory is right, there has been a serious implementation goof.

The fact that $$65537^a$$ occurs makes me wonder if the cause of the goof might be a deliberate attempt, gone horribly wrong, to make it faster to compute $$e^{-1}\bmod p$$ with $$e=65537$$; or perhaps just insure that it is defined.

Update: as noticed in comment, Daniel J. Bernstein and Tanja Lange's blog confirms an attempt at implementing [JP2006] gone wrong:

A related algorithm "GenPrime" was published by Joye and Paillier in 2006. The Joye–Paillier generator, like Lehmer's generator, starts from a new random number $$r$$ coprime to $$L$$ and then multiplies repeatedly by a constant $$g$$ modulo $$L$$, obtaining $$r$$ times a power of $$g$$. This can produce any number modulo $$L$$, and produces only a slight bias in the resulting primes. The guess was that (company) was oversimplifying and generating merely a power of $$g$$; this produces far fewer numbers modulo $$L$$.

The authors wrote back promptly, confirming that this guess was correct but not revealing more details.

• If you apply the algorithm in Fig. 2 of JP2006 on p. 162, with $\Pi = M$, $t = 0$, $v$ drawn at random, $w = 1$ so that $m = w \Pi = M$, and $a = 65537$, and if you always pick $k = 1$ instead of drawing it uniformly at random from $(\mathbb Z/m\mathbb Z)^\times$ like you're supposed to, then you start with the candidate $q_0 = [(k - t) \bmod m] + t + l = (1 \bmod M) + v M$, and then try $q_1 = (a \bmod M) + v M$, and then $q_2 = (a^2 \bmod M) + v M$, and so on. – Squeamish Ossifrage Nov 5 '17 at 1:22
• You could test this hypothesis by recovering the exponent of $a = 65537$ from one of the primes in question, and checking whether any smaller exponent is prime. I wonder whether that observation would accelerate the factoring procedure. – Squeamish Ossifrage Nov 5 '17 at 1:24
• In fact, the very next section of the paper suggests using $t = b\Pi$ for a randomly chosen $b$, which amounts to the same thing as what I just described. – Squeamish Ossifrage Nov 5 '17 at 1:28
• It looks like Bernstein and Lange wrote about this on Nov 5: blog.cr.yp.to/20171105-infineon.html. Lots of interesting info. They speculated JP2006 and the ROCA authors confirmed this. – DanaJ Nov 11 '17 at 19:19