Введение в современную криптографию


Атаки оракулу дополнения на CAPTCHA



Pdf көрінісі
бет82/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   78   79   80   81   82   83   84   85   ...   249
Криптография Катц

Атаки оракулу дополнения на CAPTCHA . CAPTCHA — это поврежденное 
изображение, скажем, английского слова, которое может легко прочитать человек, 
но не компьютер. CAPTCHA используются для проверки того, что с Интернет-стра-
ницей взаимодействует пользователь-человек, а не автоматическая программа. На-
пример, CAPTCHA используются в сервисах электронной почты, чтобы спаммеры 
не могли проникнуть в тысячи аккаунтов и использовать их для рассылки спама.
Одной из возможных конфигураций CAPTCHA может быть вариант, когда это 
отдельный сервис работающий на независимом сервере. Чтобы посмотреть, как 
это работает, обозначим веб-сервер SW , сервер CAPTCHA SC , и пользователя U. 
Когда пользователь U загружает Интернет-страницу на сервере SW , может про-
изойти следующее: SW шифрует произвольное английское слово w с помощью 
ключа k который изначально известен SW и SC , и посылает получившийся шифр-
текст пользователю (вместе с Интернет-страницей). U передает шифртекст SC , тот 
его дешифрует, получает w, и выдает поврежденное изображение w пользователю 
U. Наконец, U посылает слово w назад серверу SW для проверки. Интересно то, 
что SC расшифровывает любой шифртекст, полученный от U и выдаст ошиб-
ку «плохого дополнения», если расшифровки не будет удачной, как мы описывали 
ранее. В этом случае, U имеет возможность произвести атаку оракула добавления, 
как описано выше, и таким образом разгадать CAPTCHA (т.е. узнать слово w) авто-


115
матически без любого человеческого вмешательства, из-за чего CAPTCHA теряет 
эффективность. Хотя можно пребегнуть к специальным мерам (например, SC воз-
вращает произвольное изображение вместо ошибки расшифровки), на самом деле 
необходимо использовать шифровальную схему, устойчивую к АВШ .
Упражнения
Докажите Предположение 3.6.
Докажите, что Определение 3.8 не удовлетворяется, если Π может зашиф-
ровать сообщения произвольной длины, и противник не ограничен условием 
выдавать сообщения одинаковой длины в эксперименте 
Подсказка: Пусть q(n) — полиномиальное максимальное значе-
ние длины шифртекста, когда Π используется для шифрования еди-
ничного бита. Затем, рассмотрим противника, который выдает m0 ∈ 
{0, 1} и равномерное m1 ∈ {0, 1}q(n)+2 .
Скажем, что Π = (Gen, Enc, Dec), такое что k ∈ {0, 1}n, алгоритм Enck опреде-
лен только для сообщений максимально длины A(n) (для некоторого полиноми-
ального A). Постройте схему, удовлетворяющую Определение 3.8, даже когда 
противник не ограничен условием выдавать сообщения одинаковой длины в 
эксперименте 
.
Докажите, что Определение 3.8 и 3.9 эквивалентны.
Пусть |tt(s)| = A(|s|) для некоторого A. Рассмотрим следующий эксперимент:


Достарыңызбен бөлісу:
1   ...   78   79   80   81   82   83   84   85   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет