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

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

Понятно, что в статье обнаружатся ошибки и она потребует, как минимум, уточнений. Так, сегодня опубликована записка (Omri Shmueli), указывающая на недостижимые значения параметров, которые использованы в доказательстве корректности алгоритма. Это, впрочем, только добавляет арифметической занимательности, поскольку доказательство недостижимости основано на оценке количества простых чисел, меньших заданного. Дело в том, что описанная версия алгоритма, для корректной работы, требует построения набора из некоторого количества попарно простых натуральных чисел, меньших заданного порогового значения – но для определённых значений параметров таких чисел может не найтись в нужном количестве, поскольку не хватит простых. Если алгоритм нельзя исправить (это ещё тоже не факт) и это удастся доказать, то может даже так оказаться, что постквантовая стойкость криптологических задач теории решёток зависит от количества простых чисел, меньших заданного порога. А это весьма сильное и интересное ограничение. (Но, конечно, вряд ли это так.)



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

Воскресное чтение манускриптов. В одной из прошлых записок по теме рассматривался текст варианта записи труда Клеомеда “Учение о круговращении небесных тел” (13 в., Adv.MS.18.7.15), с описанием метода, применённого древним греком Эратосфеном для определения размеров Земли. В этот раз – посмотрим на тот же фрагмент текста Клеомеда, где указана длина окружности в стадиях, но в записи другого манускрипта: Pal. gr. 018 (часть Cleomedes, Cyclia/Caelestia) – из библиотеки Гейдельбергского университета. (Далее эти два манускрипта здесь называются просто Pl (Pal. gr. 018) и MS.)

Итак, Pl – манускрипт начала 14 века на древнегреческом, здесь нет чертежа, как в MS, а в записи, кроме такого же “скорописного” стиля, использовано множество сокращений (см. ниже), так что выглядит всё ничуть не менее загадочно, чем вариант из предыдущего MS (хоть тот и 13 века). Новый скриншот:

Manuscript Screenshot

Подчёркнута (зелёным) строка, в которой и указана длина окружности Земли по меридиану – двадцать пять мириад. В предыдущем варианте, то есть в MS, строка, сообщающая о расчётной длине меридиана в 250 тыс. стадиев, если символы перевести в современную типографику, выглядит так: “ὁ ἄρα σύμπας κύκλος γίνεται μυριάδων εἴκοσι πέντε” . Но на скриншоте манускрипта Pl запись отличается. Вот два варианта на одной картинке (вверху – Pl, а внизу – та же строка из MS, см. прошлую записку по теме):

Fragments

Думаю, что “ὁ ἄρα” – теперь нетрудно прочитать, как и лигатуру σύ со “смайликом”, построенным на диерезисе. Остальное, конечно, читается сильно сложнее. Однако, когда два варианта выставлены рядом, становится очевидно, что для опытного читателя, – возможно, инквизитора, – зашедшего в средневековый скрипторий, тут всего лишь два почерка, отличающихся в некоторых привычных деталях. Кроме, разве что, последних слов фрагмента.

Manuscript, fragment

Дело в том, что на манускрипте Pl слова “εἴκοσι πέντε” из записи “двадцати пяти” – отсутствуют (самый конец верхней строки). Вместо этого число 25 записано древнегреческими цифрами, вот так: κε – что и обозначает 20 (κ) + 5 (ε).



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

В журнале “Интернет изнутри” опубликована моя статья “Постквантовая криптография и практика TLS в браузерах”. Статья, в основном, про то, как “квантовые вычисления” связаны с теоретико-информационной криптографией, и как это влияет на TLS в архитектурном смысле, но также рассмотрен свежий пример с Kyber768 в браузере Chrome.

Цитата:

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



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

Скриншот из издания “Элементов” Евклида на английском (первый перевод, Henry Billingsley), 1570 год. Кстати, настоящий язык Шекспира: whereunto и пр. Автором “Элементов”, как нетрудно прочитать, здесь обозначен Евклид из Мегары, а не просто Евклид (то есть, Евклид из Александрии); это, впрочем, обычное, – пусть и немного загадочное, – дело для старых публикаций.

Euclid Elements, Title



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

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

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

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

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



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

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

Manuscript Screenshot, Siege Engine

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



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

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

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

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

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

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

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



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

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

Ниже приведён скриншот манускрипта конца 13 века (Adv.MS.18.7.15, древнегреческий) из коллекции Национальной библиотеки Шотландии (в коей библиотеке электронные архивы, как и дистанционный доступ к ним, пока что сохраняются). Фрагмент, на минуточку, относится к переписанной грамматиком Планудом (скорее всего) работе философа Клеомеда, в которой пересказан метод определения периметра большого круга Земли (длины меридиана), использованный древним греком Эратосфеном. Плануд переписал труд Клеомеда в 13 веке (результат – на скриншоте), а исходный труд Клеомеда, как предполагается, относится к периоду с первого по четвёртый век н. э., а вот сам Эратосфен выполнял описанные геометрические расчёты на рубеже третьего и второго веков до н.э. То есть, тут, примерно, полторы тысячи лет, в ходе которых Земля описывается как круглая (круглая Земля, заметьте, тоже может перевозиться большой черепахой, но это другая история).

Cleomedes

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

Исходя из расстояния от Сиены до Александрии (по большому кругу) в 5000 стадиев, Эратосфен определил общую длину меридиана в 250 000 стадиев – соответствующая строка манускрипта выделена зелёными метками (середина скриншота): “ὁ ἄρα σύμπας κύκλος γίνεται μυριάδων εἴκοσι πέντε” – так будет в современной типографике, но в манускрипте записано с кучей скорописных сокращений (и прочих “смайликов”), поэтому на современные начертания букв не очень-то похоже. Само число, кстати, указано как двадцать пять мириад (μυριάδων, двадцать – εἴκοσι, пять – πέντε). Двадцать пять мириад стадиев, – то есть, примерно, от 44 до 52 тыс. км, – неплохо соответствует современным оценкам в сорок тысяч километров.



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

Современные компиляторы хорошо умеют оптимизировать машинный код и обычно делают это гораздо лучше разработчика. Но нужно учитывать тот факт, что программа на некотором языке высокого уровня (ЯВУ) – это не алгоритм, а только запись алгоритма. Соответственно, компилятору принципиально доступны лишь структуры, нашедшие отражение непосредственно в записи, но не сам алгоритм. Один и тот же алгоритм вообще можно записать многими способами и на разных языках. Так что компилятор, в процессе перевода с входного ЯВУ на машинный язык, оптимизирует языковые конструкции. Компилятор не видит алгоритм и не может его оптимизировать. Разработчик, в теории, способен оптимизировать именно алгоритм, это следует из того, что разработчик как раз “переводит” (записывает) алгоритм на ЯВУ (но, конечно, лишь в том случае, если код пишется не силами очередного ИИ/LLM/ChatGPT, выстраивающего “токены” в псевдомарковскую цепь). Поэтому иногда нужен ассемблер.

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

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

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



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

Воскресное чтение манускриптов. В этот раз – небольшой скриншот манускрипта Barb.gr.580 (древнегреческий, видимо, 11 или 12 век) из Ватиканской Апостольской библиотеки. На скриншоте небольшой фрагмент одного из комментариев (тридцать второго, если точнее) Иоанна Златоуста к Евангелию от Матфея. Этот фрагмент, заканчивающийся узнаваемым сочетанием слов – “учителями и врачами”, – содержит сразу несколько занятных сокращений, которые распространены в манускриптах соответствующего типа и периода.

Vat.Barb.Gr.580

Например, можно видеть упоминавшийся недавно на dxdt.ru “греческий амперсанд“, начертание которого здесь практически совпадает с лигатурой ϗ из Unicode. Это сокращённая запись слова καί, на скриншоте – четвёртая снизу строка, справа, отмечено красной стрелкой. Сокращённая запись сотрудником скриптория использована в конце строки, а в других случаях, рядом, καί вполне себе записывается полностью.

Пара других примеров труднодоступной для чтения скорописи отмечены в конце первой строки скриншота: левее – скорописью записано φησὶν (“говорит”), а следующее загадочное сочетание лигатур – это ἐπει в ἐπειδή (“когда”, “после того как”).



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

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

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

Picture of Glen Canyon Dam

(Изображение: Glen Canyon Dam, Wikimedia.org)



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