The count-min sketch is vulnerable to offline password-guessing attacks Online publication date: Tue, 17-May-2022
by Jaryn Shen; Qingkai Zeng
International Journal of Information and Computer Security (IJICS), Vol. 18, No. 1/2, 2022
Abstract: The count-min sketch is used to prevent users from selecting popular passwords so as to increase password-guessing attackers' cost and difficulty. This approach was proposed by Schechter et al. (2010) at USENIX Conference on Hot Topics in Security in 2010. Schechter et al. (2010) originally intended the count-min sketch to resist password-guessing attacks. In this paper, however, for the first time, we point out that the count-min sketch is vulnerable to offline password-guessing attacks. Taking no account of the false positive rate, the offline password-guessing attack against the count-min sketch and the password file requires less computational cost than the benchmark attack against only the password file. Taking the false positive into account, in order to eliminate the threat to quicken password-guessing rate, the lower bound of the false positive rate must be greater than 33% in the naked count-min sketch and greater than 31% in the expensive count-min sketch, both of which are too high and unacceptable.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Information and Computer Security (IJICS):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook