Вчера я наконец-то выпустил первую публичную версию Lamer News, это одновременно и реальный пример использования Redis в виде сайта напободие Hacker News, и проект совершенно независимого сайта про новости из мира программирования.
Проект был хорошо принят сообществом, и был в топе HN в течение некоторого времени. Спасибо за обратную связь.
После релиза я получил несколько просьб об изменении хэш-функции, которую я использовал для того, чтобы хэшировать пароли в БД:
Этот код использует SHA1 с солью. Как отметили читатели, это не самый безопасный выбор, поскольку есть способы вычислить SHA1 очень быстро. Через некоторое время люди хором начали твитить и писать в комментах одно и то же предложение: «используй BCrypt». Я предложил использовать вложенные SHA1 в цикле, чтобы избежать добавления новых зависимостей в коде (если вы проверите README, одной из целей является сделать код простым и с как можно меньшим количеством зависимостей). И тут это случилось: догма шифрования. Никаких рассуждений о криптопримитивах и их возможных применениях и комбинациях, просто тупо «используй BCrypt». В глазах этих товарищей программисты — просто тупые дроны, исполняющие гайдлайны, которые не могут ни в коем случае рассуждать о криптографии. Но об этом позже…
Давайте пока сделаем шаг назад и рассмотрим исходную проблему со всем этим, и насколько небезопасен этот код.
Проблема довольно легка для понимания, но лучше объясню в деталях. Чтобы не хранить пароли в БД в открытом виде, обычно их хэшируют.
Когда серверной части нужно аутентифицировать пользователя, она получает пароль в открытом виде, хэширует его заново и сравнивает с тем, что лежит в БД. Если совпадает, то аутентификация проходит успешно.
Однако что произойдет, если злоумышленник (назовем ее Ева) добудет дамп БД? У Евы будет набор хэшированных паролей, назовем их HP1, HP2, HP3,… Её цель – найти такую атаку, которая позволит превратить HP назад в P.
Алгоритм хеширования открыт, поэтому первое что Еве стоит сделать – это попытаться применить его к словарю, состоящему из распространенных слов. Если хэш от такого слова совпадает с тем, что лежит в базе – пароль найден. Заметим, что в английском языке не так уж и много слов, поэтому эта атака может быть проведена очень легко и быстро.
Но, возможно, наш пользователь, Боб, выбрал пароль, который нельзя найти в словаре, и не очень длинный.
Ева может генерировать все комбинации для паролей, скажем, до 6 символов в длину, и вычислить их хэш. Эта атака более сложна в вычислительном плане. Если пароль представляет собой бинарную строку, скажем, из 6 символов, то всего существует 256^6 комбинаций, а именно 281474976710656.
Если наш атакующий может вычислять миллиард хэшей в секунду (современные GPU позволяют такое, и не придется особо разоряться), то на взлом этого пароля потребуется:
Это всего лишь три дня, или, в среднем случае, даже полтора. Не хорошо! Это слишком просто. Есть и еще одна проблема, пользователь вряд ли будет использовать все 256 символов с равной вероятностью. Рассмотрим худший случай, это только 26 букв в нижнем регистре, никаких цифр и других символов. Возьмем на этот раз пароль длиной в 8 символов.
Есть 26 ^ 8 возможных паролей, а именно 208 827 064 576. На этот раз наш пароль может быть взломан за 208 секунд (или за половину этого времени в среднем).
Это определенно нехорошо. Насколько длинным должен быть наш буквенный пароль, чтобы быть недоступным для атакующего, который умеет вычислять миллиард хэшей в секунду?
14 символов будут подбираться в среднем 1024 года. Для 16 символов атакующий должен потратить 1382824 года. 12 символов будут сопротивляться в течение полутора лет (опять же, в среднем), это определенно мало для большинства приложений.
Так безопасен ли SHA1 для хэширования паролей? Да, если пользователь выбрал надежный пароль из 14 символов и более. В противном случае не очень безопасно. Все зависит от длины пароля, и не секрет, что у пользователей есть плохая привычка подбирать короткие и ненадежные пароли.
К сожалению, на самом деле всё хуже. Например, атаки против наших 12 символов пароля могут быть проведены мгновенно: можно потратить примерно три года и вычислить хэши для всех комбинаций и записать их в таблицу вида P -> HP.
Однако такая таблица занимает много места (86 792 терабайта, если быть точным), и это еще если предположить, что мы настолько компактно храним данные, что тратим всего один байт на пару P,HP (малодостижимая цель). Однако это реальная угроза, когда размер таблицы находится в разумных пределах.
Суть в том, что зачастую в криптографии атаки можно провести за счет большего места, вместо большего времени.
Хорошие новости заключаются в том, что есть способ предотвратить вычисление единой таблицы, подходящей для всех сайтов, использующих такой же алгоритм. Речь идет про использование “соли”. Соль – это (публичная) строка, которую мы складываем с нашим паролем перед хэшированием. Например, если соль у нас “lame”, а пароль “foo”, то мы будем вычислять
Таким образом, для табличной атаки, Еве надо будет вычислить хэши всех комбинаций паролей с одной и той же солью. Такая таблица будет бесполезна для атаки на другой сайт, который использует другую соль.
Мы можем улучшить еще немножко и хранить не просто HP, но еще и случайную соль. Когда мы создаем аккаунт для пользователя, мы также геренируем для него случайную соль и сохраняем в аккаунте. При таком подходе наши пароли еще в большей безопасности, потому что теперь атакующему придется вычислять таблицу для каждого пользователя отдельно. И еще одно интересное наблюдение: если у нас одна глобальная соль, то вероятность того, что она попадет в руки злоумышленнику больше, даже если пароли при этом останутся в безопасности. Если у нас индивидуальные соли, то это маловероятно.
Однако даже если мы предотвратим все табличные атаки, есть еще фундаментальная проблема: если пароль короткий и Ева в состоянии вычислить HASH 1 миллиард раз в секунду, то у нас проблемы.
Мы можем кое-что сделать в этом случае: использовать хэш-функцию, которая ниипаца медленная.
Существуют алгоритмы, которые очень медленны при вычислении как программно, так и железно. Или мы можем взять существующий алгоритм и сделать его очень медленным, используя его в цикле.
Например, Blowfish — это алгоритм шифрования с медленным алгоритмом разделения ключа (сам алгоритм довольно быстр, после выполнения разделения ключа (key scheduling), так что Blowfish не хорош, только если вы хотите зашифровать много коротких сообщений с разными ключами, но может быть быстрым, если надо зашифровать большое сообщение с одним ключом).
Факт того, что у Blowfish медленный алгоритм разделения ключа делает его хорошим кандидатом для HASH.
Так Niels Provos и David Mazières разработали алгоритм, названный Bcrypt, который может быть использован для хэширования паролей. Алгоритм был представлен в 1999 году и использует модифицированную версию алгоритма разделения ключа из Blowfish. Я не уверен, что анализ Blowfish может быть применен к Bcrypt. Также я не знаю в каком объеме выполнялся анализ самого Bcrypt, поэтому я не могу делать комментарии по поводу безопасности этого алгоритма.
Однако это популярный выбор, Provos и Mazières — два известных криптографа, так что, вероятно, алгоритм не имеет явных недостатков.
Как только мы начинаем использовать медленную хэш-функцию, у атакующего начинаются проблемы. Так, например, Bcrypt можно настраивать, делая его быстрее или медленнее. Если сделать его настолько медленный, что даже на хорошем железе не получится вычислить больше тысячи хешей в секунду, то это, вероятно, будет всё еще приемлемо для ваших пользователей, однако уже непрактично для Евы. Например, пароль из 8 символов, используя только буквы в нижнем регистре:
3,3 года (в среднем) для взлома пароля из 8 символов. Наверное, всё еще недостаточно секьюрно, но уж лучше чем считанные секунды.
Однако обратите внимание, что мы все еще не защищены от атаки по словарю. Если пользователь выбрал распространенное слово, то всё безнадежно. 30k хэшей по-прежнему можно вычислить за разумное время.
На текущий момент мы рассмотрели несколько интересных мыслей. Например, не существует такой схемы хэширования, которая защитит пользователей с плохими паролями. Очень важно заставлять пользователей добавлять заглавные буквы и/или цифры и прочие символы в пароль (в случае, если безопасность важна для вашего приложения).
Важно понимать, как вещи работают. Это плавно подводит нас к следующей мысли. После хора “используй bcrypt”, я ответил, что я мог бы использовать другое решение, основанное на повторении SHA1. Но, видимо, многие считают, что программист не должен понимать криптографию. Он должен воспринимать её как догму. Если у вас есть догмы, вы будете неважным программистом, скорее всего. Что если на вашей системе нет поддержки bcrypt, но вам надо на ней работать. Я предложил тривиальную схему:
Что за ересь! Я был сочтен глупцом, не понимающим, что это небезопасно сцеплять хэш-функции таким образом в цепочку, и так далее. Но что если немного подумать?
SHA1 — это хэш-функция. Он состоит из небольших шагов, называемых раундами, которые выполняются снова и снова. Здесь нет разделения ключа, потому что это не блочный шифр, эта функция просто сжимает входной поток битов в выходной значение фиксированной длины.
Важно понимать, что многие криптоалгоритмы основаны на идее, что можно взять более простую функцию и выполнить её несколько раз для усиления её эффекта. Эта концепция настолько важна, что иногда атака на алгоритм становится непрактичной, если добавить больше раундов. Иногда криптографы используют вариант алгоритма с уменьшенным количеством раундов просто для анализа алгоритма в более уязвимой форме, для того, чтобы лучше понять, насколько силен вариант с полным количеством раундов.
Так почему же просто не добавить много раундов? Это медленно. Даже криптограф-любитель может разработать алгоритм, который является безопасным и медленным. Хороший криптограф сможет найти компромисс между безопасностью и скоростью.
Но… так как теперь мы знаем про концепцию раундов, знаем, что в SHA1 нет алгоритма разделения ключа, что выходное значение функции зависит только от её входа, и что SHA1 не был разработан с учетом возможности реверсирования (получения исходного значения по хэшу).
Так что вполне естественно, что предложенная мной схема SHA1 (SHA1 (SHA1 (..))) будет делать именно это, добавлять раундов в SHA1. Из фундаментальных свойств SHA1 следует, что вычислительно невозможно написать такую функцию SHA1000, которая будет эквивалентна тысячекратному вложенному вызову SHA1 и при этом будет легко вычислима.
Обратите внимание, что результат SHA1 (SHA1 (..)) — это не то же самое, что добавить больше раундов внутрь SHA1, так как там есть еще пре- и постобработка.
И знаете что? Сегодня утром я обнаружил, что алгоритм PBKDF1 описанный в RFC2898 делает именно то, что я предложил.
Есть люди, которые очень рады показать вам путь, но если вы приглядитесь к ним, вы обнаружите, что они не имеют понятия о чем говорят. Пожалуйста, используйте проверенные стандарты, пробуйте писать безопасный код, но также используйте свой ум, узнавайте больше о криптографии и как вы можете комбинировать примитивы. Догмы – это отстой.
Пожалуй, не будет хорошей идеей программисту изобретать свой блочный шифр и потом пытаться его где-то использовать в полезных целях. Есть специально обученные люди для этого. Гораздо важнее понимать отдельные “кирпичики”, что можно сделать с помощью криптографии, как правильно использовать протоколы и так далее.
В заключение хочу сказать, что я отношусь спокойно, когда люди грубят мне, если при этом они правы. Высокомерие – не сильно большая беда, если она идет вместе с умом. Если же вместо этого высокомерие встречается с невежеством, то это действительно печальная история.
Проект был хорошо принят сообществом, и был в топе HN в течение некоторого времени. Спасибо за обратную связь.
После релиза я получил несколько просьб об изменении хэш-функции, которую я использовал для того, чтобы хэшировать пароли в БД:
# Turn the password into an hashed one, using
# SHA1(salt|password).
def hash_password(password)
Digest::SHA1.hexdigest(PasswordSalt+password)
end
Этот код использует SHA1 с солью. Как отметили читатели, это не самый безопасный выбор, поскольку есть способы вычислить SHA1 очень быстро. Через некоторое время люди хором начали твитить и писать в комментах одно и то же предложение: «используй BCrypt». Я предложил использовать вложенные SHA1 в цикле, чтобы избежать добавления новых зависимостей в коде (если вы проверите README, одной из целей является сделать код простым и с как можно меньшим количеством зависимостей). И тут это случилось: догма шифрования. Никаких рассуждений о криптопримитивах и их возможных применениях и комбинациях, просто тупо «используй BCrypt». В глазах этих товарищей программисты — просто тупые дроны, исполняющие гайдлайны, которые не могут ни в коем случае рассуждать о криптографии. Но об этом позже…
Давайте пока сделаем шаг назад и рассмотрим исходную проблему со всем этим, и насколько небезопасен этот код.
Проблема
Проблема довольно легка для понимания, но лучше объясню в деталях. Чтобы не хранить пароли в БД в открытом виде, обычно их хэшируют.
HP = HASH (password)
# HP – hashed password, хэшированный пароль
Когда серверной части нужно аутентифицировать пользователя, она получает пароль в открытом виде, хэширует его заново и сравнивает с тем, что лежит в БД. Если совпадает, то аутентификация проходит успешно.
Однако что произойдет, если злоумышленник (назовем ее Ева) добудет дамп БД? У Евы будет набор хэшированных паролей, назовем их HP1, HP2, HP3,… Её цель – найти такую атаку, которая позволит превратить HP назад в P.
Алгоритм хеширования открыт, поэтому первое что Еве стоит сделать – это попытаться применить его к словарю, состоящему из распространенных слов. Если хэш от такого слова совпадает с тем, что лежит в базе – пароль найден. Заметим, что в английском языке не так уж и много слов, поэтому эта атака может быть проведена очень легко и быстро.
Но, возможно, наш пользователь, Боб, выбрал пароль, который нельзя найти в словаре, и не очень длинный.
Ева может генерировать все комбинации для паролей, скажем, до 6 символов в длину, и вычислить их хэш. Эта атака более сложна в вычислительном плане. Если пароль представляет собой бинарную строку, скажем, из 6 символов, то всего существует 256^6 комбинаций, а именно 281474976710656.
Если наш атакующий может вычислять миллиард хэшей в секунду (современные GPU позволяют такое, и не придется особо разоряться), то на взлом этого пароля потребуется:
281474976710656 / 1000000000 = 281474 секунд
Это всего лишь три дня, или, в среднем случае, даже полтора. Не хорошо! Это слишком просто. Есть и еще одна проблема, пользователь вряд ли будет использовать все 256 символов с равной вероятностью. Рассмотрим худший случай, это только 26 букв в нижнем регистре, никаких цифр и других символов. Возьмем на этот раз пароль длиной в 8 символов.
Есть 26 ^ 8 возможных паролей, а именно 208 827 064 576. На этот раз наш пароль может быть взломан за 208 секунд (или за половину этого времени в среднем).
Это определенно нехорошо. Насколько длинным должен быть наш буквенный пароль, чтобы быть недоступным для атакующего, который умеет вычислять миллиард хэшей в секунду?
14 символов будут подбираться в среднем 1024 года. Для 16 символов атакующий должен потратить 1382824 года. 12 символов будут сопротивляться в течение полутора лет (опять же, в среднем), это определенно мало для большинства приложений.
Так безопасен ли SHA1 для хэширования паролей? Да, если пользователь выбрал надежный пароль из 14 символов и более. В противном случае не очень безопасно. Все зависит от длины пароля, и не секрет, что у пользователей есть плохая привычка подбирать короткие и ненадежные пароли.
Но всё даже еще хуже
К сожалению, на самом деле всё хуже. Например, атаки против наших 12 символов пароля могут быть проведены мгновенно: можно потратить примерно три года и вычислить хэши для всех комбинаций и записать их в таблицу вида P -> HP.
Однако такая таблица занимает много места (86 792 терабайта, если быть точным), и это еще если предположить, что мы настолько компактно храним данные, что тратим всего один байт на пару P,HP (малодостижимая цель). Однако это реальная угроза, когда размер таблицы находится в разумных пределах.
Суть в том, что зачастую в криптографии атаки можно провести за счет большего места, вместо большего времени.
Хорошие новости заключаются в том, что есть способ предотвратить вычисление единой таблицы, подходящей для всех сайтов, использующих такой же алгоритм. Речь идет про использование “соли”. Соль – это (публичная) строка, которую мы складываем с нашим паролем перед хэшированием. Например, если соль у нас “lame”, а пароль “foo”, то мы будем вычислять
HP = HASH ("foolame")
Таким образом, для табличной атаки, Еве надо будет вычислить хэши всех комбинаций паролей с одной и той же солью. Такая таблица будет бесполезна для атаки на другой сайт, который использует другую соль.
Случайные соли
Мы можем улучшить еще немножко и хранить не просто HP, но еще и случайную соль. Когда мы создаем аккаунт для пользователя, мы также геренируем для него случайную соль и сохраняем в аккаунте. При таком подходе наши пароли еще в большей безопасности, потому что теперь атакующему придется вычислять таблицу для каждого пользователя отдельно. И еще одно интересное наблюдение: если у нас одна глобальная соль, то вероятность того, что она попадет в руки злоумышленнику больше, даже если пароли при этом останутся в безопасности. Если у нас индивидуальные соли, то это маловероятно.
Замедляем хэш-функцию
Однако даже если мы предотвратим все табличные атаки, есть еще фундаментальная проблема: если пароль короткий и Ева в состоянии вычислить HASH 1 миллиард раз в секунду, то у нас проблемы.
Мы можем кое-что сделать в этом случае: использовать хэш-функцию, которая ниипаца медленная.
Существуют алгоритмы, которые очень медленны при вычислении как программно, так и железно. Или мы можем взять существующий алгоритм и сделать его очень медленным, используя его в цикле.
Например, Blowfish — это алгоритм шифрования с медленным алгоритмом разделения ключа (сам алгоритм довольно быстр, после выполнения разделения ключа (key scheduling), так что Blowfish не хорош, только если вы хотите зашифровать много коротких сообщений с разными ключами, но может быть быстрым, если надо зашифровать большое сообщение с одним ключом).
Факт того, что у Blowfish медленный алгоритм разделения ключа делает его хорошим кандидатом для HASH.
Так Niels Provos и David Mazières разработали алгоритм, названный Bcrypt, который может быть использован для хэширования паролей. Алгоритм был представлен в 1999 году и использует модифицированную версию алгоритма разделения ключа из Blowfish. Я не уверен, что анализ Blowfish может быть применен к Bcrypt. Также я не знаю в каком объеме выполнялся анализ самого Bcrypt, поэтому я не могу делать комментарии по поводу безопасности этого алгоритма.
Однако это популярный выбор, Provos и Mazières — два известных криптографа, так что, вероятно, алгоритм не имеет явных недостатков.
Как только мы начинаем использовать медленную хэш-функцию, у атакующего начинаются проблемы. Так, например, Bcrypt можно настраивать, делая его быстрее или медленнее. Если сделать его настолько медленный, что даже на хорошем железе не получится вычислить больше тысячи хешей в секунду, то это, вероятно, будет всё еще приемлемо для ваших пользователей, однако уже непрактично для Евы. Например, пароль из 8 символов, используя только буквы в нижнем регистре:
26 ^ 8 / 1000 / 3600 / 24 / 365 = 6,6218627782
3,3 года (в среднем) для взлома пароля из 8 символов. Наверное, всё еще недостаточно секьюрно, но уж лучше чем считанные секунды.
Однако обратите внимание, что мы все еще не защищены от атаки по словарю. Если пользователь выбрал распространенное слово, то всё безнадежно. 30k хэшей по-прежнему можно вычислить за разумное время.
Про догмы
На текущий момент мы рассмотрели несколько интересных мыслей. Например, не существует такой схемы хэширования, которая защитит пользователей с плохими паролями. Очень важно заставлять пользователей добавлять заглавные буквы и/или цифры и прочие символы в пароль (в случае, если безопасность важна для вашего приложения).
Важно понимать, как вещи работают. Это плавно подводит нас к следующей мысли. После хора “используй bcrypt”, я ответил, что я мог бы использовать другое решение, основанное на повторении SHA1. Но, видимо, многие считают, что программист не должен понимать криптографию. Он должен воспринимать её как догму. Если у вас есть догмы, вы будете неважным программистом, скорее всего. Что если на вашей системе нет поддержки bcrypt, но вам надо на ней работать. Я предложил тривиальную схему:
SHA1 (SHA1 (SHA1 (...( SHA1 (password | salt))))
Что за ересь! Я был сочтен глупцом, не понимающим, что это небезопасно сцеплять хэш-функции таким образом в цепочку, и так далее. Но что если немного подумать?
SHA1 — это хэш-функция. Он состоит из небольших шагов, называемых раундами, которые выполняются снова и снова. Здесь нет разделения ключа, потому что это не блочный шифр, эта функция просто сжимает входной поток битов в выходной значение фиксированной длины.
Важно понимать, что многие криптоалгоритмы основаны на идее, что можно взять более простую функцию и выполнить её несколько раз для усиления её эффекта. Эта концепция настолько важна, что иногда атака на алгоритм становится непрактичной, если добавить больше раундов. Иногда криптографы используют вариант алгоритма с уменьшенным количеством раундов просто для анализа алгоритма в более уязвимой форме, для того, чтобы лучше понять, насколько силен вариант с полным количеством раундов.
Так почему же просто не добавить много раундов? Это медленно. Даже криптограф-любитель может разработать алгоритм, который является безопасным и медленным. Хороший криптограф сможет найти компромисс между безопасностью и скоростью.
Но… так как теперь мы знаем про концепцию раундов, знаем, что в SHA1 нет алгоритма разделения ключа, что выходное значение функции зависит только от её входа, и что SHA1 не был разработан с учетом возможности реверсирования (получения исходного значения по хэшу).
Так что вполне естественно, что предложенная мной схема SHA1 (SHA1 (SHA1 (..))) будет делать именно это, добавлять раундов в SHA1. Из фундаментальных свойств SHA1 следует, что вычислительно невозможно написать такую функцию SHA1000, которая будет эквивалентна тысячекратному вложенному вызову SHA1 и при этом будет легко вычислима.
Обратите внимание, что результат SHA1 (SHA1 (..)) — это не то же самое, что добавить больше раундов внутрь SHA1, так как там есть еще пре- и постобработка.
И знаете что? Сегодня утром я обнаружил, что алгоритм PBKDF1 описанный в RFC2898 делает именно то, что я предложил.
Есть люди, которые очень рады показать вам путь, но если вы приглядитесь к ним, вы обнаружите, что они не имеют понятия о чем говорят. Пожалуйста, используйте проверенные стандарты, пробуйте писать безопасный код, но также используйте свой ум, узнавайте больше о криптографии и как вы можете комбинировать примитивы. Догмы – это отстой.
Пожалуй, не будет хорошей идеей программисту изобретать свой блочный шифр и потом пытаться его где-то использовать в полезных целях. Есть специально обученные люди для этого. Гораздо важнее понимать отдельные “кирпичики”, что можно сделать с помощью криптографии, как правильно использовать протоколы и так далее.
В заключение хочу сказать, что я отношусь спокойно, когда люди грубят мне, если при этом они правы. Высокомерие – не сильно большая беда, если она идет вместе с умом. Если же вместо этого высокомерие встречается с невежеством, то это действительно печальная история.