Метод "Отруби и Веяние" в Криптографии

Введение

Криптографический метод

Chaffing and winnowing — это криптографический метод для обеспечения конфиденциальности без использования шифрования при передаче данных по незащищенному каналу. Название происходит из сельского хозяйства: после сбора урожая и обмолота зерно остается смешанным с несъедобной волокнистой шелухой. Затем шелуха отделяется от зерна путем веяния, и шелуха выбрасывается. Этот криптографический метод был разработан Роном Ривестом и опубликован в онлайн-статье 18 марта 1998 года. Хотя он имеет сходство как с традиционным шифрованием, так и со стеганографией, его нельзя отнести ни к одной из этих категорий. Этот метод позволяет отправителю отрицать свою ответственность за шифрование сообщения. При использовании chaffing and winnowing отправитель передает сообщение незашифрованным, в открытом виде. Хотя отправитель и получатель располагают общим секретным ключом, они используют его только для аутентификации. Однако третья сторона может обеспечить конфиденциальность их связи, одновременно отправляя специально сформированные сообщения по тому же каналу.

Как это работает

защищенный каналзащищенный каналАлиса→Чарльз→Бобсоздает 4 пакета, каждый из которых содержит один бит ее сообщения и допустимый MAC Серийный номер Бит MAC 1 1 234 2 0 890 3 0 456 4 1 678добавляет 4 пакета-обманки с инвертированными битами и недопустимым MAC, выделенные курсивом (chaffing) Серийный номер Бит MAC 1 0 321 1 1 234 2 0 890 2 1 987 3 0 456 3 1 543 4 0 765 4 1 678отбрасывает пакеты с недопустимым MAC для восстановления сообщения (winnowing) В этом примере Алиса хочет отправить сообщение "1001" Бобу. Для упрощения предположим, что все четные MAC являются допустимыми, а нечетные – недопустимыми. Отправитель (Алиса) хочет отправить сообщение получателю (Боб). В простейшей конфигурации Алиса нумерует символы в своем сообщении и отправляет каждый из них в отдельном пакете. Если символы достаточно сложны, например, текст на естественном языке, злоумышленник может отличить реальные символы от плохо подделанных символов-обманок, что создает проблему, аналогичную стеганографии, требующую генерации высокореалистичных подделок; чтобы избежать этого, символы можно свести к отдельным битам 0/1, а реалистичные символы-обманки можно просто генерировать случайным образом в соотношении 50:50, делая их неотличимыми от реальных символов. В общем случае метод требует, чтобы каждый символ прибывал в порядке и был аутентифицирован получателем. При реализации в сетях, которые могут изменять порядок пакетов, отправитель помещает серийный номер символа в пакет, сам символ (в незашифрованном виде) и код аутентификации сообщения (MAC). Многие MAC используют секретный ключ, которым Алиса делится с Бобом, но достаточно, чтобы у получателя был способ аутентификации пакетов. Ривест отмечает интересное свойство chaffing и winnowing: третьи стороны (например, интернет-провайдер) могут оппортунистически добавлять их к сообщениям без необходимости получения разрешения или координации с отправителем/получателем. Третья сторона (названная "Чарльзом"), которая передает пакеты Алисы Бобу, перемешивает пакеты с соответствующими ложными пакетами (называемыми "chaff") с соответствующими серийными номерами, произвольными символами и случайным числом вместо MAC. Чарльзу не нужно знать ключ для этого (реальные MAC достаточно велики, чтобы вероятность случайной генерации допустимого MAC была крайне мала, в отличие от примера). Боб использует MAC для поиска подлинных сообщений и отбрасывания пакетов-обманок ("chaff"). Этот процесс называется "winnowing" (просеивание). Перехватчик, расположенный между Алисой и Чарльзом, может легко прочитать сообщение Алисы. Но перехватчик между Чарльзом и Бобом должен будет определить, какие пакеты ложные, а какие реальные (то есть выполнить просеивание, или "отделить зерна от плевел"). Это невозможно, если используемый MAC безопасен и Чарльз не предоставляет никакой информации о подлинности пакетов (например, через временные задержки). Если к примеру присоединится четвертая сторона (названная Дартом), которая захочет отправить поддельные сообщения, выдавая себя за Алису, это потребует от Алисы раскрыть свой секретный ключ. Если Дарт не сможет заставить Алису раскрыть ключ аутентификации (знание которого позволит ему подделать сообщения от Алисы), то ее сообщения останутся конфиденциальными. Чарльз, с другой стороны, не является целью Дарта, поскольку он даже не обладает секретными ключами, которые можно было бы раскрыть.

secure channelinsecure channelAlice→Charles→Bobconstructs 4 packets, each containing one bit of her message and a valid MAC Serial Bit MAC 1 1 234 2 0 890 3 0 456 4 1 678adds 4 chaff packets with inverted bits and invalid MAC, shown in italics (chaffing) Serial Bit MAC 1 0 321 1 1 234 2 0 890 2 1 987 3 0 456 3 1 543 4 0 765 4 1 678discards packets with invalid MAC to recover the message (winnowing)In this example, Alice wishes to send the message "1001" to Bob. For simplicity, assume that all even MAC are valid and odd ones are invalid. The sender (Alice) wants to send a message to the receiver (Bob). In the simplest setup, Alice enumerates the symbols in her message and sends out each in a separate packet. If the symbols are complex enough, such as natural language text, an attacker may be able to distinguish the real symbols from poorly faked chaff symbols, posing a similar problem as steganography in needing to generate highly realistic fakes; to avoid this, the symbols can be reduced to just single 0/1 bits, and realistic fakes can then be simply randomly generated 50:50 and are indistinguishable from real symbols. In general the method requires each symbol to arrive in order and to be authenticated by the receiver. When implemented over networks that may change the order of packets, the sender places the symbol's serial number in the packet, the symbol itself (both unencrypted), and a message authentication code (MAC). Many MACs use a secret key Alice shares with Bob, but it is sufficient that the receiver has a method to authenticate the packets. Rivest notes an interesting property of chaffing and winnowing is that third parties (such as an ISP) can opportunistically add it to communications without needing permission or coordination with the sender/recipient. A third party (dubbed "Charles") who transmits Alice's packets to Bob, interleaves the packets with corresponding bogus packets (called "chaff") with corresponding serial numbers, arbitrary symbols, and a random number in place of the MAC. Charles does not need to know the key to do that (real MACs are large enough that it is extremely unlikely to generate a valid one by chance, unlike in the example). Bob uses the MAC to find the authentic messages and drops the "chaff" messages. This process is called "winnowing". An eavesdropper located between Alice and Charles can easily read Alice's message. But an eavesdropper between Charles and Bob would have to tell which packets are bogus and which are real (i. e. to winnow, or "separate the wheat from the chaff"). That is infeasible if the MAC used is secure and Charles does not leak any information on packet authenticity (e. g. via timing). If a fourth party joins the example (named Darth) who wants to send counterfeit messages to impersonate Alice, it would require Alice to disclose her secret key. If Darth cannot force Alice to disclose an authentication key (the knowledge of which would enable him to forge messages from Alice), then her messages will remain confidential. Charles, on the other hand, is no target of Darth's at all, since Charles does not even possess any secret keys that could be disclosed.

Вариации

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

Последствия для правоохранительных органов

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

Интересные факты

Термин "просеивание" был предложен отцом Рональда Ривеста. Перед публикацией статьи Ривеста в 1998 году другие люди обратили его внимание на роман Рекса Стоута 1965 года "The Doorbell Rang", в котором описывается та же концепция, и поэтому он был включен в список литературы к статье.