Cryptology ePrint Archive: Report 2014/369

On the Limits of Authenticated Key Exchange Security with an Application to Bad Randomness

Michèle Feltz and Cas Cremers

Abstract: State-of-the-art authenticated key exchange (AKE) protocols are proven secure in game-based security models. These models have considerably evolved in strength from the original Bellare-Rogaway model. However, so far only informal impossibility results, which suggest that no protocol can be secure against stronger adversaries, have been sketched. At the same time, there are many diff erent security models being used, all of which aim to model the strongest possible adversary. In this paper we provide the first systematic analysis of the limits of game-based security models. Our analysis reveals that diff erent security goals can be achieved in diff erent relevant classes of AKE protocols. From our formal impossibility results, we derive strong security models for these protocol classes and give protocols that are secure in them. In particular, we analyse the security of AKE protocols in the presence of adversaries who can perform attacks based on chosen randomness, in which the adversary controls the randomness used in protocol sessions. Protocols that do not modify memory shared among sessions, which we call stateless protocols, are insecure against chosen-randomness attacks. We propose novel stateful protocols that provide resilience even against this worst case randomness failure, thereby weakening the security assumptions required on the random number generator.

Category / Keywords: cryptographic protocols / authenticated key exchange (AKE), security models, impossibility results, stateless protocols, stateful protocols, bad randomness, chosen-randomness

Date: received 26 May 2014

Contact author: mmc feltz at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140527:102008 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]