Cryptography: a Management Overview! by by David S. Burris, Ph.D., CCP, CSP © Copyright 2006 david.burris@shsu.edu Center for Digital Forensics Sam Houston State University Huntsville Texas , 77341

Index:

1) Introduction

2) Basic Terminology

3) Cryptography Goals- Integrity, Authentication, Confidentiality, Non-Repudiation

4) Implementing Integrity - Hashing

5) Implementing Authentication - Digital Signatures

6) Implementing Confidentiality - Cryptography

7) Cost to Break a Key

8) Diffie-Hellmann - exchanging keys over an insecure medium

9) RSA Algorithm

10) Key Stores - remembering and tracking keys

11) Secure Socket Layer (SSL) Logic

12) Cryptography Strategy Summary

Orwellian Assumptions

by the Federal Government:

The government has the right to listen to private communications! There is something wrong with a private citizen trying to keep a secret from the government .

There is a natural tension between governments and their citizens. In general citizens wish to be insured of privacy from other citizens, business interest, and the government. The government generally agrees the private affairs of individual should be protected from intrusion from others but not the government. Citizens point to the "Bill of Rights" and abuse of power by government officials including law enforcement. Government (including law enforcement) reminds us the ability to prevent crime, catch criminals, and protect the populace from terrorist requires the ability to monitor communications.

Indeed the government believes the public should be willing to pay for encryption standards and devices ensuring the government's ability to eaves drop. Remember, these are the same people we associate with President Nixon and Watergate. The same agencies and branches of government who illegally wire taped Martin Luther King's phone. Both groups are correct.

President Bill Clinton's administration proposed the use of the Clipper Chip to protect the privacy of phone conversations. If all new phones were built using the Clipper Chip, then the public would in general be protected from other members of the public.

Use of the Clipper Chip would guarantee your phone could be tapped with ease by the government while you pay for their convenience .

Legislation espoused by President Clinton's administration including the Clipper Chip, Digital Telephony Bill, Forteeza Card, might be viewed as preemptive and unilateral attempts by the Federal Government to usurp powers that previously belonged to the people (circa 1994). In each case the public would generally be protected from itself but not the government or entity with sufficient resources.

The desire for self protection has led to the field of Cryptography. Cryptography includes any technique used to scramble a message such that only the intended recipient can decipher (extract) the message. As a general rule, cryptography has four basic goals.

Return to index:

Basic Terminology

A crypto system or cipher system is a method for scrambling information so only designated people can obtain the information content of the document. Cryptography is the art of creating and using crypto systems. The art of breaking crypto systems is called cryptanalysis . Cryptology is the study of both cryptography and cryptanalysis.

An original message is termed plaintext (or occasionally clear text). Encryption is any method used to disguise the message hiding its substance. The encrypted message is termed cipher text. Cryptography is the science , generally mathematical in nature and implemented using computers, of keeping messages secure. In principal, plaintext can be encrypted using mathematical algorithms manually. In reality, the mathematical algorithms used today to encrypt information require so many computations they are only feasible using relatively powerful computers. People working in the field are known as cryptographers. Cryptanalyst are practitioners of cryptanalysis, the art and science of breaking cipher text. The branch of mathematics encompassing both cryptography and cryptanalysis is cryptology. Its practitioners are called cryptologists.

In general a user presents a message (plain text) to an encryption device, usually a computer running software to implement the encryption algorithm. For convenience, encryption algorithms are implemented in hardware in some environments. Hardware implementation of cryptography algorithms are frequently no faster than software implementations of the algorithms. The product of the encryption device is termed "cipher text" and is typically transmitted over a publicly accessible (insecure) medium such as telephone lines, microwave, fiber optics, or radio waves. One must assume the cipher text may be intercepted (usually copied) while in transmission. Upon arrival at the receiving end, the cipher text is processed by a decryption device to extract the original message. This process is depicted below.

Assume a message is represented by M, the encryption function by E, and the decryption function by D. Mathematically, the following relations must hold:

E(M) = C

D(C) = M, and

D( E(M) ) = M.

During World War II the German's placed their faith in the Enigma Crypto Machine. Security was based on preventing the Allies from obtaining the actual machine. In reality, the Allies were able to obtain an Enigma that was thought to have gone down on a submarine. This allowed the Allies to decrypt many communications to their advantage for an extended period of time. This example emphasizes the danger of placing your faith in the security of the encryption device or algorithm. The enemy or competition will eventually obtain the device or algorithm. A goal of cryptography is to ensure privacy under the assumption the enemy has the encryption / decryption machine or algorithm.

If the security of the algorithm is based on keeping the algorithm secret, then it is called a restricted algorithm. Note that once a member of the group using the algorithm leaves or the algorithm is stolen, the method is forever compromised. Today most ciphers depend on using a key to initialize the algorithm. Security is based on the key, not the secrecy of the algorithm. It is assumed that everyone has the algorithm or will obtain it. In fact cryptographic algorithms are typically standardized after being subjected to public scrutiny for extended periods of time. The purpose of the public scrutiny is to allow for a large body of experts to examine the algorithm and verify its strength or weakness.

Again, the security of the algorithm is based on the "key" supplied by the algorithms user, not the algorithm. The range of possible values taken on by the key (key space) is assumed to be sufficiently large that an exhaustive attempt to decode the message is too costly for the information content obtained or that it cannot be completed in a timely manner, i.e., the knowledge is no longer of value by the time it is obtained.

Warning, there is absolutely no algorithm that absolutely guarantees the safety of the encrypted message. If the key is stolen or lost, the person who has obtained the key has full access to all messages encrypted using the key. Worse, you must have a lot of faith in statistics.

Even if the odds are a billion to one on guessing the key value, it is still possible the key could be guessed on the first attempt.

If the same key is used for encryption and decryption the algorithm is classified as symmetric and functions as follows.

The following must be true mathematically:

E K (M) = C

D K (C) = M, and

D K ( E K (M) ) = M.

Some algorithms use a different key for encryption and decryption. Such algorithms are called asymmetric algorithms. Assume the encryption key is K1 and the decryption key K2 .

We emphasize the security of the method is based on the key, not on the secrecy of the algorithm ! Symetric algorithms may be up to 1000 times faster than asymetric algorithms at the same level of security!

Assume a Key1 may only be used to encode messages and Key2 may only be used to decode messages. If Key1 is distributed publicly to encode messages intended for the holder of Key2 held privately (as a secret key) we call this a Public Key Algorithm. Some algorithms reverse the roles of key1 and key2. Occasionally, both the public and private key may be used as a key pair for encryption and decryption. Any algorithm employing a key pair where one key is kept private (the secret key) and the other key of the pair is made public is termed a Public Key Algorithm.

Only the bank can decrypt the transaction!

Return to Index:

Message Digest Computation

Hashing is primarily used to implement " integrity " by creating message digest. These digest are used to detect undesired modification of an objects contents in the future due to user error or hackers.

For example, assume that a hacker has cracked a Linux (UNIX) system. Hackers frequently modify system files such as /etc/passwd to contain new passwords allowing them access to the system in the future (trap door) if their original means of entry (hole) is fixed (plugged). If you suspect a system may be hacked, you employ a "detection strategy" in an effort to verify the systems state.

Detection strategies for modified system files.

•  Check the file creation date. Most systems modify a date and / or time stamp when a file is modified. No self-respecting hacker will allow himself or herself to get caught this easy. Hackers modify the file creation date or manipulate the system clock to reflect the required date and time stamps.

•  Periodically save copies of all crucial system files on backup media. If you suspect the system is breached, compare the current system file with the backup version of the files. If the files are identical, the system does not reflect a hack (break in). How far back should copies be saved and checked? Backups made since the penetration will be compromised.

•  Create a hash code or digest that represents the file. If penetration is suspected, hash the suspected file creating a new message digest for the suspected file and compare to the saved message digest computed when the file was created. Hash codes (digests) are typically short (e.g., 20 bytes for the SHA algorithm). Hence storage space and comparison time are minimal. For additional protection, the hash code may be kept on a removable storage device such as a CD or DVD created as a closed session (the media may not be modified at a latter date). A memory stick (potentially not quite as good) could also be used to hold the hash (message digest). By keeping the digest off line, it would be harder for the intruder to forge detection information to match the modified files.

It is possible to write your own hash function but this is discouraged. Amateurs tend to make non-obvious mistakes. You are encouraged to use standardized hash functions that have with stood the test of public scrutiny.

Hash algorithms generate the same footprint regardless of the size of the file. For example the SHA (or SHA-1 - "Secure Hash Algorithm") always produces a 20 byte message digest ( http://www.itl.nist.gov/div897/pubs/fip180-1.htm) . The "Secure Hash Algorithm" is defined in Secure Hash Standards, NIST FIPS 180-1 (National Institute of Standards and Technology Federal Information Processing Standards Publication).

The RSA-MD2 is defined in RFC 1319 and RFC 1423 (RFC 1423 corrects a mistake in RFC 1319). The result is a 16 byte digest suitable for digital signatures. See http://www.faqs.org/rfcs/rfcs1319.htm and http//www.faqs.org/rfcs/rfc1423.txt. RSA is an acronym for the algorithms authors Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman.

RSA-MD5 is defined in RFC 1321. It produces a 16-byte digest and is very fast and popular on 32-bit machines. See http://www.faqs.org/rfcs/rfc1321.txt

You are encouraged to explore how a hash function works using the following Java Applet. After trying several plaintext messages, try again changing or adding a single character and observing the affect on the resulting message digest (hash code). You may have to allow "popups" in your browser or change you security level to utilize the applet. Do not forget to reset your security setting at the end of the session if modified.

Hashing may be used for more than security. As an example, assume you have been hired by Microsoft to manage software downloads. To improve performance, it is desirable to have multiple servers located at different geographic location. The redundant locations are frequently refereed to as "mirror" sites. It is essential the software on the mirror sites be identical to the software on the main server.

To verify a mirror site is correct:

1) Calculate the hash for the main software site or a specific module for download.

2) Compute the corresponding hash on the mirror.

3) If both hash codes are the same, then the sites are identical as desired. If the hash codes differ, then there is a problem.

Return to Index:

---

Authentication Is Achieved via Digital Signatures

Digital Signatures:

Digital Signatures are associated with asymmetric public key cryptography. Assume a bank's main office desires to notify all branch banks to transmit detailed status information. The main bank creates a message stating what information is desired and associated restrictions. Due to the size of the message and fact the request is routine, a decision is made to transmit the message in the clear (unencrypted). We must however make sure all branch banks can validate the message is authentic. For convenience assume the bank's private key and public key may used as pairs for encryption and decryption. Further assume we have all agreed to compute hash codes using the SHA algorithm (with an appropriate padding scheme, etceteras).

Note anyone with the bank's public key can authenticate the message.

When a branch bank is ready to transmit the final status report they may use the following protocol.

Note the branch bank is sure they are communicating with the main bank as only the main bank could decrypt their message to obtain the symmetric algorithm (and symmetric key) using the main bank's private key. The main bank has not however verified the identity of the branch bank. Any holder of the main banks public key could have initiated the conversation. It is common business practice between financial institutions and merchants to verify the identity of the financial institution but not the merchant. It is generally felt the cost of verification in both directions exceed the financial risk. This is one area were identification in both directions might be used to reduce "identity theft."

Digital Signature Summary:

In general a digital signature consists of calculating a has code for a document then encrypting the has code with the private key. The hashed document may be plaintext or encrypted text. The encrypted hash code is the digital signature. The signature is verified by the receiving party calculating first calculating the hash code. They then decrypt the transmitted signature using the senders public key to retrieve the senders message digest (hash code). If the hash codes (message digests) are identical, we accept the message as both authenticated and having arrived without modification. This also implements non-repudiation!

Case Study:

It is important users of cryptography understand the basic concepts and apply them properly to their individual situation. An an example, franchise owners of a drugstore chain wish to host common sales. First they agree upon which manager will decide the product to be placed on special this month. This manager is responsible for creating sales literature and making it available to all other managers via the Internet subject to the following conditions.

First it is desirable to communicate the sales literature in the clear. We do not mind if the competition and customers receive the sales literature. In fact we encourage wide distribution of the sales literature by consumers and consumer groups. Secondly, we wish to minimize the number of secret keys that must me share. All store managers currently have a secure copy of a symmetric Blowfish key. The All managers have agreed on the following procedure.

Note we do not directly verify the identity of the sales literature creator. We know two things for sure. First the sales literature was created by a manager. Secondly, so long as the key has not been compromised (stolen or lost), we have reasonable confidence the advertising material has not been compromised. In any case, if the material appears unreasonable, it is not difficult to verify specific information by phone (with the associated delays). Note the entire sales literature could have been encrypted and signed for additional security.

Assume our environment has changed such that we must be able to authenticate every manager, i.e., every manager must be able to verify the identity of the sender of every message using public key cryptography (a public and private key). If there are M managers then each manager will have to retain (store) their own public / private key pair plus exchange and store (M-1) additional public keys (one for each of the other managers) for a total of (M+1) keys per manager. Now the manager responsible for creating the literature signs it using their private key. The other managers must then select the appropriate public key to verify the message. In our original example, only a single key was required. Verification of individual managers using public key cryptography has substantial overhead in terms of the number of keys required.

Please try the idea using a single symmetric key for the communications held secretly by the managers as a group. The following applet utilizes the DES algorithm to create a symmetric key signature. The user is required to supply an eight character secret key (make one up). You may have to allow "popups" in your browser or change you security level to utilize the applet. Do not forget to reset your security setting at the end of the session if modified.

Return to Index:

Cryptography is used to scramble (disguise) information so only designated people can obtain the information content of the document. An original message is termed plaintext (or occasionally clear text). The encrypted message is termed cipher text. You can better understand the difficulty of retrieving information from an encrypted message by encrypting a message yourself, viewing the encrypted results, then retrieving the encrypted text. The following uses the DES algorithm and requires the user to enter an 8 character encryption key. The key must be supplied latter to retrieve the message. You are encouraged to supply the wrong decryption key when prompted then try again with the correct key. You may have to allow "popups" in your browser or change you security level to utilize the applet. Do not forget to reset your security setting at the end of the session if modified.

Encryption Basics

1) Codes, Ciphers, Hybrid Systems, and Authentication

a) Codes are used to encrypt plaintext at the word level or higher (frequently used to data compression for whole phrases).

b) Ciphers generally encrypt text by the letter or by the byte in the case of digital ciphers. Unencrypted text is called plaintext. Encrypted text is called cipher text. (symmetric and asymmetric)

c) Hybrid Systems normally assumes that communications starts between two users exchanging a symmetric "session" key using an asymmetric cipher. The more efficient symmetric key is then used for the bulk of the message exchange. Changing session keys at the start of every conversation makes it harder for anyone attempting to decipher messages.

d) Authentication using Certificates , normally associated with asymmetric ciphers: Assume Bob knows Samira's public key but Robert does not know Samira's public key. Robert can be reasonably sure he has the correct public key for Samira when communicated by Bob in the following manner. First, Bob creates a file with some information about himself and Samira to communicate to Robert. This file must contain Samira's public key. Bob signs the file digitally by calculating a "message digest." Bob encrypts the message digest using his private key and includes the encrypted digest (digital signature) in the message. Upon receiving the file, Robert 1) decrypts the digital signature using Bob's public key. The result is a message digest. 2) Robert calculates the message digest (exclusive of the digital signature) himself. 3) If the message digest calculated by Robert is the same as the message digest transmitted by Bob, then Robert knows the message has arrived intact. Since Robert trusts Bob, he now feels confident that he does indeed have Samira's public key. When a message is passed in this manner through multiple people, it is referred to as a certificate chain . Many believe that the hierarchical certificate chaining popular on the Internet to a few trusted Certificate Authorities (CA's) is a major weakness . If the private key of a CA is obtained, all sorts of bogus certificates maybe issued.

2) Symmetric versus Asymmetric ciphers.

a) Symmetric or Secret Key : The same key is used for both encryption and decryption. The key must be communicated in a secure manner. If the key is obtained by anyone else, they can both encrypt and decrypt messages. Examples include DES and Blowfish. Keys may be implemented in hardware or software. DES has been implemented both ways. Symmetric encryption is frequently 1000:1 faster than asymmetric.

b) Asymmetric or Public Key: Typically two keys are utilized, a private key for decryption and a public key for encryption. The public key may be broadcast over a network. Anyone may encrypt a message using the public key. Only the holder of the private key may decrypt the message, e.g., for credit card information transfer. The public key may not be used to decrypt a message encoded using the public key. Authentication of the identity of the party sending the message by the holder of the private key is not normally possible. Primary problems include how do I know I really have the desired public key? How can I be assured a bogus key has not been substituted? Public key encryption is computationally expensive. In general more than twice as many bits are required in the keys to give the same level of protection as symmetric key encryption.

Assume a message has been encrypted using a private key. We decrypt the message using the corresponding public key. Under these circumstances, authentication is automatic as only one person holds the private key.

Asymmetric Key Possibilities

c) The most famous public key system is RSA and is patented. It was developed by Ronald L. Rivest, Adi Shamir, and Leonard M. Alderman. RSA has the unusual property that both keys (public and private) may be used for encryption and decryption . Individuals send encrypted messages using the public key. You decrypt them using the private key. In addition you may send a message encrypted using your private key. The message may be decrypted by anyone holding a copy of your public key. RSA is based on the difficulty of factoring a large number into two large prime numbers. It is currently thought to be very secure. See http://www.rsa.com/rsalabs/pubs/PKCS/ .

---

Digital signatures for messages sent in the clear or encrypted using symmetric encryption algorithm are normally created in the following manner.

1) A hash code is created for the plaintext or symmetric encrypted message.

2) The hash code is encrypted using the senders private key.

3) The encrypted message is transmitted with the hash code of the message.

The receiver verifies the signature as follows:

1) The receiver computes the hash code for the received plaintext or encrypted message.

2) The transmitted hash code is decrypted with the senders public key.

3) If the hash codes are identical, then the message could only have been sent by the holder of the private key. In addition, the message has arrived intact.

This assumes that the private key has not been stolen. Note that the plaintext may be sent in the clear with a hash code as a digital signature. If the encrypted hash code can be decrypted, we know that the owner of the private key sent the message. In addition, the hash code may be used to verify the message was not altered. Finally, non-repudiation is established as hash codes are unique (or there is almost no probability of creating a meaningful message with the same has code). The reason for sending the message in the clear with an encrypted digital signature is the reduction in overhead with respect to encrypting a hash code versus the entire plaintext.

3) Keys

Keys are a sequence of bytes used to parameterize a cipher. In practice, once plaintext is encrypted, it is not possible to reasonably reconstruct the original text without knowing the key. The assumption is that a cracker has access to the cipher. By changing keys to initialize the cipher, multiple users may safely use the same cipher.

The traditional approach to cracking a code or cipher is exhaustively trying all key combinations.

The number of possible keys is usually a function of the key length. Hence longer keys are preferred . Keys of 56 bits or less have been breakable using off-the-shelf equipment since the 1980's. Key lengths of 512 bits are considered the minimum length for reasonable security . Long key lengths do not however guarantee security if a weak cipher is used for encryption. Keys should be completely random and include non printable characters. As a rule of thumb, an asymmetric algorithm must utilize more than twice the number of bits in an asymmetric algorithm to provide the same level of security.

Names and words in dictionaries should not be used. Avoid anything that increases the ability of a cracker to predict part of the key or to reduce the number of possibilities. For example, in English, the letter "q" is almost always followed by the letter "u."

If an 8 byte key allowing all possible bit combinations is used the number of keys is (2**8)**8 = 18,446,744,073,709,551,616. If only lower case letters of the alphabet are used then, the number of possibilities for an 8 byte key is reduced to 26**8 = 208,827,064,576. If only English words are used then the number possibilities is just all 8 letter words in the dictionary . This represents a drastic reduction in the number of possible keys. The government never used the 56 bit DES standard itself.

Passwords are commonly "salted" by combining them with a random number that is also stored in the cipher text. Salting increases the space for a dictionary-based attack by several orders of magnitude. A password is frequently massaged by a padding scheme and hashing to produce a more randomized key .

Since keys are difficult for humans to remember, Java offers a digital lockbox for storing keys (security.KeyStore class). The user of the lockbox only have to remember the password allowing access to the box, and name of the keys it contains. For more information on Java's approach see "Java Cryptography" by Jonathan Kundsen, O'Reilly, ISBN 1-56592-402-9 is recommended.

Return to Index:

Cost to Break a Key

Assume a brute force attack by exhaustively trying all keys and the attacking machine can generate and try a key in 0.01 seconds. We attempt to develop a feel for the effort to break keys of various length. We assume that half the key values must be tried on average to determine the correct key. The maximum number of keys that must be tried and the average number of keys to try is exhibited below for several key lengths.

Number of key combinations for a fixed number of characters.

Legend:

Lc 26 lower case letters, 26**(number characters)

Uc 26 upper case letter, 52**(number characters)

Digits 10 digits, 62**(number characters)

Sp. Chars. 34 special characters including ~`!@#$%^&*()_-+={}[]|\:;"'<,>.?/ or 96**(number characters)

Binary all combinations assume 8 bit characters, 256**(number characters)

The following conversion were used assuming 60 seconds per minute, 60 minutes per hour, 24 hours per day, and 365 days per years. Leap years were not considered (treated as having negligible effect). Then:

3600 sec/day

86400 sec/day

31536000 sec/yr

The maximum time to break a key was computed as = (numberKeys * 0.01 sec/key) / # sec/time_period . Time to Break: We assume a single processor requiring 0.01 seconds to generate and check a key. We assume no interruptions in the attempt to break the key, e.g., no machine maintenance and no power failures. Fractional times have been truncated occasionally for convenience. The average time was assumed to be half the maximum time to break a key.

Time to break a key:

......................4 char..........6 char..........8 char...........10 char

Please consider the maximum number of attempts for a 10 character key allowing lower case + uppercase + special characters of 21,081,704,591.30 years or 2.1 x 10**10 years. Some physicist estimate the current age of the universe as 10**10 years based on the Big Bang Theory. Hence it would require our computer to run without interruption for twice the current age of the universe to try all keys. The good news is on the average, it would break the key if allowed to run the current age of the universe.

How much are you willing to spend to break the encryption? Consider using an array of 4096 processors running in parallel to cooperatively break the key. Some universities have built larger machines. Then it would only require 21,081,704,591.30 yr / 4096 = 5,146,900 years maximum. Assume a machine has been built with 1 million processors costing $200 each for a total cost of $200,000,000. Then the time to break the key exhaustively would be at most 8392993658.6 seconds or 266.14 years. A government or drug cartel might be willing to build several such machines and run them in parallel to further reduce the time to break a key.

Crackers do utilize brute force techniques but are more likely to narrow the range of keys they have to try. Most people use only a six character numeric key (10**6 = 1,000,000 possibilities) or six character alphabetic key (26**6 = 308,915,776 possibilities). Assuming all lower case or all upper case, we could break any six character key in 3.089 seconds. Names and word from dictionaries are popular. This further reduces the required search space to crack a key as not all six character letter combinations are names. Creating keys with at least two letters (both upper and lower case), two digits, and two special characters tremendously reduces the chance a casual cracker will break your key. It is not as effective as using all binary bit combinations possible for a given key length.

The decision on how long a key should be is related to the expense of encryption / decryption and length of time the document must remain secure. The time to encrypt / decrypt a message is essentially exponential encouraging reduced key length. A message that must remain secure for five hours does not require as much protection as a message that must remain secure for five months or 5 years. A key of 512 bits to 1024 bits utilizing all bit values (eliminates keys generated at the keyboard) should provide reasonable symmetric key protection. Public key (asymmetric) algorithms usually require more than twice as many bits in the key to provide the same protection as symmetric algorithms.

By 2006 password cracking software was advertising speeds of 3 to 4 million keys per second. That implies rates of 3 * 60 = 180 million keys per minute. This is sufficient to crack dictionary based passwords or encryption keys very rapidly.

You must have faith in probability: A cracker could get lucky on the first guess!

Social Engineer Version 1:

Cracker on Phone: Hello, I am from Computer Services and we have been having problems with computers in your department. If yours is working properly do yohave 10 minutes to help me restore the other machines and make sure yours does not go down?

Employee: Yes

Cracker: Thank you. Please download the diagnostic software at http://keyStrokeLogger and double clike it. Good. Now log out and log back in. Thanks, I see what the problem is and should be able to restore the other accounts thanks to your help. Before I hang up we need to delete the diagnostic software.

Social Engineer Version Two:

Cracker on Phone: Hello, I am from Computer Services and we have been having problems with computers in your department. If yours is working properly do yohave 10 minutes to help me restore the other machines and make sure yours does not go down?

Employee: Yes

Cracker: Thank you. What is your account name and password so I can complete the examination process?

Social Engineer Version Three:

Cracker on Phone: Ask for every day information using common company jargon. As long as you sound official, employeees will typically help another employee. The mayt even fax material to you off site if the information is commonly used within the company. Note employees do not generally think about guarding what they consider to be "routine" information even when it is critical.

Return to Index:

Diffie-Hellman Key Agreement

Classic problems associated with the Internet include how to exchange an encryption key over an inherently insecure communications medium, how to authenticate the person we are communicating with, and how to prevent unauthorized parties from obtaining message contents. This problem was partially solved in 1976 in a paper published by Diffie-Hellman. Diffie-Hellman are generally considered to have originated the idea of public key cryptography. The basic idea is two users, say Han Solo and Luke Skywalker, can dynamically determine an asymmetric secret key over an insecure medium such as the Internet. While they will know the asymmetric secret key, eavesdroppers will not be able to reasonably determine the secret key even if they hear every message transmission. Once established, this asymmetric secret key is normally used to generate a symmetric secret key used to efficiently encrypt and decrypt the rest of the conversation. A new secret key (both asymmetric and symmetric session keys) is usually agreed upon at the start of each new conversation. Agreeing on a new secret key for every communication session further increases the difficulty for eavesdroppers.

Assume that Han and Luke need to establish a secret key (session key). They are aware that the Empires spies will intercept their transmission. The general technique follows. This technique requires two parameters, base (g) and modulus (p), to be set by a central authority (accessible by both the good and bad guys). One implementation of the central authority is currently located at http://skip.incog.com/spec/numbers.html . The Simple Key Internet Protocol (SKIP) provides several bases including 512, 1024, and 2048 bits. The base and modulus are selected such that g is primitive mod p. That is for every value, b, from 1 to p-1, there is some value, a, that satisfies (g** a) mod p = b where g**a implies "g" raised to the power "a."

•  Han randomly selects a value, x, and computes y = (g**x) mod p. We refer to these values as xHan and yHan as the belong to Han.

•  Luke chooses a random x and calculates the corresponding y = (g**x) mod p. We will refer to these as xLuke and yLuke.

•  Han sends Luke yHan and Luke sends Han yLuke. These values are communicated in the clear (transmitted over the insecure network). They may not be used for authentication.

•  Han now computes KeyHan = (yLuke ** xHan) mod p. This is the same as g**(xLuke * XHan) mod p.

•  Luke calculates KeyLuke = (yHan ** xLuke) mod p. This is the same as g**(xHan * xLuke) mod p

Both Han and Luke now have a copy of the asymmetric secret key (session key), i.e ., KeyHan is identical to KeyLuke .

This secret (session) key (or its hash) is normally used to initialize a symmetric cipher such as DESede to encrypt and decrypt information exchanged (plaintext) for the rest of the session. It is unfortunate that Diffie-Hellman cannot be used for authentication. All Han and Luke know for sure is that the user on the other end of the communications is familiar with the algorithm if communications are successful. It could be used for authentication if values of g and p known only to Han and Luke are used. Then you have the problem of communicating these values (p and g) and keeping them secret. In general, Luke and Han would need to agree upon these values prior to separating.

Diffie-Hellman can be expanded to include three or more participants. For an excellent discussion of how to do this, please see "Java Cryptography" by Jonathan Knudsen, page 58 or any standard text on cryptography.

Diffie-Hellman is vulnerable to" the man-in-the-middle attack." This assumes that unknown to Han and Luke, an agent intercepts all communications between Han and Luke and substitutes his own information for each exchange, i.e., Han and Luke only communicate through the middleman, whose existence is not known to them.

It has been suggested these techniques be combined with cryptographic signatures to authenticate each party. The secret key can now be used as described to generate a symmetric key for further communications. The patient for Edifice expired in 1998.

A public domain implementation of Diffie-Hellman is known as the Simple Key Internet Standard located at http://skip.incog.com/spec/numbers.html . The following is an actual 1024 bit secret key generated using the 1024 bit key base found on the the SKIP standard. The 1024 DH parameter defined by SKIP is the first 79 bytes of the ASCII representation of a quote by Gandhi. "Whatever you do is insignificant, but it is very important that you do it." 512, 1024, and 2048 bit modulus parameters are supported. The resulting keys are the length of the modulus, i.e., 512, 1024, or 2048 bits.

The above description for Diffie-Hellman specified the base and modulus are selected such that g is primitive mod p. Another way to state this mathematically is : If "p" is a prime and "g" is less than "p," we say "g" is a generator modulo "p" if for each "b" from 1 to (p-1) there exists some "a" where (g**a) = b (mod p).

Stated another way, g is primitive with respect to p. As an example assume p = 11. Then 2 is a generator mod 11 since:

2**10 = 1024 = 1 (mod 11) , i.e. 1024 mod 11 = 1 (e.g. 1024 / 11 = 93 remainder 1 or 1024 modulo 11 = 1)

2**1 = 2 = 2 (mod 11) , i.e., 2 mod 11 = 2

2**8 = 256 = 3 (mod 11) , i.e., 256 mod 11 = 3 (e.g., 256 / 11 = 23 remainder 3)

2**2 = 4 = 4 (mod 11)

2**4 = 16 = 5 (mod 11)

2**9 = 512 = 6 (mod 11)

2**7 = 128 = 7 (mod 11)

2**3 = 8 = 8 (mod 11)

2**6 = 64 = 9 (mod 11)

2**5 = 32 = 10 (mod 11)

Hence every number from 1 to 10 can be expressed as 2**a (mod p). "p" = 11 is a frequent example with known generators of 2, 6, 7, and 8. Note other numbers in the range fail to be generators, e.g., 3 fails as 3**a = 2 (mod 11) does not exist.

In practice, p should be a very large and (p-1)/2 should also be prime. "g" is frequently selected as a one digit number. The security of the system is based on factoring numbers with the same number of digits (same size) as p.

Diffie-Hellman can be extended to include additional people in the conversation. As an example, assume Luke Skywalker, Han Solo, and Princes Leia wish to carry out a private conversation. This can be accomplished as follows assuming g and p are publicly available or have been selected previously. We assume all passes of data are circular to the right.

At this point KeyLuke = KeyHan = KeyLeia! The extension to additional users is straight forward.

To obtain a better feel for the security provided via keys under Diffe-Hellman, try the following Java Applet to calculate the shared secret key for Luke and Han. You will be required to enter values xLuke and xHan. The software calculates and prints yLuke and yHan. Next, the software computes and prints keyLuke and keyHan. The Skip 1024 bit standard is utilized for all calculations ( the skip base is 2 and modulas corresponds to the numeric representation of the quote by Gandhi, "Whatever you do is insignificant, but it is very important that you do it.)" You system may have trouble printing all digits in large keys. If there is a viewing problem, select smaller values of xLuke and xHan.

Care must be take to avoid the "Man in the Middle" attack!

Assume Darth Vader has positioned himself between Luke and Han. The general format for the "Man in the Middle " attack using asymmetric cryptography is:

1) Han sends Luke his public key. Vader intercepts the communication and sends Luke his (Lord Vader's) public key.

2) Luke sends Han his public key. Vader intercepts the communication and sends Han his (Lord Vader's) public key.

3) When Han sends Luke a message it is really encrypted with Vader's public key. Only Vader can decrypt the message using his private key. Vader then encrypts the message with Luke's public key and sends it to Luke potentially with appropriate changes.

4) When Luke sends Han a message it is really encrypted with Vader's public key. Only Vader can decrypt the message using his private key. Vader then encrypts the message with Han's public key and sends it to Han potentially with appropriate changes.

In Diffie-Hellman, Lord Vader makes appropriate substitutions during the key computation so he essentially winds up with a shared secret key with Han and another shared secret key with Luke. There are methods to prevent or minimize the possibility of Vader successfully employing a man in the middle attack. Note it helps if Lord Vader has exclusive control of a communications node.

Summary:

In 1976, Winfield Diffie and Martin Hellman developed "public key cryptography" at Stanford University to solve the problem of exchanging keys securely over an insecure medium. It uses two inversely related keys: a private key and a public key. Public key cryptography is asymmetric. The owner keeps the private key secret while the public key is made freely available. If the public key is used to encrypt a message, only the private key may decrypt the message and vice versa. Although the two keys are mathematically related, deriving one key from the other is computationally infeasible.

Note if a private key is compromised, it is only necessary to create a new private / public key pair. It is not necessary to modify the entire encryption or decryption algorithm. Prior to modern cryptography, security was placed in keeping the (closed) algorithm or machine (Enigma) secret. If the machine or algorithm was compromised, the entire system was compromised and a new secret algorithm or machine had to be created.

Unfortunately, public key encryption is computationally expensive and hard to use for passing large amounts of information. Typically, public key encryption is used by both parties of a communications to agree on a "symmetric key algorithm" and "symmetric secret key" for passing large of amounts of information during a single session. Hence a different secret key is used for each communications session.

RSA is the most popular asymmetric algorithm currently in use. It was developed in 1977 by professors Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. It is built into most popular web browsers and is widely used for e-commerce transactions. See http://www.rsasecurity.com for information.

Pretty Good Privacy (PGP) was developed in 1991 by Phillip Zimmermann and may be obtained at http://www.web.mit.edu/network/pgp.html . PGP is widely used for encrypting email messages and files. PGP is public-key based and depends on a "web of trust" where each client can vouch for another client's identity to prove ownership of a public key. Originally designed as a human rights tool, PGP was published for free on the Internet in 1991. This made Zimmermann the target of a three-year criminal investigation, because the government held that US export restrictions for cryptographic software were violated when PGP spread worldwide. Despite the lack of funding, the lack of any paid staff, the lack of a company to stand behind it, and despite government persecution, PGP nonetheless became the most widely used email encryption software in the world. After the government dropped its case in early 1996, Zimmermann founded PGP Inc. When that company was acquired by Network Associates Inc (NAI) in December 1997, Phil stayed on for three years as Senior Fellow. In August 2002 PGP was acquired from NAI by a new company called PGP Corporation. Phil now serves as special advisor and consultant for PGP Corporation. He is also consulting for a number of companies and industry organizations on matters cryptographic, and is a Fellow at the Stanford Law School's Center for Internet and Society.

Return to Index:

RSA

Diffie and Hellman first presented their public key encryption ideas at the 1976 National Computer Conference. Their work was followed shortly by a variety of "knapsack" algorithms, led by Ralph Merkle and Martin Hellman. The first industrial strength algorithm to implement public key cryptography allowing encryption and digital signatures however was the RSA algorithm named for its authors Dr. Ron Rivest, Dr. Adi Shamir, and Dr. Leonard Adleman. Netscape adopte RSA in its browser to implement SSL for e-commerce. RSA quickly became an international defacto standard. In fact the three jointly won the ACM's 2002 Turing Award for their work in public key cryptography.

The difficulty of breaking the algorithm is thought to be related to the difficulty of factoring large numbers with public and private keys numbering over 100 digits each. Cryptanalysis has neither proved or disproved the security of the algorithm. It has however withstood the test of time as it has been a constant target. RSA is probably the least complicated public key algorithm.

Key generation is accomplished by randomly selecting two large prime numbers p and q. P and q should have approximately the same number of digits for maximum security (typically 100 or more). Compute the product n as n = p*q.

Now randomly select an encryption key e such that e and (p-1)*(q-1) are relatively prime (see the Diffie-Hellman explanation involving generators). Using the extended Euclidean algorithm, compute the decryption key d such that e*d = 1 modulo((p-1)*(q-1)). This implies d = e **(-1) mod ((p-1)*(q-1)). Both d and n will be relatively prime.

Both e and n may be used as the "public" key. "d" is the private key. The primes p and q may now be discarded but should never be revealed. They can be retained to speed up private key operations in conjunction with the Chinese remainder theorem.

Encryption is accomplished by breaking text up into numerical blocks smaller than n. For binary data, the largest power of 2 less than n should be used. Remember, internally, all text appears as a string of digits to a computer (just a large number). If the text is broken into block of size m(i) , then the encrypted message c will consist of message blocks of about the same length. Formally, c(i) = m(i)**e modulo n. The notation m(i) means "m sub i," i is a subscript written in the style of programming languages. If both p and q are approximately 100 digit primes each, then the product n = p* q should be approximately 200 digits in length. This implies message blocks will be just under 200 digits in length.

Decryption is accomplished by computing m(i) = c(i)** d modulo n. Again, the message could have just as well be encrypted using d as the key and decrypted using e. The choice of encryption key is arbitrary.

As an example, assume the widely published sample values of p = 47 and q = 71. Then n = p*q = 47*71 = 3337. The encryption key, e, must have no common factors with (p-1)*(q-1) = 46*70 = 3220.

Assume we randomly select e = 79. Then d = 79**( -1) modulo 3220 = 1019 calculated using the extended Euclidean algorithm. The secret key is d = 1019. Either e = 79 or n = 3337 may be used as public keys.

Assume the ASCII equivalent of a text message is m = 42571627531278 and we decide to break it into 3 digit blocks as follows:

Encryption is accomplished by:

Note we padded the last block with a zero (spaces or appropriate text from a padding algorithm).

The resulting encrypted text is c = 2058 240 1519 3262 1609

Decryption is accomplished by:

RSA encryption in hardware is available from many vendors. It is not unusual for RSA hardware algorithms to run 1000 times slower than corresponding DES hardware encryption. In software, RSA is typically only about 100 times slower than DES.

Return to Index:

Key Stores :

In general, it is unreasonable to expect people to remember 56 bit, 512, bit, 1024 bit, 2048 bit, and larger keys. The solution is to store them in digital lockboxes and refer to them with names. We demonstrate the idea using Java's keytool for creating lockboxes to hold symmetric and asymmetric keys. An example of creating an RSA key pair in a "keystore," creating digital certificates, and digital signatures using the RSA Algorithm. See the "DSA" algorithm in the discussion of "KeyStore" for a more detailed explanation.

Step 1: Create the RSA public and private keys placing them in a keystore by executing MakeRSAKeystore.bat. The explanation of the parameters is contained in the discussion of the DSA algorithm (originally developed as a public domain substitute for RSA). This command has been placed in the file MakeRSAKeystore.bat for your convenience. The work is accomplished from the system (command) prompt on a windows box. The following creates a lockbox named "BurrisRSAStore" with a private / public key using the RSA algorithm of 1024 bits named "superkey.". The password to enter the store is "storePassWrd" and the password to retrieve the RSA key pair (or parts) is "keyPassWrd." The user command is in blue and the system response in green.

C:\> keytool -genkey -alias superkey -keyalg RSA

-keysize 1024 -keystore BurrisRSAStore -dname "cn=David Burris, ou=Computer Science,

o= Sam Houston State University , L= Huntsville , S= Texas , c= USA " keyPass keyPassWrd -storepass storePassWrd -v

Generating 1,024 bit RSA key pair and self-signed certificate (MD5WithRSA)

for: CN=David Burris, OU=Computer Science, O= Sam Houston State University , L= Huntsville , S= Texas , C= USA

[Storing BurrisRSAStore]

Keytool may now be used to query the keystore. The following command is in ListKeyRSAStore.bat for your convenience and lists the contents of the keystore.

C:\> keytool -list -storepass storePassWrd -keystore BurrisRSAStore -v

Starting with JDK1.2, Java has offered a key management system know as KeyStore. KeyStore allows a user to store their own private / public key pairs (non-symmetric) as well as the keys of other with whom the find it desirable to communicate. KeyStore places the public key of the owner in a self-signed certificate by default. This certificate containing the public key may then be exported to other users. If desired, the key may be submitted in the form of a CSR to a CA (Certificate Authority). The certificate is signed by the CA using the CA's private key. This verifies your registered public key to other users. You save this certificate as well as trusted certificate entries in your KeyStore. For a good discussion of KeyStore see Sun's web site. I have found http://java.sun.com/products/jdk1.2/ d ocs/guide/security/CryptoSpec.html to be very helpful. The best explanation in a text I have encountered (though a little dated) is "Java Cryptography" by Jonathan Knudsen, published by O'Reilly, pp. 79 91. Keys are stored in the KeyStore using X.509 by the International Telecommunications Union (ITU, see http://www.ith.ch/) . We will use the default KeyStore implementation from Sun (jks) to demonstrate the ideas. Sun provides its own implementation of a Keystore or you may use the KeyStore of any provider . Your choice of providers is indicated by a line in the security properties file, e.g., keystore.type=jks for Sun.

The jks saves the KeyStore in a file when it is not in main memory. To protect the keys, the jks scrambles the KeyStore passphrase with the private key. This is considered sufficient to foil most amateurs but certainly not a serious cryptanalysis. "jks" saves CSR's in PKCS#10 format, better known as the method used to store Privacy Enhanced Mail ( http://www.rsa.com/rsalabs/pubs/PKCS/ and ftp://ds.internic/rfc/rfc1421.txt) . Sun supplies three software products to manipulate the KeyStore: keytool, jarsigner (command line), and policytool (GUI).

To create a certificate containing our public key:

D:\> keytool certreq alias superkey file superkey.csr keypass keyPassWrd storepass storePassWrd keystore BurrisRSAStore

The file may be sent to a CA or another user via FTP, HTTP, or email. To view the contents of the CSR in base64 PKCS#10 format.

D:\> type superkey.csr

-----BEGIN NEW CERTIFICATE REQUEST-----

MIICkjCCAlACAQAwgYwxDDAKBgNVBAYTA1VTQTEOMAwGA1UECBMFVGV4YXMxEzARBgNVBAcTCkh1

bnRzdmlsbGUxJTAjBgNVBAoTHFNhbSBIb3VzdG9uIFN0YXRlIFVuaXZlcnNpdHkxGTAXBgNVBAsT

EENvbXB1dGVyIFNjaWVuY2UxFTATBgNVBAMTDERhdmlkIEJ1cnJpczCCAbgwggEsBgcqhkjOOAQB

MIIBHwKBgQD9f1OBHXUSKVLfSpwu7OTn9hG3UjzvRADDHj+AtlEmaUVdQCJR+1k9jVj6v8X1ujD2

y5tVbNeBO4AdNG/yZmC3a5lQpaSfn+gEexAiwk+7qdf+t8Yb+DtX58aophUPBPuD9tPFHsMCNVQT

WhaRMvZ1864rYdcq7/IiAxmd0UgBxwIVAJdgUI8VIwvMspK5gqLrhAvwWBz1AoGBAPfhoIXWmz3e

y7yrXDa4V7l5lK+7+jrqgvlXTAs9B4JnUVlXjrrUWU/mcQcQgYC0SRZxI+hMKBYTt88JMozIpuE8

FnqLVHyNKOCjrh4rs6Z1kW6jfwv6ITVi8ftiegEkO8yk8b6oUZCJqIPf4VrlnwaSi2ZegHtVJWQB

TDv+z0kqA4GFAAKBgQCHYX+dJv0GoP7kxCU/e2YgElaJj7iCU3mnN/71gu7DY0E2HmJbmfaChcfy

xC9flVONbTa77A2Kj+3xZXLl1mGzvNhFN3Kme5ZWT06ja0i4HJxckvRtlag9WK7ifJ/42OGQ8/Gx

4f0z/MsP6LNipNjo/tf82sXDN8/UlJzHdo2m0aAAMAsGByqGSM44BAMFAAMvADAsAhRWbdhvuPct

YJF8n7qZzhmdbcNYHwIUGk5RaLxYCgNkdAFpjIDB5Ttbr2c=

-----END NEW CERTIFICATE REQUEST-----

To import a certificate after being returned from the CA on in this case from Luke Skywalker.

D:\> keytool import alias Skywalker file Skywalker.x509 storePassWrd

Do not be mislead by the apparent ease of creating the key store, viewing its contents, creating a digital certificate, and importing digital certificates. While the above is accurate, it takes a great deal of effort and knowledge to create, support, and maintain these abilities in a production system.

Return to Index:

Secure Socket Layer Logic:

Assume SSL Server Keystore contains the servers "secret key" and the "public key." SSL Client Keystore contains the clients "secret" and "public" keys. The typical strategy for e-commerce is for the Server to export a Certificate containing its public key to a Key Authority such as Verisign. Clients import (obtain) the Certificate from the Key Authority and add them to their private key store. Certificates may also be obtained from a "trusted friend" who authenticates (vouches) the certificates validity.

Secure Socket Layers implements public-key technology using the RSA algorithm in conjunction with digital certificates. SSL transactions do not require client authentication. Many if not most vendor servers consider a valid credit-card number to be sufficient for authentication in secure purchases.

To begin, a client sends a message to a server requesting a secure dialog. The server responds by sending its signed digital certificate in a message to the client for authentication. This establishes that the server is whom it claims to be and a secret session key is negotiated using public-key cryptography. The session key is then used for the remainder of the transaction.

The SSL protocol breaks information into blocks, compresses, and encrypts the blocks prior to transmission over TCP/IP. At the other end, the receiver decrypts the packets, then decompresses and assembles the data. While it is possible to authenticate the server, client, or server and client; normally only the server is authenticated in most Internet SSL sessions.

Once data such as credit card information is decrypted and stored on the server, it is at risk. SSL was developed by Netscape. See http://developer.netscape.com/tech/security/ssl/protocol.html and http://www.netscape.com/security/index.html.

More formally:

Assume both the Server and Client have their own "key store." The Client's key store contains a certificate containing the Server's public key. A typical dialog might go as follows:

1) The Client sends the Server a request for a SSL e-commerce transaction encrypted with the Server's public key. Only the server can decrypt this message.

2) The Server responds by returning a message containing his digital signature encrypted with his private key.

3) The Client decrypts this message with the Server's public key to verify they are talking to the Server. Note the server is authenticated but anyone holding the Server's public key can decrypt the message.

4) The Client selects a symmetric encryption algorithm and session key to be used for the rest of the session. The algorithm name and key are encrypted with the Server's public key. Only the Server can decrypt this communication. Only the Server is typically authenticated. The Server typically accepts any transaction with a valid credit card number and other information from the merchant.

5) The rest of the communication is completed using the secret symmetric session key and algorithm for efficiency. The process of authenticating the server's identity, negotiating a symmetric encryption algorithm and symmetric session key is called " hand shaking !"

Return to Index:

The primary means of efficient encryption communications is via "symmetric secret key" transmission. The same key is used for both encryption and decryption, hence the key must be delivered by courier to both parties. The key may be stored and distributed physically in a chip, e.g., ROM, EPROM, Memory Stick. Since each party uses the same key it is not possible to authenticate which party created the message. To keep communications private between multiple parties, each sender / receiver pair require a different key. In a large organization maintaining keys would be a challenging task.

Symmetric Secret Keys Required for "N" Users Allowing Private Conversations with Authentication!

For 4 friends NumKeys = 4*(4 - 1)/2 = 4*3/2 = 6 keys.

For 10 friends NumKeys = 10 *(1 - 1)/2 = 10*9/2 = 45 keys.

For 100 friends NumKeys = 100*99/2 = 4,950 keys.

The number of keys required for private communications grows very rapidly, i.e., on the order of N**2 keys frequently expressed as O(N**2). If private communications among the "N" friends is not required, they can share a single symmetric key.

For public (asymmetric) key communications, each friend in the pair requires their own public/private key pair for authentication. Hence the number of keys is:

NumKeys = 2*N*(N-1)/2 = N*(N-1) keys.

Symmetric Secret Keys Required for "N" Banks with "M" Merchants Allowing Private Conversations with Authentication!

Given M banks and N merchants, M * N symmetric keys are required for private communications. For asymmetric key cryptography, 2 * (M * N) public/private key pairs are required.

Assume M merchants who share N customers. To ensure private communications a total of M*N keys must be retained, a separate key for each merchant / customer relation. The keys must also be distributed securely. An alternative approach to the key-exchange problem is to utilize a central authority for key distribution known as a " Key Distribution Center " or KDC . The key distribution center shares a different secret key with every user of the system. Hence the number of keys is on M+N as each merchant and customer initially only communicates with the KDC. When users wish to communicate with other users, the key distribution center generates a secret session key, encrypts the key with each users shared secret key and delivers the encrypted key to each user. The users decrypt the encrypted secret session key then use the decrypted secret session key to encrypt messages between their self and the other designated user (or group of users) for the duration of the session. This is potentially more secure as each session uses a different key. A key distribution center greatly reduces the number of required secret keys for users to communicate. If the security of the distribution center is compromised, the whole communications network is compromised.

For example, assume the KDC shares a different secret key with each user. Han Solo contacts the KDC with a request to communicate with Luke Skywalker (1). The KDC creates a symmetric secret session key, encrypts it with the secret key shared with Han (2) and transmits the key to Han (3). Next the KDC encrypts the secret session key with the secret key shared with Luke (2), then transmits the message to Luke (3). Luke and Han now have the secret session key and commence the communication. Note that changing session keys enhances the security of the communications. The message from the KDC to Luke and Han will normally specify the algorithm (including padding scheme, etceteras) in addition to the session key.

Symmetric Encryption using a Key Distribution Center:

If the shared secret key is symmetric, then authentication and non-repudiation are impossible. If the shared secret key is asymmetric, then the KDC must encrypt the session key with the users pubic key. This ensures only the desired key recipient can decrypt the message to obtain the session key. Again, the KDC is not authenticated. Additional security would be provided by the KDC first encrypting the key with the user public key then signing the message containing the key by encrypting with the KDC's private asymmetric key. The user would the have to first decrypt the message containing the key with the KDC's public key (authentication) then with the users private key. This amounts to a double encryption. Non-repudiation is questionable.

I

Public Key Considerations:

In 1976, Winfield Diffie and Martin Hellman developed "public key cryptography" at Stanford University to solve the problem of exchanging keys securely over an insecure medium. It uses two inversely related keys: a private key and a public key. Public key cryptography is asymmetric. The owner keeps the private key secret while the public key is made freely available. If the public key is used to encrypt a message, only the private key may decrypt the message and vice versa. Although the two keys are mathematically related, deriving one key from the other is computationally infeasible.

Note if a private key is compromised, it is only necessary to create a new private / public key pair. It is not necessary to modify the entire encryption or decryption algorithm.

Unfortunately, public key encryption is computationally expensive and hard to use for passing large amounts of information. Typically, public key encryption is used by both parties of a communications to agree on a "symmetric key algorithm" and "symmetric secret key" for passing large of amounts of information during a single session. Hence a different secret key is used for each communications session. Consider the following attempt by Luke Skywalker to notify Han Solo of an impending attack by the Empire.

Public-Key Encryption (Luke sends message to Han) :

Because the message is encrypted with Luke's private key, Han knows the message is from Luke. It could not be forged unless Luke's private key has been compromised. The message is authenticated but confidentiality is not assured. Any holder of the public key may obtain the message. We must prevent the Empire from obtaining this information.

Public-Key Encryption (Luke sends message to Han) :

Only Han can decrypt the message so the Empire may not obtain the information. Unfortunately, Han cannot be sure the message is actually from Luke. A third party may pose as Luke and send a false message. Both the Emperor and Darth Vader have been known to set traps using false messages.

Solution ensuring privacy and authentication!

Authentication and privacy may be ensured if the sender first encrypts the message with the receiver's public key. The sender then encrypts the result with their private key.

The receiver first decrypts the message using the sender's public key (to authenticate the sender). Next the receiver decrypts the previously decrypted message with their private key (to insure privacy). This is very expensive computationally but provides privacy, authentication, and non-repudiation. We also insured of the message's integrity.

Public-Key Encryption (Luke sends message to Han) :

Digital Envelopes:

Unfortunately, public key encryption is computationally expensive and hard to use for passing large amounts of information. Typically, public key encryption is used by both parties of a communications to agree on a "symmetric key algorithm" and "symmetric secret key" for passing large of amounts of information during a single session. Hence a different secret key is used for each communications session.

The process by which parties agree on a secret key algorithm, generate the secret key, and communicate the key over an insecure medium is called a key agreement protocol . A popular key agreement protocol is a digital envelope . First the message is encrypted using a symmetric secret key and placed in the envelope. The symmetric encryption algorithm has normally been agreed upon previously. Second the secret key is encrypted using the receiver's public key and placed in the envelope. Upon receipt, the receiver first decrypts the secret symmetric key using their private key. The message is then decrypted using the decrypted secret symmetric key.

Public-Key / Symmetric-Key and Digital Envelope:

Return to Index: