Various Links CS190 Homepage Cryptography Discussion Topics Cryptography Class Homework Cryptography White Paper by Slackers CS190 Homework Homework #1 Homework #2 Homework #3 Homework #4 Other Groups Homework Push Technology VRML Network Agents Audio Streaming Java Group Cryptography Resources Cryptography FAQs Induhvidual Home Pages Tim Grean Brandon UCSD Computer Related ACM - UCSD UCSD CSE Page This page can be viewed with: And maybe this but no guarantees: Join the DNRC:

Cryptography White Paper ``It must be that as soon as a culture has reached a certain level, probably measured largely by its literacy, cryptography appears spontaneously -- as its parents, language and writing, probably also did. The multiple human needs and desires that demand privacy among two or more people in the midst of social life must inevitably lead to cryptology wherever men thrive and wherever they write. Cultural diffusion seems a less likely explanation for its occurrence in so many areas, many of them distant and isolated.'' [David Kahn's The Code Breakers p. 84] Cryptography is one way to solve the security challenges of all forms of communication on the internet. The basic idea is that, using some secret information it is possible to protect the confidentiality and the integrity of the information being transmitted. This section of the paper aims to introduce the basic elements of cryptography to present a basic understanding of how it is used in providing secure services. Aside from confidentiality purposes such as email, cryptography methods can also be applied to authentication - where the receiver of the message can ascertain the origin of the message, integrity - the receiver can verify if the message was modified during transactino, and non-repudiation - the sender cannot deny that he/she has sent the message. In essence however, the basic scenario that is the premise for the neccesity of cryptography is when an individual, A, wants to send a message to an individual, B, in a form that another person cannot find out the original information from an interception of the transmitted message. In practice, the message that A intends to convey to B is referred to as the "clear text" or the "plain text". An ideal solution to this scenario is that to assure the secrecy of the message, A converts the clear text using a designated cryptographic system into an encrypted message or what is called "cipher text". Then when B receives the message, he decrypts the encrypted message and retrieves the clear text. In this way, even if another person has access to the encrypted message or has somehow intercepted it, he/she cannot read the original clear text without first finding out some piece of pertinent information that A and B somehow keep secret. The security of the message therefore lies in the methods of encryption and decryption. The two main methods of encryption used are substituiton and transposition and mose known modern methods are a mixture of both. Substitution is when individual letters or n-grams of plaintext are replaced by a string of letters or n-grams of ciphertext. An example of a simple substitution cipher is to replace an letter in a string with its following letter in the alphabet (also known as the Caesar substitution). In that case, the string "hello" would be converted into "ifmmp". Transposition is when the characters of the original message are rearranged according to some particular pattern. An example of this type of cipher would be to reverse the order of all the characters in the string to be encrypted. For the same string used in the previous example, the plain text "hello" would be converted into "olleh". Using such basic methods, two families of encryption algorithms have been developed: secret-key encryption algorithms and public key encryption algorithms. Secrety-key encryptionn algorithms are so named as they rely on the fact that only the sender and receiver know the secret key. The key is some piece of vital informatio that is neccesary to encrypt and decrypt the message. The basic methodology of a secret-key encryption algorithm is best demonstrated in an example: create a key (a random string) perform an XOR between the characters in the key and characters of the encrypted message to decode the message, perform an XOR on the encrypted message with the same key original string 101111 key 101010 encrypted string 000101 --- transmission --- encrypted string 000101 key 101010 original string 101111 This algorithm is generally referred to as the XOR algorithm and is of the family of polyalphabetic substitution ciphers. Another algorithm from the same family of ciphers is the Vigenere algorithm which involves a modification of the Caesar substitution. Start by choosing a small fixed number m, and m shifts of the alphabet. Memorize these shifts of the alphabet with the key that corresponds to the associated cypher letters. ie: with m=4 you could choose ... 1 abcdefghijklmnopqrstuvwxyz ghijklmnopqrstuvwxyzabcdef 2 abcdefghijklmnopqrstuvwxyz opqrstuvwxyzabcdefghijklmn 3 abcdefghijklmnopqrstuvwxyz lmnopqrstuvwxyzabcdefghijk 4 abcdefghijklmnopqrstuvwxyz fghijklmnopqrstuvwxyzabcde key = golf The plaintext is then separated into "chunks" of size m, and each m-gram is successively encrypted by replacing its first letter by the corresponding letter of the first cypher alphabet, the replacing its second letter by the corresponding letter of the second cypher alphabet, ..., and its mth letter by the corresponding letter of the mth cypher alphabet. ie: GETM EOUT OFHE REPL EASE NSER KCFY UTSJ XSAQ KOHJ Some examples of comercially used secret-key encryption algorithms are: DES (Digital Encryption Standard) is a block cipher, meaning that it encrypts data in blocsk of of 64 bits and relies on a key of 56 bits. Since some cryptographers consider the key too short in that it allows brute force methods of determining the key as a viable method, TDES (triple DES) was developed which applies the DES algorithm three times with three different keys. DES is commonly used to autheticate users on standard UNIX machines and has also been adopted by the federal standard for encryption of commercial and sensitive yet unclassified government computer data. IDEA (International Data Encryption Algorithm) is also a block cipher algorithm with blocks of 64 bits and keys of 128 bits. RC2 and RC4 are two secret-key encryption algorithms that have been developed at RSA Data Security Inc. and use 40 bit keys. Skipjack is an algorithm developed by the NSA to replace DES in future uses. The algorithm is implemented in hardware only (also called the clipper chip) and contains a key-escrow mechanism that allows governmental agencies the ability to decrypt messages. With the wide use of secret-key alorithms over the Internet, the method of exchanging the secret key in a secure fashion has become increasingly difficult. This problem led to the development of the Diffie-Hellman algorithm. The algorithm is simple and is easily implemented in appropriate situations. 1976 Diffie-Hellman Algorithm Grean and Brandon agree on a large prime number n and another number g. These numbers do not neccesarily have to be secret. Brandon generates a random number x and sends Grean the value : A = gx mod n Grean generates a random number y and sends Brandon the value : B = gy mod n Brandon receives the value B and computes : Kx = Bx mod n Grean receives the value A and computes : Ky = Ay mod n This algorithm ensures the values of Kx and Ky are equal and can be used as the key in a secret-key encryption algorithm. Since it is difficult to determine Kx (which = Ky) given the values of A and B that could be intercepted, the value of the secret key is safe. An altogether alternative to the family of secret-key algorithms are what are called public-key encryption algorithms. In this instance, there is no secret key that needs to be traded initially between sender and receiver. The idea rather is to use 2 different keys for encryption and for decryption respectively: one public key that is known by any other party and one private key that is known only to the individual. In this case, anyone who wants to send a secure message to that individual encrypts it with the publicly available key, and in turn the individual then decrypts the received message with his private key. Although seemingly advantageous in the aspect that no keys need to be exchanged whatsoever, the disadvantage that remains is that the public key system is slower than a private key system. Many times in praactie, a hybrid of both is used where a public-key protocol is used to exchange a secret key and from then on communication is based on a a secret key protocol. One of the most widely used encryption algorithms is RSA. Considered the "de facto" standard in public key encryption algorithms RSA was desgined by Ron Rivest, Adi Shamir, Leonard Adleman. The algorithm is as follows: Grean generates two large numbers p and q and chooses a number e, prime with (p-1)(q-1) (in practice the value of e is 65337). Grean computes the private key (d = e-1 mod ((p-1)(q-1))) and the public key (n = p * q , e) Grean sends the public key to Tim; Tim encrypts the message with Bob's public key: c = me mod n and sends the message to Grean; Grean decrypts the message with the private key: m = cd mod n. For two-way communication, Tim generates his public/private key pair as well. RSA is used in many applications and with the advent of the Web, has gotten much attention as it is used in web browsers like Netscape Navigator for secure transactions. (ie: SSL - secure sockets layer) A situation in which public-key / secret-key schemes have been applied is in the implementation of SSL: Secure Sockets Layer. SSL is an intermediate layer between the application and the transport protocol and its goal is to create a secure and reliable communication channel between a client and a server. The SSL protocol provides connection security with 3 basic properties: the connection is private - encryption is used after an initial public-key method handshake to define the cryptographic protocol then secret-key methods are used for data encryption (ie. DES, RC4 ...), identity can be authenticated using public-key methods. and the connection is reliable - message transmission includes a message integrity check mechanism (ie. SHA, MD5). Basically, SSL is comprised of 2 parts: the SSL Handshake Protocol - used to establish a secure channel, and the SSL Application Data Protocol - used to exchange data over the established channel. The SSL Handshake Protocol was designed for the purpose of creating an initial agreement between a client and a server on which cryptographic protocols, algorithms, methods, and parameters to use. There are three steps or phases to the SSL Handshake Protocol: Client Hello client sends the server a message with names of algorithms to be used, names of names of the compression algorithms used, and a random number. ClientHello( CypherSuite[], CompressionMethod[], ClientRandom) Three encryption protocols are defined in CypherSuite : the key exchange protocol - RSA, Diffie-Hellman the secret key algorithm - NULL, RC4, RC2, DES40, Fortezza the one-hash algorithm - NULL, MD5, SHA Server Hello Upon receiving message from the client, the server matches a cryptographic algorithm specified in the CypherSuite[], matches a compression method specified in CompressionMethod[] and returns to the client the following information: ServerHello( CypherSuite, CompressionMethod, ServerRandom ) From here on, the client and server have agreed upon a set of cryptographic and compression algorithms. If the server has a public-key certificate it sends the certificate to the client the client generates a master secret key and sends it to the server encrypted with the certificate of the server. If not, then a key exchange protocol is initiated (ie. Diffie Hellman). Last step in the handshake protocol is to send to each other a digest of the messages sent so far encrypted with the newly established secret keys. The SSL Application Data Protocol is really the transmission session that was iniitiated with the SSL Handshake Protocol, and encompasses all transmissions between the client and server thereafter. When any communication between the client and server is necessary, the established secret key is used and the integrity of the message is verified with the prefiously specified hash function. SSl is flexible in that it does not specify a cryptographic algorithm but rather defines a framework within which to apply existing algorithms for creating a secure session. SSL allows multiple forms of authentication, both with a certificate, and without. SSL is implemented in most web browsers (currently v3.0) as a method to provide secure transactions as it does not require much user intervention and the level of security provided is high. The next topic of discussion is the implemntation of cryptography in creating digital signatures. Digital signatures are vital in the role of integrity checking and non-repudiation. This is accomplished through the use of public-key algorithms along with the use of one-way hash functions. The hash function is used to create a digest of a message that retains the properties of being relatively short (between 128-256 bits), that given the message it is easy to generate the hash value, that given the hash value it is difficult to reconstruct the message, and that given the hash value, it is difficult to find a message which hashes to the same value. The most often used hash functions include MD5 - Message Digest 5 by Ron Rivest, and SHA - Secure Hash Algorithm developed by NIST and NSA. The process of imlementing digital signatures is relatively straightforward. A digest of the original message is created with the hash function and is encrypted with the private key of the individual. This encrypted digest is called the digital signature of the message. The message and the digital signature are then sent to the receiving party. That party then decrypts the digital signature using the sender's public key and computse the digest with the original message. The computed digest is compared with the received digest, and if they are the same then authentication is accomplished and Brandon is sure that the message was not altered during transmission and that the sender was indeed authenticated. This newly created digital signature can then be used in the implementation of public-key certificates. Digital Certificates, also known as Digital IDs, are the digital equivalent to driver licenses, passports and the like. They are used to proof someone or something's identity, and/or to allow access based upon this identity. A Digital ID is created by binding a particular identity to a pair of public/private keys. Since identification is done by the matching of a particular public key and its corresponding private key, all we have to go by is that the person who generated the private key is actually who they claim to be. Digital IDs prevent us from having to make this assumption, giving us us selective proof that a certain key belongs to a certain individual. Each Digital ID is certified by a Certification Authority (CA), and each CA attaches a certain level of confidence in their authorization. For example, a carrier of Verisign's Class 1, has proof of identity only to the extent that they have a unique email address, whereas a carrier of a Class 3 ID has proof that they were physical present with identification when they received the ID. Each site or person can attach a corresponding amount of trust. Each Digital ID typically contains the following information : Public Key Name Expiration date of the Key Certification Authority that issued the ID Serial number of the ID Digital Signature of the CA To verify the certificate, the digital signature of the CA must be verified, and in order to do so, the CA's public key must either be widely published, or have another Digital ID to vouch for it. Therefore, there may be multiple IDs enclosed within a message, to form a hierarchical chain, where one Digital ID will vouch for the validity of the previous ID. Verisign offers four types of IDs which are used for servers, software publishing, web browsing and email. There are also four classes of IDs, here is a quik breakdown of each : Class 1 requires : name and email address web browsing (name/password) or S/MIME apps $1000 NetSure $10/year Class 2 requires : + driver's license and SSN + online transactions and subscriptions $25,000 NetSure $20/year Class 3 (N/A) requires : physical presence (notary) + e-commerce (e.g. banking) - $100,000 NetSure Class 4 (N/A) assures affiliation with an organization - $100,000 NetSure To obtain a Digital ID, someone must generate their own key pair, and send the public key to an appropriate CA with some proof of identification. The CA then verifies the information, and sends them a Digital ID that attests to the association between said individual and public key. Like any form of identification, especially over the Internet, there is an inherent risk associated, however if used intelligently, the risk and consequences thereof can be minimal. Your Digital ID is stored on your computer, and therefore, if your computer is stolen, and someone gets a hold of your ID, they could effectively impersonate you. CAs maintain a revocation list, which you would report this to, but verification does not require checking this list. However, each ID can be opted to be password protected on your computer, so long as you decide to use this option, you should be safer than without it, and would allow you to notify key parties as to your loss. There is also risk involved with the CA that you received the ID from. The two scenarios that could affect a CA would be loss or a compromise of their private key. If it is lost, any IDs they had issued are still valid, as long as people understand to use their old public key when verifying your certificate. You can then receive a newer ID at your convenience. However, if a CA's key is compromised, false IDs can be issued, and in this case, you should be wary when receiving IDs from the CA. The CA is responsible for notifying all relevant parties not to validate based on their old key, and then regenerate a new database of certificates. In neither case is information encrypted with your key ever at risk. CyberCash represents another application of encryption methods to the web. They are focused on providing secure financial transactions over the Internet, using credit cards, electronic checks and micro transactions. As of this paper they are connected to 80% of the banks in the US, and have over 400,000 wallets in distribution. Here is a breakdown of how CyberCash involves itself in financial transactions. When a shopper finds an item of desire on a site, the server sends relevant information (item, price, transaction ID, etc.) to the consumer. The consumer activates the CyberCash wallet, selects the method of payment and sends off the encrypted information packet. The merchant receives the packet, strips off the order information, and forwards the encrypted information signed and encrypted with its private key to the CyberCash server. The CyberCash server receives the packet, takes the transaction behind its firewall, repackages the data and forwards it to the merchant's bank overdedicated lines. The bank checks the credit card or funds, and sends a reply to CyberCash, who forwards the reply to the merchant. This whole process takes about 15-20 seconds. Cryptography outside the Web mainly consists of the ubiquitious use of PGP (Pretty Good Privacy). Pretty Good Privacy is a computer program that encrypts and decrypts data using the RSA algorithm. It was written by Phil Zimmerman and released as freeware mainly as a reaction to federal government forays into the World Wide Web. Due to the fact that it was freeware it allowed itself to quickly gain market dominance. The source is freely available and you can compile it for yourself. Currently Phil Zimmerman works at PGP Inc, a company that he founded and they are in the process of developing PGP 5.0 (a commercial product, not free). Classical cryptanalysis involves an interesting combination of analytical reasoning, application of mathematical tools, pattern finding, patience, determination, and luck. It is clear that proficiency in cryptanalysis is, for the most part, gained through the attempted solution of given systems. Such experience is considered so valuable that some of the cryptanalyses performed during WWII by the Allies are still classified. The basic types of cryptanalytic attacks in order of difficulty for the attacker, hardest first, are: cyphertext only the attacker has only the encoded message from which to determine the plaintext, with no knowledge whatsoever of the latter. A cyphertext only attack is usually presumed to be possible, and a code's resistance to it is considered the basis of its cryptographic security. Known plaintext: the attacker has the plaintext and corresponding cyphertext of an arbitrary message not of his choosing. The particular message of the sender's is said to be `compromised'. In some systems, one known cyphertext-plaintext pair will compromise the overall system, both prior and subsequent transmissions, and resistance to this is characteristic of a secure code. chosen plaintext: the attacker has the capability to find the cyphertext corresponding to an arbitrary plaintext message of his choosing. chosen cyphertext: the attacker can choose arbitrary cyphertext and find the corresponding decrypted plaintext. This attack can show in public key systems, where it may reveal the private key. adaptive chosen plaintext: the attacker can determine the cyphertext of chosen plaintexts in an interactive or iterative process based on previous results. This is the general name for a method of attacking product ciphers called `differential cryptanalysis'. Cryptography is rapidly becoming a more important topic. The Federal Trade Commission (among with other Federal Government agencies) is discussing privacy rights and other issues important to how commerce will use the Internet. As more trade is done over the Internet cryptography will continue to become a central issue. A closing quote: "The popular conception of, and reaction toward, the subject of cryptography in Poe's time - and to a certain extent today - are the remnants of a medieval point of view, which regarded it in somewhat the following light: A cryptogram is a piece of writing to which a meaning exists but is not immediately perceptible; its intelligibility is concealed, hence mysterious or occult, and thus supernatural. Therefore anyone practicing the art is of necessity the associate of forces governing supernatural phenomena. The mental portrait the average layman has even today of the professional cryptographer is that of a long haired, thick bespectacled recluse; a cross between a venerable savant and a necromancer who must therefore commune daily with dark spirits in order to accomplish his feats of mental jiu-jitsu." 1936 William Friedman Office of the Chief Signal Officer War dept. Washington D.C. Copyright 1997 by Slackers Union. Comments should go to any of the group members. Opinions reflected on this page are by no means opinions of UCSD. Go sue somebody else. Last Modified: May 20th, 1997