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:
More sophisticated lines of attack
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
where s is the mod multiplicative inverse of k.
Another cryptographic tool: one-way function f (x)
Example for this class: where m is a big prime modulus.
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'')
Functions and their inverse
Probability theory and probability distributions
Identification schemes and zero-knowledge
Tue Dec 10 21:36:19 EST 1996
About this document ...