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

chap-4

MD4-хеш пароля используется в качестве входных данных для трех DES-операций. DES-ключи имеют длину 7 байт, так что каждая DES-операция использует 7-байтовый фрагмент MD4-xeшa. Все это оставляет возможность для классической атаки divide and conquer. Вместо того чтобы полностью брутить MD4-хеш (а это, как ты помнишь, 24128 вариантов), мы можем подбирать его по частям в 7 байт. Так как используются три DES-операции и каждая DES-операция абсолютно независима от других, это дает общую сложность подбора, равную 2456 + 2456 + 2456, или 2457.59. Это уже значительно лучше, чем 24138 и 24128, но все еще слишком большое число вариантов. Хотя, как ты мог заметить, в эти вычисления закралась ошибка. В алгоритме используются три DES-ключа, каждый размером в 7 байт, то есть всего 21 байт. Эти ключи берутся из MD4-хеша пароля, длина которого всего 16 байт.
То есть не хватает 5 байт для построения третьего DES-ключа. В Microsoft решили эту задачу просто, тупо заполнив недостающие байты нулями и фактически сведя эффективность третьего ключа к двум байтам.
Так как третий ключ имеет эффективную длину всего лишь два байта, то есть 2416 вариантов, его подбор занимает считаные секунды, доказывая эффективность атаки divide and conquer. Итак, можно считать, что последние два байта хеша известны, остается подобрать оставшиеся Н. Также разделив их на две части по 7 байт, имеем общее число вариантов для перебора, равное 2456 + 2456 = 2457. Все еще слишком много, но уже значительно лучше. Можно решить задачу перебора «в лоб»: организовать два цикла, в первом перебирать ключи для первого шифртекста, во втором — для второго. Но если обратить внимание на то, что оставшиеся DES-операции шифруют один и тот же текст, только при помощи разных ключей, то логичней будет организовать один цикл, внутри которого проверять оба ключа. То есть получается 2456 вариантов ключей для перебора. А это значит, что безопасность MS-CHAPv2 может быть сведена к стойкости одного DES-шифрования.
ВЗЛОМ DES
Теперь, когда диапазон подбора ключа известен, для успешного завершения атаки дело остается только за вычислительными мощностями. В 1998 году Electronic Frontier Foundation построила машину Deep Crack, которая стоила 250 тысяч долларов и позволяла взламывать DES-ключ в среднем за четыре с половиной дня. В настоящее время Pico Computing, специализирующаяся на построении FPGA-оборудования для криптографических приложений, построила FPGA-устройство (DES cracking box), которое реализует DES как конвейер с одной DES-операцией на каждый тактовый цикл. Обладая 40 ядрами по 450 МГц, оно позволяет перебирать 18 миллиардов ключей в секунду. Обладая такой скоростью перебора, DES cracking box в худшем случае взламывает ключ DES за 23 часа, а в среднем за полдня. Данная чудо-машина доступна через коммерческий веб-сервис cloudcracker.com. Так что теперь можно взломать любой MS-CHAPv2 handshake меньше, чем за день. А имея хеш пароля, можно аутентифицироваться от имени пользователя на VPN-сервисе или просто расшифровывать его трафик.
Для автоматизации работы с сервисом и обработки перехваченного трафика Мокси выложил в открытый доступ утилиту chapcrack. Она парсит перехваченный сетевой трафик, ища MS-CHAPv2 handshake’n. Для каждого найденного «рукопожатия» она выводит имя пользователя, известный открытый текст, два известных шифртекста и взламывает третий DES-ключ. Кроме этого, она генерирует токен для CloudCracker, в котором закодированы три параметра, необходимые, чтобы сервис взломал оставшиеся ключи.