Всем привет, я Олег Оболенский, технический директор одного из подразделений VK Tech. Время от времени я задаю себе вопрос: «А вот, находясь на месте ребят-программистов из моей команды, смог бы я так же, как они, или нет? Как сейчас, спустя 25 лет после того, как я вошел в профессию, выглядит программирование?»
Для честного ответа себе я время от времени делаю небольшие пет-проекты, и это позволяет мне оставаться в контексте. В этой статье я опишу, как появилась идея сделать еще один генератор паролей, как я его реализовал и с какими обстоятельствами мне пришлось столкнуться в процессе.
Даже такая простая задача не решается в лоб за пару дней или недель. Программирование, как писали классики нашей дисциплины, все еще требует ума, вкуса и терпения.
Скрытый текст
Почему я захотел сделать такой сервис
Все или почти все цифровые сервисы до сих пор защищаются паролями. Не секрет, что пароль можно подобрать, а это значит, что бывают более стойкие и менее стойкие к подбору пароли. Считается, что чем длиннее пароль и чем больше в нем различных символов, тем сложнее его подобрать. Например, приложение одного из крупных российских банков требует, чтобы длина пароля была не менее 12 символов, а сам пароль должен включать заглавные и строчные буквы, цифры и специальные символы. Дополнительные требования типа разнообразия (количество уникальных символов в строке) или отсутствия подстрок из соседствующих на клавиатуре символов на практике применяются сравнительно нечасто, но и без этого получившиеся пароли подобрать достаточно трудно, а запомнить еще труднее.
По этой причине пар��ли, записанные на приклеенных к экрану листочках, — это не только набивший оскомину стереотип, но и печальная правда жизни, встречающаяся, к сожалению, даже на конференциях по информационной безопасности.
Основной стратегией защиты в этой связи является создание таких систем, в которых пароль в принципе не нужно вводить. Кроме того, пароли по сравнению с другими факторами аутентификации обладают и плюсами: в отличие от сетчатки глаза или отпечатка пальца, их можно в случае чего сменить.
Давным-давно в какой-то, не помню уже какой именно, книге по азам информационной безопасности я почерпнул следующую технику создания пароля: он должен основываться на сочетании не связанных по смыслу слов. Например: «бледнолицый саморез», «грустноватые еноты» (именно они вдохновили на название этой статьи!) или «хризантему Васе» (удивительно, что эти вещи написаны в учебнике по информационной безопасности, а не в учебнике по информатике). Эта же идея лежит в основе такой техники создания паролей, как Diceware. Плюс, как мы уже выяснили на примере банка, пароль должен содержать цифры, верхний регистр и спецсимволы.
Формулировка гипотезы
Даже неудобно называть гипотезой то, что известно как минимум с 1982 года. Тем не менее комбинацию случайных слов, модифицированную в соответствии с требованиями по длине и количеству символов разного типа, проще запомнить, чем последовательность случайных символов с теми же требованиями. То есть если сгенерировать такой пароль-комбинацию и сообщить пользователю исходные слова, он, скорее всего, лучше его запомнит. В России в ответ на любую проблему пишут интернет-сервис, и я решил пойти этим же путем :)
Соответственно, откуда-то нужно было взять словосочетания, нужен был какой-то алгоритм создания пароля из словосочетаний, и все это нужно было упаковать в Web-сервис на Go. Забегая вперед, скажу, что с результатом можно ознакомиться здесь.
Получение словаря
Сразу ограничил себя русским языком: теоретически поддержка других языков возможна, но я решил, что сделаю решение только для одного языка (все и так оказалось намного сложнее, чем казалось вначале).
Подробное описание способа получения словаря теоретически должно повышать вероятность подбора пароля, поэтому в общих чертах расскажу, что можно взять готовый словарь, например словарь Зализняка, удалить оттуда разметку, оставив только требуемые словоформы, и использовать их, а можно попытаться сконструировать словарь самостоятельно. Опробованы и в какой-то мере использовались все приведенные ниже способы, за исключением последнего.
Словарь Зализняка описывает склонение и спряжение около 110 тыс. слов, включая имена собственные. Лицензия не допускает коммерческое использование.
Один из самых простых способов сконструировать — взять словарь от какого-нибудь лингвистического инструмента типа Hunspell, вычитать оттуда все слова, с помощью команды hunspell -g или Spylls породить из этих слов все возможные словоформы, включая фактически отсутствующие в языке, и использовать их. На момент написания статьи Google знает несколько инструментов, позволяющих из словаря и набора аффиксов Hunspell получить полный список словоформ, длина которого для русского языка будет составлять примерно 2,5 млн строк. И Hunspell, и Spylls распространяются по лицензии Mozilla.
Еще один способ сконструировать (самый трудоемкий, но и наименее юридически обязывающий) — это собрать роботом или взять откуда-нибудь подходящий по лицензионным ограничениям готовый корпус текстов, токенизировать (преобразовать в массив слов) эти тексты и выбрать какие-то, например неуникальные, токены. Не погружаясь глубоко в детали работы роботов и извлечения текста из html и pdf (так как это потребует отдельной статьи), расскажу, как токенизировал полученный корпус при помощи Apache OpenNLP.
Выделение предложений из текста и выделение токенов в предложении — это задачи с довольно неочевидным решением. Например, предложение не всегда заканчивается точкой — оно может заканчиваться многоточием, вопросительным знаком, восклицательным знаком или вообще никаким знаком не заканчиваться, если этот знак забыли поставить.
Точно так же оно не обязательно начинается с заглавной буквы — оно может начаться с кавычки, или одинарной кавычки, или с тире в случае прямой речи, или с многоточия и строчной буквы. Формализация набора правил быстро становится сложной, поэтому OpenNLP — это конвейер инструментальны�� средств, позволяющий на основе машинного обучения выделять из текста предложения, из предложений — токены, из токенов — части речи и имена собственные, из размеченных массивов частей речи — факты (деревья разбора), словом, все, что сегодня делает GenAI, но значительно дешевле с точки зрения потребляемых вычислительных ресурсов.
Токенайзер OpenNLP принимает на вход предложения, а не целые тексты, поэтому сначала я обучил Sentence Detector, а затем использовал полученные предложения для обучения токенайзера и последующей токенизации. Как я предполагаю, с Sentence Detector можно было бы ничего и не делать, считая, что содержимое всего документа — это один Sentence. Однако, поскольку разметка предложений в OpenNLP — занятие не сильно трудоемкое, последовательность действий была достаточно прямолинейной: примерно 2 000 предложений было размечено вручную для Sentence Detector и еще столько же для токенайзера. Важно, что токенайзер возвращает знаки препинания в виде отдельных токенов, поэтому поток токенов нужно дополнительно фильтровать. Так как OpenNLP написан на Java, а основную разработку я вел на Golang, сериализовал получившиеся массивы токенов в Msgpack и собирал словарь уже на Go.
Полученный список токенов дальше можно объединять или пересекать со словарем Зализняка и не только, фильтровать токены при помощи Aspell, Hunspell и т. д. Единственное, что мат придется отрезать вручную: и в Hunspell, и в интернете, и в других источниках его много. Мои познания в области русской ненормативной лексики позволили сделать это быстро и без каких бы то ни было затруднений :)
Размер словаря, полученного токенизацией корпуса текстов, будет в разы меньше, чем при использовании Hunspell, но раскрывать детали — повышать вероятность подбора.
Бонусный способ, который я не проверял, но который, исходя из общей логики, должен сработать, — это написать правильный промпт и получить искомый словарь без всех описанных сложностей.
Общее описание алгоритма
Изначальная идея была такая: пароль — это конкатенация транслитерированных случайно выбранных слов. Сумма длин этих слов должна быть равна длине пароля за вычетом требуемого количества цифр и спецсимволов. В эту конкатенацию в случайные позиции вставлялись цифры и спецсимволы, а алфавитные символы в случайных позициях заменялись на соответствующие из верхнего регистра. Несмотря на то что пароли на выходе соответствовали политикам и формально соответствовали заявленной цели, словосочетания в пароле читались с трудом, а запомнить их было все-таки сложновато, поэтому алгоритм пришлось чуть-чуть модифицировать.
Решил использовать замены, основанные на Leet. В каждой строке есть 0 или более подстрок, заменяемых по правилам Leet. Иногда эти подстроки будут состоять из одного символа, например l -> 1, а иногда из нескольких (tri -> 3, ch -> 4). То есть длина строки с заменами всегда не больше, чем длина исходной. Чтобы получить из исходной строки без цифровых символов другую, с цифровыми символами, можно применить одно из Cnk-сочетаний замен, где n — общее количество возможных в соответствии с правилами замен.
Финальная версия представляет собой цикл, в котором на каждом шаге из словаря выбирается одно или два случайных транслитерированных слова, таких, что хотя бы одно из сочетаний замен по правилам Leet и добавление требуемого политикой количества спецсимволов дают строку требуемой длины, после чего к этим одной или двум строкам применяется случайно выбранное сочетание замен. Если длина получившейся строки соответствует требуемой, в нее добавляются спецсимволы, необходимое количество алфавитных символов в случайных позициях преобразуется в верхний регистр, а сама строка добавляется в список гипотез. Если длина строки меньше, алгоритм переходит на следующий шаг цикла. Остановка происходит при формировании N гипотез, после чего гипотезы сортируются по разнообразию (количеству уникальных символов), а из наиболее разнообразных выбирается случайная.
Некоторое время пришлось экспериментировать с параметрами распределения, используемого для выбора первого слова в комбинации, так как они должны, по идее, влиять на стойкость к подбору. Например, если всегда выбирать первое слово в комбинации с длиной, равной половине длины пароля за вычетом спецсимволов, и затем второе, исходя из требуемой общей длины, то такой пароль заведомо легче подобрать, чем пароль из двух слов случайной длины.
Структура данных словаря
Из описания алгоритма понятно, что строки должны, во-первых, храниться одновременно и в латинском, и в кириллическом виде, а во-вторых, основная операция в такой структуре данных — это выбор случайной латинской строки заданной длины. Крайне желательно, кроме того, чтобы такая структура была персистентной, потому что перестраивать ее для сотен тысяч строк будет явно долго и дорого.
Реализация использует файл с заголовком и данными и фактически хранит не строки, а последовательности байтов фиксированной длины с латинской и кириллической строками, отсортированные по длине латинской строки и вторично по алфавиту (вторичная сортировка нужна для того, чтобы относительно быстро понимать, есть ли в словаре запрашиваемое слово), при этом в заголовке хранится массив из пар смещение — количество. Таким образом, выбор случайной строки заданной длины представляет собой выбор случайного числа в заданном диапазоне и чтение элемента фиксированной длины с диска по смещению, рассчитываемому как сумма базового смещения и этого случайного числа, то есть такая операция выполняется за константное время.
Структура данных создается в три прохода: на первом проходе из считываемых из файла или со стандартного ввода кириллических строк создаются последовательности байтов фиксированной длины с латинской и кириллической строкой и записываются во временный файл. На втором проходе эти последовательности в файле сортируются по длине латинской строки и алфавиту, а на третьем — записываются в упакованном виде в файл данных, а заголовок обновляется.
Транслитерация кириллических строк в латинские происходит по правилам, рекомендуемым для формирования человеко-понятных url. Ссылку, к сожалению, потерял, но здесь ничего секретного нет, поэтому приведу общее описание: по таблице транслитерируются все буквы кириллического алфавита, кроме буквы “х”, которая в зависимости от того, какой ��ыла предыдущая буква, транслитерируется либо в “h”, либо в “kh” (после символов “c”, “z” и “s”, “e” и “k” используется “kh”).
Использование записей фиксированной длины выглядело на первый взгляд оправданным, так как в результате всех изысканий со словарем выяснилось, что ни одна словарная транслитерированная из русского в кириллице латинская строка не получается длиннее 48 ASCII-символов, поэтому в заголовке 48 пар смещение — количество и размер последовательностей фиксированной длины тоже зависит от 48. То есть добавление нового языка потребует (о нет) редизайна структуры данных.
Кроме того, из соображений баланса ресурсов на создание vs стойкость получившихся паролей к подбору можно задавать максимальную длину кириллической строки. Тогда при формировании структуры данных из словаря все строки на входе с длиной, большей чем заданная, будут отбрасываться.
Дисковая хеш-таблица
Довольно быстро стало понятно, что сложный алгоритм создания пароля не гарантирует его стойкость к подбору: если пароль в каком-то сервисе уже утек, то подберут его достаточно быстро, поэтому одним из этапов фильтрации гипотез стала проверка в базе «утекших». Поскольку база «утекших» изменяется сравнительно редко (например, раз в день), то для реализации можно использовать структуру данных, создание которой долгое, а поиск — быстрый. Кроме того, поскольку базы «утечек» насчитывают сотни тысяч записей, она так же, как и словарь, должна быть персистентной.
Тут тоже все достаточно несложно: используется дисковая хеш-таблица с обычным открытым хешированием, хранящая в качестве ключей записи фиксированной длины. На первом проходе создания определяется максимальная длина записи (самый длинный утекший пароль с учетом выравнивания), исходя из волюнтаристски выбранного значения Fill Factor, равного 0,8, поиском простого числа в окрестности выбирается количество бакетов и, исходя из полученного количества хеш-конфликтов, подбирается размер цепочки значений, а на втором проходе все это сериализуется в двоичный файл. В итоге все бакеты используют цепочку значений в виде массива одного и того же размера, что означает, что бакет фактически содержит всю цепочку, а не ссылку на нее. Такая организация упрощает реализацию ценой использования значительного объема дополнительного дискового пространства. Выбор алгоритма хеширования (в экспериментах участвовали murmur, fnv32 и crc32) почти не влияет на количество хеш-конфликтов. 64-разрядные версии алгоритмов дают неожиданные спецэффекты, бороться с которыми не стал, оставил в итоге fnv32. В диапазоне от сотен тысяч до миллионов издержки на дисковое пространство большие, но не катастрофические. Для хранения миллионов записей придется приспособить что-нибудь более подходящее. Можно было использовать Perfect Hashing, но руки не дошли.
Возможные парольные политики
Парольная политика сама по себе может быть неверной, например невозможно сделать пароль из 6 символов, из которых символов нижнем регистре должно быть как минимум 2, в верхнем — тоже как минимум 2, цифр — 2 и один спецсимвол. Допустимые парольные политики для паролей-комбинаций должны варьироваться в более узких пределах, чем для Weighted Round Robin, с помощью которого генерируются случайные последовательности символов с заданными характеристиками.
В частности, если максимальная длина латинских строк в словаре — 15, с помощью упомянутого выше алгоритма принципиально невозможно создать пароль с двумя 2 спецсимволами длиной больше, чем 32 символа. Или: пароль из 4 символов с одной цифрой или одним спецсимволом почти всегда будет состоять из букв “i”, “s” и “a“, что делает такие пароли исключительно легко подбираемыми. Поэтому при использовании не соответствующих определенным правилам парольных политик (цифр запрошено больше чем полстроки, больше скольки-то спецсимволов и т. д.), алгоритм переключается на использование Weighted Round Robin.
Энтропия и оценка пароля
С помощью сервиса есть возможность «оценить» качество пароля от 0 до 100: по классической формуле log2(|c|L), где c — множество допустимых символов, а L — длина, вычисляется энтропия и сравнивается с энтропией «минимально приемлемого» пароля, под которым подразумевается строка длины N символов (14 по умолчанию), содержащая строчные и заглавные буквы, цифры и спецсимволы. Если получившаяся энтропия меньше целевой, рейтинг считается как отношение получившейся энтропии к целевой, умноженное на 100. Если больше, рейтинг считается равным 100.
Кроме энтропии, на рейтинг опционально влияют разнообразие (он будет тем ниже, чем меньше количество уникальных символов) и обнаружение в базе утекших паролей (снижает рейтинг в волюнтаристски выбранные три раза). Создаваемые в соответствии с умолчательными настройками пароли с учетом разнообразия имеют в подавляющем большинстве случаев рейтинг не ниже 90.
John the Ripper
Теоретические оценки энтропии — это хорошо, но стойкость можно измерять и экспериментально. Для чистоты эксперимента поставил риппер с русским словарем подбирать пароль, сгенерированный с умолчательными настройками. За месяц пароль подобрать не получилось, но все упирается в первую очередь в наличие производительного железа. На Чебышеве или Ломоносове дело пошло бы явно побыстрее :)
Web-сервис
Тут ничего особенно интересного нет, публичная часть торчит наружу обычным веб-сервисом с сессией в 15 минут, в рамках которой можно повторно запрашивать операции. Рейт-лимита и капчи пока нет, но, возможно, они когда-нибудь появятся. Верстку помогал делать коллега (спасибо тебе большое!). Непубличное API без сессией с аутентификацией Bearer-токенами работает без лимитов. Помимо собственно генерации пароля, в обе части — публичную и непубличную — вынесена отдельной операцией упомянутая выше оценка стойкости пароля.
Вишенка на торте
Чтобы понять, насколько более стойкие пароли придумывает алгоритм, решил оценить рейтинги 100 тыс. утекших паролей без учета собственно факта утечки (чтобы не снижалось в три раза) и разнообразия. Полученные цифры отражают отношение энтропии исследуемого пароля к энтропии эталонного, в данном случае имеющего длину 12, и, как обычно, цифры, нижний, верхний регистр и спецсимволы в составе. Гистограмма ниже показывает распределение рейтингов. Как можно видеть, с точки зрения энтропии примерно три четверти пользовательских паролей не просто плохие, а очень плохие. Эти рассуждения согласуются с экспериментальными оценками стойкости к подбору: из примерно 25 тыс. паролей с наихудшим рейтингом (от 0 до 9), захешированных bcrypt, около 250 было подобрано риппером, выполняющемся на обычном бытовом ноутбуке с Core i5, в течение первых суток.
Итоги
Задумки и первый прототип появились, когда я находился в отпуске, еще летом 2023 года. Эпизодические, но неоднократные улучшения в свободное от работы время заняли в общей сложности еще два года. Так что пет-проекты — это долго, хотя и временами увлекательно.
P.S. Меняю теперь пароли раз в два месяца :-)