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

[Thierry Moreau]

On 30/10/17 09:23 PM, Ondrej Mikle wrote:
>
> 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
>

Ah! Quite instructive!

Some wise guys found an optimization for RSA prime generation in smart 
cards. The remaining entropy was somewhat marginal, but still 
acceptable. The resulting RSA modulus had a hidden structure, but it 
would be impossible that anybody would notice, and then who would be 
qualified enough, motivated enough, patient enough, and rich enough to 
find and exploit a specialized factorization algorithm matching the RSA 
modulus structure.

The hidden structure was identified earlier by the same group, see 
reference [78] in the above article.

In hindsight, the hidden structure was not a good decision:
- security by obfuscation,
- residual entropy could be too small, and
- a specialized factorization algorithm *might* be found.

Basic lesson: be cautious about tricks in applied public key crypto.

Outstanding question: does ECC (or any portion thereof) qualifies as a 
"trick"?

Regards,

- Thierry Moreau