Passwords recognized as single tokens inconsistently rewarded for capitalization
- Dominant language
- CoffeeScript
- Stars
- 16.1k
- Forks
- 1k
- PR merge metrics
- No merged PRs in 30d
Description
First of all, great library, great paper and really enjoyable talk at USENIX. We've been using this library at [Teesside University's Software Reliability Lab](https://github.com/sr-lab) for some research around the security of password composition policies and it yields some really interesting data (and drops right in to our tooling).
While we were working with zxcvbn, we uncovered a few interesting characteristics that we hope to present to the maintainers here in future, but for now there's one particular issue that I'd like to propose a fix for.
# Overview
The crux of the issue is as follows:
The `uppercase_variations` [function](https://github.com/dropbox/zxcvbn/blob/7b4315333b99982ddf662eee86a73c5f0c2c2fc8/src/scoring.coffee#L328) takes a match and returns a guess number multiplier based on how that match's word is capitalized. This works great for passwords that have a worst-case (i.e. lowest guess number) partitioning that does not contain partitions with non-letter characters at the beginning or end, but otherwise rewards capitalization too generously.
# Demonstration
For an example of what I mean, take `bananas123` as a case in which there's no issue. This string is cleanly partitioned into `bananas` (dictionary) and `123` (sequence). Guess numbers are calculated for each partition which are then used to compute the overall guess number. Capitalizing the `b` or the `s` in this password multiplies the guess number calculated for `bananas` by 2. Everything works as expected.
Now consider `12345qwert`, a case where things don't quite work as expected. The worst-case partitioning of this password contains only one token `12345qwert` (dictionary) because this can be found in the library's [internal common passwords list](https://github.com/dropbox/zxcvbn/blob/3bf5a6cf3aa916dabb4c4e73a6ae24277ab36170/data/passwords.txt). Because `uppercase_variations` does not strip non-letter characters before computing the guess number multiplier for a partition, capitalizing the `q` in this password rewards the password for having a capital letter "in the middle" when it is intuitively in a terminal position in the `qwert` substring and warrants a flat multiplier of 2 only. This leads to some strange transpositions like `12345Qwert` (guess number 2521) being valued as stronger than `12345qwerT` (guess number 1009).
## Evidence
The following table shows a sample of tokens from the common passwords list that exhibit the issue described, against their number of occurrences in [Troy Hunt's Pwned Passwords](https://haveibeenpwned.com/Passwords) as: all-lowercase; with their first letter capitalized; and with their last letter capitalized:
| Password | Lowercase | Capitalized (First) | Capitalized (Last) |
|------------|-----------|---------------------|--------------------|
| 1q2w3e4r5t | 1109333 | 5347 | 1021 |
| 1qaz2wsx | 726341 | 3011 | 2271 |
| 123qwe | 675027 | 2906 | 516 |
| 1q2w3e4r | 598708 | 4685 | 3135 |
| 123abc | 595847 | 1215 | 91 |
| 1q2w3e | 473459 | 2171 | 363 |
| 1234qwer | 385656 | 3860 | 815 |
| 12qwaszx | 312045 | 848 | 459 |
| 50cent | 179247 | 478 | 11 |
Now consider the guess number given by zxcvbn to these same tokens:
| Password | Lowercase | Capitalized (Start) | Capitalized (End) |
|------------|-----------|---------------------|-------------------|
| 1q2w3e4r5t | 291 | 1451 | 581 |
| 1qaz2wsx | 29 | 169 | 57 |
| 123qwe | 34 | 100 | 67 |
| 1q2w3e4r | 193 | 769 | 385 |
| 123abc | 224 | 670 | 447 |
| 1q2w3e | 687 | 2059 | 1373 |
| 1234qwer | 87 | 345 | 173 |
| 12qwaszx | 350 | 2095 | 699 |
| 50cent | 2248 | 8989 | 4495 |
In all cases shown, the *more common* capitalization scheme is given a *higher* guess number. This is the opposite of what we want. After stripping all non-letter characters before doing any calculation in `uppercase_variations` we get the following:
| Password | Lowercase | Capitalized (Start) | Capitalized (End) |
|------------|-----------|---------------------|-------------------|
| 1q2w3e4r5t | 291 | 581 | 581 |
| 1qaz2wsx | 29 | 57 | 57 |
| 123qwe | 34 | 67 | 67 |
| 1q2w3e4r | 193 | 385 | 385 |
| 123abc | 224 | 447 | 447 |
| 1q2w3e | 687 | 1373 | 1373 |
| 1234qwer | 87 | 173 | 173 |
| 12qwaszx | 350 | 699 | 699 |
| 50cent | 2248 | 4495 | 4495 |
Guess numbers are now appropriately low. This change will only ever result in a reduction in guess number, never an increase.
# Impact
Running a quick script over the common passwords list to pull out entries that both contain more than one letter and start or end with a non-letter sequence yields 10,310 results. Any password containing these as dictionary partitions will have its guess number affected if a capital letter occurs as the first or last letter in the string.
# Remediation
This issue is readily fixed by stripping non-letter characters before we do any computation in the `uppercase_variations` function. In the case of `12345qwert` we now get a guess number of 1009 whether we capitalize the `q` or the `t`. I'll submit a PR straight after putting this issue in.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.