Благодаря Сэмюэл Невес за то, что указал мне правильное направление. я взглянул на упомянутая ссылка, и это касается того, как теорема 6.1 не работает для слабой безопасности. Он также охватывает MAC, который слабо защищен без проверочных запросов, но теряет свою безопасность при наличии проверочных запросов.
Почему теорема 6.1 не работает
Я обнаружил, что тонкость заключается в том, как определяются атакующие игры. Злоумышленник может отправить любую пару сообщение-тег $(м, т)$ для проверки до тех пор, пока он не входит в число ранее подписанных пар. Важно то, что в исходном определении безопасности противник выигрывает атаку. если и только если злоумышленник отправляет действительную, ранее невиданную пару сообщение-тег для проверки. Эквивалентность следует из определения условия выигрыша.
Однако при слабой безопасности прямое направление все еще сохраняется (отправка действительного $(м, т)$ пара где $м$ никогда ранее не встречавшееся явно образует достоверную никогда ранее не встречавшуюся пару), но обратное направление терпит неудачу. Обратное направление может потерпеть неудачу, потому что противник может получить $(М, Т)$ пару из запроса на подпись, а затем отправить действительный $(М, \бар{Т})$ пара, изменив тег $Т$. $(М, \бар{Т})$ является допустимой и ранее невидимой парой, но противнику не удается победить, потому что пара включает в себя сообщение, которое было ранее подписано.
Где теорема 6.1 не работает для слабой безопасности, когда авторы утверждают $\text{Pr}[W_0] = \text{MAC}^\text{vq}\text{adv}[\mathcal{A, I}]$ который предполагает, что победа в атаке эквивалентна представлению действительной, ранее невидимой пары сообщение-тег. В приведенном выше крайнем примере выше это не так, поскольку это возможно для $W_0$ произойти, но без победы в слабой игре атаки безопасности.
Как решить упражнение
Что касается того, как построить слабозащищенную систему MAC без проверочных запросов, но не слабозащищенную с проверочными запросами, вы в основном создаете систему, в которой после получения $(М, Т)$ из запроса подписи злоумышленник может легко построить действительный $(М, \бар{Т})$ пары. Представляя эти действительные, но невыигрышные пары, злоумышленник узнает достаточно информации, чтобы взломать систему MAC.
Позволять $\mathcal{K} = \{0,1\}^\ell$ и $|\mathcal{T}|$ быть супер-поли. Позволять $F$ быть PRF, определенной над $(\mathcal{К, М, Т})$, $k \stackrel{R}{\gets} \mathcal{K}$ и $\mathcal{I} = (S, V)$ быть MAC-адресом, определенным $(\mathcal{K, M, T} \times \{\perp, 0,\ldots,\ell-1\})$. Алгоритм подписи определяется как $S(m) = (F(k, m), \perp)$ и алгоритм проверки такой
V (м, (т, я))
// Проверка тега на соответствие PRF
d = F(k, m) == t
если !d или i == â
вернуть д? принять : отклонить
// Возвращаем i-й бит ключа
вернуть k[i] == 1 ? принять : отклонить
Свойство корректности сохраняется, поскольку вторая компонента $S(м)$ является $\перп$ который входит в оператор if. Эта система MAC по существу является детерминированной системой MAC, полученной из $F$ но с дополнительным индексным полем.
Сначала мы замечаем, что $\mathcal{I}$ слабо защищен без запросов проверки. Если противник побеждает, то противник представил действительную пару $(м, (т, я))$ куда $м$ раньше не видел. Это означает $\textsf{принять}$ был возвращен, что означает $д$ верно в $V(м, (т, я)))$ (либо был введен оператор if, где $\textsf{принять}$ был возвращен или оператор if не был выполнен, что подразумевает $д$ не было ложным). Это происходит с пренебрежимо малой вероятностью по теореме 6.2, так как $д$ истинность означает, что была сделана подделка детерминированного MAC, полученного из $F$ (этот MAC является безопасным в соответствии с более строгим определением безопасности).
Однако, $\mathcal{I}$ не является слабо защищенным с проверочными запросами. Противник, нарушающий безопасность,
Пусть m — произвольное сообщение
Получите (m, (t, â)) от претендента
к[0..1-1] = 0
для i = 0 .. l-1
Пусть r будет ответом претендента на запрос проверки (m, (t, i))
если г == принять
к [я] = 1
еще
к [я] = 0
// Ключ восстановлен
Пусть m' — произвольное сообщение, не равное m
// Вычисление тега m' с восстановленным ключом
Пусть t' = S(m')
Отправьте запрос проверки (m', (t', â)) претенденту
