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

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

На двадцатой конференции Defcon мы с Дэвидом Халтоном представили презентацию о взломе MS-CHAPv2. В данном посте дан примерный обзор того, что мы охватили в своем выступлении.

Автор: Moxie Marlinspike

На двадцатой конференции Defcon мы с Дэвидом Халтоном представили презентацию о взломе MS-CHAPv2. В данном посте дан примерный обзор того, что мы охватили в своем выступлении.

Почему MS-CHAPv2?

Первый очевидный вопрос – почему мы занялись MS-CHAPv2, учитывая давнее ощущение, что Интернет не стоит полагаться на этот протокол. К сожалению, даже будучи устаревшим протоколом и объектом распространенной критики, он продолжает использоваться повсеместно. Наиболее примечательно использование MS-CHAPv2 в PPTP VPN. Он также довольно интенсивно используется в конфигурациях WPA2 Enterprise, особенно в тех случаях, когда полагаются на его свойства взаимной аутентификации. Для своего выступления мы составили список из сотен VPN-провайдеров, которые зависят от PPTP. Он включает такие значимые примеры, как iPredator, VPN-сервис The Pirate Bay, который предположительно разработан для защиты информационного обмена от наблюдения со стороны государства.


Мы полагаем, что 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 символов сгенерированного пароля. Общая сложность такого перебора равна 9621, что немногим больше 2138, то есть сравнима со сложностью подбора 138-битного ключа.

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

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

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

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

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

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

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

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

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

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

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

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

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

Это означает, что безопасность 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 за поддержку и участие в данной работе.

Ваша приватность умирает красиво, но мы можем спасти её.

Присоединяйтесь к нам!