Multi-Instance Security and its Application to Password-Based Cryptography

Gareth and Marcel discussed the paper on Multi-Instance Security and its Application to Password-Based Cryptography from this year's CRYPTO in the latest study group. In this paper, Bellare, Tessaro and Ristenpart introduce the theory of multi-instance security to deal with settings where one or more instances can feasibly be compromised, but it should remain infeasible to compromise all of some large number m of instances. Here, infeasible means that the effort of compromising all m instances should at least increase linearly with m. They define security metrics and games to model security in such a setting and examine the relations between their security notions. Finally, they analyse password-based Key Derivation Functions (KDFs) from the PKCS#5 standard to show that it meets their new multi-instance security definition.

Consider the setting of password-based encryption, where a message M is encrypted under a key derived from a password. Passwords are often chosen poorly in practice, which means that the set D of likely passwords (known as a dictionary) is limited and can be exhausted. Thus, an attacker can apply brute-force to retrieve the password using cN hashes, where N is the size of the dictionary D and c is equal to the number of hashes performed by the KDF. Now, increasing c would make it harder for the attacker to break a password, but it would also decrease the efficiency of the system. Furthermore, in the multi-user setting, the effort of the attacker to break the passwords of m users is still roughly cN because he only needs to exhaust the dictionary. To protect against such attacks it is possible to pick a random bitstring called the salt and hashing it together with the password when deriving the key. This salt is sent together with the message, so only the password is needed to derive the key. Now, the effort of the attacker is increased to mcN if the salt is large enough, because the attacker would need to create a dictionary for each distinct salt value that is used.

For their security metric, the authors say that the adversary wins if he breaks all m instances of the system and no fewer. They define security games based on the Left-or-Right (LOR) security definition, where an adversary has access to an encryption oracle that takes messages M₀ and M₁, and returns an encryption of M_b for some bit b that is fixed in the oracle. The adversary has to guess whether the oracle has the fixed bit b=0 (left oracle) or b=1 (right oracle). To extend this to the multi-instance setting, they define LORX-security, where the X stands for XOR. In this security game, the oracle has a fixed bit b_i for each of the instances 1 ≤ i ≤ m. The adversary can query the oracle on a message pair and an index (M₀,M₁,i) and get the encryption of M_bi under the key associated with instance i. In the end, the adversary must guess the XOR of the bits b_i. Another variation of this game is the AND metric, where instead of having to guess the XOR of the bits b_i, the adversary has to guess the vector of all bits b_i. The reason for using XOR is that even if the adversary figures out m-1 of the challenge bits, it still cannot guess the XOR of all challenge bits with high advantage unless it figures out the last one as well.

The authors also extend the Real-or-Random (ROR) security definition to the multi-instance setting, calling it RORX. In the RORX security game, the adversary has access to an oracle (that has some fixed bits b_i) that takes a message M₁ and an index i. The oracle then generates a random message M₀ of the same length as M₁ and encrypts M_bi under the key associated to instance i. In the single-instance setting, the adversary has to decide whether he is dealing with an oracle with fixed bit b = 1 (encrypting real messages) or b = 0 (encrypting random messages). In the RORX security game, the adversary must guess the XOR of the bits b_i. Finally, they define the Universal Key-Unrecoverability (UKU) security notion, in which the adversary gets access to an encryption oracle and must recover the key. It should be noted that all these definitions include corruptions of instances, which means the adversary also has access to a corruption oracle. When given an index i, the corruption oracle returns the key associated with instance i and if appropriate the bit b_i as well.

Having defined all these security notions and games, the authors show that LORX tightly reduces to RORX, whereas the reverse incurs a loss in tightness of 2^m. Similarly, LORX tightly reduces to UKU, whereas the reduction from RORX to UKU loses a factor 2^m as well. Similarly to the single-instance setting, UKU does not imply LORX, because the encryption scheme can ignore the key and just output messages in the clear, thus being UKU secure (as encryptions contain no information on the key) but not LORX secure. They also show that LORX implies AND, under mild conditions that are "usually met". According to the authors, the loss of tightness in the reductions for RORX shows that LORX is the right security definition for their purposes.

The final result of their paper is about the PKCS#5 standard on password-based encryption. Using a very technical proof with lots of different games, they show that the advantage of an adversary trying to break LORX security of your password-based encryption is bounded from above by m times the advantage of an adversary against the used encryption scheme plus 2 times the advantage of an adversary trying to guess the passwords plus 2 times the advantage of an adversary trying to break the KDF. Thus, the conclusion is that if you use a reasonably secure encryption scheme and KDF (e.g. KD1 from PKCS#5), then it all comes down to how hard it is to guess the passwords of your users.

There are some applications where it is really necessary to break all instances. Think of a group of people using a secret sharing scheme that have their secrets stored on their email account, which is protected by a password-based encryption scheme. If the threshold of the secret sharing is equal to the number of players, then an adversary would really need to break all instances of the password-based encryption to be able to retrieve the secret. However, for some applications you might want a less strict definition of security, because having all but one of your instances broken does not seem very secure. It would be interesting to see whether it is possible to create a definition that requires some fraction of the instances to remain secure and whether this leads to any meaningful results.