zxcvbn/src/scoring.coffee

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

BRUTEFORCE_CARDINALITY = 10
MIN_GUESSES_BEFORE_GROWING_SEQUENCE = 10000
MIN_SUBMATCH_GUESSES_SINGLE_CHAR = 10
MIN_SUBMATCH_GUESSES_MULTI_CHAR = 50

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

  log10: (n) -> Math.log(n) / Math.log(10) # IE doesn't support Math.log10 :(
  log2:  (n) -> Math.log(n) / Math.log(2)

  factorial: (n) ->
    # unoptimized, called only on small n
    return 1 if n < 2
    f = 1
    f *= i for i in [2..n]
    f

  # ------------------------------------------------------------------------------
  # search --- most guessable match sequence -------------------------------------
  # ------------------------------------------------------------------------------
  #
  # takes a sequence of overlapping matches, returns the non-overlapping sequence with
  # minimum guesses. O(nml) dp alg for length-n password with m candidate matches
  # and optimal length-l sequence.
  #
  # the optimal "minimum guesses" sublist is here defined to be the sublist that
  # minimizes:
  #
  #    l! * Product(m.guesses for m in sequence) + D^(l - 1)
  #
  # where l is the length of the sequence.
  #
  # the factorial term is the number of ways to order l patterns.
  #
  # the D^(l-1) term is another length penalty, roughly capturing the idea that an
  # attacker will try lower-length sequences first before trying length-l sequences.
  #
  # for example, consider a sequence that is date-repeat-dictionary.
  #  - an attacker would need to try other date-repeat-dictionary combinations,
  #    hence the product term.
  #  - an attacker would need to try repeat-date-dictionary, dictionary-repeat-date,
  #    ..., hence the factorial term.
  #  - an attacker would also likely try length-1 (dictionary) and length-2 (dictionary-date)
  #    sequences before length-3. assuming at minimum D guesses per pattern type,
  #    D^(l-1) approximates Sum(D^i for i in [1..l-1]
  #
  # ------------------------------------------------------------------------------

  most_guessable_match_sequence: (password, matches, _exclude_additive=false) ->

    # at [k][l], the product of guesses of the optimal sequence of length-l
    # covering password[0..k].
    optimal_product = []

    # at [k][l], the final match (match.j == k) in said optimal sequence of length l.
    backpointers = []

    max_l = 0        # max-length sequence ever recorded
    optimal_l = null # length of current optimal sequence

    make_bruteforce_match = (i, j) =>
      match =
        pattern: 'bruteforce'
        token: password[i..j]
        i: i
        j: j
      match

    score = (guess_product, sequence_length) =>
      result = @factorial(sequence_length) * guess_product
      unless _exclude_additive
        result += Math.pow MIN_GUESSES_BEFORE_GROWING_SEQUENCE, sequence_length - 1
      result

    for k in [0...password.length]
      backpointers[k] = []
      optimal_product[k] = []
      optimal_score = Infinity
      for prev_l in [0..max_l]
        # for each new k, starting scenario to try to beat: bruteforce matches
        # involving the lowest-possible l. three cases:
        #
        # 1. all-bruteforce match (for length-1 sequences.)
        # 2. extending a previous bruteforce match
        #    (possible when optimal[k-1][l] ends in bf.)
        # 3. starting a new single-char bruteforce match
        #    (possible when optimal[k-1][l] exists but does not end in bf.)
        #
        # otherwise: there is no bruteforce starting scenario that might be better
        # than already-discovered lower-l sequences.
        consider_bruteforce = true
        bf_j = k
        if prev_l == 0
          bf_i = 0
          new_l = 1
        else if backpointers[k-1]?[prev_l]?.pattern == 'bruteforce'
          bf_i = backpointers[k-1][prev_l].i
          new_l = prev_l
        else if backpointers[k-1]?[prev_l]?
          bf_i = k
          new_l = prev_l + 1
        else
          consider_bruteforce = false

        if consider_bruteforce
          bf_match = make_bruteforce_match bf_i, bf_j
          prev_j = k - bf_match.token.length # end of preceeding match
          candidate_product = @estimate_guesses bf_match, password
          candidate_product *= optimal_product[prev_j][new_l - 1] if new_l > 1
          candidate_score = score candidate_product, new_l
          if candidate_score < optimal_score
            optimal_score = candidate_score
            optimal_product[k][new_l] = candidate_product
            optimal_l = new_l
            max_l = Math.max max_l, new_l
            backpointers[k][new_l] = bf_match

        # now try beating those bruteforce starting scenarios.
        # for each match m ending at k, see if forming a (prev_l + 1) sequence
        # ending at m is better than the current optimum.
        for match in matches when match.j == k
          [i, j] = [match.i, match.j]
          if prev_l == 0
            # if forming a len-1 sequence [match], match.i must fully cover [0..k]
            continue unless i == 0
          else
            # it's only possible to form a new potentially-optimal sequence ending at
            # match when there's an optimal length-prev_l sequence ending at match.i-1.
            continue unless optimal_product[i-1]?[prev_l]?
          candidate_product = @estimate_guesses match, password
          candidate_product *= optimal_product[i-1][prev_l] if prev_l > 0
          candidate_score = score candidate_product, prev_l + 1
          if candidate_score < optimal_score
            optimal_score = candidate_score
            optimal_product[k][prev_l+1] = candidate_product
            optimal_l = prev_l + 1
            max_l = Math.max max_l, prev_l+1
            backpointers[k][prev_l+1] = match

    # walk backwards and decode the optimal sequence
    match_sequence = []
    l = optimal_l
    k = password.length - 1
    while k >= 0
      match = backpointers[k][l]
      match_sequence.push match
      k = match.i - 1
      l -= 1
    match_sequence.reverse()

    # corner: empty password
    if password.length == 0
      guesses = 1
    else
      guesses = optimal_score

    # final result object
    password: password
    guesses: guesses
    guesses_log10: @log10 guesses
    sequence: match_sequence

  # ------------------------------------------------------------------------------
  # guess estimation -- one function per match pattern ---------------------------
  # ------------------------------------------------------------------------------

  estimate_guesses: (match, password) ->
    return match.guesses if match.guesses? # a match's guess estimate doesn't change. cache it.
    min_guesses = 1
    if match.token.length < password.length
      min_guesses = if match.token.length == 1
        MIN_SUBMATCH_GUESSES_SINGLE_CHAR
      else
        MIN_SUBMATCH_GUESSES_MULTI_CHAR
    estimation_functions =
      bruteforce: @bruteforce_guesses
      dictionary: @dictionary_guesses
      spatial:    @spatial_guesses
      repeat:     @repeat_guesses
      sequence:   @sequence_guesses
      regex:      @regex_guesses
      date:       @date_guesses
    guesses = estimation_functions[match.pattern].call this, match
    match.guesses = Math.max guesses, min_guesses
    match.guesses_log10 = @log10 match.guesses
    match.guesses

  bruteforce_guesses: (match) ->
    guesses = Math.pow BRUTEFORCE_CARDINALITY, match.token.length
    # small detail: make bruteforce matches at minimum one guess bigger than smallest allowed
    # submatch guesses, such that non-bruteforce submatches over the same [i..j] take precidence.
    min_guesses = if match.token.length == 1
      MIN_SUBMATCH_GUESSES_SINGLE_CHAR + 1
    else
      MIN_SUBMATCH_GUESSES_MULTI_CHAR + 1
    Math.max guesses, min_guesses

  repeat_guesses: (match) ->
    match.base_guesses * match.repeat_count

  sequence_guesses: (match) ->
    first_chr = match.token.charAt(0)
    # lower guesses for obvious starting points
    if first_chr in ['a', 'A', 'z', 'Z', '0', '1', '9']
      base_guesses = 4
    else
      if first_chr.match /\d/
        base_guesses = 10 # digits
      else
        # could give a higher base for uppercase,
        # assigning 26 to both upper and lower sequences is more conservative.
        base_guesses = 26
    if not match.ascending
      # need to try a descending sequence in addition to every ascending sequence ->
      # 2x guesses
      base_guesses *= 2
    base_guesses * match.token.length

  MIN_YEAR_SPACE: 20
  REFERENCE_YEAR: 2000
  regex_guesses: (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
      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
        year_space

  date_guesses: (match) ->
    # base guesses: (year distance from REFERENCE_YEAR) * num_days * num_years
    year_space = Math.max(Math.abs(match.year - @REFERENCE_YEAR), @MIN_YEAR_SPACE)
    guesses = year_space * 31 * 12
    # double for four-digit years
    guesses *= 2 if match.has_full_year
    # add factor of 4 for separator selection (one of ~4 choices)
    guesses *= 4 if match.separator
    guesses

  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_guesses: (match) ->
    if match.graph in ['qwerty', 'dvorak']
      s = @KEYBOARD_STARTING_POSITIONS
      d = @KEYBOARD_AVERAGE_DEGREE
    else
      s = @KEYPAD_STARTING_POSITIONS
      d = @KEYPAD_AVERAGE_DEGREE
    guesses = 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]
        guesses += @nCk(i - 1, j - 1) * s * Math.pow(d, j)
    # add extra guesses for shifted keys. (% instead of 5, A instead of a.)
    # math is similar to extra guesses of l33t substitutions in dictionary matches.
    if match.shifted_count
      S = match.shifted_count
      U = match.token.length - match.shifted_count # unshifted count
      if S == 0 or U == 0
        guesses *= 2
      else
        shifted_variations = 0
        shifted_variations += @nCk(S + U, i) for i in [1..Math.min(S, U)]
        guesses *= shifted_variations
    guesses

  dictionary_guesses: (match) ->
    match.base_guesses = match.rank # keep these as properties for display purposes
    match.uppercase_variations = @uppercase_variations match
    match.l33t_variations = @l33t_variations match
    reversed_variations = match.reversed and 2 or 1
    match.base_guesses * match.uppercase_variations * match.l33t_variations * reversed_variations

  START_UPPER: /^[A-Z][^A-Z]+$/
  END_UPPER: /^[^A-Z]+[A-Z]$/
  ALL_UPPER: /^[^a-z]+$/
  ALL_LOWER: /^[^A-Z]+$/

  uppercase_variations: (match) ->
    word = match.token
    return 1 if word.match @ALL_LOWER
    # a capitalized word is the most common capitalization scheme,
    # so it only doubles the search space (uncapitalized + capitalized).
    # allcaps and end-capitalized are common enough too, underestimate as 2x factor to be safe.
    for regex in [@START_UPPER, @END_UPPER, @ALL_UPPER]
      return 2 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
    variations = 0
    variations += @nCk(U + L, i) for i in [1..Math.min(U, L)]
    variations

  l33t_variations: (match) ->
    return 1 if not match.l33t
    variations = 1
    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.)
        variations *= 2
      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]
        variations *= possibilities
    variations

  # utilities --------------------------------------------------------------------

module.exports = scoring