Scrypt - Википедия - scrypt

зашифровать
Общий
Дизайнеров	Колин Персиваль
Впервые опубликовано	2009
Деталь шифра
Размеры дайджеста	Переменная
Размеры блоков	Переменная
Раундов	Переменная

В криптография, зашифровать (произносится как "эсс склеп"^[1]) на основе пароля ключевая деривационная функция созданный Колином Персивалем, первоначально для Tarsnap онлайн-сервис резервного копирования.^[2] Алгоритм был специально разработан, чтобы сделать крупномасштабное выполнение дорогостоящим. нестандартные аппаратные атаки требуя большого количества памяти. В 2016 году алгоритм сценария был опубликован компанией IETF в качестве RFC 7914. Упрощенная версия scrypt используется как доказательство работы схема по ряду криптовалюты, впервые реализованный анонимным программистом ArtForz в Tenebrix, а затем Fairbrix и Litecoin вскоре после.^[3]

Вступление

На основе пароля ключевая деривационная функция (KDF на основе пароля) обычно спроектирован таким образом, чтобы требовать больших вычислительных ресурсов, поэтому вычисление занимает относительно много времени (скажем, порядка нескольких сотен миллисекунд). Законным пользователям необходимо выполнять эту функцию только один раз за операцию (например, аутентификацию), поэтому требуемое время незначительно. Однако для атаки методом грубой силы, вероятно, потребуется выполнить операцию миллиарды раз, и в этот момент требования по времени станут значительными и, в идеале, запретительными.

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

Функция scrypt предназначена для предотвращения таких попыток, повышая требования к ресурсам алгоритма. В частности, алгоритм предназначен для использования большого объема памяти по сравнению с другими KDF на основе паролей,^[4] делая размер и стоимость аппаратной реализации намного более дорогими, и, следовательно, ограничивая объем параллелизма, который может использовать злоумышленник при заданном количестве финансовых ресурсов.

Обзор

Большие потребности scrypt в памяти исходят из большого вектора псевдослучайный битовые строки, которые генерируются как часть алгоритма. После того, как вектор сгенерирован, к его элементам обращаются в псевдослучайном порядке и комбинируются для создания производного ключа. Простая реализация должна будет хранить весь вектор в ОЗУ, чтобы к нему можно было обращаться по мере необходимости.

Поскольку элементы вектора генерируются алгоритмически, каждый элемент может быть сгенерирован на лету по мере необходимости, сохраняя только один элемент в памяти за раз, что значительно снижает требования к памяти. Однако создание каждого элемента должно быть дорогостоящим в вычислительном отношении, и ожидается, что к элементам будет осуществляться многократный доступ во время выполнения функции. Таким образом, существует значительный компромисс в скорости, чтобы избавиться от больших требований к памяти.

Такого рода компромисс между временем и памятью часто присутствует в компьютерных алгоритмах: скорость может быть увеличена за счет использования большего объема памяти, или требования к памяти уменьшены за счет выполнения большего количества операций и увеличения времени. Идея scrypt состоит в том, чтобы сознательно сделать этот компромисс дорогостоящим в любом направлении. Таким образом, злоумышленник может использовать реализацию, которая не требует много ресурсов (и, следовательно, может быть массово распараллелена с ограниченными затратами), но работает очень медленно, или использовать реализацию, которая работает быстрее, но имеет очень большие требования к памяти и, следовательно, дороже для распараллелить.

Алгоритм

В алгоритм входят следующие параметры:

Кодовая фраза - строка символов для хеширования.
Соль - Строка символов, изменяющая хеш для защиты от Радужный стол нападения
N - параметр стоимости процессора / памяти.
p - параметр распараллеливания; натуральное число такое, что p ≤ (2³²- 1) * hLen / MFLen.
dkLen - Предполагаемая длина вывода в октетах производного ключа; положительное целое число, удовлетворяющее dkLen ≤ (2³²- 1) * hLen.
r - параметр размера блока, который точно настраивает размер и производительность последовательного чтения из памяти. 8 обычно используется.
hLen - длина хэш-функции в октетах (32 для SHA256).
MFlen - длина в октетах вывода функции микширования (SMix ниже). Определен как r * 128 в RFC7914.

Функция зашифровать Входы:      Кодовая фраза: байты строка символов для хеширования      Соль: байты случайный соль      CostFactor (N): целое число Параметр стоимости ЦП / памяти - должен быть степенью двойки (например, 1024).      BlockSizeFactor (r): целое число параметр размера блока (обычно используется 8)      ParallelizationFactor (p): Целое число Параметр распараллеливания. (1..2³²-1 * hLen / MFlen)      DesiredKeyLen: целое число Желаемая длина ключа в байтах   Выход:      DerivedKey: байты массив байтов, DesiredKeyLen long   Шаг 1. Получите дорогую соль   blockSize ← 128 * BlockSizeFactor // Длина (в байтах) вывода функции микширования SMix (например, 128 * 8 = 1024 байта)   Используйте PBKDF2 для генерации начальных 128 * BlockSizeFactor * p байтов данных (например, 128 * 8 * 3 = 3072 байта)   Рассматривайте результат как массив п элементы, каждая запись размер блока байты (например, 3 элемента по 1024 байта)   [B₀... B_{p − 1}] ← PBKDF2_HMAC-SHA256(Кодовая фраза, Соль, 1, blockSize * ParallelizationFactor) Смешайте каждый блок B Затратное время с использованием ROMix функция (каждый блок можно смешивать параллельно)   за я ← 0 к п-1 делать      B_я ← ROMix (B_я, CostFactor) Все элементы B - это наша новая «дорогая» соль.   дорогоСоль ← B₀∥B₁∥B₂∥ ... ∥B_п-1  // где ∥ - конкатенация    Шаг 2. Используйте PBKDF2, чтобы сгенерировать желаемое количество байтов, но используя только что сгенерированную дорогостоящую соль.   возвращаться PBKDF2_HMAC-SHA256(Кодовая фраза, RoadSalt, 1, DesiredKeyLen);

Где PBKDF2 (P, S, c, dkLen) обозначение определено в RFC 2898, где c - количество итераций.

Это обозначение используется RFC 7914 для указания использования PBKDF2 с c = 1.

Функция ROMix (Блок, Итерации) Создавать Итерации копии Икс   X ← Блок за я ← 0 к Итерации − 1 делать      V_я ← X X ← BlockMix (X) за я ← 0 к Итерации − 1 делать      j ← Integerify (X) mod Итерации X ← BlockMix (X xor V_j)   возвращаться Икс

Где RFC 7914 определяет Целочисленное значение (X) в результате интерпретации последних 64 байтов X как прямой порядок байтов целое число A₁.

Поскольку итерации равны 2 в степени N, только первый Максимальный (N / 8) байт среди последний 64 байта X, интерпретируемого как прямой порядок байтов целое число A₂, действительно необходимы для вычисления Integerify (X) mod Iterations = A₁ мод Итерации = A₂ мод Итерации.

Функция БлокМикс (B): Блок B - это r 128-байтовых фрагментов (что эквивалентно 2r 64-байтовых фрагментов)    r ← Длина (B) / 128; Рассматривайте B как массив из 2r 64-байтовых блоков    [B₀... B_2р-1] ← B X ← B_{2r − 1}    за я ← 0 к 2r − 1 делать        X ← Сальса20 / 8 (X xor B_я)  // Salsa20 / 8 хеширует от 64 до 64 байтов        Y_я ← X возвращаться ← Y₀∥Y₂∥ ... ∥Y_{2r − 2} ∥ Y₁∥Y₃∥ ... ∥Y_{2r − 1}

Где Сальса20 / 8 это 8-раундовый вариант Сальса20.

Использование криптовалюты

Scrypt используется во многих криптовалютах как доказательство работы алгоритм. Впервые он был реализован для Tenebrix (выпущен в сентябре 2011 г.) и послужил основой для Litecoin и Dogecoin, который также принял свой алгоритм шифрования.^[5]^[6] Добыча криптовалюты которые используют scrypt, часто выполняются на графических процессорах (GPU ), поскольку графические процессоры обычно имеют значительно большую вычислительную мощность (для некоторых алгоритмов) по сравнению с процессором.^[7] Это привело к нехватке высокопроизводительных графических процессоров из-за роста цен на эти валюты в ноябре и декабре 2013 года.^[8]

По состоянию на май 2014 г. ASIC Оборудование для майнинга доступно для криптовалют на основе scrypt.^{[нужна цитата ]}

Смотрите также

Ключевая функция вывода
Аргон2, победитель конкурса хеширования паролей
склеп, хранение паролей и схема проверки
PBKDF2, широко используемая стандартная функция вывода ключа на основе пароля
bcrypt, функция хеширования паролей с использованием Blowfish
Компромисс между пространством и временем

внешняя ссылка

[1] "Колин Персиваль в Твиттере".

[2] "напишите страницу на сайте Tarsnap". Получено 21 января 2014.

[3] Алек Лю. «Помимо биткойнов: руководство по наиболее перспективным криптовалютам».

[4] Более надежный вывод ключей с помощью последовательных функций с жесткой памятью, Колин Персиваль

[5] Андреас М. Антонопулос (3 декабря 2014 г.). Освоение биткойнов: разблокировка цифровых криптовалют. O'Reilly Media. С. 221, 223. ISBN 9781491902646.

[6] «История криптовалюты». Архивировано из оригинал 11 июня 2016 г.. Получено 27 июн 2014.

[7] Роман Гуэлфи-Гиббс. Конфигурации майнинга Litecoin Scrypt для Radeon 7950. Цифровые сервисы Amazon.

[8] Джоэл Хруска (10 декабря 2013 г.). «Массовый рост добычи Litecoin приводит к нехватке видеокарт». ExtremeTech.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]