Довольно часто я принимаю участие в рабочих созвонах, во время которых один и тот же менеджер включает демонстрацию своего экрана. Нередко при этом ему требуется авторизоваться в одном и том же корпоративном сервисе.
И каждый раз он сначала вводит логин и пароль, затем где-то по ту сторону экрана открывает на телефоне приложение-аутентификатор и на втором шаге авторизации вводит текущий шестизначный код.
И каждый раз в этот момент я отпиваю кофе и думаю одну и ту же мысль: “Интересно, насколько безопасно показывать эти шесть цифр всем участникам встречи? Что, если сохранять эти коды вместе с точным временем их использования, а затем попытаться восстановить по ним секретный ключ?”
Для упрощения задачи можно оставить на время логин и пароль за скобками (допустим, что мы их уже получили каким-то образом). Нас интересует исключительно второй фактор аутентификации — 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, наблюдая за шестизначными кодами? Теоретически — да. Практически — решение задачи настолько далеко от современного уровня технологий, что нет никаких причин об этом беспокоиться.
Источник: habr.com