| The applications of cryptography have recently gained wide spread use in the commercial sector, enabling such things as commercial transactions over the Internet, signed/encrypted e-mail using Public Key Infrastructures, etc. This escalates the need for smart card devices to provide secure storage of sensitive private decryption and signing keys. Such devices utilize on-board random number generators and cryptographic processors for key generation, cryptographic operations, etc. and non-volatile memory for storing keys. This enables the device to both generate private keys and use them, thereby eliminating the need to export the private keys from the secure environment provided by the smart-card. However, these devices are often manufactured using tamper-resistant VLSI microchips. These chips may be viewed as cryptographic "black-boxes" since their internals cannot be easily scrutinized.;In this thesis it is shown that for many widely-used cryptographic algorithms, complementary algorithms exist with the same input/output specifications that leak private keys subliminally and exclusively to the manufacturer of the black-box device. These algorithms can be used in black-box devices creating what will be referred to as Kleptographic attacks. These attacks have a number of properties including: security against reverse-engineering in terms of forward-secrecy, polynomial indistinguishability of output with respect to the output of the corresponding honest implementation, and exclusive recoverability of private keys by the manufacturer. In particular attacks are shown for RSA and Discrete-Log key generation, Diffie-Hellman key exchanges, signature schemes like DSA, and symmetric ciphers with secret designs. These attacks imply that cryptographic algorithms can be used within cryptographic algorithms to reduce overall system security, and therefore suggests that cryptography can be as much of a disabling technology as an enabling technology. For example, the attack on RSA key generation proves that all documents signed using an RSA private key that was generated on a hardware device can be successfully repudiated unless the device is successfully reverse-engineered. The trust relationship should not be regarded as being between users and devices but rather between users and the manufacturers. |
