Задний план. Все известные мне алгоритмы MKDF (KDF с жестким использованием памяти) (Scrypt, Argon2, Balloon) на самом деле не требуют всей памяти в каждый момент времени выполнения алгоритма, а вместо этого требуют значительного вычислительного штрафа, когда используется меньше памяти. .
В общих чертах график зависимости использования памяти от времени выглядит так (конечно, лучшие MKDF будут иметь больше смежных пиков):
(Изображение из там)
Я думаю, что это ограничение (отсутствие потребности в памяти в каждый момент) связано с тем, как работают компьютеры общего назначения (например, ЦП, ОЗУ).
Вопрос. Если мы ослабим предположение об оборудовании (например, разрешим специализированное оборудование), можем ли мы определить алгоритм MKDF, который требует всей своей памяти в каждый момент времени? Например. Можем ли мы сделать так, чтобы на графике была прямая линия?
Мои мысли до сих пор. Представьте, что у нас есть механическая плоскость памяти, где состояние каждого бита памяти связано с состоянием каждого другого бита, так что если мы изменим значение одного бита, это вызовет изменение всех остальных битов во всей памяти.
С этой плоскостью механической памяти мы выполняем единственную инструкцию, которая переворачивает 1 бит, и эта единственная операция механически переворачивает состояние всех остальных битов.
Если отношения между битами непредсказуемы (например, подобно тому, как небольшое изменение в значении блока открытого текста приводит к полному изменению зашифрованного текста), то я предполагаю, что эта механическая память стала MKDF, которая может работать следующим образом:
- Пользователь инициализирует память, заполняя ее случайными битами, которые генерируются из некоторого начального числа. Это делается только один раз.
- Пользователь кодирует свой пароль в старших битах механической плоскости памяти. Очевидно, это делается каждый раз, когда пользователь хочет получить более безопасный ключ из своего пароля.
- Поскольку пользователь кодирует свой пароль в первых битах этого листа механической памяти, состояния всех битов в листе механической памяти будут меняться непредсказуемым образом.
- Наконец, когда пользователь заканчивает кодировать свой пароль, он просто выбирает младшие значащие биты этой плоскости механической памяти в качестве производного ключа.
Если злоумышленник попытается сделать это с меньшей плоскостью механической памяти (с меньшим количеством битов памяти), то полученный им ключ будет полностью случайным.
Если мои догадки верны и реализация такого оборудования возможна, то:
- Это платформа для аппаратных алгоритмов MKDF, всегда требуют одинакового объема памяти, при каждый момент времени во время выполнения функции вывода ключа.
- Пользователь покупает одну механическую плоскость памяти для своих логинов, поэтому пользователь может себе это позволить, поскольку это разовая покупка. Но противнику придется купить много этих листов, чтобы делать их параллельно. Так что я предполагаю, что это масштабируемо для пользователя, но не масштабируемо для противника.
я предполагать мы можем реализовать эту механическую плоскость памяти, используя:
- Запутанные кванты, вероятно, более естественный способ думать об этом.
- Большая механическая доска с большим количеством смазки, чтобы шестерни не застревали.
- Электроника для меньшей и менее жирной альтернативы.
