Fundamental limitations of digital signature security (DRAFT)

[wizzard0]

As you probably know, a digital signature is a virtual "seal" that proves that some message has originated from a particular person in possession of a private key

Comments

[sassa_nf]

А можно как-то подробнее, как устанавливается связь между предложенной схемой ЭЦП и каким-нибудь RSA. Мне не очевидно:

1. почему attackerу нужен Alice. У него уже есть список битов ключа.
2. почему это relying party узнаёт ответ от Alice по каждому биту в отдельности
3. если не по отдельным битам, то почему "two signatures share some subset of disclosed bits"

[wizzard0]

1. N<

[sassa_nf]

1. это не имеет значения. атакер получил подпись и он может считать, что она действительна. дело ведь не в Алисе, а в том, что атакеру нужно подобрать значения, хеши которых выдадут те же биты.

2. продемонстрируй, что это протокол, соответствующий действительности. Может, я тупой и не пойму хода мысли.

Почему "протокол _такой_", а не такой: Sam в виде подписи использует PK-бит, где N настоящих в известных Alice местах, а остальные - случайные; Alice по подписи может выяснить, в каких местах N настоящих битов и даёт ответ, сколько битов совпало.

[wizzard0]

Так, на эти вопросы еще стоит отвечать? Судя по последующим комментам, ты таки уловил мысль, которую я пытался выразить ;)

[109]

я не понял, зачем multiple hash functions? сендер берёт одну, например sha512, энкриптит приватным ключом. это его signature для сообщения. получатель берёт signature, декриптит публичным ключом, если получился тот же хэш, всё в порядке.

[wizzard0]

т.к. в данной телеге я развиваю теорию о том что всякая асимметрика может быть сломана, если она не information-theoretic а опирается на отсутствие алгоритма как например быстро раскладывать на множители, и пытаюсь соответственно оценить сколько должен весить публичный ключ в который закодирован "в общем виде" trapdoor

[109]

ничего не понял :(

trapdoor чем-то отличается от хэш-функции?

[wizzard0]

sassa_nf меня понял и сформулировал то, что я хотел выразить, понятнее чем я сам :)

[sassa_nf]

а чё в [3] k=128, внезапно?

Как я понял, что ты хочешь сказать:

допустим, у нас есть идеальная ломалка Alice, которая из каждого сообщения выделяет k бит ключа (биты выбраны случайно и равномерно из ключа). Каков размер ключа m, чтобы после взлома n+1-го случайного сообщения наша ломалка не изымет ни одного известного ранее бита с вероятностью p?

Интересная постановка вопроса, но не ясно, как ты выбираешь это самое k.

edit. а, пардон, k вычисляется из m и n. k хэш-функций - это то же самое, что выбрать k бит случайно и равномерно.

[wizzard0]

Да, именно так.

edit: ну то есть да, Alice Роб, конечно же, какая алиса? и Mallory в данном случае могут быть одним и тем же лицом, а могут быть и разными

[sergey_cheban]

> Meanwhile, everybody knows SSL certificates arent 22 MB but only about 5-20 KB in
> length. Something just doesnt seem right.
Если смотреть с точки зрения теории информации, то публичный ключ RSA содержит всю информацию о приватном, просто в хитровывернутом виде. И если уж мы предполагаем, что способны за разумное время получить из 128 битов сигнатуры 128 битов внятной информации о приватном ключе, то с тем же успехом можно предположить, что мы способны за разумное время разложить публичный ключ RSA любой длины на множители.

[wizzard0]

именно!

но - наблюдая разные подписи одним ключом, прошу заметить.

и это не теоретическая атака, plain RSA-DSS так ломается ;). собственно OAEP зачем придумали? )