Криптографические протоколы

       

Самоутверждающийся протокол


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

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

Разновидности атак на протоколы

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

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

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


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

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

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

 

Доказательство с нулевым разглашением конфиденциальной информации

Антон: "Я знаю пароль для входа в компьютерную сеть Центробанка и рецепт приготовления „Байкала"".

Борис: "Нет, не знаешь!"

Антон: "Нет, знаю!"

Борис: "Чем докажешь?"





Антон: "Хорошо, я тебе все расскажу".

Антон долго шепчет что-то на ухо Борису.

Борис: "Действительно интересно! Надо сообщить об этом газетчикам!"

Антон: "Ё-моё..."

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



Конечно, есть. В первую очередь, Антону не следует доверять свою тайну Борису. Но как тогда Антон сможет убедить Бориса в том, что действительно входит в число посвященных?

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

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

Протокол доказательства с нулевым разглашением конфиденциальной информации

Использование доказательства с нулевым разглашением конфиденциальной информации можно пояснить на конкретном примере.

Предположим, что имеется пещера, точка входа в пещеру обозначена буквой A, в точке B пещера разветвляется на две половины - C и D (см. рисунок). У пещеры есть секрет: только тот, кто знает волшебные слова, может открыть дверь, расположенную между C и D.

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

1. Борис стоит в точке A.

2. По своему выбору Антон подходит к двери либо со стороны точки C, либо со стороны точки D.

3. Борис перемещается в точку B.

4. Борис приказывает Антону появиться или (а) - через левый проход к двери, или (б) - через правый проход к двери.

5. Антон подчиняется приказу Бориса, в случае необходимости используя волшебные слова, чтобы пройти через дверь.

6. Шаги 1-5 повторяются n раз, где n - параметр протокола.



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

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

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

Протокол доказательства с нулевым разглашением срабатывает в силу того, что, не зная волшебных слов, Антон может выходить только с той стороны, с которой зашел. Следовательно, только в 50 % всех случаев Антон сумеет обмануть Бориса, сумев выйти именно с той стороны, с которой тот попросит. Если количество экспериментов равно n, то Антон успешно пройдет все испытания только в одном случае из 2n. На практике можно ограничиться n=16. Если Антон правильно исполнит приказ Бориса во всех 16 случаях, значит, он и вправду знает волшебные слова.



Пример с пещерой является очень наглядным, но имеет существенный изъян. Борису будет значительно проще проследить, как в точке B Антон поворачивает в одну сторону, а потом появляется с противоположной стороны. Протокол доказательства с нулевым разглашением здесь попросту не нужен.

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

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

2. Антон задействует протокол предсказания бита для найденного на шаге 1 решения, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этим решением, Борис мог бы достоверно убедиться, что предъявленное Антоном решение действительно было получено им на шаге 1.

3. Антон показывает новую труднорешаемую задачу Борису.

4. Борис просит Антона

или (а) - доказать, что две труднорешаемые задачи (старая и новая) изоморфны,

или (б) - предоставить решение, которое Антон должен был найти на шаге 1, и доказать, что это действительно решение задачи, к которой Антон свел исходную задачу на том же шаге.

5. Антон выполняет просьбу Бориса.

6. Антон и Борис повторяют шаги 1-6 n раз, где n - параметр протокола.

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

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



 

Параллельные доказательства с нулевым разглашением конфиденциальной информации

Обычный протокол доказательства с нулевым разглашением конфиденциальной информации требует, чтобы Антон и Борис последовательно повторили его шаги n раз. Можно попробовать выполнять действия, предусмотренные этим протоколом, одновременно:

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

2. Антон задействует протокол предсказания бита для найденных на шаге 1 n решений, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этими решениями, Борис мог бы достоверно убедиться, что предъявленные Антоном решения действительно были получены им на шаге 1.

3. Антон показывает n новых труднорешаемых задач Борису.

4. Для каждой из n новых труднорешаемых задач Борис просит Антона

или (а) - доказать, что она изоморфна исходной труднорешаемой задаче,

или (б) - предоставить решение этой задачи, которое Антон должен был найти на шаге 1, и доказать, что оно действительно является ее решением.

5. Антон выполняет все просьбы Бориса.

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

Неинтерактивные протоколы доказательства с нулевым разглашением конфиденциальной информации

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



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

2. Антон задействует протокол предсказания бита для найденных на шаге 1 n решений.

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

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

(а) если этот бит равен 1, то Антон доказывает, что исходная и i-я задачи изоморфны, или

(б) если этот бит равен 0, то Антон помещает в общедоступную базу данных решение i-й задачи, вычисленное на шаге 1.

5. Антон передает в общедоступную базу данных все обязательства, которые были получены им на шаге 2.

6. Борис, Владимир или любое другое заинтересованное лицо могут проверить правильность выполнения шагов 1-5 Антоном.

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

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

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



Тогда Антон может попытаться догадаться, на какой из этих пунктов падет выбор, и выполнить шаги 1-3 протокола. А если его догадка неверна, он повторит все сначала. Именно поэтому в неинтерактивных протоколах необходим больший запас прочности, чем в интерактивных. Рекомендуется выбирать n=64 или даже n=128.

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

Удостоверение личности с нулевым разглашением конфиденциальной информации

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

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

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



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

В-третьих, Антон может попросить Зиновия одолжить на время его цифровое удостоверение личности. Мол, Антону надо съездить в Соединенные Штаты, а поскольку он - бывший сотрудник советской разведки, работавший против США, американское правительство наотрез отказывает ему во въездной визе. Зиновий с радостью соглашается: после отъезда Антона он может пойти практически на любое преступление, поскольку обзавелся "железным" алиби. С другой стороны, ничто не мешает совершить преступление Антону. Кто поверит лепету Зиновия о том, что он одолжил свое цифровое удостоверение личности какому-то другому человеку?

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

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

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


Содержание раздела