[cryptography] Factorization Downgrade Backdoor and the "Evanescent" Security Module

Thierry Moreau thierry.moreau at connotech.com
Wed Feb 9 15:24:14 EST 2011

Dear crypto enthusiasts!

The backdoor generation of weak public modulus for integer-factorization 
cryptosystems is not a new topic. It is nonetheless difficult to solve 
once and for all.

I came across the Cunningham project periodic reports of factorization 
achievements (e.g. 
http://homes.cerias.purdue.edu/~ssw/cun/oldp/dir120/index.html ) in 
which factorizations of composite numbers in the range 2^600 to 2^1100 
are reported. These composite numbers are not as hard to factorize as a 
well-formed RSA (or R-W) public modulus. However, it appears that 
putting a factorization downgrade backdoor is really easy in a closed 
system that generates key pairs: simply force one of the two private 
factors to be much smaller than the other one (the source code may 
already have explicit limits on the difference in size between the two 
private factors). In high security systems, nobody ever has an 
opportunity to look at the private key in a way that would allow the 
detection of the backdoor.

It appears that the only solution is an open source implementation of 
the key pair generation. This may remain compatible with high security 
application environments if a) the private key is output in a form 
factor compatible with a regular HSM, and b) all data used during key 
pair generation is reliably deleted. Actually, HSM vendors usually 
provide some means of key backup and restore so that key import from an 
independent key generation system is (in theory) possible.

This introduces the major characteristics of an "Evanescent" Security 
   1) used for one-shot cryptographic operations,
   2) loaded with sofware fully subject to independent party audit,
   3) no network conection,
   4) output cryptographic secrets in a form factor and split-storage 
techniques compatible with a (non-evanescent) HSM product family,
   5) reliable means of destroying all internal data,
   6) operated under constant monitoring by "trusted" personnel, and
   7) has some reliable means of secret random number generation.

Obviously, this is a disturbing proposition because it highlights the 
limitations of certification for closed implementations, and it trades 
tamper-{evidence,detection,resistance} for "trusted" personnel 
assignments (managers might choose to buy "strong" hardware and ignore 
the criticalness of trusted personnel).

Realistically, no closed HSM vendor will ever allow an open source 
implementation outputting anything compatible with their key import 
capability. Thus, the next step is the "open source HSM" in which 
critical cryptographic secrets must be continuously protected.

Any comment?

Any work being done on something like the "Evanescent" Security Module 
or the "open source HSM" ?

Incidentally, here is a recent study of of FIPS-140-2 compliant HSM:
No threat model, no critical security review, but compatibility, 
performance, and usability review. Informative about a type of crypto 
systems with a price tag that make then outside the reach of most of us.


- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, QC, Canada H2M 2A1

Tel. +1-514-385-5691

More information about the cryptography mailing list