Virtual Machine Reset Vulnerabilities and Hedged Cryptography; Subspace LWE; Cryptography Against Continuous Memory Attacks

Virtual Machine Reset Vulnerabilities and Hedged Cryptography

Tom Ristenpart, UC San Diego

Virtual machines are widely used to, for example, support cloud computing services and improve home desktop security. In this talk I’ll present recent work on showing a new class of vulnerabilities, termed VM reset vulnerabilities, that arise due to reuse of VM snapshots. A snapshot is the saved state of a VM, which can include caches, memory, persistent storage, etc. A reset vulnerability occurs when resuming two or more times from the same VM snapshot exposes security bugs. I’ll report on our discovery of several reset vulnerabilities in modern browsers used within commonly-used VM managers. These vulnerabilities exploit weaknesses in cryptographic protocols when confronted with reused randomness. I’ll then explore a new framework of hedged cryptography, which aims to build into cryptographic protocols mechanisms that provide improved security in the face of reset (or other) vulnerabilities.

Subspace LWE

Krzysztof Pietrzak, CWI

The (decisional) learning with errors (LWE) problem asks to
distinguish “noisy” inner products of a secret vector with random
vectors from uniform. The presumed hardness of this and the related
learning parity with noise (LPN) problem has found many applications
in cryptography. Its appeal stems from the fact that it is provably as
hard as well studied worst-case lattice problems [Regev’05].

We introduce (seemingly) much stronger *adaptive* assumptions SLWE and
SLPN (S for “subspace”), where the adversary can learn inner products
of the secret and random vectors after they were projected into an
adaptively and adversarially chosen subspace. We prove that SLWE/SLPN
mapping into subspaces of dimension N are almost as hard as the
standard LWE/LPN assumptions using secrets of length N.

This implies that the standard LWE/LPN problems are surprisingly
robust with respect to tampering with the secret and/or the randomness
used to generate the samples. This robustness directly translates to
stronger security guarantees (e.g. it implies security against a broad
class of related-key attacks) one can give for cryptosystems proven
secure under the standard LWE/LPN assumptions.

We also present a new very simple and efficient authentication
protocol which is secure against active attacks under the SLPN (and
thus the standard LPN) assumption. Our protocol improves upon the HB+
protocol [Juels and Weis’05],[Katz, Shin’05] (which is the best known
protocol based on LPN achieving active security) in term of round
complexity (optimal two rounds compared to three) and a tight security
reduction.

Cryptography Against Continuous Memory Attacks

Yevgeniy Dodis, New York University

We say that a cryptographic scheme is Continuous Leakage-Resilient (CLR), if it allows users to refresh their secret keys, using only fresh local randomness, such that:
— The scheme remains functional after any number of key refreshes, although the public key never changes. Thus, the “outside world” is neither affected by these key refreshes, nor needs to know about their frequency.
— The scheme remains secure even if the adversary can continuously leak arbitrary information about the current secret-key of the system, as long as the amount of leaked information is bounded in between any two successive key refreshes. There is no bound on the total amount of information that can be leaked during the lifetime of the system.
In this work, we construct a variety of practical CLR schemes, including CLR one-way relations, CLR signatures, CLR identification schemes, and CLR authenticated key agreement protocols. For each of the above, we give general constructions, and then show how to instantiate them efficiently using a well established assumption on bilinear groups, called the K-Linear assumption.
Joint work with Kristiyan Haralambiev and Adriana Lopez-Alt and Daniel Wichs. The extended abstract of the paper will appear at FOCS’10 and can be found at http://eprint.iacr.org/2010/196