Malicious Cryptography: Exposing Cryptovirology

Chapter 11

SETUP Attack on Factoring Based Key Generation

The notion of black-box hardware and software and the hazards associated with them are familiar to everyone. For example, when a user installs a new commercial program there is no easy way to find out if the program is sending personal information across the Internet back to the manufacturer. Such information could include personal e-mail addresses, the name of the user's Internet service provider, what type of machine the user is using, and so on. The fear is that there might be an invasion of privacy that could among other things lead to aggressive marketing. Hardware implementations of algorithms are even more black-box in nature since the silicon housing hides the underlying circuitry.

When cryptosystems are implemented in a black-box fashion this fear is magnified tenfold. In a worst-case scenario the cryptosystem could be sending the user's secret keys back to the manufacturer. This could allow the manufacturer to do such things as decrypt the user's communications, sign documents on behalf of the user, or even gain unlawful access to the user's machine. This chapter addresses this threat by exploring ways of designing cryptotrojans that to do exactly this, in spades.

In the pages that follow, a set of attacks are presented that are specifically designed to attack black-box key generation algorithms that generate factoring ...