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

Время взлома

Всякий шифр, кроме единственного абсолютно стойкого, можно взломать. Взлом займёт какое-то время. Если перебирать 128-битный ключ симметричного шифра по триллиону в секунду, то потребуется около десяти триллионов раз израсходовать миллион земных лет времени, чтобы проверить все 2^128 ключей. В общем, долго, даже если тут ошибка в количестве порядков. Но секунды, годы – это всё интервалы времени.

Для идеального шифра, чтобы получить хорошие шансы угадать ключ, нужно перебрать половину пространства ключей. Для 2¹²⁸ – это не очень-то помогает: 2¹²⁷ всё равно потребляет «триллионы из миллионов». Но если в структуре шифра есть дефекты, ведущие к уязвимостям, которые позволяют разбить пространство перебора на меньшие области, то успешный перебор может потребовать гораздо меньше времени. Например, машина с триллионной производительностью из предыдущего абзаца исчерпает 2⁴⁸ ключей менее, чем за пять минут.

При оценке криптостойкости всегда используют такой параметр, как время. Просто время тут измеряется в количестве операций. Потому что сложно определить стандартную криптографическую «секунду перебора», но можно определить элементарные операции, реализующие математические преобразования шифра. Однако речь всё равно идёт о некотором вычислительном кванте, который соответствует времени. Это время взлома. Или – количество операций, требуемых для раскрытия секрета с высокой вероятностью.

На практике, требуемая стойкость шифра связана со временем актуальности сведений в защищаемых сообщениях. Если сведения в сообщении устареют через сутки, то, в принципе, это сообщение достаточно защитить шифром, на взлом которого гарантированно потребуется один месяц. Ну, или миллиард лет. Практические шифры Интернета, например AES в TLS/HTTPS, имеют предполагаемую стойкость во многие миллиарды лет вычислений. Чтобы точно хватило. Хотя, насчёт «точно» – никто точно не знает. Но ситуации, когда не понятно, как долго нужно сохранить данные в секрете, встречаются постоянно. Хуже того: то, что четверть века назад взламывалось за годы, сегодня требует лишь дней – ну, чтобы оформить доступы к суперкомпьютерам, которые потом за минуту выдадут ответ.

Ускорение вычислений. Это тоже вопрос времени. Квантовые компьютеры ожидают уже многие и многие годы. Очень долго. Их всё нет, но угроза, что записанный сейчас трафик расшифруют через пятьдесят лет на квантовом компьютере – есть. И действительно: всегда можно смело сказать, что до создания нужного квантового компьютера остаётся ещё лет двадцать – это очень хорошая стратегия, полностью подкреплённая теорией игр.

Если вы подумали, что квантовые компьютеры не шибко влияют на симметричные шифры типа AES, то вы не совсем угадали. Да, известные универсальные алгоритмы могут ускорить перебор всего лишь на экспоненциальную половину – квадратный корень, то есть 2¹²⁸ превратится в 2⁶⁴, поэтому достаточно взять 2²⁵⁶, чтобы гарантировать стойкость. Однако это универсальные алгоритмы, но не факт, что для конкретных шифров не появятся какие-то улучшенные квантовые алгоритмы, способные взломать эти шифры за разумное время.

Основной скачок времени для квантовых компьютеров намечен в направлении взлома не симметричных, а асимметричных систем, которые служат для обмена ключами. То есть, чтобы получить общий симметричный секрет, используется асимметричная криптосистема (обычно – протокол Диффи-Хеллмана). Эту криптосистему и станут взламывать квантовым алгоритмом Шора, если смогут построить квантовый компьютер за обозримое время. Пока что на квантовых компьютерах даже не научились раскладывать на множители произвольные числа, а обмен ключами в том же TLS уже защищён криптосистемами с постквантовой стойкостью, для быстрого взлома которых квантовых алгоритмов пока не найдено.

Время как координата

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

Распространённый пример – протокол TOTP (time-based one-time password): стороны этого протокола обладают общим секретом, на основе которого вычисляется токен, зависящий от текущего момента времени. Поэтому для того, чтобы метод работал, у сторон должно быть и общее время. Если вы используете TOTP, – а это очень популярный нынче источник «второго фактора» (почему-то считается надёжным), – то как только часы в системе, генерирующей токен, и часы в проверяющей системе сильно разойдутся, тут же токены перестанут срабатывать. Это одна из самых распространённых причин обращения в техническую поддержку одноразовых кодов: «– Ой, мои токены перестали подходить! – Не расстраивайтесь: давайте-ка лучше сверим часы!».

Время здесь опять прямо влияет на криптографические операции: вычисление значения одноразового кода (токена) использует таймстемп; стабильность координат по времени критически важна для того, чтобы схема работала. И если кто-то увёл секрет TOTP, то этот кто-то сможет подобрать токен под любое время (хоть бы и в будущем).

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

Доверенные метки времени используются в инфраструктуре цифровых подписей, позволяя проверить, существовала ли данная подпись раньше заданного момента времени. Обычно такие подтверждения предоставляют специальные провайдеры меток времени, и эти провайдеры криптографически подтверждают выдаваемые метки. Корректная «обработка прошлого» вообще большая проблема в цифровом документообороте. Предположим, есть некоторый документ, который подписан ключом из пары, открытая часть которой удостоверена сертификатом. Но сертификат этого ключа закончил действовать ещё пять лет назад. Можно ли верить в подпись на документе?

Казалось бы, давайте верить, ведь мы не подписываем, а проверяем подпись, и в момент подписывания – сертификат действовал. Но это всё домыслы, если прошло десять лет: ключи не даром имеют срок действия – возможно, за прошедшее время кто-то построил квантовый компьютер, подобрал все ключи цепочки и подписал документ, выпустив поддельные сертификаты задним числом. Так что верить в подпись больше нельзя. Что может быть довольно печально, благодаря интенсивной цифровизации документооборота. Поэтому-то и нужны какие-то цепочки значений хеш-функций и тому подобные решения, самое суперсовременное из которых называется «блокчейн»: основная роль, которую блокчейн играет, это строгое закрепление последовательности записей – что после чего появилось. Например, кто раньше потратил часть биткойна. Временны́е координаты важны своей жёсткостью. Впрочем, кто там чего может гарантировать в отношении цепочек хеш-функций? Говорят, что математика, стоящая за сложностью синтеза золота, понадёжнее SHA-256. Да, даже несмотря на философский камень.

Точность интервалов времени

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

Проблема локальных часов, отстающих от часов удостоверяющего центра, считается настолько распространённой, что УЦ Let's Encrypt, например, специально ставит время начала действия сертификата на час раньше, чем этот сертификат был выпущен! Машина времени. Криптографическая, но виртуальная. Так делает не только Let's Encrypt, но сильный «бэкдейтинг» TLS-сертификатов не приветствуется. Для автоматических систем быстрого выпуска сертификатов, как у Let's Encrypt, разумный «бэкдейтинг» важен потому, что свежевыпущенный сертификат уже приехал на сервер, а пользователи с отстающими часами не могут зайти на веб-сайт, так как в их «таймфрейме» сертификат ещё не начал действовать. При валидации сертификатов – важны обе временные границы, именно так: не раньше, не позже.

Определить, что время, поставленное в сертификаты, отстаёт, не так уж трудно: для этого есть логи Certificate Transparency. Логи выдают свои таймстемпы, – так называемые SCT-метки, – эти таймстемпы включаются в состав сертификата, обозначают момент, когда сервис лога увидел данные сертификата, и время может сравнить каждый самостоятельно (например, значение SCT выводит сервис анализа веб-узлов ТЦИ).

Certificate Transparency (CT) – один из масштабных примеров внедрения разных методов прикладной криптографии. Интервалы времени из сертификатов приводят к интересному эффекту. В CT все выпущенные сертификаты должны записываться в логи. Точнее – записываться должны специально выдуманные пресертификаты, но здесь мы будем всё называть сертификатами, поскольку для рассказа о времени в криптографии это не имеет особого значения. Из логов сертификаты могут читать все желающие – в этом смысл CT. Но сертификатов для TLS сейчас выпускается очень много в единицу времени – поток их настолько велик, что CT-логи пухнут слишком быстро. Распухание логов приводит к исчерпанию дискового пространства для хранения логов. Поэтому придумали тайм-шардинг.

Тайм-шардинг в CT-логах это ведение отдельных логов для сертификатов каждого интервала времени. Например, пусть будет отдельный лог для периода с июля по декабрь 2026 года. Каждый сертификат теперь попадает в тот лог, во временной интервал которого указывает таймстемп окончания действия сертификата. Обратите внимание, это важно: сертификаты сортируются по дате окончания действия, а не начала, это даёт логам возможность работать на опережение. И опять же – именно время тут играет главную роль.

Утечки через измерение времени

Есть и другой аспект: утечки информации о внутреннем состоянии реализации той или иной криптосистемы, связанные с различным временем выполнения криптографических операций. Что это означает? Возьмём какое-то работающее средство криптографической защиты информации и будем измерять, сколько микросекунд это средство защиты затратило на выполнение одной и той же операции, но с разными данными. Например, будем подписывать разные документы, измеряя время подписывания. Если удалось найти корреляцию между данными и временем выполнения криптографической операции, то, возможно, удастся раскрыть секретный ключ, так как алгоритм подписи известен. Поэтому критически важные операции стараются реализовать так, чтобы они выполнялись за фиксированное время, вне зависимости от входных данных. Это требует специальных алгоритмов и не всегда возможно. Заметьте, что схема работает не только для компьютерных систем, но и для электромеханических машин.

Хрестоматийный случай, с которого сейчас должны начинаться спецкурсы по разработке прикладных криптографических программ, это, конечно, утечка секретов при неверной реализации операции сравнения битовых строк. Реализация «в лоб» означает, что сравнение двух строк прекращается в момент обнаружения первого расхождения. Действительно, для того, чтобы строки были различными, достаточно расхождения в один бит. Здесь время (точнее – количество тактов), требуемое для вывода результата сравнения с секретным значением, зависит от состава входной строки.

Пусть уязвимая система выдаёт аутентификационный токен в том случае, если указана верная секретная строка длинной 128 бит. Тогда атакующая сторона может направлять произвольные данные в уязвимую систему и измерять время обработки каждого варианта строки. Может показаться, что для полного перебора с гарантированным нахождением секрета всё так же требуется 2¹²⁸ запросов. А это очень долго. Но это только так кажется. В том-то и фокус данной уязвимости, что она «сжимает» время за счёт утечки: атакующий может определить позицию, на которой разошлись биты. Если ответ системы максимально быстр, значит не совпал первый бит. Инвертируем этот бит – и вот он уже правильный. Отправляем изменённую строку на проверку, измеряем время проверки. По полученному значению времени определяем, какой бит не совпал с секретом. И так далее. Если сравнение уязвимо, то перебрать 128 бит с битовым разрешением можно за 128 запросов. Такой же подход работает и для более практического варианта – с байтами: утечка позволяет определить позицию последнего совпавшего байта. Но перебирать тут придётся подольше, ведь в один байт влезает 256 значений.

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

Следите за временем. Его не существует, но поэтому оно особенно важно. Как концепция.