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

В статье мы рассмотрим, зачем ИБ-специалистам и этичным хакерам подбирать пароли, по каким сценариям проводятся подобные атаки, какие для этого используются методики и инструменты. Заодно совершим небольшой экскурс в историю аутентификации при помощи паролей. 

Эта статья — адаптированный доклад Александра Песляка (aka Solar Designer) на конференции OffensiveCon24. Докладчик является основателем проекта Openwall, создателем популярного инструмента для подбора паролей John the Ripper и контрибьютором таких проектов, как OpenBSD и Debian.

Зачем использовать и взламывать пароли?

На сегодняшний день пароли являются уникальным фактором аутентификации, тем, «что мы знаем» в двухфакторной аутентификации (2FA) и многофакторной аутентификации (MFA). Они широко применяются для создания различных ключей: например, шифрования данных. Для предоставления seed-ключей, допустим, кошельков, могут использоваться мнемоники, когда выполняется исключительно кодирование. Пассфраза используется как дополнительный фактор над мнемоникой (пассфраза без мнемоники не работает). Обычно применяются сгенерированные порождающие фразы, к которым иногда добавляются дополнительные слова. Схожие концепции и техники применимы и к другим хэшируемым данным с низкой энтропией. 

Впрочем, цели и способы работы с паролями в общих чертах понятны любому, кто имеет хоть какое-то отношение к кибербезу. Но зачем нужно подбирать пароли, если ты не злоумышленник? Перечислим по пунктам: 

1. Аутентификация для предотвращения или получения доступа к системам при проведении аудитов безопасности и тестов на проникновение.

2. Восстановление доступа (альтернатива сбросу пароля).

3. Общее развитие: расширение списков подобранных/утекших паролей, обучающие и тестовые датасеты для инструментов, исследовательские проекты, соревнования, архивирование истории, анализ зловредного ПО и бэкдоров, OSINT, восстановление других хэшированных данных.

Сценарии подбора паролей

Можно выделить четыре основных сценария, которые позволяют безопасникам добиться обозначенных выше результатов.

1. Оффлайн-подбор локальных копий хэшей, дампов трафика, зашифрованных данных (именно этому, в основном, и будет посвящена наша статья).

2. Онлайн-перебор на удаленных системах. В качестве примера можно вспомнить программу для перебора на авторизациях связок логин-паролей THC Hydra. Продукт разработал van Hauser.

3. Онлайн-взлом удаленной системы с непривилегированным локальным доступом, определение паролей по сторонним каналам (тайминги сети или нажатия клавиш) и физический взлом защищенного от вмешательства устройства.

4. Сброс паролей, их утечка/извлечение в открытом виде, обход проверки и прямое извлечение ключа посредством взлома.

Цели атак

Как известно, цель оправдывает определяет средства. В зависимости от того, для чего именно выполняется атака с подбором паролей, применяются соответствующие инструменты. Так, одни решения предназначены для извлечения паролей аутентификации, другие — для получения доступа к зашифрованным файлам и файловым системам.

Впрочем, наиболее гибкие современные программы для подбора паролей или, другими словами, хэшкрякинга (John the Ripper и Hashcat), могут работать не только с паролями аутентификации: они вполне применимы для достижения других целей атак.

Например, John the Ripper позволяет оперировать так называемыми «не-хэшами» (non-hash): для этого в программе есть набор инструментов *2john.py, извлекающий из файлов псевдохэши. В свою очередь, инструмент BTCrecover применяется для подбора passphrase при использовании конкретной мнемоники.

Оптимизация подбора

Достижение перечисленных целей требует немалых ресурсов. Чтобы подбор паролей не растянулся до бесконечности, этот процесс необходимо оптимизировать. И здесь снова приходят на помощь специализированные решения.

Обозначим основные моменты, которые позволяют оптимизировать работу программ для хэшкрякинга:

1. Соотношение скорости и экономических затрат на подбор (оборудование, обслуживание, энергопотребление). Поиск паролей выполняется в оптимальном порядке, при котором избегается или минимизируется дублирование кандидатов паролей. Таким образом повышается уникальность кандидатов, оптимизируется использование памяти. Также проводятся сопоставление с загруженными хэшами или проверки корректности расшифровки.

2. Требования к памяти и накопителю относительно скорости.

3. Структура словарей: наиболее популярные пароли помещаются в начало, удаляются дубли и мусорные (слишком длинные и нереалистичные) пароли.   

4. Создание целевых словарей для каждого из хэшей.

5. Циклы обратной связи и рабочие процессы (смена оптимального порядка поиска на основании уже взломанных паролей).

История аутентификации при помощи паролей

Сейчас трудно представить, что когда-то пароли практически не защищались, а их подбор не представлял особого труда. Совершим небольшой экскурс в прошлое и проследим, как эволюционировали и развивались процессы аутентификации с течением времени. Итак, поехали!

1. Хранение паролей в открытом виде (TENEX, Unix, 1960-е — начало 1970-х, CTSS)

Разумеется, такие системы были ненадежны и подвержены взлому.

«В CTSS однажды произошло следующее: любой вошедший пользователь обнаруживал, что вместо стандартного ежедневного сообщения ему отображается файл со всеми паролями». 

Фернандо Корбато, «On Building Systems That Will Fail», 1991.

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

Не обошлось без неприятных сюрпризов и в системе Unix. 

«Изначально система Unix была реализована с файлом паролей, в котором хранились актуальные пароли для всех пользователей».

Роберт Моррис и Кен Томпсон, «Password Security: A Case History», 1978.

2. Хэширование паролей (Multics, начало 1970-х)

Главная проблема заключалась в том, что подсистема Multics User Control использовала хэш-функцию one-way encryption. 

«Я знал, что люди могут брать квадратные корни, поэтому возводил пароли в квадрат и выполнял операцию AND с ними и с маской, чтобы отсечь часть битов…

После успешного взлома системы группой экспертов Военно-воздушных сил США, проводивших проверку безопасности Multics в 1972-1974 годах, мы быстро поменяли способ хэширования на новый, более надёжный».

Том Ван Влек, «How the Air Force cracked Multics Security», 1993.

3. Хэширование паролей (Unix, середина 1970-х)

В середине 1970-х годов процессы хэширования несколько усложнились. Но всё равно подбор паролей не представлял особого труда для тех, кто обладал необходимыми навыками. 

«Сrypt(3) в Unix вплоть до шестой редакции использовал программу шифрования, которая имитировала шифровальную машину M-209. Такая машина применялась армией США во время Второй мировой войны. Пароль использовался не как текст, который нужно зашифровать, а как ключ для шифрования константы…

Процесс шифрования одного пробного пароля и проверки результата после изменения алгоритма с целью обеспечения максимальной скорости занимал на PDP-11/70 примерно 1,25 миллисекунды…

По сути, требуется не больше времени для сверки зашифрованного пробного пароля со всеми паролями во всём файле паролей или со всей коллекцией зашифрованных паролей, в том числе и собранных из других установок».

Роберт Моррис и Кен Томпсон, «Password Security: A Case History», 1978.

Фактически подобные схемы использовались и в веб-приложениях, и в Windows начала 2000-х.

4. Соль и другие модификации (Unix, конец 1970-х)

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

5. BSDI, bcrypt, PBKDF2 (1990-е)

В эти годы единственным значимым изменением стала возможность настройки медленной хэш-функции.

6. Scrypt, Argon2 (2010-е)

В 2009 году автор Scrypt Колин Персиваль в своей статье ввел понятие функций с высоким расходом памяти — memory hardness. Они предназначены для потребления больших объемов памяти компьютера и, таким образом, сильно снижают эффективность параллельных вычислений. 

Теперь задача подбора паролей стала двухмерной: для ее решения требовались не только вычислительные ресурсы, но и память.

Другие способы аутентификации

Итак, мы кратко рассмотрели развитие парольной аутентификации на историческом таймлайне. Однако существуют и другие механизмы, которые начали появляться в 1990-х годах. 

Их отличительная черта — передача пароля на сервер в незашифрованном виде. Зачастую это происходит через Transport Layer Security, но есть и другие способы аутентификации. Обычно такие системы тоже подвержены оффлайн-взлому при помощи определенных данных аутентификации:

1. Запрос/ответ (разные виды): сниффинг через сеть пары запроса/ответа.

2. Kerberos: TGT, база данных пользователей AFS.

3. S/Key, OPIE: файл skeykeys.

4. SSH: приватный ключ, зашифрованный парольной фразой, хэшированный known_hosts.

5. SRP (и другие PAKE): верификаторы.

Скорость подбора паролей

Со временем развивались не только механизмы аутентификации, но и методики, направленные на ускорение подбора паролей. Еще в 1983 году были проведены первые соревнования по подбору паролей Unix. 

1980-е: неоптимизированные способы получения хэшей

Неоптимизированный алгоритм для хэша каждого пользователя и кандидата пароля выполнял следующие действия:

1. Брались кандидат и соль хэша.

2. Вычислялся хэш.

3. Полученный хэш сравнивался с хэшем, к которому подбирался пароль. В случае совпадения — PROFIT!: шаг 1 выполнялся уже с новым хэшем. Если же совпадения не было, то весь цикл начинался заново. 

1980-е: частично оптимизированные способы в случае отсутствия соли

Если соль не используется, алгоритмы можно оптимизировать, снизив повторные затраты на хэширование. В хэшах без соли один раз вычисляется хэш от одного кандидата, а затем сравнивается со всеми искомыми хэшами. 

1. Берется кандидат.

2. Вычисляется хэш.

3. Полученный хэш сравнивается со всеми хэшами, к которым подбирается пароль. Если остались неподобранные хэши, то снова выполняется первый шаг.

Начало 1990-х: частично оптимизированные способы при использовании соли

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

Конец 1990-х: сильно оптимизированные способы при использовании соли

Такую систему можно ещё сильнее оптимизировать, как это было сделано в John the Ripper: одновременно вычислять целый ряд хэшей и загружать множество хэшей с солью, чтобы выполнять сравнение «многие ко многим». Можно также оптимизировать время построения и хэш-функцию, выводя некоторые операции во внешний цикл. Здесь снова происходит амортизация затрат благодаря многократному использованию окончательных или промежуточных результатов.

Сравнение хэшей «многие со многими»

Пожалуй, на этом стоит остановиться подробнее. Впервые такое сравнение было выполнено в начале 1997 года в ранней версии John the Ripper. Приблизительно его можно описать следующим образом.

1. Если для текущей соли загружено мало хэшей, то выполняем сравнение или разрешение коллизий.

2. Если для текущей соли загружено множество хэшей, то берем частичные хэши для сравнения с подбираемыми (для текущей соли):

а) предварительно получаем нужные элементы для каждой соли;

б) отбрасываем хэши, не находящиеся в разреженной битовой карте или фильтре Блума;

в) завершаем вычисление остальных и/или хэш-таблицы (идеальной) и так далее;

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

Амортизация затрат на подбор паролей

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

Наряду с вычислительной сложностью есть еще одна важная метрика — пространственная сложность. В реальном мире затраты могут требоваться на оборудование, обслуживание, энергию и так далее. Эти затраты связаны и с вычислительной, и с пространственной сложностью, а также с ограничениями реального мира, которые сильно различаются для тех или иных атакующих. Важно учитывать, сколько CPU и ОЗУ занято на какой промежуток времени, есть ли эти ресурсы в наличии или их надо покупать. После оценки таких затрат может оказаться, что основная проблема теперь вовсе не в CPU.

Снижение затрат на подбор паролей на GPU (с 2008 года)

Пионером в этой области стал Андрей Беленко из Elcomsoft. Компания Elcomsoft выпускала коммерческие программы для восстановления паролей, продавая их конечным пользователям и правоохранительным органам. Она занималась несколькими целевыми платформами. GPU использовались для взлома NTLM, LM и сырых хэшей MD5, притом достигалась скорость 100 млн вычислений хэшей в секунду. Поначалу скорость взлома сильно варьировалась (по крайней мере, по современным стандартам). Даже PS3 могла достигать схожих скоростей. Однако показатели быстро совершенствовались: к 2010 году это уже были десятки миллиардов в секунду на многопроцессорных машинах. Стартовала настоящая гонка в области взлома паролей. 

В 2010 году Whitepixel Марка Бевана разогналась до 33,1 млрд/с для одного хэша MD5 на компьютере с четырьмя dual-GPU HD 5970 стоимостью менее $3000.

В 2012 году OclHashcat-lite разработчика Atom поставила новый скоростной рекорд: 10,9 млрд/с на одном dual-GPU HD 6990. Выпущенная в том же году OclHashcat-plus позволила использовать ресурсы GPU почти столь же активно, как и у CPU. Поначалу система имела закрытые исходники, но в 2015 году Hashcat стал опенсорсным для хэшей MD5.

В 2010 и 2011 годах для John the Ripper появились патчи для некоторых хэшей, интегрированные в 1.7.9-jumbo-6. Впервые были реализованы bcrypt, sha512crypt.

Наконец, уже на 2022 год Hashcat 6.2.6 обеспечивал скорость 164,1 млрд/с для одного хэша MD5 на одной RTX 4090.

Снижение затрат на взлом паролей при помощи параллельной обработки

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

Добавление элементов параллельной обработки (CPU/SIMD, увеличения количества/мощности GPU/FPGA/ASIC) может «произвольно» снизить длительность атаки. При этом необходимо соответствующее увеличение объёма памяти (если только схема хэширования не обеспечивает амортизацию затрат памяти, к тому же большинство старых схем всё равно не использует большой объем памяти).

Хотя параллельная обработка не снижает количество вычислений, она сокращает время, в течение которого заняты ресурсы, и амортизирует их затраты: то есть вместо одних CPU в шасси используются и CPU, и GPU.

Снижение затрат на взлом паролей благодаря компромиссу между временем и памятью (TMTO)

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

Вот пара примеров успешного применения такой практики:

1. QCrack (1995-1997 годы) для взлома crypt(3) на основе DES помогал сэкономить примерно один день на каждый диск.

2. Радужные таблицы также облегчают подбор паролей (Филипп Оекслин, 2003 год, на основе работ Мартина Хейлмана, 1980 год). Однако сейчас они довольно редко используются на практике. Подобные таблицы есть только для хэшей без соли, а их подбор и так не представляет особой сложности. Впрочем, при недостатке ресурсов этот инструмент оказывается полезным.

Иногда ускорить вычисление функции удается благодаря большему количеству памяти. Например, в «A Fast Version of the DES and a Password Encryption Algorithm» Мэтта Бишопа (1987 год) использовались более крупные или комбинированные таблицы поиска (суммарным размером до 200 КБ). Иногда же вычислить функцию и при необходимости заново рассчитать промежуточные результаты, напротив, получается с использованием меньшего количества памяти. К слову, такому компромиссу подвержен Scrypt, чем и пользуются взломщики при подборе. При наличии множества хэшей с одинаковой солью можно увеличить частоту отбрасывания вариантов на ранних этапах, таким образом снизив затраты на вычисления и сопоставление при помощи более крупных и разреженных битовых карт.

Метрики затрат на подбор паролей

С основными способами снизить затраты на подбор паролей в общих чертах разобрались. Но как измерить полученные результаты? 

При заданной производительности (проверок {пароль, хэш} за единицу времени, возможно, амортизированной) можно выделить следующие метрики.

1. Оборудование: площадь кристалла ASIC (кв. мм) при определенной архитектуре и тактовой частоте, а также при конкретном техпроцессе ASIC.

2. Мощность(Вт): это не затраты сами по себе, но длительные атаки выливаются в затраты на энергию, коррелирующие с площадью кристаллов.

Теперь рассмотрим метрики для конкретной атаки («проверить эти кандидаты паролей на соответствие этим хэшам»).

1. Оборудование: произведение площади кристалла ASIC и времени (area-time, AT), кв. мм * с.

2. Энергия: произведение мощности и времени, Дж = Вт * с. Такая метрика коррелирует с AT, позволяя оценивать относительные затраты только в AT.

Такова современная теоретическая модель, заложенная в основу архитектуры безопасности. Оборудование и энергия могут иметь денежную стоимость, но не всегда их оплачивает атакующий. Затраты реальных атакующих могут сильно разниться, например, в зависимости от имеющегося у них оборудования.

Параллелизированная хэш-функция (изначально не требовавшая памяти)

Теперь перейдем от затрат на взлом паролей к архитектуре их хэширования. 

Так выглядела первоначальная версия параллелизированной хэш-функции. На оборудовании одновременно запускалось множество реализаций, которые выполняли параллельные вычисления. Затем хэши сравнивались по схеме «многие со многими». На данном примере видно, что мы получаем 32 хэша за то же самое время, за которое защищающаяся сторона получает один.

Параллелизированная хэш-функция (амортизированная, с расходом памяти)

При такой архитектуре используется общая память: отдельные копии данных не требуются. Подобная схема редко применяется для хэширования паролей, но широко используется в функциях proof-of-work криптовалют, в частности, Ethereum. Здесь уже финальный «счет в матче» — 16 параллельно сгенерированных хэшей против одного у защищающихся за то же время. 

Параллелизированная хэш-функция (распараллеленная, с большим расходом памяти)

В этом случае параллелизация реализована таким образом, что можно использовать мелкие ядра для вычисления каждого хэша, а память по-прежнему остается общей. Отчасти это связано с тем, что современные хэш-функции паролей с большим расходом памяти имеют настраиваемые параметры параллелизации. Если они высоки, то для подбора можно применить эту схему. Кроме того, многие хэш-функции имеют высокую степень внутренней параллелизации. Каковы же «итоги матча» в этот раз? 1 хэш за 1/16 от времени, которое защищающаяся сторона тратит на тот же результат. 

Параллелизированная хэш-функция (последовательная, с большим расходом памяти)

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

Параллелизированная хэш-функция (последовательная, с большим расходом памяти + большим расходом ПЗУ)

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

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

Это похоже на описанный выше proof of work Ethereum, но без большого расхода ОЗУ. При атаке используются ядра, ПЗУ, их порты и так далее, но потом атакующий упирается в ограничение пропускной способности памяти. Притом в защите эта схема, как минимум, не хуже классического Scrypt, потому что обеспечивает и большой расход памяти, и расход памяти с последовательным доступом.

Что понимается под ядром

Казалось бы, что тут непонятного? На показанных выше иллюстрациях ядром (core) называется любой обрабатывающий элемент, способный вычислять целевой хэш, не имея собственного большого объёма памяти. Мы предоставляем ядрам память, иногда делая её общей. Однако здесь могут возникать нюансы, так что стоит «сверить часы». 

Под ядром может также подразумеваться и обычное современное ядро CPU, и блок SIMD (single instruction, multiple data), например, в GPU CU или SM, и SIMD lane (в ядре CPU или в блоке GPU SIMD). Другой возможный вариант — этап конвейера (например, с различными командами вычислений хэша, которые перемежаются в суперскалярном CPU или GPU). Это может быть даже одноразрядное число в N-битном регистре файла регистра (когда мы обратили нашу задачу и теперь разделяем её на разряды). Но важнее всего то, что ядром может выступать логическая цепь FPGA или ASIC либо каждый этап конвейера в зависимости от контекста.

Разделение на биты (bitslicing)

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

Техника разделения на биты была придумана в 1997 году Эли Бихамом (см. «A Fast New DES Implementation in Software») и реализована примерно в сотне логических вентилей на один S-блок.

В том же году другой исследователь, Мэттью Кван, написал статью «Reducing the Gate Count of Bitslice DES», развив эти идеи. Сначала он снизил среднее количество необходимых вентилей до 87,75 (1997 год), а потом — до 51-56 (1998 год) в зависимости от доступных типов вентилей.

Другие исследователи продолжили работу. Уже знакомый нам Марк Беван достиг среднего количества вентилей в 45,5 с выборкой разрядов; Данго-Чу — 39,875, тоже с выборкой разрядов; Роман Русаков — 32,875 с выборкой разрядов и 44,125 — без неё; DeepLearningJohnDoe — 23,5 с LUT3; Sovyn Y. — 22,125 с LUT3 (пока не применяется в программах-взломщиках).

На AVX-512 bitslicing позволяет нам отбросить 512 вычисленных хэшей примерно за 9 шагов.

Ещё одна интересная особенность заключается в том, что сравнение «многие со многими» заменено функцией «многие с одним», но вычисляемой с логарифмической сложностью.

Подведём итог по оптимизациям скорости хэширования

Как видно из вышесказанного, современные и наиболее гибкие программы по подбору паролей (John the Ripper и Hashcat) поддерживают сотни различных типов и режимов хэширования на многих аппаратных платформах. Для оптимизации каждого типа и режима хэширования требуется масса усилий, так что степень оптимизации на данный момент различается в зависимости от инструментов и платформ. Есть способы многократно использовать оптимизации для разных типов хэшей и/или платформ. Среди таких высокоуровневых работ можно упомянуть john-devkit Алексея Черепанова и fast-small-crypto Аллена Эспиносы, являющиеся специализированными генераторами кода. 

OpenCL также абстрагирует большую часть этих процессов, поэтому последняя версия Hashcat использует его, отказавшись от ручной оптимизации под CPU. Также применяется настройка в среде исполнения, потому что при запуске скачанного взломщика паролей на вашей системе его производительность необязательно будет оптимальной. 

Автоматическая настройка есть и в John the Ripper, и в Hashcat, но иногда она находит субоптимальные параметры. Обычно пользователю необходимо начать подбор паролей за считанные секунды, и программа по подбору подстраивается под то, что смогла обнаружить за это короткое время. Притом иногда можно добиться лучших результатов при помощи ручной настройки.

Скорости для хэшей Unix

Теперь «взглянем на спидометр»: рассмотрим скорости взлома паролей в разных системах. 

Как уже отмечалось, в 1970-х годах Unix изменил тип хэшей, что отражено в таблице выше. Когда появился медленный хэш и 25 итераций, скорость взлома упала на два-три порядка. Затем скорость постепенно начала расти, во многом благодаря влиянию bitslicing, что также видно из приведенной таблицы. Например, можно сравнить разницу между Pentium и Alpha.

В дальнейшем методически разрабатывались различные улучшения, выполнялись реализации на FPGA и GPU. Скорости постепенно увеличивались. Как видно, сегодня GPU в шесть раз быстрее, чем последние реализации на CPU. 

Скорости для хэшей Windows

LOphtCrack 1.5 на Pentium Pro 200 проверял парольный файл с 10 паролями, использующими алфавитный набор (A-Z), за 26 часов. [...] [Примечание mudge: попробуйте собрать CLI-версию на Ultrasparc с использованием флагов компиляции в Makefile, и эти значения покажутся ужасно медленными» (1997 год).

Очевидно, ситуация с хэшами Windows не так хороша. Да, скорость взлома NTLM-хэшей выросла до сотен миллиардов в секунду, что даже выше, чем для LM-хэшей. Однако у первых хотя бы отсутствует ограничение на длину хэша, как у LM.

Разумеется, скорость в два терахэша в секунду — это повод отказаться от таких хэшей. На деле они всё ещё используются в Windows, хотя существует пентестинг баз данных пользовательских хэшей и аудит безопасности. И это кажется крайне неразумным. При пентестинге можно взломать один хэш, при аудите безопасности — 90%. Возможно, благодаря применению продуманных парольных политик такое значение удастся снизить до 50% или даже до 10%. Но всё равно показатель остается очень высоким, если, конечно, не использовать генерируемые пароли, которые могут помочь атакующим обойти проблему. 

Скорости для современных сильных хэшей

В этом плане нам интересен Argon2 — современная функция для генерации ключей, которая при этом имеет большую степень распараллеленности.

При параллельном вычислении 480 хэшей Argon2 (столько поместилось в память GPU) с помощью John the Ripper на GTX 1080 (max turbo, 180 Вт, игровой GPU 2016 года) мы получили следующие результаты:

0:00:00:28 0.03457g/s 1742p/s 1742c/s 1742C/S Dev#4:53C thrillerl..diamond

Благодаря bitslicing нам удалось использовать 50 тысяч «ядер». Разумеется, GPU не обладает таким количеством ядер, так что мы добились избыточной параллельности. Поскольку этапы конвейера тоже нужно заполнять, мы вычисляем примерно в пять раз больше инстансов компонента Argon2 с возможностью параллелизации, чем имеет оборудование для вычислений.

Для сравнения, на 2x Xeon E5-2670 + 8x DDR3-1600 (32 потока, суммарно 230 Вт, серверные CPU 2012 года) результаты были такими:

0:00:01:54 0.0O8726g/s 437.8p/s 437.8c/s 437.8C/S 050489..010591

Подведём итог по скоростям

Мы рассмотрели, как оптимизировать скорость: 

• хэширования; 

• сопоставления с загруженными хэшами.

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

В случае с современными сильными функциями скорости на одно устройство особо не изменились с 1970-х годов и в основном имеют порядок величин около 1000 проверок в секунду. При таких низких скоростях оказываются важнее другие задачи оптимизации, такие как: 

• формирование целевых словарей; 

• уникальность; 

• простота анализа; 

• обратная связь;

• структура обработки; 

• фокус атаки. 

Пожалуй, о некоторых из этих задач стоит поговорить отдельно. 

Фокус атаки на пароли

В любом деле важно оставаться в фокусе — атаки на пароли не исключение. В этом атакующим помимо прочего помогают генераторы кандидатов паролей.

Генераторы кандидатов паролей (1980-е)

Еще в 1983 году я написал простую и несовершенную программу для проверки слабых паролей. К сожалению, я поторопился передать коллеге из Калифорнийского университета в Беркли её копию, которую он добавил в пакет безопасности, применявшийся в учебном заведении. Позже кто-то распространил ее, после чего программа стала публично доступной.

Генераторы кандидатов паролей (начало 1990-х)

В 1991 году появилась программа Crack Алека Маффета.

Первый проход Crack делает с данными, взятыми из поля пользовательского пароля. В моем тестовом файле на этом проходе можно получить примерно 4% паролей (из суммарных предположительных 15%). Кроме того, этот проход выполняется очень быстро, потому что работает с малым объёмом данных, которые крайне часто используются в качестве паролей.

Первый прогон второго прохода, состоящий из словарных статей в нижнем регистре, дает ещё примерно 5% паролей. Длительность первого прогона зависит от количества поддерживаемых CPU и словарей, но при использовании /usr/dict/words из Ultrix и моего bad_pws.dat на четырёх CPU он не занимает больше нескольких часов.

В дальнейших прогонах процент взломанных паролей постепенно снижается: 2%, 1%, 0,5%… Но они принадлежат людям с достаточно экзотическими паролями, поэтому логично, что для взлома потребуется какое-то время.

Руководство пользователя Crack Алека Маффета.

Генераторы кандидатов паролей (середина 1990-х)

В середине 1990-х годов программа Crack существенно усовершенствовалась, что упростило задачу фокуса атаки на пароли. Снова обратимся к руководству пользователя Crack Алека Маффета:

Crack 5.0 поддерживает концепцию словарных групп — сличения слов, взятых из выборки сырых текстовых словарей (с одним словом на строку). Это позволяет пользователю группировать словари в «наиболее вероятные», «менее вероятные» и «наименее вероятные» для генерации успешных предполагаемых паролей…

При запуске Crack создаётся ещё две группы словарей: «gecos» и «gcperm». Группа «gecos» содержит только слова, непосредственно извлеченные из информации, хранящейся в файле паролей. Группа «gcperm» содержит слова, механически созданные перестановками и комбинациями частей слов, содержащихся в файле паролей (например, «Alec Muffett» превращается в «AMuffett», «AlecM» и так далее)...

При работе взломщик последовательно использует правила модификации и применяет их к группе словарей.

Примеры правил модификации

Правила модификации — это микрокоманды, по одной на строку, определяющие паттерны и действия, применяемые к словам из словаря для генерации последовательности кандидатов паролей.

Вот пример такого правила: /ese3u. Оно выбирает слова, содержащие букву «e», заменяет её цифрой «3» и преобразует остальную часть слова в верхний регистр (также можно использовать /e se3 u).

Такая система появилась в Crack 4.0 (ноябрь 1991 года) и поддерживалась до Crack 5.0 (декабрь 1996 года). Она была использована и расширена в John the Ripper (1996 год и далее), в инструментах InsidePro, в Hashcat.

Эволюция правил модификации

1. В John the Ripper: препроцессор, флаги отказа от правил (например, пропуск правила, если хэш нечувствителен к регистру), команды для пар слов (используется только для имён и фамилий, пример: johnsmith -> John Smith, John_Smith, John-Smith -p-c 1 <- (?a c $[ _\-] 2 (?a c), другие дополнительные команды.

2. Те же и дополнительные команды в InsidePro PasswordsPro и Hash Manager.

3. Те же и дополнительные команды в Hashcat (начиная с PasswordsPro).

4. «Первый в мире и единственный движок правил внутри ядра» Hashcat (OpenCL и CUDA).

5. Режим совместимости с Hashcat в John the Ripper.

Наборы правил модификации

Старые стандартные правила John the Ripper писались вручную, одни из них предоставляли возможности настройки, другие нет. В свою очередь, правила KoreLogic (2010 год) нацелены на пользователей, имеющих дело с парольными политиками. KoreLogic уже позволяют использовать препроцессор (гораздо более короткий набор, расширяемый примерно до 7 миллионов правил). 

Другие правила — InsidePro PasswordsPro — были импортированы сообществом пользователей Hashcat. За долгие годы сообществом было создано множество новых наборов правил (как написанных вручную, так и генерируемых). В результате проведения соревнований Hashcat best64 было выявлены 64 самых эффективных правила, позволяющих взламывать пароли с наибольшей вероятностью.

OneRuleToRuleThemAll — лучшие 25% из всех правил Hashcat (порядка 52 тысяч правил).

OneRuleToRuleThemStill — ещё более оптимизированный набор (около 49 тысяч правил).

Позже появились правила парольных фраз для Hashcat и John the Ripper (некоторые из них требуют особых входных данных), а также набор правил «All» John the Ripper (использующий вложенные директивы include) размером примерно в 11 миллионов.

Настройка наборов правил модификации

Еще в 2012 году исследователь Симон Марешал занимался автоматической генерацией правил модификации (Rulesfinder) специально для John the Ripper, но в результате его работы не были интегрированы в проект. Изначальную реализацию Rulesfinder забросили, и проект был возрожден только в 2020 году.

В 2022 году в John the Ripper была добавлена функция PerRuleStats, которую применили для изменения порядка 7,6 тысяч строк вывода препроцессора из некоторых созданных вручную правил — теперь они используются по умолчанию.

Благодаря этому «были уменьшены веса, определяющие количество предположений и каждое правило на каждый тестируемый кандидат пароля». Такой порядок хорошо подходит для быстрых и среднескоростных хэшей. Он сгенерирован на основании вывода pwned-passwords-sampler для HIBP v8 (100 миллионов неуникальных, примерно 54 миллионов уникальных хэшей), учитывая уникальные предположения.

Правила были вручную разделены на лучшие (40%), средние (следующие 40%) и худшие (последние 20%). Соответственно, первые обеспечивают основную часть взломов (более 97%), вторые — чуть более 2%, а третьи не дают никаких результатов.

Создание целевых словарей 

Здесь ключевой момент заключается в том, что под каждый хэш собирается свой словарь, основанный на информации о конкретном пользователе.

Дубликаты кандидатов паролей

Теперь поговорим о проблеме, которая часто возникает из-за наличия схожих входных паролей. Рассмотрим следующие строки из списка распространенных паролей, используемые в качестве списка слов:

• password

• password1

• Password

При использовании правила модификации «l $1» (преобразование в нижний регистр и добавление цифры 1) получим следующее:

• password1

• password11

• password1

Как видно, в списке появился дубликат. Кроме того, «password1» — это дубликат из изначального списка слов.

Устранение дубликатов кандидатов паролей

Как же бороться с обозначенной выше проблемой? В правилах программы Crack поддерживалось множество команд «отклонить слово если/если не...», которые можно было использовать, чтобы избежать генерации дубликатов слов. В John the Ripper было добавлено больше команд отклонения слов, а также флаги отклонения правил. Эти команды активно используются в стандартном наборе правил, что является нетривиальной задачей. Если входные списки слов ограничены только нижним регистром, то получается эффективно бороться с дубликатами. Особенно благополучно все складывается, если передать на вход список распространённых паролей. Например, при наличии 89,6% уникальных кандидатов паролей для стандартного списка слов и примерно 3 тысяч правил алгоритм подавления дубликатов кандидатов паролей, использующий 256 МБ ОЗУ, улучшает этот показатель до 94,3%, создавая выходной поток примерно в 50 ГБ.

В наборах правил Hashcat обычно не применяется (или почти не применяется) отбрасывание слов, из-за чего возникает гораздо больше дубликатов (например, при наличии 59,7% уникальных кандидатов для того же списка слов с лучшими 3 тысячами правил из OneRuleToRuleThemStill в режиме совместимости с John the Ripper алгоритм подавления дубликатов, занимающий 256 МБ ОЗУ, улучшает этот показатель до 80,6%.

Подавление дубликатов кандидатов паролей

Перефразируя известную максиму, не можешь устранить — подавляй. Функция «single crack» John the Ripper использует небольшие кольцевые буферы для каждой соли (а также хэш-таблицы для быстрого поиска), выявляя и подавляя недавно встреченных кандидатов.

С 2018 года Hashcat поддерживает «мозговую» функциональность для анализа кандидатов паролей. Вот некоторые ее преимущества.

1. Сетевая архитектура клиент-сервер позволяет подавлять дубликаты между задачами.

2. Такая функциональность требует лишь несложной ручной настройки даже для локального использования с одной задачей.

3. По документации сервер имеет ограничение производительности примерно в 50 тысяч паролей в секунду.

4. Функциональность записывает быстрые хэши кандидатов паролей на диск без ограничений и вытеснения.

В 2022 году появился отдельный подавитель дубликатов кандидатов паролей John the Ripper. Перечислим его основные особенности.

1. На данный момент работает с процессами по отдельности — не подавляет дубликаты между процессами.

2. По умолчанию включается, когда используются правила модификации. При низкой частоте попаданий и высокой скорости другой обработки происходит автоматическое отключение. Возможна настройка использования памяти. 

3. Скорость в несколько миллионов паролей в секунду, но последовательная и синхронизированная с остальными.

4. Обладает оппортунистическим (вероятностным) фильтром задаваемого размера и имеет вытеснение.

Подавитель дубликатов кандидатов паролей John the Ripper использует для хранения фингерпринтов (других быстрых хэшей) элементов хэш-таблицу. Она похожа на «кукушкин фильтр», только имеет не два, а лишь один потенциальный бакет для каждого элемента. В настоящее время бакеты имеют ширину 8 элементов. Когда бакет заполнен, мы просто вытесняем/заменяем фингерпринт (из второй половины).

Инструменты для устранения дубликатов из списков слов

Задача таких инструментов — удаление дублирующих строк без изменения и оптимизации их порядка. То есть сортировка дублирующих строк не производится, и не требуется место в памяти или на диске под весь вывод, за исключением этого вывода.

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

Среди других инструментов можно упомянуть следующее.

1. Duplicut (2014 год). В нём множественные потоки используются только тогда, когда файл достаточно велик, чтобы разбивать его на блоки.

2. Hashcat-utils rli (2015 год), написанную на C, и работающую в однопоточном режиме независимо от размера файла.

3. Rling. Более быстрая многопоточная альтернатива rli с большим количеством функций (2020 год) разработчика Waffle (автора программы подбора паролей MDXfind).

Парольные словари

В прошлом при подборе паролей крякеры просто использовали списки словарных слов. Небольшие публичные списки распространенных паролей появились ещё в 1980-х: вспомним хотя бы те, что использовал червь Морриса. Более длинный упорядоченный список поддерживался John the Ripper (1997 год и далее).

Ситуацию сильно изменила утечка RockYou (2009 год, 32,6 миллиона незашифрованных паролей, 14,3 миллиона уникальных): появилась большая выборка паролей, менее подверженная взлому. Эта выборка стала стандартом для обучения, тестирования и использования инструментов парольной безопасности.

По-прежнему применяются списки словарных слов (например, коллекция списков слов Openwall 2003 года, в которой объединено множество источников). Дополнительные публикуемые списки слов скрейпятся, например, из Википедии (Себастьян Раво, 2009, 2012; книги проекта «Гутенберг» (CrackStation, 2010 год).

Сообщества хэшкрякеров 

На форумах сообществ, например, InsidePro, hashkiller.co.uk, hashes.org (практически все они ныне недоступны) было собрано множество хэшей для взлома и незащищенных паролей, обычно без указания источников и имен пользователей.

Файлы с этих форумов также сохранялись сообществом оборонительной безопасности Have I Been Pwned (HIBP) или Pwned Passwords. Сотни миллионов реальных паролей, ранее обнаруженных при утечках данных, были опубликованы Троем Хантом в виде хэшей SHA-1 и NTLM (рехэшированные из открытого вида) вместе с количеством вхождений в утечках данных.

Инструмент passwdqc способен проактивно сверять новые пароли с HIBP в режиме оффлайн. Незашифрованные словари с hashes.org по-прежнему можно найти в других местах. Можно заново подобрать почти все пароли с HIBP и сгенерировать упорядоченный список утекших паролей.

Оптимизация словарей

HIBP v8 огромен: он содержит 847 миллионов уникальных паролей от нескольких миллиардов аккаунтов. Хотя трудно сказать, самая ли это большая коллекция. Что касается RockYou, то он меньше размером, но чище. Обе коллекции используются исследователями безопасности.

Нынешний password.1st из John the Ripper (2022 год, сгенерирован на то время для настройки набора правил модификации) основан на Pwned Passwords v8 (HIBP) с более чем сотней пересечений с RockYou. Инструмент отфильтрован таким образом, что требует более 97 пересечений поверх RockYou. Эти критерии подобраны так, чтобы пароль, используемый только одним человеком много раз, включался в список с очень малой вероятностью.

Сфокусированный список распространённых паролей содержит примерно 1,8 миллионов строк и весит примерно 15 МБ.

Очевидно, что распространять все эти словари совершенно этично, и они высокоэффективны.

Вероятностные генераторы кандидатов паролей (середина 1990-х)

А вот еще один подход, который облегчает подбор паролей. Это «методика генерации кандидатов паролей из статистической модели» (Симон Марешал, 2012 год). 

В 1995 году был разработан новый алгоритм для исчерпывающего поиска без дубликатов в пространстве ключей при движении вверх по 2D-поверхности Charset ** Length.

В John the Ripper 1.0 появился инкрементный режим (1996 год).

[Incremental:Alpha]

CharCount = 26

MinLen = 1

MaxLen = 8

CharsetB = smcbtdpajrhfIgkwneiovyzuqx

CharsetM = eaiornltsuchmdgpkbyvwfzxjq

CharsetE = erynsatldoghikmcwpfubzjxvq

Вероятностные генераторы кандидатов паролей (вторая половина 1990-х)

John the Ripper 1.0 можно ретроактивно назвать цепью Маркова нулевого порядка. 

Дополнительные модификации нулевого порядка были добавлены для статистики каждой длины и позиции.

Charset11 = ajyfioqxdehmnrstlcupbgkwvz

Charset21 = mdjpagetbrnsckyfilwhuoqvzx

Charset22 = olstabegrkjdhnvwcmpfiquxyz

Charset31 = dacjmbrtpslknfeghowqvzxiuy

Charset32 = aoeisumctgdblrfjpnvhwkxyzq

Charset33 = msnctdxepghlywabrjikuzofvq

В конце 1996 года Star Cracker разработчика The SOrCErEr вышел за рамки нулевого порядка.

В то же время появился второй порядок John the Ripper для каждой длины и позиции.

Вероятностные генераторы кандидатов паролей (конец 1990-х)

В конце 1996 года в John the Ripper появилось обучение на ранее взломанных паролях (чтение john.pot).

-makechars:<file> make a charset, <file> will be overwritten

В 1998 году John the Ripper 1.5 усовершенствовал поверхность для обхода с 2D до 3D. Тремя компонентами стали текущее количество виртуальных символов, длина и позиция фиксированного виртуального символа. Третий компонент был внутренним для более раннего алгоритма, но теперь стал явным. Под «виртуальным символом» подразумевается то, что он индексирует отсортированную строку, в которой может варьироваться до двух предыдущих символов (цепь Маркова второго порядка). В дальнейшем повышенная глубина детализации пригождается при параллельной или распределенной обработке.

Вероятностные генераторы кандидатов паролей (середина 2000-х)

В 2005 году вышла статья Арвинда Нараянана и Виталия Шматикова «Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff». Дадим слово исследователям.

«Нашим первым наблюдением стало то, что распределение букв в легко запоминаемых паролях, скорее всего, будет схоже с распределением букв в родном языке пользователей. Благодаря применению стандартных методик моделирования Маркова из natural language processing, это можно использовать для существенного уменьшения размера пространства поиска паролей. Нашим вторым вкладом стал алгоритм для эффективного перечисления оставшегося пространства паролей. Он позволяет применять методики выбора компромисса между временем и пространством, ограничивая доступ к памяти относительно малой таблицей размеров «частичного словаря» и позволяя реализовывать очень быструю атаку по словарю…

Мы заметили схожесть идей, использованных в этом алгоритме, с хорошо известным алгоритмом Витерби из сферы обработки голоса».

Вероятностные генераторы кандидатов паролей (начало 2010-х)

В 2007 году еще один исследователь, Симон Марешал, применил работу Нараянана и Шматикова к классическому взлому паролей.

В John the Ripper появился «Markov mode», добавленный Симоном Марешалом и расширенный Фрэнком Диттрихом и magnum (2007-2012 годы и далее). Это цепь Маркова первого порядка без разделения по длинам и позициям. В некоторых тестах она превосходит по результатам инкрементный режим, но требует сложного выбора длительности атак (указания минимальной и максимальной силы паролей). «Markov mode» поддерживает параллельную и распределенную обработку (ограничивая подинтервал узла). В работе Симона Марешала «Probabilistic password generators» 2012 года приведено сравнение множества вероятностных моделей (в том числе вариаций второго порядка).

Вероятностные генераторы кандидатов паролей (2010-е)

Позже выполнялись дальнейшие научные исследования, в частности, вышла статья Мэтта Вейра и его коллег «Password Cracking Using Probabilistic Context-Free Grammars» (2009 год) или «Pretty Cool Fuzzy Guesser (PCFG)». Приведем цитату из нее.

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

В 2013 году появилась статья Маркуса Дермута и коллег «OMEN: Faster Password Guessing Using an Ordered Markov Enumerator».

«В работе Нараянана и коллег индексирование выполнялось не в порядке уменьшения вероятности. Мы составляем список паролей с приблизительно уменьшающейся вероятностью. Если рассматривать его на высоком уровне, наш алгоритм дискретизирует вероятности в несколько блоков и итеративно обходит все эти блоки в порядке уменьшающейся вероятности (третьего порядка)».

Вероятностные генераторы кандидатов парольных фраз (2010-е и далее)

Вероятностные генераторы кандидатов паролей могут генерировать и фразы, если их обучить на таких входных данных (или просто на смешении паролей/фраз из реального мира). PCFG показывает более качественные результаты, чем посимвольные цепи Маркова.

«Phraser — это генератор фраз, использующий n-граммы и цепи Маркова для генерации фраз с целью взлома парольных фраз»; написан на C# для Windows (2015 год).

«RePhraser — это переписанный на Python Phraser, использующий цепи Маркова для лингвистически корректного взлома паролей» (2020 год). Также включает в себя созданные вручную и сгенерированные наборы правил.

Вероятностная генерация кандидатов паролей при помощи нейронных сетей (2010-е и далее)

В 2016 году появилась статья Уильяма Мелихера и коллег «Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks». В ней исследована рекуррентная нейросеть (RNN), прогнозирующая следующий символ без дубликатов. Модель размером 60 МБ превосходила по производительности другие генераторы, но все же была слишком медленной, чтобы выходить за рамки 10 миллионов кандидатов. Поэтому она использовалась только в симуляции. Модель в 3 МБ показывает себя почти так же хорошо, затрачивая на JavaScript примерно 100 мс на один пароль.

Генеративно-состязательные сети (GAN) создают дубликаты (около 50% при 1 миллиарде паролей). Вот несколько интересных работ по этой теме:

1. «PassGAN: A Deep Learning Approach for Password Guessing» (2017 год).

2. «Improving Password Guessing via Representation Learning» (2019 год).

3. Работа Дэвида Биснера «Generative Deep Learning Techniques for Password Generation» (2020 год); использует VAE, WAE, GPT2 с тонкой настройкой. Вероятно, лучшая на данный момент.

4. «GNPassGAN: Improved Generative Adversarial Networks For Trawling Offline Password Guessing». «Создает на 88,03% больше паролей и генерирует на 31,69% меньше дубликатов», чем PassGAN, производительность которой уже превзошли (2022 год).

Паттерны гласных/согласных

В версиях John the Ripper с 1.0 по 1.4 существовал параметр Wordlike, который при значении Y включал встроенный фильтр слов (отфильтровывающий слова с двумя и более гласными подряд или с более чем двумя согласными). Он был необходим наряду с цепью Маркова нулевого порядка версии 1.0, которая присутствовала как опция и в версии 1.4 в целях экономии памяти (второй порядок требовал 4 МБ ОЗУ), и для возможности в ручном режиме задавать наборы символов для каждой позиции (схожей с появившемся в будущем «mask mode»).

В версии John the Ripper 1.5 уже не было нулевого порядка, так что от всего этого отказались.

Собственные генераторы кандидатов паролей (конец 1990-х)

В конце 1996 года — начале 1997 года в John the Ripper 1.3+ появился «external mode», позволявший писать собственные генераторы или фильтры кандидатов паролей на Cи-подобном языке в файле конфигурации. Этот код компилировался в стековую VM, реализованную как потоковый код. Применялись следующие оптимизации: кэш верхушки стека, multi-push, «Labels as Values» GCC. Также имелся опциональный JIT на 32-битные x86 (1997 год), от которого отказались в версии 1.5 (1998 год).

Собственные генераторы кандидатов паролей (2000-е и далее)

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

В InsidePro появился синтаксис масок, например, ?u?l?l?l20?d?d. Он основан на использовании записи классов символов из правил отклонения слов программы Crack и перечислении всех строк, соответствующих маске (например, от Aaaa2000 до Zzzz2099).

Hashcat также использовал этот синтаксис, впоследствии расширив реализацию до применения цепей Маркова.

Позже John the Ripper тоже начал применять этот синтаксис в качестве mask mode, расширяя его конструкциями, схожими с препроцессором правил, например, ?u?l?l?l20[0-2]?d

Гибридные режимы добавляют маску поверх более умного и медленного генератора (2010-е): 

• режимы Hashcat добавляют в начале или конце списка слов (с хоста) маску (на устройстве); 

• маска John the Ripper (на устройстве ) ?w обозначает «слово» другого режима (хоста).

Генераторы кандидатов парольных фраз (по большей мере 2010-е)

А вот в этой сфере ситуация, увы, далека от идеала. Однако и здесь есть кое-какие полезные разработки и инструменты. Перечислим некоторые из них.

1. Правила для словарей, которые добавляют заданные слова в начало или конец парольной фразы.

2. Простые скрипты на Perl для комбинирования слов, опубликованные в 2006 году. 

3. Combinator mode инструмента Нashcat (2 слова из двух списков, не вероятностные). Режим комбинирования в инструменте Hashcat позволяет генерировать пароли, соединяя по два слова из разных словарей. При этом используются фиксированные комбинации без учета вероятностных алгоритмов. Это значит, что пароли создаются по простому принципу склеивания слов, что может быть полезно для перебора с целью взлома паролей.

4. PRINCE (PRobability INfinite Chained Elements) — это метод генерации паролей, разработанный Atom в 2014 году. Он основан на использовании вероятностных моделей для создания последовательностей слов, которые могут быть более эффективными при атаке на пароли. Этот подход учитывает частоту использования слов и их комбинаций, что повышает шансы на успешный подбор по сравнению с простыми переборами.

5. Функции для создания парольных фраз с использованием правил модификации, которые применяются к фразам, а не к словарям (появились в 2019 году).

6. Списки парольных фраз, не вошедшие в релизы (появились в 2021 году). Например, все извлеченные последовательности 2-6 слов из книг проекта «Гутенберг», отсортированные от самых частых до самых редких.

Комбинации генераторов кандидатов паролей

Различные генераторы создают и уникальные, и частично пересекающиеся пароли. Желательно использовать разные генераторы и подавлять перекрёстные дубликаты. Однако на практике чаще всего применяются множественные генераторы, но без подавления. Стандартный вызов John the Ripper подавляет дубликаты между списком слов и проходами инкрементального режима. «Мозг» Hashcat может действовать так же. Ещё один способ подавления заключается в исчерпывающем переборе простых паттернов с последующим исключением их и сложных прогонов.

Генераторы можно оптимизировать для использования с некоторыми другими. Например, вероятностные генераторы обычно применяются после нескольких прогонов со списками слов. Обучение вероятностного генератора наиболее оптимальной работе зачастую может приводить к переобучению и взлому меньшего количества паролей вне списка слов. При сравнениях это часто не учитывается, что неверно.

Процесс подбора паролей

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

Существуют инструменты для автоматизации процесса и управления задачами. Их функциональность частично пересекается с распределенной обработкой и координацией команды. Такие инструменты, например, применяются в соревнованиях и работе «красных команд». На основе результатов соревнований команды пишут статьи, в частности, по соревнованиям Crack Me If You Can, проводимым с 2010 года. В таких статьях можно поискать полезную информацию об организации рабочего процесса.

Будущее взлома паролей

Скорости

Очевидно, в дальнейшем будет повышаться вычислительная мощность CPU, GPU и FPGA, что повлияет на скорость хэширования. Возможные способы противостоять этому — настройка генерации хэшей и ключей, добавление в алгоритмы дополнительных итераций и задействование большего объема памяти. Надеюсь, так можно будет ограничить скорость проверки той же тысячей в секунду на близких по стоимости машинах.

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

Среди менее крупных изменений можно ожидать дальнейшие оптимизации, например, скоро появится bitslicing хэшей Lotus/Domino.

Оптимальный порядок поиска

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

Фичи

Выделим несколько наиболее перспективных фичей в сфере подбора паролей. Прежде всего, это поддержка ПЗУ yescrypt. Нельзя забывать и об использовании обобщенной (unified) памяти NVIDIA, благодаря чему упрощается распределенная обработка (более простая настройка, динамическое переназначение, безопасность). Вместе с тем в перспективе появятся специализированные вспомогательные UI или LLM, которые упростят работу с программами, в том числе и для неопытных конечных пользователей.

Вместо выводов

Подбор паролей лишь на первый взгляд кажется простой задачей. Он обладает низким порогом входа и плавной кривой обучения, но создание собственных инструментов для подбора паролей требует серьезных знаний computer science и разработки с нетривиальными социальными аспектами. Это по-прежнему активно развивающаяся и высококонкурентная сфера, приветствующая новых участников. Здесь крайне важна эффективность и оптимизация работы, все большее значение приобретают победы в специализированных соревнованиях, успехи в подборе пассфраз к криптокошелькам и так далее.

Как и в любой другой сфере наступательной информационной безопасности, постоянно появляются новые методики и результаты, которые влияют на архитектуру и параметры очередных защитных средств. Например, Yescrypt был спроектирован с опорой на технологии и методики, реализованные в John the Ripper.