In distributed systems, data is usually sent over insecure channels. A prudent user should assume that it is easy for a “bad guy” to see all the data that goes over the wire. In fact, the bad guy may be assumed to have the power to modify the data as it goes by, delete messages, inject new messages into the stream, or any combination of these operations, such as stealing a message and playing it back at a later time. In such environments, security is based on cryptographic techniques.

Messages are scrambled, or encrypted before they are sent, and decrypted on receipt.

Here M is the original plaintext message, E is the encrypted message, f1 and f2 are the encryption and decryption functions, and K is the key. In mathematical notation,

E = f1(M,K)
f2(E,K) = f2(f1(M,K), K) = M

According to the principle of public design, the encryption and decryption functions are well-known publicly available algorithms. It is the key K, known only to the sender and receiver, which provide security.

The most important feature of the encryption algorithm f1 is that be infeasible to invert the function. That is, it should be impossible, or at least very hard, to recover M from E without knowing K. In fact, it is quite easy to come up with such an algorithm: exclusive or. If the length of K (in bits) is the same as the length of M, let each bit of E be zero if corresponding bits of M and K are the same, and one if they are different. Another way of looking at this function is that it flips bits of M that correspond to one bits in K and passes through unchanged bits of M in the same position as zero bits of K. In this case, f1 and f2 are the same function. Where there is a zero bit in K the corresponding bit of M passes through both boxes unchanged; where there is a one bit, the input bit gets flipped by the first box and flipped back to its original value by the second box. This algorithm is perfect, from the point of view of invertability. If the bits of K are all chosen at random, knowing E tells you absolutely nothing about M.

However, it has one fatal flaw: The key has to be the same length as the message, and you can only use it once (in the jargon of encryption, this is a one-time pad cipher). Encryption algorithms have been devised with fixed-length keys of 100 or so bits (regardless of the length of M) with the property that M is provably hard (computationally infeasible) to recover from E even if the bad guy

• Has seen lots of messages encrypted with the same key,
• Has seen lots of (M,E) pairs encrypted with the same key (a “known plaintext” attack),
• Can trick the sender into encrypting sample messages chosen by the bad guy (a “chosen plaintext” attack).

The algorithms (proof of their properties) depend on high-powered mathematics that is beyond the scope of this course.