Module: Zxcvbn::Entropy

Includes:
Math
Included in:
Scorer
Defined in:
lib/zxcvbn/entropy.rb

Constant Summary collapse

NUM_YEARS =

years match against 1900 - 2019

119
NUM_MONTHS = 
12
NUM_DAYS = 
31
START_UPPER = 
/^[A-Z][^A-Z]+$/
END_UPPER = 
/^[^A-Z]+[A-Z]$/
ALL_UPPER = 
/^[A-Z]+$/
ALL_LOWER = 
/^[a-z]+$/

Instance Method Summary collapse

Methods included from Math

#average_degree_for_graph, #bruteforce_cardinality, #lg, #min, #nCk, #starting_positions_for_graph

Instance Method Details

#calc_entropy(match) ⇒ Object 



4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/zxcvbn/entropy.rb', line 4

def calc_entropy(match)
  return match.entropy unless match.entropy.nil?
  # debugger
  match.entropy = case match.pattern
  when 'repeat'
    repeat_entropy(match)
  when 'sequence'
    sequence_entropy(match)
  when 'digits'
    digits_entropy(match)
  when 'year'
    year_entropy(match)
  when 'date'
    date_entropy(match)
  when 'spatial'
    spatial_entropy(match)
  when 'dictionary'
    dictionary_entropy(match)
  end
  match.entropy ||= 0
end

#date_entropy(match) ⇒ Object 



58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/zxcvbn/entropy.rb', line 58

def date_entropy(match)
  if match.year < 100
    entropy = lg(NUM_DAYS * NUM_MONTHS * 100)
  else
    entropy = lg(NUM_DAYS * NUM_MONTHS * NUM_YEARS)
  end

  if match.separator
    entropy += 2
  end

  entropy    
end

#dictionary_entropy(match) ⇒ Object 



72
73
74
75
76
77
78
 
# File 'lib/zxcvbn/entropy.rb', line 72

def dictionary_entropy(match)
  match.base_entropy = lg(match.rank)
  match.uppercase_entropy = extra_uppercase_entropy(match)
  match.l33t_entropy = extra_l33t_entropy(match)

  match.base_entropy + match.uppercase_entropy + match.l33t_entropy
end

#digits_entropy(match) ⇒ Object 



46
47
48
 
# File 'lib/zxcvbn/entropy.rb', line 46

def digits_entropy(match)
  lg(10 ** match.token.length)
end

#extra_l33t_entropy(match) ⇒ Object 



99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/zxcvbn/entropy.rb', line 99

def extra_l33t_entropy(match)
  word = match.token
  return 0 unless match.l33t
  possibilities = 0
  match.sub.each do |subbed, unsubbed|
    num_subbed = word.chars.count{|c| c == subbed}
    num_unsubbed = word.chars.count{|c| c == unsubbed}
    (0..min(num_subbed, num_unsubbed)).each do |i|
      possibilities += nCk(num_subbed + num_unsubbed, i)
    end
  end
  entropy = lg(possibilities)
  entropy == 0 ? 1 : entropy
end

#extra_uppercase_entropy(match) ⇒ Object 



85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/zxcvbn/entropy.rb', line 85

def extra_uppercase_entropy(match)
  word = match.token
  [START_UPPER, END_UPPER, ALL_UPPER].each do |regex|
    return 1 if word.match(regex)
  end
  num_upper = word.chars.count{|c| c.match(/[A-Z]/) }
  num_lower = word.chars.count{|c| c.match(/[a-z]/) }
  possibilities = 0
  (0..min(num_upper, num_lower)).each do |i|
    possibilities += nCk(num_upper + num_lower, i)
  end
  lg(possibilities)
end

#repeat_entropy(match) ⇒ Object 



26
27
28
29
 
# File 'lib/zxcvbn/entropy.rb', line 26

def repeat_entropy(match)
  cardinality = bruteforce_cardinality match.token
  lg(cardinality * match.token.length)
end

#sequence_entropy(match) ⇒ Object 



31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/zxcvbn/entropy.rb', line 31

def sequence_entropy(match)
  first_char = match.token[0]
  base_entropy = if ['a', '1'].include?(first_char)
    1
  elsif first_char.match(/\d/)
    lg(10)
  elsif first_char.match(/[a-z]/)
    lg(26)
  else
    lg(26) + 1
  end
  base_entropy += 1 unless match.ascending
  base_entropy + lg(match.token.length)
end

#spatial_entropy(match) ⇒ Object 



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
 
# File 'lib/zxcvbn/entropy.rb', line 114

def spatial_entropy(match)
  if %w|qwerty dvorak|.include? match.graph
    starting_positions = starting_positions_for_graph('qwerty')
    average_degree     = average_degree_for_graph('qwerty')
  else
    starting_positions = starting_positions_for_graph('keypad')
    average_degree     = average_degree_for_graph('keypad')
  end

  possibilities = 0
  token_length  = match.token.length
  turns         = match.turns

  # estimate the ngpumber of possible patterns w/ token length or less with number of turns or less.
  (2..token_length).each do |i|
    possible_turns = [turns, i -1].min
    (1..possible_turns).each do |j|
      possibilities += nCk(i - 1, j - 1) * starting_positions * average_degree ** j
    end
  end
      
  entropy = lg possibilities
  # add extra entropy for shifted keys. (% instead of 5, A instead of a.)
  # math is similar to extra entropy from uppercase letters in dictionary matches.
  
  if match.shifted_count
    shiffted_count  = match.shifted_count
    unshifted_count = match.token.length - match.shifted_count
    possibilities   = 0
    
    (0..[shiffted_count, unshifted_count].min).each do |i|
      possibilities += nCk(shiffted_count + unshifted_count, i)
    end
    entropy += lg possibilities
  end
  entropy
end

#year_entropy(match) ⇒ Object 



54
55
56
 
# File 'lib/zxcvbn/entropy.rb', line 54

def year_entropy(match)
  lg(NUM_YEARS)
end