Как победить гроссмейстера, не умея играть в шахматы. Про злоупотребление доказательства с нулевым знанием
Это Алиса. Она не умеет играть в шахматы, но изучает защиту информации. Поэтому она сможет обыграть гроссмейстера. Для этого ей понадобится:
Два гроссмейстера,
Две шахматные доски с фигурами,
Две комнаты.
И вот как она этого добьется.
Проблема гроссмейстера
Алиса приглашает Гарри Каспарова и Анатолия Карпова сыграть с ней в шахматы в одном месте, в одно время, но в разных комнатах. Ни Каспаров, ни Карпов, не знают о присутствии другого.
Алиса играет белыми в партии с Каспаровым и черными в партии с Карповым.
Сначала Карпов делает ход первым, так как он играет за белых. Алиса записывает ход, идёт в комнату к Каспарову и повторяет записанный ход. Далее записывает ответ Каспарова черными и повторяет этот ход в партии с Карповым.
Так продолжается до тех пор, пока она не выиграет одну из партий, проигрывая другую. Либо обе партии заканчиваются вничью.
На самом деле Каспаров и Карпов играют друг с другом, а Алиса является просто посредником, передающим ходы одного другому. Однако, если Карпов и Каспаров не знают о присутствии друг друга, они крайне удивятся мастерством Алисы.
Проблема гроссмейстера – это злоупотребление доказательства с нулевым знанием. Посмотрим, что это такое.
Доказательство с нулевым знанием
Это криптографический протокол, позволяющий доказать проверяющему знание о чем-либо, при этом проверяющий не получает никакую информацию о самом знании.
Доказательство имеет форму интерактивного протокола. Допустим Алиса хочет доказать Бобу, что знает секрет, но не рассказать сам секрет. Боб задаёт Алисе ряд вопросов. Если Алиса знает секрет, то ответит на все вопросы правильно. Но ни один из вопросов и ответов не даст Бобу содержание секрета, но докажет знание Алисы. Доказательство с нулевым знанием используется для доказательства идентичности. Эта схема была впервые предложена Уриелем Файгом, Амосом Фиатом и Ади Шамиром. Однако, она не совершенна, есть различные злоупотребления. И проблема гроссмейстера это доказывает.
В примере с проблемой гроссмейстера Алиса не знала секрета, но она нашла Виктора, который знает секрет. И когда Боб задавал вопросы Алисе, она задавала их Виктору, и ответы Виктора передавала Бобу, выдавая их за свои.
Так, Алиса воспользовалась злоупотреблением доказательства с нулевым знанием.
В данном примере некоторая сторона может доказать владение секретом, не обладая им на самом деле или, другими словами, может имитировать то лицо, которому на самом деле принадлежит секрет. Есть и другие злоупотребления доказательства с нулевым разглашением. Рассмотрим их.
Обман, выполненный мафией
Алиса ужинает в ресторане Боба. Кэрол выбирает дорогие бриллианты в ювелирном магазине Дэйва. Боб и Кэрол – мафия, Алиса и Дэйв – ничего не подозревающие люди.
Алиса завершает ужин и идёт расплачиваться. Для этого ей нужно доказать свою личность Бобу. Боб подает сигнал Кэрол по тайному каналу связи, и та идёт на кассу с бриллиантами подороже и собирается доказать свою личность Дэйву. И пока Алиса доказывает свою личность Бобу, Боб передаёт сведения об Алисе Кэрол, и та передаёт их Дэйву. Дэйв запрашивает сведения Кэрол, Кэрол передаёт их Бобу, и Боб запрашивает сведения у Алисы. Когда Алиса отвечает, Боб передаёт правильный ответ Кэрол, а та Дэйву.
Получается, что Алиса просто доказывает свою личность Дэйву, тем самым покупая бриллианты. А личности Боба и Кэрол остаются незамеченными.
Обман, выполненный террористами
Теперь Алиса и Кэрол действуют сообща, пытаясь обмануть Дэйва. Кэрол – известная террористка, Алиса помогает ей въехать в страну. Дэйв – офицер-пограничник. Алиса и Кэрол общаются по тайному каналу связи.
Кэрол на машине подъезжает к границе, где её встречает Дэйв. Кэрол должна доказать свою личность. Дэйв запрашивает вопросы согласно доказательству нулевого знания. Кэрол передаёт запросы Алисе, та отвечает на них, Кэрол передаёт ответы Дэйву.
Получается, что Алиса подтверждает свою личность Дэйву, а Кэрол попадает в страну незамеченной и устраивает теракт.
Предлагаемые решения
Эти злоупотребления возможны благодаря тайному каналу связи. В случае проблемы гроссмейстера «тайным каналом» является переход Алисы из комнаты в комнату. Одним из способов предотвращения обмана является проведение процедуры доказательства личности в помещении, блокирующем связь – своеобразной клетке Фарадея. Тогда террористка Кэрол не получит сообщения от Алисы, хозяин ресторана Боб не передаст сведения Кэрол, а Алисе, запертой в одной комнате, придётся сдаться гроссмейстеру, чтобы не краснеть от стыда.
Тотас Бот и Иво Десмедт предложили ещё одно решение проблемы – ограничить время доказательства личности. У мошенников не останется времени для обмена информацией. В случае с шахматами, если время на обдумывание хода поставить не больше одной минуты, то Алиса не успеет перебежать из комнаты в комнату и повторить ход.
Для предотвращения обмана шахматисты должны следовать этому протоколу:
Перед началом игры шахматисты договариваются о конкретном значении t — время, выраженное в секундах, за которое игрок должен обдумать и сделать ход. Также договариваются, кто играет белыми (обозначим F — first), а кто чёрными (S — second). Каждый игрок имеет свой секундомер.
F начинает игру и устанавливает на своём секундомере время z = 0.
S запускает секундомер и точно за время t совершает ход. Сразу после хода устанавливает на своём секундомере время y = t.
F на секундомере в этот момент видит время e. Если e - z ≠ t, то F считает себя обманутым и завершает протокол. Если e - z = t, и ход S победный, то F признаёт себя проигравшим. Протокол завершается, S побеждает. Если e - z = t, и ход S вызывает ничью, то игра останавливается. Происходит ничья. Если e - z = t, и ход S не победный, то F точно за время t обдумывает и совершает ход. К этому времени у F на секундомере время z = e + t.
S на секундомере в этот момент видит время f. Если f - y ≠ t, то S считает себя обманутым и завершает протокол. Если f - y = t, и ход F победный, то S признаёт себя проигравшим. Протокол завершается, F побеждает. Если f - y = t, и ход F вызывает ничью, то игра останавливается. Происходит ничья. Если f - y = t, и ход F не победный, то S точно за время t обдумывает и совершает ход. К этому времени у S на секундомере время y = f + t.
Пункты 4, 5 повторяются, пока кто-то не выиграет, либо не произойдёт ничья.
Заключение
В реальном мире для доказательства личности используются физические символы – паспорт, водительские права, кредитные карты. Эти носители содержат что-то, связывающее их с конкретным человеком – фотографию, подпись. Но в цифровом мире не покажешь паспорт или права каждому запрашивающему устройству, и тогда на помощь приходят закрытые ключи и подобные схемы. Берегите свои данные и как говорится в смс, никому не сообщайте этот код!
Материал подготовлен при использовании литературы:
Шнайер Б. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си //Под редакцией ПВ Семьянова. М., Триумф. – 2002. – С. 14.