chromium/third_party/zxcvbn-cpp/native-src/zxcvbn/scoring.cpp

#include <zxcvbn/scoring.hpp>

#include <zxcvbn/adjacency_graphs.hpp>
#include <zxcvbn/util.hpp>

#include <numeric>
#include <string>
#include <vector>

#include <cmath>

#include "base/no_destructor.h"

namespace std {

hash<std::pair<T, U>>;

}

namespace zxcvbn {

const auto BRUTEFORCE_CARDINALITY = …;
const auto MIN_GUESSES_BEFORE_GROWING_SEQUENCE = …;
const auto MIN_SUBMATCH_GUESSES_SINGLE_CHAR = …;
const auto MIN_SUBMATCH_GUESSES_MULTI_CHAR = …;

const std::regex& START_UPPER() { … }

const std::regex& END_UPPER() { … }

const std::regex& ALL_UPPER() { … }

const std::regex& ALL_LOWER() { … }

template<class Tret, class Tin>
Tret factorial(Tin n) { … }

template<class M, class K, class V>
static
void insert_or_assign(M & m, const K & k, V && v) { … }

static
std::size_t token_len(const Match & m) __attribute__((pure));

static
std::size_t token_len(const Match & m) { … }

// ------------------------------------------------------------------------------
// search --- most guessable match sequence -------------------------------------
// ------------------------------------------------------------------------------
//
// takes a sequence of overlapping matches, returns the non-overlapping sequence with
// minimum guesses. the following is a O(l_max * (n + m)) dynamic programming algorithm
// for a length-n password with m candidate matches. l_max is the maximum optimal
// sequence length spanning each prefix of the password. In practice it rarely exceeds 5 and the
// search terminates rapidly.
//
// the optimal "minimum guesses" sequence is here defined to be the sequence that
// minimizes the following function:
//
//    g = 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]
//
// ------------------------------------------------------------------------------

ScoringResult most_guessable_match_sequence(const std::string & password,
                                            std::vector<Match> & matches,
                                            bool exclude_additive) { … }

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

guesses_t estimate_guesses(Match & match, const std::string & password) { … }

guesses_t unknown_guesses(const Match & match) { … }

guesses_t bruteforce_guesses(const Match & match) { … }

guesses_t repeat_guesses(const Match & match) { … }

guesses_t sequence_guesses(const Match & match) { … }

guesses_t regex_guesses(const Match & match) { … }

guesses_t date_guesses(const Match & match) { … }

guesses_t spatial_guesses(const Match & match) { … }

guesses_t dictionary_guesses(const Match & match) { … }

guesses_t uppercase_variations(const Match & match) { … }

guesses_t l33t_variations(const Match & match) { … }

}