Repository navigation
Expand file tree
/
Copy pathscoring.coffee
More file actions
354 lines (322 loc) · 13.5 KB
/
Copy pathscoring.coffee
File metadata and controls
354 lines (322 loc) · 13.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
adjacency_graphs = require('./adjacency_graphs')
# on qwerty, 'g' has degree 6, being adjacent to 'ftyhbv'. '\' has degree 1.
# this calculates the average over all keys.
calc_average_degree = (graph) ->
average = 0
for key, neighbors of graph
average += (n for n in neighbors when n).length
average /= (k for k,v of graph).length
average
scoring =
nCk: (n, k) ->
# http://blog.plover.com/math/choose.html
return 0 if k > n
return 1 if k == 0
r = 1
for d in [1..k]
r *= n
r /= d
n -= 1
r
lg: (n) -> Math.log(n) / Math.log(2)
# ------------------------------------------------------------------------------
# minimum entropy search -------------------------------------------------------
# ------------------------------------------------------------------------------
#
# takes a list of overlapping matches, returns the non-overlapping sublist with
# minimum entropy. O(nm) dp alg for length-n password with m candidate matches.
# ------------------------------------------------------------------------------
minimum_entropy_match_sequence: (password, matches) ->
bruteforce_cardinality = @calc_bruteforce_cardinality password # e.g. 26 for lowercase
up_to_k = [] # minimum entropy up to k.
# for the optimal seq of matches up to k, backpointers holds the final match (match.j == k).
# null means the sequence ends w/ a brute-force character.
backpointers = []
for k in [0...password.length]
# starting scenario to try and beat:
# adding a brute-force character to the minimum entropy sequence at k-1.
up_to_k[k] = (up_to_k[k-1] or 0) + @lg bruteforce_cardinality
backpointers[k] = null
for match in matches when match.j == k
[i, j] = [match.i, match.j]
# see if best entropy up to i-1 + entropy of this match is less than current minimum at j.
candidate_entropy = (up_to_k[i-1] or 0) + @calc_entropy(match)
if candidate_entropy < up_to_k[j]
up_to_k[j] = candidate_entropy
backpointers[j] = match
# walk backwards and decode the best sequence
match_sequence = []
k = password.length - 1
while k >= 0
match = backpointers[k]
if match
match_sequence.push match
k = match.i - 1
else
k -= 1
match_sequence.reverse()
# fill in the blanks between pattern matches with bruteforce "matches"
# that way the match sequence fully covers the password:
# match1.j == match2.i - 1 for every adjacent match1, match2.
make_bruteforce_match = (i, j) =>
pattern: 'bruteforce'
i: i
j: j
token: password[i..j]
entropy: @lg Math.pow(bruteforce_cardinality, j - i + 1)
cardinality: bruteforce_cardinality
k = 0
match_sequence_copy = []
for match in match_sequence
[i, j] = [match.i, match.j]
if i - k > 0
match_sequence_copy.push make_bruteforce_match(k, i - 1)
k = j + 1
match_sequence_copy.push match
if k < password.length
match_sequence_copy.push make_bruteforce_match(k, password.length - 1)
match_sequence = match_sequence_copy
min_entropy = up_to_k[password.length - 1] or 0 # or 0 corner case is for an empty password ''
crack_time = @entropy_to_crack_time min_entropy
# final result object
password: password
entropy: @round_to_x_digits(min_entropy, 3)
match_sequence: match_sequence
crack_time: @round_to_x_digits(crack_time, 3)
crack_time_display: @display_time crack_time
score: @crack_time_to_score crack_time
round_to_x_digits: (n, x) -> Math.round(n * Math.pow(10, x)) / Math.pow(10, x)
# ------------------------------------------------------------------------------
# threat model -- stolen hash catastrophe scenario -----------------------------
# ------------------------------------------------------------------------------
#
# assumes:
# * passwords are stored as salted hashes, different random salt per user.
# (making rainbow attacks infeasable.)
# * hashes and salts were stolen. attacker is guessing passwords at max rate.
# * attacker has several CPUs at their disposal.
# ------------------------------------------------------------------------------
SECONDS_PER_GUESS: .010 / 100 # single guess time (10ms) over number of cores guessing in parallel
# for a hash function like bcrypt/scrypt/PBKDF2, 10ms per guess is a safe lower bound.
# (usually a guess would take longer -- this assumes fast hardware and a small work factor.)
# adjust for your site accordingly if you use another hash function, possibly by
# several orders of magnitude!
entropy_to_crack_time: (entropy) ->
.5 * Math.pow(2, entropy) * @SECONDS_PER_GUESS # .5 for average vs total
crack_time_to_score: (seconds) ->
return 0 if seconds < Math.pow(10, 2)
return 1 if seconds < Math.pow(10, 4)
return 2 if seconds < Math.pow(10, 6)
return 3 if seconds < Math.pow(10, 8)
return 4
# ------------------------------------------------------------------------------
# entropy calcs -- one function per match pattern ------------------------------
# ------------------------------------------------------------------------------
calc_entropy: (match) ->
return match.entropy if match.entropy? # a match's entropy doesn't change. cache it.
entropy_func = switch match.pattern
when 'dictionary' then @dictionary_entropy
when 'spatial' then @spatial_entropy
when 'repeat' then @repeat_entropy
when 'sequence' then @sequence_entropy
when 'regex' then @regex_entropy
when 'date' then @date_entropy
match.entropy = entropy_func.call this, match
repeat_entropy: (match) ->
cardinality = @calc_bruteforce_cardinality match.token
@lg (cardinality * match.token.length)
sequence_entropy: (match) ->
first_chr = match.token.charAt(0)
if first_chr in ['a', '1']
base_entropy = 1
else
if first_chr.match /\d/
base_entropy = @lg(10) # digits
else if first_chr.match /[a-z]/
base_entropy = @lg(26) # lower
else
base_entropy = @lg(26) + 1 # extra bit for uppercase
if not match.ascending
base_entropy += 1 # extra bit for descending instead of ascending
base_entropy + @lg match.token.length
MIN_YEAR_SPACE: 20
REFERENCE_YEAR: 2000
regex_entropy: (match) ->
char_class_bases =
alpha_lower: 26
alpha_upper: 26
alpha: 52
alphanumeric: 62
digits: 10
symbols: 33
if match.regex_name of char_class_bases
@lg Math.pow(char_class_bases[match.regex_name], match.token.length)
else switch match.regex_name
when 'recent_year'
# conservative estimate of year space: num years from REFERENCE_YEAR.
# if year is close to REFERENCE_YEAR, estimate a year space of MIN_YEAR_SPACE.
year_space = Math.abs parseInt(match.regex_match[0]) - @REFERENCE_YEAR
year_space = Math.max year_space, @MIN_YEAR_SPACE
@lg year_space
date_entropy: (match) ->
# base entropy: lg of (year distance from REFERENCE_YEAR * num_days * num_years)
year_space = Math.max(Math.abs(match.year - @REFERENCE_YEAR), @MIN_YEAR_SPACE)
entropy = @lg(year_space * 31 * 12)
# add one bit for four-digit years
entropy += 1 if match.has_full_year
# add two bits for separator selection (one of ~4 choices)
entropy += 2 if match.separator
entropy
KEYBOARD_AVERAGE_DEGREE: calc_average_degree(adjacency_graphs.qwerty)
# slightly different for keypad/mac keypad, but close enough
KEYPAD_AVERAGE_DEGREE: calc_average_degree(adjacency_graphs.keypad)
KEYBOARD_STARTING_POSITIONS: (k for k,v of adjacency_graphs.qwerty).length
KEYPAD_STARTING_POSITIONS: (k for k,v of adjacency_graphs.keypad).length
spatial_entropy: (match) ->
if match.graph in ['qwerty', 'dvorak']
s = @KEYBOARD_STARTING_POSITIONS
d = @KEYBOARD_AVERAGE_DEGREE
else
s = @KEYPAD_STARTING_POSITIONS
d = @KEYPAD_AVERAGE_DEGREE
possibilities = 0
L = match.token.length
t = match.turns
# estimate the number of possible patterns w/ length L or less with t turns or less.
for i in [2..L]
possible_turns = Math.min(t, i - 1)
for j in [1..possible_turns]
possibilities += @nCk(i - 1, j - 1) * s * Math.pow(d, j)
entropy = @lg possibilities
# add extra entropy for shifted keys. (% instead of 5, A instead of a.)
# math is similar to extra entropy of l33t substitutions in dictionary matches.
if match.shifted_count
S = match.shifted_count
U = match.token.length - match.shifted_count # unshifted count
if U == 0
entropy += 1
else
possibilities = 0
possibilities += @nCk(S + U, i) for i in [1..Math.min(S, U)]
entropy += @lg possibilities
entropy
dictionary_entropy: (match) ->
match.base_entropy = @lg match.rank # keep these as properties for display purposes
match.uppercase_entropy = @extra_uppercase_entropy match
match.l33t_entropy = @extra_l33t_entropy match
match.base_entropy + match.uppercase_entropy + match.l33t_entropy
START_UPPER: /^[A-Z][^A-Z]+$/
END_UPPER: /^[^A-Z]+[A-Z]$/
ALL_UPPER: /^[^a-z]+$/
ALL_LOWER: /^[^A-Z]+$/
extra_uppercase_entropy: (match) ->
word = match.token
return 0 if word.match @ALL_LOWER
# a capitalized word is the most common capitalization scheme,
# so it only doubles the search space (uncapitalized + capitalized): 1 extra bit of entropy.
# allcaps and end-capitalized are common enough too, underestimate as 1 extra bit to be safe.
for regex in [@START_UPPER, @END_UPPER, @ALL_UPPER]
return 1 if word.match regex
# otherwise calculate the number of ways to capitalize U+L uppercase+lowercase letters
# with U uppercase letters or less. or, if there's more uppercase than lower (for eg. PASSwORD),
# the number of ways to lowercase U+L letters with L lowercase letters or less.
U = (chr for chr in word.split('') when chr.match /[A-Z]/).length
L = (chr for chr in word.split('') when chr.match /[a-z]/).length
possibilities = 0
possibilities += @nCk(U + L, i) for i in [1..Math.min(U, L)]
@lg possibilities
extra_l33t_entropy: (match) ->
return 0 if not match.l33t
extra_entropy = 0
for subbed, unsubbed of match.sub
# lower-case match.token before calculating: capitalization shouldn't affect l33t calc.
chrs = match.token.toLowerCase().split('')
S = (chr for chr in chrs when chr == subbed).length # num of subbed chars
U = (chr for chr in chrs when chr == unsubbed).length # num of unsubbed chars
if S == 0 or U == 0
# for this sub, password is either fully subbed (444) or fully unsubbed (aaa)
# treat that as doubling the space (attacker needs to try fully subbed chars in addition to
# unsubbed.)
extra_entropy += 1
else
# this case is similar to capitalization:
# with aa44a, U = 3, S = 2, attacker needs to try unsubbed + one sub + two subs
p = Math.min(U, S)
possibilities = 0
possibilities += @nCk(U + S, i) for i in [1..p]
extra_entropy += @lg possibilities
extra_entropy
# utilities --------------------------------------------------------------------
calc_bruteforce_cardinality: (password) ->
[lower, upper, digits, symbols, latin1_symbols, latin1_letters] = (
false for i in [0...6]
)
unicode_codepoints = []
for chr in password.split('')
ord = chr.charCodeAt(0)
if 0x30 <= ord <= 0x39
digits = true
else if 0x41 <= ord <= 0x5a
upper = true
else if 0x61 <= ord <= 0x7a
lower = true
else if ord <= 0x7f
symbols = true
else if 0x80 <= ord <= 0xBF
latin1_symbols = true
else if 0xC0 <= ord <= 0xFF
latin1_letters = true
else if ord > 0xFF
unicode_codepoints.push ord
c = 0
c += 10 if digits
c += 26 if upper
c += 26 if lower
c += 33 if symbols
c += 64 if latin1_symbols
c += 64 if latin1_letters
if unicode_codepoints.length
min_cp = max_cp = unicode_codepoints[0]
for cp in unicode_codepoints[1..]
min_cp = cp if cp < min_cp
max_cp = cp if cp > max_cp
# if the range between unicode codepoints is small,
# assume one extra alphabet is in use (eg cyrillic, korean) and add a ballpark +40
#
# if the range is large, be very conservative and add +100 instead of the range.
# (codepoint distance between chinese chars can be many thousand, for example,
# but that cardinality boost won't be justified if the characters are common.)
range = max_cp - min_cp + 1
range = 40 if range < 40
range = 100 if range > 100
c += range
c
display_time: (seconds) ->
minute = 60
hour = minute * 60
day = hour * 24
month = day * 31
year = month * 12
century = year * 100
[display_num, display_str] = if seconds < minute
[seconds, "#{seconds} second"]
else if seconds < hour
base = Math.round seconds / minute
[base, "#{base} minute"]
else if seconds < day
base = Math.round seconds / hour
[base, "#{base} hour"]
else if seconds < month
base = Math.round seconds / day
[base, "#{base} day"]
else if seconds < year
base = Math.round seconds / month
[base, "#{base} month"]
else if seconds < century
base = Math.round seconds / year
[base, "#{base} year"]
else
[null, 'centuries']
display_str += 's' if display_num? and display_num != 1
display_str
module.exports = scoring