Authentication and confidentiality are issues that have fascinated scientists and mathematicians for centuries. Matt Nicholson looks at some of the techniques in use today.
Originally published DNJ Online, May 2006
A man walks into a bank and presents a cheque to the cashier. The cheque is made out in the man’s name, but the cashier refuses to cash the cheque. Why?
There could be many reasons. The cashier could suspect the cheque has been tampered with so as to pay out a larger sum than the payer intended. The cashier could suspect that the customer is not who he claims to be, or that the driving licence he presents as identification is a forgery.
Whatever the scenario, secure communication essentially comes down to authentication and confidentiality. In the real world, authentication is achieved through a passport or a signature, and confidentiality through a sealed envelope or locked safe. In the digital world authentication is achieved through knowledge of a secret code, such as a password or a PIN (Personal Identification Number), and confidentiality through encryption.
The simplest encryption technique, originally attributed to Julius Caesar, is known as secret key encryption because it involves combining a digital ‘key’, known only to the sender and the receiver, with the message using an encryption algorithm. At the other end, the encrypted message can be decoded by applying the same key to the corresponding decryption algorithm. Possession of the key authenticates the sender to the receiver, and ensures that only the receiver can read the message.
This technique is also known as symmetric encryption as the same key is used for both encryption and decryption. Modern examples of secret key systems include the US government-sponsored Data Encryption Standard (DES) algorithm and its successor the Advanced Encryption Standard (AES). The cryptography namespace in the .NET Framework includes support for DES, Rijndael (on which AES is based) and TripleDES, which is a more secure version of the DES algorithm.
The weak link is, of course, the key itself which must be transmitted between sender and receiver before secure communication can take place. Anyone who intercepts the key will be able to decrypt any subsequent messages that use the same key, and indeed masquerade as either the sender or the receiver.
Nevertheless, secret key encryption is still in common use, although usually in combination with other techniques. Under Windows NT and Windows 2000, for example, user passwords are first hashed using the MD-4 algorithm (see below), and the hash then encrypted using the DES algorithm. It is the result of this process that is stored in the Security Account Manager (SAM) database, rather than the password itself.
Windows NT introduced Windows NT LAN Manager (NTLM) authentication, so called because it can also authenticate LAN Manager clients such as Windows 98. This uses a challenge-response mechanism. When a client connects, the server sends a ‘challenge’ in the form of a randomly generated value. The client response is calculated by encrypting the challenge with the hash of the user’s password using the DES algorithm. The server can extract the encrypted challenge because it has the hashed password in the SAM database. However it would be difficult for a third party to extract the hash by intercepting the transaction as the challenge is different every time.
The Windows NTLM mechanism does have weaknesses, so for Windows 2000 Microsoft adopted a rather more sophisticated system called Kerberos. Named after the three-headed dog that reputedly guards the entrance to Hades, the Kerberos mechanism was developed at MIT in the 1980s.
Kerberos relies on a central key distribution centre (KDC) which, under Windows 2000, runs on the domain controller alongside the Active Directory. The KDC is the ‘third head’ of Kerberos, the other two being the client and the server with which the client wishes to communicate.
Each user on the system, and each protected resource, shares a secret key with the KDC. When, for example, Alice wishes to access the mail server, she first contacts the KDC which responds by sending her a ticket that contains various information, including her username and a session key, all encrypted with the mail server’s secret key. Alice then presents this ticket to the mail server which extracts Alice’s username and the session key, validates her username and uses the session key to encrypt subsequent communication.
The use of a ticket makes the system inherently more secure. Buy a ticket to see a particular artist play at a particular venue on a particular night and your ticket will only get you into that concert on that night – it won’t get you into any other concert on the same night, or the same concert later in the week. You had to present the ticket vendor with your credit card in order to get the ticket, but once you have the ticket you can leave your credit card safely at home as the ticket is all the credentials you need.
There is a lot more to Kerberos than this. For example, the Kerberos system does not require Alice to send her password to the KDC every time she wants a ticket. Instead she contacts a separate ticket-granting service (TGS) for a ticket-granting ticket that she can use until it expires. For a more detailed and entertaining description of the Kerberos system see http://web.mit.edu/kerberos/www/dialogue.html.
Clever though Kerberos is, it still relies on shared secret keys. Public key encryption works in a rather different way that is inherently more secure. It involves two key values, known as a key pair: a public key, which the sender makes generally available, and a private key which he or she keeps secret. The two keys are linked by an algorithm such that messages encrypted with one key can only be decrypted using the other.
The process starts with one party using the algorithm to generate a unique public and a private key pair. The public key can be made available to the other party, or indeed to the general public. The private key is not divulged to anyone. Once this key pair has been created, anyone who encrypts a message using the public key can be confident that only the person holding the corresponding private key will be able to read it. Conversely, anyone receiving a message that can be decrypted using the public key can be confident it was sent by the owner of the corresponding private key.
Public key encryption is sometimes called asymmetric encryption, as the keys used for encryption and decryption are not the same. The popular RSA algorithm, invented at the Massachusetts Institute of Technology in 1977, is the algorithm most commonly used for public key encryption.
The beauty of public key encryption is that the private key does not have to be transported between sender and receiver. However, there is a weakness: how do you know the public key actually belongs to the person to whom it claims to belong? This is where certification comes in.
Trusting the trusted
The solution is to encrypt the public key and its owner’s details using the private key of a trusted third party. The result is a digital certificate that has been ‘signed’ by the third party, otherwise known as the Certificate Authority (CA). Once you have obtained such a certificate then anyone who has the CA’s public key can authenticate your certificate and extract your public key confident that it was indeed issued by you. Most certificates in common use are based on the X.509v3 standard, while the use of a CA, or a structure where a top-level CA authenticates multiple lower level CAs, is known as a Public Key Infrastructure (PKI).
- Alice generates a key pair and sends her public key (coloured yellow) to the Certificate Authority (CA) along with her personal details as part of her Certificate Signing Request (CSR). She keeps her private key (blue).
- Once it has authenticated Alice’s CSR, the CA uses its private key (red) to encrypt her public key, together with her personal details, and returns the result to her.
- Alice now has a certificate that she can distribute to, for example, Bob.
- Bob can use the CA’s public key (green) to decrypt Alice’s certificate and extract her public key, confident that it is indeed Alice who holds the corresponding private key.
Your digital certificate is equivalent to your passport in the real world. While customs officials may not trust you as an individual, they do trust a document from your passport office, and will accept it as proof of your identity. Your passport office effectively takes the role of the CA.
That said, most CAs issue different levels of certificates. Before issuing a top-level certificate a CA will make extensive enquiries to authenticate the applicant. However some CAs issue a low-level certificate on little more than a valid email address. Such a certificate is easily forged and should be treated with the same level of credibility as a business card.
Of course such a system only works if all your clients are already in possession of your chosen CA’s public key. Recent versions of most web browsers come with the public keys of a number of recognised CAs, such as Verisign, built in. Furthermore, there is nothing to stop you setting yourself up as a CA. This won’t immediately help on the Internet as no-one outside your organisation will have any reason to believe you are who you claim, but it is a useful strategy over an internal network.
Both Microsoft Windows 2000 Server and Windows Server 2003 include tools for creating and managing a PKI using X.509v3 certificates. The Windows CryptoAPI supports many forms of encryption, hashing and key and certificate management. This functionality is encapsulated within the .NET Framework in the System.Security.Cryptography namespace.
Security and encryption are fascinating subjects which we can only touch upon here. For more information, check out some of the books listed below.
Internet Explorer comes ready installed with the certificates of a number of top-level Certificate Authorities.
The Caesar Shift
One of the earliest examples of encryption was the Caesar Shift, so-called because it was supposedly used by Julius Caesar to communicate with his army. It simply involves rotating the letters of the alphabet by an agreed amount. For example, with a shift of 3, the letter A becomes C, the letter B becomes D and so on until Y becomes A and Z becomes B. Deciphering is easy provided you know the ‘secret key’, which in this case is the number of letters shifted.
The code still exists today in the form of ROT13 which shifts the alphabet 13 places. ROT13 is still to be found on Usenet, for example, where it is sometimes used to hide message text from the casual observer. The advantage of using a shift of 13 is that the same code can be used for both encoding and decoding.
Secure Sockets Layer
Asymmetric encryption requires much more computing power than symmetric encryption. The Secure Sockets Layer (SSL) protocol therefore uses symmetric encryption for the message itself. However, the key is transferred using asymmetric encryption, and discarded once the session is over. The client initialises an SSL session by requesting the server’s digital certificate, from which it can extract the server’s public key. The client then generates a 40-bit session key which it encrypts with the server’s public key and returns to the server, where it can be decoded using the corresponding private key and used to symmetrically encrypt the rest of the session.
Validating the message
Just as important as authenticating the sender and receiver is authenticating the message itself – in other words, ensuring the content has not been changed while the message was in transit. This is usually achieved through the application of a one-way hash algorithm.
Also known as a digest or fingerprint algorithm, a one-way hash is a function that takes a string and converts it into a fixed-length value in such a way that it is hard to reverse the process. Where it differs from an encryption algorithm is that hash algorithms do not require a key value. For example, a simple hash algorithm might sum the ASCII values of the string and then discard all but the lower four places, so the digest of the string “tom” would be 0336. Knowing the digest, it would be impossible to derive the original string.
This is a trivial example because there are so many other strings that would result in the same digest. More sophisticated hash algorithms are designed to minimise the possibility of finding two strings that result in the same digest. Two such algorithms are the MD-4 and MD-5 algorithms (MD stands for Message Digest) which were invented by Ron Rivest, a professor at MIT who was also involved in the RSA algorithm used for public key encryption. Even more secure is the Secure Hash Algorithm (SHA) designed by the National Institute of Standards and Technology (NIST). MD5 generates a 128-bit hash while SHA generates hashes of 256, 384 or 512 bits.
Hash algorithms have many uses. For example, one way of authenticating a message is to hash the message data with a secret key known only to the sender and the recipient. This creates what is known as an MAC (Message Authentication Code). The recipient performs the same operation and if the result is the same as the MAC then the message has not been tampered with, and did indeed come from the sender. This is similar to a digital certificate except that MACs use a secret key instead of a rather more secure public/private key pair.
Most people find passwords difficult to remember which means they often use the same password when registering for an online game as they use for logging into their bank account. This means that, even if your application does not handle personal data or financial transactions, you should never store passwords in plain text.
At first sight, the security support provided by the .NET Framework can seem unnecessarily complicated if all you want is to hash a password string. However hidden in the FormsAuthentication class is a useful function that, while possibly holding the record for the longest method name in history, will return your password hashed with either the SHA1 or the MD5 algorithm:
Verifying a log-in can then be accomplished by hashing the password string entered by the user and comparing it with the hashed value stored in the database.
However, this technique is vulnerable to a so-called ‘dictionary attack’ because any given string will always result in the same hash. The MD5 algorithm will always hash the string “secret”, for example, as “5EBE2294ECD0E0F08EAB”. One way to overcome this is to concatenate the password with a random ‘seed’ prior to hashing, and then store both the seed string and the hash in the database. Assuming sRandomSeed() is a function that returns a random string of (say) ten characters:
sSeed = sRandomSeed()
FormsAuthentication.HashPasswordForStoringInConfigFile(sSeed & sPassword, “md5”)
The nature of hash algorithms means the seed string can be safely stored in the user table alongside the hash of the seeded password without compromising security. This process is known as ‘salting’ the hash.