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

Поскольку браузеры, – в том числе, самый свежий Firefox, – перешли с Kyber768 на ML-KEM, я добавил на свой тестовый сервер TLS поддержку X25519MLKEM768 (не удаляя “гибриды” с Kyber768). Проверить можно при помощи новых версий браузеров Chrome и Firefox.

Кстати, немного занимательных элементов. В процессе развития постквантовой криптографии в TLS уже успели поменять “порядок байтов”. Так, в новых версиях представлений гибридных ключей – разная конкатенация массивов: в “старом” X25519Kyber768, если смотреть в сетевом порядке (так сказать, слева направо, что, конечно, математически неверно), сначала идёт ключ X25519, а потом – Kyber768; в “новом” X25519MLKEM – наоборот, сначала данные ML-KEM, а потом – X25519.

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

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

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

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

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

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

(Между прочим, с философской точки зрения, весь туман вокруг LLM и решения задач некоторым образом напоминает странные, – но популярные, – объяснения того, что “сумма всех натуральных чисел”, якобы, равна -1/12, использующие аналитическое продолжение дзета-функции Римана или что-нибудь подобное; но это уже тема для совсем другой записки.)

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

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

На замену GPS/GNSS в авиации уже предлагают использовать “прочие”, сопутствующие, радиосигналы, в том числе, GSM, и, – что не совсем обычно, – сигналы разных других спутниковых систем (то есть, не GNSS): статья The Register. В качестве исследовательской платформы в статье по ссылке выбран шар-метеозонд, снабжённый радиоприёмным оборудованием.

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

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

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

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

Занятная задача про эльфов Толкина, цифры и системы счисления попалась в канале Бориса Трушина. Условие дано в виде скриншота (подсказок в этой записке нет – смело читайте, а ответы как-нибудь потом опубликую (update 24/10/24: верное решение дал Nataraj в комментариях)):

Скриншот тут необходим потому, что Unicode не справится. Точнее – не справятся установленные шрифты: как раз тот случай, когда использование Unicode выглядит весьма разумным (не то что в IDN), но не все мыслимые эльфийские цифры внесены в официальные таблицы и типовые шрифты.

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

Очередная атака “про Spectre”, позволяющая, в частности, читать память произвольных процессов в Linux, и на Intel, и на AMD. Пусть в этот раз речь в публикации не про новые аппаратные особенности, а про исправления в старых особенностях, но я всё же сошлюсь на свою записку о неустранимости подобных дефектов аппаратуры.

(Подробная статья на OpenNET.)

В массовом TLS для веба криптосистемы с постквантовой стойкостью уже имеются, но есть ещё немало направлений, где такие криптосистемы нужны (если учитывать “угрозу квантовых компьютеров”, конечно). И во многих случаях требуются не криптосистемы согласования симметричного секрета, как в случае внедрения ML-KEM для TLS, а криптосистемы подписи. Можно, например, посмотреть в сторону DNS и DNSSEC, пусть последняя и не очень-то распространена, но там требуется именно электронная подпись. В DNS всегда приветствовались короткие пакеты данных, без излишнего раздутия. В предлагаемых сейчас постквантовых криптосистемах, традиционно, ключи и/или подписи – очень большие. Как это будет упаковываться в DNS – пока что не очень понятно: десять, предположим, килобайт на подписи с ключами – для DNS это слишком много.

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

Длины ключей/подписей в текущем состоянии постквантовой криптографии и “квантовых вычислений” тема довольно странная: с одной стороны, как оно могло бы преобразовываться на “квантовом компьютере” не ясно, но если исходить из того, что для RSA нужна тысяча “квантовых элементов” компьютера на один бит ключа, то и для RSA можно просто добавить несколько килобит, получив практическую постквантовую стойкость – в конце концов, стойкость к обычным атакам для RSA развивалась именно так: 512-битный ключ сейчас можно факторизовать достаточно быстро для того, чтобы практическую разрядность передвинули к 2048 битам. С другой стороны, нет никаких гарантий того, что для задач, лежащих в основе уже стандартизованных постквантовых систем, тоже не найдут эффективных квантовых алгоритмов.

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

Естественно, длина ключей постквантовых подписей диктуется и скоростью работы на практических компьютерах, и требованиями стойкости к атакам на этих практических классических компьютерах: улучшат такие атаки – разрядность (в том или ином виде) придётся увеличивать, вне зависимости от того, появились уже подходящие квантовые компьютеры или нет (собственно, посмотрите на тот же ML-KEM – бывший Kyber, – там уже сейчас несколько вариантов с разной классической стойкостью).

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

Занятная работа, удивительным образом не укладывающаяся в мейнстрим “про ИИ” и показывающая на конкретной статистике и конкретных примерах, что ИИ-LLM не “рассуждают”, а лишь генерируют текст, даже “решая” задачки начальной школы: GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models.

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

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

Пример из работы (всё в переводе с английского):

Предлагаемая задача (“сбивающее” добавление выделено):
Оливер собрал 44 киви в пятницу. Затем он сорбрал 58 киви в субботу. В воскресенье он собрал в два раза больше киви, чем в пятницу, но пять из них были немного меньше среднего. Сколько киви у Оливера?

Ответ с “объяснениями” LLM o1-mini:
Оливер собирал киви в течение трёх дней следующим образом:
– пятница: 44 киви;
– суббота: 58 киви;
– воскресенье: в два раза больше, чем он собрал в пятницу, то есть 2*44 = 88 киви.
Однако, в воскресенье 5 из этих киви были меньше среднего. Мы должны вычесть их из общего количества для воскресенья: 88 (киви в воскресенье) – 5 (мелкие киви) = 83 киви. Теперь, суммируя киви за все три дня: 44 (пятница) + 58 (суббота) + 83 (воскресенье) = 185 киви. У Оливера всего 185 киви.

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

(Новостная статья на ArsTechnica.)

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

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

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

Более того, поскольку одна задача (Kyber) не переводится быстро в другую (ECDH), то можно предположить не только появление специального квантового алгоритма для эффективного взлома Kyber, но и то, что квантовый компьютер, реализующий этот алгоритм, окажется (согласно некоторой теории) построить проще, чем не менее квантовый компьютер для алгоритма Шора. А что? Теоретические аналоговые вычислители они на то и теоретические, и аналоговые, что это сейчас только различные оценки количества “квантовых элементов” для практической атаки на RSA расходятся на несколько десятичных порядков, а на следующем шаге – могут разойтись и оценки достижимости по новым и старым алгоритмам.

Неочевидные особенности веб-TLS в Интернете. Посмотрим на сертификат узла dxdt.ru, а точнее на разные таймстемпы, присутствующие в этом сертификате, выпущенном удостоверяющим центром (УЦ) Let’s Encrypt. Так, время в SCT-метках: Sep 4 20:35:05 2024 GMT (миллисекунды я не указываю), а начальная граница интервала валидности сертификата: Sep 4 19:36:35 2024 GMT. То есть, время меток позже почти ровно на один час. Как такое могло бы получиться? Естественно, вариант тут только один: УЦ Let’s Encrypt выпускает сертификаты, сдвинув время начала действия на час назад. То есть, что называется, “задним числом” (backdate), но только на один час. Реальное время заказа сертификата ближе к таймстемпу из SCT-метки – понятно, что данный УЦ не мог ждать один час, чтобы отправить пресертификат в лог. Тем не менее, это означает, что сертификат “действовал” за час до того, как его заказали.

Это известная особенность, неоднократно упоминавшаяся в обращениях в Let’s Encrypt. Её традиционно объясняют необходимостью учитывать возможные неточности часов у клиентов: то есть, сертификат выпускается за секунды и должен заработать мгновенно, но если у клиентского компьютера отстают часы, то он покажет ошибку, так как в сертификате время стоит позже момента валидации по “сдвинутым часам”.

Почему достаточно одно часа? Не ясно. Возможно, из-за летнего/зимнего времени. Возможно, из-за того, что в 60 минут укладывается бо́льшая часть обычного “дрейфа” локальных часов (она, конечно, укладывается минут в двадцать, но почему бы не взять один час?).

Как это коррелирует с тем, что в SCT-метке всё равно стоит актуальное время, которое оказывается “в будущем” и валидатор всё равно мог бы заругаться? Ну, наверное, эффект остался с тех пор, когда никакие SCT-метки в сертификаты не ставились, к тому же, опережение на час находится в допустимом интервале и валидаторы браузеров не пугает: лишь бы подписи сходились.

Означает ли это, что Let’s Encrypt выпускает пресертификаты (для добавления в CT-лог) “с упреждением”? Вряд ли. Но проверить это нельзя: технически, УЦ может какие угодно сертификаты у себя штамповать, на то он и УЦ. Выпуск пресертификата без факта его заказа и подтверждения прав управления DNS-именем – будет являться грубейшим нарушением принятых правил, но (пре)сертификат ещё должен утечь. Тем не менее, какого-то смысла в подобных фокусах не просматривается.

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

Ещё одна из Британских заморских территорий, а именно – территория в Индийском Океане (IO, то есть), – должна перейти к другому государству (Республика Маврикий), а это вызывает опасения относительно перспектив домена верхнего уровня io. Домен весьма известный, конечно. В статье по ссылке в качестве примера приводят домен Советского Союза – su. Этот домен продолжает работать в глобальной DNS, но, действительно, история очень похожая: государства нет, а национальный домен – есть. История очень похожая, но не точно такая же: всё же, при всём уважении, сравнивать историческое наследие СССР и данной Британской территории – довольно сложно: весовые категории разные. С другой стороны, в зоне .io гораздо больше имён зарегистрировано, и среди этих имён есть весьма важные. Наличие работающих имён в доменной зоне является хорошим аргументом в сторону её сохранения. (Я в su размещаю, например, nox.su – он про DNSSEC.)