Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать со скриптом .

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

В криптографии , Scrypt (произносится «ESS склепа» [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 состоит в том, чтобы сознательно сделать этот компромисс дорогостоящим в любом направлении. Таким образом, злоумышленник может использовать реализацию, которая не требует много ресурсов (и, следовательно, может быть массово распараллелена с ограниченными затратами), но работает очень медленно, или использовать реализацию, которая работает быстрее, но имеет очень большие требования к памяти и, следовательно, дороже в использовании. распараллелить.

Алгоритм [ править ]

Алгоритм включает следующие параметры:

  • Кодовая фраза - строка символов для хеширования.
  • Salt - строка символов, изменяющая хэш для защиты от атак из таблицы Rainbow.
  • N - параметр стоимости процессора / памяти.
  • p - параметр распараллеливания; положительное целое число такое, что p ≤ (2 32 - 1) * hLen / MFLen.
  • dkLen - Предполагаемая длина вывода в октетах производного ключа; положительное целое число, удовлетворяющее dkLen ≤ (2 32 - 1) * hLen.
  • r - параметр размера блока, который точно настраивает размер и производительность последовательного чтения памяти. 8 обычно используется.
  • hLen - длина хэш-функции в октетах (32 для SHA256).
  • MFlen - длина в октетах вывода функции микширования ( SMix ниже). Определен как r * 128 в RFC7914.
Функция Scrypt  Входы: Passphrase: байты  строка символов , которые будут хэшированной Соль: Байты  случайной соли CostFactor (N): Целое число  процессоры / параметр стоимости памяти - Должна быть степенью 2 (например , 1024) BlockSizeFactor (г): Integer  параметра блочных (8 обычно используется) ParallelizationFactor (p): Целочисленный  параметр параллелизации. (1..2 32 -1 * hLen / MFlen) DesiredKeyLen: Целое число  Желаемая длина ключа в байтах  Выход: DerivedKey: Байты массив байтов, DesiredKeyLen long Шаг 1. Сгенерируйте дорогостоящий солевой блокSize ← 128 * BlockSizeFactor  // Длина (в байтах) вывода функции микширования SMix (например, 128 * 8 = 1024 байта) Используйте PBKDF2 для генерации начальных 128 * BlockSizeFactor * p байтов данных (например, 128 * 8 * 3 = 3072 байта).  Рассматривайте результат как массив из p элементов, каждая запись представляет собой байты размера блока (например, 3 элемента, каждые 1024 байта) [B 0 ... B р-1 ] ← PBKDF2 HMAC-SHA256 ( Passphrase , соль , 1, BLOCKSIZE * ParallelizationFactor) Смешайте каждый блок в B раз за раз, используя функцию ROMix (каждый блок можно смешивать параллельно)  для i ← от 0 до p-1 do B i ← ROMix (B i , CostFactor) Все элементы B - это наша новая «дорогая» соль RoadSalt ← B 0 ∥B 1 ∥B 2 ∥ ... ∥B p-1  // где ∥ - конкатенация  Шаг 2. Используйте PBKDF2, чтобы сгенерировать желаемое количество байтов, но используя только что сгенерированную дорогостоящую соль,  верните PBKDF2 HMAC-SHA256 (Passphrase, strictSalt, 1, DesiredKeyLen);

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

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

Функция ROMix (блок, итерации) Создание итерационных копий X X ← Блок for i ← 0 to Iterations − 1 do V i ← X X ← BlockMix (X) for i ← 0 to Iterations − 1 do j ← Integerify (X) mod Итерации  X ← BlockMix (X xor V j ) вернуть X

Там , где RFC 7914 определяет Integerify (X) , в результате интерпретации последних 64 байта X в качестве маленького обратный порядок байт целого числа A 1 .

Так как Итерации равно 2 в степени N, только первый потолка (N / 8) байты среди последних 64 байт X, интерпретируемых как маленького обратного порядка байт целого числа А 2 , действительно необходимы для вычисления Integerify (X) по модулю Итерация = 1 моды Итерация = А 2 моды Итерация .

Функция BlockMix (B): Блок B - это r 128-байтовых фрагментов (что эквивалентно 2r 64-байтовых фрагментов) r ← Длина (B) / 128; Рассматривайте B как массив из 2r 64-байтовых фрагментов [B 0 ... B 2r-1 ] ← B X ← B 2r − 1  для i ← от 0 до 2r − 1 do X ← Salsa20 / 8 (X xor B i ) // Хеширование Salsa20 / 8 из 64 байтов в 64 байта Y i ← X return ← Y 0 ∥Y 2 ∥ ... ∥Y 2r − 2 ∥ Y 1 ∥Y 3 ∥ ... ∥Y 2r − 1

Где Salsa20 / 8 - это 8-раундовая версия Salsa20 .

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

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

С мая 2014 года доступно специализированное оборудование для майнинга ASIC для криптовалют на основе scrypt. [ необходима цитата ]

См. Также [ править ]

  • Ключевая деривационная функция
  • Argon2 , победитель конкурса хеширования паролей
  • крипта , хранение паролей и схема проверки
  • 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. ↑ Joel Hruska (10 декабря 2013 г.). «Массовый рост добычи Litecoin приводит к нехватке видеокарт» . ExtremeTech.

Внешние ссылки [ править ]

  • Страница скрипта на сайте Tarsnap.
  • Оригинальная бумага для рисования.