scrypt
| Криптографическая</br>хеш-функция | |
| Название |
scrypt |
|---|---|
| Разработчик |
Колин Персиваль |
| Впервые опубликован |
май 2009 |
scrypt — адаптивная криптографическая функция формирования ключа на основе пароля, созданная офицером безопасности FreeBSD Colin Percival для системы хранения резервных копий Tarsnap. Функция создана таким образом, чтобы усложнить атаку перебором при помощи ПЛИС. Для её вычисления требуется значительный объем памяти со случайным доступом. 17 сентября 2012 года алгоритм scrypt был опубликован IETF в виде Internet Draft, планируется его внесение в RFC[1]. Используется, например, в качестве proof-of-work в криптовалюте Litecoin[2].
Основанные на пароле функции формирования ключа (password-based key derivation function, PBKDF) обычно разрабатываются таким образом, чтобы требовать относительно большого времени вычисления (по порядку величины — сотни миллисекунд). При использовании легальным пользователем требуется вычислить подобную функцию один раз (например при аутентификации) и такое время допустимо. Но при проведении атаки полного перебора (brute force) атакующему требуется произвести миллиарды вычислений функции и её вычислительная сложность делает атаку более медленной и дорогой.
Однако ранние функции PBKDF (например PBKDF2, разработанная RSA Laboratories) вычисляются сравнительно быстро, и их перебор может быть эффективно реализован на специализированном оборудовании (FPGA или ASIC). Такая реализация позволяет запускать масштабные параллельные атаки перебора грубой силы, например, с использованием сотен экземпляров функции в каждой микросхеме FPGA.
Функция scrypt разрабатывалась с целью усложнить аппаратные реализации путём увеличения количества ресурсов, требуемых для вычисления. Данный алгоритм использует значительное количество оперативной памяти (памяти со случайным доступом) по сравнению с другими PBKDF. Память в scrypt используется для хранения большого вектора псевдослучайных битовых последовательностей, генерируемых в начале алгоритма[3]. После создания вектора его элементы запрашиваются в псевдослучайном порядке и комбинируются друг с другом для получения ключа (derived key). Так как алгоритм генерации вектора известен, возможна реализация scrypt, не требующая памяти, а высчитывающая каждый элемент в момент обращения. Однако, вычисление элемента относительно сложно и в процессе работы функции scrypt каждый элемент считывается много раз. В scrypt заложен такой баланс между памятью и временем, что реализации, не использующие память, слишком медленны.
Определение scrypt
scrypt (P, S, N, r, p, dkLen) = MFcryptHMAC 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) — последовательная функция, требующая память со случайным доступом (отображение из <math>Z_{256}^{MFLen} * N</math> в <math>Z_{256}^{MFLen}</math> (в scrypt — SMix на базе Salsa20/8)
- MFLen — длина блока, перемешиваемого в MF (в байтах). MFLen =128 * r.
Входные параметры scrypt и MFcrypt:
- P — пароль (passphrase) — байтовая строка.
- S — соль (salt) — байтовая строка.
- N — параметр, задающий сложность (количество итераций для MF).
- r — параметр, задающий размер блока.
- p — степень параллельности, целое число, меньшее чем (232 − 1)*hLen/MFLen
- dkLen — требуемая длина выходного ключа в байтах, не более чем (232 − 1)*hLen.
- DK — выходной ключ
Функция MFcrypt работает по алгоритму:
- (B0 … Bp−1) = PBKDF2 PRF (P, S, 1, p * MFLen)
- Для всех i от 0 до p−1 применить функцию MF:
- Bi = MF(Bi, N)
- DK = PBKDF2 PRF (P, B0 || B1 || … || Bp−1,1, dkLen)
Потребление памяти оценивается в 128*r*N байт[4]. Соотношение количества чтений и записей в эту память оценивается в 100 % и 63 %[5].
Примеры
Рекомендуемые параметры scrypt: N = 16384, r = 8, p = 1 (потребление памяти около 16 МБ)[4][5]
Скорость вычисления одной операции scrypt на процессоре общего назначения составляет около 100 миллисекунд при настройке на использование 32 МБ памяти. При настройке на длительность операции в 1 миллисекунду, используется слишком мало памяти и алгоритм становится слабее алгоритма bcrypt, настроенного на сравнимую скорость.[6]
Криптовалюта Litecoin использует такие параметры scrypt: N = 1024, r = 1, p = 1, размер входного параметра и соли — 80 байт, размер DK — 256 бит (32 байта)[7]. Потребление оперативной памяти — около 128 КБ. Вычисление такого scrypt на видеокартах приблизительно в 10 раз быстрее чем на процессорах общего назначения[5], что является признаком выбора недостаточно сильных параметров[6].
См. также
- Crypt (C)
- Crypt (Unix)
- PBKDF2
- bcrypt
- HEKS (Rienhold, 1999)
- slothKDF (Elias Yarrkov, dhbitty)
- Time-memory tradeoff
Напишите отзыв о статье "Scrypt"
Примечания
- ↑ C. Percival, S. Josefsson (2012-09-17). «[tools.ietf.org/html/draft-josefsson-scrypt-kdf The scrypt Password-Based Key Derivation Function]» (IETF).
- ↑ [en.bitcoin.it/wiki/Litecoin Litecoin — Bitcoin]
- ↑ suanpalm3.kmutnb.ac.th/journal/pdf/vol16/ch17.pdf page 5
- ↑ 1 2 [hackage.haskell.org/packages/archive/scrypt/0.3.2/doc/html/Crypto-Scrypt.html Crypto.Scrypt]
- ↑ 1 2 3 2012.zeronights.org/includes/docs/SolarDesigner%20-%20New%20Developments%20in%20Password%20Hashing.pdf slide 4 «Issues with scrypt for mass user authentication»; slide 6
- ↑ 1 2 distro.ibiblio.org/openwall/presentations/Password-Hashing-At-Scale/YaC2012-Password-Hashing-At-Scale.pdf slide 18 «GPU Attacks on modern hashes»: «scrypt at up to ~1MB (misuse)»; slide 19-21
- ↑ [litecoin.info/Scrypt Scrypt — Litecoin Wiki]
Ссылки
- [www.tarsnap.com/scrypt.html The scrypt key derivation function] — Описание scrypt на сайте Tarsnap
- Colin Percival, [www.tarsnap.com/scrypt/scrypt.pdf «Stronger key derivation via sequential memory-hard functions»] // BSDCan’09, Май 2009
- Colin Percival, [www.tarsnap.com/scrypt/scrypt-slides.pdf scrypt: A key derivation function. Doing our best to thwart TLAs armed with ASICs], December 4, 2012
Реализации:
- [www.zer7.com/software.php?page=cryptsharp C# implementation.]
- [github.com/kocakosm/pitaya/blob/master/src/org/kocakosm/pitaya/security/SCrypt.java Java implementation.]
- [github.com/DomBlack/php-scrypt PHP implementation.]
| ||||||||||||||
Отрывок, характеризующий Scrypt
– Но особенно хорошо, – говорил один, рассказывая неудачу товарища дипломата, – особенно хорошо то, что канцлер прямо сказал ему, что назначение его в Лондон есть повышение, и чтоб он так и смотрел на это. Видите вы его фигуру при этом?…– Но что всего хуже, господа, я вам выдаю Курагина: человек в несчастии, и этим то пользуется этот Дон Жуан, этот ужасный человек!
Князь Ипполит лежал в вольтеровском кресле, положив ноги через ручку. Он засмеялся.
– Parlez moi de ca, [Ну ка, ну ка,] – сказал он.
– О, Дон Жуан! О, змея! – послышались голоса.
– Вы не знаете, Болконский, – обратился Билибин к князю Андрею, – что все ужасы французской армии (я чуть было не сказал – русской армии) – ничто в сравнении с тем, что наделал между женщинами этот человек.
– La femme est la compagne de l'homme, [Женщина – подруга мужчины,] – произнес князь Ипполит и стал смотреть в лорнет на свои поднятые ноги.
Билибин и наши расхохотались, глядя в глаза Ипполиту. Князь Андрей видел, что этот Ипполит, которого он (должно было признаться) почти ревновал к своей жене, был шутом в этом обществе.
– Нет, я должен вас угостить Курагиным, – сказал Билибин тихо Болконскому. – Он прелестен, когда рассуждает о политике, надо видеть эту важность.
Он подсел к Ипполиту и, собрав на лбу свои складки, завел с ним разговор о политике. Князь Андрей и другие обступили обоих.
– Le cabinet de Berlin ne peut pas exprimer un sentiment d'alliance, – начал Ипполит, значительно оглядывая всех, – sans exprimer… comme dans sa derieniere note… vous comprenez… vous comprenez… et puis si sa Majeste l'Empereur ne deroge pas au principe de notre alliance… [Берлинский кабинет не может выразить свое мнение о союзе, не выражая… как в своей последней ноте… вы понимаете… вы понимаете… впрочем, если его величество император не изменит сущности нашего союза…]
– Attendez, je n'ai pas fini… – сказал он князю Андрею, хватая его за руку. – Je suppose que l'intervention sera plus forte que la non intervention. Et… – Он помолчал. – On ne pourra pas imputer a la fin de non recevoir notre depeche du 28 novembre. Voila comment tout cela finira. [Подождите, я не кончил. Я думаю, что вмешательство будет прочнее чем невмешательство И… Невозможно считать дело оконченным непринятием нашей депеши от 28 ноября. Чем то всё это кончится.]
И он отпустил руку Болконского, показывая тем, что теперь он совсем кончил.
– Demosthenes, je te reconnais au caillou que tu as cache dans ta bouche d'or! [Демосфен, я узнаю тебя по камешку, который ты скрываешь в своих золотых устах!] – сказал Билибин, y которого шапка волос подвинулась на голове от удовольствия.
Все засмеялись. Ипполит смеялся громче всех. Он, видимо, страдал, задыхался, но не мог удержаться от дикого смеха, растягивающего его всегда неподвижное лицо.
– Ну вот что, господа, – сказал Билибин, – Болконский мой гость в доме и здесь в Брюнне, и я хочу его угостить, сколько могу, всеми радостями здешней жизни. Ежели бы мы были в Брюнне, это было бы легко; но здесь, dans ce vilain trou morave [в этой скверной моравской дыре], это труднее, и я прошу у всех вас помощи. Il faut lui faire les honneurs de Brunn. [Надо ему показать Брюнн.] Вы возьмите на себя театр, я – общество, вы, Ипполит, разумеется, – женщин.
– Надо ему показать Амели, прелесть! – сказал один из наших, целуя кончики пальцев.
– Вообще этого кровожадного солдата, – сказал Билибин, – надо обратить к более человеколюбивым взглядам.
– Едва ли я воспользуюсь вашим гостеприимством, господа, и теперь мне пора ехать, – взглядывая на часы, сказал Болконский.
– Куда?
– К императору.
– О! о! о!
– Ну, до свидания, Болконский! До свидания, князь; приезжайте же обедать раньше, – пocлшaлиcь голоса. – Мы беремся за вас.
– Старайтесь как можно более расхваливать порядок в доставлении провианта и маршрутов, когда будете говорить с императором, – сказал Билибин, провожая до передней Болконского.
– И желал бы хвалить, но не могу, сколько знаю, – улыбаясь отвечал Болконский.
– Ну, вообще как можно больше говорите. Его страсть – аудиенции; а говорить сам он не любит и не умеет, как увидите.
На выходе император Франц только пристально вгляделся в лицо князя Андрея, стоявшего в назначенном месте между австрийскими офицерами, и кивнул ему своей длинной головой. Но после выхода вчерашний флигель адъютант с учтивостью передал Болконскому желание императора дать ему аудиенцию.
Император Франц принял его, стоя посредине комнаты. Перед тем как начинать разговор, князя Андрея поразило то, что император как будто смешался, не зная, что сказать, и покраснел.
– Скажите, когда началось сражение? – спросил он поспешно.
Князь Андрей отвечал. После этого вопроса следовали другие, столь же простые вопросы: «здоров ли Кутузов? как давно выехал он из Кремса?» и т. п. Император говорил с таким выражением, как будто вся цель его состояла только в том, чтобы сделать известное количество вопросов. Ответы же на эти вопросы, как было слишком очевидно, не могли интересовать его.
– В котором часу началось сражение? – спросил император.
– Не могу донести вашему величеству, в котором часу началось сражение с фронта, но в Дюренштейне, где я находился, войско начало атаку в 6 часу вечера, – сказал Болконский, оживляясь и при этом случае предполагая, что ему удастся представить уже готовое в его голове правдивое описание всего того, что он знал и видел.
Но император улыбнулся и перебил его:
– Сколько миль?
– Откуда и докуда, ваше величество?
– От Дюренштейна до Кремса?
