Class: Zxcvbn::Scorer Private

Inherits:
Object
  • Object
show all
Includes:
CrackTime, Guesses
Defined in:
lib/zxcvbn/scorer.rb,
sig/zxcvbn/scorer.rbs

Overview

This class is part of a private API. You should avoid using this class if possible, as it may be removed or be changed in the future.

Finds the match sequence that minimises the total number of guesses required to crack a password, using dynamic programming.

Constant Summary

Constants included from CrackTime

CrackTime::ATTACK_SCENARIOS

Constants included from Guesses

Guesses::ALL_LOWER, Guesses::ALL_UPPER, Guesses::BRUTEFORCE_CARDINALITY, Guesses::END_UPPER, Guesses::MIN_GUESSES_BEFORE_GROWING_SEQUENCE, Guesses::MIN_SUBMATCH_GUESSES_MULTI_CHAR, Guesses::MIN_SUBMATCH_GUESSES_SINGLE_CHAR, Guesses::MIN_YEAR_SPACE, Guesses::START_UPPER

Instance Attribute Summary collapse

Attributes included from Guesses

#reference_year

Instance Method Summary collapse

Methods included from CrackTime

#display_time, #estimate_attack_times, #guesses_to_score

Methods included from Guesses

#bruteforce_guesses, #date_guesses, #dictionary_guesses, #digits_guesses, #estimate_guesses, #l33t_variations, #sequence_guesses, #spatial_guesses, #uppercase_variations, #year_guesses

Methods included from Math

#average_degree_for_graph, #nCk, #starting_positions_for_graph

Constructor Details

#initialize(data, omnimatch, reference_year) ⇒ Scorer

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns a new instance of Scorer.

Parameters:

  • data (Data) —

    the loaded frequency list and graph data

  • omnimatch (Omnimatch) —

    shared omnimatch instance

  • reference_year (Integer) —

    year used for date/year guess calculations



36
37
38
39
40
41
 
# File 'lib/zxcvbn/scorer.rb', line 36

def initialize(data, omnimatch, reference_year)
  @data = data
  @omnimatch = omnimatch
  @reference_year = reference_year
  @repeat_cache = {}
end

Instance Attribute Details

#data ⇒ Data (readonly)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns:



43
44
45
 
# File 'lib/zxcvbn/scorer.rb', line 43

def data
  @data
end

Instance Method Details

#most_guessable_match_sequence(password, matches, exclude_additive: false) ⇒ Score

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Find the match sequence that minimises total guesses for a password.

Uses a DP over positions in the password. At each position k and sequence length l, the total cost is:

factorial(l) * product_of_guesses + MIN_GUESSES^(l-1)

The additive penalty discourages padding attacks where an adversary splits a password into many low-guesses submatches.

Parameters:

  • password (String) —

    the password to analyse

  • matches (Array<MatchBuilder>) —

    candidate matches from the matchers

  • exclude_additive (Boolean) (defaults to: false) —

    omit the sequence-length penalty (used when recursively analysing repeat base tokens)

  • exclude_additive: (Boolean) (defaults to: false)

Returns:

  • (Score) —

    the optimal score with match sequence and guess count



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

def most_guessable_match_sequence(password, matches, exclude_additive: false)
  n = password.length

  return build_score(password, [], 1.0) if n.zero?

  # Index matches by their last character (j). matches_by_j is sized to the
  # password, so this relies on every match satisfying 0 <= m.j < n (and
  # 0 <= m.i <= m.j) — match indices must be positions in `password`.
  # Matchers uphold this by matching against a lowercased view that keeps the
  # original character length; see CaseHelpers.downcase_preserving_length. A
  # match with j >= n reads a nil slot below and raises NoMethodError, so any
  # new matcher must preserve this invariant.
  matches_by_j = Array.new(n) { [] }
  matches.each { |m| matches_by_j[m.j] << m }
  matches_by_j.each { |arr| arr.sort_by!(&:i) }

  # m[k][l]       = best match for a sequence of l matches ending at position k
  # pi_float[k][l] = cumulative guess product for those l matches as Float (avoids Bignum
  #                  integer multiplication; each step is Integer × Float → Float)
  # g[k][l]        = total guesses (FACTORIAL[l] * pi_float + penalty) as Float
  # g_log10[k][l]  = log10(g[k][l]), used for dominance comparisons (small Float vs Float)
  m        = Array.new(n) { {} }
  pi_float = Array.new(n) { {} }
  g        = Array.new(n) { {} }
  g_log10  = Array.new(n) { {} }

  update = lambda do |match, l|
    j       = match.j
    est     = estimate_guesses(match, password)
    pi_prev = l > 1 ? pi_float[match.i - 1][l - 1] : 1.0
    candidate = FACTORIAL[l] * est * pi_prev
    candidate += MIN_GUESSES_POW[l - 1] unless exclude_additive
    candidate_log10 = ::Math.log10(candidate)
    # only improve if no sequence of length <= l ending at j already beats candidate
    return if g_log10[j].any? { |u, a| u <= l && a <= candidate_log10 }

    g[j][l]         = candidate
    g_log10[j][l]   = candidate_log10
    m[j][l]         = match
    pi_float[j][l]  = est * pi_prev
  end

  make_bruteforce = lambda do |i, j|
    MatchBuilder.new(pattern: 'bruteforce', i:, j:)
  end

  (0...n).each do |k|
    matches_by_j[k].each do |match|
      if match.i.positive?
        m[match.i - 1].each_key { |l| update.call(match, l + 1) }
      else
        update.call(match, 1)
      end
    end

    # try bruteforce segments ending at k
    update.call(make_bruteforce.call(0, k), 1)
    (1..k).each do |t|
      bf = make_bruteforce.call(t, k)
      m[t - 1].each do |l, prev_match|
        update.call(bf, l + 1) unless prev_match.pattern == 'bruteforce'
      end
    end
  end

  # find sequence length with minimum guesses at position n-1
  optimal_l = g_log10[n - 1].min_by { |_, v| v }&.first
  total_guesses = optimal_l ? g[n - 1][optimal_l] : 1

  # backtrack to reconstruct sequence
  sequence = []
  k = n - 1
  l = optimal_l
  while k >= 0
    match = m[k][l]
    match.token ||= password.slice(match.i, match.j - match.i + 1)
    sequence.unshift(match.build)
    k = match.i - 1
    l -= 1
  end

  build_score(password, sequence, total_guesses)
end

#repeat_guesses(match) ⇒ Numeric

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Compute guesses for a repeat match by recursively scoring the base token.

Parameters:

  • match (MatchBuilder) —

    a repeat match with base_token set

Returns:

  • (Numeric) —

    base_guesses * repeat_count



147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/zxcvbn/scorer.rb', line 147

def repeat_guesses(match)
  if match.base_guesses.nil?
    # The same base_token can appear in multiple distinct match objects when
    # a repeated token occurs at several positions in the password. Cache by
    # string so each unique base_token is scored at most once per scoring run.
    match.base_guesses = @repeat_cache[match.base_token] ||= begin
      base_matches = @omnimatch.matches(match.base_token, reference_year: @reference_year)
      most_guessable_match_sequence(match.base_token, base_matches).guesses
    end
  end
  match.base_guesses * match.repeat_count
end