Previous Entry Share Next Entry
2016-01

Fundamental limitations of digital signature security (DRAFT)

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.

Let's try to look at this "seal" from the information-theoretic perspective.

We want to reach 128-bit security, i.e. a random guess should have a 1 in 2^128 chance getting a signature right.

Then, the public key is an encoding of a trapdoor function which can map X 256-bit messages into some thumbprint, where there are 2^256 ways (or more) to construct this trapdoor.


Let's assume we have Sam as the signer, trusted arbiter Alice instead of a trapdoor function, and a relying party Rob. Using an arbiter means minimal information (≤1 bit) is disclosed at each signature verification attempt (see [1])

Then, we have an easy and consistent signature scheme:
- Let the private key be a random bitstream PK, of length p.
- To sign the message, Sam computes N different hash functions H0 to Hn from the message digest, and uses them as indexes into PK. He then publishes these indexes together with corresponding bits of the private key.
- To verify the message, Rob passes the bits+indexes to Alice, who returns true/false when bits match their copy of the private key.

Sounds familiar? Yes, it's the Bloom Filter, and collision in the filter means two signatures share some subset of disclosed bits which means enough information is disclosed for the Rob to forge the signature using the same bits and hash functions.

And the formulas for bloom filter calculation are widely known. Let's calculate how large the private key has to be for signing 1M signatures and 128-bit security (3*10^-40 collision probability)? [3]

It seems we need a minimum of 22 MB of data to guarantee security, PLUS it has to be scrambled in some way if we want Rob to be able to verify the signature itself - because real-life customizable trapdoor functions are not as ideal as Alice (see GMSS or XMSS signatures, for example)

The message thumbprint size would then be about 131*(28+1)=3799 bits (475 bytes)

And it turns out, there is a paper [2] which arrives to exactly same numbers using a lot more complicated calculations :) (see Table 1)


Meanwhile, everybody knows SSL certificates arent 22 MB but only about 5-20 KB in length. Something just doesnt seem right.

So... anybody else still surprised why DSA, ECDSA, Winternitz, *MSS and other signature schemes allow Rob to compute the private key so easily if Sam does not rigorously follow restrictions of nonce, padding and so on?

This is also the reason I consider most signature schemes being insecure (as in, fundamentally susceptible to cryptanalysis, especially under the chosen-message attack)


[1] Johansson, T.: On the Construction of Perfect Authentication Codes that Permit Arbitration. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 343–354. Springer, Heidelberg (1994)

[2] Goichiro Hanaoka, Junji Shikata, Yuliang Zheng, and Hideki Imai: Unconditionally Secure Digital ignature Schemes Admitting Transferability. T. Okamoto (Ed.): ASIACRYPT 2000, LNCS 1976, pp. 130–142, 2000.

[3] http://hur.st/bloomfilter?n=1000000&p=3.0E-39


This entry was originally posted at http://wizzard.dreamwidth.org/290018.html. It has comment count unavailable comments. Please comment there using OpenID.

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

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

wizzard0 July 2nd, 2013
1. N<<len(PK). в данном случае N=131, len(PK)~=22000000 2. потому что у алисы такой протокол 3. см. 1 и 2.

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

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

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

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

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

109 July 2nd, 2013
ничего не понял :(

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

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

sassa_nf July 2nd, 2013
Давайте с другой стороны посмотрим. Дело не в ЭЦП (механизм которой, думаю, wizzard0 в курсе).

Сэм разрабатывает механизм электронной подписи. Он не знает, что знает и умеет Мэлори. Как разработать такой механизм, чтобы гарантия была в теории, а не в тонкости реализации?

ЭЦП - это пермутация известных бит (сообщение) с использованием неизвестных (ключ).

Рассматривать ключ для одного сообщения не интересно. Хотим использовать ключ на протяжении некоторого времени - допустим, подписать 1М сообщений.

Сэм считает, что использовать мало битов ключа - это значит, позволить Мэлори подобрать такие биты для любого сообщения. Поэтому Сэм будет использовать много битов. Один способ обезопасить себя - это каждый раз использовать часть ключа длиннее сообщения. Хороший способ, но ключ получается ооочень длинный.

Сэм считает, что Мэлори может выяснить значение используемых бит ключа полностью. Один способ обезопасить себя - это каждый раз выбирать не использованные ранее биты - это One Time Pad. Хороший способ, но ключ получается ооочень длинный. (Особенно в свете использования ключа длиннее сообщения и что сообщений миллион).

Поэтому Сэм минимизирует требования к безопасности и выбирает k=128 битов ключа для подписи каждого сообщения (т.о. взлом ЭЦП должен быть проще подбора 128 случайных бит). Внимание, Сэм смирился с тем, что k=128 битов ключа он теряет с каждым сообщением.

Кстати, One Time Pad для миллиона 128-бит - это 16 МБ. Тут пусть wizzard0 объяснит, зачем нужен блум-фильтр. Но продолжим.

Сэм также минимизирует длину ключа (как выяснилось, не очень-то и минимизирует, но я думаю, таков замысел), нужную для подписи миллиона сообщений, выбирая ранее использованные биты с некоторой вероятностью. Эту вероятность можно брать разной; чем выше вероятность выбрать использованный ранее бит, тем меньше работы Мэлори; чем ниже вероятность выбрать использованный ранее бит, тем длиннее ключ; нужно найти оптимум.

Минимизация требований к длине ключа такова: даже после взлома миллиона сообщений у Мэлори не будет достаточно бит ключа, чтобы ЭЦП следующего сообщения с вероятностью p=3^10-39 использовало только ранее полученные биты. Иными словами, с вероятностью (1-p) Мэлори всё ещё нужно будет подобрать один или более бит ключа.

В этом виде задача не отличается от коллизий блум-фильтра. Можете представить себе блум-фильр - это таблица вычисленных Мэлори битов. Каждый раз, когда взламывается сообщение, оно помещается в фильтр. k хэш-функций "случайно выбирают" k бит ключа, которые ему становятся известны. Расчёт показывает, что для заданного n (количество сообщений) и p (вероятность коллизии = n+1 сообщение использует только уже известные биты) размер ключа m=22МБ (расчёт также показывает, что для эффективного использования этого ключа нужны именно k=128 хэш-функций - т.е. k заранее нам и не нужно задавать; я его привёл, чтобы было понятнее, что Сэм должен смириться с утратой такого количества битов, и что на самом деле величина k ему на руку).

wizzard0 July 2nd, 2013
> Тут пусть wizzard0 объяснит, зачем нужен блум-фильтр
Блумфильтр снимает с нас обязанность хранить значение счетчика nonce, и бояться его реюза. С блумфильтром мы вместо nonce используем дайджест сообщения, и как бонус получаем привязанность сообщения к подписи (если бы нам это не нужно было, можно было бы обойтись банальным hash chain)

edit: в смысле, one time pad дает нам, конечно, вероятность 0... но вероятность ошибки оператора или replay-атаки гораздо выше, чем 1/2^128, поэтому я постулирую, что в итоговой системе блумфильтр более надежен, чем otp.

Edited at 2013-07-02 02:53 pm (UTC)

sassa_nf July 2nd, 2013
"зачем нужен блум-фильтр"

я не об этом. OTP уже даёт более низкую границу в 16 МБ. Остальные схемы дадут только более высокую границу размера ключа, но и 16 МБ уже огого.


"я постулирую, что в итоговой системе блумфильтр более надежен"

а вот тут что-то не так.

Вероятность, что применение хеш-функции даст 0 в каком-то выбранном бите, равна (1-1/m). Вероятность, что 0 в этом бите будет и после k применений хеш-функции равна (1-1/m)^k. Подчёркиваю, речь о ВЕРОЯТНОСТИ при условии, что каждый раз хеш-функция выбирает бит НЕЗАВИСИМО.

OTP - это схема, где биты выбираются ЗАВИСИМО от предыдущих выборов и соответствующие вероятности гарантированно равны 1. Не удивительно, что требуется меньше бит для ключа - но нужен более сложный протокол с функцией шифрования - функция должна учитывать историю. У OTP одинаковое сообщение шифрованное два раза даст разные результаты.

Блум-фильтр - это идеализированная схема шифрования, которая выбирает биты идеально случайным образом без учёта истории, т.е. некоторое приближение реальных функций шифрования, которыми мы пользуемся. (Одинаковое сообщение шифрованное два раза даст одинаковый результат.) Думаю, более точным приближением была бы функция, которая учитывает выбор k битов для каждого сообщения, но для оценки размера ключа это не существенно.


Так вот, OTP будет давать 0 коллизий, а блум фильтр может давать коллизии даже в одном сообщении (снижая при этом сложность взлома). Поэтому OTP более надёжен.

109 July 2nd, 2013
спасибо, кое-что понял. но не всё, потому что я тупой.

а не понял я, например, каким образом при таком протоколе получатель поймёт, что письмо подписано правильной подписью?

sassa_nf July 2nd, 2013
а чё в [3] k=128, внезапно?

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

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

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

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

Edited at 2013-07-02 08:41 am (UTC)

wizzard0 July 2nd, 2013
Да, именно так.

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

Edited at 2013-07-02 05:06 pm (UTC)

sergey_cheban September 25th, 2013
> 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 September 25th, 2013
именно!

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

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

  • 1
?

Log in

No account? Create an account