“Коммерсант” пишет про результаты соцопроса, которые связывает, ни много ни мало, с “уровнем научной грамотности” (“невысоким”).

“Как показал опрос ВЦИОМа, 35% россиян считают, что Солнце вращается вокруг Земли. О том, что Земля вращается вокруг Солнца, знает 61% респондентов.”

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



Комментарии (3) »

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

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

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

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



Комментарии (3) »

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



Комментировать »

Около года назад я кратко описывал возможную атаку на протокол биткойн, основанную на быстром вычислении дискретного логарифма при помощи квантового компьютера, что ломает подпись ECDSA. Вот, появилась весьма подробная научная публикация на эту же тему: Quantum attacks on Bitcoin, and how to protect against them – в работе рассматриваются и квантовые атака на алгоритм “доказательства проведённой работы” (PoW), они, впрочем, признаны неэффективными на практике.



Комментарии (1) »

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

Эти квантовые методы должны использовать какие-то свойства взламываемого шифра, которые хорошо проецируются именно на возможности квантовых вычислений. Пример. Предположим, что для для заданного шифра можно построить некоторую периодическую функцию, разбивающую всё пространство ключей на интервалы. Период этой функции может эффективно определить квантовый компьютер (это типичная задача, так, на поиске периода основан квантовый алгоритм Шора факторизации чисел). Знание периода позволяет путём анализа нескольких пар, состоящих из открытого текста и соответствующего ему шифротекста, определить, в какой именно из интервалов попадает секретный ключ, а дальше уже перебирать значения только из этого интервала, который, предположим, невелик. (Можно переформулировать: пусть обнаруживается период функции, определяющей возможные ключи – в таком случае, зная период, можно будет проверить только их, прыгая по значениям.) Пары открытых текстов и шифротекстов часто известны на практике. Скажем, HTTPS, использующий TLS в качестве транспорта, подразумевает передачу куки-файлов или известных заголовков запросов. При этом режим счётчика (GCM и пр.) основан на зашифровании последовательных значений. Это грубое изложение, но оно математически сходно с атаками, которые уже несколько лет обсуждаются в публикациях, применительно к различным режимам симметричных шифров.

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



Комментарии (1) »

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



Comments Off on Изогении кривых

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

Описание я планирую дополнять, потому что, несмотря на объём, охвачены ещё не все аспекты, которые хотелось бы рассмотреть. Сейчас в деталях рассмотрены такие ключевые моменты, как установление соединения (Handshake) и логика построения обмена сообщениями – это основа основ TLS. В ближайших планах: раздел, разбирающий современные шифры (в различных режимах работы), пояснения про использование криптографии на эллиптических кривых. Вероятно, будут исходники на С, поясняющие некоторые моменты реализаций. Конечно, нужен структурный путеводитель по RFC, имеющим отношение к TLS (их великое множество). Для того, чтобы получился полноценный тематический сайт я выделил проекту отдельный адрес: https://tls.dxdt.ru/. (Правда, пока там многое нужно оформить.)

Если есть какие-то поправки, уточнения, пожелания по новым темам (про что написать подробнее) – сообщайте, пожалуйста, либо мне почтой, либо в комментарии к этой записке.

Сам текст:

Ключи, шифры, сообщения: как работает TLS



Комментарии (12) »

BirdВ продолжение заметки про сеансовые ключи TLS, генерируемые по протоколу Диффи-Хеллмана (DH). Этот протокол, в классическом случае, работает на “обычной” конечной группе (современный вариант использует группу точек эллиптической кривой – см. ниже). Группа DH задаётся единственным числом – модулем. Это обязательно большое простое число. На практике веб-серверы так настроены, что используют ту или иную типовую группу (или типовой модуль, что эквивалентно). Модуль не является секретным. То есть, известна группа, используемая большинством веб-серверов, поддерживающих DH (для Рунета это более 60% веб-серверов). Эта группа является 1024-битной, что не так много.

Вся практическая полезность DH строится на сложности задачи дискретного логарифмирования (отыскания по известным A,G такого e, что A = G^e). Так вот, один из моментов, на который обратили внимание авторы атаки на TLS Logjam, состоит в том, что если у вас много ресурсов, то, в теории, для 1024-битной группы можно уже сейчас предвычислить её арифметические структуры, потратив пару лет работы суперкомпьютера и сохранив результаты в специальных таблицах. После этого вычислять дискретный логарифм можно достаточно быстро (за часы, а возможно, даже в режиме онлайн), особенно, если вы используете специальную многопроцессорную систему. Это означает, что можно расшифровать записанный ранее трафик TLS-сессий (а также других протоколов, использующих DH). Дело в том, что сеансовый ключ, если вы умеете отыскивать дискретный логарифм, элементарно вычисляется из ключа DH, который передаётся в открытом виде. Предвычислить нужную структуру можно только для известной группы, поэтому важно, чтобы TLS-серверы использовали типовые параметры. При этом, для тех, у кого ресурсов мало (кто не является специализированным агентством, например), группа остаётся вполне стойкой.

Лирическое отступление: как упоминалось выше, есть современная разновидность DH, работающая на группе точек эллиптической кривой – ECDH. Этот протокол также распространён в современных реализациях TLS. Из-за особенностей групповой операции на эллиптической кривой, отыскание дискретного логарифма в такой группе сложнее, поэтому, во-первых, можно использовать более короткие ключи, и, во-вторых, использовать общую кривую. На практике самый распространённый случай – кривая secp256r1, предлагающая 256 бит. Естественно, на ум сразу приходят теории о том, что АНБ известна пара-тройка секретных теорем, которые позволяют резко уменьшить вычислительную сложность дискретного логарифмирования на кривой secp256r1 (которая, кстати, в АНБ и сконструирована).

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



Комментарии (6) »

RailsВ работе исследователей, которые обнаружили уязвимость TLS Logjam, обсуждается возможность вычисления системами АНБ дискретного логарифма в некоторых группах, используемых в различных реализациях алгоритма Диффи-Хеллмана. (Задача дискретного логарифмирования, для правильно выбранных параметров, является вычислительно трудной, на этой трудности и основана практическая полезность протокола Диффи-Хеллмана.) Например, в решениях VPN, использующих IPsec (а это распространённая практика), для генерации общего ключа служат группы, заданные в рекомендациях (RFC). То есть, параметры известны заранее, это позволяет сильно ускорить процесс вычисления логарифма, выполнив предварительные вычисления.

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

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



Комментарии (5) »

Ops Measurment(Меня попросили простыми словами объяснить, как работают методы считывания секретных ключей через побочные излучения и наводки, например через измерение электрических параметров ноутбука, как продемонстрировано в недавней работе Genkin, Pipman, Tromer. Думаю, что описание достаточно интересно и для публикации на dxdt.ru, тем более, что в нём, на мой взгляд, есть наблюдения, полезные для понимания деталей работы современных реализаций RSA и принципов разработки криптографического ПО.)

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

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

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

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

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

Итак – секретной частью ключа RSA является расшифровывающая экспонента. Это целое число. Достаточно большое. В компьютерной памяти, естественно, оно представлено в двоичном виде. Операции с ним также осуществляются, грубо говоря, побитно – это одна из оптимизаций для быстрого умножения. После того, как исследователи определили, что можно различить исполняемые центральным процессором компьютера серии одних и тех же операций, измеряя потенциал на его корпусе, осталось найти такие зацепки в программном коде, которые позволили бы, на основе этих измерений, различать единицы и нули шифрующей экспоненты. Здесь и кроется основная задумка работы. Зацепки удалось найти в части кода GpuPG, осуществляющей умножение: здесь для 1 и 0 шифрующей экспоненты выбирались разные ветки кода, исполнение которых, при определённых условиях (см. ниже про шифротекст), оставляло разные следы в измеряемом канале утечки.

В RSA шифруемое/расшифровываемое сообщение также представляет собой большое целое число (по длине записи соответствующее длине ключа). При шифровании это число (сообщение) возводится в степень, соответствующую открытой экспоненте. Для дешифрования служит обратная, секретная экспонента. То есть, для того, чтобы наблюдать операции с секретным ключом, атакуемая система должна расшифровывать сообщения – возводить полученные числа в степень, используя соответствующий фрагмент кода GnuPG. А чтобы исследователи могли увидеть биты секретной экспоненты, нужно чтобы возводимые числа (а точнее – одно число) имели специальный вид. Использование специального шифротекста называется “атакой с подобранным шифротекстом”. В рассматриваемом случае – это основная зацепка: если система работает с другими шифротекстами, извлечь ключ описанным способом невозможно.

Подобранный шифротекст вовсе не обязан быть каким-то осмысленным сообщением. Это просто число. Значение этого числа подбиралось по параметрам открытого ключа RSA таким образом, чтобы при обработке внутри низкоуровневых функций GnuPG для нулевых битов секретной экспоненты получались промежуточные значения одного из операндов, содержащие в своем представлении большое число нулевых элементов (промежуточных произведений), а для битов секретной экспоненты, которые равны единице – нулевых элементов было бы мало. Это довольно тонкое наблюдение, очередной раз подтверждающее, что если реализация криптосистем в программном коде – штука, обладающая многими гранями сложности, то работа криптоаналитика с этими системами больше напоминает рыбалку: собирая снасти, никогда точно не знаешь, что поймаешь.

Выбрать правильный шифротекст, из-за особенностей реализации RSA, не представляло особого труда: подходит значение m – 1, где m = pq – модуль ключа, который, как известно, равен произведению двух простых чисел p и q. Значение модуля является открытым. (В секрете держится только разложение на p и q. Несмотря на то что, строго говоря, для расшифровывания сообщения нужно знать только расшифровывающую экспоненту, значения p и q сохраняются, чтобы в дальнейшем использовать их для оптимизации умножения при расшифровывании сообщений.)

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

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

И рекомендую почитать исходную работу (PDF).



Комментарии (2) »

Есть такой российский криптографический стандарт хэш-функции – ГОСТ Р 34.11-2012. На днях стартовал открытый конкурс научно-исследовательских работ, посвящённых анализу криптографических качеств этой хэш-функции. Популяризируют российскую (советскую) криптографию, и популяризируют, надо заметить, весьма кстати: сейчас второй полюс в мировом криптографическом инструментарии не помешает. При этом “гостовские” алгоритмы пока что сильно проигрывают более широко известным “западным” в степени исследованности академическим сообществом.

(Призы конкурса Streebog весьма приличные: первая премия – 500 тыс. руб.)



Комментарии (2) »