Рейтинг:0

Почему схемы WOTS и WOTS+ одноразовые?

флаг ru

Я кое-что читал о схемах подписи на основе хэшей, в частности о XMSS и, следовательно, о базовой схеме Winternitz (если быть точным, WOTS+).

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

Рейтинг:2
флаг my

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

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

Первое сообщение, которое мы подписываем, имеет хеш-значение 2; это значит, что мы публикуем $Н^2(х)$ (куда $х$ из закрытого ключа) вместе с контрольной суммой 14, которую мы публикуем как $ Н ^ {14} (у) $ (куда $у$ также из закрытого ключа)

Теперь мы подписываем (тем же закрытым ключом) хеш-значение 13; значит мы публикуем $ Н ^ {13} (х) $ и контрольная сумма $Ч^3(у)$.

На данный момент у злоумышленника достаточно информации, чтобы сгенерировать подделку, скажем, для хеш-значения 7. Для этого он взял бы $Н^2(х)$ значение из первой подписи (которую мы будем называть $а$) и вычислить $ Н ^ 5 (а) $; он бы взял $Ч^3(у)$ из второй подписи (которую мы будем называть $b$) и вычислить $ Н ^ 6 (б) $. Пара $Н^5(а), Н^6(б)$ равно $Н^7(х), Н^9(у)$, и поэтому является действительной подписью для 7, даже если злоумышленник понятия не имеет, какие значения для $х$ и $у$ находятся.

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

флаг ru
Большое спасибо, это именно то объяснение, которое я искал!

Ответить или комментировать

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