Enhancing Cryptographic Key Generation with High-Quality Randomness
Ensuring High-Quality Randomness
in Cryptographic Key Generation
Henry Corrigan-Gibbs,
Wendy Mu,
Dan Boneh -
Stanford
Bryan Ford
- Yale
20
th
ACM Conference on Computer and Communications Security
6 November 2013
Image courtesy NASA Johnson Space Center
n
=
pq
n
=
pq
n’
=
pq’
n
=
p
q
n
’
=
p
q
’
n
=
p
q
n
=
p
q
’
[Heninger et al. USENIX Sec ’12]
[Lenstra et al. CRYPTO
’
12]
If keys are the same
Can read neighbor’s traffic
If keys share a factor
Anyone can factor RSA modulus
gcd(n, n’) = gcd(pq, pq’) = p
1
0
0
,
0
0
0
s
o
f
v
u
l
n
e
r
a
b
l
e
k
e
y
s
Common Failure Modes
1) App never reads strong random values
bytes = Hash(time(), get_pid(), pwd);
[CVE-2001-0950, CVE-2001-1467, CVE-2005-3087, CVE-2006-
1378, CVE-2008-0141, CVE-2008-2108, CVE-2009-3278]
2) App misuses random values
bytes = read_block(‘/dev/random’);
// ...
bytes = Hash(time());
[CVE-2001-1141, CVE-2003-1376, CVE-2008-0166, CVE-2011-
3599]
S
t
a
t
e
o
f
t
h
e
a
r
t
Does this key
incorporate strong
randomness?
S
t
a
t
e
o
f
t
h
e
a
r
t
?
!
?
!
?
!
S
t
a
t
e
o
f
t
h
e
a
r
t
C
A
?
!
?
!
?
!
G
o
a
l
Does this key
incorporate strong
randomness?
C
A
Random
values
D
e
v
i
c
e
E
n
t
r
o
p
y
A
u
t
h
o
r
i
t
y
(
E
A
)
bytes = read_from_EA();
// ...
// ...
bytes = Hash(time());
I
n
c
o
r
p
o
r
a
t
e
l
o
c
a
l
a
n
d
r
e
m
o
t
e
r
a
n
d
o
m
n
e
s
s
i
n
t
o
s
e
c
r
e
t
s
Check proof,
Sign pk
Random
values
, proof
D
e
v
i
c
e
E
n
t
r
o
p
y
A
u
t
h
o
r
i
t
y
(
E
A
)
P
r
o
o
f
d
o
e
s
n
o
t
r
e
v
e
a
l
t
h
e
d
e
v
i
c
e
’
s
s
e
c
r
e
t
s
EA
G
o
a
l
C
A
v
o
u
c
h
e
s
f
o
r
i
d
e
n
t
i
t
y
E
A
v
o
u
c
h
e
s
f
o
r
r
a
n
d
o
m
n
e
s
s
EA
EA’s signature
1)
Output public key is as “random” as possible
key_entropy =
max(
device_entropy
,
ea_entropy
);
2)
If device uses strong randomness source, it is
no worse off by running the protocol
– Does not leak secrets to EA
S
y
s
t
e
m
G
o
a
l
s
Outline
•
M
o
t
i
v
a
t
i
o
n
•
Threat Model
•
Protocol
•
Evaluation
Outline
•
Motivation
•
T
h
r
e
a
t
M
o
d
e
l
•
Protocol
•
Evaluation
Threat model
A
d
v
e
r
s
a
r
y
:
c
a
n
e
a
v
e
s
d
r
o
p
o
n
e
v
e
r
y
t
h
i
n
g
e
x
c
e
p
t
f
o
r
a
o
n
e
-
t
i
m
e
“
s
e
t
-
u
p
p
h
a
s
e
”
D
e
v
i
c
e
:
t
r
i
e
s
t
o
g
e
n
e
r
a
t
e
c
o
r
r
e
c
t
l
y
f
o
r
m
e
d
k
e
y
d
r
a
w
n
f
r
o
m
d
i
s
t
r
i
b
u
t
i
o
n
w
i
t
h
l
o
w
m
i
n
-
e
n
t
r
o
p
y
– Device is correct otherwise
Captures many real-world
randomness threats
Preliminaries
•
Homomorphic commitments
[Pedersen, Crypto ‘91]
–
Commitment to x: C(x) = g
x
h
r
–
Given C(x) and C(y), can compute C(x+y)
•
ZK proof of knowledge for multiplication
–
Given C(x), C(y), z, prove in zero knowledge
that z = xy m
od Q
–
bool Verify(
π, C(x), C(y), z
)
Outline
•
Motivation
•
Threat Model
•
P
r
o
t
o
c
o
l
•
Evaluation
C(x), C(y)
x’, y’
n, δ
x
, δ
y
, π
Find δs to make
p = x+x’+δ
x
q = y+y’+δ
y
RSA primes.
π =
Prove
(n=pq).
Check δs are small
Verify
(π, C(p), C(q), n),
sign public key
Prevents device
from setting x = –x’
σ(n)
C(p) = C(x)g
x’+
δ
x
Prevents device from
setting
δ
x
= –x’
Security Properties
•
If the device uses strong randomness
EA learns no useful info about the secrets
•
If the device uses strong randomness OR
the EA is correct:
Device ends up with a strong key
E
v
e
n
i
f
t
h
e
E
A
i
s
u
n
t
r
u
s
t
w
o
r
t
h
y
,
d
e
v
i
c
e
i
s
b
e
t
t
e
r
o
f
f
r
u
n
n
i
n
g
t
h
e
p
r
o
t
o
c
o
l
C(x), C(y)
x’, y’
n, δ
x
, δ
y
, π
Zero-knowledge
proof leaks no info
δs are O(log p), so
they don’t leak “much”
C
l
a
i
m
1
:
I
f
d
e
v
i
c
e
u
s
e
s
s
t
r
o
n
g
r
a
n
d
o
m
n
e
s
s
,
E
A
l
e
a
r
n
s
n
o
u
s
e
f
u
l
i
n
f
o
Randomized
commitments leak
no info
C(x), C(y)
x’, y’
n, δ
x
, δ
y
, π
C
l
a
i
m
2
:
C
o
r
r
e
c
t
E
A
w
i
l
l
n
e
v
e
r
s
i
g
n
a
k
e
y
s
a
m
p
l
e
d
f
r
o
m
a
d
i
s
t
r
i
b
u
t
i
o
n
w
i
t
h
l
o
w
m
i
n
-
e
n
t
r
o
p
y
Given x, x’, y, y’,
there are only a
few valid keys
C
(
x
)
,
C
(
y
)
x’, y’
n, δ
x
, δ
y
, π
C
l
a
i
m
2
:
C
o
r
r
e
c
t
E
A
w
i
l
l
n
e
v
e
r
s
i
g
n
a
k
e
y
s
a
m
p
l
e
d
f
r
o
m
a
d
i
s
t
r
i
b
u
t
i
o
n
w
i
t
h
l
o
w
m
i
n
-
e
n
t
r
o
p
y
A faulty device’s
only option is to pick
a “tricky” x and y
We prove that no
such “tricky”
values exist
Multiple Entropy Authorities
Outline
•
Motivation
•
Threat Model
•
Protocol
•
E
v
a
l
u
a
t
i
o
n
Key Generation Time
•
Wall-clock time (in seconds) to generate a key on a
Linksys E2500-NP home router.
•
EA is modern Linux server 5000 km away (80ms RTT)
Less than 2x
slowdown for RSA
Less than 2 seconds
for EC-DSA
Computational Overhead
Overhead diminishes
for RSA keys
Slowdown tends to 4x
for EC-DSA keys
Computational Bottlenecks
RSA-2048 key on Linksys E2500-NP home router
Protocol cost
Related Work
•
Hedged PKC
[Bellare et al., ASIACRYPT
’
09]
•
Better random values
–
Hardware RNG
–
Entropics
[Mowery et al. Oakland
’
13]
•
Juels-Guajardo Protocol
[PKC ‘02]
–
Defends against
kleptography
–
Requires heavier primitives
(24x more big exponentiations)
T
o
d
a
y
?
!
?
!
?
!
?
!
W
i
t
h
o
u
r
p
r
o
t
o
c
o
l
EA
Conclusion
•
Using “entropy authorities” is a practical
way to prevent weak cryptographic keys
•
Other parts of the stack need help too
–
Signing nonces, ASLR, DNS source ports, …
•
Interested in running an entropy authority?
Let’s talk!
Q
u
e
s
t
i
o
n
s
?
Henry Corrigan-Gibbs
henrycg@stanford.edu
http://github.com/henrycg/earand
Thanks to David Wolinsky,
Ewa Syta, Phil Levis, Suman Jana,
and Zooko Wilcox-O’Hearn.
p
q
Q
Q
Warning:
Simplification
ahead!
p
q
Q
Q
x
y
x+2
k
y+2
k
x’ and y’ are k-bit
values, so box has area
2
2k
Picked by
device
Max EA
value
Order of
group
2
k
2
k
p
q
Q
Q
x
y
x+2
k
y+2
k
x’
y’
E
A
’
s
r
a
n
d
o
m
c
h
o
i
c
e
o
f
x
’
a
n
d
y
’
d
e
t
e
r
m
i
n
e
s
n
(
+
/
-
δ
s
)
p
q
Q
Q
x
y
x+2
k
y+2
k
x’
y’
p
q
Q
Q
x
y
x+2
k
y+2
k
x’
y’
W
e
p
r
o
v
e
:
f
o
r
e
v
e
r
y
v
a
l
i
d
n
,
t
h
e
c
h
a
n
c
e
t
h
a
t
E
A
“
l
a
n
d
s
o
n
”
n
i
s
n
e
g
l
i
g
i
b
l
e
p
q
Q
Q
x
y
x+2
k
y+2
k
x’
y’
p
q
Q
Q
x
y
x+2
k
y+2
k
x’
y’
p
q
Q
Q
x
y
y+2
k
x’
y’
p
q
Q
Q
x
y
x+2
k
y+2
k
x’
y’
P
r
o
o
f
h
o
l
d
s
n
o
m
a
t
t
e
r
h
o
w
t
h
e
d
e
v
i
c
e
p
i
c
k
s
x
,
y
O
u
r
G
o
a
l
Reveals device’s
secrets to EA only
This presentation discusses the critical aspect of ensuring high-quality randomness in cryptographic key generation processes. It explores key vulnerabilities and common failure modes, emphasizing the importance of incorporating strong randomness. The content delves into various methods and issues related to randomness in cryptographic key generation, with insights from research studies and industry practices.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Ensuring High-Quality Randomness in Cryptographic Key Generation Henry Corrigan-Gibbs, Wendy Mu, Dan Boneh - Stanford Bryan Ford - Yale 20th ACM Conference on Computer and Communications Security 6 November 2013
n = pq Image courtesy NASA Johnson Space Center
n = pq n = pq
n = pq n = pq
[Heninger et al. USENIX Sec 12] [Lenstra et al. CRYPTO 12] If keys are the same Can read neighbor s traffic If keys share a factor Anyone can factor RSA modulus n = pq gcd(n, n ) = gcd(pq, pq ) = p n = pq 100,000s of vulnerable keys
Common Failure Modes 1) App never reads strong random values bytes = Hash(time(), get_pid(), pwd); [CVE-2001-0950, CVE-2001-1467, CVE-2005-3087, CVE-2006- 1378, CVE-2008-0141, CVE-2008-2108, CVE-2009-3278] 2) App misuses random values bytes = read_block( /dev/random ); // ... bytes = Hash(time()); [CVE-2001-1141, CVE-2003-1376, CVE-2008-0166, CVE-2011- 3599]
State of the art Does this key incorporate strong randomness?
State of the art ?!?!?!
State of the art ?!?!?! CA
Goal Does this key incorporate strong randomness? CA
Entropy Authority (EA) Device Random values bytes = read_from_EA(); // ... // ... bytes = Hash(time());
Entropy Authority (EA) Device Random values Proof does not reveal the device s secrets Incorporate local and remote randomness into secrets , proof Check proof, Sign pk EA
Goal EA s signature EA CA vouches for identity EA vouches for randomness
System Goals 1) Output public key is as random as possible key_entropy = max(device_entropy, ea_entropy); 2) If device uses strong randomness source, it is no worse off by running the protocol Does not leak secrets to EA
Outline Motivation Threat Model Protocol Evaluation
Outline Motivation Threat Model Protocol Evaluation
Threat model Adversary: can eavesdrop on everything except for a one-time set-up phase Device: tries to generate correctly formed key drawn from distribution with low min-entropy Device is correct otherwise Captures many real-world randomness threats
Preliminaries Homomorphic commitments [Pedersen, Crypto 91] Commitment to x: C(x) = gxhr Given C(x) and C(y), can compute C(x+y) ZK proof of knowledge for multiplication Given C(x), C(y), z, prove in zero knowledge that z = xy mod Q bool Verify( , C(x), C(y), z)
Outline Motivation Threat Model Protocol Evaluation
Prevents device from setting x = x C(x), C(y) x , y C(p) = C(x)gx + x Prevents device from setting x = x Find s to make p = x+x + x q = y+y + y RSA primes. = Prove(n=pq). n, x, y, Check s are small Verify( , C(p), C(q), n), sign public key (n)
Security Properties If the device uses strong randomness EA learns no useful info about the secrets If the device uses strong randomness OR the EA is correct: Device ends up with a strong key Even if the EA is untrustworthy, device is better off running the protocol
Claim 1: If device uses strong randomness, EA learns no useful info Randomized commitments leak no info C(x), C(y) x , y Zero-knowledge proof leaks no info s are O(log p), so they don t leak much n, x, y,
Claim 2: Correct EA will never sign a key sampled from a distribution with low min-entropy C(x), C(y) Given x, x , y, y , there are only a few valid keys x , y n, x, y,
Claim 2: Correct EA will never sign a key sampled from a distribution with low min-entropy C(x), C(y) x , y A faulty device s only option is to pick a tricky x and y We prove that no such tricky values exist n, x, y,
Outline Motivation Threat Model Protocol Evaluation
Key Generation Time Wall-clock time (in seconds) to generate a key on a Linksys E2500-NP home router. EA is modern Linux server 5000 km away (80ms RTT) Less than 2x slowdown for RSA Less than 2 seconds for EC-DSA No proto Proto Proto+net Slowdown 59.16 96.93 101.57 1.7x RSA 2048 EC-DSA 224 0.45 0.84 1.61 3.6x
Computational Overhead Slowdown tends to 4x Overhead diminishes for RSA keys for EC-DSA keys
Computational Bottlenecks Protocol cost RSA-2048 key on Linksys E2500-NP home router
Related Work Hedged PKC [Bellare et al., ASIACRYPT 09] Better random values Hardware RNG Entropics [Mowery et al. Oakland 13] Juels-Guajardo Protocol [PKC 02] Defends against kleptography Requires heavier primitives (24x more big exponentiations)
Today ?!?!?!?!
Conclusion Using entropy authorities is a practical way to prevent weak cryptographic keys Other parts of the stack need help too Signing nonces, ASLR, DNS source ports, Interested in running an entropy authority? Let s talk!
Questions? Henry Corrigan-Gibbs henrycg@stanford.edu http://github.com/henrycg/earand Thanks to David Wolinsky, Ewa Syta, Phil Levis, Suman Jana, and Zooko Wilcox-O Hearn.
q Q Warning: Simplification ahead! p Q
q x and y are k-bit values, so box has area 22k Q y+2k 2k y 2k x x+2k Max EA value p Q Order of group Picked by device
q EA s random choice of x and y determines n (+/- s) Q y+2k y y x x x+2k p Q
q Q y+2k y y x x+2k x p Q
q We prove: for every valid n, the chance that EA lands on n is negligible Q y+2k y y x x x+2k p Q
q Q y+2k y y x x x+2k p Q
q Q y+2k y y x x x+2k p Q
q Q y+2k y y x x p Q
q Q y+2k y y Proof holds no matter how the device picks x, y x+2k x p x Q
Our Goal Device Entropy Authority Strong randomness Weak randomness Strong randomness Weak randomness / Malicious Reveals device s secrets to EA only
