Cryptography basic idea of crypto is to hide information from prying eyes. Traditionally this has been done with a symmetric cipher, aka conventional encryption. Symmetric because the key is the same on both sides. The communicating parties (Alice and Bob) agree on a secret key "out of band". This communication can be intercepted. If you try to encrypt that, you need to agree on a key out of band for this and so on ad infinitum. Cryptography is only as strong as the weakest link in the chain of communication. e.g. Telnet sends the password in the clear. Using Telnet ROT-13 is as useless because it requires no effort to reverse the encoding. Crypto is about making the cost of retrieving a message much higher than the value of the message itself. ie: a digicash packet with a value of $15 does not warrant using a million dollars to crack. ---- Substitution ciphers Rot13 original alphabet ABCDEF... new alphabet MNOPQR... XORs message 01011 key 101 10110 result 11101 cipher 11101 key 101 10110 message 01011 XORs are another form of replacement ciphers. Basically there are several substitutions goingon simultaneously. The problem is that regularities in the data show up quickly, and it is utterly vulnerable to the known plaintext attack. Knowing a plaintext reveals the key. Nulls are also a problem - uncompressed data contains null sequences which reveal the key.... So the answer is to make a one time pad, where each key is unique, secret and as long as the message. This is the only cryptosystem that cannot be broken since *ANY* substitution could be occuring. The message could encode anything since the key is as long as the message there are no regularities to exploit. Modern computers have made this easier. Long strings are no problem. Problem: how to distribute keys. How to generate keys. Knowing the source of randomness opens key breaking to statistical attack. ie: knowing which keys are more likely to occur. Block ciphers DES and IDEA are block ciphers, so called because they operate on fixed sized blocks of data. They depend on the complexity of the output (ie: inputs have no obvious correlation with outputs) rather than the secrecy of the algorithm. DES is now getting on a bit, and the cost of breaking it is seen to be low. Interesting story: the experts who designed DES had proposed a 128 bit key, as IDEA (a swiss algorithm) has. The DoD thanked the experts and published the DES standard with a 56 bit key length. There has never been a clear explanation of why this happened. This also gives you a hint about the paranoia around Clipper. A new variant is to run three DES encodings in series (3DES), giving an effective key length over 128 bits. Key management is a nightmare for these systems. Agreeing on keys to exchange keys later. Tracking what keys are valid and who can use them, etc. ---- Public key ciphers aka Asymmetric keys Whitfield Diffie and Prof Hellman here at Stanford came up with the idea of having different keys of encrypting and decoding. Asymmetric since the key used to encode a message is different from the message used to decode it. The math is hairy but the basic idea is: Take two very large primes, multiply them. Do this for another pair of primes and then combine the primes using some funky math and throw half the primes away and you get two keys. RSA system (Rivest, Shamir, Adelmann) A key comes in two parts. Something encrypted with one key can only be decrypted with the other and vice versa. A key cannot decrypt messages using itself. Alice generates a key pair. One half she keeps to herself, the other she publishes far and wide. Bob encodes a message to Alice using Alice's public key. This too can be posted far and wide. Only alice's key will decode the messge. Suddenly the problem of agreeing on keys out of band is no longer a big problem. Key management in the usual sense is no longer a problem. The problem now is that everyone you talk to has a key, and you need to keep those in order. And whose key do you trust? When agreeing on secret key there is high confidence that there is no one listening in because you are using a secure channel. When exchanging public keys using a public channel, anyone can listen in, and anyone could make a substitution invisibly. If you had a secure channel to exchange public keys, you would not need public key crypto... So you can't trust a public key... We look more at this later. ---- The problem is that working with 100 digit numbers takes time. Another is that the key must be as long as the message or the key is open to attack through analysis. Session Keys Generate a 128 bit random number and use that as the key for DES or IDEA block cipher. Use the block cipher to encrypt the message itself. Then encrypt the random number (session key) using public key crypto. Stick encrypted session key on front of message and send. This detail is usually ignored and we talk about using keys to encrypt messages we are really talking about session keys. ---- Uses of Public Keys: Signatures If Alice sends a message to Bob encrypted with Bob's public key, then Bob knows the message was intended for him and not someone else. How does he know Alice sent it? Alice signs messages by encrypting the message with her secret key. Bob decrypts the message using Alice's public key, which proves that Alice sent it, since only Alice has access to Alice's secret key (hopefully - remember the weakest link) Now: Who do you trust? If Alice meets Bob, then Alice can sign Bob's public key using her secret key, generating a signature certificate that can be attached to Bob's public key. The certificate says: Alice guarantees that Bob's key really is Bob. Next time someone looks a Bob's key in the public directory they will notice that Alice has issued a certificate for it. There are different models of how trust is distributed. Note there is a big difference between signing a key and signing a msg If Alice wants to post a message it is not practical to sign the whole message (equivalent to a long number) Instead Alice computes a hash function (message digest) of the message and encrypts the hash value using her secret key. To check the message signature the reader recomputes the digest of the message and compares it to the decrypted value sent along with the message. Any difference between the two indicates tampering. Allows people without public key software to read message as well. ---- PEM - Privacy Enhanced E-mail RFC 1421-1424 Adds new headers to mail, and stores key and signature info there. To send a PEM message: Generate a session key and encrypt message with it. (IDEA/DES) Encrypt session key with secret key giving Data Encryption Key: DEK Stick DEK in header in ASCIIfied format. Plonk public key and Distinguished Name (DN) associated with key into header. If signing a message, generate a message digest/hash value and encrypt that with session key. Call this Message Integrity Code (MIC) Hierarchy of trust. Internet Policy Registration Authority is God. IPRA certifies (signs) Policy Certificate Authorities PCAs signs CAs (Certification Authorities) CAs sign user keys and other CAs. IPRA public key has to be distributed out of band. This is a problem. A key is distributed with its Certificates, so that the validity of the key can be recursively checked. Certificates can be like badges of authority/authenticity: Yes, he does work for us. Having a small number of PCAs and well defined CAs makes it easy to distribute revoked key certificates. Basically, if a key is old or stolen then the user should issue a revokation. Don't use this key! Having the CAs trusted means they can sign revocation so you know it is true. This is good. --- secure HTTP - coming soon In WWW there is an asymmetry between readers and servers. Few servers - lots of readers/users. Servers have keys, readers don't. EIT are using RSA/DSIs PKCS-7 package, which is a standard implementation/library of public key functions. It allows different systems to be plugged in as well. It is freely available in the US as part of the PEM agreement. Available in export form with 40 bit keys. Just as client can specify what mime types it accepts, Server can specify what encryption systems it accepts. Client receives a form. Form contains Distinguished Name, key associated with name and certificates of key (like PEM). Also has list of cryptosystems server understands (PKCS7, PGP etc) Client takes sensitive data and encrypts with session key. Encrypts session key with server's key. Sends encrypted packet to server. Entire packet is encrypted. Observer cannot even tell what action is being requested. Server decrypts request and does something. Note it does not need client to have a public key of its own. Server encrypts results using session key and sends result back to client. Return code is also encrypted, so observer cannot tell if request succeeded. This prevents some traffic analysis. ie: looking at communication patterns. Client decrypts result with the session key it used for the initial encryption and shows the result to the user. Public key encryption takes time - it's a big performance hit for the server, so you want to do little of it. Use sparingly Current encryption is either a PGP/PEM hack or BASIC, which is uuencoding, which is a substitution cipher -not secure at all. PGP involves fingering server for a key - ugh! ---- PGP : Pretty Good Privacy PEM is intended to interoperate with various systems. PGP operates only with itself. There is talk of fixing this soon. PEM has to in order to survive. Getting a CA certified key is too much hassle. Not an RFC, just a de facto standard. There are 5000+ PGP signatures on the keyservers, while PEM has barely 1000. With a US legal PGP just announced there should be even more in the next few weeks. PGP uses a web of trust model, with no ultimate issuing authority. It is guerilla crypto for the masses. As Dorothy Denning has said: "PGP may become a problem." PGP works on the idea that you choose who you trust. If you receive a public key from Bob, then you may choose to sign it if you verify say the checksum of the key with Bob. Signing a key is akin to saying: I guarantee that this is Bob. In the PEM model, all trust is absolute. Any CA signature is as good as any other. PGP is for people who prefer to pack their own parachutes. In PGP, you assign levels of trust of the people whose keys you receive. So if I trust Bob totall, I will trust keys signed by Bob as if I signed them myself. Alice I don't trust very much - so a key signed by Alice must also be signed by someone else I trust about as much, Charlie for example. ie: Alice or Charlies signatures individually are not trusted, but together I guess they must be right. This web of interconnections makes it harder to find out if a key is trustworthy since there is no simple tree. You need an introducer that you trust between you and an unknown key. Eventually keys will be distributed with lots of signatures so that there will be automatically a bridge of trust between you and Alice. PGP uses RSAs public key algorithm - which is patented. This has caused some problems. More later. PGP uses IDEA with 128 bit session keys under a patent license, which is under some dispute regarding commercial use. PGP compresses text before encryption - this is good. It reduces redundancy which is a prime source of key attacks. Revoking a key in PGP is a bit of a hit and miss affair. Since there is no ultimately trusted issuer, people may not receive the revocation certificate. PGP is also open to key spoofing. In the PEM hierarchy, a CA must make sure that the Distinguished Name is unique. In PGP anyone can issue a key with any name. Alice has a key posted to the key server bulletinboard. Bob generates a key with Alice's name and sends it off to the key server where it replaces the existing key. Alice discovers that she can no longer read messages sent to her and that her signatures are no longer accepted. She fixes this by resending her key but it is as easy for Bob to override the key as before. This is why the trust web is so important. Alice's key will be signed by lots of friends, while Bob's bogus key will not be signed by anyone except creatures of Bob's imagination. PEM is much more trustworthy from this viewpoint, but it is a big hassle to deal with. It will come to pass - simply due to need for commercial grade trust. ---- Clipper - The Empire Strikes Back Clipper is a public key system that uses a secret algorithm (SKIPJACK) for the actual encryption. SKIPJACK is similar to DES, but uses 80 bit key. Each chip has a unique id, and a unique key associated with the id. Clipper chips also have a family key that they all share. session key --unit key--> intermediate result intermediate result + serial number + authentication pattern --> 128 bit 128 bit result --family key--> Law Enforcement Access Field 128 bits Transmit LEAF to reciever Clipper. Recipient decrypts LEAF using Family key (80 bits) getting intermediate result and serial number Serial number --> session key Clipper comes with something called Key Escrow. Any clipper chip will have copies of the unit key, unit serial number pair split up using an XOR and the two key fragments sent to escrow agencies. Police will use a family key box to decode the LEAF and obtain the serial number of the communicating clipper chip. On presentation of a legal instrument (presumably a wiretap warrant, but the text is vague) the escrow agencies will present their fragments of the unit key associated with the serial number to the law officers. The officers can the surreptitiously decrypt any communications using the unit key to get the session key. At this point, if the intercept turns out to be unwarranted, then you need to buy a new clpper chip, since the one you have has been compromised. CAPSTONE is the computer version of CLIPPER - it has more functions but is basically CLIPPER. TESSERAE is the environment that CAPSTONE lives in. Some criticism of Clipper. Whit Diffie before Senate Judiciary Committee: Family key is only 80 bits long - this is the weak shared link. We just saw a 387 bit key fall after 6 months of work by the net. The LEAF even includes a nice pattern to tell you when you decrypt a key correctly - I wonder why that's there.... The family key only has to be broken once for all Clipper chips. The unit key can be found by trying all possible 80 bit keys on the encrypted session key. Use each resulting decrypted session key on the message. Once the message has been decrypted, the key used to decrypt the session key is the unit key. The clipper chip under attack is now worthless. Escrow agencies are not responsible for anything in their posessions. There is a strong move to have an independent (non-govt) escrow. Any data intercepted is admissible in court, even if the tap was not authorise. ---- Legal stuff ITAR Strong crypto is a weapon of war, and is therefore controlled by ITAR International Traffic in Arms Regulations. (340 K of text, brief guide is only 34 K) Export is controlled by Commerce, but State Dept controls ITAR. Anything above 40 bits is controlled. This is a joke, since PGP is widely available with 1024 bit keys on FTP servers from here to Murmansk. There are bills in House and Senate to stop this nonsense. Interestingly - freedom of press allows the export of public key or DES listings, as they are freely available in library books on crypto. The same listing on a disk can get you jail and a fine. PGP made it to the internet somehow and it spread out of the country. This violated ITAR and Phil Zimmerman is now under a Grand Jury investigation to determine whether he violated ITAR by placing it on the net, which he claims he did not. Patents Patents on idea of public key tech. Strange attitude. Too broad. Never been tested in court. Stanford and MIT set up Public Key Partners (PKP) to license patents. No one seems to work there. RSA licensed technology from PKP and develop apps and librarys for further licensing. Govt and govt contractors do not need a license since govt funded research. PGP violates patents since it has not been licensed. Zimmermann tried to get a license but could not since he was giving it away. ViaCrypt in Texas have a license from RSA/PKP and developed PGP that used the licensed libraries. RSA did not like this but had to live with it. It costs a $100 in executable only form. MIT has just released a PGP with RSAREF a freely available in the US crypto library for non-commercial use. PGP has become legal to use in the US. It has always been patent legal in the rest of the world, as no-one else recognizes the PKP patents. ITAR is still a problem. PGP can be exported but the crypto engine (RSAREF) cannot.