Public Key Cryptography
Cryptography
‹#›
Cryptography
Greek for “hidden writing”
The art of enciphering and deciphering codes
In modern use – the art of secure communication
Much wider than just enciphering and deciphering
One of the main tools for protecting information
Confidentiality – prevents adversaries from reading the information
Integrity – ensures detection of unauthorised modifications
‹#›
‹#›
Finite Fields
A field is an algebraic structure that consists of:
A set of elements
Four operations: addition, subtraction, multiplication and division
Examples: rational numbers, real numbers.
Finite fields are fields with a finite number of elements
Example: GF(p) – Integers modulo a prime number p
‹#›
Example: GF(7)
Seven elements: 0, 1, 2, 3, 4, 5, 6
Arithmetic:
1+1=?
3+3=?
5+5=?
3·2=?
4·2=?
1/2=?
‹#›
Exponentiation
Exponentiation: repeated multiplication
x0 = 1
xi+1 = x·xi
What is 32 in GF(7)? 33?
Can we do that efficiently with large numbers?
… e.g. 1000 digit numbers?
‹#›
A look at binary numbers
A binary number e is a sequence of bits e0…en-1 such that
What is ⎣e/2k⎦?
What about ⎣e/2k-1⎦?
‹#›
Square and Multiply
x ⟵1
for i ⟵|e|-1 downto 0 do
x ⟵x2 mod p
if (ei =1) then
x = xb mod p
endif
done
return x
‹#›
Logarithms
Reverse of exponentiation
What is log3(6) in GF(7)?
Discrete logarithm (DLP) is a hard problem!
No efficient algorithm known
‹#›
Key pairs
Agree on a finite field GF(p) and a generator g
Keys come in pairs
Represent a DLP problem
(public, private) = (A, α) where A=gα mod p
Oscar (the adversary) knows A. Why can’t he find α
Discrete logarithm is hard.
If p is a 3072 bit prime, Bob needs to test ~2128 values to find α
‹#›
Identity
Identity means holding a private key
How do we prove identity?
How does Bob verify that he is talking to Alice?
In our settings, Alice claims/asserts identity by publishing (“committing”) a public key A from a pair (A, α)
‹#›
Identification
Problem: Alice no longer has an identity
(A, α) = keypair()
A
???
s
A =? gs (mod p)
s=α
‹#›
Ephemera
Bob verifies because
gs = gα+r = gα·gr=A·R (mod p)
Note: s reveals nothing about α because r is random
(A, α) = keypair()
A
???
R
A·R =? gs (mod p)
s=α+r
(R, r) = keypair()
s
‹#›
Ephemera
Problem: Replay attack
Will solve later
(A, α) = keypair()
A
???
R
A·R =? gs (mod p)
s=α+r
(R, r) = keypair()
s
‹#›
Cheating
Bob verifies because
gs = gr’ = R’=A·R (mod p)
Note: Oscar knows nothing about α
Oscar does not know log(R)
(A, α) = keypair()
A
???
R
A·R =? gs (mod p)
s=r’
(R’, r’) = keypair()
s
R=R’/A
‹#›
Detecting cheating
Alice sends s=α+r=log(A·R)
And knows both α=log(A) and r=log(R)
Oscar sends s=log(A·R)
But knows neither α=log(A) nor r=log(R)
Bob cannot ask for α, and cannot ask for both s and r as these would reveal α
Bob can ask for either s or r and verify them
Correct s proves knowledge of α, if honest
Correct r proves honesty but not knowledge of α
‹#›
Identification
Bob verifies because
gs = geα+r = geα·gr=Ae·R (mod p)
To cheat, Oscar need to guess e: 50% chance
Replay attacks have 50% chance of being detected
Repeat until Bob is satisfied
(A, α) = keypair()
A
???
R
Ae·R =? gs (mod p)
s=eα+r
(R, r) = keypair()
s
e=random({0,1})
e
‹#›
Chaum-Evertse-Graaf ID
(A, α) = keypair()
A
???
R1
Ae1·R1 =? gs1 (mod p)
s1=e1α+r1
(R1, r1) = keypair()
s1
e1=random({0,1})
e1
???
R128
Ae128·R128 =? gs128 (mod p)
s128=e128α+r128
s128
e128=random({0,1})
e128
‹#›
Schnorr ID
128 rounds of Chaum-Evertse-Graaf:
Too much communication
128⨉R, 128⨉s
Too much computation
Alice and Bob compute 128 exponentiations, each
Schnorr’s idea: “parallelise” the 128 rounds
Use a single 128-bit challenge instead of 128 one bit challenges
‹#›
Schnorr ID
Single round
Alice computes one exponentiation
Bob computes two exponentiations (one is short)
(A, α) = keypair()
A
???
R
Ae·R =? gs (mod p)
s=eα+r
(R, r) = keypair()
s
e=random({0,1})
e
e=random([0,2128))
‹#›
Digital Signatures
Non-interactive proofs that a signer has witnessed (created, saw) some data
Provides:
Authenticity – we know the message is genuine
Message integrity – we know it was not modified
Non-repudiability – the signer cannot deny signing
Only need the signer’s public key to verify signatures
‹#›
“Non-interactive Schnorr”
(A, α) = keypair()
A
e=Hash(R)
Ae·R =? gs (mod p)
s=eα+r
(R, r) = keypair()
s
R
e=Hash(R)
‹#›
Cryptographic Hash Function
A hash function that is also:
One-way, i.e. no easy way of inverting it
Small changes in the input result in large changes in the output
Collision resistant – hard to find a pair of inputs that hash to the same value
Examples:
MD5 (insecure)
SHA-1 (insecure)
SHA-256
Keccak
‹#›
“Compact NI Schnorr”
“Compact” because e is typically much shorter than R
(A, α) = keypair()
A
e=Hash(R)
Ae·R =? gs (mod p)
s=eα+r
(R, r) = keypair()
s
R
e=Hash(R)
e
R=gs/Ae (mod p)
e=?Hash(R)
‹#›
Avoiding Division
Division is less efficient than multiplication. Can we remove it?
(A, α) = keypair()
A
e=Hash(R)
s=eα+r
(R, r) = keypair()
s
e
R=gs/Ae (mod p)
e=?Hash(R)
s=r-eα
R=gs·Ae (mod p)
e=?Hash(R)
‹#›
Schnorr Signatures
(A, α) = keypair()
A
e=Hash(R)
(R, r) = keypair()
s
e
s=r-eα
R=gs·Ae (mod p)
e=?Hash(R)
M
e=Hash(R,M)
R=gs·Ae (mod p)
e=?Hash(R,M)
‹#›
Symmetric encryption
5pm at the
rose garden?
5pm at the
rose garden?
‹#›
“Formal” definitions
A cipher defined over (K, M, C) is a pair of efficient functions (E, D)
E: K⨉MC, D: K⨉CM
(We usually write Ek(m) instead of E(k,m))
5pm at the
rose garden?
Ek()
Gobbledy
gobbledygook
Gobbledy
gobbledygook
Dk()
5pm at the
rose garden?
‹#›
Diffie-Hellman Key Exchange
Task:
Alice and Bob want to establish a shared secret
They have no secure channel to transfer it
Recall that A=gα mod p, B=gβ mod p
Hence: Bα=(gβ)α=gβα=gαβ= (gα)β=Aβ
(A, α) = keypair()
A
(B, β) = keypair()
B
S=Bα mod p
S=Aβ mod p
‹#›
Forward Secrecy
Alice and Bob can now use S to derive a secret key for a symmetric protocol.
What would happen if Alice’s key is compromised?
Alice can generate a new key pair
But what about past communication?
(A, α) = keypair()
A
(B, β) = keypair()
B
S=Bα mod p
S=Aβ mod p
‹#›
Ephemeral DH
Alice and Bob generate random key pairs every time they communicate
Provides forward secrecy
No authentication. Vulnerable to Man in the Middle (MITM) attacks
(KA, kA) = keypair()
KA
(KB, kB) = keypair()
KB
S=KBkA mod p
S=KAkB mod p
‹#›
Class Exercise
Describe an MITM attack that allows Oscar to decrypt all communication between Alice and Bob.
(KA, kA) = keypair()
KA
(KB, kB) = keypair()
KB
S=KBkA mod p
S=KAkB mod p
‹#›
Ephemeral DH + Signatures
Use long term keys to sign ephemeral keys
How does Alice know that B is Bob’s key?
(KA, kA) = keypair()
KA
(KB, kB) = keypair()
KB
S=KBkA mod p
S=KAkB mod p
(A, α) = keypair()
A
(B, β) = keypair()
B
(RA, sA) = sign(KA, α)
(RA, sA)
(RB, sB) = sign(KB, β)
verify(KB, RB, sB, B)
verify(KA, RA, sA, A)
(RB, sB)
‹#›
Certificates
To know that B is Bob’s key, Bob asks a trusted entity (certificate authority or CA) to sign it.
The CA issues a certificate certifies that the key belongs to Bob
How does Alice know she can trust the certificate authority?
Use another trusted certificate authority?
Root CAs are implicitly trusted.
‹#›
Root CAs
Where do we get these from?
Downloaded with the browser?
Firefox default list includes 159 CAs
Chicken and egg problem
Pre-installed on our computer
What happens if one of them is breached?
‹#›
e = ei ⋅2
i
i=0
n−1
∑
e=e
i
×2
i
i=0
n-1
å
e 2k⎢⎣
⎥
⎦= ei ⋅2
i−k
i=k
n−1
∑
e2
k
ê
ë
ú
û
=e
i
×2
i-k
i=k
n-1
å
e 2k−1⎢⎣
⎥
⎦= ei ⋅2
i−k+1
i=k−1
n−1
∑ = 2 ⋅ e 2k⎢⎣ ⎥⎦+ ek−1
e2
k-1
ê
ë
ú
û
=e
i
×2
i-k+1
i=k-1
n-1
å
=2×e2
k
ê
ë
ú
û
+e
k-1
e 2k−1⎢⎣
⎥
⎦= ei ⋅2
i−k+1
i=k−1
n−1
∑
e2
k-1
ê
ë
ú
û
=e
i
×2
i-k+1
i=k-1
n-1
å
e 2k−1⎢⎣
⎥
⎦= 2 ⋅ e 2
k⎢
⎣
⎥
⎦+ ek−1
e2
k-1
ê
ë
ú
û
=2×e2
k
ê
ë
ú
û
+e
k-1
b
e 2k−1⎢⎣⎢
⎥
⎦⎥ = b
2⋅ e 2k⎢⎣⎢
⎥
⎦⎥+ek−1
b
e2
k-1
ê
ë
ê
ú
û
ú
=b
2×e2
k
ê
ë
ê
ú
û
ú
+e
k-1
= b
e 2k⎢⎣⎢
⎥
⎦⎥⎛
⎝
⎜
⎞
⎠
⎟
2
⋅bek−1
=b
e2
k
ê
ë
ê
ú
û
ú
æ
è
ç
ö
ø
÷
2
×b
e
k-1