Multi-Instance Security
and its Application to Password-Based Cryptography
Mihir Bellare (UCSD)
Thomas Ristenpart (University of Wisconsin-Madison)
Stefano
Tessaro (MIT)
Abstract:
This paper develops a theory of multi-instance (mi) security and applies it
to provide the first proof-based support for the classical practice of
salting in password-based cryptography. Mi-security comes into play in
settings (like password-based cryptography) where it is computationally
feasible to compromise a single instance, and provides a second line of
defense, aiming to ensure (in the case of passwords, via salting) that the
effort to compromise all of some large number m of instances grows linearly
with m. The first challenge is definitions, where we suggest LORX-security as
a good metric for mi security of encryption and support this claim by showing
it implies other natural metrics, illustrating in the process that even
lifting simple results from the si setting to the
mi one calls for new techniques. Next we provide a composition-based
framework to transfer standard single-instance (si)
security to mi-security with the aid of a key-derivation function. Analyzing
password-based KDFs from the PKCS#5 standard to
show that they meet our indifferentiability-style
mi-security definition for KDFs, we are able to
conclude with the first proof that per password salts amplify mi-security as
hoped in practice. We believe that mi-security is of interest in other
domains and that this work provides the foundation for its further
theoretical development and practical application.