По замыслу, догадка в криптосистеме применяется только к одному кортежу открытого текста, ключа и зашифрованного текста. Если вам нужно проверить, дает ли определенный пароль доступ в мою учетную запись на почтовом сервере, вы проверяете комбинацию имени пользователя и пароля. Если у вас есть список хэшированных паролей, вы можете запустить алгоритм, подобный следующему (мы вернемся к тому, почему я использую термин «хэшированный», через минуту):
List dictionary[words] // a set of candidate passwords
List passwords[hashes] // a set of hashed passwords
For word in dictionary {
Candidate = hash(word);
If ‘Candidate’ in passwords: print ‘Candidate’
С точки зрения злоумышленника, это удобно, потому что результат каждой операции хэширования сравнивается с каждой записью в списке паролей. Если список состоит из 50 хэшированных паролей, они делают хэш один раз и сравнивают его с 50 сохраненными паролями.
Мы используем алгоритм хэширования, потому что если мы зашифровали список паролей, то любой, кто украдет ключ шифрования, может просто расшифровать список. И на самом деле мы используем то, что называется соленым хэшем. «Соль» – это маленькая случайная величина, своя у каждой записи в списке паролей, и мы хэшируем (соль, пароль) и храним соль, хэш. (Если быть точным, то слово «маленький» здесь означает достаточный для того, чтобы иметь уникальную соль для каждого элемента в списке – обычно 32 бита или более, – и есть несколько аргументов против 128 или 256 битов.)
Таким образом, как показано в таблице 7.1, даже если у нас один и тот же пароль, наши сохраненные значения паролей будут разными. (Для удобства чтения я использую короткие соли и усеченные хэши.)
Таблица 7.1. Пароли и соли
Конечным результатом является то, что работа злоумышленника по хэшированию одной потенциальной комбинации пароля и соли раскрывает не более одного пароля, а не один хэш, что приводит к раскрытию каждого пользователя, чьим паролем является RememberAlderaan. (Галактика кишит сторонниками повстанцев.) Если предположить, что поиск в таблице выполняется быстрее, чем хэширование, то это хорошо для защитника. На самом деле, мы разрабатываем алгоритмы хэширования таким образом, чтобы их нельзя было ускорить.
Атака методом грубой силы всегда будет работать при наличии достаточного количества времени, поэтому криптосистемы имеют очень большие пространства поиска (длины ключей).
Информированное угадывание. Теперь, если RememberAlderaan является распространенным паролем, возможно, злоумышленники упорядочат свои словари так, чтобы он шел перед другими кандидатами из 17 символов. Злоумышленник может упорядочить свой словарь любым образом, и сегодня порядок основан на крупных утечках паролей, в результате которых были раскрыты десятки миллионов паролей. Злоумышленники, как правило, угадывают в неравномерно распределенном пространстве поиска. По мере того как они нацеливаются на конкретного человека, знание других паролей, которые он использовал, или его хобби, фамилий и важных дат, таких как дни рождения и годовщины, может резко изменить шансы.
Запоминающиеся строки гораздо легче запомнить и даже набрать, что способствует эффективности словарей. (Кстати, если вы все еще вводите свои пароли, как доиндустриальные эвоки, приобретите менеджер паролей.)
Компромиссы между временем и памятью, включая радужные таблицы. Если у вас ресурсоемкая операция, кэширование результатов может быть полезным. Если эта операция заключается в хэшировании паролей, злоумышленники могут хранить хэши наиболее распространенных миллиардов или триллионов возможных паролей или комбинаций паролей и соли. Если соль имеет только 12 бит (как в случае с хранилищем парольных слов Unix), то это лишь 4096-кратное увеличение потребности в хранилище. Да, только. Кажется, что это много, и так оно и есть, но, если у вас есть миллиард 8-байтовых последовательностей и миллиард 16-байтовых хэшей, это 24 миллиарда байт, то есть 24 ГБ. Чтобы увеличить этот показатель в 4096 раз, потребуется примерно 100 ТБ. Но для этого нужно хранить миллиард паролей – примерно по три на каждого жителя Соединенных Штатов.
Когда мы думаем о том, что хранить, мы приходим к компромиссу между временем и памятью. Если соли отсутствуют или невелики, можно предварительно вычислить значения для популярных паролей (скажем, первые несколько миллионов). Вместо того чтобы пересчитывать, вы сохраняете результаты. Это приводит к компромиссу между хранилищем и последующим временем вычислений.
Существуют гораздо более умные способы оптимизации, в том числе «радужные таблицы». Это позволяет гибко выбирать между пространством для хранения и затратами времени на поиск.
Проблема дня рождения
Есть атаки, где атакующему нужно получить очень конкретное попадание; в других случаях сгодится любое совпадение. Забыть о втором варианте легко, что приводит к неприятностям.
Например, предположим, что у вас есть веб-сервер и вы хотите получить правильный большой номер для доступа к фотографиям, поэтому вы создаете URL-адреса вида /pictures/19800521/photo1, /pictures/19800521/photo2 и т. д. Возможно, я не угадал, какой именно большой номер нужен для просмотра фотографий, которые загрузил Джордж Лукас. Если /pictures/19800522/ – это фотографии режиссера фильма «Империя наносит ответный удар» Лоуренса Кэздана, я в любом случае могу быть доволен. Конечно, это тривиальное увеличение на единицу, что хуже, чем маленькие случайные числа, которые еще хуже, чем большие случайные числа. Если вы пытаетесь угадать мой пароль, вам нужно найти конкретную строку в списке сохраненных паролей. Но если для ваших целей сгодится любой пароль, показатель трудозатрат значительно снижается.
Из статистики можно сделать важный вывод, который называется проблемой дня рождения. Это простая задача: сколько человек должно находиться в комнате, чтобы с вероятностью 50 % двое из них имели общий день рождения? Ну, я надеюсь, что к этому моменту вы почувствуете ловушку. Если вы не почувствовали ловушку, ничего страшного; считайте, что вы предупреждены. С этим предупреждением запишите ваш ответ. Некоторые люди напишут 182, потому что это интуитивно очевидное число, и оно совсем неверно. У первого человека есть все шансы не совпасть в дне рождения. Второй человек имеет шанс 364/365 не совпасть с тем человеком, которого уже упомянули. Вероятность того, что следующий игрок не совпадет, составляет 363/365, а общие шансы составляют 1 × 364/365 × 363/365. По мере того как мы добавляем людей, вероятность того, что кто-то не найдет совпадений в комнате, снижается до чуть менее 1 к 2 при количестве людей всего лишь 23. А теперь вопрос: каковы шансы, что при наличии 23 человек в комнате у кого-то конкретно день рождения совпадет именно с вашим? Шансы падают обратно к 1 из 365 – опять же разница между необходимостью угадать любое допустимое значение и необходимостью угадать конкретное.
Атака угадыванием дня рождения актуальна, потому что злоумышленнику иногда нужно угадать определенный день рождения, а иногда ему нужно угадать любой день рождения, и шансы угадать растут удивительно быстро. Например, может быть, им нужен файл, который хэшируется в определенное значение SHA-2, или, может быть, им нужен файл, который хэшируется в любое значение SHA-2, подписанное вашим ключом? (SHA-2 – это криптографический хэш-стандарт.)
Иногда новички в области безопасности хотят разработать свои собственные криптосистемы, и это здорово. Это может быть приятным опытом обучения, например, когда вы видите, как ваша боевая станция уничтожается каким-то фермерским мальчишкой, управляющим истребителем, в котором он сидит в первый раз. Шансов на то, что ваша система выживет, намного меньше, чем шансов на успешную навигацию в астероидном поле. Так что не стесняйтесь что-то проектировать, но, пожалуйста, не применяйте это на практике. Существуют также угрозы, связанные с таймингом: если ваша криптография работает быстрее в одних обстоятельствах, чем в других, злоумышленники будут использовать это для выкачивания информации. Это подводит нас к теме времени.
Время и временны́е угрозы
То, что «время – это иллюзия», не мешает системам полагаться на него в целях безопасности. Есть атаки, которые полагаются на изменение времени, атаки, которые полагаются на измерение времени, и это самое подходящее время, чтобы поговорить о проблемах с последовательностью, если у нас не закончится время.
Многие сетевые протоколы полагаются на то, что часы приблизительно сверены. Они ожидают, что удаленные системы будут соблюдать сроки годности. К угрозам относятся сообщения, которые появляются слишком рано или слишком поздно, а также те, в которых вместо порядковых номеров или случайных чисел используется время.
Злоумышленникам бывает полезно знать, сколько сейчас времени по мнению удаленной системы или сколько времени заняло какое-либо действие.
Как мы видели в главе 4 «Раскрытие информации и конфиденциальность», измерение того, сколько времени занимает шифрование или расшифровка, может помочь вам определить, сколько битов содержится в ключе. Точно так же такие атаки, как Spectre, используют время, чтобы увидеть, какие данные находятся в кэше и приводит ли данная операция к попаданию в кэш или к промаху.
Оказывается, когда вы позволяете злоумышленнику запускать код, даже код с ограничениями, он может определить местное время достаточно точно для всякого рода пакостей. На самом деле, в документе о Spectre инженеры Google пишут и «Просто перечислить все часы сложно», и «Удивительно, но грубые часы все еще полезны для эксплуатации уязвимости» [Awhalley, 2018].
Удаленные системы послушно предоставляют время множеством способов, начиная от протокола времени (порт 37) и заканчивая баннерами, заголовками, содержимым сообщений, журналами и другими деталями, предоставляемыми почтовыми серверами, веб-серверами и другими протоколами.