rough outline of CS007 security issues and tools

Two approaches to security:

• information-theoretic (perfect secrecy/perfect security)
• computation-theoretic

Information-theoretic security: no matter how much computation a party (e.g. eavesdropper) does, she can't learn about the secret--she doesn't have enough information to even narrow down the possibilities.

Not even brute-force attack helps.

Examples

• one-time pad/Vernam cypher
• secret-sharing
• (Can also be used in authentication)

Corresponding to each new piece of concealed information is new key. For example, Vernam cypher:
cleartext is string of a thousand bits: 010001100001010...
key is string of a thousand random bits: 010101000010000001011111...
---------------------------
cyphertext: each bit is mod 2 sum of corresponding bit of clear and corresponding bit of key.

Can Eve learn anything about the cleartext from the cyphertext?

She knows without looking that the cyphertext is a bunch of random bits--probability distribution doesn't depend on the cleartext--therefore she can learn nothing.

Secret-sharing Say it's known that secret s is between 0 and m-1 (where m is a known modulus). To share secret s among two people, choose random x uniformly between 0 and m-1, let y be a number between 0 and m-1 such that

Two pieces: x and y
Learning single piece yields no information about s.

Disadvantage of perfect secrecy in cryptography:

• The key must be as long as the cleartext.
  • use of one-time pad consumes huge amounts of key
  • sender and recipient must have agreed on key in advance

Use of cryptographic schemes that are not secure in an information-theoretic sense.

• key is of fixed size (e.g. 128 bits), regardless of length of cyphertext.
• scheme often used as a block cypher - each block of, say, 64 bits is encrypted separately with same key.
• Brute-force attack would work in principle:
  • Say cyphertext is much longer than key (e.g. 1000 bits long), so number of possible decryptions (= number of possible keys) is much smaller than total number of possible cleartexts.
  • If Eve knows something about format or content of cleartext, then she might be able to further reduce possible cleartexts.
    
  • Once Eve learns key, she can decrypt future messages (unlike one-time pad, where learning about the key doesn't help for subsequent blocks)
• Security achieved by
  • making key big enough that brute-force attack would take thousands of years even on fastest computer
  • designing cryptosystem so that no apparent short-cut to brute-force atack (historically, many systems proposed, some cracked). Examples of current systems: DES (56-bit key), triple-DES (112-bit key), IDEA (128-bit key), RC5 (variable-length key)

More sophisticated lines of attack

known cleartext attack:

Eve sees some cleartext-cyphertext pairs. This is obviously helpful in conjunctions with brute-force attack; can try all keys--you known when you get the right one.

Chosen cleartext attack:

Eve selects particular cleartexts, gets to learn corresponding cyphertexts.

chosen cyphertext attack:

Eve selects cyphertexts, gets to learn corresponding cleartexts.

An ideal cryptosystem would resist all these attacks. A cryptosystem known to be susceptible to any of these attacks (e.g. addition cypher) should never be used.

In this class, our example cryptosystem is the exponentiation cypher

• key size is flexible
• based on a prime modulus m known to everyone
• key is a number k less than m-1 and relatively prime to m-1.
• each block is a mod m number
• encryption:

  

• decryption:

  

  where s is the mod multiplicative inverse of k.

• seems to be secure against attacks (if modulus is big enough)
• Too slow to be used in practice
• Does have a property not possessed by practical cryptosystems: ``commutativity'' (order of encryption with different keys doesn't matter)
  Used in card game (lab 6)

One weakness of most cryptosystems used as block cypher: if exact same block of cleartext is encrypted twice, cyphertext is exactly the same. This can provide some information to Eve. Useful information? Depends. Can be avoided by use of some randomness (a nonce) in encryption.

Another cryptographic tool: one-way function f (x)

• easy to go ``forwards'' (input: a, output f (a))
• hard to go ``backwards'' (input: b, output: a such that f (a)=b)

Assume that one-way function to be used is known to all parties; this should not hinder security.

Example for this class: where m is a big prime modulus.

• nothing special about 2. Could use another base.
• In fact, some bases are better than others, e.g. 1 is obviously a bad choice. Generally, choice depends on modulus. Don't worry about this issue for this class.

Use in protecting password file

A similar tool: cryptographic hash function/message digest function

function is agreed-upon and known to all parties in system; this should not hinder security

• arbitrarily long input
• fixed-length output (e.g. 128 bits)
• (Hence many inputs lead to same output.)

Security goal: collision-intractability: hard to find two specific inputs for which outputs are the same.

Practical examples: MD5, SHA

(We didn't give any explicit examples for use in this class)

Main application: digital signatures

Also can be used for commitment schemes (We used one-way function for this but there are security problems in doing so; better to use cryptographic hash function)

Agreeing on a key over a channel that is subject to eavesdropping: Diffie and Hellman's exponential key agreement protocol.

An eavesdropper who saw all the information going back and forth would still find it computationally difficult to figure out the agreed-upon key.

Once the parties agree on a key, they can use it in conjunction with an encryption scheme (probably a computationally secure one--using it with an informationally secure scheme would be inconvenient)

If channel is manipulable, Eve can use a person-in-the-middle attack to get the two parties to think they are communicating with each other while revealing cleartext to Eve-this can be avoided using signatures (as in homework 6).

Public-key cryptography-separate keys, one for encrypting and one for decrypting. Encryption key is public, decryption key is secret.

Like key agreement but avoids the need for interaction.

Inherently not information-theoretically secure--Eve knows Bob's public key so can encrypt on her own-can try all possible decryption keys, find the one that works.

examples: RSA, ElGamal

in practice, public key encryption is used for encryption of a session key that is then used for traditional single-key encryption.

Digital Signatures (e.g. use RSA ``backwards'')

• signer's public key is known to everyone anyone can verify her signature.
• enables signer to provide evidence that she approved of a document.
• signature depends on document
  
• Could be used on all sorts of offical documents

Public-key certificate

• document giving specific person's public key

  

• signature by some trusted Certificate Authority whose public key is widely known
• certificate prevents tampering with a party's public key.

Number theory

• modular arithmetic, modular multiplicative inverses
• Euler's phi function
• Euler's theorem, and use in decryption

Algorithms

• repeated squaring algorithm for modular exponentiation
• Euclid's algorithm for modular multiplicative inverse
• some computational problems are hard-no good algorithm

Functions and their inverse

Probability theory and probability distributions

Identification schemes and zero-knowledge

Lisa Eckstein
Tue Dec 10 21:36:19 EST 1996

About this document ...