Fuzzy Verifier: To overcome the dilemma of maintaining usability while achieving two-factor security even the smart card can be tampered, here we propose a tradeoff between security and usability: Instead of storing {h(PWi)} in the card memory, we store {h(PWi) mod N}, where PWi stands for user Ui’s password, h() is a Hash function (e.g., SHA-1 in the following experiments), and N the balance factor (a moderate integer, e.g. N=256). Then, user Ui can change her password locally, yet this user-friendliness comes at the prices of security: the chances of an adversary to guess Ui’s password is roughly 256t/D, where D is the password space from which each user’s password is uniformed drawn and t is the number of adversary’s online attempts. Generally, D is moderately limited, e.g., |D|=1000,000 [1,2]. That’s to say, the modified protocol using this new method is able to meet the Level 1 security of NIST SP800-63-2 [3] even if the smart card has been compromised, which guarantees that the success probability of one online guessing attempt by the adversary is no more than 1/1024.As is well known, online guessing can be effectively thwarted by locking the account after several failed login attempts or by only allowing a probabilistic number of failed guesses [9].In two other cases, the security is improved: (1) the chances of an adversary to change Ui’s password is 1/256; (2) the chances of Ui to accidentally make the card unusable is 1/256 when inputs an unintended new password in the password change phase, reduced to 1/65536 if users are required to type the new password twice.
In the above analysis, the value of 256t/D is obtained on the basis of the assumption that, user passwords are uniformly distributed. However, in practice, this is generally not the case——user passwords have strong bias towards similarity! This can be evidenced by the following statistics. For example, the top 20 most popular passwords from Rockyou dataset [4] account for 2.54% of the entire set. To evaluate the practical effectiveness of our proposed ``fuzzy verifier’’ when user password space is greatly biased, we use four real-life publicly available password datasets(i.e., top 1 million most popular passwords from 32 million Rockyou dataset, top 2 million most popular passwords from 32 million Rockyou dataset, top 1 million most popular passwords from 6.43 million CSDN dataset [5], top 1 million most popular passwords from 6.43 million CSDN) to carry out the following two explorations:
(1) How many passwords in D fall into the same password pool with PWi? As a complement, we say PWj falls into the same pool with PWi only if the value of h(PWj) mod 256 equals h(PWi) mod 256. We say the resulting password pool is POOLi.
(2) How many password finally remained if we remove these passwords from POOLi that are unlikely to be Ui’s password PWi? Without any specific information about Ui’s personal information (e.g., hobbies, name, birthday), it is really difficult (probably impossible) to accurately define what’s the character(s) that are unlikely to be hold by Ui’s password PWi. As a result, we can only use the statistical information of POOLi to detect whether there is any abnormality. An effective metric is the expected number of guesses required to find any password in POOLi if the attacker proceeds an optimal online attack (i.e., testing the most likely passwords first), known as guesswork or guessing entropy [2,6].
Admittedly, we have obtained two large dataset with user ID and password, yet such information is definitively sensitive, and may cause subtle sufferings to victims if such dataset are illustrated publicly, for users tend to reuse their IDs and passwords [7,8]. As far as we know, using guessing entropy to characterize a password dataset is currently the best strategy that can be adopted while corresponding user-specific information is unavailable (or cannot be appropriately used). Assume password pool POOLi includes x entries. Each of the entry is of the <Password, Count, Popularity> form, see POOL0 of the top 2 million CSDN dataset 0.txt. Note that, the term “Count” stands for the popular count of the corresponding password. For example, if the password “shanshan” occurs 210 times in the entire 6 million CSDN dataset, we say the popular count of password “shanshan” is 210. The “Popularity” of password “shanshan” is 210/(total count in the current pool)=210/13262=0.0158347. For simplicity, we denote the popularities of each password pool in decreasing order P1, P2, P3, …… Px.
Accordingly, we can determine the guessing entropy [2] of POOL0 by computing E=1 * P1 + 2 * P2 + 3 * P3 + … + x * Px = 2492.49, which is larger than 1024. This means POOL0 is a valid pool, and the success probability of one online guessing attempt using password candidates in POOL0 by the adversary is 1/2492.49, no more than 1/1024.
Our empirical results demonstrate that the distribution bias of password space D does not significantly degrade our proposed method, and it ensures the Level 1 security of NIST SP800-63-2.