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 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. This impossibility result resolves an open problem stated by Bellare, Ristenpart and Tessaro (CRYPTO 2012).Category / Keywords: secret-key cryptography / password-based encryption, simulation-based security, random oracle Date: received 19 Feb 2016, last revised 19 Feb 2016 Contact author: gregory demay at inf ethz ch Available format(s): PDF | BibTeX Citation Version: 20160219:201823 (All versions of this report) Short URL: ia.cr/2016/166 Discussion forum: Show discussion | Start new discussion