Как победить гроссмейстера, не умея играть в шахматы. Про злоупотребление доказательства с нулевым знанием

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

  • Два гроссмейстера,

  • Две шахматные доски с фигурами,

  • Две комнаты.

И вот как она этого добьется.

Проблема гроссмейстера

Алиса приглашает Гарри Каспарова и Анатолия Карпова сыграть с ней в шахматы в одном месте, в одно время, но в разных комнатах. Ни Каспаров, ни Карпов, не знают о присутствии другого. 

Алиса играет белыми в партии с Каспаровым и черными в партии с Карповым. 

Сначала Карпов делает ход первым, так как он играет за белых. Алиса записывает ход, идёт в комнату к Каспарову и повторяет записанный ход. Далее записывает ответ Каспарова черными и повторяет этот ход в партии с Карповым.

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

На самом деле Каспаров и Карпов играют друг с другом, а Алиса является просто посредником, передающим ходы одного другому. Однако, если Карпов и Каспаров не знают о присутствии друг друга, они крайне удивятся мастерством Алисы.

Проблема гроссмейстера – это злоупотребление доказательства с нулевым знанием. Посмотрим, что это такое.

Доказательство с нулевым знанием

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

Доказательство имеет форму интерактивного протокола. Допустим Алиса хочет доказать Бобу, что знает секрет, но не рассказать сам секрет. Боб задаёт Алисе ряд вопросов. Если Алиса знает секрет, то ответит на все вопросы правильно. Но ни один из вопросов и ответов не даст Бобу содержание секрета, но докажет знание Алисы. Доказательство с нулевым знанием используется для доказательства идентичности. Эта схема была впервые предложена Уриелем Файгом, Амосом Фиатом и Ади Шамиром. Однако, она не совершенна, есть различные злоупотребления. И проблема гроссмейстера это доказывает.

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

Так, Алиса воспользовалась злоупотреблением доказательства с нулевым знанием.

В данном примере некоторая сторона может доказать владение секретом, не обладая им на самом деле или, другими словами, может имитировать то лицо, которому на самом деле принадлежит секрет. Есть и другие злоупотребления доказательства с нулевым разглашением. Рассмотрим их.

Обман, выполненный мафией

Алиса ужинает в ресторане Боба. Кэрол выбирает дорогие бриллианты в ювелирном магазине Дэйва. Боб и Кэрол – мафия, Алиса и Дэйв – ничего не подозревающие люди.

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

Получается, что Алиса просто доказывает свою личность Дэйву, тем самым покупая бриллианты. А личности Боба и Кэрол остаются незамеченными.

Обман, выполненный террористами

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

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

Получается, что Алиса подтверждает свою личность Дэйву, а Кэрол попадает в страну незамеченной и устраивает теракт.

Предлагаемые решения

Эти злоупотребления возможны благодаря тайному каналу связи. В случае проблемы гроссмейстера «тайным каналом» является переход Алисы из комнаты в комнату. Одним из способов предотвращения обмана является проведение процедуры доказательства личности в помещении, блокирующем связь – своеобразной клетке Фарадея. Тогда террористка Кэрол не получит сообщения от Алисы, хозяин ресторана Боб не передаст сведения Кэрол, а Алисе, запертой в одной комнате, придётся сдаться гроссмейстеру, чтобы не краснеть от стыда.

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

Для предотвращения обмана шахматисты должны следовать этому протоколу:

  1. Перед началом игры шахматисты договариваются о конкретном значении t — время, выраженное в секундах, за которое игрок должен обдумать и сделать ход. Также договариваются, кто играет белыми (обозначим F — first), а кто чёрными (S — second). Каждый игрок имеет свой секундомер.

  2. F начинает игру и устанавливает на своём секундомере время z = 0.

  3. S запускает секундомер и точно за время t совершает ход. Сразу после хода устанавливает на своём секундомере время y = t.

  4. 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.

  5. 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.

  6. Пункты 4, 5 повторяются, пока кто-то не выиграет, либо не произойдёт ничья.

Заключение

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

Материал подготовлен при использовании литературы:

Шнайер Б. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си //Под редакцией ПВ Семьянова. М., Триумф. – 2002. – С. 14.

Реклама

Комментарии 23

    0

    deleted, sorry

      0
      Классная статья, Любовь! Я все понял
        +1
        Один из векторов атаки на автомобили с бесключевым доступом и один из способов защиты от неё описаны в этой статье, хотя я думал, что это всё уже всем известно.
          0
          Кстати, да. От установки канала связи между ключем и машиной, чтобы машина думала, что водитель все еще стоит рядом, а не ушел в магазин за покупками, до считывания кода от брелка, блокируя канал приема, а затем передачи предыдущего ключа. А какой есть способ защиты?
            +1
            Так описанное в статье ограничение времени, машина замеряет сколько миллисекунд прошло до ответа ключа и отказывается работать если есть задержка.
              0

              За одну миллисекунду радиосигнал проходит 300км. Тут нужны доли микро секунд. Не думаю что это возможно

          +2
          Помню, написал скрипт на Selenium, который заходил в какой-то чат рулетку текстовый, под двумя браузерами и общался с разными людьми, пересылая им сообщения.
          Смешно было.
            0
            В реальном мире для доказательства личности используются физические символы – паспорт, водительские права, кредитные карты. Эти носители содержат что-то, связывающее их с конкретным человеком – фотографию, подпись.

            Вопрос в том как используются? Проверяющий должен сличить фотографию из документа с лицом стоящего перед ним человеком, а также подпись из паспорта и с подписью собственноручно проставленной человеком под неким документом.
            В цифровом мире тоже есть физические символы — это сертификат, где прописан открытый ключ человека и его идентификационные данные (ФИО, ИНН и т.п.).
            А для доказательства того, что данный человек владеет не только сертификатом с открытым ключом, то и самим закрытым ключом, которым собственно и делается подпись, от него требуется подписать что-то нейтральное, а не просто показать флэшку или токен. И после проверки этой тестовой подписи можно утверждать, что данным секретом владеет именно данный человек.
            Как видим, технология в принципе одна и та же.
            Да, а закрытый ключ (пароль/PIN-код к нему) надо беречь как синица око.

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

                Играл так в начале 00ых в шахматы через интернет, с живыми людьми Параллельно запускается шахматная программа. Ходы противника вводишь как свои. Ответ программы выдаешь противнику. "Выход из комнаты" не отрывая задницы от стула.

                  +1
                  Рассказывают, как-то во время международного шахматного турнира к Эмануэлю Ласкеру обратился незнакомец с предложением сыграть по переписке с его талантливым сыном. Просьба была подкреплена солидным материальным вознаграждением, и Ласкер, подумав, согласился.
                  В случае победы он получал 500 долларов, а если мальчик каким-то чудом выиграет — на что отец, разумеется, никак не рассчитывал — тогда уже гроссмейстеру придется раскошелиться на 1500 долларов.
                  В конце концов чемпиону мира удалось победить, хотя и с огромным трудом.
                  Тайна раскрылась позднее. Оказалось, что Ласкер играл по переписке с самим Капабланкой, который согласился на те же условия незнакомца, а мальчик был просто мистификацией. Когда Ласкер, игравший белыми, сделал первый ход, он был повторен незнакомцем в партии с Капабланкой. А ответ Капабланки за черных, в свою очередь, был доведен незнакомцем до Ласкера. Таким образом, через посредника-«отца» игралась партия Ласкер-Капабланка.
                  Очевидно, что при такой игре «отец» гарантировал себе ничейный счет в матче с сильнейшими шахматистами того времени, а, значит, и чистую прибыль в размере 1000 долларов. Он выплатил 500 долларов выигравшему Ласкеру, в то время как проигравший Капабланка заплатил ему 1500 долларов.
                  +1
                  Почему нельзя зашить в протокол доказательства параметры, которые меняются в зависимости от ситуации, чтобы их нельзя было переиспользовать?

                  Например, играть в шахматы Фишера и seed для выбора расстановки считать на основе хэша от имен игроков.

                  А при доказательстве личности при покупке задавать вопросы, связанные с покупаемыми товарами, чтобы ответы на вопросы о еде в ресторане нельзя было использовать для покупки алмазов.
                    0
                    Например, играть в шахматы Фишера и seed для выбора расстановки считать на основе хэша от имен игроков.

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

                      0
                      Я думал, что шахматы тут как метафора криптографических протоколов)

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

                        Думаю это невозможно — баланс все равно будет нарушен, тем более на гроссместерском уровне игры :)

                      0
                      Ну ведь так и делают. Если оформить криптографически, то в данных для проверки включают время и назначение. Даже в самом простом случае подтверждения покупки через интернет банк присылает не только код, но и сумму платежа, назначение/место покупки, и этот код действует не более 5 минут. Это не позволяет интернет магазину или же злоумышленнику с доступом информации к нему запросить код к другому платежу.
                        0
                        Пока читал статью, был уверен, что автор как раз подводит нас к тому, чтобы убедить вставлять в запросы как можно больше подобных параметров для предотврещения таких атак.
                          +1
                          Я тоже удивлен тем что в статье даже не затронули систему доверенных сертификатов в интернете, которая как раз сделана так, чтобы исключить проблемы нулевого знания. Достаточно одного надежного фактора идентификации, чтобы исключить проблему человека посередине.
                      +1
                      Крутая статья! автору респект)
                        +1
                        Ayazhan has entered the chat
                        +3
                        Там в конце статьи как раз то, что ждёт всех террористов: ЗАКЛЮЧЕНИЕ.
                          –2

                          Несколько странные ситуации. В реальном мире используются физические символы. И за них получают реальные физические блага. В цифровом мире паспорт не покажешь — так почему блага остались физическими?


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


                          А тут подменили понятия, введя две идентификации. Первая — с кого брать деньги, вторая — кому отдавать товар, и эту вторую свели к "тому, кто стоит перед продавцом". Если идентификация одна — проблем нет.

                            +1

                            Я как-то с другом играли в шахматы, потом нам надоело играть против друг друга и у меня на телефоне были шахматы против компа, он был силен и мы установили доску и играли против него вдвоем в итоге все равно проиграли.

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое