rough outline of CS007 security issues and tools

Two approaches to security:

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.


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:

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

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

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)

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

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

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

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

Public-key certificate

Number theory


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