Как все мы знаем, пароли следует всегда хэшировать с помощью медленного алгоритма с использованием соли. Чаще всего применяют scrypt, bcrypt или PBKDF2, но этот пост не о том, какой алгоритм использовать. Вместо этого мы поговорим о том, что делать с хэшами дальше.
20- (или 32-) байтовые соль и хэш должны храниться в энергонезависимом, зарезервированном, надёжном хранилище, то есть обычно в реляционной базе данных. Но в каких именно таблицах их хранить? Чаще всего используется таблица со столбцами (user_id, salt, hash) или столбцы salt и hash могут быть в общей таблице Users. В обоих случаях хэш и соль находятся в отношении один-к-одному с пользователями.
Беда в том, что даже с подсоленными хэшами, хакерам слишком легко использовать словарные атаки, если они получат доступ к соли и хэшу конкретного пользователя. Допустим, что, благодаря медленному хэшированию, они могут проверить всего тысячу паролей в минуту. Вас может неприятно удивить то, какими слабыми паролями часто пользуются люди, и какой их процент можно взломать даже в этом случае.
Нам нужен способ проверить, верен ли пароль, с абсолютным минимумом риска раскрытия пароля любого пользователя, даже если злоумышленник имеет полный доступ к нашей системе и большие вычислительные мощности. История показывает, что стоит потратить немного времени и денег, чтобы сделать это настолько трудным, насколько возможно.
Мне пришла в голову идея хранить все хэши в такой таблице:
Заметьте отсутствие внешнего ключа: мы не знаем, какой хэш относится к какому пользователю. Соль по-прежнему хранится в отношении один-к-одному с пользователями.
При создании нового пользователя или изменении пароля существующего вы генерируете случайную соль, сохраняете её в данные пользователя, вычисляете хэш пароля с этой солью и вставляете результат в таблицу Hashes.
При попытке входа в систему вы находите соль, соответствующую имени пользователя, хэшируете с ней пароль, как обычно, и проверяете, есть ли результат в таблице. Если да, то пользователь допускается в систему. То есть вместо проверки того, совпадает ли этот хэш с хэшем конкретного пользователя, мы проверяем только то, есть ли такой хэш в системе вообще. Вы можете подумать, что эта проверка намного слабее обычной. И в принципе это так. Но пусть даже у вас в системе триллионы хэшей, размер хэша как минимум 160 бит, так что вероятность случайного совпадения меньше 10-18. Скорее в ваш сервер попадёт метеор, чем кто-то сумеет залогиниться с неправильным паролем!
Примечание: как указал один из читателей, хотя всегда следует случайно сгенерировать значения соли, в данном случае особенно важно использовать случайное и уникальное значение соли для каждого пользователя.
Дальше мы можем вставить столько фиктивных значений в таблицу хэшей, сколько потерпит наше оборудование. Для начала можно сгенерировать миллиард случайных значений.
Какие же выгоды мы получаем от отсутствия связи между хэшами и пользователями и от заполнения таблицы хэшей шумом? Во-первых, фиктивные хэши нельзя отличить от настоящих, то есть злоумышленникам придётся проверять всю таблицу на каждый сгенерированный пароль. Так что кроме мощности процессора им требуется и большая оперативная память: если таблица не влезает в память, то это убъёт их скорость. Я не уверен, но подозреваю, что это также создаст проблемы при использовании GPU для перебора. Во-вторых, чтобы хотя бы иметь шансы взломать перебором пароль хотя бы одного пользователя, нужна большая часть таблицы хэшей, если не вся. Вы можете сделать таблицу настолько большой, чтобы попытка скопировать существенную её часть была легко заметна.
Допустим, что вы вставили, как в предыдущем примере, миллиард случайных хэшей. Это 20 ГБ данных в таблице (на самом деле больше из-за накладных расходов на хранение в базе данных). Числа, которые нас интересуют в первую очередь — скорость EXISTS (для проверки пароля) и INSERT (для создания нового пользователя). Они должны быть достаточно быстры, чтобы наш сайт работал и пользователи их не замечали. Заметьте, что хэширование производится серверами приложения, а запросы — базой данных, так что мы разделяем нагрузку, которая потребуется хакерам для перебора.
Для проверки я создал на ноутбуте такую таблицу и после часа вставок в ней было сто миллионов рядов. При этом я всё ещё добавлял больше миллиона рядов в минуту, а профайлер сообщал, что запрос на существование занимает меньше 1 миллисекунды. Файл с базой данных занимал около 6 ГБ, из них 2.8 уходили на «данные», а 3.2 — на «индекс». Достаточно дешёвый сервер с 64--128 ГБ оперативной памяти должен легко справиться с миллиардами хэшей.
Так стоит ли игра свеч? Представим себе, как пошло бы дело, если бы эту схему использовал LinkedIn:
[Дополнение] Рассмотрим такой пример — хотя всего у Facebook хранится больше 100 ПБ данных, логины, соли и хэши всех 800 миллионов активных пользователей могут уместиться на одну флешку. Один недовольный программист может вынести их в кармане. Этот метод позволит предотвратить такую возможность.
[Дополнение №2] Какой-то гений в комментариях на Reddit назвал это «безопасностью через ожирение». Должен сказать, что мне нравится это название! Конечно, это только первая попытка найти следующий шаг в защите пользователей от самих себы. И вполне может оказаться, что в недалёком будущем понадобится перейти к следующему способу (так же образом, как сейчас миллионам сайтов нужно переходить от PBKDF2 к scrypt). Это несложно сделать: при логине пользователя он переводится на новую систему, а через некоторое время принудительно сбрасываются пароли неактивных пользователей.
20- (или 32-) байтовые соль и хэш должны храниться в энергонезависимом, зарезервированном, надёжном хранилище, то есть обычно в реляционной базе данных. Но в каких именно таблицах их хранить? Чаще всего используется таблица со столбцами (user_id, salt, hash) или столбцы salt и hash могут быть в общей таблице Users. В обоих случаях хэш и соль находятся в отношении один-к-одному с пользователями.
Беда в том, что даже с подсоленными хэшами, хакерам слишком легко использовать словарные атаки, если они получат доступ к соли и хэшу конкретного пользователя. Допустим, что, благодаря медленному хэшированию, они могут проверить всего тысячу паролей в минуту. Вас может неприятно удивить то, какими слабыми паролями часто пользуются люди, и какой их процент можно взломать даже в этом случае.
Нам нужен способ проверить, верен ли пароль, с абсолютным минимумом риска раскрытия пароля любого пользователя, даже если злоумышленник имеет полный доступ к нашей системе и большие вычислительные мощности. История показывает, что стоит потратить немного времени и денег, чтобы сделать это настолько трудным, насколько возможно.
Мне пришла в голову идея хранить все хэши в такой таблице:
CREATE TABLE [Hashes]
[Hash] [binary](20) NOT NULL,
CONSTRAINT [PK_Hashes] PRIMARY KEY NONCLUSTERED ([Hash] ASC)Заметьте отсутствие внешнего ключа: мы не знаем, какой хэш относится к какому пользователю. Соль по-прежнему хранится в отношении один-к-одному с пользователями.
При создании нового пользователя или изменении пароля существующего вы генерируете случайную соль, сохраняете её в данные пользователя, вычисляете хэш пароля с этой солью и вставляете результат в таблицу Hashes.
При попытке входа в систему вы находите соль, соответствующую имени пользователя, хэшируете с ней пароль, как обычно, и проверяете, есть ли результат в таблице. Если да, то пользователь допускается в систему. То есть вместо проверки того, совпадает ли этот хэш с хэшем конкретного пользователя, мы проверяем только то, есть ли такой хэш в системе вообще. Вы можете подумать, что эта проверка намного слабее обычной. И в принципе это так. Но пусть даже у вас в системе триллионы хэшей, размер хэша как минимум 160 бит, так что вероятность случайного совпадения меньше 10-18. Скорее в ваш сервер попадёт метеор, чем кто-то сумеет залогиниться с неправильным паролем!
Примечание: как указал один из читателей, хотя всегда следует случайно сгенерировать значения соли, в данном случае особенно важно использовать случайное и уникальное значение соли для каждого пользователя.
Дальше мы можем вставить столько фиктивных значений в таблицу хэшей, сколько потерпит наше оборудование. Для начала можно сгенерировать миллиард случайных значений.
Какие же выгоды мы получаем от отсутствия связи между хэшами и пользователями и от заполнения таблицы хэшей шумом? Во-первых, фиктивные хэши нельзя отличить от настоящих, то есть злоумышленникам придётся проверять всю таблицу на каждый сгенерированный пароль. Так что кроме мощности процессора им требуется и большая оперативная память: если таблица не влезает в память, то это убъёт их скорость. Я не уверен, но подозреваю, что это также создаст проблемы при использовании GPU для перебора. Во-вторых, чтобы хотя бы иметь шансы взломать перебором пароль хотя бы одного пользователя, нужна большая часть таблицы хэшей, если не вся. Вы можете сделать таблицу настолько большой, чтобы попытка скопировать существенную её часть была легко заметна.
Допустим, что вы вставили, как в предыдущем примере, миллиард случайных хэшей. Это 20 ГБ данных в таблице (на самом деле больше из-за накладных расходов на хранение в базе данных). Числа, которые нас интересуют в первую очередь — скорость EXISTS (для проверки пароля) и INSERT (для создания нового пользователя). Они должны быть достаточно быстры, чтобы наш сайт работал и пользователи их не замечали. Заметьте, что хэширование производится серверами приложения, а запросы — базой данных, так что мы разделяем нагрузку, которая потребуется хакерам для перебора.
Для проверки я создал на ноутбуте такую таблицу и после часа вставок в ней было сто миллионов рядов. При этом я всё ещё добавлял больше миллиона рядов в минуту, а профайлер сообщал, что запрос на существование занимает меньше 1 миллисекунды. Файл с базой данных занимал около 6 ГБ, из них 2.8 уходили на «данные», а 3.2 — на «индекс». Достаточно дешёвый сервер с 64--128 ГБ оперативной памяти должен легко справиться с миллиардами хэшей.
Так стоит ли игра свеч? Представим себе, как пошло бы дело, если бы эту схему использовал LinkedIn:
- В реальности:
- 6 миллионов хэшей, 120 МБ данных, все соответствуют настоящим паролям
- больше 2 миллионов паролей были взломаны за несколько часов
- С солью и медленным алгоритмом (PBKDF2):
- 6 миллионов хэшей, 6 миллионов солей, 200 МБ данных, все соответствуют настоящим паролям
- думаю, что около миллиона можно было бы взломать перебором, затратив меньше тысячи долларов на EC2
- С моей схемой:
- 100 миллиардов хэшей, 6 миллионов солей, больше 2 ТБ данных, 0,006% соответствуют настоящим паролям
[Дополнение] Рассмотрим такой пример — хотя всего у Facebook хранится больше 100 ПБ данных, логины, соли и хэши всех 800 миллионов активных пользователей могут уместиться на одну флешку. Один недовольный программист может вынести их в кармане. Этот метод позволит предотвратить такую возможность.
[Дополнение №2] Какой-то гений в комментариях на Reddit назвал это «безопасностью через ожирение». Должен сказать, что мне нравится это название! Конечно, это только первая попытка найти следующий шаг в защите пользователей от самих себы. И вполне может оказаться, что в недалёком будущем понадобится перейти к следующему способу (так же образом, как сейчас миллионам сайтов нужно переходить от PBKDF2 к scrypt). Это несложно сделать: при логине пользователя он переводится на новую систему, а через некоторое время принудительно сбрасываются пароли неактивных пользователей.
