the point of Kerckhoffs’ principle? After all, it must certainly be more difficult for Trudy to attack a cryptosystem if she doesn't know how the cipher works. So, at first glance, it might seem that Kerckhoff is making Trudy's life easier, which is something that we never want to do. There are at least a couple of problems with trying to rely on a secret design for your security. For one, the details of “secret″ systems (whether in cryptography or elsewhere) seldom, if ever, remain secret for long. Reverse engineering can be used to recover algorithms from software, and even algorithms embedded in tamper‐resistant hardware are sometimes subject to reverse engineering attacks and exposure. And, even more worrisome is the fact that secret crypto‐algorithms have a long history of failing to be secure once they have been exposed to public scrutiny—see [50] for a relatively modern example where Microsoft violated Kerckhoffs’ principle.
Cryptographers will not deem a crypto‐algorithm to be worthy until it has withstood extensive public analysis by many knowledgeable cryptographers. The bottom line is that any cryptosystem that does not satisfy Kerckhoffs’ principle is suspect. In other words, ciphers are presumed “guilty″ until “proven″ innocent. Actually, no practical ciphers are proven secure, but there must be a solid body of cryptanalysis indicating that a cipher is not easy to break.
Kerckhoffs’ principle is often extended to cover various aspects of security well beyond cryptography. In other contexts, this basic principle is usually taken to mean that the security design itself is open to public scrutiny. The belief is that “more eyeballs″ are more likely to expose more security flaws, and therefore ultimately result in a system that is more secure. Although Kerckhoffs’ principle (in both its narrow crypto form and in a broader context) seems to be universally accepted in principle, there are many real‐world temptations to violate this fundamental tenet, almost invariably with disastrous consequences. Throughout this book we'll see several examples of security failures that were directly caused by a failure to heed the venerable meneer Kerckhoffs.
In the next section, we look briefly at a few classic cryptosystems. Although the history of crypto is a fascinating topic [61], the purpose of this material is to provide an elementary introduction to some of the crucial concepts that arise in modern cryptography. So, pay attention since we will see all of these concepts again in the next couple of chapters and in many cases, in later chapters as well.
2.3 Classic Ciphers
In this section, we examine four classic ciphers, each of which illustrates a feature that is relevant to modern cryptosystems. First on our agenda is the simple substitution, which is one of the oldest cipher systems—dating back at least 2,000 years—and one that is good for illustrating some basic attacks. We then turn our attention to a type of double transposition cipher, which includes important concepts that are used in modern ciphers. We discuss classic codebooks, since many modern ciphers can be viewed as the “electronic″ equivalent of codebooks. We also consider the one‐time pad, a cipher that is provably secure. No other cipher in this book (or in common use) is provably secure.
2.3.1 Simple Substitution Cipher
First, we consider a particularly simple implementation of a simple substitution cipher. In the simplest case, the message is encrypted by substituting the letter of the alphabet
| plaintext: |
a b c d e f g h i j k l m n o p q r s t u v w x y z
|
| ciphertext: |
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
|
where we've followed the convention that the plaintext is lowercase, and the ciphertext is uppercase. In this example, the key could be stated succinctly as “3″ since the amount of the shift is, in effect, the key.
Using the key 3, we can encrypt the plaintext message
by looking up each plaintext letter in the table above and substituting the corresponding letter in the ciphertext row, or by simply replacing each letter by the letter that is three positions ahead of it in the alphabet. For the particular plaintext in (2.1), the resulting ciphertext is
To decrypt this simple substitution, we look up the ciphertext letter in the ciphertext row and replace it with the corresponding letter in the plaintext row, or we can shift each ciphertext letter backward by three. The simple substitution with a shift of three is known as a Caesar's cipher.3
There is nothing magical about a shift by three—any shift can be used in a Caesar's cipher. If we limit the simple substitution to shifts of the alphabet, then the possible keys are
and she suspects that it was encrypted with a simple substitution cipher using a shift by
This brute force attack is something that Trudy can always attempt. Provided that Trudy has enough time and resources, she will eventually stumble across the correct key and break the message. This most elementary of all crypto attacks is known as an exhaustive key search. Since this attack is always an option, it's necessary (although far from sufficient) that the number of possible keys be too large for Trudy to simply try them all in any reasonable amount of time.
How large of a keyspace is large enough? Suppose Trudy has a fast computer (or group of computers) that can test
