Not everyone who uses encryption is a computer programmer. People using computer programs (such as PGP) or cryptographic hardware to perform their encryption are, to a certain extent, trusting their supplier. There are possibilities for malicious alteration of an encryption system so that it seems to be functioning normally, but will reveal all your messages to the attacker who provided you with a program or device that was tampered with (while still keeping them secret from other parties).
As an example, let us take a program like PGP. How could a malicious programmer use the available source to produce a modified version of the program that would appear to operate normally in every way?
When performing conventional encryption, opportunities for mischief are few; but a modified program could hide an encrypted version of the key used, and the name of the file it was used on, somewhere on the user's hard disk.
When used for communications with both RSA and IDEA, however, there are many opportunities for mischief. (Of course, the current version of PGP uses Diffie-Hellman and Triple-DES instead, but I will avoid confusing complications.)
An encrypted E-mail message, being encrypted in CBC mode, includes an initialization vector, chosen at random by the program. This IV could be chosen to include information about the session key.
For example, the session key could be generated from the IV. Having only 2^64 possibilities for the 128-bit session key, out of 2^128, would be hard to detect.
Of course, that only lets the adversary read messages from the person who has the modified program. What about the messages to him?
Well, it is possible to do even worse. A tampered-with version of PGP could generate only 32 random bits, and combine them with 32 bits that contain both a part of one of the user's private keys, and an indication of which part of which key it is; encipher that for use as the IV, and then use the IV to generate the session key.
The method used to protect users of PGP against this is simple enough: the official version of the PGP executable was itself signed using PGP.
As a Canadian, able to distribute source code under more favorable restrictions than U.S. citizens, at least prior to a recent liberalization of the regulations, but still limited by U.S. law for executables I produce on compilers that come from the U.S., I have considered the question of whether I could make a program similar to PGP but which would have inherent resistance to tampering, by changing the protocol used, so that people using such a program, despite my having no control over the executables, would have some chance of safety.
I have recently learned that the technique which the following paragraphs describe may be covered under one or more U.S. patents, including patent number 5,673,319, owned by IBM, covering inventions by Mihir Bellare.
If one uses RSA as the public-key component of such a cipher (at the rate I'm going, the patent [on RSA, that is. The Bellare patent dates from 1997.] will expire before I write any code) one can save bandwith as well as improve security by the following expedient: instead of padding the session key with "random" bits to create a block for encipherment under RSA, encipher the following under RSA: the session key, the IV, and as much of the message as will fit. Then, the remainder of the message is enciphered using a conventional cipher system outside the RSA block.
A malicious programmer could still have the program choose several different values for the IV and session key, encrypt each one under RSA, and choose to use the one that had the desired value for a small number of bits to be leaked in the RSA block. This would be very slow; but one could instead choose different values so as to leak information in the conventionally-encrypted portion of the message, and the trials for this would be much faster. Also, even if no information is leaked, if the number of possible session keys were limited to some small value, say 2^40 or less, then (the conventionally-encrypted portion of) messages could be read without any leaked information.
So, I've taken this idea, which seems to help matters, and advanced another step with it. I propose to allow a program which, like RIPEM or PGP, encrypts messages with a combination of public and private key methods, to function without generating any random numbers whatever.
Of course, random numbers are still used to set up an initial choice of RSA keys, and so a modified program could be designed to choose primes from a set with only 2^40 members. So, 100% security is still not obtained.
What I would do is this: Given the message to be transmitted, I would divide it into two parts: the first 160 bits, and all the rest. Then, I would obtain a 160-bit hash of the rest of the message, using SHA. This hash would then be XORed to the first 160 bits of the message. The result would be used as the session key and IV. (If 160 bits aren't enough, I would simply take the remainder of the message, and repeat the process, dividing it into a first 160 bits and all the rest.) Then, the rest of the message (whether or not it will be later part of the RSA block; this will make chosen-plaintext attacke more difficult) is encrypted conventionally. Finally, as much of the message as possible, including of course the entire session key and IV, are encrypted in a block using RSA.
The following diagram illustrates the process:
If the user needs to encrypt multiple copies of the same message, the user can manually add some random text to the message to prevent the multiple copies from enciphering identically.
If one is using hardware for encryption, other possibilities present themselves. A simple DES chip can have its operation validated; the only bad thing it can do is disclose keys when sent some secret combination of signals.
But one unusual possibility bears noting.
Suppose one is supplied with a chip (or a program) that merely carries out an unknown encryption algorithm. Obviously, there is the hazard that this algorithm might be poorly designed, and therefore weak. But there is a way to maliciously design an algorithm that would appear and be strong, except against attacks by those who set it up.
Let us suppose the following "super-duper algorithm" is provided: encryption using DES under a constant key, XOR with the key provided by the customer, encryption using DES under another constant key.
This algorithm would behave like a secure block cipher with a 64-bit key. However, to those who designed it, knowing the constant keys used for the DES steps, it would fall trivially to a known-plaintext attack.
Computer operating systems are, of course, susceptible to many kinds of attacks, such as from computer viruses, or, in the case of multi-user systems, other users exploiting weaknesses in programs that have operating system privileges. So the idea of having encryption performed by a self-contained module, which generates its own random keys without disclosing them, is attractive.
However, if one doesn't trust a hardware box not to choose keys badly, it seems one can't take advantage of this.
I've worked out a scheme by which this sort of problem can be avoided.
In addition to carrying out the steps in a secret-key algorithm such as Rijndael, let us suppose our all-in-one chip can generate random numbers in hardware, perform the multiprecision arithmetic for the RSA and Diffie-Hellman public-key ciphers, and even search for large primes. Let the chip have its own public/private RSA key pair for communicating with the outside world.
Then, I propose to have the chip function in the following way: when requesting it to encipher data using its secret-key algorithm, send it a block of random data from which to produce the key to use. How the key is derived from the data is known. The data is encrypted using the chip's public RSA key.
Thus, one can generate one's own data block, calculate the hash, and encrypt the block, and then one can check that the chip, like any other chip for simply performing a secret-key cipher, is encrypting the data correctly with that key.
But the chip can also generate blocks of random numbers from internal hardware. Instead of using them directly as keys, it encrypts them using its own public RSA key, and provides the user with the result.
The computer in which that chip is installed can then use that random data as a starting point, applying a randomly chosen transformation to it. The result is a block of data, still encrypted in the chip's public RSA key, whose decrypted value is not known to the computer, but which is effectively random from the point of view of the chip, which can no longer recognize it as a key it produced.
In this way, as long as the software carrying out encryption, and the chip, were not produced by groups that could collude, one is not required to fully trust either the chip or the computer software. Of course, the computer software still handles plaintext, but that would be true using an ordinary encryption chip as well; this simply allows the benefits of an all-in-one encryption chip to be obtained from a chip that doesn't need to be trusted.
Further steps are needed to complete this, at least in many applications. The encrypted random blocks from the chip need to come with signed certificates, so that the user can, after an altered block was used for encryption, reveal the original block used and the transformation applied to it, and get a signature from the chip that a particular stream of data was encrypted with a chip-generated key. This ensures other parties to a communication that rogue software on one computer wasn't bypassing the random key generation feature of its chip.
Searching for primes to produce a public/private key pair would also use a random seed block of the same form as used for a secret key; here, once the key pair was produced, one can reveal the source of a seed block to obtain a similar certificate.
The transformation I propose is raising the random block to a randomly chosen power, modulo the RSA modulus in use.
Multiplying the block by a number, as is typically used in blinding schemes, can't be used, though.
What is required of the key is that neither the chip, nor the operating system, can control its value. Because discrete logarithm is hard, the operating system, when given a random value by the chip, can't find an exponent that will produce a desired value (in this case, the desired key, encrypted using the chip's public RSA key) as a result.
In the case of multiplication as a blinding method, the blinding factor required to produce a desired value can be determined through modular division, so no assurance would be obtained that the operating system does not know, and did not directly choose, the key, from the fact that it is a blinded version of a chip-generated key.
But more general transformations, like a one-way hash of the key, subject to rules that kept the result in the required range, are also possible.
Also, it's been noted that this scheme can be improved by having the user choose a blinding exponent in advance, and supply a hash of it when requesting a random block, thereby preventing searches by the software for a blinding exponent with special characteristics. This may well be important for some applications.