**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

- 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)

**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*)

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.

**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*