**Password hardening** is a method where the system uses a combination of following to authenticate: - User's secret or password - User's typing patterns (feature vector) ### How do we quantify how someone types? For a password of length $n$, we measure: - How long a key is pressed - How long it takes to move from one key to the next **Feature vector** - There are $n$ key press lengths measured, there are $n−1$ transitions between keys, and so we are measuring $m = 2n−1$ time intervals or features. - The time intervals are characterized as fast, slow, or undefined (neither fast nor slow). - Being fast or slow is a distinguishing feature and undefined is a non-distinguishing feature. ## Instruction Table Passwords can be hashed and stored but feature vector values may vary across different login requests. ### Secret sharing based implementation - $ss(m, 2m)$ is a scheme in which a secret can be split into $2m$ shares and we need any $m$ of these shares to reconstruct it. - These secrets are stored in an **instruction table** which is encrypted with the password $pwd_a$. - By typing at the right speed we are able to get $m$ of the shares from the secret sharing scheme. In the image below the value on the left is chosen when slow and the value on the right is chosen when fast. We choose $m = 2n - 1$ total secret shares and all of them must be correct. If the true value is undefined the user can be either fast or slow.![[attachments/Screenshot 2023-05-30 at 6.37.25 PM.png]] - The secret that we reconstruct is the hardened password, which is used to encrypt the **history file**. The history file stores some number of past user login feature vectors. The history file is used to update the expected feature vector as the user's typing tendencies change. - $password$ → $instruction \space table + feature \space vector$ → $hardened \space password$ → $decrypted \space history \space file$ When we are able to successfully decrypt the history file, we know that the login was successful. #### Implementation Overview ![[attachments/Pasted image 20230604145349.png]] - $pwd_a =$ Password of user $a$ - $\phi_{i}(a)=$ Feature value of a user $a$ for $i^{th}$ feature (0, 1, or undefined) - $Hpwd_a =$ Hardened password; a randomly selected key with sufficient entropy - We want to check $Hpwd_a$ with a valid $pwd_a$, $\phi_{i}(a)$ and stored information - *Instruction table* and *History file* are stored by the system for the user $a$ which are used for the validation of the password & keystroke features ### Login procedure #### Initialization When a user is logging in for the first time, they go through the initialization sequence. **Notion** - Set $A$ of user accounts and account $a \in A$ - Password for $a$ is $pwd_a$ - Hardened password $hpwd_a$ is randomly chosen key of sufficient length **Initialization** - Choose $hpwd_a$ - Generate $2m$ shares of $hpwd_a$ - Encrypt each share with $pwd_a$ - History file is stored encrypted with $hpwd_a$. This has text which tells us when decryption is successful. - $t_i$ is threshold value for feature $i$ that defines when a feature is *slow* or *fast* #### Login procedure Let’s assume, - This is the $l_{th}$ attempt to log into the account $a$ - $pwd^‘$ is the typed password - $\phi(a,l)$ are the feature values for $i = 1,2,...m$ ![[attachments/Pasted image 20230604152331.png]] **READ FROM PAGE 22. Make notes later** - The system changes the hardened password on each login. Since this is the secret in our sharing scheme, the secret shares also have to change as a result. This means that if the attacker is able to compromise the **instruction table**, it will just get changed on the next login, giving them no significant advantage. - A user’s login history’s $mean$ and $standard \space deviation$ is used to categorize them as *fast* or *slow*. If the key press history is *fast* ($mean + factor\_standard \space dev < threshold$), we put the correct secret share into the left side of the instruction table and garbage into the right side, if it is *slow* ($mean - factor\_standard \space dev > threshold$) we put the good share on the right and garbage in the left. If neither, it is indistinguishing and we put good shares in both left and right of the instruction table. - A system needs nothing more than a personal & consistent typing device to validate passwords using this mechanism, unlike some other MFA systems that need additional hardware (i.e. fingerprint scanner). - The main benefit comes when features are distinguishing and unique to users. We can make a tradeoff between hardening and usability by adjusting the size of our undefined typing speed region. The implementation updates to track drift in user typing habits via the history file. Commercial offering → TypingDNA ### Security Analysis If the attacker compromises the machine and has access to all of the information within, - Trying to break into the **history file** requires hardened password, which has a high [[Guessing Entropy|entropy]] - Finding the password requires - Guessing the password - Guessing all the share combinations from the **instruction table**. This increases the [[Guessing Entropy#Entropy and work factor|work factor]] If an attacker uses a malware to get the password, they still need to find the right **feature vectors**. This is a question of [[Guessing Entropy#Hardening Entropy|hardening entropy]]. ### Hardening Entropy Let’s assume, - Each user has exactly 1 *distinguishing feature* - The index of this *distinguishing feature* follows uniform distribution On average, it will take $\frac{(2m+1)}{2}$ tries, which is $O(m)$. The hardening entropy is the logarithm of the work factor. $\sum_{𝑗=1} ^{𝑗=2𝑚} 𝑗. 𝑃(𝑗𝑡ℎ feature vector) = 1/2m . 2m. (2m+1)/2 = m$ $hardening \space entropy = O(log_2(m))$ **READ PAGE 29 ONWARD. Notes later** --- #comfort-hard