Visual Studio .NET加密技术剖析系列课程(1)：加密技术理论概观

It may have occurred to you that, it is possible that more than one result might be in-telligible, resulting in some uncertainty about whether or not you have indeed discovered the true key. For example, assume that you have the very short cipher text WZR, and you know that it was produced using the Caesar Cipher. If you perform a brute force key search, using the CaesarCipherBruteForce program, you will see three plausible plaintext results: TWO (key N=3), RUM (key N=5), and LOG (key N=11). However, keep in mind that as the num-ber of characters in the known cipher text increases, the probability of finding more than one meaningful plaintext result diminishes quickly. This has been mathematically formalized and it is referred to as the unicity distance. The unicity distance is a measure of how much ciphertext is needed to reduce the probability of spurious keys close to 0. It is therefore also an indication of how much ciphertext is required (at least with a hypothetical computer of arbitrary power) to obtain the key. Unicity distance depends on the statistical characteristics of both the message and the cipher, which will be discussed in more detail in chapter XXX. In the previous paragraphs, we talk about searching for a result that appears to be meaningful. You may now be wondering about what “meaningful” means. What if the plain-text could be written in any spoken language? Then all sorts of results could be considered meaningful. That can make the cipher attack more problematic . What if the plaintext was compressed before it was enciphered? Then just about nothing would be human readable, and nothing would appear to be meaningful. However, in modern cryptography, we gener-ally assume that the attacker knows all of these details. In real life, this may not always be the case, but for the purposes of analyzing a cipher design, it should be assumed that the attacker knows what plaintext would be meaningful. It is also assumed that the attacker knows all the details of the cipher implementation. For example, if the plaintext is com-pressed before being encrypted, then we should assume that the attacker knows the entire cipher operation, including the compression step. In general, we assume that the attacker knows everything except for the secret key and the plaintext they are attacking. You may notice that if you apply the Caesar Cipher multiple times, you do not actu-ally increase the strength of the cipher one iota. For example, if you encrypt the text CAT with N= 6 to get IGZ, and then encrypt that result with N=4 to get MKD, you have effec-tively done nothing more than simply encrypt once with N=10, since 4+6=10. This is analo-gous to the fact that if you apply a compression algorithm to a file that has already been compressed, you will typically find that you have not achieved much if any additional com-pression. Many ciphers experience diminished gains when applied repeatedly in this way, however, TripleDES, which will be described in chapter XXX, is an effective cipher that employs repeated application of the same algorithm as part of its implementation. Needless to say, the Caesar Cipher is not a very strong cipher by modern standards, but perhaps we should not be asking too much of a 2000 year old cipher! A ciphertext only attack only requires a simple program to exhaustively test the very small keyspace of 25 keys. In the case of a known plaintext attack, the work is trivial, since the plaintext and its corresponding ciphertext can be compared, and the key that was used becomes visually ob-vious. We will look at an improved classical cipher named the Vgenère cipher, as well as some modern ciphers later in this chapter, but first, lets look at how to calculate the work required in carrying out a brute force attack on the Caesar Cipher. Estimating the Brute Force Attack Work Factor The amount of work it takes to accomplish a computational goal is referred to as its work factor. Calculating the work factor for breaking a cipher is an important aspect of analyzing the effectiveness of that cipher. We will now look at calculating this work factor for the Caesar Cipher. In the section titled Complexity Theory in chapter XXX, we will look at this type of calculation in a more rigorous manner. As we have just seen, the Caesar Cipher is pretty pathetic, since its keyspace is so tiny, not to mention other serious weaknesses. With only 25 keys, the keyspace can is equivalent in an information theoretic sense to a tiny 6-bit key, since 2 to the power of 6 equals 32, which is large enough to represent all key values. Fortunately, there are many more powerful ciphers, with much larger keyspaces. And of course, more powerful ciphers require more sophisticated attacks than the brute force key search just described. This is because, for very large keyspaces, and exhaustive test on each possible key would simply take too long. For example, if a given cipher employs a key that is 128 bits long, then there are 2 to the power of 128 possible keys. This is a horrendously large number of keys! In base 10, this number is represented using 39 digits! Keep in mind that a large enough key is necessary, but not sufficient to guarantee cipher security. 2^128 = 340,282,366,920,938,463,463,374,607,431,768,211,456 Ignoring insignificant details, such as leap years, the number of seconds per year is 60 sec/min * 60 min/hr * 24 hr/day * 365 day/year = 31,536,000. If we make the very conservative estimate of the number of CPU clock cycles required for testing each key to be 100, then a 1 GHz machine can test approximately 100,000,000 keys per second. This results in 315,360,000,000,000 keys tested per year. This is a lot of keys, but unfortunately, 2^128 keys will then take 1,079,028,307,080,601,418,897,052 years to test. The universe is believed to be no older than 15 billion years old, so the brut force attack on this cipher would take 71,935,220,472,040 times as long as the age of the universe. Current semiconductor technology is not all that far from the theoretical switching speed limits imposed on us by quantum mechanics, so we cannot hope to get much relief by waiting until next year’s improved clock speeds. Trying to solve the problem by distributing the attack over multiple machines is also quite futile. To solve complete the attack in one year, assuming that you could achieve per-fect scalability, you would need to purchase 1,079,028,307,080,601,418,897,052 CPUs. Even at volume discounts, this will cost much more than the entire US Federal budget. The volume of the Moon is approximately 2.2 * 10^25 cubic centimeters. Assuming 1 cubic cen-timeter per CPU, your custom built super computer would occupy about 5% of the volume of the moon. But that is only the volume of the CPUs. The memory and bus interconnect hardware would be the mother of all motherboards, which would easily fill another 20% of the moon’s volume. This would create enough gravitational force to crush the devices at the center of the computer, and create an enormous list of other moon-sized problems. The questions become absurd: How much would it cost? How long would it take to build? How much power would it consume? Obviously these are all silly questions, but they do clearly demonstrate that the brute force key search technique has its limitations.