Функция жесткой памяти
В криптографии функция с жесткой памятью ( MHF ) — это функция, которой требуется значительный объем памяти . для эффективной оценки [1] Она отличается от функции, привязанной к памяти , которая требует затрат из-за замедления вычислений из-за задержки памяти. [2] MHF нашли применение в расширении ключей и проверке работы , поскольку их повышенные требования к памяти значительно снижают преимущество в вычислительной эффективности специального оборудования по сравнению с оборудованием общего назначения по сравнению с не-MHF. [3] [1]
Введение
[ редактировать ]MHF предназначены для потребления больших объемов памяти компьютера с целью снижения эффективности параллельных вычислений . Чтобы вычислить функцию, используя меньше памяти, требуется значительное время. Поскольку каждое вычисление MHF требует большого объема памяти, количество вычислений функций, которые могут выполняться одновременно, ограничено объемом доступной памяти. Это снижает эффективность специализированного оборудования, такого как специализированные интегральные схемы и графические процессоры , которые используют распараллеливание при вычислении MHF для большого количества входных данных, например, при подборе хэшей паролей или майнинге криптовалюты . [1] [4]
Мотивация и примеры
[ редактировать ]SHA Доказательство работы Биткойна использует повторную оценку функции -256 , но современные процессоры общего назначения, такие как готовые процессоры , неэффективны при многократном вычислении фиксированной функции. Специализированное оборудование, такое как специализированные интегральные схемы (ASIC), предназначенные для майнинга биткойнов, может использовать в 30 000 раз меньше энергии на хэш, чем процессоры x86, имея при этом гораздо более высокие скорости хеширования. [4] Это привело к опасениям по поводу централизации майнинга биткойнов и других криптовалют. [4] Из-за этого неравенства между майнерами, использующими ASIC, и майнерами, использующими процессоры или готовое оборудование, разработчики более поздних систем доказательства работы использовали хэш-функции, для которых было трудно создать ASIC, которые могли бы оценить хеш-функцию значительно быстрее, чем процессор. . [3]
Поскольку стоимость памяти не зависит от платформы, [1] MHF нашли применение в майнинге криптовалют, например, Litecoin , который использует scrypt в качестве хэш-функции. [3] Они также полезны при хешировании паролей, поскольку значительно увеличивают стоимость проверки множества возможных паролей в утекшей базе данных хешированных паролей без значительного увеличения времени вычислений для законных пользователей. [1]
Измерение жесткости памяти
[ редактировать ]Существуют различные способы измерения жесткости памяти функции. Одной из часто встречающихся мер является совокупная сложность памяти (CMC). В параллельной модели CMC — это сумма памяти, необходимой для вычисления функции на каждом временном шаге вычисления. [5] [6]
Другие жизнеспособные меры включают интеграцию использования памяти со временем и измерение потребления полосы пропускания памяти на шине памяти. Функции, требующие высокой пропускной способности памяти, иногда называют «функциями с жесткой пропускной способностью». [7]
Варианты
[ редактировать ]MHF можно разделить на две разные группы в зависимости от моделей их оценки: зависящие от данных функции жесткой памяти (dMHF) и независимые от данных функции жесткой памяти (iMHF). В отличие от iMHF, шаблон доступа к памяти dMHF зависит от входных данных функции, например пароля, предоставленного функции получения ключа. [8] Примерами dMHF являются scrypt и Argon2d , а примерами iMHF — Argon2i и catena . Многие из этих MHF были разработаны для использования в качестве функций хеширования паролей из-за жесткости их памяти.
Заметная проблема с dMHF заключается в том, что они подвержены атакам по побочным каналам, таким как синхронизация кэша. Это привело к предпочтению использования iMHF при хешировании паролей. Однако математически доказано, что iMHF обладают более слабыми свойствами стойкости памяти, чем dMHF. [9]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д и Чен, Биньи (2019). Функции, связанные с памятью: когда теория встречается с практикой (тезис). Калифорнийский университет в Санта-Барбаре.
- ^ Дворк, Синтия; Гольдберг, Эндрю; Наор, Мони (2003). Боне, Дэн (ред.). «О функциях, связанных с памятью, для борьбы со спамом» . Достижения криптологии — КРИПТО 2003 . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer: 426–444. дои : 10.1007/978-3-540-45146-4_25 . ISBN 978-3-540-45146-4 .
- ^ Перейти обратно: а б с ЛЮ, АЛЕК (29 ноября 2013 г.). «За пределами Биткойна: Путеводитель по наиболее перспективным криптовалютам» . Порок . Проверено 30 сентября 2023 г.
- ^ Перейти обратно: а б с Бирюков, Алекс; Ховратович, Дмитрий (2015). Ивата, Тецу; Чхон, Чон Хи (ред.). «Компромиссный криптоанализ функций с жесткой памятью» . Достижения в криптологии – ASIACRYPT 2015 . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer: 633–657. дои : 10.1007/978-3-662-48800-3_26 . ISBN 978-3-662-48800-3 .
- ^ (AS15) Алвен, Сербинеко, Графы высокой параллельной сложности и функции, требовательные к памяти , 2015
- ^ Алвен, Джоэл; Блоки, Иеремия; Петшак, Кшиштоф (7 июля 2017 г.). «Устойчивая космическая сложность». arXiv : 1705.05313 [ cs.CR ].
- ^ Блоки, Иеремия; Лю, Пэйюань; Рен, Линг; Чжоу, Самсон (2022). «Функции, связанные с пропускной способностью: сокращения и нижние границы» (PDF) . Архив электронной печати по криптологии . Архивировано (PDF) из оригинала 12 января 2023 г. Проверено 11 января 2023 г.
- ^ Блоки, Иеремия; Харша, Бен; Канг, Ситенг; Ли, Сынхун; Син, Лу; Чжоу, Самсон (2019). Болдырева Александра; Миччанчо, Даниэле (ред.). «Независимые от данных жесткие функции памяти: новые атаки и более сильные конструкции» . Достижения криптологии – CRYPTO 2019 . Конспекты лекций по информатике. Чам: Springer International Publishing: 573–607. дои : 10.1007/978-3-030-26951-7_20 . ISBN 978-3-030-26951-7 .
- ^ Алвен, Дж., Блоки, Дж. (2016). Эффективное вычисление независимых от данных функций памяти.