Lecture 1 (Weds 9/17/97)

Scribes: Shawn Butler, Will Uther, Henri Dubois-Ferriere, Yih-Chun Hu

Textbook

• Introduction
• RSA
• Why not use Public Key Cryptography everywhere?
• Rabin Cryptography
• Certificate hierachies
• Alternative certificate Structures
• Key Escrow
• Secret Sharing
• Key Exchange/Selection

Cryptology - Definitions

Cryptography

Making Ciphers

Cryptoanalysis

Breaking Ciphers

Traffic Analysis

Monitoring who sends messages when, even if you don't know what they say.

Plaintext

The text we wish to protect

Ciphertext

The scrambled text we will send over the unsecured line

Encryption Function

ciphertext=E(plaintext, e-key)

Decryption Function

plaintext=D(ciphertext, e-key)

How much is currently secure?

• Land-line phones are easily listened in on
• Analog Cellular Phones are notorious -- How easy is it to break into communications: Former Gov of VA and Newt Gingrich experienced that on their cellular phones
• Internet is usually insecure

Cryptoanalysis Attacks

Enigma machine was used by the Germans during WWII. A major center in England was set up to break German codes.

William Freidman headed the US effort to break the Japanese codes. Because the US successfully broke the code, the Battle of Midway was a success.

It is always assumed that the opponent knows the algorithm being used, i.e. that they know E and D but not the e-key and d-key. There are further assumptions that can be made about what they know:

Ciphertext only

Adversary only has access to the ciphertext - almost never true.

Known plaintext

Adversary has access to both the ciphertext and corresponding plaintext for some messages and just the ciphertext for other messages. This is very common - for example, most cryptographic protocols have standard headers that often get encrypted. e.g. ciphertext is intercepted going into an embassy. 5 minutes later a press statement is released.

Chosen plaintext

Adversary is able to obtain ciphertext for the plaintext of their choice. This is also very common. e.g. "Please sign this for me."

Public Key Cryptography

Private Key

This key is held secure by one of the parties

Public Key

This key is made public

• Sending
  • Encrypt with the receiver's public key.
  • Recipient Decrypts with their private Key.
• Key Management
  • Use public key cryptography to send a fresh, randomly generated, session key to another party.
  • Use the session key with a normal (symmetric) cryptographic system.
  • Symmetric (private) key crypto is about 3 orders of magnitude faster than most public key systems
• Digital Signatures
  • Encrypt either:
    • a checksum, or
    • the entire document,
    with your private key. Anyone can decode, but they know you encrypted it.
  • Only useful if public keys are associated with individuals. This is handled by Certificates.
• Certificates
  • A trusted body signs a small packet containing a name and a public key specifying that only the person named knows the private key that goes with that public key.

RSA

Recall that if p and q are large primes then, by Euler's theorem, if m is relatively prime to p and q then:

m^(p-1)(q-1) = 1 mod pq

so, make:

E(m) = m^e mod pq
D(c) = c^d mod pq

where:

ed = k(p-1)(q-1)+1

so:

(m^e)^d = m^ed = m^{k(p-1)(q-1)+1} = m^k(p-1)(q-1)m = ((m^(p-1)(q-1))^k)m = (1^k)m = m [all mod pq]

If we can factor it is easy to find d given e. Just use extended Euclidean GCD algorithm. (Am + Bm = GCD(m,n)). Therefore, Factoring is harder than or equal to RSA.

Politics

Why aren't we secure yet?

• Know who we're taking to.
• Know that the message wasn't changed or tampered with en route.
• Know that no one (The Bad Guys) is listening in.

• Read our mail/TCP streams.
• Modify our mail/TCP streams.
• Spoof mail/IP addresses, etc.

• Cryptography that is secure.
• Protocols that can use it.
• Standards that use those protocols.

For example, we could:

• All use RSA or similar public key encryption.
• Everyone has a public key/private key pair.
• The public keys are signed by Certifying Authorities (CA's). These digital certificates vouch for the (name,public key) pairing.
• Names would be hierachial with each organisation handling its own CA. e.g. everyone in CS has their public keys signed by CS. All the schools within CMU get their keys signed by CMU, etc.
• Extranets use cross signing of certificates. e.g. CMU and MIT both sign each other's public key.
• Organisations can compete for root of the tree later.
• Once you know someone's public key it's easy to:
  • Authenticate (have them prove that they know the private key) and,
  • establish a session key (so that you can do fast symmetric crypto for the rest of the session).

So, why hasn't this happened?

1. Users
   • Prefer convenience to security (until personally burned)
     • fancy features, including
     • the ability to embed executables almost everywhere (Trojan horses)
   • Are ignorant. They only know how to click OK.
2. Jim Bidzos
   • President of RSA Inc.
   • Vigorously defends RSA patents of both the RSA algorithm and everything else :)
   • "We started out negotiating an RSA license and decided it would be easier to buy the company."
3. Committees
   • Too hard to get documentation
   • Too many pieces that have to be fit together
   • What does get produced is too complex to be easily understood/implemented
   • No rules, no convergence - the drafts keep changing - never finalize
   • Democracy by committee seems to fail in this case.
   • "Mine" vs. "Yours" battles
   • Often no power to make binding decisions
4. Researchers
   • Like working on the complex areas. More complex = more open-ended = more stuff to play with & write papers on.
   • There is little motivation for researchers to actually deploy/produce usable systems
   • Most researches want something that solves ALL problems. Getting something perfect takes forever, but they won't put out the 80% or 90% solution.
   • Think the most elegant solution is the most general and so make things Turing complete - users don't know what the capabilities of various systems are.
   • Tend to explore the rare, interesting cases, leading to bizarre paranoia while the world waits for a "good enough" solution.
5. Root Envy
   • Everyone wants to be the root of the Certificate Authority tree
   • Make everything proprietary - often in hardware
   • Want the world to be forever dependent on them.
   • A monopoly means you can charge money both
     • acquiring a certified key, and
     • verifying a key
   • The root model is not even necessary:
     • Bottom up or Web of Trust model
     • Sign your parent as well as your children
     • Cross-sign between extra-nets
     • Key rollover is easy and it's possible to recover from compromise of Root key.
     • If your organization manages its own CA well, your fate is in your own hands, not some outsider's.
     • The two models are even compatible
   • So, why hasn't this happened?
     • Confusion - only geeks get together for key signing parties
     • Commercial systems all want to be at the root of the tree. Commercial solutions don't support this model.
     • Arm-twisting on patent licensing
     • Installed base.
     • Verisign - limited to Verisign approved applications
     • Post Office had planned to be root for everyone, with three levels of authentication:
       1. basically, no check.
       2. Verify ID
       3. Retinal scan
6. Microsoft
   • There is no market push for security over other features.
   • Microsoft won't 'waste their time' on features that people aren't clamoring for
   • There are three milestones in the history of OS security:
     • Multics
     • Unix
     • DOS
7. Orange Book
   • Actually, Trusted Computer Security Evaluation Criteria
   • It's a Dept. of Defense standard: a checklist of features and grades of security
     • Ratings from D to A1.
   • Elaborate, expensive mechanisms to stop data leaks in a vertical hierarchy
     • even by malicious users
     • ranges from the obvious blocking of messaging and file transfer mechanisms across levels to more advanced clouding issues such as preventing bursts of CPU use being provoked to convey some information in a coded manner.

       For example at one time press reporters hounding the White House could get an indication that something important was going on when the evening pizza deliveries intensified!

   • Much less protection to stop data getting destroyed
   • Designed for a central computer model, everyone on the same machine (mainframe).
   • Some specs are obscure, and useless outside military applications.
     • Stop users communicating by any means - e.g. CPU load or free disk space.
     • Network = Trusted Backbone
   • Customers don't want to understand security. They just want a magic fix. They put full trust in a DoD "stamp of approval" or grading. Companies know this, and spend a lot of time and money fitting their products to the Orange Book specs, instead of going to more efficient solutions. This has a negative impact on a lot of security products development, since it takes large amounts of both money and time to get certified.
   • This still goes on
8. Lawyers
   • Mainly Utah and DC, although other places too
   • Lawyers don't eschew obfusification
   • liability issues make people wary of marketing security solutions
     • digital signatures legally binding in Utah
     • What happens if you lose your public key?
     • More than just money. e.g. child custody
     • better off not having one
   • Want 100% security. Takes a possibly infinite amount of time to achieve
   • Patents and other legal obstacles (see Jim Bidzos) have stopped many algorithms (RSA for one) from being widely implemented.
   • Export Policies
9. France
   • Usage controls on usage of cryptography on French soil. The average Joe (or more likely the average Jean-Pierre) is restricted by French law from just about use of any form of cryptography.
   • Currently you need 3 versions
     • US version (128 bit)
     • US export version (40 bit)
     • French version (no crypto at all)
10. Even if US export controls were to go away you'd still need 2 versions
11. The good ol' US of A
    • Not just NSA
    • Conventional Wisdom: The government is only a hindrance for export of crypto products. Fact: the real issue is control of domestic cryptography.
    • Crypto isn't a US secret, isn't hard to implement, and is relatively easily available from overseas.
    • Rules are unclear
      • Each agency (NSA, FBI, ...) has its own priorities
      • You don't even know if something will be exportable till you build it (and show the government that it can be cracked!!)
    • Rules change
    • No laws restrict cryptography in the US (yet), but the export laws achieve some of the same goals
    • Export Laws
      • It's expensive and difficult to produce two different versions, so sometimes only one less-secure version is produced for sale everywhere.
      • It's difficult to beat the red tape to get something exported.
      • You can't export it if the US govt. can't crack it.

Alternatives to RSA

The Rabin Method

Based on the Chinese Remainder Theorem:

if x = y mod p and x = y mod q then x = y mod pq

A number has two roots: the roots of x² mod p are x and p-x

So, each number has 4 roots mod pq.

# mod 15	# mod 3	# mod 5
1	1	1
4	1	-1
11	-1	1
14	-1	-1

Now, consider adding two of these roots:

+	# mod 15	# mod 3	# mod 5
	1	1	1
	11	-1	1
Total:	12	0	2

Because 11+1 mod 3 is 0, GCD(12, 15) is a factor of 15 (namely, 3). So, if we take two square roots and add them, then the GCD with pq, we are 50% likely to get p or q.

So, if we have all the roots we can factorize, and if we have any root we can factor probabilistically:

• take a random r² mod pq
• compute its square root s
• there will be a 50% chance that GCD (r+s,pq) is p or q

This means that finding the roots must be at least as hard as factorization. Actually we can also go the other way, so the two are equivalent. This is a better guarantee than RSA's.

How do you use it?

• To encrypt, square the message.
• To sign, compute a square root.
• To verify a signature, square it.

Alternative Public Key Encryption Methods

• DSS (DSA El-Gamal) Schneier 19.6, 20.1, 20.2
  • Good for signing documents, but hard to twist into an encryption technique
  • That's just what the US Govt. would like!
  • El-Gamal is patented, so not widely available.
• Elliptic Curve algorithms
  • Traditional encryption techniques all use integers, of which there is only = one set (albeit infinite). There are in contrast many different elliptic curves. Define an arithmetic system based on elliptic curves, with operations similar to integer operations.
  • e.g. plus
    • draw a line between the two points
    • solve for the third point where it intercepts the curve
    • reflect that third point over the X-axis
  • Then many cryptographic techniques transfer directly to this new system.
  • Arithmetic systems defined on elliptic curves seem to be more complex than the integers.
  • It possibly takes fewer bits (smaller keys) for the same amount of power, and that generally means faster computation.
  • The algorithms/ideas aren't patented, but the common computer representations of elliptic curves are.

Key Escrow

• aka "Key recovery plan" if you're in favor of the idea.
• Pushed by the FBI
• Previous plan was the "Clipper Chip" or Fortezza, intended to give the U.S. federal government the ability to decrypt any message it might run upon.
  • Each chip has a serial number and a unit key
  • Each transmission consists of: E(plaintext, users-key) + E(users-key, unit-key) + E(Serial number, Govt. Key) + CryptoChecksum(rest of message).
  • The algorithm is private so only another clipper chip can decode
  • A clipper chip will only decode if the checksum matches, so you can't just leave off the escrow information
  • The government can start with its key to get the serial number, use that to get the unit key, use that to get the message key, and use that to get the plaintext.
  • Unfortunately, the checksum is only 16 bit. This makes it susceptible to brute-force attacks. Matt Blaze demonstrated that it was possible to simply try out all the possible checksums in a reasonable amount of time, making it possible to send a message in which the serial number had been falsified, thus making government decryption impossible.
• Current Proposal: do the same thing, but in software