Malicious Cryptography: Exposing Cryptovirology

Chapter 12

SETUP Attacks on Discrete-Log Cryptosystems

Existing cryptosystems based on the discrete logarithm problem are in no way immune to the threat of kleptographic attacks. This chapter expands upon the previous chapter by showing how to mount SETUP attacks on such cryptosystems. The notion of a discrete-log kleptogram is introduced that allows the attacker to obtain secret information covertly from fielded cryptosystems. What is novel about this approach is that it implements SETUP attacks without using explicit subliminal channels. Rather than employing information leaking channels, the implementation uses internal cryptographic tools to generate opportunities to leak information. As before, the approach avoids trivial attacks on the pseudorandomness of the device and similar simple attacks that would enable a successful reverse engineer to learn future states of the device.

The approach employs the discrete logarithm as a one-way function thereby assuring forward secrecy. The discrete-log kleptogram primitive is then used to attack the Diffie-Hellman key exchange [92]. The attack gives the attacker access to the shared secret key that is generated in the exchange. The primitive is then applied to discrete-log based public key encryption algorithms. It is shown how this gives the attacker access to plaintext. Finally, it is shown how to apply the primitive to discrete-log ...