Какие требования предъявляются к хэш функциям которые используются для хранения паролей

Обновлено: 02.07.2024

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

Каждые несколько недель мы пересматриваем некоторые из любимых постов нашего читателя на протяжении всей истории сайта. Этот учебник был впервые опубликован в январе 2011 года.

1 отказ

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

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

Это достигается с помощью односторонней хэш-функции. «Односторонний» означает, что его очень трудно (или практически невозможно) повернуть вспять.

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

3 Использование хэш-функции для хранения паролей

Обычный процесс при регистрации пользователя:

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

И процесс входа в систему:

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

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

Обратите внимание, что оригинальный пароль нигде не был сохранен. Если база данных украдена, логины пользователей не могут быть скомпрометированы, верно? Ну, ответ «это зависит». Давайте посмотрим на некоторые потенциальные проблемы.

4 Проблема № 1: Столкновение хэша

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

Как это можно использовать?

В качестве примера я видел несколько старых скриптов, которые использовали crc32 () для хэширования паролей. Эта функция генерирует 32-битное целое в результате. Это означает, что есть только 2 ^ 32 (то есть 4 294 967 296) возможных результатов.

Давайте хешируем пароль:

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

Например, после выполнения этого точного сценария на моем компьютере в течение нескольких мгновений мне дали « MTIxMjY5MTAwNg== ». Давайте проверим это:

Как это можно предотвратить?

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

5 Задача № 2: Радужные таблицы

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

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

Эти таблицы могут содержать до миллионов или даже миллиардов строк.

Как это можно предотвратить?

Мы можем попробовать добавить «соль». Вот пример:

// use bunch of random characters, and it can be longer than this // this will NOT be found in any pre-built rainbow table

Что мы в основном делаем, это объединяем строку «соль» с паролями перед их хэшированием. Результирующая строка, очевидно, не будет ни на одном заранее построенном радужном столе. Но мы все еще не в безопасности!

6 Задача № 3: Радужные таблицы (снова)

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

Как это можно использовать?

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

Как это можно предотвратить?

Вместо этого мы можем использовать «уникальную соль», которая меняется для каждого пользователя.

Кандидатом на этот тип соли является значение идентификатора пользователя из базы данных:

Это предполагает, что идентификационный номер пользователя никогда не меняется, как это обычно бывает.

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

Этот метод защищает нас от Rainbow Tables, потому что теперь каждый пароль был добавлен с другим значением. Атакующий должен будет сгенерировать 10 миллионов отдельных Радужных Столов, что было бы совершенно непрактично.

7 Проблема № 4: скорость хэширования

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

Как это можно использовать?

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

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

Если пароль может содержать строчные, прописные буквы и цифры, то есть 62 (26 + 26 + 10) возможных символов.
Строка длиной 8 символов имеет 62 ^ 8 возможных версий. Это чуть более 218 трлн.
Со скоростью 1 миллиард хэшей в секунду это можно решить примерно за 60 часов.

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

Не стесняйтесь требовать пароли длиной 9 или 10 символов, однако вы можете начать раздражать некоторых из ваших пользователей.

Как это можно предотвратить?

Используйте более медленную хэш-функцию.

Представьте, что вы используете хеш-функцию, которая может запускаться только на одном оборудовании 1 миллион раз в секунду вместо 1 миллиарда раз в секунду. Затем злоумышленнику потребуется в 1000 раз больше времени, чтобы перебрать хэш. 60 часов превратились бы почти в 7 лет!

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

Постараюсь очень лаконично и быстро обрисовать ситуацию с хэшами.

Сразу определю какую задачу применения хешей буду рассматривать — аутентификация пользователей. Не токены восстановления паролей, не аутентификация запросов, не что-то еще. Это также не статья про защиту канала передачи данных, так что комментарии по challenge-response и SSL неуместны!

Матчасть (короткая)

Hash = хеш функция — (свертка) функция однозначного отображения строки (любой длины) на конечное множество (строку заданной длины).
Само число (строка) хеш — результат вычисления хеш-функции над данными.
Существуют криптографические и некриптографические (классифицируются отдельно, к ним относятся, например, контрольные суммы) хеш-функции.

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

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

стойкость к атакам перебора (прямой перебор и перебор по словарю)
невозможность поиска одинаковых паролей разных пользователей по хешам

Для выполнения первого требования нужно использовать стойкие в настоящее время (а не в 90х годах!) хеш-функции.
Для выполнения второго — к паролю перед хешированием добавляется случайная строка (соль). Таким образом, у двух пользователей с паролем «123456» будут разные соли «соль1» и «соль2», а соответственно и хеш-функции от «123456соль1» и «123456соль2» в базе тоже будут разные.

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

Используйте локальный параметр!

Чтобы усложнить жизнь при атаке перебора следует дописать соль к паролю, а не наоборот (для людей, которые пишут слева направо, конечно).
Так как хеш-функция, как правило, вычисляется последовательно по строке (требования поточности алгоритма), то злоумышленнику при переборе «соленых» хешей, будет проще, когда подхешовое выражение начинается с соли.
Проще потому, что он (злоумышленник) может предвычислить заранее хеш(соль) и далее считать хеш(соль)+хеш(пароль) уже куда быстрее (практически с той же скоростью, что и просто хеш(пароль)). Для всех паролей, что он будет перебирать.

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

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

Единственный раз мы (ONsec) ломали хеши с локальным параметром, выработав при этом тактику атаки на сам локальный параметр (регистрируемся в приложении, затем ищем в базе свой хеш, соль (свой пароль мы и так знаем) и перебираем ЛП). И тщетно. На длинах 16+ байт для современных функций хеширования — это очень дорого по железу. В итоге проще оказалось скомпрометировать систему аутентификации (проставить себе role=admin в базе через UPDATE ;) )

Защищайте свои хранилища надежно и грамотно!

Заключение

Буду реалистом — естественно, никто не станет переписывать свои проекты ради «каких-то» хешей. Но новые проекты можно писать на scrypt/bcrypt. А также — внедряйте локальный параметр даже на слабых MD5 — он правда помогает, проверено :)

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

В заключении, привожу скорости перебора хешей (единицы измерения — мегахэши в секунду, то есть количество ), полученных на карточке AMD Radeon 7990 стоимостью менее $1000 (даже по старому курсу):

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

Как известно, криптография призвана решать задачи обеспечения конфиденциальности, целостности, аутентификации, невозможности отказа от авторства, неотслеживаемости с использованием математических методов. Для решения ряда данных задач используются криптографические функции хэширования (hash-functions, MDC).

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

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

Невозможность отказа от авторства (использование хэш-функций при вычислении электронной цифровой подписи)

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

Идентификация с использованием паролей

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

Другие сферы использования хэш-функций

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

Блочные шифры (например, Shacal-2).
Поточные шифры.
Генераторы псевдослучайных чисел.

Итеративная конструкция Меркля-Дамгорда

По итеративному принципу построено абсолютное большинство хэш-функций, используемых в настоящее время на практике (например, хэш-функции MD5, SHA-1, семейство хэш-функций SHA-2, отечественный стандарт на хэш-функцию ГОСТ Р 34.11-94).

Наиболее распространенным способом построения ключевой хэш-функции является алгоритм HMAC. Данный алгоритм позволяет строить ключевую хэш-функцию на основе бесключевой.

Конструкция HMAC позволяет построить ключевую функцию хэширования на основе любой бесключевой хэш-функции. Данную конструкцию предложили в 1996 году М. Белларе (Mihir Bellare), Р. Канетти (Ran Canetti), Х. Кравчук (Hugo Krawczyk).

Ключевую хэш-функцию, построенную на основе бесключевой хэш-функции H с использованием конструкции HMAC, принято обозначать HMAC-H (например, HMAC-MD5).

Стойкость конструкции HMAC-H основана на криптографических свойствах хэш-функции H и длине используемого ключа. Конструкция HMAC стандартизирована организациями ANSI, IETF, ISO и NIST. Конструкция HMAC получила столь широкое применение, что само название «HMAC» стало по существу синонимом термина «ключевая хэш-функция».

Хэш-код создается функцией Н :

Хэш-функция Н должна применяться к блоку данных любой длины.
Хэш-функция Н должна создавать выход фиксированной длины.
Н(М) относительно легко (за полиномиальное время) вычисляется для любого значения М .
Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н(M)=h .
Для любого данного М вычислительно невозможно найти М′ ≠ M такое, что H(M)=H(M′) .
Вычислительно невозможно найти произвольную пару (M,M′) такую, что H(M)=H(M′) .

Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Шестое свойство защищает против класса атак, известных как атака "день рождения".

"Парадокс дня рождения"

Так называемый "парадокс дня рождения" состоит в следующем.

Первая задача. Каким должно быть число k , чтобы для данного значения X и значений Y₁, …, Y_k , каждое из которых принимает значения от 1 до n, вероятность того, что хотя бы для одного Y_i выполнялось равенство X=Y

Для одного значения Y вероятность того, что X=Y , равна 1/n .

Соответственно, вероятность того, что X ≠ Y , равна 1 – 1/n .

Если создать k значений, то вероятность того, что ни для одного из них не будет совпадений, равна произведению вероятностей, соответствующих одному значению, т.е. (1 – 1/n) k .

Следовательно, вероятность по крайней мере одного совпадения равна

P (X = Y_i) = 1 – (1 – 1/n) k

По формуле бинома Ньютона

$(1 – a)k = 1 – ka + \frac <k(k-1)> a^2 - … \approx 1 – ka$

Теперь рассмотрим вторую задачу. Обозначим P(n,k) вероятность того, что в множестве из k элементов, каждый из которых может принимать n значений, есть хотя бы два с одинаковыми значениями. Чему должно быть равно k , чтобы P(n,k) была бы больше 0,5 ?

Число различных способов выбора элементов таким образом, чтобы при этом не было дублей, равно

$n (n-1) … (n-k+1) \frac <n!>$

Всего возможных способов выбора элементов равно

Вероятность того, что дублей нет, равна

$\frac <n!>$

Вероятность того, что есть дубли, соответственно равна

$1 - \frac <n!>$

$P (n, k) = 1 – n! / ((n-k)! \times n^k) = 1 – (n \times (n-1) \times … \times (n-k-1)) / n^k = 1 – [ (n-1)/n \times (n-2)/n \times … \times (n-k+1)/n] = 1 – [( 1- 1/n) \times (1 – 2/n) \times … \times (1 – (k-1)/n)]$

Известно, что Если хэш-код имеет длину m бит, т.е. принимает 2 m значений, то

$k_1 – x \leg e^-^x$

$P (n, k) > 1 – [e^-1^/^n \times e^-^2^/^n \times … \times e^-^k^/^n]$

$\frac 1 2 = 1 – e^-^k^(^k^-^1^)^/^n$

$k (k-1) \approx k^2$

$k = \sqrt <(2n \times ln 2)> = 1,17 \sqrt n \approx \sqrt n = \sqrt = 2^m^/^2$

Подобный результат называется "парадоксом дня рождения", потому что в соответствии с приведенными выше рассуждениями для того, чтобы вероятность совпадения дней рождения у двух человек была больше 0,5, в группе должно быть всего 23 человека. Этот результат кажется удивительным, возможно, потому, что для каждого отдельного человека вероятность того, что с его днем рождения совпадет день рождения у кого-то другого в группе, достаточно мала.

Тем не менее, возможны различного рода атаки, основанные на "парадоксе дня рождения". Возможна следующая стратегия:

Вследствие этого длина хэш-кода должна быть достаточно большой. Длина, равная 64 битам, в настоящее время не считается безопасной. Пред-почтительнее, чтобы длина составляла не менее 100 битов.

Читайте также: