mostGuessableMatchSequence function

MostGuessableMatchSequence mostGuessableMatchSequence(String password, List<Match> matches, [ bool excludeAdditive = false ])

---

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 = sequenceLength! * Product(m.guesses for m in sequence) + D^(sequenceLength - 1)

where sequenceLength is the length of the sequence.

the factorial term is the number of ways to order sequenceLength patterns.

the D^(sequenceLength-1) term is another length penalty, roughly capturing the idea that an attacker will try lower-length sequences first before trying length-sequenceLength 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^(sequenceLength-1) approximates Sum(D^i for i in 1..sequenceLength-1

---

Implementation

MostGuessableMatchSequence mostGuessableMatchSequence(
    String password, List<Match> matches,
    [bool excludeAdditive = false]) {
  final ScoringHelper scoringHelper = ScoringHelper(
    password: password,
    excludeAdditive: excludeAdditive,
  );

  final int passwordLength = password.length;
  final List<List<Match>> matchesByCoordinateJ =
      List.generate(passwordLength, (_) => []);

  matches.forEach((match) {
    matchesByCoordinateJ[match.j].add(match);
  });
  // small detail: for deterministic output, sort each sublist by i.
  matchesByCoordinateJ.forEach((matchesForIndex) {
    matchesForIndex.sort((a, b) => a.i.compareTo(b.i));
  });

  for (int k = 0; k < passwordLength; k++) {
    matchesByCoordinateJ[k].forEach((match) {
      if (match.i > 0) {
        scoringHelper.optimal.m[match.i - 1].keys.forEach((sequenceLength) {
          scoringHelper.update(match, sequenceLength + 1);
        });
      } else {
        scoringHelper.update(match, 1);
      }
    });

    scoringHelper.bruteforceUpdate(k);
  }

  final optimalMatchSequence = scoringHelper.unwind(passwordLength);
  final optimalSequenceLength = optimalMatchSequence.length;
  // TODO validate null checks
  final double guesses = password.isEmpty
      ? 1
      : scoringHelper.optimal.g[passwordLength - 1][optimalSequenceLength]!;

  return MostGuessableMatchSequence(
    password: password,
    guesses: guesses,
    guessesLog10: log10(guesses),
    sequence: optimalMatchSequence,
  );
}