Cryptology ePrint Archive: Report 2012/659

Does Counting Still Count? Revisiting the Security of Counting based User Authentication Protocols against Statistical Attacks

Hassan Jameel Asghar and Shujun Li and Ron Steinfeld and Josef Pierpzyk

Abstract: At NDSS 2012, Yan et al. analyzed the security of several challenge-response type user authentication protocols against passive observers, and proposed a generic counting based statistical attack to recover the secret of some counting based protocols given a number of observed authentication sessions. Roughly speaking, the attack is based on the fact that secret (pass) objects appear in challenges with a different probability from non-secret (decoy) objects when the responses are taken into account. Although they mentioned that a protocol susceptible to this attack should minimize this difference, they did not give details as to how this can be achieved barring a few suggestions.

In this paper, we attempt to fill this gap by generalizing the attack with a much more comprehensive theoretical analysis. Our treatment is more quantitative which enables us to describe a method to theoretically estimate a lower bound on the number of sessions a protocol can be safely used against the attack. Our results include 1) two proposed fixes to make counting protocols practically safe against the attack at the cost of usability, 2) the observation that the attack can be used on non-counting based protocols too as long as challenge generation is contrived, 3) and two main design principles for user authentication protocols which can be considered as extensions of the principles from Yan et al. This detailed theoretical treatment can be used as a guideline during the design of counting based protocols to determine their susceptibility to this attack. The Foxtail protocol, one of the protocols analyzed by Yan et al., is used as a representative to illustrate our theoretical and experimental results.

Category / Keywords: cryptographic protocols / Identification protocols, observer attack, human-computer cryptography.

Publication Info: This is the full version of the paper with the same title which is to appear in the proceedings of the Network & Distributed System Security Symposium (NDSS) 2013.

Date: received 19 Nov 2012

Contact author: hassan jameel at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20121126:013024 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]