Scrypt

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

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

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

Функція scrypt розроблялася з метою ускладнення апаратних реалізацій шляхом збільшення кількості ресурсів, необхідних для обчислення. Даний алгоритм використовує значну кількість оперативної пам'яті (пам'яті з довільним доступом) порівняно з іншими PBKDF. Пам'ять у scrypt використовується для зберігання великого вектора псевдовипадкових бітових послідовностей, що генеруються, на початку алгоритму. Після створення вектора його елементи запитуються у псевдовипадковому порядку і комбінуються один з одним для отримання ключа. Так як алгоритм генерації вектора відомий, можлива реалізація scrypt, не вимагає пам'яті, і вираховує кожен елемент в момент звернення. Однак, обчислити елемент відносно складно і в процесі роботи функції scrypt кожен елемент прочитується багато разів. У scrypt закладений такий баланс між пам'яттю і часом, і реалізації, що не використовують пам'ять, надто повільні.

Визначення scrypt

scrypt (P, S, N, r, p, dkLen) = MFcrypt_{HMAC 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) — послідовна функція, що потребує пам'ять із довільним доступом (відображення ${\displaystyle Z_{256}^{MFLen}*N}$ в ${\displaystyle Z_{256}^{MFLen}}$ у scrypt — SMix на базі Salsa20/8)
• MFLen — довжина блока, що перемішується у MF (в байтах). MFLen =128 * r.

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

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

Функція MFcrypt працює за алгоритмом:

1. (B₀ … B_p−1) = PBKDF2 _PRF (P, S, 1, p * MFLen)
2. Для всіх i від 0 до p−1 застосувати функцію MF:

   B_i = MF(B_i, N)

3. DK = PBKDF2 _PRF (P, B0 || B1 || … || B_p−1,1, dkLen)

Споживання пам'яті оцінюється в 128*r*N байт. Співвідношення кількості читань і записів в цю пам'ять оцінюється в 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 байти). Споживання оперативної пам'яті — близько 128 КБ. Обчислення такого scrypt на відеокартах приблизно в 10 разів швидше, ніж на процесорах загального призначення, що є ознакою вибору недостатньо сильних параметрів.

Див. також

• PBKDF2
• bcrypt
• Просторово-часова домовленість

Примітки

1. . Twitter. Colin Percival. 23 травня 2016. Архів оригіналу за 22 лютого 2022. Процитовано 3 квітня 2018. (англ.)
2. . Архів оригіналу за 16 червня 2018. Процитовано 3 квітня 2018.
3. http://suanpalm3.kmutnb.ac.th/journal/pdf/vol16/ch17.pdf [ 17 грудня 2013 у Wayback Machine.] page 5
4. Crypto.Scrypt
5. . Архів оригіналу за 16 серпня 2013. Процитовано 3 квітня 2018.
6. 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. 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

Посилання

• The scrypt key derivation function [ 28 травня 2019 у Wayback Machine.] — Опис scrypt на сайті Tarsnap
• Colin Percival, «Stronger key derivation via sequential memory-hard functions» [ 14 квітня 2019 у Wayback Machine.] // BSDCan'09, Травень 2009
• Colin Percival, scrypt: A key derivation function. [ 24 червня 2018 у Wayback Machine.] Doing our best to thwart TLAs armed with ASICs [ 24 червня 2018 у Wayback Machine.], December 4, 2012
• Реалізація на C# [ 4 квітня 2018 у Wayback Machine.]
• реалізація на Java
• реалізація на PHP [ 11 червня 2018 у Wayback Machine.]
• scrypt в стандартній бібліотеці Go [ 16 червня 2018 у Wayback Machine.]