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

(Заметка первоначально опубликована в Facebook, 19/05/2020.) Я вот так устроил, что один сервис, проверяющий TLS, использует специально сконструированное сообщение ClientHello TLS 1.3 (см. скриншот) с посланиями внутри. Небольшая хитрость состоит в том, что там не только поля SessionID и ClientRandom с сообщениями, но и ключ для Диффи-Хеллмана (ECDH) на кривой P-256 – с посланием. Ключ – это два числа, но они должны задавать точку кривой, и хорошие реализации TLS проверяют, что ключ принадлежит кривой. Конечно, вычисление второй координаты Y по известной X-координате – никакой проблемы не составляет, но пришлось урезать пару символов, так как число приводится по порядку базового поля. У тех, кто знаком с ECDH, сразу возникнет вопрос – решил ли я попутно задачу дискретного логарифмирования для P-256? Но нет (а если бы решил, то сообщил бы об этом более занятным способом). Дело в том, что реально в этом сканере общий секрет не нужен, поэтому ответный ключ сервера просто игнорируется. (Конечно, вряд ли кто-то ещё это всё видит в трафике. Но при отладке – помогает.)

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

Руны входят в таблицы Unicode. (“Обобщённые” символы Unicode тоже называют рунами, но в нашем случае – речь про конкретное подмножество, про англосаксонские руны.) Используемое кодирование (представление Unicode) занимает по три байта на каждую руну. При этом для записи 40 битов (пять байтов) в Base32 используется 8 символов: каждый символ несёт пять битов, откуда, собственно, число 32 == 2^5. То есть, получается, что Base32 на основе рунического письма в Unicode превращает пять байтов исходных данных в 24 байта (восьмибитных) закодированного текста. Не очень-то экономно. Оригинальный вариант Base32, построенный на латинском ASCII-алфавите и ASCII-цифрах, даёт результат лучше: пять байтов кодируются восемью байтами (если при кодировании текста используется привычное, 8-битное, представление байта). Но руны выглядят интереснее, что подтверждается скриншотом ниже, на котором запечатлён TLS-сертификат, записанный в runic32.

Примеры использования утилиты, написанной на Go, приведены на странице репозитория Runic32 в GitHub.

“В магазин привезли два ящика с апельсинами. В каждом ящике – пять апельсинов. Сколько всего апельсинов привезли в магазин?”. Эта задача для начальной школы, а точнее – обсуждение её требуемого способа решения, как выясняется, несёт с собой много занимательных трактовок. Задача существует в различных вариантах (“диваны/подушки”, “полки/книги” и пр.), а её решение с постоянством обсуждается “в интернетах” уже несколько лет. Обсуждение вращается вокруг следующего момента: вариант решения “5*2 == 10” – учитель признаёт неверным; требуется решать так: “2*5 == 10 (апельсинов)”, поскольку в первом варианте “получаются ящики, а не апельсины“. Возможна и иная трактовка, в которой левое умножение заменяется правым, но для нас это не важно, поскольку причина бурных обсуждений состоит в том, что результат вообще зависит от порядка множителей. Почему-то считается, что это невозможно, поскольку умножение в натуральных числах коммутативно. Вообще, если отвлечься от неясных вопросов преподавания в начальной школе, то задача, взятая вместе с методикой решения, оказывается связанной с интересными аспектами математики и их проекцией в привычный опыт.

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

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

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

Распространённое конструктивное возражение такое: у нас же даны не апельсины, а “апельсины на ящик”. Да, это весьма разумный довод, опирающийся на введение некоторого понятия “размерности”. Действительно, умножаем число с размерностью “апельсины/ящик” на число с размерностью “ящик”, “ящики” сокращаются – получаем искомые апельсины, вне зависимости от порядка множителей (операндов). Это очень привычно (м/сек., кг/м² и др.), поэтому мало кто замечает, что введение такой “размерности” подразумевает построение некоторой дополнительной теории. Почему при умножении “апельсины/ящик”*”ящик” – сокращаются именно “ящики”? Что такое “сокращаются”? А можно ли записать наоборот “ящик/апельсины”? Заметьте, что привычное деление, которое приходит тут на ум, мало того, что легко выводит за пределы натуральных чисел, так ещё и является некоммутативной операцией! (В алгебре деление вообще не рассматривают в “повседневном” смысле, а только умножение на обратный элемент. В частности, поэтому в натуральных числах универсального деления, в строгом смысле, просто нет. Что, конечно, никак не запрещает утверждать, что оно там всё же имеется, поскольку 12/3 == 4.) Другими словами, для того, чтобы реализовать коммутирующее преобразование типов при помощи только что описанного понятия “размерности”, потребуется принять некоторые вспомогательные соглашения, например, что a/b*b == a, и ситуация не отличается от соглашения про выбор типа правого (или левого) операнда.

Почему же в исходной задаче выбирается именно правый (или левый) операнд в качестве носителя типа результата? Сложно сказать точно, тут возможны варианты. Одно из объяснений следующее: пусть умножение вводится как “повторное сложение”, тогда один из операндов задаёт количество шагов такого сложения. В случае апельсинов и ящиков, ящики разбивают некоторое подразумеваемое множество апельсинов на подмножества, используя отношение “быть в ящике”, а правила записи и преобразования предписывают “разбивающий тип” указывать слева, а в качестве типа результата – использовать тип правого операнда. Ну, или наоборот – тут можно и запутаться. Тем не менее, это позволяет достаточно строго, достаточно простым образом (используя минимум дополнительных понятий) построить универсальный механизм решения, который будет работать и для апельсинов в ящиках, и для подушек на диванах, и для книг на полках. Конечно, эти правила должны быть согласованы, прежде чем можно ставить задачу. Но если они согласованы, то попытка умножения 5 (апельсинов) на 2 (ящика) действительно даст в ответе 10 ящиков, сколь бы странным и неудобным это ни показалось. (Неудобным – потому что засовывать ящики в апельсины довольно сложно.)

Представьте гипотетический язык программирования, в котором предложения { 2 + “3” } и { “2” + 3 }, после преобразования компилятором, дают разные результаты: первый вариант – строку “23”, а второй – число 5. Исходя из рассмотренной выше задачи, нетрудно догадаться, почему такое происходит. Дело в том, что компилятор не только выполняет неявное преобразование типов, но ещё и “подгоняет” операции. В качестве главного типа компилятор выбирает тип правого операнда, приводя левый операнд к нему. Поэтому, в предложении { 2 + “3” } числовой тип двойки преобразуется в строку из символа “2”, а операция сложения превращается в конкатенацию (некоммутативная операция, кстати). Да. Не очень-то удобно, не то что апельсины по ящикам.

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

Мастер-водитель

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

Экономия топлива

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

Маршрутное разнообразие

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

Винтажное такси

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

Для хипстеров

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

(Продолжение следует.)

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

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

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

Пишут, что Windows Update некоторое время раздавал весьма странный патч для Windows 7. Так, описание обновления представляет собой строку символов, которая практически неотличима от тех псевдослучайных последовательностей символов, которые получаются у разработчиков, когда они наобум пробегают по клавиатуре пальцами – ну, вместо того, чтобы набрать какой-нибудь типовой тестовый текст, типа “This is not a virus”.

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

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

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

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

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

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

Попробовал придумать, как всесильное АНБ могло бы использовать вычислительную мощность сети биткоин (которую, в таком случае, агентство само и продвигает, незаметно) в своих целях. Напомню, что майнеры биткоинов вычисляют SHA-256, подбирая аргумент под заданное значение. Результат SHA-256 от входного сообщения (заголовка блока транзакций) должен быть меньше заданного в сети числа. Подбор заголовка и составляет сложность. Казалось бы, какой от этого толк криптологии?

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

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