[Busec] BUsec this week: Eric Miles (Monday Oct 1, 10am MCS137)

Sharon Goldberg goldbe at cs.bu.edu
Sun Sep 30 12:25:12 EDT 2012


Our speaker tomorrow 10AM will be Eric Miles from Northeastern, speaking
about his CRYPTO'12 paper.  As usual, we meet at 10AM Monday in MCS
137 at 111 Cummington St, with lunch will be provided.

The following week, Nadia Heninger will speak about her USENIX best
paper  on detecting weak RSA and DSA keys, on Tuesday Oct 9 at 10AM.
(Note the different date, due to Columbus day).

Abstracts below.


BUsec Calendar:  https://sites.google.com/site/busecuritygroup/calendar
BUsec Mailing list:  http://cs-mailman.bu.edu/mailman/listinfo/busec


Substitution-permutation networks, pseudorandom functions, and natural proofs
Speaker: Eric Miles, Northeastern.
Monday October 1, 10:00am – 11:30am in MCS 137

There currently exists a troubling gap between the construction of
pseudorandom functions (PRF) and those of their popular,
bounded-input-length counterparts including block ciphers and hash
functions. This gap is both quantitative, because these counterparts
are more efficient than PRF in various ways, and methodological,
because these counterparts are often constructed via the
substitution-permutation network paradigm (SPN) which has not been
used to construct PRF. We take a step towards closing this gap by
giving new candidate PRF that are inspired by the SPN paradigm. This
paradigm involves a "substitution function" (S-box). Our main
candidates are

1. An SPN whose S-box is a random function on b bits, given as part of
the seed. We prove unconditionally that this candidate resists attacks
that run in time at most 2^(Omega(b)). Setting b = omega(log n) we
obtain an inefficient PRF, which seems to be the first such
construction using the SPN paradigm.

2. An SPN whose S-box is field inversion, a common choice in practical
constructions. This candidate is computable with Boolean circuits of
size n * polylog(n), and we prove that it has exponential security
against linear and differential cryptanalysis.

3. A candidate using an extreme setting of the SPN parameters (one
round, one S-box), where the S-box is again field inversion. This
candidate is also computable by circuits of size n * polylog(n), and
we prove that it has exponential security against parity tests that
look at 2^(0.9n) outputs.

Assuming the security of our candidates, our work narrows the gap
between the "Natural Proofs barrier" of Razborov and Rudich and
existing lower bounds, in three models: unbounded-depth circuits, TC0
circuits, and Turing machines.

"Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices"
Speaker: Nadia Heninger, MSR.
*** TUESDAY***** Oct 9, 2012, 10:00am – 11:30am in MCS 137

RSA and DSA can fail catastrophically when used with malfunctioning
random number generators, but the extent to which these problems arise
in practice has never been comprehensively studied at Internet scale.
We perform the largest ever network survey of TLS and SSH servers and
present evidence that vulnerable keys are surprisingly widespread. We
find that 0.75% of TLS certificates share keys due to insufficient
entropy during key generation, and we suspect that another 1.70% come
from the same faulty implementations and may be susceptible to
compromise. Even more alarmingly, we are able to obtain RSA private
keys for 0.50% of TLS hosts and 0.03% of SSH hosts, because their
public keys shared nontrivial common factors due to entropy problems,
and DSA private keys for 1.03% of SSH hosts, because of insufficient
signature randomness. We cluster and investigate the vulnerable hosts,
finding that the vast majority appear to be headless or embedded
devices. In experiments with three software components commonly used
by these devices, we are able to reproduce the vulnerabilities and
identify specific software behaviors that induce them, including a
boot-time entropy hole in the Linux random number generator. Finally,
we suggest defenses and draw lessons for developers, users, and the
security community.

Joint work with Zakir Durumeric, Eric Wustrow, and J. Alex Halderman

Sharon Goldberg
Computer Science, Boston University

Sharon Goldberg
Computer Science, Boston University

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list