®BuscaLegis.ccj.ufsc.br
Learning About Cryptography
A Basic Introduction to Crypto
A Ciphers By Ritter Page
Terry Ritter
Current Version: 2001 Nov 09
You may wish to help support this work by patronizing Ritter's Crypto Bookshop.
Contents
The Fundamental Idea of Cryptography:
It is possible to transform or encipher a message or plaintext into "an intermediate form" or ciphertext in which the original information is present but hidden. Then we can release the transformed message (the ciphertext) without exposing the information it represents.
By using different transformations, we can create many different ciphertexts for the exact same message. So if we select a particular transformation "at random," we can hope that anyone wishing to expose the message ("break" the cipher) can do no better than simply trying all available transformations (on average, half) one-by-one. This is a brute force attack.
The difference between intermediate forms is the interpretation of the ciphertext data. Different ciphers and different keys will produce different interpretations (different plaintexts) for the exact same ciphertext. The uncertainty of how to interpret any particular ciphertext is how information is "hidden."
Naturally, the intended recipient needs to know how to transform or decipher the intermediate form back into the original message, and this is the key distribution problem.
By itself, ciphertext is literally meaningless, in the sense of having no one clear interpretation. In so-called perfect ciphers, any ciphertext (of appropriate size) can be interpreted as any message, just by selecting an appropriate key. In fact, any number of different messages can produce exactly the same ciphertext, by using the appropriate keys. In other ciphers, this may not always be possible, but it must always be considered. To attack and break a cipher, it is necessary to somehow confirm that the message we generate from ciphertext is the exact particular message which was sent.
A Concrete Example
Most of us have encountered a simple form of ciphering in grade school, and it usually goes something like this:
A Simple Cipher
On a piece of lined paper, write the alphabet in order, one character per line:
A
Then, on each line, we write another character to the right. In this second column, we also want to use each alphabetic character exactly once, but we want to place them in some different order.
A F
When we have done this, we can take any message and encipher it letter-by-letter.
Enciphering
To encipher a letter, we find that letter in the left column, then use the associated letter from the right column and write that down. Each letter in the right column thus becomes a substitute for the associated letter in the left column.
Deciphering
Deciphering is similar, except that we find the ciphertext letter in the right column, then use the associated plaintext letter from the left column. This is a little harder, because the letters in the right column are not in order. But if we wanted to, we could make a list where the ciphertext letters were in order; this would be the inverse of the enciphering transformation. And if we have both lists, enciphering and deciphering are both easy.
The Single Transformation
The grade school cipher is a simple substitution cipher, a streaming or repeated letter-by-letter application of the same transformation. That "transformation" is the particular arrangement of letters in the second column, a permutation of the alphabet. There can be many such arrangements. But in this case the key is that particular arrangement. We can copy it and give it to someone and then send secret messages to them. But if that sheet is acquired -- or even copied -- by someone else, the enciphered messages would be exposed. This means that we have to keep the transformation secret.
Many Transformations
Now suppose we have a full notebook of lined pages, each of which contains a different arrangement in the second column. Suppose each page is numbered. Now we just pick a number and encipher our message using that particular page. That number thus becomes our key, which is now a sort of numeric shorthand for the full transformation. So even if the notebook is exposed, someone who wishes to expose our message must try about half of the transformations in the book before finding the right one. Since exposing the notebook does not immediately expose our messages, maybe we can leave the notebook unprotected. We also can use the same notebook for messages to different people, and each of them can use the exact same notebook for their own messages to each other. Different people can use the same notebook and yet still cipher messages which are difficult to expose without knowing the right key.
Note that there is some potential for confusion in first calling the transformation a key, and then calling the number which selects that transformation also a key. But both of these act to select a particular ciphertext construction from among many, and they are only two of the various kinds of "key" in cryptography.
Weak and Strong Transformations
The simple substitution used in our grade school cipher is very weak, because it "leaks" information: The more often a particular plaintext letter is used, the more often the associated ciphertext letter appears. And since language uses some letters more than others, simply by counting the number of times each ciphertext letter occurs we can make a good guess about which plaintext letter it represents. Then we can try our guess and see if it produces something we can understand. It usually does not take too long before we can break the cipher, even without having the key. In fact, we develop the ultimate key (the enciphering transformation) to break the cipher.
A "real" cipher will have a far more complex transformation. For example, the usual 64-bit block cipher will encipher 8 plaintext letters at the same time, and a change in any one of those letters will change all 8 letters of the resulting ciphertext. This is still simple substitution, but with a huge alphabet. Instead of using 26 letters, a 64-bit block cipher views each of 264 different block values as a separate letter, which is something like 18,000,000,000,000,000,000 "letters."
Nevertheless, the point remains that what we think is a strong cipher may not actually be a strong cipher. In practice, strength is contextual and depends not only upon some unknown "absolute" strength, but also upon the knowledge and abilities of the attacker or opponent.
Unfortunately, we do not expect to know who the attackers may be, nor their capabilities, nor will they tell us of their successes. So, absent some sort of "proof of strength in practice" (which is generally not possible), there is no way to know whether a cipher is actually protecting the information we entrust to it.
Keyspace
Suppose we have 256 pages of transformations in the notebook; this means there are exactly 256 different keys we can select from. If we write the number 256 in binary we get "100000000"; here the leftmost "1" represents 1 count of 28, and we call this an "8 bit" number. Or we can compute the base 2 logarithm by first taking the natural log of 256 (about 5.545) and dividing that by the natural log of 2 (about 0.693); this result is also 8. So we say that having 256 key possibilities is an "8 bit" keyspace. If we choose one of the 256 key values at random, and use that transformation to encipher a message, someone wishing to break our cipher should have to try about 128 decipherings before happening upon the correct one. The effort involved in trying, on average, 128 decipherings (a brute force attack) before finding the right one, is the design strength of the cipher.
If our notebook had 65,536 pages or keys (instead of just 256), we would have a "16 bit" keyspace. Notice that this number of key possibilities is 256 times that of an "8 bit" keyspace, while the key itself has only 8 bits more than the "8 bit" cipher. The strength of the "16 bit" cipher is the effort involved in trying, on average, 32,768 decipherings before finding the right one.
The idea is the same as a modern cipher: We have a machine which can produce a huge number of different transformations between plaintext and ciphertext, and we select one of those transformations with a key value. Since there are many, many possible keys, it is difficult to expose a message, even though the machine itself is not secret. And many people can use the exact same machine for their own secrets, without revealing those secrets to everyone who has such a machine.
Digital Electronic Ciphering
One of the consequences of having a digital electronic machine for ciphering, is that it operates very, very fast. This means that someone can try a lot more possibilities than they could with a notebook of paper pages. For example, a "40 bit" keyspace represents about 1012 keys, which sounds like a lot. Unfortunately, special-purpose hardware could try this many decipherings in under 5 seconds, which is not much strength. A "56 bit" keyspace represents about 7 x 1016 different keys, and was recently broken by special brute force hardware in 56 hours; this is also not much strength. The current strength recommendation is 112 to 128 bits, and 256 is not out of the question. 128 bits is just 16 bytes, which is the amount of storage usually consumed by 16 text characters, a very minimal amount. A 128 bit key is "strong enough" to defeat even unimaginably extensive brute force attacks.
Under the theory that if a little is good, a lot is better, some people suggest using huge keys of 56,000 bits, or 1,000,000 bits, or even more. We can build such devices, and they can operate quickly. We can even afford the storage for big keys. What we do not have is a reason for such keys: a 128 bit key is "strong enough" to defeat even unimaginably extensive brute force attacks. While a designer might use a larger key for convenience, even immense keys cannot provide more strength than "strong enough." And while different attacks may show that the cipher actually has less strength, a huge keyspace is not going to solve those problems.
Some forms of cipher need relatively large key values simply to have a sufficiently large keyspace. Most number-theory based public key ciphers are in this class. Basically, these systems require key values in a very special form, so that most key values are unacceptable and unused. This means that the actual keyspace is much smaller than the size of the key would indicate. For this reason, public key systems need keys in the 1,000 bit range, while delivering strength comparable to 128 bit secret key ciphers.
Naive Ciphers
Suppose we want to hide a name: We might think to innovate a different rule for each letter. We might say: "First we have 'T', but 't' is the 3rd letter in 'bottle' so we write '3.'" We can continue this way, and such a cipher could be very difficult to break. So why is this sort of thing not done? There are several reasons:
Moreover, in a modern cipher, we expect the key to not be exposed, even if The Opponent has both the plaintext and the associated ciphertext for many messages (a known-plaintext attack). In fact, we normally assume that The Opponent knows the full construction of the cipher, and has lots of known plaintext, and still cannot find the key. Such designs are not trivial.
Naive Challenges
Sometimes a novice gives us 40 or 50 random-looking characters and says, "Bet you can't break this!" But that is not very realistic.
In actual use, we normally assume that a cipher will be widely distributed, and thus somewhat available. So we assume The Opponent will somehow acquire either the cipher machine or its complete design. We also assume a cipher will be widely used, so a lot of ciphered material will be around somewhere. We assume The Opponent will somehow acquire some amount of plaintext and the associated ciphertext (that is, known plaintext). And even in this situation, we still expect the cipher to hide the key and other messages.
A cipher designer should expect everything to be exposed -- the complete cipher design, ciphertext, unlimited associated plaintext, etc. -- except the actual message and key. All of the exposed information should be provided to anyone working on the problem.
What Cryptography Can Do
Potentially, cryptography can hide information while it is in transit or storage. In general, cryptography can:
Cryptography can kill in the sense that boots can kill; that is, as a part of some other process, but that does not make cryptography like a rifle or a tank. Cryptography is defensive, and can protect ordinary commerce and ordinary people. Cryptography may be to our private information as our home is to our private property, and our home is our "castle."
Potentially, cryptography can hide secrets, either from others, or during communication. There are many good and non-criminal reasons to have secrets: Certainly, those engaged in commercial research and development (R&D) have "secrets" they must keep. Professors and writers may want to keep their work private, until an appropriate time. Negotiations for new jobs are generally secret, and romance often is as well, or at least we might prefer that detailed discussions not be exposed. And health information is often kept secret for good reason.
One possible application for cryptography is to secure on-line communications between work and home, perhaps leading to a society-wide reduction in driving, something we could all appreciate.
What Cryptography Can Not Do
Cryptography can only hide information after it is encrypted and while it remains encrypted. But secret information generally does not start out encrypted, so there is normally an original period during which the secret is not protected. And secret information generally is not used in encrypted form, so it is again outside the cryptographic envelope every time the secret is used.
Secrets are often related to public information, and subsequent activities based on the secret can indicate what that secret is.
And while cryptography can hide words, it cannot hide:
Cryptography with Keys
Usually, we arrange to select among a huge number of possible intermediate forms by using some sort of "pass phrase" or key. Normally, this is some moderately-long language phrase which we can remember, instead of something we have to write down (which someone else could then find).
Those who have one of the original keys can expose the information hidden in the message. This reduces the problem of protecting information to:
Problems with Keys
The physical key model reminds us of various things that can go wrong with keys:
Cryptography without Keys
It is fairly easy to design a complex cipher program to produce a single complex, intermediate form. In this case, the program itself becomes the "key."
But this means that the deciphering program must be kept available to access protected information. So if someone steals your laptop, they probably will also get the deciphering program, which -- if it does not use keys -- will immediately expose all of your carefully protected data. This is why cryptography generally depends upon at least one remembered key, and why we need ciphers which can produce a multitude of different ciphertexts.
Keyspace
Cryptography deliberately creates the situation of "a needle in a haystack." That is, of all possible keys, only one should recover the correct message, and that one key is hidden among all possible keys. Of course, The Opponent might get lucky, but probably will have to perform about half of the possible decipherings to find the message.
To keep messages secret, it is important that a cipher be able to produce a multitude of different intermediate forms or ciphertexts. Clearly, no cipher can possibly be stronger than requiring The Opponent to check every possible deciphering. If such a brute force search is practical, the cipher is weak. The number of possible ciphertexts is the "design strength" of a cipher.
Each different ciphertext requires a different key. So the number of different ciphertexts which we can produce is limited to the number of different keys we can use. We describe the keyspace by the length in bits of the binary value required to represent the number of possible ciphertexts or keys.
Recently, a 56-bit keyspace was searched (with special hardware) and the correct key found in about 56 hours. Note that a 56-bit key represents 216 times as many transformations as a 40-bit key. So, all things being equal, similar equipment might find a 40-bit key in about 3 seconds. But at the same rate, an 80-bit key (which is presumably 224 times as strong as a 56-bit key) would take over 100,000 years.
Strength
Keyspace alone only sets an upper limit to cipher strength; a cipher can be much weaker than it appears. An in-depth understanding or analysis of the design may lead to "shortcuts" in the solution. Perhaps a few tests can be designed, each of which eliminates vast numbers of keys, thus in the end leaving a searchable keyspace; this is one form of cryptanalysis.
Given the large and developed field of cryptography, one might think that surely there must be tests which can report the strength of an arbitrary cipher. Alas, there can be no such test. Every keyed cipher is weak if the key can be found, so what we normally mean by "strength" is the inability of unknown Opponents to develop the correct key based on whatever information they can acquire. (Normally, we assume the Opponent has a large amount of both the plaintext and the associated ciphertext, because it is difficult in practice to eliminate all known-plaintext exposure.) Thus, strength in practice depends upon the abilities of Opponents we cannot know. Those Opponents will have all the knowledge of the "open scientific literature," plus whatever additional knowledge they may have developed in their own groups.
Every user of cryptography should understand that, in practice, all known ciphers (including the one time pad, when used in practice) are at least potentially vulnerable to some unknown technical attack. And if such a break does occur, there is no reason to expect that we would find out about it.
Ciphers and Trust
With respect to trust, cryptography is not like most areas of technology: Normally, we can see or hear or otherwise directly sense when our devices perform as designed. For example, when we build a car, we can see how fast and far it goes, how easily it starts, and so on; the goal of moving people inside a machine is observable and measurable in many ways. Whenever we use a car and see that it works, that builds trust. When thousands of cars cross a bridge successfully, we learn to trust that bridge, at least for cars. When we turn on a radio and listen to a station we know the radio "works."
We even know when software "works": In general, we use software to produce some sort of result we want. We can then examine the results and decide whether or not they are indeed what we want. Even if bugs do occur, they are generally secondary to the results we manage to produce. So as we use software, we can build trust that it will do what we expect, because we can see what it does.
In contrast, the purpose of cryptography is to protect our secret information, and that is a result we cannot see: The loss of information is something we simply can neither see nor measure. We do not know whether or not a cipher "works." And since we cannot tell whether a cipher is "working," simply using a cipher should not build trust, even if many people use that cipher over many years. Unfortunately, this is such an unusual situation that most people do not recognize the distinction.
The inability to measure whether or not a cipher "works" lends an ironic aspect to the concept of cryptography as a science.
It is sometimes argued that not knowing whether or not a cipher "works" is not too far from the situation of pharmaceutical drugs, in the sense that we simply cannot know the long-term implications of any medication. But we certainly do expect that a drug actually will improve matters in some observable way, or it will not be used. And in cryptography, we cannot even say that using a cipher will improve matters. In a real sense, any cipher could be a "placebo," presenting only the appearance of medication, and we may be the sad unmedicated patient. The belief that we are being helped when that is not the truth is precisely the situation our Opponents wish to achieve!
But what about cipher "contests," and all the pro-bono analysis contributed by crypto experts? Surely all that must tell us something we can believe in! Well, that does tell us something, but perhaps not what we hope for.
What academic cryptanalysis tells us is that those who participate and who know the open scientific literature are unaware of any obvious successful attacks. Unfortunately, that says nothing at all about strength with respect to non-academic Opponents, who know both the open academic literature and their own in-house development, and may spend far more time on cryptanalysis.
If our Opponents are successful at breaking our cipher they will not tell us. For if we know for sure that our cipher is broken, we will eventually change the cipher, and the new one may be more difficult to break than the old one. So our Opponents will seek to avoid providing even hints that our cipher is weak. In fact, Opponents who are successful in breaking our cipher may actively seek to discount any hints of cipher weakness, and also disparage anyone carrying that message. Propaganda is a natural, expected consequence of the situation. In the end, there is no reason to expect that we will know when our cipher becomes weak.
System Design and Strength
Cryptographic design may seem as easy as selecting a cipher from a book of ciphers. But ciphers, per se, are only part of a secure encryption system. It is common for a cipher system to require cryptographic design beyond simply selecting a cipher, and such design is much trickier than it looks.
The use of an unbreakable cipher does not mean that the encryption system will be similarly unbreakable. A prime example of this is the man-in-the-middle attack on public-key ciphers. Public-key ciphers require that one use the correct key for the desired person. The correct key must be known to cryptographic levels of assurance, or this becomes the weak link in the system: Suppose an Opponent can get us to use his key instead of the right one (perhaps by sending a faked message saying "Here is my new key"). If he can do this to both ends, and also intercept all messages between them (which is conceivable, since Internet routing is not secure), The Opponent can sit "in the middle." He can decipher each message (now in one of his keys), then re-encipher that message in the correct user key, and send it along. So the users communicate, and no cipher has been broken, yet The Opponent is still reading the conversation. Such are the consequences of system design error.
Cryptanalysis versus Subversion
Cryptanalysis is hard; it is often tedious, repetitive, and very, very expensive. Success is never assured, and resources are always limited. Consequently, other approaches for obtaining the hidden information (or the key!) can be more effective.
Approaches other than a direct technical attack on ciphertext include getting the information by cunning, outright theft, bribery, or intimidation. The room or computer could be bugged, secretaries subverted, files burglarized, etc. Most information can be obtained in some way other than "breaking" ciphertext.
When the strength of a cipher greatly exceeds the effort required to obtain the same information in another way, the cipher is probably strong enough. And the mere fact that information has escaped does not necessarily mean that a cipher has been broken.
Secret Ciphers
Although, in some cases, cryptanalysis might succeed even if the ciphering process was unknown, we would certainly expect that this would make The Opponents' job much harder. It thus can be argued that the ciphering process should remain secret. Certainly, military cipher systems are not actually published (although it may be assumed internally that the equipment is known to the other side). But in commercial cryptography we normally assume (see Kerckhoff's Requirements) that The Opponents will know every detail of the cipher (although not the key, of course). There are several reasons for this:
Hardware vs Software Ciphers
Block Ciphers
There are a whole range of things which can distinguish one cipher from another. But perhaps the easiest and most useful distinction is that between stream ciphers and block ciphers. A block cipher requires that a full block of data be collected before ciphering can begin; a stream cipher can cipher individual units (perhaps bits or bytes) as they occur. As a consequence, if it ever becomes necessary to cipher individual bits or bytes in a block cipher, it will be necessary to fill the rest of the block with padding before ciphering.
Logically, a conventional block cipher (other than a transposition cipher) is just simple substitution: A block of plaintext data is collected and then substituted into an arbitrary ciphertext value. So a toy version of a block cipher is just a table look-up, much like the amusement ciphers in newspapers. Of course, a realistic block cipher has a block width which is far too large to hold the transformation in any physical table. Because of the large block size, the invertible transformation must be simulated, in some way dynamically constructed for each block enciphered.
In a conventional block cipher, any possible permutation of "table" values is a potential key. So if we have a 64-bit block, there would theoretically be 264 factorial possible keys, which is a huge, huge value. But the well-known 64-bit block cipher DES has "only" 256 keys, which is as nothing in comparison. In part, this is because any real mechanism can only emulate the theoretical ideal of a huge simple substitution. But mostly, 56-bit keys have in the past been thought to be "large enough." Now we expect at least 128 bits, or perhaps somewhat more.
Stream Ciphers
If a block cipher is a huge simple substitution, a stream cipher can be a small substitution which is in some way altered for each bit or byte enciphered. Clearly, repeatedly using a small unchanging substitution (or even a linear transformation) is not going to be secure in a situation where The Opponent will have a substantial quantity of known plaintext. One way to use a small transformation securely is to use a simple additive combiner to mix data with a really random confusion sequence; done properly, this is an "unbreakable" one-time pad.
Logically, a stream cipher can be seen as the general concept of repeatedly using a block transformation to handle more than one block of data. I would say that even the simple repeated use of a block cipher in ECB mode would be "streaming" the cipher. And use in more complex chaining modes like CBC are even more clearly stream meta-ciphers which use block transformations.
One common idea that comes up again and again with novice cryptographers is to take a textual key phrase, and then add (or exclusive-OR) the key with the data, byte-by-byte, starting the key over each time it is exhausted. This is a very simple and weak stream cipher, with a short and repeatedly-used running key and an additive combiner. I suppose that part of the problem in seeing this weakness is in distinguishing between different types of stream cipher "key": In a real stream cipher, even a single bit change in a key phrase would be expected to produce a different running key sequence, a sequence which would not repeat across a message of any practical size. In the weak version, a single bit change in the short running key would affect only one bit each time it was used, and would do so repeatedly, as the keying sequence was re-used over and over again. In any additive stream cipher, the re-use of a keying sequence is absolutely deadly. And a real stream cipher would almost certainly use a random message key as the key which actually protects data.
Public Key Ciphers
Public key ciphers are generally block ciphers, with the unusual property that one key is used to encipher, and a different, apparently unrelated key is used to decipher a message. So if we keep one of the keys private, we can release the other key (the "public" key), and anyone can use that to encipher a message to us. Then we use our private key to decipher any such messages. It is interesting that someone who enciphers a message to us cannot decipher their own message even if they want to.
The prototypical public key cipher is RSA, which uses the arithmetic of huge numeric values. These values may contain 1,000 bits or more (over 400 decimal digits), in which each and every bit is significant. The keyspace is much smaller, however, because there are very severe constraints on the keys; not just any random value will do. So a 1,000-bit public key may have a brute-force strength similar to a 128-bit secret key cipher.
Because public key ciphers operate on huge values, they are very slow, and so are normally used just to encipher a random message key. The message key is then used by a conventional secret key cipher which actually enciphers the data.
At first glance, public key ciphers apparently solve the key distribution problem. But in fact they also open up the new possibility of a man-in-the-middle attack. To avoid this, it is necessary to assure that one is using exactly the correct key for the desired user. This requires authentication (validation or certification) via some sort of secure channel, and that can take as much effort as a secure secret key exchange. A man-in-the-middle attack is extremely worrisome, because it does not involve breaking any cipher, which means that all the effort spent in cipher design and analysis and mathematical proofs and public review would be completely irrelevant.
The Most Important Book
The most important book in cryptography is:
Other important books include
Good books on "The Vietnam War" (and which have nothing to do with cryptography) include:
Retirado de: http://www.ciphersbyritter.com/LEARNING.HTM