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]+$/.freeze
END_UPPER = 
/^[^A-Z]+[A-Z]$/.freeze
ALL_UPPER = 
/^[A-Z]+$/.freeze
ALL_LOWER = 
/^[a-z]+$/.freeze

Instance Method Summary collapse

Methods included from Math

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

Instance Method Details

#calc_entropy(match) ⇒ Object 



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/zxcvbn/entropy.rb', line 8

def calc_entropy(match)
  return match.entropy unless match.entropy.nil?

  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)
    else
      0
    end
end

#date_entropy(match) ⇒ Object 



65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/zxcvbn/entropy.rb', line 65

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

  entropy += 2 if match.separator

  entropy
end

#dictionary_entropy(match) ⇒ Object 



78
79
80
81
82
83
84
 
# File 'lib/zxcvbn/entropy.rb', line 78

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 



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

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

#extra_l33t_entropy(match) ⇒ Object 



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
# File 'lib/zxcvbn/entropy.rb', line 105

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..[num_subbed, num_unsubbed].min).each do |i|
      possibilities += nCk(num_subbed + num_unsubbed, i)
    end
  end
  entropy = lg(possibilities)
  entropy.zero? ? 1 : entropy
end

#extra_uppercase_entropy(match) ⇒ Object 



91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/zxcvbn/entropy.rb', line 91

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..[num_upper, num_lower].min).each do |i|
    possibilities += nCk(num_upper + num_lower, i)
  end
  lg(possibilities)
end

#repeat_entropy(match) ⇒ Object 



32
33
34
35
 
# File 'lib/zxcvbn/entropy.rb', line 32

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

#sequence_entropy(match) ⇒ Object 



37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/zxcvbn/entropy.rb', line 37

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 



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

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 



61
62
63
 
# File 'lib/zxcvbn/entropy.rb', line 61

def year_entropy(_match)
  lg(NUM_YEARS)
end