The Second Internet by Lawrence Hughes - HTML preview

PLEASE NOTE: This is an HTML preview only and some elements such as links or page numbers may be incorrect.
Download the book in PDF, ePub, Kindle for a complete version.

Appendix A – Cryptography & PKI

Several topics in this book involve cryptography and/or PKI (Public Key Infrastructure). IPsec (Internet Protocol layer security) includes both AH (Authentication Header) and ESP (Encapsulating Security Payload). AH is used to do sender authentication of packets, and detection of tampering. Instead of using a combination of message digest (e.g. SHA1) with asymmetric cryptography (e.g. RSA), AH uses a keyed message digest, also called Hashed Message Authentication Code (HMAC). ESP does symmetric key encryption of the payload part of an IP packet. The symmetric key for this can be manually distributed (referred to as “shared secret key”), or automatically exchanged in a secure manner using Internet Key Exchange (IKE). IKE uses an application of asymmetric key cryptography called the Diffie– Hellman Key Agreement algorithm, and a new kind of digital certificate called an IPsec Certificate to fully automate distribution of symmetric keys for IPsec.

The cryptographic mechanisms used in these IP security protocols are explained in this chapter. If you are not already familiar with them, you should review this chapter before trying to understand the IP security protocols themselves. There are some good books listed in the bibliography that cover these cryptographic mechanisms in considerably more detail, if this chapter is not sufficient for you. I spent two years with VeriSign creating and delivering training on just these topics, and took an entire week to cover the topics in this chapter. What follows is a very concise coverage of these topics.

A.1 – Cryptography Standards

The X.509 digital certificate is the foundation of PKI. It was originally specified as part of the ITU-T (formerly CCITT) X.500 standard for directory services. The public key certificate was specified in part of this larger standard, as fascicle X.509, “The Directory: Public-key and attribute certificate frameworks”, July 1998. What is in current use is version 3 of this specification. This standard has been incorporated into the RFC standard set as RFC 5280, “Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile”, May 2008. The standards related to PKI and cryptography based on X.509 certificates are overseen by the PKIX Working Group of the IETF.

Since X.500 was part of the OSI network standard, there are some artifacts of that origin in the X.509 certificate, such as distinguished names, for example:

cn=Lawrence Hughes, o=InfoWeapons Corp., ou=Administration, c=PH

RFC 5280 describes ways to integrate this OSI technology into TCP/IP, in addition to making all of the details of the certificate itself available to all for free. If this syntax looks familiar, it is also found in LDAP, which also was derived from the OSI X.500 technology.

Some of the concepts covered in this chapter were first defined in a set of standards from RSA called PKCS (Public Key Cryptography Standards). For example, S/MIME was first defined in PKCS #7. There were a number of PKCS standards, the most important of which were:

*     PKCS #1 – RSA Cryptography Standard, now in RFC 3447, “Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1”, February 2003.

*     PKCS #3 – Diffie-Hellman Key Agreement Standard

*     PKCS #5 – Password-based Encryption Standard, now in RFC 2898, “PKCS #5: Password-Based

Cryptography Specification Version 2.0”, September 2000

* PKCS #7 – Cryptographic Message Syntax Standard, now in RFC 2315, “PKCS #7: Cryptographic message Syntax Standard Version 1.5”, March 1998. The specifics of S/MIME, which is a large part of this standard have been refined in RFC 3851, “Secure/Multipurpose Internet Mail Extensions (S/MIME) Version 3.1 Message Specification”, July 2004; and RFC 3852, “Cryptographic Message Syntax (CMS)”, July 2008. The most recent specification of S/MIME is RFC 5751, “Secure/Multipurpose Internet Mail Extensions (S/MIME) Version 3.2 Message Specification”, January 2010.

*     PKCS #8 – Private-Key Information Syntax Standard, now in RFC 5208, “Public-Key Cryptography

Standards (PKCS) #8: Private-Key Information Syntax Specification Version 1.2”, May 2008

*     PKCS #10 – Certification Request Standard, now in RFC 2986, “PKCS #10: Certification Request

Syntax Specification Version 1.7”, November 2000

*     PKCS #11 – Cryptographic Token Interface (Cryptoki)

*     PKCS #12 – Personal Information Exchange Syntax Standard

*     PKCS #15 – Cryptographic Token Information Format Standard, now ISO/IEC 7816-15.

The original PKCS standards are still available today if you are interested, but most of the important ones have been incorporated into the RFC standards track and continue to evolve there. However, even today, we often refer to creating a PKCS #10 Certificate Signing Request, using the PKCS #11 Cryptoki Application Program Interface to a cryptographic module, or exporting public and/or private keys securely in a PKCS #12 package.

A.2 – Cryptography, Encryption and Decryption

Cryptography involves scrambling information in such a way that all of the information is still present, but recoverable only by a recipient who has access to the scheme by which it can be unscrambled. In a very simple case, alphabetic substitution could map each letter of the alphabet to the letter 3 further along, so that A becomes D, B becomes E, etc. That is called an encryption algorithm. Here is the complete mapping from the letters in the message (the plaintext) to the encrypted letters (the ciphertext) for this scheme. To encrypt a message, you would take each letter (in the first line) and map it to the one below it (in the second line).


The word “HELLO” would become “KHOOR”. To unscramble this message, the recipient would need to know how to reverse the encryption (a decryption algorithm), which in this case would involve mapping each letter to the one three before each of the encrypted letters. So, D would become A, E would become B, etc. You could use the same two lines, but instead locate each letter from the ciphertext in the second line and replace it with the letter above it (in the first line). Hence “KHOOR” would become “HELLO”. In this case, the algorithm must be kept secret, because knowledge of it would allow anyone to decrypt the message. The security of this system depends on keeping the algorithm secret.

A.2.1 – Cryptographic Keys

The “shift by 3” encryption system is so simple that almost anyone could figure out how to crack a message encrypted with it in just a few minutes. To make it a stronger system, instead of always shifting by three characters, you could shift by n letters (where n could be any number from 0 to 25). The “shift by 3” scheme would be a special case of this “shift by N” scheme, where N = 3. In the “shift by N” scheme, the value of N is known as an encryption key. To decrypt a message, the recipient needs to know not only the decryption algorithm, but also the specific key used to encrypt a given message. One day, the sender might use N=7 (“HELLO” becomes “OLSSV”), but on the next, they might use N=12 (“HELLO” becomes “TQXXA”). The same plaintext results in different ciphertexts, depending on the key used.

In general, real encryption algorithms are key driven. The same algorithm can produce radically different ciphertexts, depending on which key is used. A key is really just an ordered string of bits. You might think of the encryption algorithm as a generalized machine, in which case a particular key would be like one of many possible cams, which control the operation of the machine (how it slices and dices the data). Replace the cam with a different one and the same machine slices and dices the data in a completely different way.

In fact, modern algorithms are designed in such a way that complete knowledge of the general algorithm itself can be made available to anyone, and it does not make it any easier for them to crack a message encrypted with a key that they do not know. In other words, the security of the system is entirely dependent on keeping the keys used (not the details of the algorithm) secret. Full details of most modern encryption algorithms are not only known, they are standardized, peer reviewed, and available to anyone that is interested. The more good cryptanalysts that have reviewed an algorithm, and pronounced it strong (difficult to crack), the better. It is not possible to prove than an algorithm is uncrackable, but you can build evidence that as yet, no one has managed to crack it (or at least, no one has admitted to being able to crack it).

A.2.2 – Symmetric Key Cryptography

In the “shift by N” system, the same key that was used to encrypt some plaintext is also used to decrypt the resulting ciphertext. This is analogous to your house key. You use the same key to lock your house when you leave, and to unlock it when you return. This is the defining characteristic of symmetric key cryptography which has been around for about 2,000 years. In comparison, with asymmetric key cryptography (invented only recently), one key of a related pair of keys is used to encrypt some plaintext, but only the other key the pair can decrypt the resulting ciphertext. Not even the key it was encrypted with can decrypt it. This is not as intuitive as symmetric key cryptography, but allows some remarkable things to be done.

Standards related to symmetric key cryptography include:

*     FIPS PUB 46 – Data Encryption Standard (January 1977)

*     FIPS PUB 46-1 – Data Encryption Standard (January 1988)

*     FIPS PUB 46-2 – Data Encryption Standard (December 1993)

*     FIPS PUB 46-3 – Data Encryption Standard (October 1999) (includes Triple DES)

*     FIPS PUB 197 – Advanced Encryption Standard (November 2001)

*     RFC 3565, “Use of the Advanced Encryption Standard (AES) Encryption Algorithm in Cryptographic Message Syntax”,  July 2003

*     RFC 3566, “The AES-XCBC-MAC-96 Algorithm and Its Use With IPsec”, September 2003

*     RFC 3602, “The AES-CBC Cipher Algorithm and Its Use with IPsec”, September 2003 A.2.3 – Cryptanalysis

The algorithm just described (“shift by N”) could be known by the recipient in advance, but somehow the sender would have to let the recipient know which key (which value of N) was used to encrypt a given message. There are only 26 possible keys (0 to 25), which would only take 5 bits to represent (actually 5 bits would allow up to 32 possible keys). A key length of 5 bits is not very secure. It would not take long to try every possible key, and chances are, only one of the possible values would result in an English text. If the message was longer, or the same key was used for all messages on a given day, once a third party figured out the key being used, they could easily decrypt the rest of the message, or all of the messages encrypted with it.

Note that in the “shift by N” system, the key N=0 is a weak key, as the ciphertext is identical to the plaintext. Real encryption algorithms may have weak keys as well. DES has 16 known weak keys, which you have to check for when you generate a random DES key (although the probability of creating one is quite low). It is amazing that after all the slicing and dicing that DES does on the binary level, the result (using a weak key) could be exactly what you started with, but that is the way it works.

Cracking secure messages (being able to recover the plaintext of an encrypted message without having access to the correct key) is called cryptanalysis. There are many techniques used to cryptanalyse encrypted messages. For example, with alphabetic substitution schemes, letter frequencies can help you identify the encrypted characters for the most common letters (the character that appears most often in the ciphertext is probably the code for E, etc). With modern algorithms there are other techniques. With DES, a technique called differential cryptography was used to determine its real strength only justified a  56-bit key – anything longer would only give the illusion of more strength. Sometimes cryptanalysts can completely cryptanalyse a new proposed algorithm, which means it is cracked, and messages can be decrypted without knowledge of the keys used. You might think of cryptography as building secure safes and cryptanalysis as safe cracking. Cryptology is the science that includes both cryptography and cryptanalysis. RSA was founded by two cryptographers and one cryptanalyst. The cryptographers proposed one asymmetric key system after another, then the cryptanalyst would analyze and break them. The cryptographers would then try to design one more difficult to break, based on how the previous system was broken. When an algorithm remained unbroken after quite an effort, they released it as the RSA algorithm. Since then, many other cryptanalysts have tried to break it, with no success. The RSA algorithms is now specified in RFC 4055, “Additional Algorithms and Identifiers for RSA Cryptography for use in the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile”, June 2005.

The “shift by N” encryption scheme can be implemented with two disks or two rings, each of which has the entire alphabet written on them, but one of which can be rotated to put A on the plaintext ring next to any letter on the ciphertext ring. Various Radio and TV shows (as well as Cereal manufacturers) have included these cipherdisks as premiums over the years. It is a real (but not very strong) cryptographic system, complete with the concept of a key.


A Secret Decoder Ring

From Wikipedia Creative Commons

A.2.4 – Cryptographic Strength

Modern real world cryptographic systems don’t do just alphabetic substitution, or work on just ASCII text. They accept a block of binary data as input, and scramble information in very complex ways at the bit level. The output is also a block of binary data. A scheme like the DES (Data Encryption Standard) has a block size of 64 bits, using a 56-bit binary key, producing a 64 bit binary ciphertext. With 56-bit keys, there are 256  (about 7.2 E+16) possible keys. Trying every possible key is known as the brute force attack. When DES was released in 1975, that number of keys was effectively considered infinite. However, in 1998, a group at the Electronic Frontier Foundation built a machine called Deep Crack with extensive hardware parallelism that could try roughly a million DES keys every microsecond. At this rate, it took about 56 hours to try all possible keys.

RSA ran a “DES challenge” that involved decrypting a plaintext containing an English phrase in ASCII characters. There were several “crowd computing” attacks, which divided the entire key space into millions of chunks, which individuals could download and try to find the right key among. These typically took several months to locate the valid key, even with tens of thousands of people searching for it. With Deep Crack the problem was recognizing when it had found the right key. Most decryptions with a wrong key resulted in non-ASCII binary gibberish, which could be discarded. Another computer checked the relatively few decryptions that resulted in ASCII text to see if it contained any English words. If so, a human was alerted, who could determine if a valid English phrase was recovered. After Deep Crack, DES was considered no longer “strong”. The assumption was that if a few people could create such a machine with a budget of about $200,000 that at least some governments (and certainly the U.S. NSA) probably already had and used such machines.


One of the circuit boards from Deep Crack, with multiple DES chips (from Wikipedia Creative Commons)

Each additional bit of key length doubles the time that Deep Crack would take to find a key, so here is a table of how long it would take for various common key lengths:


As you can see, with a symmetric key algorithm, the time required for a brute force attack quickly increases with increasing key length to totally impractical time scales. Even 128 bit keys are probably sufficient for most purposes. With 256 bit keys the time is greater than the expected life of the universe.

The most common symmetric key algorithm in use today is the AES (Advanced Encryption Standard) which replaced DES in 2000. It is very fast, and can use either 128 or 256 bit binary keys. There are currently no known attacks against AES that are faster than brute force. Several algorithms were entered in a competition to replace DES as the new standard, including TwoFish (successor to BlowFish) and Serpent. The algorithm that won (and is now known as AES) was called Rijndael (prounounced RAIN- dell). There are no royalties required for use, but many countries have laws restricting use of strong cryptography.

A.2.6 – Key Management

Whether you are using the “shift by n” scheme or AES, the sender must somehow securely communicate the symmetric key they used to the message recipient. This is not easy to do, as if it is sent via any plaintext channel (e.g. spoken over a telephone call, sent by fax, etc), then the easiest way to attack the system is to intercept the key. Systems based on symmetric key cryptography alone have very complex key management systems, and these are usually the weakest link of any such system. Kerberos is an example of a cryptographic system based entirely on symmetric key cryptography (actually DES).

A.3 – Message Digest

Another cryptographic algorithm (message digest) does not include the entire contents of the input text in the output, even in scrambled form. It is not possible to recover the plaintext from a generated message digest. It is a one way algorithm. In fact, regardless of how large the input document is, the output is a fixed length (for a given message digest algorithm). For example, the MD5 message digest algorithm produces a 128 bit output, SHA1 produces a 160 bit output, and SHA-256 produces a 256 bit output. The output characterizes the input document. Any change at all in the input document is amplified by the message digest algorithm. Even a single bit difference in the input would result in a totally different output. This makes it very good for determining if two documents are identical (or the same document at two different points in time).  If a document is modified in any way at all (changing, deleting or adding characters or bits), the generated message digest will be different after the modification. It is like an extremely sensitive checksum. The term Message Authentication Code (MAC) is  also sometimes used for Message Digest (not to be confused with the network term MAC, which refers to the Media Access Control layer, or MAC Addresses).

The following RFCs define Message Digest Algorithms:

*     RFC 1321, “The MD5 Message-Digest Algorithm”, April 1992

*     RFC 3174, “US Secure Hash Algorithm 1 (SHA1)”, September 2001

*     RFC 3874, “A 224-bit One-way Hash Function:  SHA-224”, September 2004

*     RFC 4634, “US Secure Hash Algorithms (SHA and HMAC-SHA)”, July 2006

Note that RFC 4634 includes definition of the newer SHA-224, SHA-256, SHA-384 and SHA-512.

A.4 – Asymmetric Key Cryptography

In the early 1970s, some English cryptographers at GCHQ (James Ellis, Clifford Cocks and Malcolm Williamson) invented an entirely new type of cryptography, which was kept classified and not revealed until 1997. It was re-invented independently in 1976 by two researchers named Whitfield Diffie and Martin Hellman (based on work by Ralph Merkle). This scheme is called asymmetric key cryptography, and it involves using not one key, but a related pair of keys. If you encrypt something with one of the keys, only the other key of a pair will decrypt the ciphertext produced. Even the key used to encrypt the plaintext will not correctly decrypt the ciphertext. Later, three mathematicians from M.I.T. named Ron Rivest, Adi  Shamir and Leonard Adleman created a company called RSA that was the first to commercially exploit this concept. Their asymmetric key algorithm (also called RSA) is still in extensive use today.

All asymmetric key algorithms depend on some very hard mathematical problem that is far faster to do in one direction (e.g. multiplying two large prime numbers together) than the other direction (e.g. factoring a giant product of two primes into the two prime numbers). The mathematical problems are referred to as trap door functions (because a trap door allows things to go easily in one direction, but not in the other). The fast direction (e.g. multiplying two giant primes) is used when you generate a pair of matched keys, but deriving the private key from the public key involves working the problem in the reverse direction (factoring the product of the two primes). The time required to do this increases greatly with the length of the product. A product that is 512 bits long (about 154 decimal digits) is considered weak. A product that is 1024 bits long (about 308 decimal digits) is considered fairly strong. A product that is 2048 bits (about 616 decimal digits) or longer is considered very strong. As computing power increases (and factoring theory improves) year by year, what was once considered strong is later considered weak, so key lengths must slowly increase. For example, cracking a 512 bit RSA key is estimated to take about 7,000 MIP-years to accomplish. In 1979, the Motorola 68000 ran at about 1 MIPS, so it would take 7,000 years for one machine (or 70 years for 100 machines) to break one 512 bit key. In 2000, the AMD Athlon ran at about 3500 MIPS, so it would take about 2 years to do the same thing. The most recent Intel Core i7 (i980EE) runs at about 147,000 MIPS, so one machine with this CPU would be able to crack a 512 bit key in about 18 days. Such increases will eventually result in having to use impractically long keys with RSA. Fortunately, a newer asymmetric key algorithm called Elliptic Curve Cryptography (ECC) has better characteristics (strength goes up more rapidly with increasing key length   than it does with RSA). At some point, as computing power increases, cryptographic systems will have to switch over to using ECC. The standards already support it.

There is also an asymmetric key algorithm called the Digital Signature Algorithm (DSA), created by the U.S. NSA (National Security Agency). DSA is part of the Digital Signature Standard (DSS) which is specified in FIPS 186. The DSS was adopted in 1996 as FIPS 186-1, and then expanded in 2000 as FIPS 186-2, and again in 2009 as FIPS 186-3. There is no general encryption algorithm (e.g. for digital envelope) associated with DSA – it is just for digital signatures.

Let’s say Alice creates two keys. She publishes one of them (called her public key) to the entire world. The other one (called her private key), she never shows to anyone. Anyone in the world can obtain and use her public key to encrypt things, but she is the only one than can decrypt things encrypted with her public key. So if she wanted to send something securely to Bob, she would obtain Bob’s public key (even through insecure channels – it does not matter who sees it). She would encrypt her message using Bob’s public key, and send the encrypted message to him. Anyone in the world would be able to send Bob such a message, because all they need is his public key. He would use his private key to decrypt it. He is  the only person in the world who could do this (assuming no one has discovered his private key). This provides complete privacy, without having to do complex and insecure symmetric key distribution.

A.4.1 – Digital Envelopes

Compared with symmetric key cryptography, asymmetric key cryptography is very slow (in terms of how many bytes per second can be encrypted), so it is not commonly used to encrypt entire long messages.

It is usually used just to encrypt a short (e.g. 128 bit) symmetric session key or a short (e.g. 160 bit) message digest. So, in a real system (such as S/MIME e-mail), Alice would generate a random symmetric session key (just for this e-mail message, never to be used again), encrypt the message with it (using AES), then encrypt the symmetric session key and Bob’s public key (using RSA). She would send both the encrypted message and the encrypted session key to Bob. He would first decrypt the session key with his private key (using RSA), then use the recovered session key to decrypt the message (using AES). This is called creating a digital envelope. A digital envelope provides privacy. Asymmetric key cryptography solves the problem of how to securely distribute symmetric keys.

A.4.2 – Digital Signatures

Asymmetric key cryptography is also useful for creating digital signatures, when used in combination with a message digest algorithm. As an example, to produce a digital signature of a document, Alice first produces a message digest of the message (using SHA1) then encrypt the message digest with her private key (using RSA). The result would be encoded into ASCII and appended to the message. She would send the message including the digital signature to Bob. Bob would strip off the digital signature, and produce a new message digest of the message (using SHA1). He would also decrypt the encrypted message digest with Alice’s public key (using RSA). He would then compare the recovered message digest with the newly generated message digest. If they match, then the digital signature is valid. If they don’t match then either the message was signed using someone else’s private key (hence was probably sent by someone else), or the message had been tampered with along the way. In either case, the message should not be accepted as valid. A digital signature provides sender authentication (knowing  for certain that it was sent by the person it appears to be from), and message integrity (being able to detect any possible change to the message). These are two very useful things to know about a message.

A.4.3 – Combined Digital Signature and Digital Envelope

By itself, a digital signature does not provide privacy. You may not care who reads a message, but you want to know for certain who it came from, and whether or not it has been tampered with along the way. In this case, only a digital signature is needed. If you also want privacy, then you must both digitally sign and then digitally envelope the message. There is no conflict between the two processes. S/MIME e-mail allows you to do neither, either or both. They are completely independent processes (although if combined, the digital signature must be done first and checked last).

A.4.4 – Public Key Management and Digital Certificates

When Alice sends Bob a digitally signed message, she has all the keys she needs (her own private key) at the time she composes the message. When he is reading the message, Bob needs Alice’s public key, which she can simply append to the message. If Alice appended her key, Bob can use the appended public key to check the signature. If she didn’t, Bob can obtain her public key in various other ways, perhaps she published her key on a website via HTTP, or in an LDAP directory.

When Alice sends Bob a digitally enveloped message, she needs Bob’s public key, which she may not have. Bob might have published it on his website, or in an LDAP directory, or he could simply send Alice a digitally signed message first. Many secure e-mail systems save the public keys of the senders of all digitally signed messages in case you want to later send them digitally enveloped messages. When Bob receives a digitally enveloped message, he has all the keys he needs to open it (his own private key).

Regardless of how Bob obtained Alice’s public key, how does he know for certain that the key really belongs to Alice? In general, anytime you use a public key, you must determine if it is the real public key for that user. If Charlie can trick Bob into using his public key to check what he thinks is Alice’s signature, Charlie can sign the message using his own private key and Bob will think it is a valid signature from Alice (this is called the public key substitution threat).

A public key must be distributed embedded in a digitally signed document that includes other identifying information, such as the key owner’s name, email address, expiration date, etc. This is called a public key digital certificate. It should be produced and signed by a trusted third party (someone other than Alice and Bob, but whom they both trust). For example, VeriSign will produce digital certificates for anyone. Such an organization is called a Certification Authority or CA for short. They must verify all of the information to be embedded in the digital certificate as correct, and operate in a secure manner to prevent bogus certificates from being issued. The digital signature binds all of the included information together.

The trust domain for a given application consists of all the involved parties. For a bank and their customers, the bank could issue digital certificates to their customers and supply them with the necessary root certificates to install in their browsers (this is called a private hierarchy PKI). If the  involved parties can be just anyone in the world, then the trusted third party must be someone like VeriSign, who have embedded their root certificate in all browsers (this is called a public hierarchy PKI).

A.4.4.1 – Chain of Trust

Since each person’s digital certificate is signed by a Certification Authority (using their own private key), you must verify the signature in each person’s digital certificate by using the CA’s public key. How do you know that you have the real public key for the CA, and not that of some hacker? The necessary public key is provided in yet another digital certificate (an intermediate certificate). The intermediate certificate is signed by the CA’s root private key, and you verify the intermediate certificate’s digital signature with the CA’s root public key. The root public key is provided to you in a self-signed certificate (one signed by the root private key), but is installed in your application (e.g. your browser) by the vendor so you can trust it. Verifying all of the certificates from that of the person you are communicating with, up to the root certificate of the relevant Certification Authority is called climbing a chain of trust.

A.4.5.2 – Certificate Validity Period

Like a credit card, a digital certificate has an expiration date, past which it should not be accepted by anyone. Certificates are usually renewed (re-issued) once a year, after re-verifying all the embedded information. This insures that the embedded information has been verified recently. Unlike credit cards, digital certificates also have a starting date. The certificate is only valid from the starting date until the expiration date.

A.4.5.3 – Certificate Revocation

When you use your credit card in a store, they used to check its number against a printed book of revoked card numbers (from people who didn’t pay their credit card bill). If your number was in the book, the store would not accept your card, and would usually cut it up. Later this was automated, so that the number (and the amount of the transaction) was sent online to the credit card company, who determined if the card was still valid, and the amount was within their remaining credit limit for that card.

Digital Certificates can also be revoked before their expiration date. There are two mechanisms for doing this: Certificate Revocation Lists and Online Certificate Status Protocol (OCSP). The first scheme (CRL) is the older, and is similar to the printed books of revoked credit cards. CRLs are published (via HTTPS) periodically (usually daily), so there may be some delay before everyone can become aware that a certificate has been revoked. The other scheme (OCSP) is more recent, but allows users to determine the current status of certificates instantly. Not all client applications support OCSP.

A.4.5.4 – Public Key Infrastructure (PKI)

It is the responsibility of any client or server that uses digital certificates to verify all of these things before accepting a certificate as valid (for an example, see the details of the SSL/TLS handshake later in  this chapter). The issuance of digital certificates, and all of the things related to the management of them, is called a Public Key Infrastructure (PKI). Creating and running a PKI is not a trivial thing, but it is necessary for any system that uses asymmetric key cryptography.

A.5 – Hash-Based Message Authentication Code (HMAC)

There are also some message digest algorithms that use a key, similar to an encryption algorithm. They still produce a fixed length message digest, like a regular message digest, but a key is used in the process, which modifies the way the digest is created. For a given input text, and a given HMAC algorithm, if you change the key, you will get a very different message digest. This is kind of a lightweight digital signature (no asymmetric cryptography is used). HMAC is used in IPsec for the

Authentication Header. The sender produces an HMAC of the relevant fields of the packet, using a given key. One key is shared securely with the recipient for a lot of packets, via either “shared secret key” or via IKE. Upon receipt of a packet, the recipient calculates the HMAC of the same relevant fields, using the HMAC key that was used by the sender. If an identical message digest is produced, then this is proof that the relevant fields of the packet have not been tampered with, and could only have been sent by the purported sender (not by someone else).

Using HMAC is much faster than doing a full digital signature, which is why it is “lightweight”. A full digital signature would be more secure, and far more difficult to fake, but the computing overhead on every packet would be enormous, and packet throughput would drop dramatically. Likewise for ESP, a full digital envelope is not used for every packet, but only symmetric key encryption is used, with a key that is exchanged once (for a large number of packets) using either “shared secret” or IKE.

Relevant standards for Hash-Based Message Authentication Codes are:

*     FIPS PUB 198, The Keyed-Hash Message Authentication Code, March 2002

* RFC 2104, “HMAC: Keyed-Hashing for Message Authentication”, February 1997. This defines several algorithms, including HMAC-MD5, HMAC-SHA1 and HMAC-RIPEMD (based on the MD5, SHA1 and RIPEMD message digests, respectively).

*     RFC 2403, “The Use of HMAC-MD5-96 within ESP and AH”, November 1998

*     RFC 2857, “The Use of HMAC-RIPEMD-160-96 within ESP and AH”, June 2000

*     RFC 4634, “US Secure Hash Algorithms (SHA and HMAC-SHA)”, July 2006

*     RFC 4868, “Using HMAC-SHA-256, HMAC-SHA-384 and HMAC-SHA-512 with IPsec”, May 2007 A.6 – Internet Key Exchange (IKE)

Internet Key Exchange is part of IPsec. It is used to automate the distribution of symmetric session keys to any number of IPsec enabled nodes, in a secure manner. It depends heavily on asymmetric key cryptography. IKE is based on the Diffie-Hellman Key Agreement algorithm. It is covered in more detail in the chapter on TCP/IPv6 Advanced Protocols.

Relevant standards are:

*     RFC 2409, “The Internet Key Exchange (IKE)”, November 1998

*     RFC 4306, “Internet Key Exchange (IKEv2) Protocol”, December 2005 A.6.1 – IKE using IPsec Digital Certificates

If IKE is used to automate IPsec key management, a full PKI must still be deployed, to create and manage the IPsec digital certificates. One certificate must be generated for each node that participates in IPsec traffic. With IPsec certificates, the public key is bound to IP address(es), not to a Fully Qualified Domain Name and an organization name (as in server certificates) or to a person’s name and e-mail address (as

in client certificates). To simplify the process of having every IPsec enabled node obtain the necessary IPsec digital certificate, the Simple Certificate Enrollment Protocol (SCEP) is typically used to allow nodes tor request and obtain IPsec certificates from a CA without the complex and time consuming manual processes used to obtain server or client certificates.

The shared secret key distribution mechanism is widely used with current implementations of IPsec , but it is likely that only IPsec certificate based automated key exchange with IKE will be allowed in the future.

Relevant standards for IPsec Digital Certificates in IKE are:

*     RFC 4809, “Requirements for an IPsec Certificate Management Profile”, February 2007.

*     RFC 5406, “Guidelines for Specifying the Use of IPsec Version 2”, February 2009 A.6.2 – Diffie-Hellman Key Exchange

One of the first applications of asymmetric cryptography (once it was re-invented) was to securely exchange a symmetric session key between two communicating parties. This is still used today as the heart of the Internet Key Exchange (IKE).

Let’s use Diffie-Hellman to exchange a symmetric session key between Alice and Bob. First there are two public parameters “p” and “g”. The “p” parameter is a very large prime number, while “g” is an integer less than p with certain characteristics. Anyone can know these values. They can be agreed to and shared well in advance, even over insecure channels. They can even be defined and built into a cryptographic system, such as IKE.

1.    Alice generates a random private value “a”, and Bob independently generates another random private value “b”. They don’t share these values with anyone, even each other.

2.    Alice generates her public value X= ga  mod p, and Bob generates his public value Y = gb  mod p.

3.    Alice sends her public value (X) to Bob, and Bob sends his public value(Y) to Alice, over an insecure channel

4.    Alice computes kab  = (Y)a  mod p, and Bob computes kba  = (X)b  mod p

5.    Remarkably, kab  = kba, so Alice and Bob now have a shared secret value, from which a symmetric session key can be derived.

It is computationally infeasible to try to derive the shared secret given Alice’s and Bob’s public values (which are sent in the clear) due to the discrete logarithm problem (another trap door function), assuming p is sufficiently large.

A.7 – Secure Socket Layer (SSL) / Transport Layer Security (TLS)

Probably the most popular cryptographic application is SSL/TLS, which is used to secure HTTP (web) connections. It was originally created by Netscape in their web server and web browser. SSL 2.0 implemented server to client authentication and symmetric key exchange (in SSL 2.0). In a non-secure connection (e.g. web over port 80), a client connects to the server, and is granted access. No authentication is performed, no symmetric key is exchanged, and traffic is exchanged between the server and the client in plaintext.

SSL is implemented as a shim layer between the application layer and the Transport Layer. Only TCP is supported in the Transport Layer – there is no SSL or TLS for UDP. The application must have knowledge of SSL and call socket I/O routines in the SSL library to create a socket, to read and write data, and to close the socket (instead of directly calling the usual routines in the Transport Layer). Significant changes are required to the source code of both the server application and the client application.

SSL can be used in almost any query/response client-server protocol which is implemented over TCP. With SSL, there is both a non-secure port and a corresponding secure port for each protocol. It has been successfully used in HTTP (80/443), LDAP (389/689), POP3 (110/995), IMAP (143/993) and SMTP (25/465). A commercial toolkit from RSA (BSAFE), or an open source toolkit (OpenSSL) can be used to add SSL to any client-server network application.

A server certificate must be obtained and installed in the server application. This digital certificate binds a Fully Qualified Domain Name and an organization name to the public key. The root certificate of the server certificate’s hierarchy must be installed in both the server application and the client application, along with any necessary intermediate certificate(s). These might be hard wired into the applications by the vendor, or installed manually by a system administrator.

If a connection is attempted via the secure port (e.g. web over port 443), then the following exchange takes place before the normal web traffic continues:

1. The server sends its digital certificate to the client in plaintext.

2. The client verifies the validity of the server certificate as follows:

a. The digital signature of the server certificate must be verified using the public key intermediate certificate of the signer (e.g. VeriSign).

b. The digital signature of the intermediate certificate must be verified using the public key root certificate of the server certificate signer (e.g. VeriSign), as hardwired in the web browser by the vendor

c. The current time must be within the validity period of the certificate (after the starting date, but before the expiration date)

d. The Fully Qualified Domain Name from the browser URL must match the Fully Qualified Domain Name (common name) in the server certificate

e. The server certificate’s revocation status must be checked either by consulting the appropriate Certificate Revocation List for the server certificate, or via OCSP.

3. The client and the server negotiate the strongest cryptographic algorithms that they hold in common, both for asymmetric key cryptography (e.g. RSA 1024 bit) and asymmetric key (e.g. RC4 128 bit).

4. The client generates a challenge string, encrypts it with the public key from the server certificate using the agreed upon asymmetric key algorithm, and sends the encrypted string to the server.

5. The server decrypts the encrypted challenge string using its own private key and the agreed upon asymmetric key algorithm. It then returns the result to the client, where it must match the original challenge string which the client had created. This establishes server to client authentication. Only the owner of the private key associated with the public key from the server certificate would be able to pass this cryptographic challenge.

[optional client authentication handshake in SSL 3.0 goes here – see below]

10. The client generates a symmetric session key for the agreed upon symmetric key algorithm and key length. It encrypts this symmetric key using the server’s public key, and the agreed upon asymmetric key algorithm. The encrypted key is sent to the server.

11. The server receives the encrypted symmetric session key and decrypts it using its private key and the agreed upon asymmetric key algorithm. Now the client and the server share a common symmetric session key, which has been exchanged securely. Even if this entire exchange is intercepted by a third party, the symmetric session key cannot be discovered.

Following these steps, all traffic between client and server is encrypted. The sender encrypts the traffic using the shared symmetric session key, and the recipient decrypts the traffic using the same key. Periodically (based on time and or traffic volume) a new symmetric session key will be negotiated and used.

A.7.1 – Secure Socket Layer 3.0 – Optional Strong Client Authentication

In SSL 3.0 (1996), Netscape added an optional second part of the cryptographic handshake. It is enabled by selecting strong client authentication on the server. This can be optional (strong client authentication allowed), in which case if the client has no acceptable client certificate the server will fall back to username/password authentication. It can also be mandatory (strong client authentication required). It this case, if the client has no acceptable client certificate, it will not be able to connect to the server.

The root certificate of the client certificate hierarchy (plus any intermediate certificates) must be installed in both the server and client applications, either hardwired in the application by the vendor, or installed manually by the administrator.

After step 5 above, if strong client authentication is enabled, the handshake includes the following new steps:

6. The server sends a request to the client to present a client certificate, including a filter that specifies criteria for acceptable client certificates

7. The client presents a list of all acceptable client certificates found in its certificate database, from which the user selects one. That certificate is sent to the server in plaintext.

a. The digital signature of the client certificate must be verified using the public key intermediate certificate of the signer (e.g. VeriSign).

b. The digital signature of the intermediate certificate must be verified using the public key root certificate of the client certificate signer (e.g. VeriSign), as hardwired in the web browser by the vendor (or installed by the user)

c. The current time must be within the validity period in the client certificate (after the starting date, but before the expiration date)

d. The common name from the client certificate is extracted to use as the login name. e.    The server certificate’s revocation status must be checked either by consulting the appropriate Certificate Revocation List for the server certificate, or via OCSP.

8. The server generates a challenge string, encrypts it with the public key from the client certificate using the agreed upon asymmetric key algorithm, and sends the encrypted string to the client.

9. The client decrypts the encrypted challenge string using its own private key and the agreed upon asymmetric key algorithm. It then returns the result to the server, where it must match the original challenge string which the server had created. This establishes client to server authentication. Only the owner of the private key associated with the public key from the client certificate would be able to pass this cryptographic challenge. At no point did the owner of the private key have to expose it to anyone in order to prove possession of it.

A.7.2 – Transport Layer Security (TLS) – Continuation of SSL as an IETF Standard

When Netscape released their proprietary SSL 3.0 standard to the IETF, it was further refined and extended as TLS 1.0. Additional cryptographic suites were installed, including Diffie-Hellman asymmetric key algorithms and additional symmetric key algorithms. Also, an optional handshake mechanism was defined for those protocols that could support it (e.g. SMTP) which allows both secure and non-secure connections to use the same port. A connection over TLS begins in the non-secure state, but a negotiation (e.g. using ESMTP extension announcements and commands) can initiate the SSL/TLS handshake and switch to a secure connection over the same port.

There are really no RFCs concerning SSL, as it was a Netscape proprietary protocol. Here are some of the standards related to TLS:

*     RFC 2246, “The TLS Protocol Version 1.0”, January 1999.

*     RFC 2487, “SMTP Service Extensions for Secure SMTP over TLS”, January 1999.

*     RFC 2595, “Using TLS with IMAP, POP3 and ACAP”,  June 1999

*     RFC 2817, “Upgrading to TLS Within HTTP/1.1”, May 2000

*     RFC 3546, “Transport Layer Security (TLS) Extensions”, June 2003

*     RFC 4217, “Securing FTP with TLS”, October 2005

*     RFC 4346, “The Transport Layer Security (TLS) Protocol Version 1.1”, April 2006

*     RFC 5246, “The Transport Layer Security (TLS) Protocol Version 1.2”, August 2008 A.7.3 – Link Oriented Nature of SSL/TLS

SSL/TLS is inherently a link-oriented protocol. It can only secure a single connection such as web browser to web server. For multi-connection scenarios, such as e-mail (client to local server, local server to remote server and remote client to remote server), there is no simple way to insure that all of the links will use SSL/TLS protection, but even if they do, the traffic will be in plaintext on each intervening node, e.g. on intermediate mail servers. S/MIME is the preferred technology for securing e-mail. It takes place in the sending and receiving client, and is transparent to any intervening servers. This is called “end to end”.

A.7.4 – SSL-VPN

VPNs typically need to be end-to-end as well, and IPsec is. Unfortunately IPsec does not work well on IPv4 networks due to the omnipresence of NAT. Because of this, on the First Internet, many people now use a VPN scheme based on SSL, called “SSL-VPN”. There is no IETF standard for this, it uses an Application Layer technology (SSL) in the Internet Layer, and is inherently link-oriented. The only alternative is to add NAT traversal technology to all IPsec clients and servers, which greatly complicates them and introduces serious security issues. VPNs will work well using the approved technology (IPsec) without any NAT traversal mechanisms, only once IPv6 connections are available between the nodes to be connected with VPNs.