"Yes, because his algorithm requires you to get two secure ones, and other public key algorithms don't."

Would be the authors' response to that.

One could write an equivalent article suggesting the need to avoid weak groups for Diffie-Hellman means that Rivest is right.

The weak group problem is addressable by a NIST standard in a way that the two-relatively-secure-primes problem isn't. "Here, use exactly these values", instead of "use code that does X, not Y".

And the retort to the author would be the case of the PS3 and ECDSA. Using low entropy PRNGs at all is the _REAL_ problem.

Are we sure the problem is a low entropy CSPRNG? The problem could be "when bad primes happen to good CSPRNGs".

(The paper itself makes the DSA point.)

They do mention that the lower depth results of the tree could be from bad entropy on a CSPRNG. Which is what I'm making my comment from. There may be a potential flaw in an implementation e.g CRT.

My comment was in regards to crypto usage in general where the most problematic factor is the misuse of PRNG and seeds. (ECDSA PS3 for example).

edit: Article makes points towards a flaw in the CSPRNG and Prime generation.

I don't think I'm being clear. Sorry.

Obviously, if unrelated people around the world are at random times coming up with the same (ostensibly) random gigantic prime factors, there is a randomness issue.

The point the paper makes is that this isn't necessarily a CSPRNG issue. The issue is not necessarily that people are using rand() to generate primes. It's that to generate factors for RSA, you need more than a CSPRNG: you need a prime number generator that correctly uses the CSPRNG. The paper hypothesizes one very plausible prime number generator that would be insecure even if driven off hardware entropy.

I understand your point now and reread that end section 3 of the article. The authors seem to imply that it is possibly resultant from a toolkit which a) doesn't implement the generation of provable primes correctly and therefor b) doesn't comply with NIST standards and will be not be considered for FIPS 186-3 approval.

I've tried to do quick research and the method of generating random primes seems to have been added between FIPS 186-2 and FIPS 186-3. Since FIPS 186-3 only came out (approved not draft) in 2009 its probably, feel free to prove this extrapolation wrong, that these older key pairs could've been generated by an older toolkit, or in a time where this random prime generation recommendation was unknown. So once again we're bitten by these multi-year certificates.

I'm guilty of not having read every word of the paper. But for those who have, perhaps you could indulge my laziness:

Have they ruled out the cause as a buggy or backdoored key generator? Or running down the cause left for some future research?

They did not rule that out, but when they write things like "the quagmire of vulnerabilities that we waded into, makes it infeasible to properly inform everyone involved", I don't get the sense that "backdoor" is top of mind.