ksks7 (Техничная записка из области популярной криптологии, которая, думаю, будет полезна и на dxdt.ru.)

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

Если третья сторона записывает TLS-трафик, то вместе с ним сохраняются и данные, послужившие источником сеансовых ключей (в случае использования DH). Фактически, можно говорить о том, что эти ключи тоже сохраняются вместе с записанным трафиком. В этом и состоит тонкость, относящаяся к области различий между реально уничтоженными (или отсутствующими) и зашифрованными данными. Для восстановления ключей DH из записи трафика нужно обладать дополнительной информацией (либо уметь решать вычислительные задачи, которые сейчас считаются трудными). К такой дополнительной информации относится, скажем, состояние генератора псевдослучайных чисел, который использовался на стороне сервера (или клиента) при выработке сеансовых параметров DH.

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

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

Для детального понимания ситуации нужно рассмотреть следующий случай: предположим, что стороны, обменивающиеся данными в рамках защищённой сессии, используют заранее известный им разовый (относительно сессии) набор секретных сеансовых симметричных ключей и, скажем, AES. То есть, симметричные ключи не генерируются при помощи обмена в рамках DH, а известны заранее. По каналу связи они не передаются, канал не используется для их генерации. (Аутентификацию оставим за скобками.) Пусть используется добротный режим потокового шифрования: генерируется ключевой поток (гамма), совпадающей по длине с открытым текстом, а шифротекст является результатом операции XOR над открытым текстом и ключевым потоком. Примерно так работает GCM (аутентификацию мы договорились оставить за скобками) и всякий другой “режим счётчика”. Так как полученный ключевой поток будет, вообще говоря, вычислительно неотличим от псевдослучайной функции, то для записавшей трафик стороны ситуация окажется, условно говоря, семантически неотличима от абсолютно стойкого шифрования.

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

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

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



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

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

Из-за того, что в исходном документе содержится некоторая дополнительная структура, для восстановления не нужно перебирать все варианты перестановок. Так, если вы можете точно определить, что две данные полоски были (или не были) соседними (даже без выяснения правый или левый “сосед” обнаружился), то сложность восстановления всего документа из “лапши” не превысит n2. Занятно, что восстановление чистого белого листа оказывается более проблематичным, чем листа с текстом. Если, конечно, предполагать, что в качестве опорной структуры используется начертание букв и строк текста (или некий рисунок). С другой стороны, зачем восстанавливать чистый лист?

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

И, конечно, можно устроить шредер так, что восстановить документ будет невозможно: достаточно измельчать бумагу в труху, пусть и механическим способом.



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

Сейчас самый популярный хеш – 9ec4c12949a4f31474f299058ce2b22a. Это число, размещённое на официальной нашивке штатовского киберкомандования. С подачи Wired многие кинулись “расшифровывать” – что значит сей хеш? Быстро выяснилось, что это как бы всего лишь MD5 от официального “бюрократического” описания миссии киберкомандования (текст не привожу, его легко найти; уже сутки как вошло в “Википедию”). Вроде бы, уже официальные лица подтвердили, что, да, так и есть – использовался текст описания миссии, несекретный. Пресса пошумела в англоязычном секторе. Сейчас российская подхватит. Очень много блогеры пишут. В общем, грамотный PR, без дураков.

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

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

Вот.



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

К работающему на dxdt.ru сервису генерации картинок с формулами, записанными LaTeX (это нужно для удобного размещения формул в вебе), добавилась страница, на которой работает очень простой “редактор предложений”. Редактор пригодится для генерации строки с <img…> для вызова картинки. Редактор доступен (и, возможно, будет развиваться) вот по этому адресу: https://dxdt.ru/le/. Подробности о предмете – на странице “LaTeX в вебе“.

Пример использования:

Formula



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

Классический футбольный мяч шьётся по развёртке усечённого икосаэдра:

Фото: Sebastiano Calì

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

(Понятно, впрочем, что надутый мяч – не многогранник.)



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

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


Скажем, генератор случайных чисел, встроенный в ОС Windows, автоматически используется во всех приложениях системы, связанных с защитой информации. И при этом конкретные алгоритмы генерации, используемые в Microsoft для данной цели, никогда открыто не публиковались[…]

…аналитики нашли уязвимость, позволяющую организовать атаку, эффективно отыскивающую предыдущие состояния генератора, а значит, и вычислять будущие числа на выходе.”

Вот такие случайные числа, генерируемые, тем не менее, “алгоритмом” и, тем не менее, вычисляемые на будущее аналитиками. По-моему, кошмар.

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

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

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

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

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

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

Ссылка по теме: моя колонка про случайные числа на “Информационном буме”.



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

Кстати, первое опровержение известной гипотезы Эйлера насчёт обобщения большой теоремы Ферма появилось в 1966-ом:

1445 = 1335+1105+845+275

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



Comments Off on Эйлер и числа

Забавно (специально для arbuz.uz Скляревского):

31138+20128+19538+8618=28238+27678+25578+11288

Там же: 224955952840404+75924319813914+272397916926404=299998579386094

(via)



Comments Off on Числа

Между прочим, раз тут зашел разговор, то Том Хейлз (Thomas C. Hales), механистически разобравшийся в 1998 году со старинной задачей Кеплера о наиболее плотной упаковке сфер, поддерживает целый проект по обоснованию своего доказательства с помощью специального формализма.

Хейлз подтвердил правильность данного Кеплером решения, частный случай которого давно применяется продавцами круглых апельсинов и известен даже Чебурашке (укладка апельсинов пирамидой, практиковалась этим персонажем).

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

Компьютерным программным кодам нет доверия.

Это правильно.

Но Хейлз поддерживает проект под названием Flyspeck. Вообще-то, flyspeck – английское название для “мушиного помета”, но по версии создателей проекта это всего лишь слово из словаря, подходящее под маску /f.*p.*k/ (где FPK – Formal Proof of Kepler).

Цель проекта – получение программной реализации некоего компьютерного “формализма”, оперирующего не какими-то “алгоритмами” и “данными”, а строгими теоремами (там есть и тип данных – theorem). Таким образом, планируется получение виртуально строгого, но, вместе с тем, компьютерного, вычислительного доказательства. Попутно обещают выкинуть все интуитивное из всех доказательств вообще. Вот так. Объем работы – двадцать человеко-лет.



Комментарии (2) »
Навигация по запискам: