dxdt.ru: занимательный интернет-журнал

В связи с успехами проектов квантовых компьютеров опять рассказывают про “закат современной криптографии”, а рассказывать-то нужно о том, что постквантовый криптографический мир наступит раньше, чем будут созданы опасные квантовые компьютеры (если их вообще создадут).

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

“Универсальный квантовый компьютер” – что под этим подразумевается? Подразумевается сложное устройство, которое позволяет выстраивать составляющие его базовые элементы, обладающие “квантовыми свойствами”, в произвольные схемы с заданной архитектурой. “Схемы” здесь обозначают такие конфигурации, в которых возможно создание общего квантового состояния для набора элементов, с последующим управлением эволюцией получившейся системы и возможностью контролируемого измерения. Упрощённо, такую систему можно назвать “набором кубитов”, так обычно и поступают. Кубиты строятся различными способами, а получившаяся логическая схема, вообще говоря, должна обладать обратимостью (то есть, состояния можно проигрывать по времени не только вперёд, но и назад – это означает, что информация о предыдущих состояниях на входах не теряется: её можно восстановить по выходам). Квантовый компьютер должен реализовывать достаточное для практических применений количество вычислительных кубитов.

“Квантовый алгоритм” – это какой? Главная особенность квантовых алгоритмов в том, что они, – по крайней мере, в своей квантовой части, – не подразумевают вычислений в привычном по классическим устройствам смысле слова. Классический вариант предполагает пошаговое проведение операций с некоторыми значениями. В квантовом случае всё хитрее: здесь сама схема, реализующая алгоритм, устраивается таким образом, чтобы после измерения она с высокой вероятностью оказалась в состоянии, соответствующем искомому ответу. Максимизация вероятности получения полезного ответа реализуется благодаря интерференции квантовых состояний, в которых вычислитель прибывает одновременно. Поэтому неверно говорить, что “квантовый компьютер параллельно проверяет множество вариантов” – напротив, квантовый компьютер ничего не проверяет, однако само пространство всех возможных его состояний оказывается устроено так, что после измерения оно с высокой вероятностью схлопнется в один из искомых вариантов, который и есть решение. Всякий эффективный квантовый алгоритм подразумевает, что за решаемой задачей стоит некоторая точная математическая структура, которую классический компьютер может найти только перебором вариантов, а квантовый – в результате применения некоторого набора квантовых преобразований сразу ко всему пространству состояний. То есть, необходимых для решения задачи циклов работы квантового компьютера оказывается существенно меньше.

Например, когда говорят о задаче криптографии с открытым ключом, речь идёт об алгоритме Шора. Квантовая часть этого алгоритма позволяет найти значение (период известной функции), знание которого делает возможным быстрое вычисление разложения заданного числа на множители уже на классическом компьютере. Искомый период функции здесь и есть отражение структуры, соответствующей разложению на множители. Собственно, разложение на множители актуально для криптосистемы RSA, однако тот же алгоритм позволяет взломать и криптосистемы, основанные на задаче дискретного логарифмирования, например, подпись ECDSA или распространённые сейчас реализации алгоритма Диффи-Хеллмана.

Итак, алгоритм Шора, в теории, позволяет взять произвольный открытый ключ RSA, за часы или дни найти для него разложение на простые множители, после чего практически мгновенно получить соответствующий секретный ключ. В чуть больших деталях этот процесс мог бы выглядеть так: открытый ключ RSA уже известен, он состоит из модуля M и “шифрующей экспоненты” e – это два целых числа; модуль является произведением двух простых чисел M = p*q; секретный ключ представляет собой “расшифровывающую экспоненту” d (опять целое число), которая соответствует “шифрующей”. Знание p и q позволяет очень быстро вычислить d для заданной экспоненты e на обычном компьютере (собственно, это вычисление проводится всякий раз, когда генерируется пара ключей RSA).

Сколько кубитов потребуется для атаки на практически используемые ключи RSA? Типичная битовая длина RSA-модуля сейчас 2048 бит. А вот оценки для количества кубитов – очень разные. Из свойств алгоритма Шора понятно, что потребуется, как минимум, двойная разрядность, то есть, 4096 кубитов. Однако эта оценка очень оптимистична: предполагается, что в зависимости от физического воплощения квантового компьютера и реализации алгоритма Шора может потребоваться и десятикратное увеличение (то есть, 20480 кубитов), и даже миллионы кубитов. Так или иначе, сейчас, когда говорят об универсальных квантовых компьютерах, имеют в виду единичные устройства с несколькими десятками кубитов (например, 53 кубита у Google и IBM). Поэтому до практических разрядностей ещё далеко. Тут, впрочем, есть два интересных момента: во-первых, вполне вероятно, что получив работающий универсальный квантовый компьютер с сотней кубитов, его смогут быстро масштабировать на тысячи и далее; во-вторых, для атаки на широко применяемые сейчас криптосистемы, использующие арифметику эллиптических кривых (ECDSA), кубитов нужно меньше, чем в случае с RSA, потому что меньше разрядность.

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

Такие криптосистемы разрабатываются давно, некоторые из них были даже предложены задолго до публикации алгоритма Шора (опубликован в 1994). Естественно, совсем старые системы не позиционировались как постквантовые, это свойство возникает у них в качестве дополнительного – просто, для их криптоанализа не подходит метод, основанный на нахождении периода функций. К сожалению, для использования они не годятся по другим причинам: либо оказались уязвимы для классического криптоанализа (стойкость к взлому при помощи квантового алгоритма вовсе не означает, что криптосистема будет стойкой и в классическом случае), либо просто чрезвычайно неудобны на практике.

NIST уже несколько лет выполняет программу по выбору постквантовых криптосистем. Есть надежда, что внезапно возникший квантовый компьютер вряд ли “сломает всю мировую криптографию”, хоть такой вариант и нельзя полностью исключать, прежде всего, по причине его особой литературной ценности. Более вероятно, что к моменту создания этого самого компьютера – постквантовые криптосистемы уже давно войдут в практику. Или даже так: постквантовые криптосистемы уже будут широко использоваться, а подходящий для взлома 1024-битной RSA квантовый компьютер всё ещё будут пытаться построить.

Тем не менее, на данный момент, массово внедрённых постквантовых криптосистем с открытым ключом – нет. Существуют только экспериментальные варианты. Но некоторые из них даже внедрялись в браузере Chrome.

Скорее всего, на практике будет использован тот или иной вариант криптосистемы на эллиптических кривых. Для генерации общего секрета – протокол Диффи-Хеллмана (DH). С этим протоколом связано одно из расхожих заблуждений, что, якобы, он не обладает постквантовой стойкостью. В реальности, уязвимости возникают вовсе не в протоколе Диффи-Хеллмана, а в применении алгоритма Шора к математическими объектами, стоящим за классическими реализациями DH. Криптоанализ на квантовом компьютере позволяет быстро решать задачу дискретного логарифмирования в конкретном математическом окружении, но протокол Диффи-Хеллмана прекрасно обобщается на другие математические конструкции. Поэтому сразу несколько кандидатов в постквантовые криптосистемы используют DH (примеры: SIDH, CSIDH).

Постквантовые криптосистемы необходимы для решения двух высокоуровневых задач: электронная подпись и генерация общего секрета (распределение симметричных ключей). Третья фундаментальная часть практической криптографии – симметричные шифры — не столь подвержена квантовым атакам: несмотря на то, что возможны какие-то квантовые улучшения для атак на конкретные шифры, считается, что в целом, использование мощного квантового компьютера позволяет получить лишь квадратичный прирост в скорости перебора. То есть, добротный шифр с 256-битным ключом даёт 128 бит постквантовой стойкости, а этого более чем достаточно. Отсюда выводится весьма консервативная рекомендация: если вы опасаетесь за секретность передаваемых данных в ситуации наступления эры квантовых компьютеров, то проще всего сейчас отказаться от асимметричных криптосистем, перейти исключительно на симметричные шифры. Таким образом, “конец асимметричной криптографии” наступит в отдельно взятом случае ещё раньше, чем появится квантовый компьютер. Конечно, это не очень-то практичное решение. В некоторых особенно “специальных” случаях, действительно, такими решениями пользуются, как применяют и абсолютно стойкий шифр Вернама, но представить, что от асимметричных криптосистем полностью отказались в массовых протоколах вроде TLS – непросто. Причина понятна: большую проблему составляет распределение ключей. (Но в случае небольшого закрытого списка корреспондентов и наличия возможности обмениваться твердотельными носителями информации – задача распределения ключей решаема.)

Однако в любом случае придётся учитывать такой момент: для обычных защищённых протоколов, где сеансовый секрет генерируется только при помощи той или иной классической асимметричной криптосистемы, под угрозой оказывается записанный трафик. Квантовый компьютер позволит восстановить симметричный ключ из записанных данных, после чего можно расшифровать весь поток (я описывал это некоторое время назад, применительно к TLS).

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

На Wired небольшая заметка (англ.) о том, что системы “искусственного интеллекта”, которые построены на основе популярных сейчас методов машинного обучения, могут содержать в себе алгоритмические закладки, приводящие, в случае активации, к неожиданным эффектам. Это довольно старая тема, но сейчас она начинает проникать в популярные СМИ.

Речь идёт о том, что на этапе обучения в систему могут быть специально заложены сценарии, срабатывающие в строго определённых условиях. Например, при демонстрации конкретного изображения. Хитрость состоит в том, что обнаружить наличие таких сценариев, или как-то гарантировать, что их нет, – чрезвычайно сложно. Дело в том, что современное машинное обучение, грубо говоря, это автоматизированный подбор огромного количества коэффициентов, составляющих некоторые уравнения (или формулы). Получающийся в типичном случае результирующий набор данных, часто называемый “обученной нейросетью”, настолько огромен, что полностью необозрим даже для автоматизированных методов анализа.

Готовая нейросеть работает очень быстро, поскольку задача вычисления результата применения нейросети к конкретному набору входных данных – простая, в вычислительном смысле. В этом, собственно, и состоит удобство: можно быстро получить более или менее приемлемый результат – распознать объект, выбрать сценарий действий и пр. Однако обратная задача, в которой всем возможным значениям на выходе сопоставляются входные значения (то есть, прообразы), оказывается чрезвычайно сложной, требующей больших вычислительных мощностей, если она вообще разрешима на практике.

Представьте, что есть нейросеть, которая обучена узнавать наличие дикобразов на фотографии. В простейшем случае, вы применяете нейросеть к конкретному изображению, а на выходе получаете один бит: “есть дикобраз” – 1; “нет дикобраза” – 0. Пусть входное изображение имеет допустимые размеры в 1 млн пикселей (1000×1000 – это не важно). Посчитать выходной бит нейросети для любого фотоснимка очень просто, компьютер справляется за малую долю секунды. Но развернуть биты обратно, разбив все допустимые входные изображения на два класса (“есть дикобраз”/”нет дикобраза”), очень сложно, так как нейросеть состоит из тысяч коэффициентов, выстроенных в несколько слоёв (или представленных как система уравнений, это не принципиально) – граф состояний нейросети огромен. А перебрать все возможные сочетания пикселей, скармливая нейросети тестовые изображения – и того сложнее. Соответственно, может существовать сочетание пикселей, при наличии которого любой дикобраз, хорошо видимый на картинке, узнан не будет, с гарантией. Просто, на этапе обучения “нейросети” такие картинки специально подсовывались в выборку и отмечались как “здесь точно нет дикобраза”. Это и есть алгоритмическая закладка. Конечно, в несколько утрированном виде, но общая логика – именно такая.

Так что обнаружить алгоритмическую закладку на практике нельзя, а работать эта закладка будет идеально, даже точнее, чем все прочие возможности нейросети. И нейросеть, призванная распознавать объекты в видеопотоке и используемая в системе контроля доступа, станет игнорировать присутствие в кадре людей, надевших маску Микки-Мауса – они смогут беспрепятственно перемещаться по охраняемой территории.

Речь о протоколе, который скрывает метаинформацию о самом факте обмена сообщениями. Какими свойствами должен обладать такой протокол? Можно ли что-то подобное вообще реализовать на практике? Прежде чем такие вопросы более или менее содержательно формулировать, нужно, конечно, выбрать модель угроз.

Предположим, что стоит задача устойчивого обмена короткими сообщениями (тексты и фотографии низкого разрешения) через тот или иной вариант “глобальной” Сети. “Глобальной” в кавычках, потому что ситуация за пару десятков лет изменилась очень существенно: есть все основания не только использовать здесь кавычки, но и рассматривать возможность потери связности и разделения Сети на сегменты (которые, к тому же, не работают и внутри, но это другая история). Чтобы излишне не сгущать тучи, предполагаем, что связность всё же есть, какие-то данные передаются, однако некая третья сторона полностью контролирует трафик, просматривает его, может произвольно подменять узлы, передаваемые данные, и старается прервать все сеансы обмена, которые не были прямо санкционированы автоматом фильтрации (это вариант “белого списка протоколов”, который, например, я упоминал в недавней статье про фильтрацию трафика). Система фильтрации/блокирования пытается обнаружить трафик скрытого протокола, выявить узлы, его использующие, и работает в автоматизированном режиме: то есть, фильтры и блокировки включаются автоматом, но правила могут задаваться вручную.

Скрытый протокол, по условиям задачи, должен работать на базе распределённой сети и не требовать строгого центрального управления всеми узлами при обмене сообщениями. Это обусловлено риском компрометации такого “центра управления”, а также тем, что центральный вариант гораздо более уязвим к сегментации сети (да, есть варианты с автоматическим выбором нового “центра” и так далее, но мы пока просто примем, что протокол использует распределённую сеть).

Сразу же возникает вопрос о транспорте данных (может быть, этот транспорт – TCP?), но так как мы практически сразу столкнёмся с необходимостью стеганографии и маскировки узлов, то с транспортом всё окажется не так просто, поэтому конкретный протокол в условия задачи не включаем, оговорим только, что “какой-то транспорт” между “какими-то узлами” должен быть доступен.

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

Итак, какими свойствами и механизмами должен обладать скрытый протокол в таких (весьма жёстких) условиях?

1.

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

2.

Для сокрытия трафика необходимо использовать стеганографию. В принятой модели угроз, если один из узлов просто передаёт зашифрованное сообщение вне прочих сеансов, то этот факт тут же оказывается обнаружен. Стеганографический канал маскирует сеанс обмена сообщениями под трафик другого типа. Это означает, что протокол не может прямо использовать привычные виды транспорта, а должен подразумевать наличие дополнительного трафика. Простой пример: сообщения могут быть скрыты внутри текстов веб-страниц и веб-форм, в качестве базового трафика используется имитация работы с веб-сайтом. В данном случае, веб-трафик может передаваться по TCP или UDP, с использованием TLS/HTTPS или QUIC, экзотические варианты вместо веб-трафика используют непосредственно TLS, или даже служебные заголовки IP-пакетов и DNS, всё это не так важно для стеганографии. Важны достаточный объём данных и наличие симметричных ключей, позволяющих организовать стойкий стеганографический канал. При наличии ключей – такой канал организовать всегда можно. (Ключи используются для задания псевдослучайной последовательности, которая необходима для работы механизма встраивания скрытых данных в поток трафика.)

3.

Так как третья сторона может подменять узлы, протокол должен предусматривать аутентификацию узлов. При этом процесс аутентификации оказывается сложным: узел не может просто так назваться узлом, использующим скрытый протокол, да ещё и подтвердить это подписью – подобное решение раскрывает всю секретность, так как третья сторона получает возможность простым способом “проиндексировать” все узлы, поддерживающие протокол, что даёт дополнительную информацию о сеансах, в которых данные узлы участвовали. Простые алгоритмы, основанные на знании секретного ключа, очень эффективны, но они работают только в ограниченном случае – например, для закрытого списка корреспондентов. Пример такого алгоритма, реализованного на уровне веба: проверяющий полномочия узла корреспондент отправляет запрос HTTP GET, где в качестве имени документа указан уникальный код, снабжённый меткой подлинности, вычисленной на основе секретного ключа; узел, обнаружив такой запрос и убедившись в его валидности, отвечает соответствующим значением, также с меткой подлинности; если же запрос невалидный, то узел отвечает стандартной ошибкой HTTP – тем самым он оказывается неотличим от обычного веб-сервера. Однако, действительно хорошо скрытая от активного “индексатора” аутентификация, – или, если говорить строго, семантически стойкая аутентификация, – возможна только на базе нескольких итераций “запрос-ответ” и, похоже, оказывается весьма сложной. Другими словами, с аутентификацией как раз и могут возникнуть основные проблемы на практике.

4.

Необходим механизм миграции узлов и обнаружения ранее не известных адресов (имён) узлов, поддерживающих скрытый протокол. Понятно, что простая публикация списка не подходит. В принципе, возможны варианты, в которых успешный сеанс обмена сообщениями завершается передачей некоторых “секретов”, которые позволяют построить список вероятных адресов (или имён), а также ключей аутентификации, подходящих для следующих сеансов. Соответственно, для обнаружения новых узлов потребуется перебрать адреса из этого списка, пытаясь аутентифицировать их. Здесь возникает ещё одна отдельная задача – построение скрытого механизма сканирования узлов.

5.

Выбранная модель угроз гарантирует, что третья сторона может использовать подставные узлы, имитирующие узлы-участники скрытого обмена сообщениями. Если протокол поддерживает возможность создания новых каналов обмена сообщениями и подключения новых узлов (а это часто необходимо), то возникает ещё одна непростая задача: как отличить деятельность атакующей третьей стороны от настоящих участников обмена? Одним из вариантов решения является удостоверение ключей новых участников ключами уже работающих узлов (напоминает практику PGP). Однако, в случае скрытого протокола, процедура такого удостоверения может оказаться весьма сложной: как и где обмениваться подписями, не раскрывая факта такого обмена и идентификаторов узлов? Предположим, что скрытым протоколом хотят воспользоваться два участника, которые раньше сообщениями не обменивались – понятно, что у них, в общем случае, нет возможности отличить подставной узел от подлинного корреспондента. Можно было бы заблаговременно раздать всем некоторый общий открытый ключ, который будет удостоверять новые узлы, но в таком случае возникает центральная схема, которой все должны доверять, в том числе, новые участники. К тому же, схема неустойчива к утрате соответствующего секретного ключа (и кто его будет хранить?) Похоже, кроме варианта с предварительным распределением многих личных ключей, остаётся только офлайновый обмен (опять же, вспоминается PGP).

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

Нередко приходится встречать картинки под собирательным названием “как видит мир кошка”. Каждая такая картинка подразумевает сравнение с тем, как видит мир человек. Казалось бы, огромный объём данных, пытающихся описывать природу визуального восприятия мира человеком, в том числе, данных “популярных”, типа различных иллюзий, должен сразу поставить любую подобную картинку под сомнение. Человеческое зрительное восприятие связано прежде всего с психикой и предыдущим опытом, только потом – с устройством глаза. Вспомните разные шумные цветовые иллюзии, вроде прений о том, “какого цвета платье на фотографии” или “параллельны ли улицы на этих снимках”. Набор иллюзий у условной кошки – не известен, и уже поэтому представить, как видит мир кошка, не имея опыта конкретной кошки, человеку невозможно.

Вспомните про эксперименты с призматическими очками. Известно, что человеческий глаз даёт перевёрнутое изображение. То, где у мира условный “верх” и условный “низ” – определяет предыдущий опыт. Если взрослому человеку надеть очки, которые переворачивают картинку ещё раз, делая изображение на сетчатке ориентированным “правильно”, то он тут же начинает видеть мир перевёрнутым и испытывает трудности с навигацией по этому миру. Но если очки не снимать, то через несколько дней мозг адаптируется и переворачивает картину мира вновь: проблемы с ориентацией исчезают; до тех пор, конечно, пока подопытный человек не снимет призматические очки. Казалось бы, в данном случае, можно хорошо представить, как видит мир человек в подобных очках: просто показываем перевёрнутую картинку. О реальном же эффекте можно судить только по описанию ощущений, которое даёт испытуемый, и модель с переворотом изображения оказывается весьма грубой. Так, если верить отчётами, у испытуемого возникают переходные периоды, когда изображение переворачивается туда-сюда в результате каких-то манипуляций в поле зрения, например, движений руки или проявления хорошо знакомого феномена: “вещи всегда падают вниз, если их отпустить”. (Этот эффект похож на многие зрительные иллюзии, когда, приложив некоторое мысленное усилие, можно “перевернуть” или “обратить” наблюдаемую картинку.) В общем, оказывается, что другому человеку даже тут представить что-то в деталях, не надевая призматические очки, весьма непросто, а уж тем более, нарисовать точную модель.

А кошка? Предположим, что мозг кошки ещё “подцепляет” к каждому визуальному образу акустическую картинку (у кошек особые уши), а также (например) температурный фон и движение потоков воздуха (вибриссы никто не отменял). Все эти параметры формируют опыт, человеку недоступный, но для кошки – создающий то самое зрительное восприятие мира. Конечно, можно возразить, что акустика, температура объектов, потоки воздуха – это всё не имеет отношения к зрению. Однако, если бы это было так, то и человек в призматических очках всегда видел бы мир перевёрнутым.

Анонимизация больших объёмов данных, которые собирались для конкретных персон, представляет большую проблему. Особенно, если данные достаточно подробные, уникальные и их много. В недавно опубликованной работе исследователи показывают, что публично доступные “анонимизированные” базы “расшифровок” человеческой ДНК, собранные различными проектами, не только оказываются пригодными для эффективной деанонимизации, но ещё и позволяют идентифицировать людей, которые образцов ДНК ни в какой проект не сдавали (но, понятно, где-то такой образец оставили). Данные ДНК могут показаться разрозненными, но это совсем не так, если смотреть на них с точки зрения биологических механизмов. Интересно, что если наложить на набор данных ДНК генеалогические деревья, сопоставив родственников по фрагментам кода, то исходный набор “анонимных” данных тут же теряет всю свою “вариативность”. Если у вас есть база данных с ФИО и отношениями родства, то достаточно подставить в дерево хотя бы одну реальную персону, как все остальные узлы тут же деанонимизируются самым очевидным образом. При неполных данных – всё равно можно уверенно перескакивать между ветками, обнаруживая двоюродную и троюродную родню.

В работе по ссылке – показано, что механизм наследования достаточно силён для того, чтобы покрыть практически всю популяцию, собрав ДНК лишь у небольшой части людей. И речь тут идёт о том, что публичные “анонимизированные” базы позволяют идентифицировать персон, ДНК которых в базе отсутствует, но нашлись родственники разной степени “отдалённости”. Цитата:

“Используя конкретную модель, мы можем предсказать, что база данных с записями о приблизительно 3 млн жителей США европейского происхождения (2% соответствующего взрослого населения), позволяет найти для 99% населения данной этнической принадлежности как минимум одного троюродного родственника, а для 65% – как минимум одного двоюродного”.

Чтобы сопоставить реальных персон записям в базах ДНК, исследователи используют год рождения, примерное место проживания – это позволяет резко улучшить точность. Собственно, задача складывается в чисто комбинаторную, а комбинаторные соображения очень часто помогают убрать всё лишнее и найти реальную структуру, стоящую за данными. Я довольно давно писал на сходную тему, правда, в привязке к “анонимизированным” данным геолокации.

Немного занимательной теории чисел, применительно к одной весьма экзотической особенности TLS (как известно, это основной защищённый протокол современного Интернета). Изучая настройки и параметры данного протокола, можно столкнуться с интересной формулой:

p = 2ⁿ – 2ⁿ⁻⁶⁴ + 2⁶⁴(⌊2ⁿ⁻¹³⁰e⌋ + x) – 1

Для чего она нужна и что обозначает?

В новой версии TLS 1.3 зафиксированы практически все криптографические параметры, которые только можно как-то зафиксировать. Так, зафиксированы группы для протокола Диффи-Хеллмана (DH), причём, даже группы для “классического” варианта (“классический” – это который в мультипликативной группе кольца вычетов; а если говорить проще, то тот вариант, который по модулю простого числа, с взятием остатков, а не эллиптический). С наперёд заданными параметрами криптосистем связаны опасения: а вдруг эти параметры специально выбраны с бэкдором? Поэтому существуют методы, позволяющие генерировать параметры некоторым проверяемым и, вместе с тем, “непредсказуемым” способом. Теперь переходим к формуле.

Это формула, по которой генерируются простые числа, задающие группу для DH в TLS. n – требуемая разрядность, e – основание натурального логарифма, x – переменная, принимающая целые положительные значения. То есть, можно сказать, эта формула извлекает из числа e подходящее целое простое число нужной разрядности (подходящее – потому что подходит не всякое, но это детали). Для получения именно простого числа – нужно подбирать значение x (используется минимальное подходящее). Механизм описан в RFC 7919 (но попробуйте “нагуглить” эту формулу).

Простыми словами: смысл данной магической операции в том, что нельзя выбрать в качестве задающего группу параметра произвольное число с нужными свойствами (с бэкдором), а приходится довольствоваться фрагментом записи числа e. Конечно, вооружившись “секретными теоремами“, можно предположить, что данная формула как раз и извлекает только нужные простые числа, потому что само e – это бесконечная сумма значений, связанных со всякими комбинаторными штуками. Но это уже была бы магия столь высокого градуса, что лучше о её существовании я рассуждать не стану, тем более, что в записи e заведомо можно найти любое простое число, соответственно, и число с бэкдором.

Впрочем, с фиксированными параметрами DH связаны и более простые рассуждения: стойкость DH базируется на сложности дискретного логарифмирования, но для классического варианта и заранее заданной группы (параметра, то есть) известно, что можно предвычислить некоторые алгебраические структуры, которые потом позволят вычислять логарифм быстро. Правда, такие вычисления требуют огромных мощностей и/или затрат времени. Но если вы теоретико-числовая служба специального агентства и заранее знаете, что набор из нескольких групп позволит раскрывать почти весь TLS-трафик, то можно и потратиться. Ключевой момент тут – нужно заранее знать группу, а универсальные методы неизвестны.

Многие слышали про криптографию на эллиптических кривых. Но эллиптические кривые, которые давно являются мощным инструментом теории чисел, можно успешно применить к решению элементарной (по формулировке) арифметической задачки про бананы, яблоки и ананасы. Текст ниже – несколько сокращённая версия моего перевода ответа Quora.com, который дал Alon Amit (англ.).
Читать полностью

Немного теорий заговора. Сетевого уровня.

Маршрутизаторы – эффективное направление атак на сети, которые являются сегментами глобальной Сети. В подавляющем большинстве случаев, если “погасить” несколько умело выбранных маршрутизаторов, сеть падает полностью, несмотря на попытки резервирования, предпринятые при проектировании и построении сегмента. Хрестоматийная ситуация: резервные маршрутизаторы не справляются с изменившейся конфигурацией сети; причин может быть много разных – от возросшего трафика, до невозможности обмена управляющей информацией в результате возникших в сети “штормов”. Например, предполагается, что довольно давний случай с глобальной аварией сети в Сирии был вызван тем, что специалисты АНБ, во время операции по удалённому внедрению (обновлению?) программных закладок, случайно “уронили” ключевой маршрутизатор.

Интересно, как можно обнаруживать подобные действия?

Предположим, доверять маршрутизатору нет оснований, поэтому сразу считаем, что там есть закладки. Естественно, крайний вариант закладки – это продвинутый kill switch, срабатывающий по какой-нибудь последовательности в проходящих через маршрутизатор данных. Обнаружить его до срабатывания – чрезвычайно сложно, поэтому противодействовать не получится. Можно рассчитывать, что нет универсального “выключателя”, поэтому взамен вышедших из строя удастся быстро ввести новые маршрутизаторы. (Наличие подобного инструмента, конечно, вообще выглядит довольно фантастично. Тем не менее, совсем не рассматривать его тоже нельзя.)

С универсальным выключателем – мало что можно сделать. Но возможен более мягкий вариант: наличие несанкционированного удалённого доступа к маршрутизатору (через недокументированные возможности). Такой доступ позволяет управлять настройками и, скажем, выстраивать хитрые логические атаки. Каналы, реализующие доступ, могут быть хорошо замаскированы средствами стеганографии. Быстрый поток там не нужен, достаточно передавать несколько десятков коротких команд в минуту. Поэтому набор транспортов – радует свой широтой. Можно передавать биты “полезной нагрузки” в заголовках пакетов (TCP, IP, UDP и т.п. – выбирайте сами). Для этого нужно знать маршруты и располагать узлами, находящимися по разные стороны от контролируемого маршрутизатора: пакеты должны ходить через маршрутизатор, чтобы процессоры могли считывать недокументированные команды и отвечать на них. Естественно, можно ограничиться и отправкой пакетов только снаружи, лишь бы они достигали маршрутизатора, но вариант с трафиком, проходящим “через пару портов”, гораздо более привлекателен с точки зрения реализации недокументированных возможностей: во-первых, так проще реализовать скрытую обработку (из-за архитектуры маршрутизатора); во-вторых, больше способов отправить ответ. С ответами – вообще отдельная задача. Маршрутизатор не может просто так заменять какие-то параметры в заголовках, допустим, произвольных пакетов – велика вероятность ненамеренно испортить значимые данные, тем самым демаскировав всю операцию. Но зато специально выделенные пакеты – можно заменить (или сгенерировать) полностью, даже вместе с содержимым. Выделить пакеты для связи помогут ранее отправленные команды, сам пакет – будет передан узлом, находящимся за одним из портов, но данные в пакете заменяются маршрутизатором (пакет передаётся для того, чтобы не рисковать поднятием флагов во всяких системах учёта трафика, повсеместно внедрённых – они считают именно пакеты и иногда их длину; впрочем, перекос даже в один процент – вряд ли вызовет подозрения).

IP или, например, UDP, оказываются универсальными в силу того, что работают на общем для всех узлов IP-сети логическом уровне. При этом другие протоколы спускаются на несколько уровней ниже. Так, есть инструменты VLAN (виртуальные сети) и другие логические элементы, невидимые для IP. Связанные с ними протоколы также можно было бы использовать для передачи недокументированных сигналов. Однако из-за того, что свойства даже соседствующих сетей на соответствующих уровнях очень сильно разнятся, тут встречаются трудности. С другой стороны, можно представить ситуацию, когда использование расширений стандарта Ethernet (например) позволяет скрывать от анализаторов трафика, работающих параллельно маршрутизаторам, целый пласт ходящих по физической линии связи данных. Элементарный пример, понятный каждому: представим, что для анализа трафика используется обычный компьютер и Wireshark, но продвинутая сетевая карта – игнорирует часть пакетов, например, обнаружив в заголовке Ethernet некоторый заранее зашитый в процессор карты индекс (заметьте, что такое поведение аналогично штатной функции, позволяющей разграничивать VLAN-ы). Понятно, что Wireshark в таком случае не будет видеть часть трафика, и обнаружить, что видны не все пакеты, вряд ли получится. Конечно, пакеты могло бы прятать и ядро ОС, но аппаратная фильтрация сетевой картой – куда как более эффективна: зафиксировать передачу данных теперь можно только при помощи логического анализатора, подключенного непосредственно к проводам. А вот уже представить себе логический анализатор, который прячет сигналы, гораздо сложнее, чем только что описанную конфигурацию с продвинутой сетевой картой. Но многие ли мониторят сети при помощи логических анализаторов? (Вопрос даже не риторический, а скорее похож на шутку.)

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

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

И все те же параметры отдельного спутника – отлично подходят для создания орбитального радара. При этом, для решения SpaceX заявлена высокоскоростная связь между спутниками (судя по всему, речь вообще идёт об оптических каналах) и особое внимание уделяется точности определения положения спутников в пространстве (если там будут оптические каналы, то взаимное расположение можно измерять чрезвычайно точно). Это означает, что спутники смогут эффективно осуществлять согласованную обработку сигналов. Очевидно, что связь между спутниками является критическим параметром и в смысле обеспечения высокоскоростного доступа к Сети. А для гипотетического радара – это мощная платформа, позволяющая реализовать алгоритмы цифровой обработки сигналов и построить все мыслимые конфигурации радиолокационных систем. Если нужна бистатическая радиолокация, то одни спутники могут передавать зондирующий сигнал, другие – принимать его, корректируя результат на основе опорных данных, полученных по внутренней сети группировки. Предположим, что требуется синтезировать апертуру (это метод повышения чувствительности и разрешающей способности РЛС, заменяющий огромную физическую антенну на перемещение приёмника) – для этого тоже имеется отличный фундамент: есть точное общее время, известно положение всех приёмников в пространстве и приёмники-спутники постоянно движутся по довольно стабильным траекториям. Сложно придумать что-то лучше.

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