zxcvbn/lib/scoring.js

// Generated by CoffeeScript 1.10.0
var BRUTEFORCE_CARDINALITY, MIN_GUESSES_BEFORE_GROWING_SEQUENCE, MIN_SUBMATCH_GUESSES_MULTI_CHAR, MIN_SUBMATCH_GUESSES_SINGLE_CHAR, adjacency_graphs, calc_average_degree, k, scoring, v;

adjacency_graphs = require('./adjacency_graphs');

calc_average_degree = function(graph) {
  var average, k, key, n, neighbors, v;
  average = 0;
  for (key in graph) {
    neighbors = graph[key];
    average += ((function() {
      var len, m, results;
      results = [];
      for (m = 0, len = neighbors.length; m < len; m++) {
        n = neighbors[m];
        if (n) {
          results.push(n);
        }
      }
      return results;
    })()).length;
  }
  average /= ((function() {
    var results;
    results = [];
    for (k in graph) {
      v = graph[k];
      results.push(k);
    }
    return results;
  })()).length;
  return average;
};

BRUTEFORCE_CARDINALITY = 10;

MIN_GUESSES_BEFORE_GROWING_SEQUENCE = 10000;

MIN_SUBMATCH_GUESSES_SINGLE_CHAR = 10;

MIN_SUBMATCH_GUESSES_MULTI_CHAR = 50;

scoring = {
  nCk: function(n, k) {
    var d, m, r, ref;
    if (k > n) {
      return 0;
    }
    if (k === 0) {
      return 1;
    }
    r = 1;
    for (d = m = 1, ref = k; 1 <= ref ? m <= ref : m >= ref; d = 1 <= ref ? ++m : --m) {
      r *= n;
      r /= d;
      n -= 1;
    }
    return r;
  },
  log10: function(n) {
    return Math.log(n) / Math.log(10);
  },
  log2: function(n) {
    return Math.log(n) / Math.log(2);
  },
  factorial: function(n) {
    var f, i, m, ref;
    if (n < 2) {
      return 1;
    }
    f = 1;
    for (i = m = 2, ref = n; 2 <= ref ? m <= ref : m >= ref; i = 2 <= ref ? ++m : --m) {
      f *= i;
    }
    return f;
  },
  most_guessable_match_sequence: function(password, matches, _exclude_additive) {
    var backpointers, bf_i, bf_j, bf_match, candidate_product, candidate_score, consider_bruteforce, guesses, i, j, k, l, len, m, make_bruteforce_match, match, match_sequence, max_l, new_l, o, optimal_l, optimal_product, optimal_score, prev_j, prev_l, q, ref, ref1, ref2, ref3, ref4, ref5, ref6, score;
    if (_exclude_additive == null) {
      _exclude_additive = false;
    }
    optimal_product = [];
    backpointers = [];
    max_l = 0;
    optimal_l = null;
    make_bruteforce_match = (function(_this) {
      return function(i, j) {
        var match;
        match = {
          pattern: 'bruteforce',
          token: password.slice(i, +j + 1 || 9e9),
          i: i,
          j: j
        };
        return match;
      };
    })(this);
    score = (function(_this) {
      return function(guess_product, sequence_length) {
        var result;
        result = _this.factorial(sequence_length) * guess_product;
        if (!_exclude_additive) {
          result += Math.pow(MIN_GUESSES_BEFORE_GROWING_SEQUENCE, sequence_length - 1);
        }
        return result;
      };
    })(this);
    for (k = m = 0, ref = password.length; 0 <= ref ? m < ref : m > ref; k = 0 <= ref ? ++m : --m) {
      backpointers[k] = [];
      optimal_product[k] = [];
      optimal_score = Infinity;
      for (prev_l = o = 0, ref1 = max_l; 0 <= ref1 ? o <= ref1 : o >= ref1; prev_l = 0 <= ref1 ? ++o : --o) {
        consider_bruteforce = true;
        bf_j = k;
        if (prev_l === 0) {
          bf_i = 0;
          new_l = 1;
        } else if (((ref2 = backpointers[k - 1]) != null ? (ref3 = ref2[prev_l]) != null ? ref3.pattern : void 0 : void 0) === 'bruteforce') {
          bf_i = backpointers[k - 1][prev_l].i;
          new_l = prev_l;
        } else if (((ref4 = backpointers[k - 1]) != null ? ref4[prev_l] : void 0) != null) {
          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;
          candidate_product = this.estimate_guesses(bf_match, password);
          if (new_l > 1) {
            candidate_product *= optimal_product[prev_j][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;
          }
        }
        for (q = 0, len = matches.length; q < len; q++) {
          match = matches[q];
          if (!(match.j === k)) {
            continue;
          }
          ref5 = [match.i, match.j], i = ref5[0], j = ref5[1];
          if (prev_l === 0) {
            if (i !== 0) {
              continue;
            }
          } else {
            if (((ref6 = optimal_product[i - 1]) != null ? ref6[prev_l] : void 0) == null) {
              continue;
            }
          }
          candidate_product = this.estimate_guesses(match, password);
          if (prev_l > 0) {
            candidate_product *= optimal_product[i - 1][prev_l];
          }
          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;
          }
        }
      }
    }
    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();
    if (password.length === 0) {
      guesses = 1;
    } else {
      guesses = optimal_score;
    }
    return {
      password: password,
      guesses: guesses,
      guesses_log10: this.log10(guesses),
      sequence: match_sequence
    };
  },
  estimate_guesses: function(match, password) {
    var estimation_functions, guesses, min_guesses;
    if (match.guesses != null) {
      return match.guesses;
    }
    min_guesses = 1;
    if (match.token.length < password.length) {
      min_guesses = match.token.length === 1 ? MIN_SUBMATCH_GUESSES_SINGLE_CHAR : MIN_SUBMATCH_GUESSES_MULTI_CHAR;
    }
    estimation_functions = {
      bruteforce: this.bruteforce_guesses,
      dictionary: this.dictionary_guesses,
      spatial: this.spatial_guesses,
      repeat: this.repeat_guesses,
      sequence: this.sequence_guesses,
      regex: this.regex_guesses,
      date: this.date_guesses
    };
    guesses = estimation_functions[match.pattern].call(this, match);
    match.guesses = Math.max(guesses, min_guesses);
    match.guesses_log10 = this.log10(match.guesses);
    return match.guesses;
  },
  bruteforce_guesses: function(match) {
    var guesses, min_guesses;
    guesses = Math.pow(BRUTEFORCE_CARDINALITY, match.token.length);
    min_guesses = match.token.length === 1 ? MIN_SUBMATCH_GUESSES_SINGLE_CHAR + 1 : MIN_SUBMATCH_GUESSES_MULTI_CHAR + 1;
    return Math.max(guesses, min_guesses);
  },
  repeat_guesses: function(match) {
    return match.base_guesses * match.repeat_count;
  },
  sequence_guesses: function(match) {
    var base_guesses, first_chr;
    first_chr = match.token.charAt(0);
    if (first_chr === 'a' || first_chr === 'A' || first_chr === 'z' || first_chr === 'Z' || first_chr === '0' || first_chr === '1' || first_chr === '9') {
      base_guesses = 4;
    } else {
      if (first_chr.match(/\d/)) {
        base_guesses = 10;
      } else {
        base_guesses = 26;
      }
    }
    if (!match.ascending) {
      base_guesses *= 2;
    }
    return base_guesses * match.token.length;
  },
  MIN_YEAR_SPACE: 20,
  REFERENCE_YEAR: 2000,
  regex_guesses: function(match) {
    var char_class_bases, year_space;
    char_class_bases = {
      alpha_lower: 26,
      alpha_upper: 26,
      alpha: 52,
      alphanumeric: 62,
      digits: 10,
      symbols: 33
    };
    if (match.regex_name in char_class_bases) {
      return Math.pow(char_class_bases[match.regex_name], match.token.length);
    } else {
      switch (match.regex_name) {
        case 'recent_year':
          year_space = Math.abs(parseInt(match.regex_match[0]) - this.REFERENCE_YEAR);
          year_space = Math.max(year_space, this.MIN_YEAR_SPACE);
          return year_space;
      }
    }
  },
  date_guesses: function(match) {
    var guesses, year_space;
    year_space = Math.max(Math.abs(match.year - this.REFERENCE_YEAR), this.MIN_YEAR_SPACE);
    guesses = year_space * 31 * 12;
    if (match.has_full_year) {
      guesses *= 2;
    }
    if (match.separator) {
      guesses *= 4;
    }
    return guesses;
  },
  KEYBOARD_AVERAGE_DEGREE: calc_average_degree(adjacency_graphs.qwerty),
  KEYPAD_AVERAGE_DEGREE: calc_average_degree(adjacency_graphs.keypad),
  KEYBOARD_STARTING_POSITIONS: ((function() {
    var ref, results;
    ref = adjacency_graphs.qwerty;
    results = [];
    for (k in ref) {
      v = ref[k];
      results.push(k);
    }
    return results;
  })()).length,
  KEYPAD_STARTING_POSITIONS: ((function() {
    var ref, results;
    ref = adjacency_graphs.keypad;
    results = [];
    for (k in ref) {
      v = ref[k];
      results.push(k);
    }
    return results;
  })()).length,
  spatial_guesses: function(match) {
    var L, S, U, d, guesses, i, j, m, o, possible_turns, q, ref, ref1, ref2, ref3, s, shifted_variations, t;
    if ((ref = match.graph) === 'qwerty' || ref === 'dvorak') {
      s = this.KEYBOARD_STARTING_POSITIONS;
      d = this.KEYBOARD_AVERAGE_DEGREE;
    } else {
      s = this.KEYPAD_STARTING_POSITIONS;
      d = this.KEYPAD_AVERAGE_DEGREE;
    }
    guesses = 0;
    L = match.token.length;
    t = match.turns;
    for (i = m = 2, ref1 = L; 2 <= ref1 ? m <= ref1 : m >= ref1; i = 2 <= ref1 ? ++m : --m) {
      possible_turns = Math.min(t, i - 1);
      for (j = o = 1, ref2 = possible_turns; 1 <= ref2 ? o <= ref2 : o >= ref2; j = 1 <= ref2 ? ++o : --o) {
        guesses += this.nCk(i - 1, j - 1) * s * Math.pow(d, j);
      }
    }
    if (match.shifted_count) {
      S = match.shifted_count;
      U = match.token.length - match.shifted_count;
      if (S === 0 || U === 0) {
        guesses *= 2;
      } else {
        shifted_variations = 0;
        for (i = q = 1, ref3 = Math.min(S, U); 1 <= ref3 ? q <= ref3 : q >= ref3; i = 1 <= ref3 ? ++q : --q) {
          shifted_variations += this.nCk(S + U, i);
        }
        guesses *= shifted_variations;
      }
    }
    return guesses;
  },
  dictionary_guesses: function(match) {
    var reversed_variations;
    match.base_guesses = match.rank;
    match.uppercase_variations = this.uppercase_variations(match);
    match.l33t_variations = this.l33t_variations(match);
    reversed_variations = match.reversed && 2 || 1;
    return 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: function(match) {
    var L, U, chr, i, len, m, o, ref, ref1, regex, variations, word;
    word = match.token;
    if (word.match(this.ALL_LOWER)) {
      return 1;
    }
    ref = [this.START_UPPER, this.END_UPPER, this.ALL_UPPER];
    for (m = 0, len = ref.length; m < len; m++) {
      regex = ref[m];
      if (word.match(regex)) {
        return 2;
      }
    }
    U = ((function() {
      var len1, o, ref1, results;
      ref1 = word.split('');
      results = [];
      for (o = 0, len1 = ref1.length; o < len1; o++) {
        chr = ref1[o];
        if (chr.match(/[A-Z]/)) {
          results.push(chr);
        }
      }
      return results;
    })()).length;
    L = ((function() {
      var len1, o, ref1, results;
      ref1 = word.split('');
      results = [];
      for (o = 0, len1 = ref1.length; o < len1; o++) {
        chr = ref1[o];
        if (chr.match(/[a-z]/)) {
          results.push(chr);
        }
      }
      return results;
    })()).length;
    variations = 0;
    for (i = o = 1, ref1 = Math.min(U, L); 1 <= ref1 ? o <= ref1 : o >= ref1; i = 1 <= ref1 ? ++o : --o) {
      variations += this.nCk(U + L, i);
    }
    return variations;
  },
  l33t_variations: function(match) {
    var S, U, chr, chrs, i, m, p, possibilities, ref, ref1, subbed, unsubbed, variations;
    if (!match.l33t) {
      return 1;
    }
    variations = 1;
    ref = match.sub;
    for (subbed in ref) {
      unsubbed = ref[subbed];
      chrs = match.token.toLowerCase().split('');
      S = ((function() {
        var len, m, results;
        results = [];
        for (m = 0, len = chrs.length; m < len; m++) {
          chr = chrs[m];
          if (chr === subbed) {
            results.push(chr);
          }
        }
        return results;
      })()).length;
      U = ((function() {
        var len, m, results;
        results = [];
        for (m = 0, len = chrs.length; m < len; m++) {
          chr = chrs[m];
          if (chr === unsubbed) {
            results.push(chr);
          }
        }
        return results;
      })()).length;
      if (S === 0 || U === 0) {
        variations *= 2;
      } else {
        p = Math.min(U, S);
        possibilities = 0;
        for (i = m = 1, ref1 = p; 1 <= ref1 ? m <= ref1 : m >= ref1; i = 1 <= ref1 ? ++m : --m) {
          possibilities += this.nCk(U + S, i);
        }
        variations *= possibilities;
      }
    }
    return variations;
  }
};

module.exports = scoring;

//# sourceMappingURL=scoring.js.map