Crypto Concepts
Using the tools described above, it's possible to build a very complicated and very extensible system for network security. IPSec is an example. IPSec uses symmetric ciphers in CBC mode for encryption and HMACs for bulk data authentication. The Internet Key Exchange is basically an authenticated Diffie-Hellman exchange. One method of authentication is digital signatures, another involves HMACing a shared secret, a third involves public key encryption to authenticate a peer.
There are certain concepts that are important to IPSec that are not necessarily cryptographic tools.
Perfect Forward Secrecy
Symmetric keys have a much shorter lifetime than asymmetric. This is due to the complexity of the algorithms. Asymmetric algorithms are based on one-way functions, symmetric algorithms are not. While both are in the same class of complexity, asymmetric algorithms are necessarily the most difficult to solve of that class. They may be as difficult to solve as symmetric algorithms (it's the complexity theorists debate of whether NP is equal to NP-complete) but are believed to be more difficult. Until someone proves that these two types of algorithms are of equal complexity we continue to believe that asymmetric algorithms are more complex than symmetric ones. This is a long way of explaining that certain keys have to be thrown away, and never used again, much sooner than other keys.
When a Diffie-Hellman exchange is used to generate a symmetric key (the kind of key that must be changed more frequently), both parties contribute to the result. The key is ephemeral. If that key is thrown away and replaced by a new key, which is the result of another Diffie-Hellman exchange, the two keys will have no relationship to each other. If an attacker broke a single symmetric key, he would have access to all data that was protected by that key but not to data protected by any other key. In other words, the system that uses such ephemeral, single-use, keys has perfect forward secrecy.
A system would not have perfect forward secrecy if there was a single secret from which all symmetric keys were derived. In that case, breaking the root key could give an attacker all keys derived from that root and therefore all data protected by all those keys.
The important issue to keep in mind regarding perfect forward secrecy is that it is not enough to just use a different key, the keys must be unique.
Perfect forward secrecy is important for some applications but not for all. There is a definite overhead associated with doing a Diffie-Hellman exchange at each rekey interval. If the data requires such security it is an appropriate price to pay, but if it doesn't, it could be excessive. So, perfect forward secrecy may not be necessary every single time. The IPSec standard key exchange, IKE, therefore has an option for perfect forward secrecy. If the parties desire it, it is possible, but not necessary.
Denial of Service
Cryptography is not free. Doing modular exponentiation or computing the product of two very large prime numbers, even decrypting and verifying the integrity of individual packets, takes both wall clock time and CPU time. If it was possible to force a computer to do unnecessary work while trying to achieve security, it might be possible to shut down that computer. Such an attack is called a denial of service attack.
Denial of service attacks can be launched against cryptographic systems if the system can be induced to do unnecessary work or allocate memory unnecessarily. A denial of service attack is when the attacker can cause the attackee to do more work in response to the attack than is necessary to launch the attack.
An example of such an attack would be if Alice was willing to do a Diffie-Hellman exchange and Mallory sent thousands of bogus Diffie-Hellman public values to her, all with fake return addresses. Alice could be forced to do her part for these fake exchanges. That could be quite a bit of work! It would be almost no work for Mallory, though, because it's computationally effortless to generate a string of random bits that look like a Diffie-Hellman public value. It's much more work to actually exponentiate and generate a real one.
Another denial of service attack can be launched if Alice and Bob share symmetric keys which they use to encrypt and authenticate individual IP packets. Mallory could send thousands of packets to Bob that look like they came from Alice. Since Mallory doesn't share the key the packets would be bogus, but the only way Bob could find that out is to do the work of decrypting and verifying the integrity of the packet! It's much cheaper to generate bogus packets than it is to detect that they're bogus.
Thankfully, IPSec and IKE are constructed with partial defenses against denial of service attacks. These defenses do not defeat all denial of service attacks, but merely increase the cost and complexity to launch them.
More Information
This chapter provides a brief overview of some cryptographic concepts that will be expanded on later in this book. Cryptography is a complex art, though, and it cannot be adequately explained in a short chapter like this. There are many good books that give a solid background in cryptography that you're strongly encouraged to read. A good place to start is Cryptography and Data Security by Dorothy Denning, and Applied Cryptography by Bruce Schneier.
There are important and fascinating protocols and problems that were not covered here. For instance, the zero knowledge proof: where one party proves to another that she knows some information without actually divulging the information. Another one-way function that was not discussed is the knapsack problem. Like the discrete logarithm problem, the knapsack problem can be used to construct public key cryptosystems. Other, more complicated, key exchanges also exist, like the Encrypted Key Exchange (EKE). There are even attacks against the cryptographic tools that IPSec uses, like the Birthday Attacks against hash functions. This attack takes its name from the observation that if you are in a room with only 182 other people, the chances are even that one of those persons has the same birthday as you. If there is a room of only 23 people, the chances are even that there are two people in the room that share the same birthday. This in spite of the fact that there are 365 (sometimes 366) days in the year! The birthday paradox affects hashing algorithms because it illustrates the statistical probability of finding two random inputs that will hash to the same digest—i.e., in finding a collision. If the digest from a hash algorithm is n bits in length, finding two distinct messages that hash to the same digest would take O(2n/2) operations.
Cryptography is probably as old as speech but it continually evolves to solve new, interesting, and critically important problems of today and tomorrow.
There are certain concepts that are important to IPSec that are not necessarily cryptographic tools.
Perfect Forward Secrecy
Symmetric keys have a much shorter lifetime than asymmetric. This is due to the complexity of the algorithms. Asymmetric algorithms are based on one-way functions, symmetric algorithms are not. While both are in the same class of complexity, asymmetric algorithms are necessarily the most difficult to solve of that class. They may be as difficult to solve as symmetric algorithms (it's the complexity theorists debate of whether NP is equal to NP-complete) but are believed to be more difficult. Until someone proves that these two types of algorithms are of equal complexity we continue to believe that asymmetric algorithms are more complex than symmetric ones. This is a long way of explaining that certain keys have to be thrown away, and never used again, much sooner than other keys.
When a Diffie-Hellman exchange is used to generate a symmetric key (the kind of key that must be changed more frequently), both parties contribute to the result. The key is ephemeral. If that key is thrown away and replaced by a new key, which is the result of another Diffie-Hellman exchange, the two keys will have no relationship to each other. If an attacker broke a single symmetric key, he would have access to all data that was protected by that key but not to data protected by any other key. In other words, the system that uses such ephemeral, single-use, keys has perfect forward secrecy.
A system would not have perfect forward secrecy if there was a single secret from which all symmetric keys were derived. In that case, breaking the root key could give an attacker all keys derived from that root and therefore all data protected by all those keys.
The important issue to keep in mind regarding perfect forward secrecy is that it is not enough to just use a different key, the keys must be unique.
Perfect forward secrecy is important for some applications but not for all. There is a definite overhead associated with doing a Diffie-Hellman exchange at each rekey interval. If the data requires such security it is an appropriate price to pay, but if it doesn't, it could be excessive. So, perfect forward secrecy may not be necessary every single time. The IPSec standard key exchange, IKE, therefore has an option for perfect forward secrecy. If the parties desire it, it is possible, but not necessary.
Denial of Service
Cryptography is not free. Doing modular exponentiation or computing the product of two very large prime numbers, even decrypting and verifying the integrity of individual packets, takes both wall clock time and CPU time. If it was possible to force a computer to do unnecessary work while trying to achieve security, it might be possible to shut down that computer. Such an attack is called a denial of service attack.
Denial of service attacks can be launched against cryptographic systems if the system can be induced to do unnecessary work or allocate memory unnecessarily. A denial of service attack is when the attacker can cause the attackee to do more work in response to the attack than is necessary to launch the attack.
An example of such an attack would be if Alice was willing to do a Diffie-Hellman exchange and Mallory sent thousands of bogus Diffie-Hellman public values to her, all with fake return addresses. Alice could be forced to do her part for these fake exchanges. That could be quite a bit of work! It would be almost no work for Mallory, though, because it's computationally effortless to generate a string of random bits that look like a Diffie-Hellman public value. It's much more work to actually exponentiate and generate a real one.
Another denial of service attack can be launched if Alice and Bob share symmetric keys which they use to encrypt and authenticate individual IP packets. Mallory could send thousands of packets to Bob that look like they came from Alice. Since Mallory doesn't share the key the packets would be bogus, but the only way Bob could find that out is to do the work of decrypting and verifying the integrity of the packet! It's much cheaper to generate bogus packets than it is to detect that they're bogus.
Thankfully, IPSec and IKE are constructed with partial defenses against denial of service attacks. These defenses do not defeat all denial of service attacks, but merely increase the cost and complexity to launch them.
More Information
This chapter provides a brief overview of some cryptographic concepts that will be expanded on later in this book. Cryptography is a complex art, though, and it cannot be adequately explained in a short chapter like this. There are many good books that give a solid background in cryptography that you're strongly encouraged to read. A good place to start is Cryptography and Data Security by Dorothy Denning, and Applied Cryptography by Bruce Schneier.
There are important and fascinating protocols and problems that were not covered here. For instance, the zero knowledge proof: where one party proves to another that she knows some information without actually divulging the information. Another one-way function that was not discussed is the knapsack problem. Like the discrete logarithm problem, the knapsack problem can be used to construct public key cryptosystems. Other, more complicated, key exchanges also exist, like the Encrypted Key Exchange (EKE). There are even attacks against the cryptographic tools that IPSec uses, like the Birthday Attacks against hash functions. This attack takes its name from the observation that if you are in a room with only 182 other people, the chances are even that one of those persons has the same birthday as you. If there is a room of only 23 people, the chances are even that there are two people in the room that share the same birthday. This in spite of the fact that there are 365 (sometimes 366) days in the year! The birthday paradox affects hashing algorithms because it illustrates the statistical probability of finding two random inputs that will hash to the same digest—i.e., in finding a collision. If the digest from a hash algorithm is n bits in length, finding two distinct messages that hash to the same digest would take O(2n/2) operations.
Cryptography is probably as old as speech but it continually evolves to solve new, interesting, and critically important problems of today and tomorrow.
