Attacker & Defender
Прежде чем переходить к алгоритмам и построению схемы хеширования, надо вообще понять, от чего же мы защищаемся и какую роль в безопасности веб-сервиса должно играть хеширование паролей. Обычно сценарий таков, что атакующий ломает веб-сервис (или несколько веб-сервисов) через цепочку уязвимостей, получает доступ к базе данных пользователей, видит там хеши паролей, дампит базу и идет развлекаться с GPU (и, в редких случаях, с FPGA и ASIС).
Что в этом случае делает защищающийся? В первую очередь — отправляет пользователей, хеши паролей которых были скомпрометированы, на принудительную смену пароля и дополнительную аутентификацию при помощи привязанного телефона, почты и т. д. В этом случае хороший алгоритм хеширования дает время на то, чтобы понять масштаб бедствия, запустить все необходимые процедуры и, в итоге, спасти аккаунты пользователей от захвата злоумышленником.
Hardware
Как я упонянул выше, для ускорения вычислений атакующий может использовать такое оборудование, как GPU, FPGA, ASIC. На мой взгляд, самое опасное из этого списка — GPU, потому что очень много людей увлекается майнингом криптовалют, трехмерными играми и т. д. GPU держат наготове, чтобы начать перебирать хеши паролей. FPGA, в свою очередь, не распространены массово, стоят дорого, часто возможностей отладочной платы недостаточно, а припаять что-то в домашних условиях обычно нереально (на больших частотах повышенные требования к качеству пайки и т. д.). И, наконец, ASIC требует довольно существенных инвестиций, проектирования, запуска цикла производства. Зачастую это будет дороже, чем стоимость информации, которую злоумышлениик может добыть, взломав ваш сервис.
Ну а защищающаяся сторона обычно использует серверные CPU, на которых работают веб-приложения. У серверных CPU много ядер (но меньше, чем в GPU), большой L3-кэш и т. д. Поэтому очевидная идея при разработке алгоритмов хеширования — оптимизировать их под возможности CPU и максимально замедлять их на GPU, FPGA и ASIC. Среди подобных способов замедления можно выделить следующие:
1. Использование большого количества RAM (на GPU shared memory ограничена, а поход в global memory очень «дорогой»; на FPGA и ASIC нужно припаивать внешнюю память, что приводит к удорожанию всей схемы, задержкам при доступе и т. д.) и устойчивость к Time-Memory Tradeoff (так называемые алгоритмы Memory Hard).
2. Использование чтений/записей малого количества данных по случайным адресам в маленьком регионе памяти, который помещается в L1-кэш (если попытаться прочитать 4 байта из GPU global memory, то на самом деле будет прочитано 32 байта, что заставляет GPU впустую использовать шину памяти).
3. Использование операции умножения MUL. На CPU она выполняется так же быстро, как и обычные операции типа сдвигов и ADD, но на FPGA и ASIC это приводит к более сложной конфигурации, большим задержкам в обработке данных и т. д.
4. Использование так называемого instruction-level parallelism и алгоритма хешировния SIMD-friendly design. Современные CPU несут на борту разные advanced-наборы инструкций типа SSE2, SSSE3, AVX2 и т. д., которые позволяют проводить несколько операций за один раз и значительно ускорить вычисления.
Перечисленные техники используются не во всех алгоритмах. Так, в Argon2 (победителе Password Hashing Competition) используются все перечисленных техники, кроме второй. В Yescrypt, который получил special recognition в конкурсе PHC, используются все четыре техники (но надо включить специальный режим работы).
Для себя мы выбрали Argon2, поскольку этот алгоритм хорошо исследован, прост для понимания и реализации, а также хорошо оптимизирован для x64 и SIMD.
Проблема computational DoS
Если алгоритм в процессе работы использует много памяти и гарантированно занимает определенное количество времени CPU, то бездумный выбор параметров может привести к ситуации computational DoS, когда небольшие RPS могут вывести из строя веб-сервис или значительно замедлить ответы пользователю. Реальность такова, что путей выхода из ситуации не очень много. Вот некоторые из них:
1. «Залить проблему железом» — добавить много дополнительных северов, на которых работает веб-сервис. Это в каком-то смысле поможет справиться с computational DoS при должной балансировке нагрузки, но такой способ не решает проблему долгих ответов пользователю. Другими словами, добавление большого количества ресурсов не уменьшает время ответа, а всего лишь увеличивает пиковые RPS на кластер. Как вы можете догадаться, это не наш путь.
2. Максимальная оптимизация кода алгоритма хеширования, использование SIMD-инструкций и т. д.
3. Уменьшение используемых параметров алгоритма до приемлемого уровня — с добавлением различных mitigations на уровне всей схемы хеширования паролей.
Очевидно, что стоит заниматься последними двумя пунктами. Если высокая производительность для вас не так важна, то, используя оптимизированную версию алгоритма, вы можете позволить себе бoльшие параметры, что еще сильнее затруднит перебор паролей на GPU, FPGA, ASIC. А добавление mitigations на уровне схемы хеширования паролей может также сделать невозможными (или, по крайней мере, трудноисполнимыми) офлайн-атаки на базу хешей и допустить перебор хешей только в том случае, если злоумышленник находится в вашей сети, что облегчает детектирование такой ситуации и расследование инцидента.
Mitigations на уровне протокола
Какие mitigations на уровне схемы хеширования существуют в настоящее время:
1. Использование локальных параметров (local parameters). Эта идея довольно проста — надо добавить в алгоритм секретный параметр, который хранится не в базе данных, а в приложении (например, в environment-переменных). Таким образом, злоумышленнику будет недостаточно получить доступ к базе данных с хешами паролей — придется ломать еще и приложение. Также администратор базы данных не сможет сдампить хеши и развлекаться с ними дома с GPU.
2. Использование большого ROM (Read-only memory) для подмешивания значений из него при хешировании паролей. Эта идея была предложена авторами Yescrypt как одна из адаптаций алгоритма для large scale password hashing. По сути, если использовать ROM порядка 100 ГБ, то его будет сложно украсть — для быстрого перебора на CPU надо иметь сервер с минимальной памятью 100 ГБ. На GPU, FPGA и ASIC все тоже будет медленно, поскольку мы не только используем большой ROM, но и оптимизируем алгоритм хеширования так, чтобы он был медленным на этих типах оборудования и т. д. К недостаткам идеи можно отнести то, что вам придется все время жить с этим большим ROM и вы, скорее всего, никогда от него не избавитесь.
3. Использование CryptoAnchors — маленьких микросервисов, которые выполняют только одну операцию: применяют PRF с секретным ключом, например HMAC. Секретный ключ хранится в микросервисе и никогда не покидает его. Суть идеи в том, что микросервис маленький, простой. Провести его аудит легко, а взломать — очень трудно, поэтому его использование позволяет превратить офлайн-атаки в онлайн-атаки. Другими словами, для атаки на базу хешей злоумышленник должен оставаться внутри сети и слать запросы к этому микросервису.
Идея CryptoAnchors используется в схеме хеширования паролей Facebook под названием Passwords Onion, но может быть задействована и в других частях инфраструктуры.
4. Использование так называемых Partially-Oblivious PRF (по сути? это часть пункта 3). Если использовать CryptoAnchors с чем-то типа HMAC, то возникает проблема смены секретного ключа при его компрометации. Один из способов решить проблему — создать еще один слой HMAC, что приводит к различным неудобствам. Кроме того, в случае обычных CryptoAnchors этот микросервис видит все хеши, которые присылает приложение. Другими словами, если сервис будет взломан, злоумышленник сможет собирать хеши в чистом виде и проводить офлайн-атаку. Для решения этих двух проблем исследователи из CornellTech предложили использовать Partially-Oblivious PRF, основанные на billinear pairing. Такая конструкция позволяет менять секретный ключ, организовывать логирование и ограничения по количеству запросов для каждого пользователя. При этом микросервис не видит хеши в открытом виде. Подробнее можно почитать в их статье.
Вкратце идея такова, что приложение хеширует пароль, использует blinding для его маскировки и передает в микросервис маскированный пароль вместе с идентификатором пользователя t. Микросервис применяет billinear pairing к этим значениям, используя известный только ему ключ k и передает результат в приложение, которое, в свою очередь, может применить unblinding (снять маскировку) и сравнить результат с тем, что хранится в БД. При этом линейность billinear pairing позволяет микросервису с POPRF выдать приложению токен для обновления ключа, и приложение может пройтись по БД и обновить записи.
Оптимизация производительности. Аргонище — наша реализация Argon2
На GitHub есть официальная реализация алгоритма Argon2, однако она использует
?march=native, что для нас чревато падениями сервиса с исключением Illegal instruction, поскольку у нас используются разные модели процессоров, а эта настройка заставляет компилятор оптимизировать код под модель процессора, на котором происходит сборка. Если мы создадим максимально переносимую конфигурацию сборки, то потеряем где-то 15–20 процентов возможной производительности (а в случае AVX2 — до 65 процентов). Поэтому мы создали свою реализацию алгоритма Argon2, которая позволяет максимально использовать возможности CPU, на котором происходит выполнение кода.
Наша реализация использует технику под названием Runtime CPU dispatching. Ее суть в том, что при инициализации библиотеки с кодом алгоритма выполняется инструкция
cpuid, которая определяет, какие из наборов advanced instructions поддерживаются текущим CPU, и выбирает ветку кода с соответствующими оптимизациями. Наша библиотека содержит код, оптимизированный под наборы инструкций SSE2, SSSE3, SSE4.1 и AVX2. Разницу в производительности на Argon2d с параметрами p=1,m=2048,t=1 можно увидеть на графике ниже.
И так как Argon2 использует Blake2B, то мы в качестве бонуса получили Blake2B, оптимизированный под перечисленные выше наборы инструкций. Внутри компании мы рекомендуем использовать Blake2B в качестве быстрой и безопасной замены
SHA-1 и HMAC-SHA-1. Итак, отличия от официальной реализации Argon2 следующие:1. C++14 и cmake в качестве системы сборки.
2. Runtime CPU dispatching.
3. Blake2B, оптимизированный под SSE2, SSSE3, SSE4.1, AVX2.
4. OpenMP вместо pthread, а если OpenMP нет, то все вычисления будут производиться последовательно.
Также в процессе работы мы написали с нуля версию Argon2 для набора инструкций AVX2 и отправили PR в официальный репозиторий, где наши изменения были приняты мейнтейнерами.
В целом, проблема хеширования паролей в больших и высоконагруженных сервисах решаема. Для ее решения надо:
• ускорять реализацию алгоритма хеширования,
• подбирать параметры алгоритма исходя из KPI на время отклика,
• вносить изменения в схему хеширования для защиты от офлайн-атак.
Благодарности
Мы благодарим Solar Designer (он же Александр Песляк) за огромное количество мыслей, идей, экспериментов и полезных обсуждений проблемы хеширования паролей в больших интернет-компаниях. Еще хотим сказать спасибо Дмитрию Ховратовичу за различные идеи, совместное обсуждение и анализ разных подходов к хешированию паролей. Большое спасибо Игорю cerevra Клеванцу, который в перерывах между внесениями правок в стандарт C++ нашел время на ревью кода нашей реализации Argon2.
Полезные ссылки
• Проект Аргонище на GitHub
• Официальный репозиторий Argon2
• Статья про Pythia и Partially-Oblivious PRF
• Intel Intrinsics Guide
• PASS: Strengthening and Democratizing Enterprise Password Hardening
Комментарии (61)
dpantele
31.08.2017 16:34А bcrypt уже считается "устаревшим"?
FractalizeR
31.08.2017 16:54Нельзя сказать, что устарел полностью, но Аргон его в какой-то степени превосходит: 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
dpantele
31.08.2017 20:43Они же проголосовали просто за включение, вроде никто bcrypt не убирает.
Но кажется что никаких причин срочно отказываться от bcrypt нет (как отказываются сейчас от SHA1 и MD5).
bolk
31.08.2017 21:05Аргон2 используется в АПИ, правильное использование которого должно рехешировать (во время логина пользователя) все пароли под дефолтное хеширование. Дефолтным как Аргон2 и стал.
FractalizeR
01.09.2017 12:25Они, по-моему, пока ревертнули этот коммит: https://github.com/php/php-src/pull/1997/commits/1bc381848add707db42671b3c33e1082aa3e7f93
dpantele
31.08.2017 16:35+4Интересно, получилась ли версия с Runtime CPU dispatching в результате быстрее чем референс с march=native под конкретный сервер. Можно и на этапе деплоймента, а не в рантайме, разбираться какие инструкции есть.
xmm10 Автор
31.08.2017 16:41+4Чуть быстрее, но скорее за счет того, что в референсной реализации нет оптимизаций для Blake2B. К сожалению, конкретных цифр нет под рукой.
Разбираться с процессором на этапе деплоя можно, но это не всегда удобно (например, при деплое Docker-контейнеров). Тут многое зависит от вашей системы деплоя. Для нас просто runtime CPU dispatching это самое удобное, что можно сделать.dpantele
31.08.2017 20:35Ну в принципе можно прямо внутри контейнера выбирать с какой версией библиотеки линковать или даже какой скомпилированный бинарник запускать (при static-linkage). Наверное, можно и через
dlopen. Но не ясно что дешевле — поддерживать разные имплементации или сборку для разных targets.xmm10 Автор
31.08.2017 22:31+2Но это надо собирать бинарь внутри контейнера, тащить в продакшн компилятор и т.д., при этом ждать, пока все соберется при запуске контейнера (будет большая задержка на старте).
Несколько бинарей или dlopen будут работать, но это же тот же runtime CPU dispatching, только чуть по-другому.dpantele
01.09.2017 07:08Нет, компилятор тащить я совсем не предлагал. Я предлагал заранее собрать под каждый хост свой бинарник/библиотеку через -march=native, не используя специальных реализаций, и при запуске выбирать нужное, для чего мне пришли в голову 3 вышеперечисленных способа.
То есть тут сложность поддержки реализации заменяется сложностью сборки под каждый хост.
alexr64
31.08.2017 16:44Можно и на этапе деплоймента
Неудобно когда ферма — зоопарк из машин «что было — то и запилили».
RomanArzumanyan
31.08.2017 17:03+71. Использование большого количества 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 были сделаны.
В общем, анализ так себе.xmm10 Автор
01.09.2017 10:58+3Доступ к глобальной памяти (которой является RAM) для всех дорогой — и для CPU тоже.
Все верно, но в серверных CPU есть большой L3 кэш, который позволяет все ускорить.
Есть такая штука, как локальная память, разделяемая внутри кластера потоковых процессоров на GPU. Время доступа — несколько тактов. И кэши данных у GPU тоже есть, просто они распределены и меньшего объёма.
А где-то утверждается, что кешей или локальной памяти в GPU нет?
Пример с использованием чтений/записей по случайным адресам взят из bcrypt, который использует всего 4кб.
Бенчмарки bcrypt CPU vs GPU убедительно доказывают, что чтения/записи 4 байт по случайным адресам в регионе 4кб сильно снижают эффективность GPU.
Наверняка сами знаете, что в некоторых моделях GPU даже 4кб быстрой памяти на поток это роскошь.
SIMD вычисления — это то, ради чего GPU были сделаны.
Просто неудачная фраза, смысл в том, что алгоритмы оптимизированы под x64 с учетом наборов инструкций типа SSE2…
В общем, анализ так себе.
Негативный фидбек тоже важен для насRomanArzumanyan
01.09.2017 11:15+1Наверняка, у криптографии своя специфика, но приходилось делать оптический поток и поиск / компенсацию движения на GPU — там чтения по случайным адресам 4/8/16 байт — работало в реальном времени на мобильных платформах. Достаточно было векторных загрузок с ближайшего выровненного адреса.
За пояснения спасибо.
vlanko
02.09.2017 21:26Одно дело, когда напрямую интегрированный в процессоре контролер памяти. Другое — Pci-express (16 ГБ/сек в лучшем случае) — проц — память.
masterspline
31.08.2017 18:16C++14 и cmake в качестве системы сборки.
OpenMP вместо pthread
В Яндексе еще не знают, что начиная с C++11 в языке появились потоки? Cmake тоже нормально поддерживает потоки (начиная с v3.1, у вас используется 3.5).
Поиск потоков в CMakeLists.txtset( CMAKE_THREAD_PREFER_PTHREAD TRUE ) set( THREADS_PREFER_PTHREAD_FLAG TRUE ) find_package( Threads REQUIRED) # this works with only wieth cmake 3.1.0+ target_link_libraries( target Threads::Threads )Kobalt_x
31.08.2017 21:21+1Ну OpenMP как бы более высокий уровень скорее являющийся аналогом параллельных алгоритмов из 17 стандарта
xmm10 Автор
31.08.2017 22:18+1Вопрос OpenMP vs pthread это скорее холивар вроде «ручное управление потоками» vs «что-то, что управляет потоками за тебя». В данном конкретном случае мне просто было удобнее использовать OpenMP.
Akon32
31.08.2017 19:14+1Не совсем понятен следующий переход:
Нужно максимально замедлить перебор хэшей на GPU/etc взломщика, поэтому вы ускоряете(!) реализации(!) алгоритмов на своих(!) CPU.
Как уже отмечалось выше, GPU также имеют кэши и прочие "радости" из мира CPU. Нужно очень постараться, чтобы создать криптоалгоритмы (не реализации!), плохо пригодные для реализации на GPU. Насколько я понимаю, основная проблема тут не в архитектурах железа, а в том, что создание своих алгоритмов (хэширования) в мире криптографии не приветствуется.
Не лучше ли солить хэши?
dpantele
31.08.2017 20:24Хеши же наверняка солёные. Я думаю что защищаются от того чтобы по дампу базы нельзя было бы сломать "словарные" пароли конкретных аккаунтов.
vlanko
02.09.2017 21:301. если хеширование с правильной солью, то спасет только полный перебор. Вот от него и защищаются.
2. а если соль одна и ее вычисляют по заложенному заранее своему паролю…
dpantele
31.08.2017 20:53+1При хешировании у вас нет задачи это делать быстро — надо проверить один пароль. При брутфорсе надо проверить много. И тут задач стоит чтобы GPU вёл себя не лучше CPU. А дальше уже всё это можно как угодно ускорять — пользователей с паролем password таким способом всё равно не спасти.
xmm10 Автор
31.08.2017 22:20+1Да, хэши соленые. В Argon2 соль обязательна. Про остальное dpantele отлично ответил за меня.
Akon32
01.09.2017 12:09К сожалению, комментарии 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) Какое-то из предположений (а, б) верно, или ситуация принципиально иная?FractalizeR
01.09.2017 14:12+11) Правильно я понимаю, что вы используете схему криптосистемы, как в bcrypt, где перебор хэшей затрудняется путём усложнения хэш-функции таким образом, что время её расчёта становится намного дольше?
Используется схема криптосистемы как в bcrypt, где перебор хешей усложняется таким образом, чтобы время расчета группы таких хешей на GPU максимально приближалось ко времени расчета хешей на CPU. Яндекс при логине пользователя всегда считает хеши на CPU. Посчитать нужно 1 хеш на пользователя. Хакеры считают на GPU сразу много, чтобы было быстрее. Профит в затруднении расчетов хешей именно на GPU для хакеров.
вы действительно разработали криптосистему
Яндекс не является разработчиком криптосистемы Аргон. Об этом написано в статье.
Master_Dante
31.08.2017 19:34-2Все что написано в Hardware нужно делать, если злоумышленник, может получить доступ к коду сервера, и увидеть как строится хеш функция. Без этого даже отрезанный вдвое SHA 256 будет вводить в заблуждение любого криптоаналитика. Имхо статья по большей части понторезная и вредная с точки зрения хайлоад.
Scratch
31.08.2017 20:48+1Интересно было бы глянуть на имплементацию POPRF, планируете показать?
xmm10 Автор
01.09.2017 10:19Это нечто с чем мы пока экспериментируем, пока же можно посмотреть код ребят из Cornell Tech. Буду рад, если после поделитесь своим мнением.
Scratch
01.09.2017 12:24Да, эту штуку я уже видел, думал есть что то более читабельное ) Питон и отсутствие документации слабо помогают понять что происходит. Там paring-based криптография, пока новая тема для меня.
Сам я из подобного заимплементил Sphinx
webee.technion.ac.il/~hugo/sphinx.pdf
gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042
Чем-то напоминает пифию, но там всё гораздо проще. Правда никаких обновлений ключей и прочих наворотов.
Chikey
31.08.2017 21:03+1Пароли вообще не надо хешировать, из них надо дерайвить приватный ключ и им уже подписывать запросы. Отдавать пароль плейнтекстом на левый сервер пусть хоть яндекса — dead end.
xmm10 Автор
31.08.2017 22:11+1«Дерайвить» в каком-то смысле и есть хеширование :) Я догадываюсь к чему вы клоните, но в вашей схеме все равно присутствует master password и алгоритм хеширования паролей scrypt.
подписывать запросы
Подписывать целиком HTTP запрос?
Kobalt_x
31.08.2017 21:16OpenMP вместо pthread. Вы не поверите в GCC оно работает таки поверх pthread. Afaik только в специфичных компиляторах и от вендоров e.g ICC, xlc оно работает на чем то своём
xmm10 Автор
31.08.2017 22:34Я не говорю об этом как о преимуществе, а только как об отличии от референсной реализации
Kobalt_x
31.08.2017 21:19"Использование операции умножения MUL. На CPU она выполняется так же быстро, как и обычные операции типа сдвигов и ADD, но на FPGA и ASIC это приводит к более сложной конфигурации, большим задержкам в обработке данных и т. д." На FPGA современных вроде есть встроенные dsp поэтому пока их будет хватать, эффектов описанных в статье не будет даже рядом? Информация в статье точно актуальна?
xmm10 Автор
31.08.2017 22:00Тут я хочу сослаться на разработчиков алгоритмов и материалы PHC. Эта конструкция используется в Yescrypt (pwxform transformation, слайды 1, 2), Argon2 (спецификация, страница 15 второй абзац снизу), Lyra2. Честно признаться, сам я с FPGA и ASIC каждый день не работаю :)
kyb27
01.09.2017 10:03+1Судя по всему авторы и лиры и аргона с FPGA и ASIC вообще не работали. В статьях только ссылки.
Схемы быстрого умножения описаны в старой советской литературе 30-40 летней давности, не говоря о том, что можно купить готовые ядра.
Большие объемы памяти тоже не проблема — готовые контроллеры DDR есть на opencores. Та же RIVYERA V7-2000T дает 20Гб на FPGA.
vlreshet
01.09.2017 07:59+1Знающие люди (если не лень), объясните пожалуйста на пальцах — почему нельзя использовать использовать обычный sha1 с солью, просто с большим количеством раундов? Если захешировали в sha1 1024 раза, и каждый раз с солью — неужели это реально взломать брутфорсом?
xmm10 Автор
01.09.2017 09:45Примерно то, что вы описываете, называется PBKDF2 и описано в стандарте PKCS#5. Да, оно хорошо перебирается на GPU и остальном железе.
RadicalDreamer
01.09.2017 12:17Да, оно хорошо перебирается на GPU и остальном железе.
Каким образом? Если использовать радужные таблицы, они не особо помогут со взломом хеша с солью, или может я чего-то не понимаю?TimTowdy
01.09.2017 12:58Суть же не в радужных таблицах, а обычном брутфорсе (либо брутфорсе по словарю). В случае обычного соленого хеша (пусть даже с N итерациями), его очень легко распараллелить на GPU.
RadicalDreamer
01.09.2017 13:53Это если соль хранилась в БД и была благополучно скомпрометрована. Никто же не запрещает хранить соль вне БД, например в конфиге системы. Лично я не представляю себе такое устройство, которое могло бы подобрать пароль + соль к украденному хешу, за сколько-нибудь обозримое время (при условии надежности самого алгоритма хеширования и прочих равных), пусть это даже будет множество GPU, работающих параллельно.
RadicalDreamer
01.09.2017 13:58Впрочем, похоже, я назвал то, что итак предлагается в статье, а именно, использование локального параметра.
TimTowdy
01.09.2017 14:24Никто же не запрещает хранить соль вне БД, например в конфиге системы
И никто не запрещают сохранить себе эту соль (а заодно и всю базу) уволившемуся админу/разработчику.
Подразумевается именно сложность брутфорса при полностью скомпрометированных данных. Никаких security through obscurity. Секретная соль — это один слой защиты, невозможность распараллелить брутфорс — другой. Они никак не пересекаются, каждый слой выполняет свою задачу.vlreshet
01.09.2017 18:04А если соль не статическая, а является частью от хеша этого же пароля? Алгоритм получения соли будет известен, но так как соль — это часть того же пароля, то толку от знания алгоритма будет мало. Слабо верится что несколько тысяч итераций такого хеширования можно размотать брутфорсом, чисто математически оно же упирается в дохрена времени…
TimTowdy
01.09.2017 21:16Не очень понял что вы имеете ввиду.
Но в любом случае, сколько бы тысяч итераций примитивного хеширования у вас не было, проблема остается: увеличив количество ядер в N раз, мы ускорим брутфорс в N раз.
vitaliy2
02.09.2017 18:57Если соль вычисляется по паролю, то это уже не соль.
Соль нужна:
- Как дополнительная защита на случай, если злоумышленники смогли получить доступ к базе, но не смогли получить доступ к алгоритму. Без соли этот алгоритм можно просто перебрать. Конечно же, вариантов алгоритмов может быть триллионы, но карты могут перебирать их квадриллионы в секунду, и даже квинтиллионы в секунду (при использовании одного раунда). А в одних сутках у нас 86400 секунд!
Соль из 5 символов усложнит перебор алгоритма в 10 млрд раз, соль из 10 символов — в 100 квинтиллионов раз и т.?д. Ваша же идея тоже усложнит перебор, но максимум в 10–1000000 раз. Как минимум соль — это намного проще. - Чтобы Ваш алгоритм точно был уникальным. Если он будет неуникальным, то одновременно с Вашей базой можно заодно перебирать и 10 других баз или даже заюзать радужные таблицы.
- Чтобы разграничить права, кто к какой части имеет доступ.
- Как дополнительная защита на случай, если злоумышленники смогли получить доступ к базе, но не смогли получить доступ к алгоритму. Без соли этот алгоритм можно просто перебрать. Конечно же, вариантов алгоритмов может быть триллионы, но карты могут перебирать их квадриллионы в секунду, и даже квинтиллионы в секунду (при использовании одного раунда). А в одних сутках у нас 86400 секунд!
vitaliy2
02.09.2017 18:20Почему нельзя использовать использовать обычный sha1 с солью и большим количеством раундов?
Сложность паролей на сайтах обычно примерно в 500 млрд раз меньше, чем на паролях, защищённых от оффлайн-перебора. Соль спасает, но раз базу взломали, вполне могут и соль взломать. Самое хорошее в соли — на каждом сайте она своя, поэтому нельзя перебрать базы сразу от всех сайтов одновременно.
Нужно отметить, что хэш должен считаться не от пароля, от от логина+пароля+соль. В этом случае перебирать пароли придётся для каждого пользователя отдельно, что очень сильно усложняет перебор. Как результат — при такой хорошей защите соль влияет меньше, т.?к. если взломано два сайта и две соли, но все логины разные, то и без соли бы пришлось перебирать столько же.
С большим количеством раундов
Большое количество раундов — это хорошо, но бесконечно увеличивать мы его не можем, т.?к. растёт нагрузка на наши сервера и время ответа пользователю. Как результат, раунды — это хорошо, но если можно бесплатно усложнить перебор ещё в 10 раз, то почему бы и нет?
Rupper
02.09.2017 06:24Немного оффтопик, но есть ли реализации схемы zero knowlege proof для вебприложений?
Схема выглядит примерно так. Пользователь генерирует открытый закрытый ключ, открытый сохраняется на сервере закрытый у пользователя. При авторизации клиент обращается к серверу, тот генерит случайный текст, возвращает клиенту. Клиент шифрует закрытым ключем и передает серверу. Сервер открытым ключем дешифрует сообщение и сравнивает с оригинальным. Если совпало — успех.xmm10 Автор
02.09.2017 14:58Вот, например, протокол SRP. Прямо в википедии есть пример реализации на python.
Rupper
02.09.2017 17:27srp вроде как не совсем повторяет указанную схему, про него я читал, но «по диагонали».
Надо будет внимательно прочитать схему, если это то что я спрашиваю.
vitaliy2
02.09.2017 14:07Возможно, это очевидно, но всё-таки в статье не указано что считать хэш нужно не от пароля, а от логина+пароля+соль. Тогда для каждого пользователя нужно будет делать отдельный перебор. Например, если есть миллион пользователей, то на перебор всей базы потребуется в миллион раз больше времени.
Как результат, на простых рандомных 9-символьных паролях, составленных по 95-символьному словарю, можно получить скорость перебора порядка 14 юзеров в день (это на 1 млн карт, и если на одном ядре CPU подсчёт занимает 0.1 мс). Если мы усложнили перебор на картах в 10 раз, то скорость будет 1.4 юзера в день. За год переберётся 500 юзеров (но мощность карт растёт).
PS. На сколько на самом деле Argon2 усложняет перебор на картах — не знаю.
PS. Возможно, интересным решением было бы самому считать на картах, но как я подозреваю, это может дать задержку.VolCh
02.09.2017 22:09логин+соль = соль в данном контексте. Зачем лишняя зависимость? Или вы про одну глобальную соль для всей базы? Так ещё кто-то делает?
vitaliy2
02.09.2017 23:12Да, я про одну глобальную соль. Соль спасёт тогда, когда злоумышленник получил доступ только к базе, а не к соли. Также соль может помочь разграничить доступы.
Также без соли есть риск, что Ваш алгоритм будет слишком стандартным и будет подвержен атаке радужными таблицами. Либо же, если разные взломанные сайты будут использовать одинаковый алгоритм, то перебор сильно упростится ?(но только при совпадении логинов, т.?к. логин+разделитель включены в хэш).
Зачем лишняя зависимость?
Не понял Вас. Вы боитесь потерять соль? Лучше бойтесь потерять базу с хэшами)
farwayer
03.09.2017 16:09Глобальная соль будет передаваться через переменную окружения, либо хранится в конфиге. Так что получив доступ только к базе придется подбирать соль, что в случае достаточной ее длины будет сделать крайне сложно.
А соль пользователя скорее всего будет храниться там же в базе.
vlanko
02.09.2017 21:24Почему нет AVX-1? Все-же два поколения ЦПУ, а более старые уже неактуальны.
Тем более 4,1 почему-то хуже 3.xmm10 Автор
03.09.2017 15:58AVX просто заточен под floating-point. В Intel Intrinsics Guide можно посмотреть все инструкции из этого набора. Про SSE4.1 vs SSSE3 — да, там почти нет разницы (небольшая разница в реализации Blake2B) и возможно я удалю верcию для SSE4.1.
RouR
Вы перечислили 4 способа замедления и 4 mitigations. А используете какие? Что там внутри этого Аргонища?