scrypt

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

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

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

Функція scrypt розроблялася з метою ускладнення апаратних реалізацій шляхом збільшення кількості ресурсів, необхідних для обчислення. Даний алгоритм використовує значну кількість оперативної пам'яті (пам'яті з довільним доступом) порівняно з іншими PBKDF. Пам'ять у scrypt використовується для зберігання великого вектора псевдовипадкових бітових послідовностей, що генеруються, на початку алгоритму[3]. Після створення вектора його елементи запитуються у псевдовипадковому порядку і комбінуються один з одним для отримання ключа. Так як алгоритм генерації вектора відомий, можлива реалізація 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 байт[4]. Співвідношення кількості читань і записів в цю пам'ять оцінюється в 100 % і 63 %.

Приклади

Рекомендовані параметри scrypt: N = 16384, r = 8, p = 1 (споживання пам'яті — близько 16 МБ)

Швидкість обчислення однієї операції scrypt на процесорі загального призначення становить близько 100 мілісекунд при налаштуванні на використання 32 МБ пам'яті. При налаштуванні на тривалість операції в 1 мілісекунду використовується дуже мало пам'яті і алгоритм стає слабшим алгоритму bcrypt, налаштованого на порівнянну швидкість.

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

Див. також

Примітки
  1. https://twitter.com/cperciva/status/734613598383841281
  2. Litecoin — Bitcoin
  3. http://suanpalm3.kmutnb.ac.th/journal/pdf/vol16/ch17.pdf Архівовано 17 грудня 2013 у Wayback Machine. page 5
  4. Crypto.Scrypt
  5. Scrypt — Litecoin Wiki. Архів оригіналу за 16 серпня 2013. Процитовано 3 квітня 2018.
  6. http://2012.zeronights.org/includes/docs/SolarDesigner%20-%20New%20Developments%20in%20Password%20Hashing.pdf slide 4 «Issues with scrypt for mass user authentication»; slide 6
  7. http://distro.ibiblio.org/openwall/presentations/Password-Hashing-At-Scale/YaC2012-Password-Hashing-At-Scale.pdf slide 18 «GPU Attacks on modern hashes»: «scrypt at up to ~1MB (misuse)»; slide 19-21

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.