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

Уязвимости в области безопасности Интернета вещей приводят к возникновению бесчисленных угроз и атак, которые потенциально могут поставить под угрозу критически важные объекты инфраструктуры и даже национальную безопасность, вызвать физические и финансовые потери и многое другое. Ежеквартальный отчет компании McAfee об угрозах в сфере информационной безопасности сообщает, что каждую минуту появляется 176 новых киберугроз. Недавняя DDoS-атака на недорогие устройства Интернета вещей, основанная на Mirai-ботнете, за четыре месяца заразила более 2,5 миллионов устройств. Ожидается, что объем атак с использованием различных уязвимостей безопасности вырастет еще больше. На конец 2020 года большая часть из 26 миллиардов IoT устройств не предлагает адекватных мер безопасности для защиты от постоянно растущего пула кибератак и угроз. Кроме того, простота большинства веб-интерфейсов, использующихся в IoT устройствах, делает их довольно уязвимыми перед удаленными атаками. Несмотря на то, что были предложены эффективные методы повышения безопасности для сети устройств, большинство из них не подходят ввиду скромных вычислительных мощностей последних. Более того, большинство таких решений использует программное обеспечение, которое имеет свой собственный набор проблем и уязвимостей. Следовательно, крайне важно изучить и, если возможно, использовать аппаратную поддержку совместно с программой защитой устройств IoT, чтобы предотвратить непредвиденные угрозы.

Угрозы для устройств интернета вещей

Перед разработкой и внедрением защитных решений против различных атак на IoT устройства, очень важно понимать, какими возможностями обладает атакующий и какие цели преследует. Злоумышленник может получить физический доступ к простым и недорогим устройствам, регулярный мониторинг и постоянная защита которых не всегда может быть практически и финансово осуществимы. Физический контроль над такими устройствами открывает возможности для атак по сторонним каналам, включения аппаратных ошибок и троянов, а также замены поддельными устройствами. В этой статье мы рассмотрим лишь кибератаки, осуществляемые через программное обеспечение и сеть. Основной целью кибератак является искажение выходных данных (и последующих действий из-за неправильных данных) устройства, либо нарушение текущих процессов (отказ в обслуживании), либо раскрытие любой секретной информации, хранящейся на устройстве, такой как секретные ключи и пароли. Современные устройства собирают массивы данных о своих пользователях. Некоторым из них для работы требуется не только пароль, но и имя пользователя, его контактная информация, сведения о биографии. Такое количество информации требует надежной и качественной защиты, однако на данный момент IoT не может похвастаться защищенностью. Как показано на рис. 1, устройство IoT может подвергнуться атакам следующих типов:

Вредоносное ПО

Современные устройства Интернета вещей могут быть заражены различными вредоносными программами на разных этапах своей работы. В большинстве случаев вредоносное ПО (вирусы, трояны и черви) обычно нацелено на локальную эксплуатацию и эксплуатацию на уровне операционной системы в зависимости от сложности атаки и её выполнения. Основная задача вредоносного ПО заключается в том, чтобы нарушить текущие операции и перехватить контроль над устройством. Самым распространённым оружием злоумышленников являются руткиты (наборы утилит, которые хакер устанавливает на взломанном им устройстве после получения первоначального доступа, позволяющий хакеру закрепиться во взломанной системе и скрыть следы своей деятельности). Они предоставляют хакерам постоянный привилегированный доступ к системе, активно скрывая свое присутствие. Тем самым злоумышленник овладевает всей вычислительной мощностью и данными устройства, а также может размещать невидимые пользователям драйверы и службы. Кроме того, устройства Интернета вещей могут стать жертвой атак типа отказ в обслуживании (DoS) или распределенного отказа в обслуживании (DDoS), которые с каждым днем становятся серьезной проблемой. Такое уязвимое устройство может работать как бот (или зомби) для заражения других допустимых устройств в сети или потреблять пропускную способность сети и вычислительную мощность устройств, предоставляя злоумышленнику дополнительные ресурсы. Цифры дают возможность лучше оценить масштабы кибернетических атак на умные устройства. Сотрудники Лаборатории Касперского с начала 2019 года регистрируют хакерские атаки на умные девайсы с помощью ханипотов спецприманок для хакеров. Им удалось зафиксировать более 105 миллионов атак на IoT-устройства, которые производились с 276 тысяч уникальных IP-адресов.

Раскрытие закрытого ключа

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

Программно-управляемый ввод неисправностей

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

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

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

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

Аппаратные методы безопасности

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

Использование аппаратных средств безопасного создания ключей шифрования

Одним из основных требований для выполнения защищенной информационной транзакции между устройствами IoT через ненадежную сеть является использование надежной и безопасной схемы управления ключами и обработки данных на оборудовании. В этом отношении хорошо зарекомендовали себя Trusted Platform Module (TPM- название спецификации, описывающей криптопроцессор, в котором хранятся криптографические ключи для защиты информации, а также обобщённое наименование реализаций указанной спецификации). Такие TPM позволяют использовать криптографические ключи, которые могут быть привязаны к определенным параметрам платформы и защищены от раскрытия любым другим ненадежным аппаратным компонентом, процессом или программным обеспечением. Микросхемы с дискретным TPM (dTPM) и модули пластиковых печатных плат могут предложить больший охват услуг, позволяя совместно использовать ресурсы между несколькими приложениями на одной физической машине. Кроме того, архитектуры с поддержкой ARM TrustZone и Intel Software Guard Extension (SGX) добавляют новые функции в современные SoC (system on a chip), предоставляя надежную и безопасную среду для выполнения критически важных для безопасности процессов, даже несмотря на то, что привилегированное ядро и программное обеспечение потенциально вредоносны. С другой стороны, криптозащищенные процессоры, такие как AEGIS и Ascend, используют однокристальную архитектуру для обеспечения частной и аутентичной обработки с зашифрованным и запутанным выполнением инструкций. Однако такие конструкции в основном обеспечивают защиту от физических атак, таких как вмешательство и зондирование внутренних компонентов, и не обеспечивают защиту от киберугроз в случае компрометации самой программы.

Микроархитектурный мониторинг событий

Хотя TPM и прочие системы криптографической устойчивости предлагают надежную среду для приложений, чувствительных к безопасности, такое оборудование, как правило, дорогое, энергоемкое и не подходит для легких и недорогих IoT устройств. Кроме того, вредоносные программы, такие как вирусы, трояны и боты, могут незаметно заражать устройства в обход таких систем, если сеть недостаточно защищена. Непосредственно после заражения очень сложно обнаружить вредоносное ПО, так как оно может обойти антивирусные программы на устройстве. В таких случаях может помочь аппаратный мониторинг событий микроархитектуры и SIEM-системы(Security information and event management). Он предлагает тонкую фильтрацию для отдельных запусков, может собирать многомерную информацию и обеспечивает более быстрый отклик, чем программные аналоги для защиты от вредоносных программ.

Сердцем таких аппаратных мониторов являются блоки мониторинга производительности (PMU), доступные в современных процессорах и SoC.Основная цель PMU - предоставить представление о производительности ЦП путем регистрации набора микроархитектурных событий и соответствующих подсчетов с помощью встроенных аппаратных счетчиков производительности (HPC). Например, один или несколько HPC в PMU могут определять, сколько раз заранее определенное событие (разрешенное соответствующей архитектурой), такое как промахи кэша, происходит во время выполнения программы, что служит для оценки производительности тестируемой системы. PMU в архитектурах ARM и Intel x86 можно управлять через программные модули, такие как Linux Perf tool. Он предоставляет обратную связь в режиме реального времени для диагностики ошибок или выявления узких мест в программном обеспечении . Первоначально PMU был разработан для мониторинга производительности, но его также разумно использовать в SIEM-системах, что существенно ускоряет обработку инцидентов, связанных с информационной безопасностью, а также помогает обнаруживать атаки и другие угрозы для элементов инфраструктуры. Еще одно преимущество состоит в том, что, будучи интегрированной частью оборудования, PMU работает прозрачно для любого программного обеспечения, запущенного на процессоре, и не может быть обмануто внешним вредоносным ПО. То есть сам аппаратный монитор не обращает внимания на процессы. Поскольку любое вредоносное ПО или даже модифицированная прошивка или руткит должны выполнять определенные действия, мониторинг событий PMU потенциально способен обнаруживать такие вредоносные действия.

Разработчики из NYU Polytechnic School of Engineering, Brooklyn, New York, USA предложили основанную на хосте структуру обнаружения DDoS-атак под названием BRAIN (BehavioR based Adaptive Intrusion detection in Networks). Он использует аппаратные функции для моделирования безопасного поведения и DDoS-атак. Чтобы обнаружить DDoS-атаки, он использует методы машинного обучения для моделирования поведения приложений и сетевой статистики. Поскольку корреляция между статистикой сети и приложений с данными HPC нетривиальна, необходимо выбирать аппаратные события с высокой точностью. Авторы предложили реализовать интегрированный механизм обнаружения DDoS-атак (DDoSDE), который отслеживает поведение как оборудования, так и сети. Интерфейс предотвращения DDoS-атак (DDoSPI) реагирует на любую обнаруженную атаку, занося IP-адреса в черный список (и удаляя при необходимости) на основе динамической сети и порогового значения на основе HPC, тем самым мешая злоумышленнику изучить критерии и политики безопасности устройств.

Повышение безопасности с помощью методов машинного обучения

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

• Выбор высокоточных микроархитектурных функций для сбора событий с помощью высокопроизводительных вычислений

• Выбор эффективных методов машинного обучения для задач классификации и регрессии

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

1. Сбор данных

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

2. Анализ данных

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

3. Приём решения

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

Модуль обнаружения уязвимостей периодически получает информацию HPC от целевого модуля, на котором работает ненадежная программа или вредоносное ПО. Архитектура системы должна позволять модулю обнаружения работать с наивысшим уровнем привилегий и независимо от любой другой программы. Кроме того, она должна предоставлять доступ к физической памяти для хранения данных HPC и иметь изолированную память, чтобы сам модуль обнаружения не был поврежден. Объем памяти, необходимый для хранения данных машинного обучения, сильно различается в зависимости от типа классификатора, используемого для анализа, что требует дополнительной места в памяти и вычислительной мощности. Как можно понять, точность используемого метода машинного обучения и детальное разрешение дискретизированных данных HPC для выбранных событий играют жизненно важную роль для повышения точности и производительности всей системы обнаружения.

С целью повышения эффективности связки HPC +ML был проведён всесторонний анализ с использованием информации о высокопроизводительных вычислениях во время их выполнения. Он показывает, что программная реализация различных методов машинного обучения на уровне ядра ОС является чрезвычайно медленной, в диапазоне миллисекунд, что достаточно велико по сравнению со временем выполнения вредоносного ПО и выборки данных на аппаратном уровне. Очевидно, что методы классификации на уровне программного обеспечения недостаточно подходят для сбора данных и обнаружения аномалий с высокой степенью уверенности. Следовательно, для более низкой задержки и более высокой точности требуется аппаратная реализация метода машинного обучения. Для этого ML специалисты предоставили свои решения, реализуемые на аппаратных платформах, таких как Virtex 7 для сравнительного анализа. Было обнаружено, что метод OneR был наиболее эффективным классификатором доброкачественных и вредоносных программ с самой высокой точностью и наименьшим использованием вычислительной мощности, а общий успех обнаружения составил около 81%.

Дизассемблеры уровня инструкций на основе побочных каналов

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

Широко известен такой класс киберугроз, как атака по сторонним каналам. Такие атаки нарушают конфиденциальность криптосистем, используя информацию о протекающих физических процессах в устройстве, например измеряя время выполнения операции, вольт-амперные характеристики, электромагнитное излучение устройства и так далее. Злоумышленники, собирая достаточное количество статистических данных, после определенного анализа могут предположить, какой алгоритм используется в криптосистеме, получить доступ к секретным ключам или внести изменения в алгоритм. Таким образом, злоумышленник с легкостью обходит защиту и овладевает IoT устройством. Но почему бы не использовать данную уязвимость во благо? С тем же самым успехом можно обнаружить, выполняет ли IoT устройство подозрительные инструкции, является оно "зараженным" или нет. Достаточно всего лишь зафиксировать какое-либо физическое отклонение в поведении устройства.

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

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

Будущее развитие

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

1. Существующее надежное и безопасное оборудование, такое как TPM, обычно требовательно в плане энергопотребления и состоит из множества компонент. Таким образом, адаптация таких устройств и архитектур по принципу plug-and-play не подходит для легких устройств IoT, где процессор менее мощный, а размер устройства и энергозатраты ограничены.

2. Методы обнаружения вредоносных программ на основе контроля производительности устройства во многом основаны на эффективных и сложных методах машинного обучения, позволяющих различать допустимые и вредоносные операции. Однако такие методы обычно реализуются в программном обеспечении, где данные HPC собираются на оборудовании и передаются в программу для обработки и обнаружения в режиме онлайн / офлайн. Это, к сожалению, создает узкое место в схеме обнаружения, поскольку программная классификация очень медленная по отношению к накопленным аппаратным данным. Это заставляет выборку событий/данных выполняться с гораздо меньшей частотой, повышая риск того, что вредоносные события или исполнения останутся незамеченными. В конечном итоге это снижает вероятность успеха и увеличиваетоперационные издержки.

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

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

Аппаратные решения в области информационной безопасности для устройств IoT прекрасно дополняют существующие программные механизмы защиты. Ключевым направлением исследований может быть создание аппаратных ускорителей для высокоскоростных реализаций машинного обучения на одном чипе с прочим оборудованием. Разработка упрощенных методов машинного обучения также имеет решающее значение для обнаружения вредоносных программ / аномалий на основе распознавания событий. В дополнение к PMU для обеспечения безопасности могут использоваться различные встроенные датчики, такие как датчики температуры, а также новые архитектуры.

Заключение

С появлением устройств Интернета вещей и приложений, ориентированных на Интернет вещей, крайне важно предоставить надежную и безопасную платформу для этой сферы, чтобы обеспечить максимальную защиту от существующих и будущих кибератак. Большинство существующих решений не подходят, поскольку такие методы защиты не обеспечивают широкого и надежного покрытия. Следовательно, необходимо использовать как аппаратные, так и программные решения гибридным образом. Аппаратная защита устройств Интернета вещей доказала свою эффективность и универсальность. Однако нет сомнений в том, что необходимы дальнейшие исследования в области разработки соответствующих механизмов безопасности для легких приложений IoT.

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

Дело в том, что в отличие от обычных блокчейн-проектов, где в транзакции явно указано, какая монета тратится из какого кошелька, в прайваси блокчейнах используются разные способы запутывания следов. Одними из первых, кто занимался решением этой задачи, был проект CryptoNote, в котором была реализована схема с кольцевой подписью. Такая схема, вместо явного указания на транзакцию-источник монет, позволяет включить в подпись группу из случайных транзакций, не связанных с этим переводом. Таким образом, сторонний наблюдатель не догадывается, из какой именно транзакции-источника на самом деле берутся деньги. Известно только, что отправитель доказал свое право владения одной из них. Такие подмешанные транзакции называются mixins или decoys, а их количество определяет так называемый anonymity set.

Самым узнаваемым проектом, построенным на базе CryptoNote, на сегодняшний день является Monero. За последние несколько лет участники этого проекта внедрили целый ряд улучшений, скрыли значения сумм переводов, а также усовершенствовали саму подпись. Тем не менее, существенной проблемой остается размер подписи и ее производительность, которые линейно зависят от количества элементов кольцевой подписи или же от размера кольца, и это накладывает определенные ограничения на уровень анонимности (на момент написания статьи, в Monero по умолчанию используется anonymity set 10).

В настоящее время, в рамках проекта Zano мы работаем над созданием такой подписи, в которой зависимость ее размера от количества decoys была бы логарифмической, что в свою очередь позволило бы нам значительно увеличить anonymity set, и, следовательно, повысить уровень приватности. Несколько месяцев назад у Anton Sokolov возникла интересная идея по реализации такой подписи , и после того, как он ее сформулировал и опубликовал ее базовые теоретические аспекты, мы решили объединить усилия, Антон присоединился к нашей команде и сейчас мы активно изучаем возможности построения технологии на базе этой подписи.

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

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

Конкурс в баре

В городе есть бар. Горожане, посетители бара, обладают хорошим вкусом и всегда могут отличить на вкус один напиток от другого. Под напитками понимаются смеси разных компонентов, например, рома, водки, вина, фруктовых соков и т.п. Два напитка считаются одинаковыми, если процентное соотношение всех компонентов в одном из напитков равно процентному соотношению всех компонентов в другом напитке. В противном случае, напитки считаются разными.

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

Для того, чтобы не отходить далеко от канвы математических рассуждений, представим себе, что в баре есть устройство, позволяющее смешивать напитки в определенных пропорциях. Например, в устройство можно вставить по бутылке водки и рома (или две емкости с какими-либо другими напитками), указать пропорцию 449/17, и получить на выходе емкость с напитком, содержащим 449 единиц водки на 17 единиц рома. Также в баре есть генератор случайных равномерно распределенных пропорций от 1/100000 до 100000/1. Конструкции устройства смешивания и генератора пропорций открытые, в правильности их работы никто не сомневается. Также, для полноты картины, в баре есть электронный дегустатор, которому на вход наливают два напитка, и у него загорается зеленая лампочка, если напитки одинаковые, и красная, если напитки разные. Электронный дегустатор никогда не ошибается, это могут подтвердить все жители города.

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

Шаг 1: Итак, игра начинается с того, что участник ставит на свой стол бокал, помеченный буквой Z, с напитком, известным только ему. Участнику известны соотношения компонентов напитка в этом бокале, т.е. он знает рецепт приготовления содержимого Z, но держит этот рецепт в секрете. Известно только то, что согласно условиям, участник должен добавлять в Z и цитрус, и алкоголь. Вдобавок, участник ставит на стол второй помеченный H1 бокал с некоторым выбранным им самим содержимым, рецепт приготовления которого может быть ему как известен, так и неизвестен, т.е. участник волен налить в бокал H1 все что угодно.

Шаг 2: бармен получает пропорцию с11 от генератора случайных пропорций, смешивает ром и водку в этой пропорции и ставит на барную стойку бокал R1 с полученным алкогольным напитком. Затем, бармен получает пропорцию с13 от генератора случайных пропорций, смешивает лимонный и апельсиновый соки в этой пропорции и ставит на барную стойку бокал R2 с полученным цитрусовым напитком. Все посетители бара, включая самого участника, видят значения с11 и с13, а также то, что бармен готовит содержимое бокалов R1 и R2 из указанных компонентов и в указанных пропорциях.

Шаг 3: участник, зная пропорции с11 и с13, берет по части содержимого своих бокалов Z и H1 и смешивает их в некоторой определяемой им пропорции r1, и ставит на стол третий бокал S1 c полученной смесью. Участник может показать значение r1 всем, включая бармена, хотя бармену оно неинтересно. Все, включая бармена, следят только за тем, чтобы в бокале S1 была смесь только содержимого из Z и H1. Затем, участник каким-то образом готовит содержимое четвертого бокала H2 и ставит его на стол. Участник может показать всем, как он готовит содержимое H2, а может и не показывать. В бокал H2 участник волен налить все что угодно и в каких угодно пропорциях, и даже, как и в бокал H1, налить совершенно неизвестную жидкость.

Шаг 4: бармен получает пропорцию с2 от генератора случайных пропорций, смешивает содержимое бокалов R1 и R2 в этой пропорции и ставит на барную стойку бокал R с полученным алкогольно-цитрусовым напитком. Все видят пропорцию с2, а также то, что содержимое R честно получено в этой пропорции из содержимого R1 и R2.

Шаг 5: участник, зная теперь еще и пропорцию с2, смешивает содержимое бокалов S1 и H2 в некоторой определяемой им пропорции r2 и наливает результат в пятый бокал S2, который ставит на стол. Все следят за тем, чтобы в S2 было налито только содержимое бокалов S1 и H2.

Шаг 6: электронному дегустатору наливают из бокалов R и S2. Если загорелась красная лампочка, то игра заканчивается ничем, участник платит за использованные напитки. Если загорелась зеленая лампочка, то процедура валидации считается пройденной.

Теперь проводится финальная проверка: участник сообщает всем рецепт, т.е. компоненты и процентный состав содержимого своего бокала Z. Бармен готовит указанный состав и открыто сравнивает его на электронном дегустаторе с остатками содержимого в бокале Z, тем самым позволяя всем убедиться в том, что участник правильно назвал рецепт содержимого Z. Если участник дал неправильный ответ, то игра заканчивается ничем, участник платит за использованные напитки. Если же согласно рецепту оказалось, что в бокале Z присутствуют одновременно алкоголь и цитрусовый сок, то участник выигрывает и забирает себе всю выпивку с полок бара, которой там много.

Иными словами, в этой игре процедура валидации составлена владельцем бара так, чтобы участник не смог подобрать нужные соотношения смесей для получения аналога R при условии, что в бокале Z присутствуют компоненты обоих смесей, а именно: крепкий алкоголь (ром и водка) и цитрусовые (лимонный и апельсиновый сок). Зеленая лампочка никогда не загорается при сравнении R и S2, если в Z находится, например, смесь ром-апельсиновый сок или ром-водка-лимонный сок, или же водка-лимонный-апельсиновый сок, и т.д. Вернее, в таких случаях она может загореться только с пренебрежимо малой вероятностью, и владелец бара, который немного шарит в математике, об этом знает.

Для посетителей бара это может быть неочевидно, они рассуждают приблизительно так: допустим, мы не будем добавлять в бокал Z никаких других компонентов кроме рома, водки, лимонного и апельсинового соков, потому что если мы добавим что-то еще, например, молоко, то оно обязательно будет присутствовать в S2 и, таким образом, в S2 всегда будет что-то, отличающееся от R. Но если мы нальем в Z, например, ром и лимонный сок, то зная c11, c13, c2 и обладая возможностью выбирать содержимое H1, H2 и пропорции r1, r2, мы всегда сможем уравновесить состав S2 так, чтобы он стал идентичной версией R.

Таким образом, посетители бара начинают участвовать в конкурсе, стараясь обмануть процедуру валидации. Но, увы, никто из них не способен подобрать H1, а затем и r1 и H1 в ответ на c11 и c13, затем r2 в ответ на c2 так, чтобы составы S2 и R оказались одинаковыми, если в Z присутствуют в ненулевых пропорциях алкоголь и цитрусовый сок.

Со временем становится понятно, что если налить в бокал Z, например, только алкоголь, т.е. смесь рома и водки, налить в H1 чистую водку, затем подобрать r1 так, чтобы в S1 получилось то же самое, что и в R1, а в H2 налить лимонно-апельсиновую смесь в пропорции c13, то в S2 можно легко получить то же самое, что и в R.

Часть 2

Видя угасающий интерес к игре, владелец бара объявляет о том, что теперь, если игра не закончилась на пятом шаге процедуры валидации, то финальная проверка будет более мягкой. Теперь финальная проверка будет следующей: если доказано, что в бокале Z находится только алкоголь, то достаточно предоставить доказательство того, что в одном из бокалов H1 или S1 присутствует цитрусовый сок, и тогда участник выигрывает. Если же доказано, что в Z находится только цитрусовый состав, то достаточно предоставить доказательство того, что в одном из бокалов H1 или S1 присутствует алкоголь, и тогда участник тоже выигрывает.

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

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

Ну уж теперь, казалось бы, процедуру валидации и облегченную проверку можно будет обойти и выиграть. Однако, по-прежнему никто не в состоянии подобрать H1, затем r1 и H1 в ответ на c11 и c13, затем r2 в ответ на c2 так, чтобы составы S2 и R оказались идентичными, если в Z, H1 и S1 присутствует что-то, отличающееся либо от чистой смеси рома и водки, либо от смеси лимона и апельсина.

Часть 3

Процедура валидации, придуманная владельцем бара, похожа на криптографическую схему Lin2-Xor леммы в драфте на eprint. Заметив это сходство, горожане интересуются, почему смеси напитков в бокалах ведут себя как элементы циклической группы простого порядка, где discrete logarithm problem is hard, или даже как точки основной подгруппы криптографической кривой ed25519, используемой в системе Zano?

Ответ прост: при условии наличия генератора анти-напитков, смеси напитков в бокалах обладают теми же свойствами, что и точки основной подгруппы кривой ed25519. Вернее, у точек на ed25519, конечно же, больше интересных свойств, но свойства, используемые в Lin2-Xor лемме, те же самые.

Поэтому, если кто-то из участников конкурса все-таки сможет выиграть всю выпивку с полок, это будет подразумевать опровержение Lin2-Xor-леммы.

Каким образом такие чистые напитки, как ром, водка, лимонный и апельсиновый соки в емкостях у бармена соответствуют точкам (элементам группы) P1, Q1, P2, Q2 в условии леммы? Точки P1, Q1, P2, Q2 обязаны быть такими, чтобы ни одна из них не являлась линейной комбинацией (смесью) других из этого же набора. Это достигается путем применения идеальной хэш-функции на точках кривой. То же самое проделываются и с базовыми напитками. Например, лимонный сок не должен получаться путем смешивания рома, водки и апельсинового сока в любых, в том числе и отрицательных пропорциях.

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

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

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

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

Является ли сравнение напитков на электронном дегустаторе сравнением точек на равенство? Почти, только с тем отличием, что электронный дегустатор менее критичен к напиткам, чем проверка на равенство. Электронный дегустатор не чувствителен к объему напитков на входе, т.е. в терминах точек он сравнивает две точки с точностью до какого-то известного числа, на которое одна из них умножается. Таким образом, дегустатор не уменьшает шансы участников на обман процедуры верификации по сравнению с использованием чистой проверки на равенство для точек.

Часть 4

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

Процедура валидации теперь немного удлиняется. Вместо двух первых шагов, на которых, с одной стороны, бармен генерирует случайные пропорции вначале (с11, с13), а затем с2, и, соответственно, смешивает базовые напитки, а с другой стороны, участник составляет вначале пропорцию и бокал (r1, H2), а затем пропорцию r2, и смешивает свои напитки, теперь происходят три шага. Со стороны бармена эти три шага выглядят как генерация (с11, с13), затем (с21, с23), затем с3, и, соответственно, смешивание. Co стороны участника три шага выглядят как составление (r1, H2), затем (r2, H3), затем r3, и смешивание.

При этом оказывается, что процедура валидации пропускает только указанные выше четыре смеси, и непонятно, как ее можно обмануть. Более того, если у бармена будет шестнадцать базовых напитков и он будет генерировать (с11, с13), (с21, с23), (с31, с33), с4, а участник будет генерировать (r1, H2), (r2, H3), (r3, H4), r4, то процедура валидации будет пропускать только восемь смесей пар базовых напитков. Таким же образом можно использовать 32 базовых напитка, 64, 128 и т.д., и получать одну из, соответственно, 16, 32, 64 смесей пар напитков. Это протокол Lin2-Selector леммы.

Вернемся к точкам на криптографической кривой. Если взять, скажем, 1024 базовых точек, объединенных в 512 пар, то протокол Lin2-Selector леммы позволяет выбрать линейную комбинацию точек из ровно одной пары, не пропуская никакие другие точки или комбинации. При этом требуется порядка log(1024) шагов, т.к. каждое удвоение базового набора точек требует прибавления одного шага в процедуру верификации.

Если провести аналогию с Merkle Tree, то, не вдаваясь в детали реализации, там так же, для доказательства принадлежности некоторого элемента к некоторому фиксированному множеству элементов требуется создать журнал шагов. Основное отличие состоит в том, что в Merkle Tree мы обязаны раскрыть тот элемент, для которого мы доказываем принадлежность к фиксированному множеству. В протоколе Lin2-Selector леммы мы достаточно легко можем хорошо скрыть тот элемент, для которого мы доказываем принадлежность к множеству.

В терминах игры в баре, корень Merkle Tree представляет из себя подобие бокала R, приготавливаемого барменом, хотя действия бармена для Merkle tree отличаются. А доказательство принадлежности напитка в стакане Z множеству базовых напитков представляет из себя последовательность из log числа бокалов H1, H2, H3, . При этом для Merkle tree критически важны как состав содержимого бокалов, так и точный объем содержимого. В то же время, для протокола Lin2-Selector леммы объем содержимого бокалов не важен, важны только пропорции компонентов. В случае с Merkle Tree обойтись одними пропорциями никак нельзя.

Постойте, но ведь Merkle tree это не интерактивная структура данных, а протокол Lin2-Selector леммы и конкурс в баре - это интерактивные игры между двумя участниками, как же в таком случае сравнивать не интерактивную структуру с интерактивной игрой? Сравнивать можно, дело в том, что в криптографии многие интерактивные игры переводятся в неинтерактивные с помощью приема, называемого эвристикой Фиата-Шамира. Это настолько широко применяемый прием, что мы на нем не будем останавливаться, и рассматриваем неинтерактивную и интерактивную версии протоколов Lin2-Xor и Lin2-Selector одновременно. Т.е. мы сравниваем неинтерактивную версию протокола Lin2-Selector леммы и неинтерактивное Merkle tree.

Согласно Lin2-Selector лемме, чтобы скрыть элемент множества, доказывающий предоставляет не сам элемент множества, а этот элемент умноженный на какой-то секретный скаляр, а также предоставляет доказательство для него. Т.е. доказывающий предоставляет не тот конкретный бокал с апельсиновым соком, который у него есть, а, скажем, 1/379 этого бокала, и держит число 1/379 в секрете. А хорошо ли это скрывает апельсиновый сок в бокале? Ну, конкретно апельсиновый сок это не скрывает никак, но если ме говорим о точках криптографической кривой, то скрывает абсолютно, также, как например публичный ключ полностью скрывает приватный ключ. Это обусловлено тем свойством криптографической кривой, что discrete logarithm problem is hard на ней.

Может возникнуть логичный вопрос, зачем нужны пары элементов? Пары элементов нужны только для того, чтобы применять Lin2-Xor и Lin2-Selector леммы, это техническая необходимость. Мы делаем один из элементов в каждой из пар таким, чтобы доказывающий не мог его смешивать с другими элементами, это легко сделать. К слову, этот технический элемент только добавляет анонимности.

Как сказанное выше соотносится с линкинг тегом, не забыли ли мы про него? А линкинг тег формата CryptoNote (совсем немного модифицированный) нам только помогает, т.к. если смешать этот линкинг тег с публичным стелс-адресом, то у нас получается как раз линейно независимый базовый элемент, который нам нужен в Lin2-Xor и Lin2-Selector леммах. Чтобы получить log-size ring signature, мы составляем базовые элементы кольца именно таким образом, а затем отправитель анонимно доказывает, что он знает приватный ключ одного из этих элементов.

Заключение

Надеюсь, вам понравилась статья. Ну а если кто-то заметил ошибки тут или в самой работе, пишите нам - мы всегда рады оппонентам!