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 (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}\ast 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 байт^[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].

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

• 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.]

• Криптографічні геш-функції

• Шаблон:Webarchive:посилання на Wayback Machine
• Вікіпедія:Запити на переклад
• Сторінки, що використовують InterwikiLanglist