Paper 2011/530
Key-Evolution Schemes Resilient to Space-Bounded Leakage
Stefan Dziembowski, Tomasz Kazana, and Daniel Wichs
Abstract
Much recent work in cryptography attempts to build secure schemes in
the presence of \emph{side-channel leakage} or leakage caused by
malicious software, like computer viruses. In this setting, the
adversary may obtain some additional information (beyond the control
of the scheme designer) about the internal secret state of a
cryptographic scheme. Here, we consider key-evolution schemes that
allow a user to evolve a secret-key via a \emph{deterministic}
function , to get updated keys . Such a scheme is \emph{leakage-resilient} if an adversary
that can leak on the first steps of the evolution process does
not get any useful information about any future keys. For such
schemes, one must assume some restriction on the \emph{complexity}
of the leakage to prevent \emph{pre-computation attacks}, where the
leakage on a key simply pre-computes a future key
and leaks even a single bit on it.
We notice that much of the prior work on this problem, and the
restrictions made therein, can be divided into two
types. Theoretical work offers rigor and provable security, but at
the cost of having to make strong restrictions on the type of
leakage and designing complicated schemes to make standard
reduction-based proof techniques go through (an example of such an
assumption is that only the data actually used in computation can
leak to the adversary). On the other hand, practical work focuses on
simple and efficient schemes, often at the cost of only achieving an
intuitive notion of security without formal well-specified
guarantees.
In this paper, we complement the two tracks via a middle-of-the-road
approach. On one hand, we rely on the random-oracle model,
acknowledging the usefulness of this methodology in practice despite
its theoretical shortcomings. On the other hand, we show that even
in the random-oracle model, designing secure leakage-resilient
schemes with clear and meaningful guarantees requires great care and
is susceptible to pitfalls. For example, just assuming that leakage
``cannot evaluate the random oracle'' can be misleading. Instead, we
define a new model in which we assume that the ``leakage'' can be
any arbitrary \emph{space bounded} computation that can make random
oracle calls itself. We connect the space-complexity of a
computation in the random-oracle modeling to the \emph{pebbling
complexity} on graphs. Using this connection, we derive meaningful
guarantees for relatively simple key-evolution constructions. Our
security proofs do not rely on the assumption that only data used in
the computation can leak.
Our scheme is secure also against a large and natural class of
active attacks. This is especially important if the key evolution
is performed on a PC that can be attacked by a virus. So far, all
results that provided solutions against such attacks were secure
under the assumption that the virus can download the data from the
machine, but he cannot modify any information stored on it (that was
called the {\em bounded retrieval model (BRM)}). This paper
provides the first scheme were the adversary in the BRM can also
modify the data stored on the machine.