Security
Topics > Cryptography

IT Security
Overview


Firewalls

Intrusion
Detection


Security
Policies

Vulnerability
Assessments

Cryptography

Portal
Review

Scanners

Against
Security?

 

"Privacy is necessary for an open society in the electronic age. Privacy is not secrecy. A private matter is something one doesn't want the whole world to know, but a secret matter is something one doesn't want anybody to know. Privacy is the power to selectively reveal oneself to the world."
from A Cyberpunk's Manifesto
by Eric Hughes.

Contents

Introduction

Writing about cryptography from a neophyte's standpoint seems to be a foolhardy (and facetious) endeavor to say the least, given the ready availability of excellent resources both online and in print. Nevertheless, I am prepared to hurl myself into unknown territory armed only with a passionate interest in the subject and a healthy curiosity. My efforts, I hope, would be of some benefit to others who are likewise new to cryptography. A complete (and unabridged) history of cryptography is beyond the scope of this particular paper, but I point you to the very readable book 'Crypto' by Steven Levy, a straightforward account of the history of cryptography and the major players in the field. However, no understanding of cryptography and its importance in today's information society is complete without at least a cursory knowledge of how it came about and why it is what it is today. While I have included a short historical introduction to cryptography, the purpose of this paper is to answer some pertinent questions about how modern-day cryptography works and special emphasis will be placed on public key cryptography.

Briefly now, some interesting footnotes in the history of Cryptography. Cryptography is the science of encrypting and decrypting information. The goal of cryptography is to make it virtually impossible to decrypt an encrypted text (ciphertext) into plaintext without the use of a corresponding secret key. The first documented example of written cryptography dates to as far back as 1900 B.C. when an Egyptian scribe first used non-standard hieroglyphics of the day to communicate. The history of cryptography is littered with many notable personages, from Julius Ceasar (100-44 B.C.) who used a simple substitution cipher with the normal alphabet in government communications to Arnaldus de Bruxella (1473-1490), who used five lines of cipher to conceal the crucial part of the operation of making a philosopher's stone and to Thomas Jefferson in the 1790s, possibly aided by Dr. Robert Patterson (a mathematician at U. Penn.), who invented his wheel cipher which would be redeveloped as the Strip Cipher, M-138-A, used by the US Navy during World War II.

The biggest wave of change yet seen in the field of cryptography owes its beginnings to the scientific mobilization of World War II. A leading figure in cryptographic discourse, William Frederick Friedman, founder of Riverbank Laboratories; cryptanalyst for the US government, and lead code breaker of Japan's World War II Purple Machine (invented in response to techniques discovered by Herbert O. Yardley), is "honored as the father of U.S. cryptanalysis". In another significant development during the war, the Germans' cryptographic workhorse, the Enigma machine developed by Arthur Scherbius was broken by the Polish mathematician Marian Rejewski, based on captured ciphertext and one list of three months worth of daily keys obtained through a spy. Major code breaking developments during the war was continued by Alan Turing, Gordon Welchman and others at Bletchley Park in England.

After the war, the locus of cryptographic activity centered in the National Security Agency (NSA), a branch of the Department of Defense located at Fort Meade, Maryland. Created in 1952 at the behest of President Harry Truman, the NSA took on the role of a centralized intelligence agency whose twin purposes were to protect U.S. military and executive communications from hostile interception and intercepting and decoding communications belonging to other governments.

Meanwhile, the revolution in computers and electronic communications drove the need for civilian research in cryptography, as companies and individuals began to sense the same need for encryption and privacy protection that the government had long recognized. In the 1970s, Dr. Horst Feistel led a cryptography research group at IBM's Watson Research Laboratory and developed the Lucifer cipher, the precursor to today's U.S. Data Encryption Standard (DES) and other product ciphers, known collectively as the 'Feistel ciphers'.

top

Data Encryption Standard (DES)

DES is perhaps the most well-known and widely used cryptosystem in the world. It is a symmetric block algorithm written by IBM that encodes 64-bit blocks of data using a 56-bit key. DES was based on the Lucifer cipher and after some particularly controversial changes to the algorithm mandated by NSA (including the changing the contents of some of the algorithm's eight substitution boxes (s-boxes) and the reduction of key size from 128 bits to 56 bits) was chosen to be the U.S. Data Encryption Standard. The NSA's involvement generated widespread doubts about the algorithm's strength and integrity, as the drastic reduction of key size as well as the classification of how the s-boxes were used by the algorithm fed fears that the government was deliberately endorsing a weakened form of encryption that was strong enough for public use but weak enough for the government to decrypt using classified knowledge. Despite these debates and controversies, DES has since found worldwide acceptance even though the algorithm has been cracked (and by machines that cost much less than the information it routinely encrypts). Attempts at extending the life of DES have included the use of longer keys, larger block sizes, and more encryption rounds. Variations such as 3-key triple-DES are now commonly used, meaning that the plaintext is in effect encrypted three times.

top

Private Key Cryptography

Before the concept of public key cryptography took root, private key cryptography was the main conduit through which encrypted conversations could take place. Both sender and receiver share the same key which must be kept private. The difficulty lies in the fact that if communication is to occur, A has to tell B what secret key they are to use without compromising the key's privacy. For this to happen, A has to get the key to B through a secure channel, though if a secure channel already exists, it would be rather redundant to use encryption. Private key cryptography is also known as symmetric cryptography because the same key is used on both sides of the communication channel. Therefore, if A encrypts a piece of text into ciphertext with the key 'nibelung' to send to B, B needs to use the same key 'nibelung' to decrypt it into plaintext.

The main problem with private key cryptography was one of key distribution. In order for secure communications to take place, one has to share a unique private key with every individual with whom one has contact with. So if Jack has 15 friends that he regularly exchanges encrypted messages with, he will have to have 15 different keys with which to encrypt messages to each of his 15 friends. Needless to say, the potential costs and logistical difficulties with supporting such large distribution of keys can be frighteningly prohibitive. Another problem associated with private key cryptography is that you can't send someone a private key for communication purposes without already having a secure channel of communication for sending that key.

The key distribution center (KDC) is one way of getting around this logical bind. The KDC acts as a middleman between two people who need to communicate through a secure channel. Suppose that Tom needs to talk to Jerry, he simply contacts the KDC requesting a session key. The KDC then sends out encrypted session keys to both Tom and Jerry, each encrypted with their own secret keys that are kept on file at the KDC. After decrypting these session keys with their secret keys, Tom can now have a secure conversation with Jerry. On the other hand, a centralized key distribution system is itself no guarantee of security; there is probably no way to ensure that the private keys kept on file at a KDC have not been compromised or tampered with.

top

Public Key Cryptography

The birth of public key cryptography in the 1970s was in part due to the combined efforts of Whitfield Diffie and Martin Hellman. The premise of their collaborative effort, "Multi-User Cryptographic Techniques" was that it should be possible to create a multi-user cryptography system in which a message could be encrypted with one key and decrypted with another. The idea of multi-user cryptography was a watershed moment in the field - the problem however, was one of implementation. Without going into the complexities of the math behind the theory, this was the solution Diffie and Hellman eventually put forth in their definitive paper, "New Directions in Cryptography".

To put it simply, assume that Andy wants to exchange an encryption key with Susan in an insecure environment. Andy and Susan would then each need to start with a secret key, and by exchanging information based on those keys, derive a session key that they can then use to encrypt future communications. (Below is an explanation derived from Garfinkel (72) which I've used to explain the concept to myself.)

  • Both Susan and Andy agree on two numbers that are known to the both of them. The numbers need not be private, and can in fact be widely known. Susan picks a number x. Andy picks the number y.
  • In addition to picking a publicly known number, each then chooses a secret number. Susan picks the secret number a. Andy picks the secret number b.
  • Susan then uses a mathematical formula that involves {x, y and a} to compute the result S, which she sends to Andy. Andy does the same, using the same formula that involves {y, x and b} to compute the result A which he then sends to Susan.
  • Susan now has Andy's computed result A, and Andy has Susan's computed result S.
  • Both Susan and Andy can now compute a third number (or session key) called K, by using a second mathematical formula discovered by Diffie and Hellman. This third number may be derived as a function of either {a and A} or {b and S}, but not from the numbers A and S.
  • In other words, once Susan has Andy's computed result A, she is then able to compute the session key K with her secret number for future encryption purposes. Andy is likewise able to derive the session key K from his own secret number and Susan's computed result.
  • However, Evil Bob who might be listening in on their exchange will not be able to calculate the session key K using the numbers A and S which were sent in plain sight, provided that he has no knowledge of either Susan's or Andy's secret keys.

The Diffie-Hellman algorithm however requires two active participants working together at the same time in order for it to be used as a workable encryption system, but the idea of multi-user cryptography took root and gave fruition to the birth of RSA, an algorithm while based on the original Diffie-Hellman concept, took it several steps further in enabling encryption and decryption in the absence of active participation on the part of users, thus creating the first real prototype public-key system that was both effective and practical to implement.

top

RSA

RSA was developed by Ronald L. Rivest, Adi Shamir and Leonard M. Adleman, who were collectively inspired by the Diffie-Hellman multi-user cryptography concept. It was a practical public-key cipher based on the difficulty of factoring very large numbers. The idea is that it is easy to find two large primes but it is difficult to factor the product of the two primes. Deducing an RSA key will theoretically require an extraordinary amount of computer processing power and time.

So how does RSA actually work? The mathematics behind this asymmetric algorithm is far beyond the scope of this paper (and the abilities of this writer), but essentially, if Calvin wants to use RSA, he must first create a key pair consisting of a secret key and public key. Calvin then picks two very large prime numbers, say p and q and calculates the value of the encryption modulus N by multiplying p and q. Calvin now has to pick an encryption key number E that shares no common factors with the number (p-1)(q-1). Now all that Calvin has to do is compute his decryption key D, which he does, using the Euclid algorithm and the prime numbers that are known only to him.

So now Calvin has:

  • N: the encryption modulus
  • E: the encryption key (public)
  • D: the decryption key (private)

The formula for D is as follows:

D = E-1 (p-1)(q-1)

In sum, Calvin's public key is the pair {N, E} and his private key is {N, D}. Remember that the two prime numbers that Calvin picked at the very beginning should be kept private or destroyed.

So if say, Hobbes wanted to send an encrypted number X to Calvin, he simply goes to the public key registry and looks up Calvin's public key numbers {N, E}. With these in hand, he takes X and raises it to the Eth power and multiplies it by Calvin's encryption modulus N: hence:

XEN = Encrypted Number

When Calvin receives the encrypted number from Hobbes, he performs the same operation but uses his private decryption key D. Hence,

(Encrypted Number)DN = Decrypted Number X.

While RSA represented an important breakthrough for public key cryptography, the algorithm itself was a serious problem in terms of the computational power needed to work with such large prime numbers. For all intents and purposes, the commercial debut of public key cryptography was stymied by the computational demands of the RSA algorithm and the fact that the technology was simply a few rungs too high on the evolutionary ladder.

top

Pretty Good Privacy

The next important figure to arrive on the scene was Phil Zimmerman, the founder of Pretty Good Privacy or PGP. Zimmermann released his first version of PGP (Pretty Good Privacy) in response to the threat by the FBI to demand access to the cleartext of the communications of citizens. PGP offered high security to the general public and as such could have been seen as a competitor to commercial products like Mailsafe from RSADSI, a company founded on the backbone of the RSA algorithm. However, PGP is especially notable because its worldwide acceptance as the encryption standard was in no small part due to the fact that it was released as freeware. The legal controversies surrounding the use of PGP centered around the fact that the product included patented technology (the RSA and Merkle-Hellman public key patents) that it did not have the rights to. There's a nice section in Garfinkel where he talks about the licensing difficulties of PGP's early start, the maturing of the product into an extremely secure encryption tool from its humble beginnings as the product of a cryptographic amateur, and of the inter-relational difficulties between RSADSI's Jim Bidzos (self-styled protector of RSA's patents and rights) and Zimmerman (the opportunistic visionary who skirted the thin edges of patent law in the development of PGP on the back of the RSA algorithm).

top

Bibliography

1. Cryptography FAQ (http://www.faqs.org/faqs/cryptography-faq/)

2. Cryptography lectures online. http://www.cs.cmu.edu/afs/cs/academic/class/15827-f98/www/lectures.html

3. Cryptography: The Study of Encryption (http://world.std.com/~franl/crypto.html)

4. Ellison, K. (1996). CME's Cryptography Timeline. Retrieved April 25, 2001, from the World Wide Web: http://world.std.com/~cme/html/timeline.html

5. Garfinkel, S. (1995). PGP: Pretty Good Privacy. Sebastopol, CA: O'Reilly & Associates, Inc.

6. Hebert, S.J. (2001). A Brief History of Cryptography. Retrieved April 25, 2001, from the World Wide Web: http://cybercrimes.net/Cryptography/Articles/Hebert.html

7. Hughes, E. (1993). A Cyberpunk's Manifesto (http://www.eff.org/pub/Privacy/Crypto_misc/cypherpunk.manifesto)

8. Kahn, D. (c.1996). The Codebreakers: the story of secret writing. New York: Scribner.

9. Schneier, B. (2000). Why Digital Signatures are not Signatures. Crypto-Gram. Retrieved April 25, 2001, from the World Wide Web: http://www.counterpane.com/crypto-gram-0011.html#1

10. Simpson, S. (1997). Cryptography Defined/Brief History. Retrieved April 25, 2001, from the World Wide Web: http://www.eco.utexas.edu/faculty/Norman/BUS.FOR/course.mat/SSim/history.html

top