Обзор атак на приложения и протоколы, использующие алгоритм MD5, часть 6

© Сергей Панасенко, 2013

Продолжим обзор атак на различные приложения и протоколы, использующие алгоритм хэширования MD5.

В 2007 г. вышла работа [1] Жетана Лорана (Gaetan Leurent), которому удалось заметно усилить обсуждавшиеся в предыдущих частях статьи атаки Ванг и ее коллег [2] по поиску двухблочных коллизий для алгоритма MD5. Лоран отметил, что в предыдущих работах, включая работу Ванг, технология модификации сообщений применялась последовательно – от первой итерации алгоритма до тех пор, пока трудоемкость удовлетворения условий следующей итерации не превышает выгоду от этого (заключающуюся в увеличении вероятности возникновения коллизии для пары модифицируемых сообщений). Он предложил альтернативную технологию модификации сообщений: выбор стартовой итерации (в конце итераций первого раунда) и параллельное применение модификации сообщений к итерациям первого и второго раунда [1].

Данная технология может быть обобщена таким образом, что некоторые (выбранные атакующим) слова в дающих коллизию сообщениях могут иметь фиксированные (также выбранные атакующим) значения, что, в отличие от абстрактных коллизий Ванг, дает атакующему некоторый контроль над данными сообщениями. Такую коллизию уже нельзя назвать абстрактной, поскольку части сообщений выбирается атакующим, исходя из условий и цели атаки.

Выбор фиксируемых слов ограничен и приводит к незначительному увеличению трудоемкости поиска коллизий, которые по-прежнему могут вычисляться достаточно эффективно. Наиболее интересной с точки зрения практического применения Лоран посчитал возможность выбора фиксируемых слов в конце сообщений, на основе которой можно сконструировать следующие атаки:

1. При выборе фиксируемых слов в том месте дополнения к сообщению, где содержится исходный размер сообщения (см. подробное описание MD5 в [3]), можно найти дающие коллизию сообщения, размер которых составляет менее одного блока (см. рис. 1). В [1] приведена подобная коллизия для алгоритма MD4; аналогичный пример для MD5 автором не предоставлен.
2. В 2005 г. в работе [4] был предложен метод усиления хэш-функций против атак, направленных на поиск коллизий (на примере алгоритмов MD5 и SHA-1), с помощью предварительной обработки (preprocessing) хэшируемых сообщений таким образом, чтобы защитить обработанные сообщения от атак, направленных на поиск коллизий. Для хэш-функции H(m) вводится усиленная хэш-функция H*(m):

H*(m) = H(?(m)),

где ?(m) – функция, осуществляющая предварительную обработку одним из следующих способов:

• отбеливание (whitening) – внедрение в сообщение специфических (например, нулевых) блоков через определенные промежутки;
• чередование (self-interleaving) блоков – дублирование блоков сообщения.

Лоран показал, что его технология поиска коллизии эффективна даже при применении отбеливания сообщений, и привел пример коллизии для модификации алгоритма MD5 с предварительным отбеливанием сообщения.

3. Атака, позволяющая определить несколько символов пароля пользователя, использующего команду APOP для аутентификации на сервере электронной почты. Рассмотрим команду APOP и данную атаку подробнее.

Команда APOP используется для усиленной (по сравнению с простой передачей логина и пароля в открытом виде) аутентификации пользователя на сервере электронной почты в рамках протокола POP (Post Office Protocol) версии 3 [5]. Данная команда использует алгоритм MD5; при ее выполнении между почтовым сервером и клиентом передаются следующие данные (см. рис. 2):

• при получении от клиента запроса на соединение сервер передает клиенту стартовую информацию («баннер»), в которую включается следующая информация (если сервер поддерживает команду APOP):

<process-ID.clock@hostname>

где:

• process-ID – идентификатор процесса (PID) почтового сервера в десятичном виде;
• clock – метка времени сервера, также в десятичном виде;
• hostname – доменное имя сервера;

данный фрагмент баннера может выглядеть так (приведен пример из [5]):

<1896.697170952@dbc.mtview.ca.us>

• клиент выполняет команду APOP, которая имеет следующий формат:

APOP username digest

где:

• username – идентификатор пользователя на почтовом сервере (логин);
• digest – хэш-значение MD5 от следующей последовательности:

<process-ID.clock@hostname>password

т. е. перед хэшированием клиент присоединяет к полученному фрагменту баннера пароль пользователя; в результате хэшируемая последовательность может выглядеть, например, так:

<1896.697170952@dbc.mtview.ca.us>4pZl#amq

• сервер формирует аналогичную строку для хэширования (поскольку серверу известен пароль пользователя), вычисляет от нее хэш-значение MD5 и сравнивает с полученным значением параметра digest; при совпадении пользователь считается успешно прошедшим аутентификацию.

Атака Лорана на команду APOP предполагает, что злоумышленник играет роль почтового сервера и, следовательно, может выбирать значение баннера [1, 6]. Предполагается, что, если первый запрос пользователя на аутентификацию вернул неудачный результат, то пользователь попробует выполнить аутентификацию повторно. Атакующий в качестве сервера возвращает пользователю при первом и втором запросе на установление соединения такие фрагменты баннера <M1> и <M2>, которые дают двухблочную коллизию следующего вида:

MD5(<M1>x) = MD5(<M2>x),

где x – некий единичный символ; использование фиксируемых слов делает такую коллизию возможной.

Таким образом, атакующий может смонтировать атаку с выбранным открытым текстом, поскольку в качестве ответа клиента атакующий получает два хэш-значения MD5 от следующих строк:

<M1>password
<M2>password

Если первый символ пароля пользователя равен x, то получается, что полученные хэш-значения содержат двухблочную коллизию и, следовательно, они эквивалентны.

Далее в атаке предполагается, что при неудачной аутентификации пользователь совершит много подобных запросов (это является требованием и ограничением успешной атаки; оно достаточно реально, поскольку количество запросов на аутентификацию обычно ограничивается именно на стороне сервера, который является злоумышленником). Атакующий в каждой паре запросов перебирает один из возможных символов и, в результате, он рано или поздно получает пару эквивалентных значений, с помощью которой определяет первый символ пароля пользователя.

Данная атака является расширяемой и позволяет (с невысокой трудоемкостью) подобрать до трех символов пароля пользователя с помощью следующей коллизии:

MD5(<M1’>xyz) = MD5(<M2’>xyz),

где x, y и z – различные единичные символы.

Таким образом, атака Лорана на команду APOP является практически применимой с некоторыми ограничениями и позволяет существенно снизить стойкость аутентификации с помощью данной команды, поскольку знание трех символов пароля позволит многократно снизить трудоемкость дальнейшего перебора пароля. Это особенно эффективно для коротких паролей (таких, как приведенный мной в примере выше пароль «4pZl#amq», который, на первый взгляд, не выглядит слабым).

Независимо от Лорана, аналогичную атаку на APOP одновременно с Лораном представили Ю Сасаки (Yu Sasaki) и его коллеги в работе [7]. Данная атака была найдена еще в конце 2006 г., однако, задержка в публикации результатов работы произошла из-за японского законодательства, согласно которому до публикации подобных атак необходимо ставить в известность Агентство по информационным технологиям Японии (Information-technology Promotion Agency – IPA) [8].

В 2008 г. в работе [9] другой коллектив японских специалистов (также с участием Ю Сасаки) существенно усилил данную атаку путем применения предложенных еще в 1993 г. в работе ден Боера и Босселаерса [10] псевдо-коллизий функции сжатия алгоритма MD5. Криптоаналитики ввели новую технологию, названную ими «IV Bridge» (см. рис. 3): получение из стандартного вектора инициализации (эквивалентного для двух сообщений) после обработки первой пары блоков такой разности между текущими значениями переменных A…D двух сообщений, которая позволила бы применить псевдо-коллизию ден Боера и Босселаерса (данный вид псевдо-коллизии был подробно описан в [11]).

Технология «IV Bridge» позволила атакующим добиться несравнимо большего контроля над фрагментами сообщений, дающими коллизию, и, в результате, достичь следующих возможностей по поиску паролей пользователей, применяемых в команде APOP [9]:

• атака позволяет раскрыть до 11 символов пароля пользователя менее, чем за секунду;
• до 51 символа пароля могут быть получены с помощью расширенной атаки, трудоемкость которой (до 2⁴³ операций) позволяет применить атаку на практике;
• теоретически, данная атака позволяет определить до 61 символа пароля.

Поскольку можно утверждать, что подавляющее большинство паролей пользователей, применяемых для доступа к электронным почтовым ящикам, вряд ли длиннее 11 символов, с выходом работы [9] команду APOP можно считать полностью взломанной даже с учетом описанных выше ограничений атаки на данную команду (не говоря уже о расширении атаки Сасаки и его коллег до 51 вскрываемого символа пароля).

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

Литература

1. Leurent G. Message Freedom in MD4 and MD5 Collisions: Application to APOP. // http://citeseerx.ist.psu.edu – Ecole Normale Superieure, Paris, France.
2. Wang X., Feng D., Lai X., Yu H. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. // http://eprint.iacr.org – Revised on August 17, 2004.
3. Панасенко С. Алгоритм хэширования MD5. // Sec.ru. – 13.08.2012 г.
4. Szydlo M., Yin Y. L. Collision-Resistant usage of MD5 and SHA-1 via Message Preprocessing. // http://citeseerx.ist.psu.edu.
5. Myers J., Rose M. RFC 1939. Post Office Protocol – Version 3. // http://tools.ietf.org – May 1996.
6. Leurent G. Message Freedom in MD4 and MD5 Collisions. Application to APOP. // http://fse2007.uni.lu – Ecole Normale Superieure, Paris, France – Fast Software Encryption 2007 Presentation.
7. Sasaki Y., Yamamoto G., Aoki K. Practical Password Recovery on an MD5 Challenge and Response. // http://siteseerx.ist.psu.edu.
8. Sasaki Y., Yamamoto G., Aoki K. Practical Password Recovery on an MD5 Challenge/Response such as APOP. // http://fse2007.uni.lu – Fast Software Encryption 2007 Presentation.
9. Sasaki Y., Wang L., Ohta K., Kunihiro N. Security of MD5 Challenge and Response: Extension of APOP Password Recovery Attack. // http://link.springer.com – 2008.
10. Den Boer B., Bosselaers A. Collisions for the compression function of MD5. // http://citeseerx.ist.psu.edu – 23 July 1993.
11. Панасенко С. Обзор атак на алгоритм хэширования MD5: поиск коллизий, часть 1. // Sec.ru. – 09.11.2012 г.

Рисунки:

1. Коллизия для коротких сообщений.
2. Обмен данными при выполнении команды APOP.
3. Технология «IV Bridge».

Предыдущая часть статьи

Следующая часть статьи