энтропия пароля из нескольких слов

[beroal]

Родилась задача по теории вероятностей, имеющая практическое значение. Есть способ выбора пароля под названием «Diceware». Используется словарь $W$, состоящий из коротких английских слов. $\#W = 6^5$. Выбирается элемент $W$ с помощью $5$-ти подбрасываний игральной кости. То есть имеем случайную величину $X$, равномерно распределённую на $W$. Пароль — это список из $n$ слов из $W$. То есть пароль выбирается с помощью случайной величины $X^n$. Есть нюанс: информационные системы требуют, чтобы пароль был строкой. Это решается преобразованием, которое вставляет между словами пробелы и конкатенирует всё. Это преобразование инъективно, поэтому энтропия пароля равна энтропии $X^n$. Энтропии случайных величин выше считаются элементарно. $\mathrm{H}(X) = 12,92481250360578\text{ бит}$, $\mathrm{H}(X^n) = n\times \mathrm{H}(X)$.

Такой метод выбора пароля имеет недостаток: длинные пароли. Их долго набирать. Некоторые информационные системы требуют пароли ограниченной длины. Конкретный случай, с которым я столкнулся: ОС Android требует, чтобы пароль к ОС имел длину максимум 16 символов, и использует этот пароль для шифрования. Как вы знаете, пароли шифрования должны иметь большую энтропию, по моим прикидкам, больше $52$ бит. Я придумал способ сократить пароль, полученный с помощью «Diceware»: выбросить часто встречающиеся буквы, а именно, гласные («aeiou») и пробелы. Задача подсчитать энтропию. Пусть случайная величина $Y$ — это результат удаления гласных из результата $X$. Энтропию $Y$ я посчитал из словаря с помощью программы на Java ниже, $\mathrm{H}(X) = 11,125381731183683\text{ бит}$. То есть при выбрасывании гласных энтропия падает не сильно, способ годный.

Используется синтаксис Java

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Map;
import java.util.Optional;
import java.util.stream.Collectors;

public class DicewareVowel {

    public static Optional<String> extractWord(String line) {
        final int i = line.indexOf('\t');
        return i == -1 ? Optional.empty() : Optional.of(line.substring(i + 1, line.length()));
    }

    public static boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    public static String deleteVowels(String s) {
        final StringBuilder s1 = new StringBuilder();
        s.chars().forEach(c -> {
            if (!isVowel((char) c)) s1.append((char) c);
        });
        return s1.toString();
    }

    /**
     * @param args element at {@code 0}: the path to a Diceware dictionary text file
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        final Map<String, Long> wordCounts = Files
                .lines(Paths.get(args[0]))
                .flatMap(line -> extractWord(line).stream())
                .collect(Collectors.groupingBy(DicewareVowel::deleteVowels, Collectors.counting()));
        final long n = wordCounts.values().stream().mapToInt(Long::intValue).sum();
        System.out.println("# of words in the dictionary: " + n);
        final long len1 = wordCounts
                .entrySet()
                .stream()
                .mapToLong(entry -> entry.getValue() * entry.getKey().length())
                .sum();
        System.out.println("expected length of a word without vowels: " + len1 / (double) n);
        final double entropy1 = wordCounts.values().stream()
                .mapToDouble(n1 -> n1 * Math.log(n1)).sum();
        final double entropyBit = (Math.log(n) - entropy1 / n) / Math.log(2);
        System.out.println("entropy of a word without vowels: " + entropyBit);
    }
}

А вот с выкидыванием пробелов проблема. Очевидно, что энтропия уменьшится, но насколько? Пусть $Y_n$ — конкатенация $n$ слов, выбранных с помощью $Y$. Как посчитать или хотя бы оценить снизу энтропию $Y_n$, я не придумал, кроме полного перебора всех результатов $Y^n$, что нереально для реальных паролей по понятным причинам.

[Dmitriy40]

beroal в сообщении #1535991 писал(а):

Это решается преобразованием, которое вставляет между словами пробелы и конкатенирует всё. Это преобразование инъективно, поэтому энтропия пароля равна энтропии $X^n$.

beroal в сообщении #1535991 писал(а):

А вот с выкидыванием пробелов проблема. Очевидно, что энтропия уменьшится, но насколько?

Мне кажется или тут противоречие? Сначала пробелы не меняют энтропию, потом вдруг меняют.

beroal в сообщении #1535991 писал(а):

Энтропию $Y$ я посчитал из словаря с помощью программы на Java ниже, $\mathrm{H}(X) = 11,125381731183683\text{ бит}$.

Вы уверены в правильности этого числа? Оно почему-то не соответствует целому числу слов. Если энтропия выше была ровно для $6^5=7776=2^{12.92481250360578}$ слов, то здесь получается $2^{11.125381731183683}=2233.95085252710245$ слов, что странно.
Кроме того, я после удаления тех же символов получил $3531$ различных слов или энтропию $H=11.786$, при средней длине слова $3.2$ символа.

Ну и уменьшение количества слов с $7776$ до $2234$ слов, более чем втрое, называть "падает не сильно" ...

С другой стороны, в $16$ символов пароля влезут в среднем $3.775$ слова (у них средняя длина $4.2388$ символа), что даст $7776^{3.775}=4.855\cdot10^{14}=2^{48.8}$, т.е. перебор $49$ битов. После удаления гласных средняя длина уменьшится, но лишь до $3.2$ символов, тогда в $16$ символов пароля влезут в среднем $5$ слов, что даст $3531^5=5.5\cdot10^{17}=2^{58.93}$, т.е. перебор $59$ битов, даже заметно больше.

-- 23.10.2021, 16:34 --

Разумеется последние оценки для всего пароля очень в среднем, чтобы посчитать точно надо поделить словарь на слова одинаковой длины и перебором всех вариантов комбинаций длин слов получить полное количество комбинаций (и энтропию как его двоичный логарифм). Не так уж и сложно в общем.

-- 23.10.2021, 16:44 --

Данные по длинам слов для точного расчёта энтропии.
Для исходного словаря в $7776$ слов длины $1...6:\{52,773,839,2345,3136,631\}$ (сколько слов такой длины).
Для словаря без гласных в $3531$ слов длины $1...5:\{47,544,1646,1230,64\}$.

[mihaild]

Dmitriy40 в сообщении #1536048 писал(а):

Мне кажется или тут противоречие? Сначала пробелы не меняют энтропию, потом вдруг меняют.

Тут утверждение такое: энтропия строки, получающейся конкатенацией через пробел, равна энтропии кортежа. Энтропия строки, получающейся конкатенацией без разделителя, может быть меньше.

Dmitriy40 в сообщении #1536048 писал(а):

Оно почему-то не соответствует целому числу слов.

После выкидывания гласных распределение на том что получилось не обязано быть равномерным.

[beroal]

Dmitriy40 в сообщении #1536048 писал(а):

Мне кажется или тут противоречие? Сначала пробелы не меняют энтропию, потом вдруг меняют.

Возможно, я выражался не ясно, но это для краткости. Чтобы стало яснее, введу обозначения.

Пусть $\Sigma$ — ASCII. $W\subseteq \Sigma^*$.

mihaild в сообщении #1536061 писал(а):

После выкидывания гласных распределение на том что получилось не обязано быть равномерным.

Да. Человек выбирает слово из $W$ согласно закону равномерного распределения, и это слово он держит в памяти. Гласные выкидываются при наборе слова.

Пусть $d: \Sigma^* \to \Sigma^*$ — функция, удаляющая гласные. Примеры: $d(\text{<<avoid>>}) = \text{<<vd>>}$, $d(\text{<<avon>>}) = \text{<<vn>>}$. $Y = d(X)$. Кстати, в начальном сообщении опечатка: $\mathrm{H}(Y) = 11,125381731183683\text{ бит}$.

Распределение $Y$ не равномерное. Следующий код показывает, что у разных результатов $Y$ может быть разное количество прообразов по $d$. Например, $\text{<<ccd>>} = d(\text{<<cicada>>})$, $\text{<<tdy>>} = d(\text{<<tidy>>}) = d(\text{<<toady>>}) = d(\text{<<today>>})$. Поэтому вероятность $\text{<<tdy>>}$ в $3$ раза больше, чем вероятность $\text{<<ccd>>}$.

Используется синтаксис Java

        final Map<String, List<String>> wordSources = Files
                .lines(Paths.get(args[0]))
                .flatMap(line -> extractWord(line).stream())
                .collect(Collectors.groupingBy(DicewareVowel::deleteVowels, Collectors.toList()));
        System.out.println("word sources: " + wordSources);
 

Пусть $j_s: \Sigma^*^* \to \Sigma^*$ — конкатенация списка через пробел. Пример: $j_s([\text{<<avoid>>}, \text{<<avon>>}]) = \text{<<avoid avon>>}$. Поскольку $j_s$ инъективна на $W^*$, $\mathrm{H}(j_s(Y^n)) = \mathrm{H}(Y^n)$. Пусть $j: \Sigma^*^* \to \Sigma^*$ — конкатенация списка. Пример: $j_s([\text{<<avoid>>}, \text{<<avon>>}]) = \text{<<avoidavon>>}$.

Задача: найти $\mathrm{H}(j(Y^n))$.

-- Пн окт 25, 2021 18:12:31 --

Dmitriy40 в сообщении #1536048 писал(а):

Разумеется последние оценки для всего пароля очень в среднем, чтобы посчитать точно надо поделить словарь на слова одинаковой длины и перебором всех вариантов комбинаций длин слов получить полное количество комбинаций (и энтропию как его двоичный логарифм). Не так уж и сложно в общем.

Дайте подумать.

-- Пн окт 25, 2021 18:14:43 --

Dmitriy40 в сообщении #1536048 писал(а):

С другой стороны, в $16$ символов пароля влезут в среднем $3.775$ слова (у них средняя длина $4.2388$ символа), что даст $7776^{3.775}=4.855\cdot10^{14}=2^{48.8}$, т.е. перебор $49$ битов. После удаления гласных средняя длина уменьшится, но лишь до $3.2$ символов, тогда в $16$ символов пароля влезут в среднем $5$ слов, что даст $3531^5=5.5\cdot10^{17}=2^{58.93}$, т.е. перебор $59$ битов, даже заметно больше.

Ради этого всё и затеяно . Не зря в семитских письменностях так поступили.

[beroal]

Dmitriy40 в сообщении #1536048 писал(а):

Разумеется последние оценки для всего пароля очень в среднем, чтобы посчитать точно надо поделить словарь на слова одинаковой длины и перебором всех вариантов комбинаций длин слов получить полное количество комбинаций (и энтропию как его двоичный логарифм). Не так уж и сложно в общем.

Мне кажется, вы решаете задачу сгенерировать пароль из ровно $16$ символов. Я такой задачи не ставил, хотя её тоже надо решать. Я думал генерировать пароль из $6$ слов. Ожидаемая длина $j(Y^6)$ равна $16,574074074074076$ символов. Если пароль получится слишком длинным, генерировать ещё раз.

[beroal]

Есть идея использовать оценку $\max_{p\in j(W^n)} \# ((j\restriction W^n)^{-1}(\{p\})) \leq 6^n$. Это для вычисления $\mathrm{H}(j(X^n))$.

[Dmitriy40]

beroal в сообщении #1536330 писал(а):

mihaild в сообщении #1536061 писал(а):

После выкидывания гласных распределение на том что получилось не обязано быть равномерным.

Да. Человек выбирает слово из $W$ согласно закону равномерного распределения, и это слово он держит в памяти. Гласные выкидываются при наборе слова.

Э, но ведь тогда возникает неоднозначность. А, Вы дальше про неё и пишите, ок. Кстати несколько слов вообще исчезают (состоят только из выкинутых гласных), а пустые пароли недопустимы.
Ну и вопрос коллизий надо как-то обрабатывать, когда два разных пароля имеют одинаковое представление после удаления гласных. Обычно это нехорошо.
Собственно я тогда не понимаю чем этот процесс отличается в лучшую сторону от выбора уже по сокращенному словарю. Получается вероятности искажаются и энтропия падает (с 3531 вариантов до 2234 вариантов) при сохранении длины пароля. Ну может преимущества и есть, типа лёгкого запоминания человеком ...

В любом случае это не мешает подсчитывать точную энтропию, надо только лишь дополнительно слова каждой длины поделить ещё и по группам встречаемости после удаления гласных (сколько однозначно восстанавливаются, сколько в два разных, сколько в три, и т.д.) и аккуратно подсчитать количество возможных комбинаций. Руками муторно, программой реально. Это всё равно на много порядков меньше полного перебора.

beroal в сообщении #1536337 писал(а):

Мне кажется, вы решаете задачу сгенерировать пароль из ровно $16$ символов.

Да я взял просто для примера, что прикинуть несложно. Хотел точно посчитать энтропии для 6 символьного пароля для обоих словарей как пример, но замучился выписывать формулой все произведения (хотя все комбинации переписал).
Моя основная мысль была что для точного подсчёта энтропии не обязательно перебирать все комбинации всех слов словаря, достаточно перебрать все комбинации длин слов. Для ровно 16 символов или любого другого условия, не суть.

[beroal]

Dmitriy40 в сообщении #1536346 писал(а):

В любом случае это не мешает подсчитывать точную энтропию, надо только лишь дополнительно слова каждой длины поделить ещё и по группам встречаемости после удаления гласных (сколько однозначно восстанавливаются, сколько в два разных, сколько в три, и т.д.) и аккуратно подсчитать количество возможных комбинаций.

Я всё-таки не понимаю, почему это корректный способ. Вы учли, например, что пароль «aftera» получается из [«after», «a»] и [«aft», «era»]?

Dmitriy40 в сообщении #1536346 писал(а):

Собственно я тогда не понимаю чем этот процесс отличается в лучшую сторону от выбора уже по сокращенному словарю. Получается вероятности искажаются и энтропия падает (с 3531 вариантов до 2234 вариантов) при сохранении длины пароля. Ну может преимущества и есть, типа лёгкого запоминания человеком ...

Сейчас мне кажется, что лучше решить другую задачу, а именно, поменять словарь, а возможно и способ выбора паролей . Скажем, составить такой словарь, что любая пара разных слов из него не совпадает в первых 3-х символах. Человек запоминает слово, а вводит его префикс длины 3.

[Dmitriy40]

beroal в сообщении #1536348 писал(а):

Я всё-таки не понимаю, почему это корректный способ. Вы учли, например, что пароль «aftera» получается из [«after», «a»] и [«aft», «era»]?

Да: пароль из 6 символов можно получить и как 5+1, и как 3+3, и ещё десятка три комбинаций (от 6 и 4+2 и 2+4, до 1+2+1+1+1 и 1+1+1+1+2 и 1+1+1+1+1+1). Просто как количество разных разложений числа $6$ в сумму натуральных чисел.

(Полный список для 6 символов)

$\{6\}$
$\{1, 5\}$
$\{5, 1\}$
$\{2, 4\}$
$\{4, 2\}$
$\{3, 3\}$
$\{1, 1, 4\}$
$\{1, 4, 1\}$
$\{4, 1, 1\}$
$\{1, 2, 3\}$
$\{1, 3, 2\}$
$\{2, 1, 3\}$
$\{2, 3, 1\}$
$\{3, 1, 2\}$
$\{3, 2, 1\}$
$\{2, 2, 2\}$
$\{1, 1, 1, 3\}$
$\{1, 1, 3, 1\}$
$\{1, 3, 1, 1\}$
$\{3, 1, 1, 1\}$
$\{1, 1, 2, 2\}$
$\{1, 2, 1, 2\}$
$\{1, 2, 2, 1\}$
$\{2, 1, 1, 2\}$
$\{2, 1, 2, 1\}$
$\{2, 2, 1, 1\}$
$\{1, 1, 1, 1, 2\}$
$\{1, 1, 1, 2, 1\}$
$\{1, 1, 2, 1, 1\}$
$\{1, 2, 1, 1, 1\}$
$\{2, 1, 1, 1, 1\}$
$\{1, 1, 1, 1, 1, 1\}$

Например для пароля из 6 символов из исходного словаря есть $631$ вариант из одного слова, $3136\cdot52+52\cdot3136=326144$ комбинаций из слов длины 5 и 1 в любом порядке, $839^2=703921$ комбинаций из слов длины 3 (даже двух одинаковых), и например $839\cdot773\cdot52=33724444$ комбинаций из слов длины 3 и 2 и 1 символов именно в таком порядке. Чтобы учесть разный порядок достаточно домножить на количество перестановок, которых для таких трёх слов всего $6$, а например для слов длиной 3 и 1 и 1 и 1 символов перестановок будет лишь 4 разных (3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3) и количество комбинаций $839\cdot52^3\times 4=471880448$. Сложив их и все остальные комбинации получим полное количество всех возможных комбинаций пароля, без перебора самих этих комбинаций.
Для исходного словаря полное количество комбинаций ровно 6 символьного пароля будет $58839018855\approx2^{35.776}$ — сумма всех строк, каждая из которых как перемножение соответствующих количеств слов указанной в строке длины. $35.776$ это энтропия пароля.
Для исходного словаря полное количество комбинаций ровно 16 символьного пароля будет $70348031827212043070971446506\approx7.0348\cdot10^{28}\approx2^{95.83}$ с энтропией $95.83$. По сравнению с грубой оценкой выше в $48.8$.
Надеюсь ни в чём не ошибся, но лучше проверьте. Да, считал не руками, написал программулю на PARI/GP, считалось доли секунды:

? v=[52,773,783,2345,3136,631];
? z=0; forpart(x=6, forperm(x,s, z+=prod(i=1,#s,v[s[i]])), #v); print(z,"=2^",log(z)/log(2));
58839018855=2^35.77605413862021505930980806
? z=0; forpart(x=16, forperm(x,s, z+=prod(i=1,#s,v[s[i]])), #v); print(z,"=2^",log(z)/log(2));
70348031827212043070971446506=2^95.82849671765207141028344286
time = 46 ms.

Вот про коллизии не подумал, факт.