scrypt

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

scrypt
Впервые опубликован май 2009

scrypt (читается эс-крипт[1]) — адаптивная криптографическая функция формирования ключа на основе пароля, созданная офицером безопасности FreeBSD Колином Персивалем для системы хранения резервных копий Tarsnap. Функция создана таким образом, чтобы усложнить атаку перебором при помощи ПЛИС. Для её вычисления требуется значительный объём памяти со случайным доступом. 17 сентября 2012 года алгоритм scrypt был опубликован IETF в виде Internet Draft, планируется его внесение в RFC[2]. Используется, например, в качестве доказательства выполненной работы в криптовалюте Litecoin[3].

Основанные на пароле функции формирования ключа (password-based key derivation function, PBKDF) обычно разрабатываются таким образом, чтобы требовать относительно большого времени вычисления (по порядку величины — сотни миллисекунд). При использовании легальным пользователем требуется вычислить подобную функцию один раз (например при аутентификации) и такое время допустимо. Но при проведении атаки полного перебора атакующему требуется произвести миллиарды вычислений функции и её вычислительная сложность делает атаку более медленной и дорогой.

Однако ранние функции PBKDF (например PBKDF2, разработанная RSA Laboratories) вычисляются сравнительно быстро, и их перебор может быть эффективно реализован на специализированном оборудовании (FPGA или ASIC). Такая реализация позволяет запускать масштабные параллельные атаки перебора грубой силы, например, с использованием сотен экземпляров функции в каждой микросхеме FPGA.

Функция scrypt разрабатывалась с целью усложнить аппаратные реализации путём увеличения количества ресурсов, требуемых для вычисления. Данный алгоритм использует значительное количество оперативной памяти (памяти со случайным доступом) по сравнению с другими PBKDF. Память в scrypt используется для хранения большого вектора псевдослучайных битовых последовательностей, генерируемых в начале алгоритма[4]. После создания вектора его элементы запрашиваются в псевдослучайном порядке и комбинируются друг с другом для получения ключа. Так как алгоритм генерации вектора известен, возможна реализация scrypt, не требующая памяти, а высчитывающая каждый элемент в момент обращения. Однако, вычисление элемента относительно сложно и в процессе работы функции scrypt каждый элемент считывается много раз. В scrypt заложен такой баланс между памятью и временем, что реализации, не использующие память, слишком медленны.

Определение scrypt

[править | править код]

scrypt (P, S, N, r, p, dkLen) = MFcryptHMAC SHA256,SMixr (P, S, N, p, dkLen)

где N, r, p — параметры, задающие сложность вычисления функции.

MFcrypt определена так: DK = MFcrypt PRF,MF (P, S, N, p, dkLen)

где

  • PRF — псевдослучайная функция (в scrypt — HMAC-SHA256)
  • hLen — длина выхода PRF в байтах
  • MF (mixing function) — последовательная функция, требующая память со случайным доступом (отображение из в (в scrypt — SMix на базе Salsa20/8)
  • MFLen — длина блока, перемешиваемого в MF (в байтах). MFLen =128 * r.

Входные параметры scrypt и MFcrypt:

  • P — пароль (passphrase) — байтовая строка.
  • S — соль (salt) — байтовая строка.
  • N — параметр, задающий сложность (количество итераций для MF).
  • r — параметр, задающий размер блока.
  • p — степень параллельности, целое число, меньшее чем (232 − 1)*hLen/MFLen
  • dkLen — требуемая длина выходного ключа в байтах, не более чем (232 − 1)*hLen.
  • DK — выходной ключ

Функция MFcrypt работает по алгоритму:

  1. (B0 … Bp−1) = PBKDF2 PRF (P, S, 1, p * MFLen)
  2. Для всех i от 0 до p−1 применить функцию MF:
    Bi = MF(Bi, N)
  3. DK = PBKDF2 PRF (P, B0 || B1 || … || Bp−1,1, dkLen)

Потребление памяти оценивается в 128*r*N байт[5]. Соотношение количества чтений и записей в эту память оценивается в 100 % и 63 %[6].

Примеры

[править | править код]

Рекомендуемые параметры scrypt: N = 16384, r = 8, p = 1 (потребление памяти — около 16 МБ)[5][6].

Скорость вычисления одной операции scrypt на процессоре общего назначения составляет около 100 миллисекунд при настройке на использование 32 МБ памяти. При настройке на длительность операции в 1 миллисекунду используется слишком мало памяти и алгоритм становится слабее алгоритма bcrypt, настроенного на сравнимую скорость[7].

Криптовалюта Litecoin использует такие параметры scrypt: N = 1024, r = 1, p = 1, размер входного параметра и соли — 80 байт, размер DK — 256 бит (32 байта)[8]. Потребление оперативной памяти — около 128 КБ. Вычисление такого scrypt на видеокартах приблизительно в 10 раз быстрее, чем на процессорах общего назначения[6], что является признаком выбора недостаточно сильных параметров[7].

См. также

[править | править код]

Примечания

[править | править код]
  1. ↑ Colin Percival on Twitter: "For the record, "scrypt" is pronounced "ess crypt". Like bcrypt, except with an S instead of the B. It is NOT pronounced "script".". Дата обращения: 4 мая 2017. Архивировано 17 февраля 2019 года.
  2. ↑ C. Percival, S. Josefsson. The scrypt Password-Based Key Derivation Function (неопр.). — Инженерный совет Интернета, 2012. — 17 September.
  3. ↑ Litecoin — Bitcoin. Дата обращения: 16 июля 2013. Архивировано 16 июня 2018 года.
  4. ↑ Архивированная копия. Дата обращения: 17 июля 2013. Архивировано 17 декабря 2013 года. page 5
  5. ↑ 1 2 Crypto.Scrypt
  6. ↑ 1 2 3 http://2012.zeronights.org/includes/docs/SolarDesigner%20-%20New%20Developments%20in%20Password%20Hashing.pdf Архивная копия от 28 декабря 2016 на Wayback Machine slide 4 «Issues with scrypt for mass user authentication»; slide 6
  7. ↑ 1 2 http://distro.ibiblio.org/openwall/presentations/Password-Hashing-At-Scale/YaC2012-Password-Hashing-At-Scale.pdf Архивная копия от 18 октября 2014 на Wayback Machine slide 18 «GPU Attacks on modern hashes»: «scrypt at up to ~1MB (misuse)»; slide 19-21
  8. ↑ Scrypt — Litecoin Wiki. Дата обращения: 17 июля 2013. Архивировано из оригинала 16 августа 2013 года.

Ссылки

[править | править код]

Реализации:

Источник — https://ru.wikipedia.org/w/index.php?title=Scrypt&oldid=124355421