Насколько сложно взломать второй фактор MFA?

Я часто участвую в рабочих созвонах, на которых один и тот же менеджер демонстрирует свой экран. При этом ему нередко приходится входить в один и тот же корпоративный сервис.

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

В такие моменты я делаю глоток кофе и неизменно задаюсь вопросом: «Насколько безопасно показывать эти шесть цифр всем участникам встречи? Что, если записывать коды и точное время их использования, а потом попытаться восстановить секретный ключ?»

Чтобы упростить задачу, пока оставим логин и пароль за скобками: предположим, что они нам уже известны. Нас интересует только второй фактор аутентификации — TOTP.

Интуитивно ясно, что восстановление секретного ключа по последовательности одноразовых кодов потребует огромных ресурсов. Но насколько огромных? Попробуем оценить порядок величин.

Немного теории

TOTP (Time-based One-Time Password) — алгоритм формирования одноразовых паролей, описанный в RFC 6238.

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

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

Исходный секретный ключ обычно имеет длину 160 бит, или 20 байт. Для удобства его часто записывают в кодировке Base32: получается строка из 32 символов, состоящая из заглавных латинских букв A–Z и цифр 2–7. Например:

GEZDGNBVGY3TQOJQGEZDGNBVGY3TQOJQ

Коды, создаваемые на основе ключа, содержат шесть цифр и зависят от текущего времени. Обычно они меняются каждые 30 секунд, тогда как сам ключ остаётся скрытым.

Иными словами, функция использует исходные 20 байт и текущее время, чтобы каждые 30 секунд выдавать новый шестизначный код. Он выглядит случайным, но при одном и том же ключе и времени результат всегда будет одинаковым.

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

Сколько нужно наблюдений?

Вернёмся к менеджеру и представим, что мы начали записывать увиденные шестизначные коды вместе с точным временем их ввода. Постепенно у нас появляется таблица: какой код и когда использовался.

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

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

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

Звучит обнадёживающе. При такой скорости сокращения потребуется сравнительно немного наблюдений, чтобы с высокой вероятностью остался единственный подходящий ключ: как мы увидим, достаточно примерно девяти.

В чём же подвох?

Цена первой итерации

Подвох заключается в длине секретного ключа.

Напомним: его длина составляет 160 бит. Каждый бит может иметь одно из двух значений — 0 или 1. Значит, общее число возможных ключей равно:

2¹⁶⁰

Два в сто шестидесятой степени. В десятичной записи это число из 49 цифр:

1,46 × 10⁴⁸

Чтобы провести первую итерацию и отобрать ключи, создающие нужный шестизначный код, придётся проверить каждый вариант.

Допустим, у нас есть невероятно мощный суперкомпьютер, который проверяет триллион ключей в секунду. Сколько времени ему понадобится, чтобы перебрать все возможные варианты?

Разделим число ключей на производительность машины и получим время в секундах:

1,46 × 10⁴⁸ / 10¹² = 1,46 × 10³⁶

Переведём результат в годы:

4,63 × 10²⁸

Это 46,3 октиллиона лет по русской системе наименования больших чисел.

Для сравнения: возраст Вселенной оценивается примерно в 13,8 миллиарда лет. Выходит, одна только первая итерация займёт у нашего суперкомпьютера примерно в 3,4 квинтиллиона раз больше времени, чем существует Вселенная.

И это лишь первая из девяти итераций. Последующие обойдутся значительно дешевле, но до них ещё нужно добраться.

Кажется, возникли небольшие технические трудности.

Параллельные вычисления

Хорошо, одному суперкомпьютеру задача не по силам. Но выполнять все вычисления на единственной машине необязательно. Что, если распределить перебор между множеством суперкомпьютеров, поручив каждому свою часть ключей?

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

Тогда первая итерация завершится в миллион раз быстрее и займёт примерно:

4,63 × 10²² лет

Это по-прежнему более чем в три триллиона раз превышает возраст Вселенной.

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

Похоже, дело не в нехватке компьютеров. Просто возможных ключей слишком много.

Последняя надежда

С обычными компьютерами всё более или менее ясно. Обратимся к технологиям будущего — например, к квантовым вычислениям.

Существует алгоритм Гровера, который позволяет квантовому компьютеру искать среди множества вариантов значительно быстрее, чем при обычном переборе. И дело не просто в большей производительности: число необходимых проверок сокращается примерно с 2¹⁶⁰ до 2⁸⁰.

Звучит неплохо. Вместо числа из 49 цифр нам понадобится выполнить:

2⁸⁰ ≈ 1,21 × 10²⁴ операций

Это около 1,2 септиллиона квантовых итераций.

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

Сколько времени потребуется, чтобы восстановить секретный ключ?

Разделим число квантовых итераций на производительность компьютера:

1,21 × 10²⁴ / 10¹² = 1,21 × 10¹² секунд

Переведём секунды в годы:

1,21 × 10¹² / 31 536 000 ≈ 38 400 лет

Примерно 38 тысяч лет. И это при условии, что каждая квантовая итерация, включающая вычисление и проверку TOTP, занимает одну триллионную долю секунды.

За пределами разумного

Похоже, мы исчерпали возможности современных и даже гипотетических вычислительных технологий. Остаётся обратиться к научной фантастике.

В «Автостопом по галактике» Дугласа Адамса упоминается суперкомпьютер Milliard Gargantubrain, способный пересчитать все атомы звезды за миллисекунду.

Попробуем привлечь его к решению нашей задачи.

По приблизительным оценкам, Солнце содержит порядка 10⁵⁷ атомов. Если условно считать подсчёт одного атома одной элементарной операцией, производительность компьютера составит:

10⁶⁰ операций в секунду

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

TOTP использует криптографическую функцию HMAC, которая в одном из распространённых вариантов основана на SHA-1. Проверка одного ключа требует нескольких тысяч элементарных операций. Для нашего фантастического эксперимента округлим это число до 10 000.

С учётом стоимости проверки одного ключа получаем производительность порядка:

10⁶⁰ / 10⁴ = 10⁵⁶ проверок в секунду

Теперь разделим число возможных ключей на производительность:

1,46 × 10⁴⁸ / 10⁵⁶ = 1,46 × 10⁻⁸ секунды

Это около 15 наносекунд.

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

Есть лишь одна загвоздка: Milliard Gargantubrain не существует.

Цена вопроса

До сих пор мы оценивали только время перебора ключей. Но есть ещё один необходимый ресурс — энергия.

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

Возьмём современный процессор Intel Core i9-14900K. При тяжёлой многопоточной нагрузке он потребляет примерно 250–300 Вт, а при снятых ограничениях мощности — до 350–400 Вт. Для расчёта используем нижнюю оценку — 250 Вт.

Предположим, что процессор способен проверять 10 миллионов TOTP-ключей в секунду. Это очень условная оценка. Рассчитаем энергозатраты на проверку одного ключа:

250 / 10⁷ = 0,000025 Дж

Всего 25 микроджоулей.

Много ли это? Такого количества энергии хватит, лишь чтобы маломощный индикаторный светодиод горел 25 миллисекунд или чтобы поднять каплю воды на высоту 5 сантиметров. Ничтожно мало.

Но на первой итерации необходимо проверить все 2¹⁶⁰ возможных ключей. Умножим:

1,46 × 10⁴⁸ × 0,000025 ≈ 3,65 × 10⁴³ Дж

Получается 36,5 тредециллиона джоулей.

Чтобы представить масштаб, вспомним, что Солнце каждую секунду излучает примерно 3,83 × 10²⁶ джоулей энергии. Разделим наши энергозатраты на светимость Солнца:

3,65 × 10⁴³ / 3,83 × 10²⁶ ≈ 9,53 × 10¹⁶ секунд

Это приблизительно 3 миллиарда лет.

Иными словами, даже научившись собирать абсолютно всю энергию солнечного излучения, мы накапливали бы её 3 миллиарда лет, чтобы провести первую итерацию перебора. Причём речь обо всей энергии Солнца, а не только о той ничтожной доле, которая достигает Земли.

Конец

Можно ли восстановить секретный ключ TOTP, наблюдая за шестизначными кодами? Теоретически — да. На практике такая задача настолько далеко выходит за пределы современных технологий, что беспокоиться о восстановлении ключа таким способом не приходится.

 

Источник