Bias in character distribution due to constraint application

[teythoon]

Describe the bug There is a postprocessing step (applyConstraints) that introduces a bias of the character distribution in generated passwords. Furthermore, due to the fact that four characters are appended to the generated password, there is structure in the generated passwords (e.g., in non-alphanumeric mode, the character in front of a + is more likely to be a number, the one in front of that is more likely to be a lower-case letter, the one in front of that more likely to be a upper-case letter). Obfuscating the location of these insertions by rotation is easily reversed by locating it using the + character.

This flaw was already present in the original algorithm.

To illustrate the problem, here is the distribution of output characters in alphanumeric and non-alphanumeric mode sampled over 10_000_000 passwords:

alphanumeric    non-alphanumeric
d, 2149503  P, 2366593
a, 2149518  b, 2366931
t, 2150279  c, 2367134
w, 2150562  l, 2367179
k, 2150680  N, 2367582
j, 2150755  C, 2367725
l, 2150815  U, 2368164
b, 2151422  z, 2368321
m, 2151865  Q, 2368362
o, 2152170  g, 2368717
q, 2152264  n, 2368804
e, 2152605  k, 2369032
y, 2152672  F, 2369143
x, 2152716  I, 2369151
v, 2152851  j, 2369311
i, 2152953  p, 2369338
s, 2153305  a, 2369490
r, 2153632  u, 2369490
n, 2153677  d, 2369622
c, 2153700  X, 2369636
z, 2153951  o, 2369654
h, 2154435  J, 2369725
p, 2154601  t, 2369777
g, 2154878  x, 2369869
f, 2154902  y, 2369914
u, 2155674  h, 2369923
4, 2239210  G, 2369966
2, 2255558  A, 2370011
6, 2255920  f, 2370101
5, 2256314  v, 2370125
1, 2257769  i, 2370298
3, 2258829  L, 2370426
8, 2273739  M, 2370587
9, 2273871  e, 2370681
0, 2275995  r, 2370763
7, 2292161  V, 2370921
I, 2597570  w, 2370984
T, 2597607  Y, 2371308
J, 2598230  E, 2371329
Q, 2598376  R, 2371375
O, 2598790  D, 2371763
G, 2599002  m, 2371848
U, 2599700  K, 2371885
K, 2599798  q, 2371969
L, 2599950  /, 2372319
H, 2599954  T, 2372381
P, 2600865  O, 2372689
S, 2601001  S, 2372894
M, 2601807  H, 2372988
N, 2602154  Z, 2373142
C, 2820596  s, 2373496
V, 2822187  W, 2374592
F, 2822946  B, 2374875
A, 2823313  4, 2443266
Y, 2823593  5, 2456374
X, 2824046  1, 2456971
W, 2824475  6, 2458689
B, 2824565  3, 2459493
Z, 2824647  2, 2461716
R, 2825588  0, 2472203
E, 2825834  8, 2473281
D, 2826545  9, 2473491
        7, 2488416
        +, 8620687

Expected behavior There should be no bias in the distribution of characters in the generated passwords.

[GWuk]

I'm no crypto expert to assess this, but from my point of view the purpose of pwdhash is to create passwords for websites and not crypographically strong keys as such (for which such a bias would be an issue).

I've no idea how to fix this without breaking existing passwords. If someone can provide a pull request which fixes the bias while maintaining backward compatibility, I'll be happy to merge it.

[teythoon]

This means that the passwords are weaker than they appear based on the length of the password.

Fixing this would break previously generated passwords.

I have surveyed a number of algorithms like PwdHash, and have concluded that LessPass is a better implementation of the same concept. I wanted to share my findings with you because you are providing this updated version of PwdHash in the Firefox extension store.