Разделяй и властвуй: гарантированный взлом MS-CHAPv2

Автор: Moxie Marlinspike

Мы полагаем, что MS-CHAPv2 остается таким распространенным, поскольку предыдущие исследователи потенциальных слабостей протокола главным образом фокусировались на атаках по словарю. Если сложить эту ограниченность исследований с крайне широким количеством клиентов, поддерживающих протокол, и его совместимостью с ОС, станет понятно, почему это решение, требующее наименьшего количества телодвижений от пользователя, столь заманчиво.

В своем анализе данного протокола (1999 год), например, Брюс Шнайер и Мадж заключили следующее: "Microsoft улучшил PPTP, исправив основные изъяны безопасности, описанные в [SM98]. Однако, фундаментальная слабость аутентификации и шифрования протокола в том, что он безопасен настолько, насколько безопасен выбранный пользователем пароль. " [курсив добавлен]. Эта и другие работы привели к тому, что провайдеры и пользователи решили, что они могут использовать MS-CHAPv2 в PPTP VPN и взаимно аутентифицироваться с серверами WPA2 Enterprise, если будут выбирать хорошие пароли.

Например, на основе данного в работе Шнайера анализа Riseup.net, сконцентрированный на безопасности провайдер VPN, решил пойти на генерацию для своих пользователей равномерно случайных 21-символьных паролей, не давая им возможности выбирать свои собственные пароли, чтобы гарантировать безопасность развертывания PPTP VPN-сервиса.

Протокол

Давайте взглянем на сам протокол, чтобы увидеть, с чем мы имеем дело:

 

На первый взгляд может показаться, что протокол излишне сложен. Он похож на цифровой эквивалент пустого размахивания руками – как будто добавление лишнего хэша, случайного числа или необычное строение дайджеста как-то повлияют на предполагаемых противников. Строковые константы "Pad to make it do more than one iteration" и "Magic server to client signing constant" выглядят особенно занятно.

При аккуратном рассмотрении, однако, оказывается, что во всем протоколе действительно неизвестным является лишь MD4-хэш пароля пользователя, который используется для построения трех отдельных ключей DES. Все прочие элементы протокола либо сами посылаются явным образом, либо могут быть получены из того, что посылается явно:

Так как все остальное известно, мы можем попробовать игнорировать все, кроме неизвестного ядра, и посмотреть, какие возможности это нам дает:

У нас есть неизвестный пароль, неизвестный MD4-хэш этого пароля, известный открытый текст и известный шифртекст. Присмотревшись, можно видеть, что MD4-хэш пользовательского пароля служит эквивалентом пароля, то есть, MD4-хэша пароля пользователя достаточно для аутентификации от имени этого пользователя, равно как и расшифровки любого его трафика. Итак, нашей целью является восстановление MD4-хэша пользовательского пароля.

Обычно, располагая перехваченным трафиком, атакующий попытается провести атаку по словарю. Используя инструмент вроде asleap, возможно быстро перебрать ряд паролей в оффлайн-режиме. Для каждого пароля из словаря, password_guess, атакующий может просто вычислить MD4(password_guess), разделить полученный хэш на три DES-ключа, зашифровать известный открытый текст три раза и посмотреть, совпадает ли сконкатенированный результат DES-шифрований с известным шифртекстом.

Проблема с данным подходом в том, что он не даст атакующему 100% гарантию успеха, а также зависит от склонности пользователя выбирать предсказуемые пароли. В случае PPTP VPN-сервиса riseup.net, например, атакующему пришлось бы перебирать все 96 вариантов символа для каждого из 21 символов сгенерированного пароля. Общая сложность такого перебора равна 96²¹, что немногим больше 2¹³⁸, то есть сравнима со сложностью подбора 138-битного ключа.

В ситуации с неограниченной длиной пароля, составленного из широкого набора символов, имеет смысл напрямую подбирать результат MD4-хэширования. Тем не менее, длина MD4-хэша равна 128 бит. Это делает размер пространства ключей, подлежащих перебору, равным 2¹²⁸, что вряд ли когда-либо станет вычислительно достижимым.

Разделяй и властвуй

Преследуемый нами хэш, однако, используется как ключевой материал для трех DES-операций. DES-ключи имеют длину 7 байт, так что каждая DES-операция использует 7-байтовый фрагмент MD4-хэша. Это дает нам возможность для классической атаки "разделяй и властвуй".

Поскольку имеют место три DES-операции, и каждая DES-операция полностью независима от остальных, это дает нам аддитивную сложность всего пространства ключей, равную 2⁵⁶ + 2⁵⁶ + 2⁵⁶ = 2^57.59.

Это безусловно лучше, чем 2¹³⁸ или 2¹²⁸, но все еще довольно большое число. Однако, наши вычисления не совсем верны. Нам нужно три DES-ключа, каждый 7 байтов длиной, а всего 21 байт:

Данные ключи извлекаются из значения MD4(password), которое имеет длину лишь 16 байт.

Нам недостает пяти байтов ключевого материала для третьего DES-ключа. Решение Microsoft состоит в дополнении пяти последних байт нулями, что делает эффективную длину третьего DES-ключа равной двум байтам.

Поскольку третий DES-ключ имеет эффективную длину всего два байта, т. е. принадлежит пространству ключей размером всего 2¹⁶, мы можем немедленно увидеть эффективность подхода "разделяй и властвуй", подобрав третий ключ за секунды. Это даст нам два последних байта MD4-хэша. Нам осталось найти 14 оставшихся байтов хэша, но мы можем разделить их на два 7-байтовых фрагмента, что дает общую сложность 2⁵⁷.

Опять же большое число, но значительно лучше. По существу, нам осталось решить такую ключевую задачу:

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

Здесь мы пробегаем каждый ключ в пространстве ключей, используем его для шифрования нашего известного открытого текста и сравниваем результат с нашим первым известным шифртекстом. Когда будет найдено соответствие, мы начнем сначала и пробежим каждый ключ, шифруя известный открытый текст и сравнивая результат с нашим вторым известным шифртекстом.

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

Таким образом, мы уменьшим общую сложность до 2⁵⁶!

Это означает, что безопасность MS-CHAPv2 может быть сведена к стойкости одного DES-шифрования.

Взлом DES

Теперь остается открытым лишь вопрос вычислительной достижимости. В 1998 году EFF использовала ASIC чтобы построить Deep Crack, который стоил $250,000 и взламывал ключ в среднем за 4.5 дня.

Компания Дэвида Халтона, Pico Computing, специализируется на построении FPGA оборудования для криптографических приложений. Они смогли построить FPGA-устройство, DES cracking box, которое реализовывало DES как конвейер с одной DES-операцией на каждый тактовый цикл. Обладая 40 ядрами по 450 МГц оно позволяет перебирать 18 миллиардов ключей в секунду. Используя 48 FPGA, DES cracking box в худшем случае взламывает ключ DES за 23 часа, а в среднем за полдня.

Теперь, вооружившись данным оборудованием Pico Computing, мы можем взломать любое рукопожатие по протоколу MS-CHAPv2 меньше, чем за день.

Если бы взломать рукопожатия MS-CHAPv2 могли только я или Дэвид, это было бы не так весело. Поэтому, мы интегрировали DES cracking box с CloudCracker, чтобы сделать доступными для каждого талант, навыки и ресурсы Дэвида и его команды.

Мы опубликовали утилиту, названную chapcrack, которая разбирает перехваченный сетевой трафик в поисках рукопожатий MS-CHAPv2. Для каждого рукопожатия она выводит имя пользователя, известный открытый текст, два известных шифртекста и взламывает третий DES-ключ. Она также выводит "токен" CloudCracker, в котором закодированы три параметра, обходимые для нашей атаки "разделяй и властвуй".

Когда токен отправляется в CloudCracker, закодированная в нем задача передается DES cracking box, и вы получаете результаты менее чем через день.

Что вы выигрываете?

Теперь вы можете поместить взломанный CloudCracker MD4-хэш обратно в chapcrack, и она расшифрует весь захваченный сетевой трафик (и все последующие перехваты трафика данного пользователя). Вы также можете использовать данный хэш для входа в VPN-сервис пользователя или на RADIUS-сервер WPA2 Enterprise.

Мы надеемся, что, сделав данный сервис доступным, мы сможем эффективно прекратить использование MS-CHAPv2 в Интернет раз и навсегда. И, как обычно, передача задач по взлому MS-CHAPv2 на CloudCracker доступна через стандартный веб-интерфейс и через API.

Что теперь?

1) Все пользователи и провайдеры PPTP VPN-решений должны немедленно начать миграцию на другой VPN-протокол. PPTP-трафик следует считать незашифрованным.

2) Компании, которые зависят от свойств взаимной аутентификации MS-CHAPv2 для соединения со своими WPA2 RADIUS-серверами, должны немедленно начать миграцию на альтернативное решение.

Во многих случаях большие компании выбрали использование IPSEC-PSK поверх PPTP. В то время как PPTP теперь очевидно взломан, IPSEC-PSK, вероятно, еще более уязвим к вектору атаки по словарю, чем когда-либо был PPTP. PPTP по крайней мере требует от атакующего перехвата активного сетевого трафика, чтобы начать оффлайновую атаку по словарю, тогда как IPSEC-PSK VPN в агрессивном режиме, по существу, выдает хэши любому подключившемуся атакующему.

Учитывая доступные сегодня решения, безопасное развертывание чего-либо нуждается в некоторой проверке сертификатов. Это касается либо конфигурации OpenVPN, либо использования IPSEC в режиме сертификатов вместо PSK.

Благодарности

Большое спасибо Marsh Ray за поддержку и участие в данной работе.