Каковы оптимальные факторы работы скрутки?

Я использую Java scrypt library для хранения паролей. Он вызывает значения N, r и p, когда я шифрую вещи, которые в его документации называются параметрами "стоимость процессора", "стоимость памяти" и "стоимость параллелизации". Проблема только в том, что я не знаю, что конкретно они подразумевают, или какие хорошие ценности будут для них; возможно, они каким-то образом соответствуют кнопкам -t, -m и -M на оригинальном приложении Colin Percival?

Есть ли у кого-нибудь предложения по этому поводу? Сама библиотека перечисляет N = 16384, r = 8 и p = 1, но я не знаю, является ли это сильным или слабым или что.

Ответ 1

В начале:

cpercival упомянул в своих слайдах с 2009 года что-то вокруг

(N = 2, 14, r = 8, p = 1) 100 мс (интерактивное использование) и
(N = 2, 20, r = 8, p = 1) 5s (чувствительное хранилище).

Эти значения оказались достаточно хорошими для общего использования (password-db для некоторых WebApp) даже сегодня (2012-09). Конечно, особенности зависят от приложения.

Кроме того, эти значения (в основном) означают:

N: общий коэффициент работы, количество итераций.
r: блокировать использование для основного хеша; тонко настраивает относительную стоимость памяти.
p: коэффициент параллелизации; тонко настраивает относительную стоимость процессора.

r и p предназначены для решения потенциальной проблемы, что скорость процессора и объем памяти и пропускная способность не увеличиваются, как ожидалось. Если производительность процессора увеличивается быстрее, вы увеличиваете p, вместо этого прорыв в технологии памяти обеспечивает улучшение порядка, вы увеличиваете r. И N должно идти в ногу с общим удвоением производительности за несколько промежутков времени.

Важно: все значения изменяют результат. (Обновлено:) Вот почему все параметры scrypt хранятся в результирующей строке.

Ответ 2

Память, необходимая для работы scrypt, рассчитывается как:

128 байт × N_cost × r_blockSizeFactor

для параметров, которые вы указываете (N=16384, r=8, p=1)

128 × 16384 × 8 = 16,777,216 байта = 16 МБ

Вы должны учитывать это при выборе параметров.

Bcrypt "слабее", чем Scrypt (хотя все еще на три порядка сильнее, чем PBKDF2), потому что ему требуется только 4 КБ памяти. Вы хотите затруднить распараллеливание растрескивания в аппаратном обеспечении. Например, если видеокарта имеет 1,5 ГБ встроенной памяти, и вы настроили scrypt для использования 1 ГБ памяти:

128 × 16384 × 512 = 1 073 741 824 байта = 1 ГБ

то злоумышленник не мог распараллелить его на своей видеокарте. Но тогда ваше приложение/телефон/сервер должны будут использовать 1 ГБ ОЗУ каждый раз, когда они будут вычислять пароль.

Это помогает мне думать о параметрах scrypt как о прямоугольнике. Где:

ширина - это объем требуемой памяти (128 * N * r)
высота - это количество выполненных итераций.
а итоговая область - общая твердость

cost (N) увеличивает как использование памяти, так и итераций.
blockSizeFactor (r) увеличивает использование памяти.

Оставшийся параметр parallelization (p) означает, что вам нужно выполнить все 2, 3 и более раз:

Если у вас было больше памяти, чем у процессора, вы могли бы рассчитать три отдельных пути параллельно - требуя тройной памяти:

Но во всех реалиях реального мира он рассчитывается последовательно, в три раза требуя вычислений:

В действительности никто никогда не выбирал фактор p, отличный от p=1.

Каковы идеальные факторы?

Сколько оперативной памяти вы можете сохранить
столько времени, сколько вы можете сэкономить!

Бонусная карта

Графическая версия выше:

Примечания:

вертикальная ось - масштаб шкалы
Сам фактор затрат (по горизонтали) - log (iterations = 2 ^CostFactor)
Выделено в кривой r=8

И увеличенная версия выше в разумной области:

Ответ 3

Я не хочу наступать на превосходные ответы, приведенные выше, но никто не говорит о том, почему "r" имеет значение, которое оно имеет. Низкоуровневый ответ, предоставленный документом Colin Percival Scrypt, заключается в том, что он относится к "продукту с пропускной способностью для памяти". Но что это значит?

Если вы правильно используете Scrypt, у вас должен быть большой блок памяти, который в основном находится в основной памяти. От основной памяти требуется время. Когда итерация цикла блочного перехода сначала выбирает элемент из большого блока для смешивания в рабочий буфер, ему приходится ждать порядка 100 нс для первого набора данных. Затем он должен запросить другого и ждать его прибытия.

При r = 1 вы будете выполнять 4nr Salsa20/8 итерации и 2n чтения с латентностью из основной памяти.

Это не хорошо, потому что это означает, что злоумышленник может получить преимущество над вами, создав систему с уменьшенной задержкой в основной памяти.

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

Тем не менее, существует точка уменьшения возвратов с увеличением r, и это связано с упомянутым ранее "продуктом с пропускной способностью памяти". Что указывает этот продукт, так это то, сколько байтов данных может проходить транзитом из основной памяти в процессор в любой момент времени. Это та же идея, что и шоссе - если через 10 минут переходить из пункта A в точку B (латентность), и дорога доставляет 10 автомобилей в минуту до точки B от точки A (пропускная способность), проезжая часть между точками A и B содержит 100 автомобилей. Таким образом, оптимальное значение r относится к количеству 64-байтовых фрагментов данных, которые вы можете запросить сразу, чтобы скрыть задержку этого первоначального запроса.

Это улучшает скорость алгоритма, позволяя вам либо увеличить N для большей памяти и вычислений, либо увеличить p для большего количества вычислений, если это необходимо.

Есть и другие проблемы с увеличением "r" слишком много, чего я не видел много:

Увеличение r при уменьшении N уменьшает количество псевдослучайных скачков вокруг памяти. Последовательный доступ легче оптимизировать и может дать злоумышленнику окно. Как заметил Колин Персиваль в Twitter, более крупный r мог позволить злоумышленнику использовать более дешевую и медленную технологию хранения, значительно сократив затраты (https://twitter.com/cperciva/status/661373931870228480).
Размер рабочего буфера равен 1024r бит, поэтому количество возможных конечных продуктов, которые в конечном итоге будут загружены в PBKDF2 для создания выходного ключа Scrypt, составляет 2 ^ 1024r. Количество перестановок (возможных последовательностей) переходов вокруг большого блока памяти равно 2 ^ NlogN. Это означает, что существует 2 ^ NlogN возможных продуктов цикла памяти. Если 1024r > NlogN, это, по-видимому, указывает на то, что рабочий буфер находится в смешанном состоянии. Хотя я не знаю этого точно и хотел бы увидеть доказательство или опровержение, возможно, будут найдены корреляции между результатом рабочего буфера и последовательностью прыжков, что может позволить злоумышленнику уменьшить свои требования к памяти без значительного увеличения вычислительных затрат. Опять же, это наблюдение, основанное на числах - возможно, в каждом раунде все так хорошо перемешано, что это не проблема. r = 8 значительно ниже этого потенциального порога для стандартного N = 2 ^ 14 - при N = 2 ^ 14 этот порог будет r = 224.

Подводя итог всем рекомендациям:

Выберите r, чтобы быть достаточно большим, чтобы усреднить эффекты латентность памяти на вашем устройстве и не более того. Имейте в виду, что значение, рекомендованное Колином Персивалем, r = 8, похоже, остается справедливым оптимально в целом для технологии памяти, и это, по-видимому, не значительно изменилось за 8 лет; 16 может быть немного лучше.
Решите, как большой объем памяти, который вы хотите использовать в потоке, имея в виду, что это также влияет на время вычисления, и установите N соответственно.
Увеличьте p произвольно высоко до того, что ваше использование может терпеть (обратите внимание: в моей системе и используя мою собственную реализацию, p = 250 (4 потоки) с N = 16384 и r = 8 занимает ~ 5 секунд) и включить если вы имеете дело с добавленной стоимостью памяти.
При настройке предпочитайте большой размер N и размер блока памяти увеличенным p и время вычисления. Первоначальное преимущество Scrypt исходит из его больших размер блока памяти.

Тест моей собственной реализации Scrypt на Surface Pro 3 с i5-4300 (2 ядра, 4 потока) с использованием константы 128Nr = 16 МБ и p = 230; левая ось - секунды, нижняя ось - значение r, полосы ошибок - +/- 1 стандартное отклонение: