Password-based Encryption Analyzed

The use of passwords in security protocols is particularly delicate because of the possibility of off-line guessing attacks. We study password-based protocols in the context of a recent line of research that aims to justify symbolic models in terms of more concrete, computational ones. We offer two models for reasoning about the concurrent use of symmetric, asymmetric, and password-based encryption in protocol messages. In each of the models we define a notion of equivalence between messages and also characterize when passwords are used securely in a message or in a set of messages. Our new definition for the computational security of password-based encryption may be of independent interest. The main results of this paper are two soundness theorems. We show that under certain (standard) assumptions about the computational implementation of the cryptographic primitives, symbolic equivalence implies computational equivalence. More importantly, we prove that symbolically secure uses of passwords are also computationally secure.