2. Оценка производительности
Наиболее свежим исследованием производительности MD5, найденным автором этого документа, была работа J. Touch из ISI. Результаты этого исследования были опубликованы в [RFC1810]. На момент проведения этого исследования наилучшая программная реализация MD5 обеспечивала производительность 87 Мбит/с. Предполагается, что к этой оценке применим закон Мура. Экстраполяция этого значения на время подготовки данного документа (2002 год) дает значение около 2,1 Гбит/с.
Для упрощения мы будем предполагать, что при попытках подбора ключа атакующий будет использовать только короткие пакеты. Возможным типом таких пакетов будут отклики ACK, не содержащие данных. Это ведет к необходимости расчета MD5 примерно для 40 байтов данных вместе с некоторым разумным максимальным числом байтов ключа. MD5 дополняет входные данные для выравнивания по границе 512 битов (64 байта). Это означает, что минимальный «блок» MD5 имеет размер 64 байта и с учетом экстраполированной для 2002 г. производительности 2,1 Гбит/с мы получим для 1-процессороной системы производительность MD5 около 4.1*e6 одноблоковых операций MD5 в секунду.
Эти значения основаны на предположении, что занимающийся подбором ключей, ограничен ресурсами одного процессора. На практике распределенные криптографические атаки с подбором ключей в недавнем прошлом достаточно часто завершались успехом.
Может оказаться поучительным анализ недавних эпидемий «червей» в Internet в целях определения максимального числа хостов, которые могут быть тайком вовлечены в организацию атаки MD5 путем подбора ключей. В отчете CAIDA [CAIDA2001] указывается, что червь Code Red смог заразить более 350 000 хостов Internet за первые 14 часов своей деятельности. Представляется разумным предположение, что червь, содержащий незаметный механизм для участия в атаке с подбором ключей (возможно использующий периоды бездействия CPU на зараженном хосте) будет по крайней мере столь же эффективным, как Code Red. Если предположить, что такой червь будет максимально скрытным, в установившемся состоянии размер его популляции может достигнуть миллиона хостов или более того. Это позволит увеличить производительность операций подбора (на однопроцессорной системе около 4.1*e6 операций в секунду) до 1.0e11 — 1.0e13 операций MD5 в секунду.
В 1997 г. John Gilmore и Electronic Frontier Foundation [EFF98] разработали машину специального назначения для проведения исследований стоимостью приблизительно $250000. Эта машина была способна организовать атаку с подбором ключей против алгоритма DES и рассчитывала один ключ в неделю. На основе закона Мура можно предположить, что за те же деньги сегодня можно создать машину, способную работать примерно в 8 раз быстрее. Разумно предположить, что подобное оборудование может использоваться для подбора ключей MD5 и при таком же размере ключей, как в DES, оно будет незначительно уступать в производительности (производительность аппаратной реализации MD5 в 2-3 раза уступает производительности DES).