Scrypt

Scrypt — это функция формирования ключа, предназначенная для усложнения аппаратных атак методом полного перебора (brute-force) за счёт требования значительного объёма оперативной памяти. Относится к классу memory-hard функций (функций, требовательных к памяти) и широко применяется в криптовалютах, системах хранения паролей и других областях, где необходима защита от массовых вычислительных атак.

История

Scrypt была разработана в 2009 году американским программистом Колином Персивалем (Colin Percival), известным также как создатель утилиты для резервного копирования Tarsnap. Первоначально функция предназначалась для использования в Tarsnap для защиты ключей шифрования от перебора. В 2012 году алгоритм был стандартизирован в документе RFC 7914 (Internet Research Task Force).

Основной мотивацией создания Scrypt стало стремление преодолеть недостатки существовавших на тот момент функций формирования ключа, таких как PBKDF2 и bcrypt. PBKDF2, хотя и позволяла регулировать вычислительную сложность, была крайне эффективна для реализации на специализированных интегральных схемах (ASIC) и графических процессорах (GPU), что делало её уязвимой для массовых атак. Bcrypt, в свою очередь, требовала больше памяти, но её объём был фиксирован и невелик. Scrypt ввела параметр, позволяющий задавать требуемый объём памяти, что сделало её первой широко распространённой memory-hard функцией.

С 2011 года Scrypt начала активно применяться в криптовалютах, в частности, в Litecoin (LTC), который стал первым крупным проектом, использующим алгоритм для майнинга. Это было сделано для того, чтобы сделать майнинг более доступным для владельцев персональных компьютеров и снизить преимущество ASIC-майнеров, доминировавших в сети Bitcoin (использующей SHA-256).

Принцип работы

Scrypt основана на алгоритме PBKDF2-HMAC-SHA256, но с добавлением этапа интенсивного использования памяти, называемого SMix (Sequential Memory-hard Mixing). Общий процесс вычисления можно разделить на три фазы:

1. Генерация массива (Expansion): На основе входного пароля и соли (случайной строки) с помощью PBKDF2 генерируется большой массив псевдослучайных данных. Размер этого массива задаётся параметром N (количество блоков) и r (размер блока). Общий объём памяти, необходимый для хранения массива, составляет примерно N r 128 байт.
2. Смешивание (SMix): Выполняется серия из N операций чтения и записи в сгенерированный массив. Каждая операция считывает случайно выбранный блок данных, обрабатывает его с помощью функции ROMix (Random Oracle Mix), а затем записывает результат обратно в массив. Ключевая особенность этого этапа — порядок доступа к памяти является случайным и зависит от предыдущих результатов. Это делает невозможным эффективное вычисление функции без хранения всего массива в быстрой памяти (например, в DRAM), так как любая попытка пересчитать данные на лету потребует многократного повторения операций, что резко замедлит вычисление.
3. Формирование ключа (Compression): Результирующий массив после смешивания и исходный пароль с солью подаются на вход PBKDF2 для получения финального ключа заданной длины.

Таким образом, Scrypt не просто требует много вычислений, а требует именно много быстрой памяти. Если злоумышленник пытается использовать ASIC или GPU с ограниченным объёмом встроенной памяти, он будет вынужден использовать медленную внешнюю память (например, HDD или SSD), что сделает перебор в тысячи раз медленнее.

Параметры

Эффективность и ресурсоёмкость Scrypt регулируются тремя основными параметрами:

• N (cost parameter): Параметр вычислительной сложности и объёма памяти. Определяет количество итераций и размер массива. Обычно задаётся как степень двойки (например, N=1024, 4096, 16384). Увеличение N в 2 раза удваивает и время вычисления, и требуемый объём памяти.
• r (block size factor): Размер блока данных (в байтах). Влияет на скорость доступа к памяти и эффективность использования кэша. Обычно принимает значения 8 или 16.
• p (parallelization parameter): Параметр параллелизма. Определяет количество независимых потоков вычислений. Увеличение p увеличивает время вычисления, но не влияет на объём памяти, так как каждый поток использует свой массив.

На практике для защиты паролей часто используют комбинацию N=16384, r=8, p=1, что требует около 16 МБ памяти и занимает несколько секунд на современном процессоре. Для криптовалют параметры могут быть иными, например, в Litecoin используется N=1024, r=1, p=1.

Применение

Криптовалюты

Scrypt стал основой для многих криптовалют, стремящихся к децентрализации майнинга и устойчивости к ASIC-атакам. Наиболее известные примеры:

• Litecoin (LTC): Первая и самая капитализированная криптовалюта на Scrypt.
• Dogecoin (DOGE): Изначально запущен на Scrypt, что позволило майнить его совместно с Litecoin (merged mining).
• Vertcoin (VTC): Проект, активно сопротивляющийся появлению ASIC-майнеров и периодически меняющий параметры алгоритма.

В контексте криптовалют Scrypt используется как proof-of-work (доказательство выполнения работы) — майнеры соревнуются в нахождении хеша, удовлетворяющего условию сложности, что требует многократного вычисления функции.

Защита паролей

Scrypt рекомендуется для хранения хешей паролей в базах данных веб-приложений и сервисов. Благодаря требовательности к памяти, она значительно усложняет задачу злоумышленнику, получившему доступ к базе данных: даже с мощным GPU он сможет перебирать лишь десятки или сотни паролей в секунду, тогда как для PBKDF2 этот показатель может достигать миллионов.

Шифрование ключей

Scrypt используется в утилитах шифрования, таких как Tarsnap и VeraCrypt, для генерации ключа из пароля пользователя. Это обеспечивает высокую стойкость к атакам на пароль.

Критика и ограничения

Несмотря на преимущества, Scrypt имеет ряд недостатков:

1. Уязвимость к ASIC: Хотя Scrypt изначально проектировалась как ASIC-устойчивая, с 2014 года появились специализированные майнеры для Litecoin (например, Antminer L3+), которые демонстрируют высокую производительность. Это снизило её главное преимущество в криптовалютной сфере.
2. Ресурсоёмкость для серверов: Для проверки пароля при каждом входе пользователя сервер должен выделить значительный объём памяти (например, 16 МБ) и вычислительное время. При большом количестве одновременных запросов это может привести к деградации производительности.
3. Сложность настройки: Неправильный выбор параметров (N, r, p) может сделать функцию либо слишком слабой, либо неприемлемо медленной. Например, слишком маленькое значение N снижает защиту, а слишком большое — делает использование на мобильных устройствах или в браузерах нецелесообразным.
4. Атаки на кэш: Существуют теоретические атаки, использующие утечки по времени доступа к кэш-памяти (cache-timing attacks), которые могут частично раскрыть информацию о вычислениях. Однако на практике такие атаки сложны и требуют физического доступа к системе.

Сравнение с другими функциями

• PBKDF2: Менее требовательна к памяти, легко ускоряется на GPU и ASIC. Scrypt превосходит её по стойкости к массовым атакам.
• bcrypt: Требует фиксированного объёма памяти (около 4 КБ), что делает её уязвимой для ASIC. Scrypt позволяет гибко настраивать объём памяти, что даёт ей преимущество в долгосрочной перспективе.
• Argon2: Победитель конкурса Password Hashing Competition (2015). Argon2 (в версиях Argon2d и Argon2id) считается более современной и эффективной memory-hard функцией, чем Scrypt. Она лучше защищена от атак по сторонним каналам и имеет более гибкую архитектуру. В настоящее время Argon2 рекомендуется для новых проектов, но Scrypt остаётся широко распространённой и хорошо изученной.

Интересные факты

• Название «Scrypt» происходит от «Script» (сценарий), но с заменой «i» на «y» для благозвучия.
• Колин Персиваль, создатель Scrypt, является доктором наук в области компьютерной безопасности и получил престижную премию ACM Doctoral Dissertation Award в 2012 году.
• В 2014 году в сети Litecoin произошёл форк (разделение) из-за спора о параметрах Scrypt, в результате чего появилась монета Litecoin Classic.

Источники

• RFC 7914 — The scrypt Password-Based Key Derivation Function (Internet Research Task Force, 2016)
• Colin Percival. «Stronger Key Derivation via Sequential Memory-Hard Functions» (2009)
• Официальная документация Tarsnap (tarsnap.com)
• Стандарты NIST SP 800-132 (рекомендации по хранению паролей)