Комментарии 65
А bcrypt уже считается "устаревшим"?
Нельзя сказать, что устарел полностью, но Аргон его в какой-то степени превосходит: https://crypto.stackexchange.com/questions/30785/password-hashing-security-of-argon2-versus-bcrypt-pbkdf2
Мнение PHP-мэйтейнеров красноречиво: https://wiki.php.net/rfc/argon2_password_hash#resolved_inclusion_on_74
Они же проголосовали просто за включение, вроде никто bcrypt не убирает.
Но кажется что никаких причин срочно отказываться от bcrypt нет (как отказываются сейчас от SHA1 и MD5).
Они, по-моему, пока ревертнули этот коммит: https://github.com/php/php-src/pull/1997/commits/1bc381848add707db42671b3c33e1082aa3e7f93
Интересно, получилась ли версия с Runtime CPU dispatching в результате быстрее чем референс с march=native под конкретный сервер. Можно и на этапе деплоймента, а не в рантайме, разбираться какие инструкции есть.
Разбираться с процессором на этапе деплоя можно, но это не всегда удобно (например, при деплое Docker-контейнеров). Тут многое зависит от вашей системы деплоя. Для нас просто runtime CPU dispatching это самое удобное, что можно сделать.
Ну в принципе можно прямо внутри контейнера выбирать с какой версией библиотеки линковать или даже какой скомпилированный бинарник запускать (при static-linkage). Наверное, можно и через dlopen. Но не ясно что дешевле — поддерживать разные имплементации или сборку для разных targets.
Несколько бинарей или dlopen будут работать, но это же тот же runtime CPU dispatching, только чуть по-другому.
Нет, компилятор тащить я совсем не предлагал. Я предлагал заранее собрать под каждый хост свой бинарник/библиотеку через -march=native, не используя специальных реализаций, и при запуске выбирать нужное, для чего мне пришли в голову 3 вышеперечисленных способа.
То есть тут сложность поддержки реализации заменяется сложностью сборки под каждый хост.
Можно и на этапе деплоймента
Неудобно когда ферма — зоопарк из машин «что было — то и запилили».
1. Использование большого количества RAM...
Доступ к глобальной памяти (которой является RAM) для всех дорогой — и для CPU тоже.
2. Использование чтений/записей малого количества данных по случайным адресам в маленьком регионе памяти, который помещается в L1-кэш (если попытаться прочитать 4 байта из GPU global memory, то на самом деле будет прочитано 32 байта, что заставляет GPU впустую использовать шину памяти).
Есть такая штука, как локальная память, разделяемая внутри кластера потоковых процессоров на GPU. Время доступа — несколько тактов. И кэши данных у GPU тоже есть, просто они распределены и меньшего объёма.
4. Использование так называемого instruction-level parallelism и алгоритма хешировния SIMD-friendly design. Современные CPU несут на борту разные advanced-наборы инструкций типа SSE2, SSSE3, AVX2 и т. д., которые позволяют проводить несколько операций за один раз и значительно ускорить вычисления.
SIMD вычисления — это то, ради чего GPU были сделаны.
В общем, анализ так себе.
Доступ к глобальной памяти (которой является RAM) для всех дорогой — и для CPU тоже.
Все верно, но в серверных CPU есть большой L3 кэш, который позволяет все ускорить.
Есть такая штука, как локальная память, разделяемая внутри кластера потоковых процессоров на GPU. Время доступа — несколько тактов. И кэши данных у GPU тоже есть, просто они распределены и меньшего объёма.
А где-то утверждается, что кешей или локальной памяти в GPU нет?
Пример с использованием чтений/записей по случайным адресам взят из bcrypt, который использует всего 4кб.
Бенчмарки bcrypt CPU vs GPU убедительно доказывают, что чтения/записи 4 байт по случайным адресам в регионе 4кб сильно снижают эффективность GPU.
Наверняка сами знаете, что в некоторых моделях GPU даже 4кб быстрой памяти на поток это роскошь.
SIMD вычисления — это то, ради чего GPU были сделаны.
Просто неудачная фраза, смысл в том, что алгоритмы оптимизированы под x64 с учетом наборов инструкций типа SSE2…
В общем, анализ так себе.
Негативный фидбек тоже важен для нас
За пояснения спасибо.
Ну OpenMP как бы более высокий уровень скорее являющийся аналогом параллельных алгоритмов из 17 стандарта
Не совсем понятен следующий переход:
Нужно максимально замедлить перебор хэшей на GPU/etc взломщика, поэтому вы ускоряете(!) реализации(!) алгоритмов на своих(!) CPU.
Как уже отмечалось выше, GPU также имеют кэши и прочие "радости" из мира CPU. Нужно очень постараться, чтобы создать криптоалгоритмы (не реализации!), плохо пригодные для реализации на GPU. Насколько я понимаю, основная проблема тут не в архитектурах железа, а в том, что создание своих алгоритмов (хэширования) в мире криптографии не приветствуется.
Не лучше ли солить хэши?
Хеши же наверняка солёные. Я думаю что защищаются от того чтобы по дампу базы нельзя было бы сломать "словарные" пароли конкретных аккаунтов.
При хешировании у вас нет задачи это делать быстро — надо проверить один пароль. При брутфорсе надо проверить много. И тут задач стоит чтобы GPU вёл себя не лучше CPU. А дальше уже всё это можно как угодно ускорять — пользователей с паролем password таким способом всё равно не спасти.
К сожалению, комментарии dpantele для меня мало что прояснили.
Попытаюсь сформулировать вопрос по-другому.
1) Правильно я понимаю, что вы используете схему криптосистемы, как в bcrypt, где перебор хэшей затрудняется путём усложнения хэш-функции таким образом, что время её расчёта становится намного дольше?
2) Если ответ на вопрос (1) да, то каким образом влияет ваша реализация алгоритмов на реализацию взломщиков? Пример: вы считаете 1000 хэшей за время 1000T (1T времени/хэш), взломщик на ферме GPU считает 1 000 000 000 хэшей за время 1 000 000T (0.001T времени/хэш). Вы оптимизируете свой алгоритм, и начинаете считать 1000 хэшей за время 100T (0.1T времени/хэш). Реализация взломщика продолжает считать на скорости 0.001T времени/хэш. В чём профит?
(а)Предполагаю, что оптимизированный алгоритм вы можете запускать большее количество раз, и тогда взломщик должен пропорционально увеличить мощность ферм. Но с другой стороны, вы можете сами задействовать GPU, ведь взломщику всё равно считать больше, чем вам. AVX, SSE, это вот всё скорее всего проиграют GPU, но если утверждать это серьёзно, нужны тесты.
(б)Либо вы действительно разработали криптосистему, которая жрёт память объёмом в диапазоне от (размер кэша GPU) до (размер кэша серверного CPU), и поэтому любая её реализация принципиально тормозит на GPU, но не на CPU. В таком случае, хотелось бы увидеть схему этой криптосистемы.
3) Какое-то из предположений (а, б) верно, или ситуация принципиально иная?
1) Правильно я понимаю, что вы используете схему криптосистемы, как в bcrypt, где перебор хэшей затрудняется путём усложнения хэш-функции таким образом, что время её расчёта становится намного дольше?
Используется схема криптосистемы как в bcrypt, где перебор хешей усложняется таким образом, чтобы время расчета группы таких хешей на GPU максимально приближалось ко времени расчета хешей на CPU. Яндекс при логине пользователя всегда считает хеши на CPU. Посчитать нужно 1 хеш на пользователя. Хакеры считают на GPU сразу много, чтобы было быстрее. Профит в затруднении расчетов хешей именно на GPU для хакеров.
вы действительно разработали криптосистему
Яндекс не является разработчиком криптосистемы Аргон. Об этом написано в статье.
Сам я из подобного заимплементил Sphinx
webee.technion.ac.il/~hugo/sphinx.pdf
gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042
Чем-то напоминает пифию, но там всё гораздо проще. Правда никаких обновлений ключей и прочих наворотов.
подписывать запросы
Подписывать целиком HTTP запрос?
OpenMP вместо pthread. Вы не поверите в GCC оно работает таки поверх pthread. Afaik только в специфичных компиляторах и от вендоров e.g ICC, xlc оно работает на чем то своём
"Использование операции умножения MUL. На CPU она выполняется так же быстро, как и обычные операции типа сдвигов и ADD, но на FPGA и ASIC это приводит к более сложной конфигурации, большим задержкам в обработке данных и т. д." На FPGA современных вроде есть встроенные dsp поэтому пока их будет хватать, эффектов описанных в статье не будет даже рядом? Информация в статье точно актуальна?
Схемы быстрого умножения описаны в старой советской литературе 30-40 летней давности, не говоря о том, что можно купить готовые ядра.
Большие объемы памяти тоже не проблема — готовые контроллеры DDR есть на opencores. Та же RIVYERA V7-2000T дает 20Гб на FPGA.
Да, оно хорошо перебирается на GPU и остальном железе.
Каким образом? Если использовать радужные таблицы, они не особо помогут со взломом хеша с солью, или может я чего-то не понимаю?
Никто же не запрещает хранить соль вне БД, например в конфиге системыИ никто не запрещают сохранить себе эту соль (а заодно и всю базу) уволившемуся админу/разработчику.
Подразумевается именно сложность брутфорса при полностью скомпрометированных данных. Никаких security through obscurity. Секретная соль — это один слой защиты, невозможность распараллелить брутфорс — другой. Они никак не пересекаются, каждый слой выполняет свою задачу.
Но в любом случае, сколько бы тысяч итераций примитивного хеширования у вас не было, проблема остается: увеличив количество ядер в N раз, мы ускорим брутфорс в N раз.
Соль нужна:
- Как дополнительная защита на случай, если злоумышленники смогли получить доступ к базе, но не смогли получить доступ к алгоритму. Без соли этот алгоритм можно просто перебрать. Конечно же, вариантов алгоритмов может быть триллионы, но карты могут перебирать их квадриллионы в секунду, и даже квинтиллионы в секунду (при использовании одного раунда). А в одних сутках у нас 86400 секунд!
Соль из 5 символов усложнит перебор алгоритма в 10 млрд раз, соль из 10 символов — в 100 квинтиллионов раз и т. д. Ваша же идея тоже усложнит перебор, но максимум в 10–1000000 раз. Как минимум соль — это намного проще. - Чтобы Ваш алгоритм точно был уникальным. Если он будет неуникальным, то одновременно с Вашей базой можно заодно перебирать и 10 других баз или даже заюзать радужные таблицы.
- Чтобы разграничить права, кто к какой части имеет доступ.
Почему нельзя использовать использовать обычный sha1 с солью и большим количеством раундов?
Сложность паролей на сайтах обычно примерно в 500 млрд раз меньше, чем на паролях, защищённых от оффлайн-перебора. Соль спасает, но раз базу взломали, вполне могут и соль взломать. Самое хорошее в соли — на каждом сайте она своя, поэтому нельзя перебрать базы сразу от всех сайтов одновременно.
Нужно отметить, что хэш должен считаться не от пароля, от от логина+пароля+соль. В этом случае перебирать пароли придётся для каждого пользователя отдельно, что очень сильно усложняет перебор. Как результат — при такой хорошей защите соль влияет меньше, т. к. если взломано два сайта и две соли, но все логины разные, то и без соли бы пришлось перебирать столько же.
С большим количеством раундов
Большое количество раундов — это хорошо, но бесконечно увеличивать мы его не можем, т. к. растёт нагрузка на наши сервера и время ответа пользователю. Как результат, раунды — это хорошо, но если можно бесплатно усложнить перебор ещё в 10 раз, то почему бы и нет?
Схема выглядит примерно так. Пользователь генерирует открытый закрытый ключ, открытый сохраняется на сервере закрытый у пользователя. При авторизации клиент обращается к серверу, тот генерит случайный текст, возвращает клиенту. Клиент шифрует закрытым ключем и передает серверу. Сервер открытым ключем дешифрует сообщение и сравнивает с оригинальным. Если совпало — успех.
Как результат, на простых рандомных 9-символьных паролях, составленных по 95-символьному словарю, можно получить скорость перебора порядка 14 юзеров в день (это на 1 млн карт, и если на одном ядре CPU подсчёт занимает 0.1 мс). Если мы усложнили перебор на картах в 10 раз, то скорость будет 1.4 юзера в день. За год переберётся 500 юзеров (но мощность карт растёт).
PS. На сколько на самом деле Argon2 усложняет перебор на картах — не знаю.
PS. Возможно, интересным решением было бы самому считать на картах, но как я подозреваю, это может дать задержку.
Также без соли есть риск, что Ваш алгоритм будет слишком стандартным и будет подвержен атаке радужными таблицами. Либо же, если разные взломанные сайты будут использовать одинаковый алгоритм, то перебор сильно упростится (но только при совпадении логинов, т. к. логин+разделитель включены в хэш).
Зачем лишняя зависимость?
Не понял Вас. Вы боитесь потерять соль? Лучше бойтесь потерять базу с хэшами)
А соль пользователя скорее всего будет храниться там же в базе.
Тем более 4,1 почему-то хуже 3.
Как правильно хешировать пароли в высоконагруженных сервисах. Опыт Яндекса