No subject

Wed Aug 22 15:37:00 EDT 2012

Simulation Technique
Speaker: Omer Paneth. BU.
Monday, September 24, 10:00am =E2=80=93 11:30am in MCS 137

The introduction of a non-black-box simulation technique by Barak
(FOCS 2001) has been a major landmark in cryptography, breaking the
previous barriers of black-box impossibility. Barak=E2=80=99s techniques we=
subsequently extended and have given rise to various powerful
applications.  We present the first non-black-box simulation technique
that does not rely on Barak=E2=80=99s technique (or on nonstandard
assumptions). Our technique is based on essentially different tools:
it does not invoke universal arguments, nor does it rely on
collision-resis=E2=80=8Btant hashing. Instead, the main ingredient we use i=
the impossibility result for general program obfuscation of Barak et
al. (CRYPTO 2001).

Using our technique, we construct a new resettably sound
zero-knowledge (rsZK) protocol. rsZK protocols remain sound even
against cheating provers that can repeatedly reset the verifier to its
initial state and random tape. Indeed, for such protocols black-box
simulation is impossible. Our rsZK protocol is the first to be based
solely on semi-honest oblivious transfer and does not rely on
collision-resis=E2=80=8Btant hashing; in addition, our protocol does not us=
PCP machinery. In the converse direction, we show a generic
transformation from any rsZK protocol to a family of functions that
cannot be obfuscated.

Joint work with Nir Bitansky.


Substitution-pe=E2=80=8Brmutation networks, pseudorandom functions, and nat=
ural proofs
Speaker: Eric Miles, Northeastern.
Monday October 1, 10:00am =E2=80=93 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-l=E2=80=8Bength 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-pe=E2=80=8Brmutation 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 =3D 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 Device=
Speaker: Nadia Heninger, MSR.
Monday Oct 8, 2012, 10:00am =E2=80=93 11:30am in MCS 137

RSA and DSA can fail catastrophicall=E2=80=8By when used with malfunctionin=
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

More information about the Busec mailing list