hashbro
296 lines
8.5 KiB
PHP
296 lines
8.5 KiB
PHP
<?php
|
||
|
||
namespace App\Services;
|
||
|
||
use App\Services\Chain\Bip44;
|
||
|
||
class MnemonicDetector
|
||
{
|
||
/** @var list<int> */
|
||
public const LENGTHS = [12, 15, 18, 21, 24];
|
||
|
||
public const MIN_SUSPECTED = 8;
|
||
|
||
public const MIN_GAPPED_HITS = 9;
|
||
|
||
public const MAX_GAPS = 2;
|
||
|
||
public const MIN_CONFIRMED = 12;
|
||
|
||
public const MIN_UNIQUE = 8;
|
||
|
||
/**
|
||
* Hardware-wallet chrome that is also on the BIP39 list. Only used to
|
||
* break ties when two sliding windows both checksum.
|
||
*
|
||
* @var array<string, true>
|
||
*/
|
||
private const UI_PREFIX = [
|
||
'card' => true,
|
||
'key' => true,
|
||
'wallet' => true,
|
||
'seed' => true,
|
||
'word' => true,
|
||
'phrase' => true,
|
||
'recovery' => true,
|
||
'secret' => true,
|
||
'hardware' => true,
|
||
'device' => true,
|
||
'account' => true,
|
||
];
|
||
|
||
/** @var array<string, true>|null */
|
||
private static ?array $english = null;
|
||
|
||
/**
|
||
* @return array{candidate: string, word_count: int, score: int, language: string, confirmed: bool}|null
|
||
*/
|
||
public function detect(string $text, bool $strictGaps = false): ?array
|
||
{
|
||
$text = trim($text);
|
||
if ($text === '') {
|
||
return null;
|
||
}
|
||
|
||
$tokens = $strictGaps ? $this->noteTokens($text) : $this->englishTokens($text);
|
||
$wordlist = $this->englishSet();
|
||
$real = array_values(array_filter($tokens, fn ($word) => $word !== ''));
|
||
if (count($real) < self::MIN_SUSPECTED) {
|
||
return null;
|
||
}
|
||
|
||
$perfect = $this->perfectPhrase($tokens, $wordlist);
|
||
if ($perfect !== null) {
|
||
return $perfect;
|
||
}
|
||
if ($strictGaps) {
|
||
return null;
|
||
}
|
||
|
||
$partial = $this->suspectedWindow($tokens, $wordlist);
|
||
|
||
return $partial !== null && $this->uniqueListWords($partial['candidate']) >= self::MIN_UNIQUE
|
||
? $partial
|
||
: null;
|
||
}
|
||
|
||
public function uniqueListWords(string $candidate): int
|
||
{
|
||
$wordlist = $this->englishSet();
|
||
$uniq = [];
|
||
foreach (preg_split('/\s+/', strtolower(trim($candidate))) ?: [] as $word) {
|
||
if (isset($wordlist[$word])) {
|
||
$uniq[$word] = true;
|
||
}
|
||
}
|
||
|
||
return count($uniq);
|
||
}
|
||
|
||
/**
|
||
* @param list<string> $tokens
|
||
* @param array<string, true> $wordlist
|
||
* @return array{candidate: string, word_count: int, score: int, language: string, confirmed: bool}|null
|
||
*/
|
||
private function perfectPhrase(array $tokens, array $wordlist): ?array
|
||
{
|
||
$run = [];
|
||
$best = null;
|
||
$n = count($tokens);
|
||
for ($i = 0; $i <= $n; $i++) {
|
||
$word = $tokens[$i] ?? null;
|
||
if ($word !== null && $word !== '' && isset($wordlist[$word])) {
|
||
$run[] = $word;
|
||
|
||
continue;
|
||
}
|
||
$hit = $this->confirmedFromRun($run);
|
||
if ($hit !== null && ($best === null || $hit['word_count'] > $best['word_count'])) {
|
||
$best = $hit;
|
||
}
|
||
$run = [];
|
||
}
|
||
|
||
return $best;
|
||
}
|
||
|
||
/**
|
||
* @param list<string> $run
|
||
* @return array{candidate: string, word_count: int, score: int, language: string, confirmed: bool}|null
|
||
*/
|
||
private function confirmedFromRun(array $run): ?array
|
||
{
|
||
$n = count($run);
|
||
$fallback = null;
|
||
foreach (array_reverse(self::LENGTHS) as $len) {
|
||
if ($n < $len) {
|
||
continue;
|
||
}
|
||
$usable = [];
|
||
for ($offset = 0; $offset <= $n - $len; $offset++) {
|
||
$hit = $this->hitFromWords(array_slice($run, $offset, $len), true);
|
||
$fallback ??= $hit;
|
||
if (Bip44::isUsableMnemonic($hit['candidate'])) {
|
||
$usable[] = $hit;
|
||
}
|
||
}
|
||
if ($usable !== []) {
|
||
return $this->preferNonUiPrefix($usable);
|
||
}
|
||
}
|
||
|
||
return $fallback;
|
||
}
|
||
|
||
/**
|
||
* @param list<string> $words
|
||
* @return array{candidate: string, word_count: int, score: int, language: string, confirmed: bool}
|
||
*/
|
||
private function hitFromWords(array $words, bool $confirmed): array
|
||
{
|
||
$len = count($words);
|
||
|
||
return [
|
||
'candidate' => implode(' ', $words),
|
||
'word_count' => $len,
|
||
'score' => $len * 10,
|
||
'language' => 'en',
|
||
'confirmed' => $confirmed,
|
||
];
|
||
}
|
||
|
||
/**
|
||
* @param non-empty-list<array{candidate: string, word_count: int, score: int, language: string, confirmed: bool}> $hits
|
||
* @return array{candidate: string, word_count: int, score: int, language: string, confirmed: bool}
|
||
*/
|
||
private function preferNonUiPrefix(array $hits): array
|
||
{
|
||
foreach ($hits as $hit) {
|
||
$first = explode(' ', $hit['candidate'])[0] ?? '';
|
||
if (! isset(self::UI_PREFIX[$first])) {
|
||
return $hit;
|
||
}
|
||
}
|
||
|
||
return $hits[0];
|
||
}
|
||
|
||
/**
|
||
* @param list<string> $tokens
|
||
* @param array<string, true> $wordlist
|
||
* @return array{candidate: string, word_count: int, score: int, language: string, confirmed: bool}|null
|
||
*/
|
||
private function suspectedWindow(array $tokens, array $wordlist): ?array
|
||
{
|
||
$n = count($tokens);
|
||
$best = null;
|
||
for ($i = 0; $i < $n; $i++) {
|
||
if ($tokens[$i] === '' || ! isset($wordlist[$tokens[$i]])) {
|
||
continue;
|
||
}
|
||
$hits = 0;
|
||
$gaps = 0;
|
||
$end = $i;
|
||
for ($j = $i; $j < $n; $j++) {
|
||
$word = $tokens[$j];
|
||
if ($word !== '' && isset($wordlist[$word])) {
|
||
$hits++;
|
||
$end = $j;
|
||
|
||
continue;
|
||
}
|
||
$next = $tokens[$j + 1] ?? null;
|
||
if ($gaps < self::MAX_GAPS && $next !== null && $next !== '' && isset($wordlist[$next])) {
|
||
$gaps++;
|
||
|
||
continue;
|
||
}
|
||
break;
|
||
}
|
||
$minHits = $gaps === 0 ? self::MIN_SUSPECTED : self::MIN_GAPPED_HITS;
|
||
if ($hits < $minHits) {
|
||
continue;
|
||
}
|
||
$window = array_slice($tokens, $i, $end - $i + 1);
|
||
$score = ($hits * 10) - ($gaps * 4);
|
||
if ($best !== null && ($hits < $best['word_count'] || ($hits === $best['word_count'] && $score <= $best['score']))) {
|
||
continue;
|
||
}
|
||
$best = [
|
||
'candidate' => implode(' ', $window),
|
||
'word_count' => $hits,
|
||
'score' => $score,
|
||
'language' => 'en',
|
||
'confirmed' => false,
|
||
];
|
||
}
|
||
|
||
return $best;
|
||
}
|
||
|
||
/** @return list<string> */
|
||
private function englishTokens(string $text): array
|
||
{
|
||
preg_match_all('/[a-z]{3,8}/', strtolower($text), $m);
|
||
|
||
return $m[0] ?? [];
|
||
}
|
||
|
||
/**
|
||
* Keep list indices (1 / 1. / 1.during / 12)wrist) from breaking a phrase,
|
||
* but digits/units like 200 or 1.5 split a run so "pipe 200 cable" is not 12 words.
|
||
*
|
||
* @return list<string>
|
||
*/
|
||
private function noteTokens(string $text): array
|
||
{
|
||
$out = [];
|
||
foreach (preg_split('/\s+/u', strtolower($text)) ?: [] as $raw) {
|
||
$word = trim($raw, ".,!?;:\"'()[]");
|
||
if ($word === '') {
|
||
continue;
|
||
}
|
||
if (preg_match('/^[a-z]{3,8}$/', $word) === 1) {
|
||
$out[] = $word;
|
||
|
||
continue;
|
||
}
|
||
if (preg_match('/^\d{1,2}\.?$/', $word) === 1) {
|
||
continue;
|
||
}
|
||
if (preg_match('/^\d{1,2}[.)\]、．:：]?([a-z]{3,8})$/u', $word, $m) === 1) {
|
||
$out[] = $m[1];
|
||
|
||
continue;
|
||
}
|
||
$out[] = '';
|
||
}
|
||
|
||
return $out;
|
||
}
|
||
|
||
/** @return array<string, true> */
|
||
private function englishSet(): array
|
||
{
|
||
return self::$english ??= $this->loadSet();
|
||
}
|
||
|
||
/** @return array<string, true> */
|
||
private function loadSet(): array
|
||
{
|
||
$set = [];
|
||
$path = resource_path('bip39/english.txt');
|
||
if (! is_file($path)) {
|
||
return $set;
|
||
}
|
||
foreach (file($path, FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES) ?: [] as $line) {
|
||
$word = strtolower(trim($line));
|
||
if ($word !== '') {
|
||
$set[$word] = true;
|
||
}
|
||
}
|
||
|
||
return $set;
|
||
}
|
||
}
|