Хеширование паролей. Лекция №6

У Г А Т У
Общие сведения
Уфимский государственный авиационный технический университет
Хеширование паролей
Если пароли пользователей хранятся в системе напрямую, то доступ к системным файлам равносилен доступу к паролям
Можно хранить в системе только хеш-функции от паролей
Пользователь вводит пароль
От пароля вычисляется хеш-функция, после чего пароль стирается
Хеш-функция сравнивается с хранящейся в таблице
С помощью хеширования можно получить на основе пароля секретный ключ и потом использовать его для шифрования
Таблица проверки паролей

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Атаки на хешированные пароли и защита от них
Взлом полным перебором
Таблицы предрассчитанных цепочек
Радужные таблицы
Соленые пароли
Специализированные функции для хеширования паролей

У Г А Т У
Таблица полного перебора
Уфимский государственный авиационный технический университет
У злоумышленника есть доступ к базе хешей; его задача – подобрать пароль, соответствующий известной хеш-функции
Заданы хеш-функция от пароля h=f(p) и два множества – множество возможных хеш-функций H и множество предполагаемых паролей P
При взломе полным перебором необходимо рассчитывать h(p) для любых p, пока не найдется совпадение
Можно заранее рассчитать таблицу и искать по ней пароль, соответствующий хеш-функции
Недостаток – нужен большой объем памяти для хранения

У Г А Т У
Таблица предрассчитанных цепочек
Уфимский государственный авиационный технический университет

У Г А Т У
Таблица предрассчитанных цепочек
Уфимский государственный авиационный технический университет
Из цепочки удаляются все элементы кроме первого пароля и последней хеш-функции
Составляется таблица из множества таких цепочек
Необходимо по возможности охватить все множествo P
Поиск пароля px по известному h=hash(px) в таблице
шаг 1. поиск h в таблице
шаг 2. если h найдена – перерассчитать цепочку, которая ей кончается, и взять из нее нужный пароль
шаг 3. иначе h=hash(r(h))
шаг 4. повторять шаги 1-3, пока h не найдется
Таблица предрассчитанных цепочек

У Г А Т У
Таблица предрассчитанных цепочек
Уфимский государственный авиационный технический университет
Недостаток – чувствительность к коллизиям функции редукции
Разные цепочки могут сливаться друг с другом
Таблица оказывается избыточной
Часть паролей может оказаться неучтенной

У Г А Т У
Радужная таблица
Уфимский государственный авиационный технический университет

У Г А Т У
Соленые пароли
Уфимский государственный авиационный технический университет
Криптографическая соль [salt] – случайный код, который используется для обеспечения непредсказуемости при хешировании паролей
Либо h=HASH(p||s)
Либо в стандарте хеш-функции указан дополнительный параметр h=HASH(p,s)
В качестве соли может использоваться вектор инициализации
В файле проверки паролей хранятся значения соли и хеш-функции пароля для каждого пользователя
Преимущества:
Соль защищает от перебора паролей при помощи радужных таблиц
Если у пользователя есть два аккаунта с одним и тем же паролем, хеш-функция от этих паролей будет разная
Безопасная длина соли ~128 бит

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Атаки на хешированные пароли и защита от них
Специализированные функции для хеширования паролей
Общие сведения
PBKDF2
Scrypt

У Г А Т У
Общие сведения
Уфимский государственный авиационный технический университет
KDF
Функции формирования ключа [Key Derivation Function, KDF] – специализированные хеш-функции для получения ключей симметричного шифрования на основе произвольных данных
Также применяются для:
хеширования паролей
контроля целостности записей в распределенных реестрах
Если обычные ХФ должны по возможности вычисляться быстро, то вычисление KDF должно быть ресурсоемким и трудно распараллеливаемым
Обычные ХФ часто вычисляются от больших файлов, KDF как правило от небольших объемов данных

У Г А Т У
PBKDF2
Уфимский государственный авиационный технический университет
Password-based KDF, RSA Laboratories, 2000
Параметры:
K = PBKDF2 ( PRF, P, S, c, kLen)
PRF [pseudorandom function] «псевдослучайная функция» – используемый в рамках PBKDF2 алгоритм вычисления имитовставки (как правило, HMAC)
P - Пароль
S – соль
с – количество раундов (рекомендуется от 1000)
kLen – длина ключа в байтах

У Г А Т У
PBKDF2
Уфимский государственный авиационный технический университет
Длина ключа может быть различной
Ключ разбивается на блоки с такой же длиной, как у имитовставки
Каждый i-й блок K[i] вычисляется по следующему алгоритму:
U[0] = S||i; //суммарная длина S и i должна быть равна длине имитовставки
K[i] = 0;
для j от 1 до c
U[j] = PRF( P, U[j-1] ); // P трактуется как ОТ, а U - как ключ имитовставки
K[i] = xor( K[i], U[j] );
конец

У Г А Т У
PBKDF2
Уфимский государственный авиационный технический университет
WPA-PSK:
PBKDF2( HMAC-SHA2, P, ssid, 4096, 256 )
где ssid – идентификатор точки доступа
Р 50.1.111 2016
PBKDF2( HMAC-Стрибог-512, P, S, >1000, 256 )
Злоумышленник не может распараллелить вычисление PBKDF2, если длина выходного ключа меньше, чем длина блока
Однако можно параллельно вычислять хеши для разных вариантов пароля

У Г А Т У
scrypt
Уфимский государственный авиационный технический университет
Колин Персиваль, 2009
Для быстрого вычисления требуется большой объем оперативной памяти, поэтому распараллеливание на ПЛИС или GPU не дает значительного преимущества
В рамках стандарта используются:
PBKDF2 на основе HMAC от SHA256
алгоритм Salsa20/8 (Salsa20 c количеством раундов 8 вместо 20)
Параметры:
K = scrypt (P, S, c, r, p, kLen)
P – пароль
S – соль
с – количество раундов
r – размер блока в кибибитах (1 Киб = 128 Б = 1024 б)
p – степень параллельности
kLen – длина ключа

У Г А Т У
scrypt
Уфимский государственный авиационный технический университет
Алгоритм:
B = PBKDF2 (P,S,1,p*r*128) \\ B - массив из p блоков по 128*r байт
для i от 0 до p-1 выполнить B[i]=MIX(B[i],c)
K = PBKDF2(P,B,1,kLen)
Функция X = MIX( B, c ):
X = B
для i от 0 до (2^c)-1 выполнить
V[i] = X
X = BlockMIX(X)
конец
шаг 3. для i от 0 до (2^c)-1 выполнить
j = X mod 2^c
X = BlockMIX(X)
конец

У Г А Т У
scrypt
Уфимский государственный авиационный технический университет
Функция A = BlockMIX( B ):
// B - массив 64-битных блоков
r = length(B)/128
X = B[2*r-1]
для i от 0 до (2^c)-1 выполнить
X = Salsa20_8(X xor B[i])
Y[i] = X
конец
A = Y[0] || Y[2] || … || Y[2*r-2] || Y[1] || Y[3] || … || Y[2*r-1]
Выбор параметров алгоритма:
Требуемый объем оперативной памяти для быстрого вычисления 128*r*c байт
Рекомендуемая версия параметров с=16384 r=8 p=1
«Криптовалютная» (слабая) версия параметров с=1024 r=1 p=1