Public-Key Crypto
Review: Integrity
Problem: Sending a message over an
untrusted channel without being changed
Provably-secure solution: Random function
Practical solution:
m, v := fk(m) Mallory m’, v’ =? fk(m’) e.g. “Attack at dawn”, 628369867…
Pseudorandom function (PRF) Input: arbitrary-length k
Output: fixed-length value
Secure if practically indistinguishable from
a random function, unless know k Real-world use:
Message authentication codes (MACs) built on cryptographic hash functions
Popular example: HMAC-SHA256k(m) [Cautions?!]
k
Alice
k
Bob
2
Review: Confidentiality
Problem: Sending message in the presence
of an eavesdropper without revealing it Provably-secure solution: One-time pad
Practical solution:
Pseudorandom generator (PRG)
c
Bobk
p := D (c) k
Input: fixed-length k
Output: arbitrary-length stream
Secure if practically indistinguishable from a random stream, unless know k
Real-world use:
Stream ciphers (can’t reuse k)
Popular example: AES-128 + CTR mode
Block ciphers (need padding/IV)
Popular example: AES-128 + CBC mode
[Cautions?!]
k
Alice
c := E (p) k
Eve
Review: Diffie-Hellman Key Exchange Lets Alice and Bob agree on a shared secret
value by having a public conversation
Alice
Generates random secret a (0 < a < p)
Bob
Generates random secret b (0 < b < p)
gb mod p Computes x′
a
g modp
Eve
Computes x
ba ab
=(g modp) modp =(g modp) modp
a
Alice
b
Bob
ba
=g modp
ab
=g modp
x == x′ Problem: Man-in-the-middle attacks
ga modp gv modp
gu modp gb modp
Caution: D-H gives you a shared secret, but don’t know who’s on the other end!
a
Alice
uv
Mallory
b
Bob
Suppose Alice publishes data to lots of people, and they all want to verify integrity...
Can’t share an integrity key with everybody, or else anybody could forge messages
Suppose Bob wants to receive data from lots of people, confidentially...
Schemes we’ve discussed would require a separate key shared with each person
[What to do?]
Solution:
Public-key Crypto
So far, encryption key == decryption key “symmetric key crypto”
New idea: Keys are distinct, and you can’t find one from the other
Almost always used by splitting key-pair Alice keeps one key private (“private key”)
Publishes the other key (“public key”) Many applications
Invented in 1976 by Diffie and Hellman (earlier by Clifford Cocks of British intelligence, in secret)
Best known, most common public-key algorithm: RSA
Rivest, Shamir, and Adleman 1978
Requirements for a public key crypto system to be secure
1. Computationally easy for B to generate a key pair: PUb, PRb
2. Computationallyeasyforsender A to generate the ciphertext for message M: C=E(PUb, M)
3. Computationally easy for receiver B to decrypt the ciphertext: M=D(PRb, C)
4. Computational infeasible to guess PRb knowing PUb.
5. Computational infeasible to recover M from PUb and C.
How RSA works
Key generation:
1. Pick large (say, 1024 bits) random primes p and q
2. Compute N := pq
(RSA uses multiplication mod N)
3. Pick e to be relatively prime to (p-1)(q-1)
4. Find d so that ed mod (p-1)(q-1) = 1
5. Finally:
To encrypt: To decrypt:
Public key is (e,N) Private key is (d,N)
e
E(x) = x mod N
D(x) = xd mod N
Why RSA works
“It works” theorem: For all 0 < x < N,
can show that D(E(x)) = x Proof:
ed
D(E(x)) = (x mod pq) mod pq
ed
=x modpq
= xa(p-1)(q-1)+1 mod pq for some a (because ed mod (p-1)(q-1) = 1)
= (x(p-1)(q-1))ax mod pq
= (x(p-1)(q-1) mod pq)ax mod pq = 1ax mod pq
(because of the fact that if p,q are prime, then for all 0 < x < N,
x(p-1)(q-1) mod pq = 1) =x
Is RSA secure?
Best known way to compute d from e
is factoring N into p and q.
Best known factoring algorithm:
General number field sieve
Takes more than polynomial time but less than exponential time
to factor n-bit number.
(Still takes way too long if p,q are large enough and random.)
Fingers crossed...
but can’t rule out a breakthrough!
Signing with the public key for confidentiality or secrecy:
Does this provide integrity?
Signing with private key for integrity/authentication.
Does this provide confidentiality?
Subtle fact: RSA can be used for either confidentiality or integrity
RSA for confidentiality:
Encrypt with public key Decrypt with private key
“your eyes only” message
RSA for integrity:
Encrypt (“sign”) with private key Decrypt (“verify”) with public key
called a digital signature
[What if we want both confidentiality and integrity on the same message?]
How to have both confidentiality and integrity (using RSA)?
Alice (A) wants to send a secret message M to Bob (B) so that Bob can verify that it comes from Alice.
Which one(s) is/are secure?
1. E(E(M,PRA),PUB)
2. E(E(M, PUB), PRA)
3. C=E(M, PRA) t=E(H(C), PUB) • Send C||t
4. C=E(M, PUB) t=E(H(C), PRA) • Send C||t
Review: Public-key Crypto
So far, encryption key == decryption key
“symmetric key crypto” New idea: Keys are distinct.
RSA: N := pq
Public key is (e,N)
Private key is (d,N)
To encrypt: E(x) = x mod N
e
To decrypt: D(x) = xd mod N
RSA for confidentiality:
Encrypt with public key Decrypt with private key
RSA for integrity (digital signatures): Encrypt (“sign”) with private key
Decrypt (“verify”) with public key
[Cautions?!]
RSA drawback: Performance
Factor of 1000 or more slower than AES.
Dominated by exponentiation – cost goes up (roughly) as cube of key size.
Message must be shorter than N. [How big should the RSA keys be?]
Use in practice:
Encryption:
Use RSA to encrypt a random x < N, compute k := PRF(x), encrypt message using a symmetric cipher and key k
Signing:
Compute v := PRF(m), use RSA to sign a carefully padded version of v (many gotchas!)
Almost always should use crypto libraries to get the details right
True or false:
Public-key encryption is a general- purpose technique that has made symmetric encryption obsolete
True or false:
Key distribution is trivial when using public-key encryption, compared to the cumbersome handshaking involved with key distribution centers for symmetric encryption.
Attacks against RSA
1. Bruteforce:tryingallpossible private keys
2. Mathematicalattacks:factoring
3. Timingattacks:usingtherunning time of decryption
4. Hardware-based fault attack: induce faults in hardware to generate digital signatures
5. Chosenplaintextattackon unpadded RSA
Exercise
Suppose Bob uses RSA crypto with a very large modulus n for which the factorization cannot be found in a reasonable amount of time.
Suppose Alice sends a message to Bob by representing each alphabet letter as an integer between 0 and 25 (A->0, …, Z->25) and then encrypting each number separately using RSA with large e and large n.
Is this method secure?
If yes, why?
If not, how to efficiently attack this encryption method?
Solution:
For a set of message block values SM = {0, 1, 2, …, 25}. The set of corresponding ciphertext block values SC = {0e mod N, 1e mod N, …, 25e mod N}, and can be computed by everybody with the knowledge of the public key of Bob.
The most efficient attack is to compute Me mod N for all possible values of M, then create a look-up table with a ciphertext as an index, and the corresponding plaintext as a value of the appropriate location in the table.
Two subtle “textbook” RSA problems:
1. For small e and m: m^e mod N == m^e Trivial to decrypt!
2. If m is chosen from a small set, easy to confirm a ciphertext is a given message (anyone can encrypt!)
Chosen plaintext attack
Solution: RSA Padding
Need to make sure m is as large enough to wrap around N
Need to randomize before encryption
So Far:
The Security Mindset Message Integrity Confidentiality
Key Exchange
Building a Secure Channel Public Key Crypto
Next Week:
Begin Web Security Unit
HTTPS: Secure channels for the web