208
ленник опрашивает H(>||r) с только лишь пренебрежимо малой вероятностью
(так как r является универсальной n-битной строкой); если он ни разу не сделает
запрос этой формы, тогда H(m»r) ничего не откроет о m. Привязка проистекает
из факта, что H является стойкой к коллизиям.
Схемы обязательств могут быть сконструированы без случайных оракулов
(фактически, из однонаправленной функции), но
подробности находятся за
пределами данной книги.
Ссылки и дополнительная литература
Стойкие к коллизиям хэш-функции были формально
определены Дамгордом
[52]. Дополнительное описание касательно понятий о
безопасности для хэш-
функций помимо стойкости к коллизиям можно найти в [120, 150]. П реобразова-
ние Меркле-Дамгорда было представлено отдельно Дамгордом и Меркле [53, 123]
HMAC был представлен Белларом и др. [14], а позже и стандартизирован
[131]. Атаки «дней рождения» малого пространства, описанные в Разделе 5.4.2,
опираются на
алгоритм нахождения цикла Флойда (Floyd).
Соответстующие алгоритмы
описаны по сслыке: http://en.wikipedia.org/wiki/Cycle_detection.
Идея нахожде-
ния значимых коллизий с использований атак малого пространства по Ювалю
(Yuval) [180]. Ключ
параллелизации атак нахождения коллизий, которые могут предложить зна-
чительные ускорения на практике, описана в [170]. Компромиссы простран-
ства/времени для функции инверсии были представлены Хеллманом (Helman)
[87] с практическими улучшениями, не описанными здесь, предоставленными
Ривестом (Risvest) (неопубликовано) и Oechslin [134].
Первая формальная трактовка модели со случайным оракулом была дана Бел-
ларом и Рогавэем [21], хотя идея использования «произвольно ищущей» функ-
ции в криптографических приложениях была предложена ранее в значительной
степени Фиатом (Fiat) и Шамиром (Shamir) [65]. Правильная реализация слу-
чайного оракула на основе конкретной криптографической хэш-функции опи-
сана в [21, 22, 23, 48]. Фундаментальный негативный результат касательно мо-
дели со случайным оракулом принадлежит Канетти (Canetti) и др. [41], который
показал (изобрел) схемы, которые защищены в модели со случайным оракулом,
но незащищены для любых конкретных реализаций случайного оракула.
Деревья Меркле были представлены в [121]. Установление ключа, использу-
емое на практике, включая HKDF, PBKDF2 и bcrypt. См. [109] для формальной
трактовки проблемы и анализа HKDF.