company_banner

Как правильно хешировать пароли в высоконагруженных сервисах. Опыт Яндекса

    Я расскажу о такой проблеме, как хеширование паролей в веб-сервисах. На первый взгляд кажется, что тут все «яснопонятно» и надо просто взять нормальный алгоритм, которых уже напридумывали много, написать чуть-чуть кода и выкатить все в продакшн. Но как обычно, когда начинаешь работать над проблемой, возникает куча подводных камней, которые надо обязательно учесть. Каких именно? Первый из них — это, пожалуй, выбор алгоритма: хоть их и много, но у каждого есть свои особенности. Второй — как выбирать параметры? Побольше и получше? Как быть с временем ответа пользователю? Сколько памяти, CPU, потоков? И третий — что делать с computational DoS? В этой статье я хочу поделиться некоторыми своими мыслями об этих трех проблемах, опытом внедрения нового алгоритма хеширования паролей в Яндексе и небольшим количеством кода.



    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 на уровне всей схемы хеширования паролей.

    Очевидно, что стоит заниматься последними двумя пунктами. Если высокая производительность для вас не так важна, то, используя оптимизированную версию алгоритма, вы можете позволить себе бóльшие параметры, что еще сильнее затруднит перебор паролей на 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
    Яндекс 527,95
    Как мы делаем Яндекс
    Поделиться публикацией
    Комментарии 64
    • –1
      Вы перечислили 4 способа замедления и 4 mitigations. А используете какие? Что там внутри этого Аргонища?
      • 0

        А bcrypt уже считается "устаревшим"?

      • +4

        Интересно, получилась ли версия с Runtime CPU dispatching в результате быстрее чем референс с march=native под конкретный сервер. Можно и на этапе деплоймента, а не в рантайме, разбираться какие инструкции есть.

        • +4
          Чуть быстрее, но скорее за счет того, что в референсной реализации нет оптимизаций для Blake2B. К сожалению, конкретных цифр нет под рукой.

          Разбираться с процессором на этапе деплоя можно, но это не всегда удобно (например, при деплое Docker-контейнеров). Тут многое зависит от вашей системы деплоя. Для нас просто runtime CPU dispatching это самое удобное, что можно сделать.
          • 0

            Ну в принципе можно прямо внутри контейнера выбирать с какой версией библиотеки линковать или даже какой скомпилированный бинарник запускать (при static-linkage). Наверное, можно и через dlopen. Но не ясно что дешевле — поддерживать разные имплементации или сборку для разных targets.

            • +2
              Но это надо собирать бинарь внутри контейнера, тащить в продакшн компилятор и т.д., при этом ждать, пока все соберется при запуске контейнера (будет большая задержка на старте).

              Несколько бинарей или dlopen будут работать, но это же тот же runtime CPU dispatching, только чуть по-другому.
              • 0

                Нет, компилятор тащить я совсем не предлагал. Я предлагал заранее собрать под каждый хост свой бинарник/библиотеку через -march=native, не используя специальных реализаций, и при запуске выбирать нужное, для чего мне пришли в голову 3 вышеперечисленных способа.


                То есть тут сложность поддержки реализации заменяется сложностью сборки под каждый хост.

                • 0
                  Да, это тоже будет работать.
          • 0
            Можно и на этапе деплоймента

            Неудобно когда ферма — зоопарк из машин «что было — то и запилили».
          • +7
            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 были сделаны.
            В общем, анализ так себе.
            • +3
              Доступ к глобальной памяти (которой является RAM) для всех дорогой — и для CPU тоже.

              Все верно, но в серверных CPU есть большой L3 кэш, который позволяет все ускорить.
              Есть такая штука, как локальная память, разделяемая внутри кластера потоковых процессоров на GPU. Время доступа — несколько тактов. И кэши данных у GPU тоже есть, просто они распределены и меньшего объёма.

              А где-то утверждается, что кешей или локальной памяти в GPU нет?

              Пример с использованием чтений/записей по случайным адресам взят из bcrypt, который использует всего 4кб.
              Бенчмарки bcrypt CPU vs GPU убедительно доказывают, что чтения/записи 4 байт по случайным адресам в регионе 4кб сильно снижают эффективность GPU.
              Наверняка сами знаете, что в некоторых моделях GPU даже 4кб быстрой памяти на поток это роскошь.
              SIMD вычисления — это то, ради чего GPU были сделаны.

              Просто неудачная фраза, смысл в том, что алгоритмы оптимизированы под x64 с учетом наборов инструкций типа SSE2…
              В общем, анализ так себе.

              Негативный фидбек тоже важен для нас
              • +1
                Наверняка, у криптографии своя специфика, но приходилось делать оптический поток и поиск / компенсацию движения на GPU — там чтения по случайным адресам 4/8/16 байт — работало в реальном времени на мобильных платформах. Достаточно было векторных загрузок с ближайшего выровненного адреса.

                За пояснения спасибо.
              • 0
                Одно дело, когда напрямую интегрированный в процессоре контролер памяти. Другое — Pci-express (16 ГБ/сек в лучшем случае) — проц — память.
              • 0
                C++14 и cmake в качестве системы сборки.
                OpenMP вместо pthread

                В Яндексе еще не знают, что начиная с C++11 в языке появились потоки? Cmake тоже нормально поддерживает потоки (начиная с v3.1, у вас используется 3.5).
                Поиск потоков в CMakeLists.txt
                set( 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 )
                

                Если серьезно, то почему OpenMP, а не потоки из C++11?
                • +1

                  Ну OpenMP как бы более высокий уровень скорее являющийся аналогом параллельных алгоритмов из 17 стандарта

                  • +1
                    Вопрос OpenMP vs pthread это скорее холивар вроде «ручное управление потоками» vs «что-то, что управляет потоками за тебя». В данном конкретном случае мне просто было удобнее использовать OpenMP.
                  • +1

                    Не совсем понятен следующий переход:
                    Нужно максимально замедлить перебор хэшей на GPU/etc взломщика, поэтому вы ускоряете(!) реализации(!) алгоритмов на своих(!) CPU.


                    Как уже отмечалось выше, GPU также имеют кэши и прочие "радости" из мира CPU. Нужно очень постараться, чтобы создать криптоалгоритмы (не реализации!), плохо пригодные для реализации на GPU. Насколько я понимаю, основная проблема тут не в архитектурах железа, а в том, что создание своих алгоритмов (хэширования) в мире криптографии не приветствуется.


                    Не лучше ли солить хэши?

                    • 0

                      Хеши же наверняка солёные. Я думаю что защищаются от того чтобы по дампу базы нельзя было бы сломать "словарные" пароли конкретных аккаунтов.

                      • 0
                        1. если хеширование с правильной солью, то спасет только полный перебор. Вот от него и защищаются.
                        2. а если соль одна и ее вычисляют по заложенному заранее своему паролю…
                      • +1

                        При хешировании у вас нет задачи это делать быстро — надо проверить один пароль. При брутфорсе надо проверить много. И тут задач стоит чтобы GPU вёл себя не лучше CPU. А дальше уже всё это можно как угодно ускорять — пользователей с паролем password таким способом всё равно не спасти.

                        • +1
                          Да, хэши соленые. В Argon2 соль обязательна. Про остальное dpantele отлично ответил за меня.
                          • 0

                            К сожалению, комментарии 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
                              1) Правильно я понимаю, что вы используете схему криптосистемы, как в bcrypt, где перебор хэшей затрудняется путём усложнения хэш-функции таким образом, что время её расчёта становится намного дольше?

                              Используется схема криптосистемы как в bcrypt, где перебор хешей усложняется таким образом, чтобы время расчета группы таких хешей на GPU максимально приближалось ко времени расчета хешей на CPU. Яндекс при логине пользователя всегда считает хеши на CPU. Посчитать нужно 1 хеш на пользователя. Хакеры считают на GPU сразу много, чтобы было быстрее. Профит в затруднении расчетов хешей именно на GPU для хакеров.


                              вы действительно разработали криптосистему

                              Яндекс не является разработчиком криптосистемы Аргон. Об этом написано в статье.

                        • –2
                          Все что написано в Hardware нужно делать, если злоумышленник, может получить доступ к коду сервера, и увидеть как строится хеш функция. Без этого даже отрезанный вдвое SHA 256 будет вводить в заблуждение любого криптоаналитика. Имхо статья по большей части понторезная и вредная с точки зрения хайлоад.
                          • +1
                            Интересно было бы глянуть на имплементацию POPRF, планируете показать?
                            • 0
                              Это нечто с чем мы пока экспериментируем, пока же можно посмотреть код ребят из Cornell Tech. Буду рад, если после поделитесь своим мнением.
                              • 0
                                Да, эту штуку я уже видел, думал есть что то более читабельное ) Питон и отсутствие документации слабо помогают понять что происходит. Там paring-based криптография, пока новая тема для меня.
                                Сам я из подобного заимплементил Sphinx
                                webee.technion.ac.il/~hugo/sphinx.pdf
                                gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042

                                Чем-то напоминает пифию, но там всё гораздо проще. Правда никаких обновлений ключей и прочих наворотов.
                                • 0
                                  Теория конечно жуткий матан, но вся магия вроде бы вот в этом коде, насколько я понимаю. Это если вы blinded версию используете. Можно попробовать разобраться и написать отдельную статью)
                            • +1
                              Пароли вообще не надо хешировать, из них надо дерайвить приватный ключ и им уже подписывать запросы. Отдавать пароль плейнтекстом на левый сервер пусть хоть яндекса — dead end.
                              • +1
                                «Дерайвить» в каком-то смысле и есть хеширование :) Я догадываюсь к чему вы клоните, но в вашей схеме все равно присутствует master password и алгоритм хеширования паролей scrypt.

                                подписывать запросы


                                Подписывать целиком HTTP запрос?
                                • 0
                                  Ну, имеется ввиду хешировать на сервере. Локально хешировать все равно придется.

                                  Достаточно подписать какую то строчку для логина «логин + таймштамп итд» и потом уже получить bearer token в куки.
                              • 0

                                OpenMP вместо pthread. Вы не поверите в GCC оно работает таки поверх pthread. Afaik только в специфичных компиляторах и от вендоров e.g ICC, xlc оно работает на чем то своём

                                • 0
                                  Я не говорю об этом как о преимуществе, а только как об отличии от референсной реализации
                                • 0

                                  "Использование операции умножения MUL. На CPU она выполняется так же быстро, как и обычные операции типа сдвигов и ADD, но на FPGA и ASIC это приводит к более сложной конфигурации, большим задержкам в обработке данных и т. д." На FPGA современных вроде есть встроенные dsp поэтому пока их будет хватать, эффектов описанных в статье не будет даже рядом? Информация в статье точно актуальна?

                                  • 0
                                    Тут я хочу сослаться на разработчиков алгоритмов и материалы PHC. Эта конструкция используется в Yescrypt (pwxform transformation, слайды 1, 2), Argon2 (спецификация, страница 15 второй абзац снизу), Lyra2. Честно признаться, сам я с FPGA и ASIC каждый день не работаю :)
                                    • +1
                                      Судя по всему авторы и лиры и аргона с FPGA и ASIC вообще не работали. В статьях только ссылки.

                                      Схемы быстрого умножения описаны в старой советской литературе 30-40 летней давности, не говоря о том, что можно купить готовые ядра.
                                      Большие объемы памяти тоже не проблема — готовые контроллеры DDR есть на opencores. Та же RIVYERA V7-2000T дает 20Гб на FPGA.
                                  • +1
                                    Знающие люди (если не лень), объясните пожалуйста на пальцах — почему нельзя использовать использовать обычный sha1 с солью, просто с большим количеством раундов? Если захешировали в sha1 1024 раза, и каждый раз с солью — неужели это реально взломать брутфорсом?
                                    • 0
                                      Примерно то, что вы описываете, называется PBKDF2 и описано в стандарте PKCS#5. Да, оно хорошо перебирается на GPU и остальном железе.
                                      • 0
                                        Да, оно хорошо перебирается на GPU и остальном железе.

                                        Каким образом? Если использовать радужные таблицы, они не особо помогут со взломом хеша с солью, или может я чего-то не понимаю?
                                        • 0
                                          Суть же не в радужных таблицах, а обычном брутфорсе (либо брутфорсе по словарю). В случае обычного соленого хеша (пусть даже с N итерациями), его очень легко распараллелить на GPU.
                                          • 0
                                            Это если соль хранилась в БД и была благополучно скомпрометрована. Никто же не запрещает хранить соль вне БД, например в конфиге системы. Лично я не представляю себе такое устройство, которое могло бы подобрать пароль + соль к украденному хешу, за сколько-нибудь обозримое время (при условии надежности самого алгоритма хеширования и прочих равных), пусть это даже будет множество GPU, работающих параллельно.
                                            • 0
                                              Впрочем, похоже, я назвал то, что итак предлагается в статье, а именно, использование локального параметра.
                                              • 0
                                                Никто же не запрещает хранить соль вне БД, например в конфиге системы
                                                И никто не запрещают сохранить себе эту соль (а заодно и всю базу) уволившемуся админу/разработчику.

                                                Подразумевается именно сложность брутфорса при полностью скомпрометированных данных. Никаких security through obscurity. Секретная соль — это один слой защиты, невозможность распараллелить брутфорс — другой. Они никак не пересекаются, каждый слой выполняет свою задачу.
                                                • 0
                                                  А если соль не статическая, а является частью от хеша этого же пароля? Алгоритм получения соли будет известен, но так как соль — это часть того же пароля, то толку от знания алгоритма будет мало. Слабо верится что несколько тысяч итераций такого хеширования можно размотать брутфорсом, чисто математически оно же упирается в дохрена времени…
                                                  • 0
                                                    Не очень понял что вы имеете ввиду.
                                                    Но в любом случае, сколько бы тысяч итераций примитивного хеширования у вас не было, проблема остается: увеличив количество ядер в N раз, мы ускорим брутфорс в N раз.
                                                    • 0
                                                      Если соль вычисляется по паролю, то это уже не соль.

                                                      Соль нужна:
                                                      1. Как дополнительная защита на случай, если злоумышленники смогли получить доступ к базе, но не смогли получить доступ к алгоритму. Без соли этот алгоритм можно просто перебрать. Конечно же, вариантов алгоритмов может быть триллионы, но карты могут перебирать их квадриллионы в секунду, и даже квинтиллионы в секунду (при использовании одного раунда). А в одних сутках у нас 86400 секунд!

                                                        Соль из 5 символов усложнит перебор алгоритма в 10 млрд раз, соль из 10 символов — в 100 квинтиллионов раз и т. д. Ваша же идея тоже усложнит перебор, но максимум в 10–1000000 раз. Как минимум соль — это намного проще.
                                                      2. Чтобы Ваш алгоритм точно был уникальным. Если он будет неуникальным, то одновременно с Вашей базой можно заодно перебирать и 10 других баз или даже заюзать радужные таблицы.
                                                      3. Чтобы разграничить права, кто к какой части имеет доступ.

                                                      • 0

                                                        Как так, что sha(пароль) в 10 млрд раз сложнее sha(парольсоль5)?

                                                        • 0
                                                          1005 = 1010 = 10 млрд

                                                          А если соль по 256-символьному словарю, то соль из 5 символов усложнит перебор в 1 трлн раз.
                                          • 0
                                            Почему нельзя использовать использовать обычный sha1 с солью и большим количеством раундов?

                                            Сложность паролей на сайтах обычно примерно в 500 млрд раз меньше, чем на паролях, защищённых от оффлайн-перебора. Соль спасает, но раз базу взломали, вполне могут и соль взломать. Самое хорошее в соли — на каждом сайте она своя, поэтому нельзя перебрать базы сразу от всех сайтов одновременно.

                                            Нужно отметить, что хэш должен считаться не от пароля, от от логина+пароля+соль. В этом случае перебирать пароли придётся для каждого пользователя отдельно, что очень сильно усложняет перебор. Как результат — при такой хорошей защите соль влияет меньше, т. к. если взломано два сайта и две соли, но все логины разные, то и без соли бы пришлось перебирать столько же.

                                            С большим количеством раундов

                                            Большое количество раундов — это хорошо, но бесконечно увеличивать мы его не можем, т. к. растёт нагрузка на наши сервера и время ответа пользователю. Как результат, раунды — это хорошо, но если можно бесплатно усложнить перебор ещё в 10 раз, то почему бы и нет?
                                          • 0
                                            Немного оффтопик, но есть ли реализации схемы zero knowlege proof для вебприложений?
                                            Схема выглядит примерно так. Пользователь генерирует открытый закрытый ключ, открытый сохраняется на сервере закрытый у пользователя. При авторизации клиент обращается к серверу, тот генерит случайный текст, возвращает клиенту. Клиент шифрует закрытым ключем и передает серверу. Сервер открытым ключем дешифрует сообщение и сравнивает с оригинальным. Если совпало — успех.
                                            • 0
                                              Вот, например, протокол SRP. Прямо в википедии есть пример реализации на python.
                                              • 0
                                                srp вроде как не совсем повторяет указанную схему, про него я читал, но «по диагонали».
                                                Надо будет внимательно прочитать схему, если это то что я спрашиваю.
                                            • 0
                                              Возможно, это очевидно, но всё-таки в статье не указано что считать хэш нужно не от пароля, а от логина+пароля+соль. Тогда для каждого пользователя нужно будет делать отдельный перебор. Например, если есть миллион пользователей, то на перебор всей базы потребуется в миллион раз больше времени.

                                              Как результат, на простых рандомных 9-символьных паролях, составленных по 95-символьному словарю, можно получить скорость перебора порядка 14 юзеров в день (это на 1 млн карт, и если на одном ядре CPU подсчёт занимает 0.1 мс). Если мы усложнили перебор на картах в 10 раз, то скорость будет 1.4 юзера в день. За год переберётся 500 юзеров (но мощность карт растёт).

                                              PS. На сколько на самом деле Argon2 усложняет перебор на картах — не знаю.
                                              PS. Возможно, интересным решением было бы самому считать на картах, но как я подозреваю, это может дать задержку.
                                              • 0
                                                логин+соль = соль в данном контексте. Зачем лишняя зависимость? Или вы про одну глобальную соль для всей базы? Так ещё кто-то делает?
                                                • 0
                                                  Да, я про одну глобальную соль. Соль спасёт тогда, когда злоумышленник получил доступ только к базе, а не к соли. Также соль может помочь разграничить доступы.

                                                  Также без соли есть риск, что Ваш алгоритм будет слишком стандартным и будет подвержен атаке радужными таблицами. Либо же, если разные взломанные сайты будут использовать одинаковый алгоритм, то перебор сильно упростится  (но только при совпадении логинов, т. к. логин+разделитель включены в хэш).

                                                  Зачем лишняя зависимость?

                                                  Не понял Вас. Вы боитесь потерять соль? Лучше бойтесь потерять базу с хэшами)
                                                  • 0
                                                    VolCh имел в виду уникальную для каждого пользователя соль.
                                                  • 0
                                                    Глобальная соль будет передаваться через переменную окружения, либо хранится в конфиге. Так что получив доступ только к базе придется подбирать соль, что в случае достаточной ее длины будет сделать крайне сложно.
                                                    А соль пользователя скорее всего будет храниться там же в базе.
                                                • 0
                                                  Почему нет AVX-1? Все-же два поколения ЦПУ, а более старые уже неактуальны.
                                                  Тем более 4,1 почему-то хуже 3.
                                                  • 0
                                                    AVX просто заточен под floating-point. В Intel Intrinsics Guide можно посмотреть все инструкции из этого набора. Про SSE4.1 vs SSSE3 — да, там почти нет разницы (небольшая разница в реализации Blake2B) и возможно я удалю верcию для SSE4.1.

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое