Cryptology ePrint Archive: Report 2016/166

Per-Session Security: Password-Based Cryptography Revisited

Grégory Demay and Peter Gaži and Ueli Maurer and Björn Tackmann

Abstract: Cryptographic security is usually defined as some form of guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of a secure cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. In particular, a user with a very strong password enjoys the full security guarantees of an analysis in which passwords are replaced by uniform cryptographic keys.

Our contributions are two-fold. First, we provide a new, general technique for stating security guarantees that degrade gracefully and which could not be expressed with existing formalisms. Our method is simple, does not require new security definitions, and can be carried out in any simulation-based security framework (thus providing composability). Second, we apply our approach to revisit the analysis of password-based message authentication and of password-based (symmetric) encryption (PBE), investigating whether they provide strong per-session guarantees.

In the case of PBE, one would intuitively expect a weak form of confidentiality, where a transmitted message only leaks to the adversary once the underlying password is guessed. Indeed, we show that PBE does achieve this weak confidentiality if an upper-bound on the number of adversarial password-guessing queries is known in advance for each session. However, such local restrictions appear to be questionable since we show that standard domain separation techniques employed in password-based cryptography, such as salting, can only provide global restrictions on the number of adversarial password-guessing queries. Quite surprisingly, we show that in this more realistic scenario the desired per-session confidentiality is unachievable.

Category / Keywords: secret-key cryptography / password-based encryption, simulation-based security, random oracle

Date: received 19 Feb 2016, last revised 19 Apr 2017

Contact author: gregory demay at inf ethz ch

Available format(s): PDF | BibTeX Citation

Version: 20170419:141650 (All versions of this report)

Short URL: ia.cr/2016/166

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]