Intercepting tokens in cryptographic protocols: The empire strikes back in the clone wars

Achieving information-theoretically secure key exchange between two parties requires some “hardware set-up”, like the possibility to transmit quantum bits. An alternative approach, which recently emerged in the crypto community, is to use tamper-resistant hardware tokens in protocols. However, such tokens need to be transmitted physically between parties, opening up the possibility to attack the actual transfer of the token, possibly in combination with attacks on the digital protocol. We discuss such interception attacks on cryptographic protocols which rely on trustworthy hardware like one-time memory tokens (Goldwasser et al., Crypto 2008). In such attacks the adversary can mount man-in-the-middle attacks and access, or even substitute, transmitted tokens. We show that many of the existing token-based protocols are vulnerable against this kind of attack, which typically lies outside of the previously considered security models. We also give a positive result for protocols remaining secure against such attacks. We present a very efficient protocol for password-based authenticated key exchange based on the weak model of one-time memory tokens. Our protocol only requires four moves, very basic operations, and the sender to send ℓ tokens in the first step for passwords of length ℓ. At the same time we achieve information-theoretic security in Canetti´s universal composition framework (FOCS 2001) against adaptive adversaries (assuming reliable erasure), even if the tokens are not guaranteed to be transferred securely, i.e., even if the adversary can read or substitute transmitted tokens.