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

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

Понятно, что стандартизованная постквантовая криптосистема может оказаться уязвимой для классического криптоанализа (и, скорее всего, так и выйдет). При этом, несмотря на прижившиеся штампы в СМИ, пока никто не продемонстрировал, как именно можно было бы реализовать алгоритм Шора с полиномиальной сложностью, что называется, в железе. Потому что те немногие эксперименты с числом 15 или чуть большим числом, на которые ссылаются много лет, в принципе не позволяют проверить ключевую часть реализации алгоритма – квантовое преобразование Фурье.

Тем не менее, пробовать построить квантовый компьютер хотя бы на 2^1024 состояний – это полезно.



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

На скриншоте ниже – график частотности слова delves в текстах корпуса 2019 года по версии полезного сервиса Google Ngrams (период: 1800 – 2019 годы, английский язык):

Delvs and a graph

Английское delve означает “копать”, “рыть”, но и “рассматривать” – в значении “тщательно разбирать и изучать предмет, исследовать”. Форма delves здесь специально, это не опечатка – см. ниже.

Вообще, delve – родное для современного английского языка слово, однако редкое даже для классического литературного английского (который существенно отличается и от разговорного, и от “академического” – см. ниже). Тем не менее, в контексте “исследований” delve встречается в комедии Шекспира The Tragedie of Cymbeline: “I cannot delve him to the root”. У Диккенса можно найти в A Tale of Two Cities, но тоже придётся покопаться: “men and women here, to dig and delve”. В общем, слово выразительное (это нормально для английского, который больше аналитический), а для “академического языка”, если только речь не о языкознании, может быть признано слишком выразительным. (Delves – это ещё и фамилия. Нельзя забывать и delve into.)

Вернёмся к графику, на котором, – для delves, – отлично виден рост, но, если обратить внимание на вертикальную шкалу, общая доля не слишком велика. (Оси к сожалению, в Google подписывать не умеют, что, как бы, существенно снижает доверие к результату, тем более, что не подписывают не только оси, но и шкалы, да и сами графики; всё же, воспользуемся этим вариантом.)

Выбор слова и вся эта предыстория могут показаться странными, – пусть и позволяют поставить тег “Лингвистика“, – однако в свежей научной работе (препринт [*]) по пикам на графиках частотности слов определяют влияние ChatGPT и прочих LLM на текстовый состав аннотаций научных (опять же) работ. И delves там используется непосредственно, см. второй скриншот:

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

В работе исследована статистика слов из аннотаций (“абстрактов”) научных публикаций PubMed – около 14 млн “абстрактов” за период с 2010 по 2024 год (представьте, кстати, сколько научных работ публикуется ежегодно; и это ещё LLM только начали разворачиваться). Выделены “резкие скачки” на графиках по некоторым словам, что связывается с влиянием использования ChatGPT и других LLM, которые могли быть задействованы при подготовке текстов. Действительно, LLM, являясь синонимайзерами переростками, выводят редкие слова в генерируемый текст, часто – невпопад. Но вот почему может быть верным обратное утверждение, – что “выбросы” редких слов в аннотациях свидетельствуют о “вмешательстве” LLM, – из исходной работы не очень понятно (кроме, конечно, указания на странное совпадение по времени). Предположим, кто-то из авторов прочих публикаций использовал новое слово в статье. Другие авторы, которым слово понравилось, тоже стали его использовать. На графике Google (с неподписанными осями) delves резко растёт ещё с 1981 года – свидетельствует ли это о возвращении дополнительных произведений Диккенса в школьную программу (в Англии, конечно)? Не факт, но всякое может совпасть по времени. Естественно, корпус сервиса Google Ngrams отличается от выборки PubMed, это тоже понятно.

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

Необходимо, впрочем, признать, что авторам исходной работы совсем не чужд профильный юмор. Цитата:

We hope that future work will meticulously delve into tracking LLM usage more accurately and assess which policy changes are crucial to tackle the intricate challenges posed by the rise of LLMs in scientific publishing.
(Смысла переводить нет, потому что это, очевидно, аллюзия к общей теме работы: “meticulously delve”, “tackle the intricate challenges” и др.)


[*] Dmitry Kobak, Rita González Márquez, Emőke-Ágnes Horvát, Jan Lause;
Delving into ChatGPT usage in academic writing through excess vocabulary
arXiv:2406.07016



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

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

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

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

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

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

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

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



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

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

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

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



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

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

Цитата:

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



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

В марте довольно много писали про новую атаку на SHA-256, “с обнаружением коллизий”. Вообще, тут нужно отделять академические атаки от практики, условно говоря, всяких биткойнов: в исходной работе (“New Records in Collision Attacks on SHA-2”, Li, Liu, Wang) речь идёт про академические атаки на урезанную “функцию сжатия” (см. ниже) из состава SHA-2 (SHA-256 – это разновидность SHA-2), да ещё и со специально подобранным предыдущим состоянием. Это общепринятый подход к исследованию стойкости хеш-функций, результат существенно лучше предыдущих достижений, но нужно учитывать, что он не обязательно приводит к практической атаке на полную хеш-функцию. В статье сказано именно про “практическую атаку”, это верно, однако это разная “практика”.

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

После каждого раунда, блок, в результате применения преобразований, изменяется и потом снова подвергается тем же преобразованиям, которые опять изменяют блок. Эта комбинаторная часть позволяет добиться нужного разрежения для отображения входных блоков в выходные значения. Штатная схема SHA-256 использует 64 раунда в функции сжатия. Атака, о которой идёт речь, работает для 39 раундов (обратите внимание: с подобранным начальным состоянием – это очень важный момент).

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

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

Естественно, обнаружение точек совпадения для уменьшенного количества раундов нередко даёт инструменты для взлома всей хеш-функции целиком. Именно поэтому академические атаки на примитивы с урезанным количеством раундов – важнейший инструмент. Однако, является ли тот факт, что коллизия найдена для более чем половины количества раундов, автоматической гарантией успешного применения того же метода к, предположим, половине оставшейся половины? Нет, совсем не является. Методы тут развиваются, так сказать, полностью “нелинейно”, так что непреодолимое вычислительное препятствие может возникнуть хоть бы и на каждом следующем раунде – потребуется полностью переделать метод атаки. Собственно, это очередное улучшение атак на SHA-2 как раз построено на новых методах, если сравнивать с теми методами, которые использовали для атак на MD5 и пр.

Конкретный пример, взятый из исходной работы: для 39 раундов SHA-256, при заданном начальном состоянии, получаются совпадающие значения для разных входных блоков (выдача программы, прилагаемой к работе):

431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d
431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d

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

d33c0cff 17c9de13 21f528f0 3362e217 563f1779 521a1b9c df062e86 19fb5973 
105d6c34 43ceb0ad 120ba1a0 3362e217 d6dd86e0 7da567b5 cf1ca736 19fb5973

Это, ещё раз, никак не уменьшает ценности результата для 39 раундов, но показывает, что для полной SHA-256 всё, – пока что, – хорошо.

Криптографические хеш-функции отображают сообщения произвольной длины в блоки фиксированной длины, так что, математически, коллизии там есть по определению. Другое дело, что если хеш-функция хорошо отображает множество входных текстов в, скажем, 2^256 выходных значений, то о коллизиях “на полном переборе” можно не особенно задумываться: мало кто может создать и записать даже 2^128 текстов. Атаки с обнаружением точек совпадения в функции сжатия как раз, потенциально, выявляют дефекты отображения, которые могут позволить найти коллизии без необходимости полного перебора. А возможно, что и позволят найти способы решения гораздо более сложной задачи вычисления прообраза, – то есть, подбора входного текста по значению хеш-функции.



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

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

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

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

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

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

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



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

Цитата из моей недавней статьи, опубликованной в журнале “Интернет изнутри”:

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

(Я писал об этом на dxdt.ru тоже, конечно.)



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

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

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

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

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

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

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



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

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

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

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



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

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

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

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

(Update, 04/01/2024: пример успешного переключения “шампанского” и “хлопчатобумажного” на примере GigaChat.)



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