Пароли и KDF: перебор, радужные таблицы, GPU

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

Тема разбирает хранение паролей от начала до конца. Сначала — почему хранить хеш недостаточно: одинаковые пароли дают одинаковые хеши, и одна утёкшая база превращается в словарь для следующей. Потом соль и перец, затем конструкции, замедляющие перебор: PBKDF2, scrypt, Argon2. Дальше — экономика атаки: сколько стоит перебор на GPU, что даёт радужная таблица и почему 2^32 вариантов — это не «много», а несколько минут. Завершается выбором параметров, при которых защита переживает ближайшие годы.

Почему пароли ломаются

Энтропия человеческого выбора

Люди выбирают пароли из маленького распределения: слова, имена, даты, шаблоны вроде Имя2024!. Оценки показывают, что реальная энтропия типичного пароля — десятки бит, а не сотни ⁸. Перебор по словарю с мутациями покрывает значительную долю реальных паролей, и именно поэтому важно не «сколько бит в пароле», а «сколько попыток в секунду может позволить себе противник».

Офлайн и онлайн

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

Хранение: хеш, соль, перец

Просто хеш

Если база хранит H(пароль), то одинаковые пароли выглядят одинаково, а готовая таблица «хеш → пароль» ломает всю базу мгновенно. Хеш без соли — это не protector, а отпечаток.

Соль

Соль — случайное значение, уникальное для каждой записи и хранимое рядом с хешем: H(salt || пароль). Она уничтожает предвычисления: таблица, построенная для одной соли, бесполезна для другой. Соль не обязана быть секретной — её задача уникальность, а не секретность.

Перец

Перец — секретное значение, общее для приложения и хранимое вне базы (в конфигурации, в HSM). Он защищает от сценария «утёкли только хеши»: без перца перебор невозможен даже при знании соли. Цена — ротация перца требует пересчёта всех хешей, и перец не спасает, если утекла и конфигурация.

Медленные KDF

Соль и перец не мешают перебирать конкретный пароль — они лишь запрещают предвычисления. Замедляет перебор функция выработки ключа: PBKDF2 с большим числом итераций, scrypt с большими N, r, p, Argon2id с памятью. Идея одна: сделать каждую попытку дорогой по времени и памяти, чтобы преимущество GPU и ASIC уменьшилось ¹²³.

PBKDF2:  DK = F(P, S, c, dkLen)      c итераций HMAC
scrypt:  DK = scrypt(P, S, N, r, p)   память ~128·N·r байт
Argon2id: память m, проходы t, параллелизм p

PBKDF2 дёшев по памяти, поэтому хорошо параллелится на GPU. scrypt требует памяти, что ограничивает параллелизм. Argon2id — современный выбор, учитывающий и память, и время, и устойчивость к сторонним каналам.

Парольный хеш — не то же самое, что KDF из ключа

Слово «KDF» покрывает две разные задачи, и путать их опасно. Первая — выработка ключа из уже случайного секрета: вход имеет полную энтропию, и задача функции — растянуть его, разделить по назначению и связать с контекстом. Для этого служит HKDF: Extract собирает энтропию, Expand выдаёт нужное число байт с метками. Вторая — хранение пароля: вход имеет низкую энтропию, и задача функции — сделать каждую попытку дорогой. Для этого служат PBKDF2, scrypt, Argon2id, и HKDF здесь не годится: он быстр по построению, а быстрота — именно то, чего нельзя давать перебирающему.

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

Перец без самодеятельности

Перец — секрет, общий для приложения, и стандартный способ его применения — не «дописать строку к паролю и надеяться», а передать его в KDF отдельным параметром: как ключ HMAC в PBKDF2, как дополнительный вход Argon2 или как ключ обёртки вокруг уже посчитанного хеша, хранимого в HSM. Конструкция H(pepper ‖ salt ‖ password) встречается в самодельных схемах и опасна тем, что её стойкость зависит от порядка и от того, что перец не попадёт в тот же дамп, что и хеши; кроме того, при ротации такой схемы приходится пересчитывать всё и следить, чтобы старые записи не сверялись с новым перцем. Перец хранится отдельно от базы (конфигурация, KMS, HSM), ротируется с пересчётом или с версионированием, и не считается секретом, если утечка базы и утечка конфигурации происходят вместе.

Онлайн-защита

Медленный KDF защищает только от офлайн-перебора по украденной базе. Пока база не украдена, пароль подбирают через сам сервис, и там работают другие меры: ограничение частоты попыток на аккаунт и на IP, экспоненциальная задержка, блокировка после серии неудач, обязательная многофакторная аутентификация для чувствительных операций, обнаружение credential stuffing по распределённым источникам и по спискам утёкших паролей, уведомление пользователя о входе с нового устройства. Проверка пароля по списку скомпрометированных (например, по диапазонам хешей) должна происходить при установке, а не после инцидента. Офлайн-стойкость и онлайн-стойкость — разные бюджеты, и оба нужны.

Экономика перебора

Скорость

Порядок величин: MD5 и SHA-1 на хорошей GPU — миллиарды в секунду; SHA-256 — сотни миллионов; PBKDF2 с 100 000 итераций — тысячи; scrypt с 64 МБ — сотни; Argon2id с 64 МБ — десятки. Разница в шесть-семь порядков — и есть вся защита.

Оценка

Для случайного пароля из алфавита A длины L число вариантов |A|^L. Для словаря с мутациями — число слов, умноженное на число шаблонов. Время — варианты, делённые на скорость. Отсюда практическое правило: подбирайте параметры так, чтобы одна попытка стоила порядка 0,1–0,5 секунды на целевом железе; тогда перебор миллиона словарных вариантов займёт сутки на каждую утёкшую запись.

Память важнее скорости

GPU силён в параллельных вычислениях с малым объёмом памяти на поток. Функция, требующая 64 МБ на попытку, вынуждает GPU обрабатывать десятки потоков вместо тысяч — выигрыш атакующего падает на порядки. Именно поэтому scrypt и Argon2 считаются лучше PBKDF2 при равном времени.

Радужные таблицы

Идея

Радужная таблица — компромисс между памятью и временем. Строятся цепочки: стартовое значение, затем h, затем R (reduction — сжатие хеша обратно в пространство паролей), и так t раз. В таблице хранятся только начало и конец цепочки. При поиске пароля по хешу цепочка «восстанавливается» от известного хеша и сверяется с концами ⁶⁷.

Почему соль их убивает

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

Что показывает учебная задача

В работе вы строите мини-таблицу для маленького пространства и видите выигрыш по памяти. Главный вывод: радужная таблица ускоряет перебор только при отсутствии соли и медленной KDF; вместе они закрывают этот путь полностью.

Утечки и повторное использование

Credential stuffing

Люди повторяют пароли. Утёкшая база одного сервиса становится словарём для другого, и это работает лучше любого перебора. Защита — не в KDF, а в организационных мерах: проверка паролей по утёкшим базам, второй фактор, ограничение попыток.

Что делать после утечки

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

Выбор параметров

Практические ориентиры

OWASP рекомендует PBKDF2-HMAC-SHA256 не менее 600 000 итераций, scrypt — N=2^17, r=8, p=1, Argon2id — 19 МиБ памяти, 2 прохода, 1 поток как минимум ⁵. NIST SP 800-63B требует, чтобы KDF была «дорогой» и параметры пересматривались ⁴. Конкретные числа меняются вслед за железом: важно не значение, а процедура — измерять на своём железе и обновлять.

Смена параметров

Параметры хранятся вместе с хешем (алгоритм, соль, итерации, память). При входе хеш проверяется старыми параметрами; если они устарели, пароль пересчитывается с новыми. Это позволяет обновлять защиту без сброса паролей.

Итоги темы

• Стойкость пароля определяется распределением, из которого его выбирают, и ценой одной попытки.
• Хеш без соли позволяет предвычисления и одинаковые отпечатки; соль обязательна.
• Перец защищает от утечки только хешей, но не заменяет KDF.
• Медленная KDF и память — основная защита от офлайн-перебора.
• Радужные таблицы бесполезны при уникальной соли.
• Параметры измеряются на своём железе и пересматриваются; смена параметров не требует сброса паролей.

Литература

1. RFC 8018: PKCS #5: Password-Based Cryptography Specification Version 2.1. 2017. — PBKDF2 и требования к параметрам.
2. RFC 7914: The scrypt Password-Based Key Derivation Function. 2016. — scrypt и его параметры.
3. RFC 9106: Argon2 Memory-Hard Function for Password Hashing and Proof-of-Work Applications. 2021. — Argon2id и рекомендации.
4. NIST. SP 800-63B: Digital Identity Guidelines — Authentication and Lifecycle Management. 2017. — требования к хранению аутентификаторов.
5. OWASP. Password Storage Cheat Sheet. — практические рекомендации по алгоритмам и параметрам.
6. Hellman M. A Cryptanalytic Time-Memory Trade-Off. IEEE Transactions on Information Theory, 1980. — идея компромисса память-время.
7. Oechslin P. Making a Faster Cryptanalytic Time-Memory Trade-Off. CRYPTO 2003. — радужные таблицы.
8. Bonneau J. The Science of Guessing: Analyzing an Anonymized Corpus of 70 Million Passwords. IEEE S&P 2012. — распределение реальных паролей.

Дополнительные материалы к апокрифу 8

Вопросы для самопроверки

1. Почему одинаковые пароли без соли выдают себя?
2. Что именно ломает соль — перебор или предвычисления?
3. В каком сценарии перец полезен, а в каком бесполезен?
4. Почему PBKDF2 параллелится на GPU лучше, чем scrypt?
5. Что ограничивает атакующего в Argon2id: время, память или и то и другое?
6. Как перевести скорость перебора во время атаки?
7. Почему 2^32 вариантов — это минуты, а не «много»?
8. Как устроена цепочка радужной таблицы?
9. Почему уникальная соль делает радужную таблицу бесполезной?
10. Чем credential stuffing отличается от перебора?
11. Как выбрать параметры KDF для своего сервиса?
12. Как обновлять параметры без сброса паролей?
13. Почему HKDF не заменяет PBKDF2 при хранении паролей?
14. Что делать после утечки базы?
15. Почему длина пароля важнее его «сложности»?

Глоссарий темы

Шпаргалка

cp kdf_template.py kdf.py     && python3 check_kdf.py
cp crack_template.py crack.py && python3 crack.py && python3 check_crack.py

Что почитать и посмотреть

• RFC 8018 — PBKDF2 и параметры.
• RFC 7914 — scrypt с тестовыми векторами.
• RFC 9106 — Argon2id и рекомендации по памяти.
• NIST SP 800-63B — требования к аутентификации и хранению.
• OWASP Password Storage Cheat Sheet — практические параметры.
• Hellman 1980 и Oechslin 2003 — компромисс память-время и радужные таблицы.
• Bonneau 2012 — наука угадывания паролей по корпусу в 70 миллионов.
• Документация hashlib.scrypt — https://docs.python.org/3/library/hashlib.html#hashlib.scrypt.

Углубление: почему память дороже скорости

GPU хорош там, где много независимых вычислений с малым состоянием: тысячи потоков выполняют одни и те же операции. Если функция требует 64 МБ на попытку, число одновременных попыток падает до десятков — карта с 24 ГБ памяти не может держать больше нескольких сотен контекстов. Именно поэтому scrypt и Argon2 при равном времени на одну попытку дают атакующему в десятки раз меньше попыток в секунду.

Отсюда практическое правило: при выборе параметров сначала выделяйте память, затем время. PBKDF2 с миллионом итераций всё равно остаётся функцией с крошечным состоянием, и специализированные ASIC считают её миллиардами в секунду.

Углубление: почему соль — это про уникальность, а не про секретность

Соль хранится рядом с хешем и потому известна противнику. Её задача — сделать каждую запись «отдельным миром»: нельзя построить одну таблицу на всю базу, нельзя сравнивать записи между собой, нельзя заранее посчитать хеши популярных паролей. Уникальность соли превращает атаку «один раз посчитать — много раз применить» в атаку «для каждой записи считай заново», а это ровно то, что делает медленная KDF дорогой.

Перец, наоборот, про секретность: он защищает от сценария, когда утекли только хеши. Если перец хранится в HSM и не попал в дамп, перебор невозможен даже при известной соли. Но перец не заменяет KDF: при утечке конфигурации он теряет смысл, а ротация требует пересчёта всех записей.

Углубление: сколько бит у пароля

Инженерная оценка: пароль из словаря с мутациями имеет энтропию порядка 20–30 бит; случайный пароль из 12 символов четырёх алфавитов — около 78 бит; фраза из четырёх случайных слов — около 52 бит. При скорости 10^12 попыток в секунду (GPU против MD5) 30 бит — это секунды, 52 бита — недели, 78 бит — миллионы лет. Но скорость зависит от KDF: с Argon2id, дающим 50 попыток в секунду, даже 30 бит растягиваются на годы.

Поэтому спор «длина или сложность» решается вместе с выбором KDF: длинная фраза плюс медленная KDF — практичный оптимум; короткий «сложный» пароль плюс быстрый хеш — катастрофа.

Лабораторная работа 8. Цена одной попытки

• Раздел курса: апокриф 8 «Пароли и KDF: перебор, радужные таблицы, GPU»

Введение

В «Сейфе» утекли хеши паролей. Разработчик хранил MD5(пароль) — «быстро и просто». Из шести записей пять вскрываются словарём с мутациями за секунды, а шестая (scrypt) требует уже совсем другого времени. Разница между этими двумя строками и есть тема: пароль защищает не алгоритм, а стоимость одной попытки.

Работа идёт от примитивов к экономике. Сначала PBKDF2, HKDF и scrypt своими руками и сверка с тестовыми векторами. Потом вскрытие учебной утечки: словарь, мутации, разные алгоритмы. Затем измерение скорости перебора и подбор параметров под бюджет времени. В продвинутой части — радужные таблицы, перец и миграция параметров без сброса паролей.

Части: KDF, вскрытие утечки, экономика перебора, радужные таблицы, продвинутая.

Цель работы

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

После выполнения работы получится:

• реализовывать PBKDF2, HKDF и scrypt и сверять с эталонными векторами;
• вскрывать утечку словарём с мутациями и видеть разницу между алгоритмами;
• измерять скорость перебора и переводить её во время атаки;
• подбирать число итераций под бюджет времени;
• объяснять, почему соль убивает радужные таблицы;
• формулировать политику параметров и их миграции.

Теоретический минимум

Разделы «Почему пароли ломаются», «Хранение: хеш, соль, перец», «Экономика перебора», «Радужные таблицы», «Выбор параметров» апокрифа 8. Ориентиры:

DK = PBKDF2(P, S, c, dkLen)      c итераций HMAC
DK = scrypt(P, S, N, r, p)       память ≈ 128·N·r байт
Argon2id: m КиБ, t проходов, p потоков
время = варианты / скорость

Перечень оснащения

Ubuntu 24.04, Python 3.10+. Права root не нужны. Архив lr-env.

mkdir -p ~/lab-apocrypha-08 && cd ~/lab-apocrypha-08
unzip ~/lr-env.zip
cp kdf_template.py kdf.py
python3 check_kdf.py

Заготовки копируются в файлы без суффикса _template: kdf.py, crack.py.

Порядок выполнения работы

В журнал записывайте: измеренную скорость перебора для каждого алгоритма, число итераций под бюджет, время вскрытия каждой записи и оценку полного перебора. Провал проверки записывайте причиной — неверная соль, перепутан порядок salt ‖ password, неверный dkLen, — а не отметкой «не вышло».

Часть 1. KDF

Задание

1. Реализуйте pbkdf2_sha256 и сверьте с hashlib.pbkdf2_hmac на итерациях 1, 2, 4096.
2. Реализуйте hkdf_extract, hkdf_expand, hkdf и сверьте с тестовым случаем RFC 5869.
3. Реализуйте scrypt_kdf с проверкой ограничений: n — степень двойки, n < 2^(16r), r·p < 2^30.
4. Реализуйте audit_leaked: найдите пароли в учебной базе, включая мутации (заглавная буква, суффиксы 1, !, 2024).
5. Реализуйте pick_pbkdf2_iterations: подберите число итераций под 50 и 200 мс.
6. Запустите python3 check_kdf.py: двенадцать проверок, включая векторы RFC.
7. Ответьте: почему HKDF не годится для хранения паролей, а PBKDF2 не годится для выработки сессионных ключей из общего секрета.

Что должно получиться

Двенадцать пройденных проверок, найденные пароли учебной базы и понимание, что HKDF и PBKDF2 решают разные задачи.

Часть 2. Вскрытие утечки

Задание

1. Реализуйте load_leaks, load_words, digest: соль в записи — hex-строка, для md5 и sha256 она приписывается слева; для pbkdf2 и scrypt берите параметры из записи.
2. Реализуйте crack_with_wordlist с мутациями: слово, слово с заглавной буквы, каждое с суффиксами 1, !, 2024.
3. Обходите записи в порядке возрастания стоимости: md5, sha256, затем pbkdf2, затем scrypt.
4. Запустите python3 crack.py, затем python3 check_crack.py.
5. Запишите, сколько времени заняла каждая запись. Во сколько раз scrypt дороже md5 при одном и том же словаре?
6. Ответьте: почему соль не мешает вскрытию конкретной записи, но мешает вскрытию всей базы сразу.

Что должно получиться

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

Часть 3. Экономика перебора

Задание

1. Реализуйте guesses_per_second: измерьте скорость вызовов KDF, усреднив десять запусков.
2. Реализуйте estimate_seconds и iterations_for_budget.
3. Посчитайте время полного перебора 2^32 и 2^40 вариантов для md5, pbkdf2 с 100 000 итераций и scrypt с 64 МБ.
4. Подберите число итераций PBKDF2 так, чтобы одна попытка стоила 0,2 секунды на вашем железе.
5. Оцените, за сколько лет перебирается словарь из 10 миллионов вариантов при вашей скорости.
6. Запустите python3 check_crack.py — формулы должны сойтись.
7. Ответьте: почему для защиты важнее память, чем число итераций, и в каких сценариях это меняется.

Что должно получиться

Таблица «алгоритм — скорость — время перебора 2^32», подобранные параметры и понимание, что бюджет времени задаёт политику.

Часть 4. Радужные таблицы

Задание

1. Постройте мини-таблицу для пространства из 10^4 паролей: цепочки длины 100, reduction — простое сжатие хеша в номер пароля.
2. Реализуйте поиск по таблице и измерьте время вскрытия против полного перебора.
3. Добавьте соль к хранению и покажите, что таблица становится бесполезной: для каждой соли нужна своя.
4. Оцените память таблицы (только начала и концы цепочек) и сравните с полным словарём.
5. Ответьте: почему радужная таблица — аргумент в пользу соли, а не против хеширования, и почему она не работает против PBKDF2 с большой солью.

Что должно получиться

Работающая мини-таблица, замер выигрыша по памяти и вывод о границах применимости.

Часть 5. Продвинутая: параметры, перец и миграция

Задание

1. Сравните на своём железе PBKDF2 (600 000 итераций), scrypt (N=2^17, r=8, p=1) и Argon2id (если доступен) по времени и памяти на одну попытку.
2. Сформулируйте политику: целевое время на вход, минимальные параметры, периодичность пересмотра.
3. Реализуйте перец: H(pepper ‖ salt ‖ password), хранение перца вне базы. Оцените, что произойдёт при ротации перца.
4. Реализуйте миграцию параметров: при успешном входе пересчитайте хеш с новыми параметрами и обновите запись.
5. Разберите сценарий: утекли только хеши, конфигурация осталась. Что даёт перец и чего он не даёт?
6. Сформулируйте чек-лист хранения паролей из семи пунктов.

Что должно получиться

Сравнительная таблица KDF, письменная политика, реализованная миграция и чек-лист, пригодный для ревью.

Журнал работы

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

Контрольные вопросы

1. Почему стойкость пароля определяется распределением, а не длиной?
2. Чем офлайн-атака отличается от онлайн и что защищает от каждой?
3. Зачем нужна соль и почему она не обязана быть секретной?
4. Что даёт перец и в каком сценарии он бесполезен?
5. Почему PBKDF2 плохо сопротивляется GPU?
6. Что даёт память в scrypt и Argon2?
7. Как оценить время перебора по скорости и числу вариантов?
8. Почему радужные таблицы бесполезны при уникальной соли?
9. Чем HKDF отличается от PBKDF2 по назначению?
10. Как менять параметры KDF без сброса паролей?
11. Какие параметры считаются приемлемыми сегодня?
12. Что делать после утечки базы?