сценарий
| Общий | |
|---|---|
| Дизайнеры | Колин Персиваль |
| Впервые опубликовано | 2009 |
| Деталь шифрования | |
| Размеры дайджеста | переменная |
| Размеры блоков | переменная |
| Раунды | переменная |
В криптографии . scrypt (произносится как «эсс крипт») [1] на основе пароля, ) — это функция получения ключей созданная Колином Персивалем в марте 2009 года первоначально для службы онлайн-резервного копирования Tarsnap . [2] [3] Алгоритм был специально разработан для того, чтобы сделать проведение крупномасштабных специализированных аппаратных атак дорогостоящим , требующим больших объемов памяти. В 2016 году алгоритм scrypt был опубликован IETF как RFC 7914. [4] Упрощенная версия scrypt используется в качестве схемы доказательства работы рядом криптовалют , сначала реализованная анонимным программистом по имени ArtForz в Tenebrix, а вскоре после этого — Fairbrix и Litecoin . [5]
Введение [ править ]
на основе пароля Функция получения ключа (KDF на основе пароля) обычно рассчитана на интенсивные вычисления, поэтому ее вычисление занимает относительно много времени (скажем, порядка нескольких сотен миллисекунд). Законным пользователям необходимо выполнить эту функцию только один раз за операцию (например, аутентификацию), поэтому требуемое время незначительно. Однако для атаки методом грубой силы, скорее всего, потребуется выполнить операцию миллиарды раз, после чего требования ко времени станут значительными и, в идеале, непомерно высокими.
Предыдущие KDF на основе паролей (такие как популярный PBKDF2 от RSA Laboratories ) имели относительно низкие требования к ресурсам, то есть для их работы не требовалось сложное оборудование или большой объем памяти. Поэтому их легко и дешево реализовать аппаратно (например, на ASIC или даже FPGA ). Это позволяет злоумышленнику, обладающему достаточными ресурсами, запустить крупномасштабную параллельную атаку, создав сотни или даже тысячи аппаратных реализаций алгоритма и заставив каждую из них искать различное подмножество пространства ключей. Это делит время, необходимое для завершения атаки методом перебора, на количество доступных реализаций, что вполне возможно снизит ее до разумных временных рамок.
Функция scrypt предназначена для предотвращения таких попыток за счет повышения требований к ресурсам алгоритма. В частности, алгоритм предназначен для использования большого объема памяти по сравнению с другими KDF на основе паролей. [6] что делает размер и стоимость аппаратной реализации намного дороже и, следовательно, ограничивает объем параллелизма, который может использовать злоумышленник, при заданном объеме финансовых ресурсов.
Обзор [ править ]
Большие требования к памяти для scrypt обусловлены большим вектором псевдослучайных битовых строк, которые генерируются как часть алгоритма. После создания вектора доступ к его элементам осуществляется в псевдослучайном порядке и объединяются для получения производного ключа. Простая реализация должна была бы хранить весь вектор в оперативной памяти, чтобы к нему можно было получить доступ по мере необходимости.
Поскольку элементы вектора генерируются алгоритмически, каждый элемент может генерироваться « на лету» по мере необходимости, одновременно сохраняя в памяти только один элемент и, следовательно, значительно сокращая требования к памяти. Однако генерация каждого элемента требует больших вычислительных затрат, и ожидается, что к элементам придется обращаться много раз в ходе выполнения функции. Таким образом, чтобы избавиться от больших требований к памяти, приходится идти на компромисс в скорости.
Подобный компромисс между временем и памятью часто существует в компьютерных алгоритмах: скорость можно увеличить за счет использования большего количества памяти, или требования к памяти уменьшаются за счет выполнения большего количества операций и увеличения времени выполнения. Идея scrypt состоит в том, чтобы намеренно сделать этот компромисс дорогостоящим в любом направлении. Таким образом, злоумышленник может использовать реализацию, которая не требует большого количества ресурсов (и, следовательно, может быть подвергнута массовому распараллеливанию с ограниченными затратами), но работает очень медленно, или использовать реализацию, которая работает быстрее, но имеет очень большие требования к памяти и, следовательно, более дорога в использовании. распараллелить.
Алгоритм [ править ]
Function scrypt Inputs: This algorithm includes the following parameters: Passphrase: Bytes string of characters to be hashed Salt: Bytes string of random characters that modifies the hash to protect against Rainbow table attacks CostFactor (N): Integer CPU/memory cost parameter – Must be a power of 2 (e.g. 1024) BlockSizeFactor (r): Integer blocksize parameter, which fine-tunes sequential memory read size and performance. (8 is commonly used) ParallelizationFactor (p): Integer Parallelization parameter. (1 .. 232-1 * hLen/MFlen) DesiredKeyLen (dkLen): Integer Desired key length in bytes (Intended output length in octets of the derived key; a positive integer satisfying dkLen ≤ (232− 1) * hLen.) hLen: Integer The length in octets of the hash function (32 for SHA256). MFlen: Integer The length in octets of the output of the mixing function (SMix below). Defined as r * 128 in RFC7914. Output: DerivedKey: Bytes array of bytes, DesiredKeyLen long Step 1. Generate expensive salt blockSize ← 128*BlockSizeFactor // Length (in bytes) of the SMix mixing function output (e.g. 128*8 = 1024 bytes) Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data (e.g. 128*8*3 = 3072 bytes) Treat the result as an array of p elements, each entry being blocksize bytes (e.g. 3 elements, each 1024 bytes) [B0...Bp−1] ← PBKDF2HMAC-SHA256(Passphrase, Salt, 1, blockSize*ParallelizationFactor) Mix each block in B Costfactor times using ROMix function (each block can be mixed in parallel) for i ← 0 to p-1 do Bi ← ROMix(Bi, CostFactor) All the elements of B is our new "expensive" salt expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1 // where ∥ is concatenation Step 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generated return PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);
Где обозначение PBKDF2(P, S, c, dkLen) определено в RFC 2898, где c — количество итераций.
Это обозначение используется в RFC 7914 для указания использования PBKDF2 с c = 1.
Function ROMix(Block, Iterations)
Create Iterations copies of X
X ← Block
for i ← 0 to Iterations−1 do
Vi ← X
X ← BlockMix(X)
for i ← 0 to Iterations−1 do
j ← Integerify(X) mod Iterations
X ← BlockMix(X xor Vj)
return X
Где RFC 7914 определяет Integerify(X) в результате интерпретации последних 64 байтов X как целого числа с прямым порядком байтов A 1 .
Поскольку число итераций равно 2 в степени N, только первые байты Ceiling(N / 8) среди последних 64 байтов X, интерпретируемые как целое число с прямым порядком байтов A 2 . для вычисления фактически необходимы Integerify(X) mod Iterations = A1 mod Iterations = A2 mod Iterations.
Function BlockMix(B):
The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)
r ← Length(B) / 128;
Treat B as an array of 2r 64-byte chunks
[B0...B2r-1] ← B
X ← B2r−1
for i ← 0 to 2r−1 do
X ← Salsa20/8(X xor Bi) // Salsa20/8 hashes from 64-bytes to 64-bytes
Yi ← X
return ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1
Где Salsa20/8 — это 8-раундовая версия Salsa20 .
Использование криптовалюты [ править ]
Scrypt используется во многих криптовалютах в качестве алгоритма доказательства работы (точнее, как хеш-функция в Hashcash алгоритме доказательства работы ). Впервые он был реализован для Tenebrix (выпущен в сентябре 2011 года) и послужил основой для Litecoin и Dogecoin , которые также переняли его алгоритм шифрования. [7] [8] Майнинг криптовалют , использующих scrypt, часто выполняется на графических процессорах ( GPU ), поскольку графические процессоры, как правило, имеют значительно большую вычислительную мощность (для некоторых алгоритмов) по сравнению с CPU. [9] Это привело к нехватке высокопроизводительных графических процессоров из-за роста цен на эти валюты в ноябре и декабре 2013 года. [10]
Утилита [ править ]
| Разработчик(и) | Колин Персиваль |
|---|---|
| Стабильная версия | 1.3.2 [11] 
/ 2 октября 2023 г |
| Репозиторий | github |
| Веб-сайт | www |
Утилита scrypt была написана в мае 2009 года Колином Персивалем как демонстрация функции получения ключа сценария. [2] [3] Он доступен в большинстве Linux и BSD дистрибутивов .
См. также [ править ]
- Argon2 – победитель конкурса хеширования паролей 2015 г.
- bcrypt — функция хеширования паролей на основе Blowfish
- bcrypt - кроссплатформенная утилита шифрования файлов на основе Blowfish, разработанная в 2002 году. [12] [13] [14] [15]
- crypt — библиотечная функция Unix C
- crypt — утилита Unix
- ccrypt — утилита
- Функция вывода ключей
- Ключевая растяжка
- mcrypt — утилита
- PBKDF2 — широко используемая стандартная функция получения ключа на основе пароля 2.
- PufferFish — функция хеширования паролей с жестким кэшем, основанная на улучшенной конструкции bcrypt.
- Компромисс между пространством и временем
Ссылки [ править ]
- ^ «Колин Персиваль» . Твиттер . Архивировано из оригинала 17 февраля 2019 года.
- ^ Jump up to: Перейти обратно: а б «Функция получения ключа сценария» . Тарснап . Архивировано из оригинала 28 мая 2019 года . Проверено 21 января 2014 г.
- ^ Jump up to: Перейти обратно: а б «Руководство по общим командам SCRYPT(1)» . Страницы руководства Debian . Архивировано из оригинала 2 марта 2022 года . Проверено 2 марта 2022 г.
- ^ Персиваль, Колин; Йозефссон, Саймон (август 2016 г.). «Функция получения ключа на основе пароля» . Редактор RFC. Архивировано из оригинала 13 декабря 2021 года . Проверено 13 декабря 2021 г.
- ^ Алек Лю (29 ноября 2013 г.). «За пределами Биткойна: Путеводитель по наиболее перспективным криптовалютам» . Архивировано из оригинала 13 июня 2018 года . Проверено 8 июля 2017 г.
- ^ Персиваль, Колин. «Более надежный вывод ключей с помощью последовательных функций с жесткой памятью» (PDF) . Архивировано (PDF) из оригинала 14 апреля 2019 г. Проверено 11 ноября 2022 г.
- ^ Андреас М. Антонопулос (3 декабря 2014 г.). Освоение биткойнов: разблокировка цифровых криптовалют . О'Рейли Медиа. стр. 221, 223. ISBN. 9781491902646 .
- ^ «История криптовалюты» . litecoin.info вики . 7 февраля 2014 года. Архивировано из оригинала 11 июня 2016 года . Проверено 27 июня 2014 г.
- ^ Роман Гуэльфи-Гиббс. Конфигурации майнинга Litecoin Scrypt для Radeon 7950 . Цифровые услуги Amazon. Архивировано из оригинала 24 октября 2016 года . Проверено 11 сентября 2017 г.
- ^ Джоэл Хруска (10 декабря 2013 г.). «Массовый всплеск добычи Litecoin приводит к нехватке видеокарт» . ЭкстримТех. Архивировано из оригинала 12 декабря 2017 года . Проверено 1 января 2014 г.
- ^ «Выпуск 1.3.2» . 2 октября 2023 г. Проверено 20 октября 2023 г.
- ^ Шелли, Джонни; Столарчик, Филипп. «Bcrypt – шифрование файлов Blowfish (домашняя страница)» . Сорсфордж . Архивировано из оригинала 29 августа 2015 года . Проверено 8 апреля 2024 г.
- ^ «bcrypt APK для Android – скачать бесплатно на Droid Informer» . droidinformer.org . Архивировано из оригинала 15 февраля 2020 года . Проверено 2 марта 2022 г.
- ^ «Пакет Т2 – транк – bcrypt – Утилита для шифрования файлов» . t2sde.org . Архивировано из оригинала 28 октября 2017 года . Проверено 2 марта 2022 г.
- ^ «Информация о лицензировании Oracle® GoldenGate» . Справочный центр Oracle . Архивировано из оригинала 6 марта 2024 года . Проверено 8 апреля 2024 г.
