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 настоящих битов и даёт ответ, сколько битов совпало.

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

sassa_nf July 2nd, 2013
не, не надо отвечать :) таки уже подумал головой и согласен, что идея оценки размера ключа таким способом очень хорошая.

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 более надёжен.

wizzard0 July 2nd, 2013
я согласен, что OTP теоретически абсолютно безопасен.

также я согласен, что сравнивать "зависимо" с "независимо" не стоит.

но! из-за http://wizzard0.livejournal.com/316613.html я считаю, что с практической точки зрения OTP *в сценарии ЭЦП* можно рассматривать только в связке с марковской цепью (например) которая моделирует событие "упал винт, ресторнул бэкап, релизнул новый билд суперсекурного мессенжера, OOPS we're screwed". я не знаю как это воркароундить, поэтому это надо учитывать. как учитывать, я тоже не знаю, но учитывая MTBF винтов и проеба девайсов - это явно более вероятное событие, чем 1/2^128.

sassa_nf July 2nd, 2013
на практике, где есть способы виртуализировать обозреваемую историю, реализация OTP невозможна, да. я рассуждал в рамках драфта.

wizzard0 July 2nd, 2013
> но нужен более сложный протокол с функцией шифрования - функция должна учитывать историю.

в сценарии "ресторнули виртуальную машину из бекапа"/"хостер спер нашу виртуальную машину с супер-пупер гомоморфным шифрованием и всего лишь сгенерил еще раз" построить такой протокол по-моему невозможно :(

или ты знаешь что-то такое про эти сценарии, чего не знаю я?

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

sassa_nf July 2nd, 2013
нет, не знаю :) я чисто теоретически. "ресторнули вертухайную машину" - это уже не One Time Pad.

wizzard0 July 2nd, 2013
еще мне не дает покоя мысль о том, что OTP можно заменить hash chain'ом и тогда у нас ключ будет всего лишь 256 бит. в смысле, понятно что заменять "подложку под блумфильтр" хешчейном нельзя, потому что биты зависимы, а вот если заменить им отп и публиковать с конца - то что?

ооо... кстаати... тут нельзя использовать OTP! точнее, нельзя в том виде, в котором ты описал - ведь тогда Сэм сможет наебать Роба, точнее, двух Робов, выпустив одновременно 2 сообщения и раскрыв им одинаковые биты. даже если они передадут сообщения Алисе и она им скажет, что "какая-то тут хуйня", они не могут быть уверены, кого же из них наебали!

поэтому, хотя нам и пофиг на свойство "одно сообщение - множество сигнатур", но "множество сообщений - одна сигнатура" допускать нельзя!

edit: перепутал лиц, аяяй! и в комменте ниже тоже перепутал!

edit2: поскольку Роб не факт что доверяет Сэму, то применение OTP вместо сигнатуры_от_хэша нарушает еще и свойство non-repudiation применительно к сигнатурам, если только Сэм не складывает хэш к арбитру. короче, не нравится мне тут OTP, сразу же появляется необходимость минимум в глобальных часах, а то и в глобальном публичном registry, а это ffuuuu

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

sassa_nf July 2nd, 2013
non-repudiation и прочий траст не имеет значения с тз вышеизложенного.

hash chain - это ты начинаешь расчитывать на свойства конкретной функции, а нам это делать запрещено по условиям задачи.

wizzard0 July 2nd, 2013
Ага. Ну вообще да, с тем, что я излишне упростил условие и оно стало кривоватое - я согласен. Point taken.

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

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

wizzard0 July 2nd, 2013
> каким образом при таком протоколе получатель поймёт, что письмо подписано правильной подписью?

ну вот я там выше уже обратил внимание sassa_nf что если тупо заменить блумфильтр на OTP, то действительно не поймет, и менять надо как-то похитрее.

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

109 July 2nd, 2013
какой ещё нахуй блумфильтр? к чёрту подробности, город какой? :)

сначала мне надо понять, как протокол вообще работает.

wizzard0 July 2nd, 2013
А...

Слушай, если честно - мне лениво. Как и с предыдущей статьей. As in "меня просят поработать, а рабочий день уже закончился, и еще куча других вещей несделанных лежит"-лениво, а не "вообще лениво".

Я бы запросто обьяснил по ходу на салфетке под пиво/виски, разглядывая собеседника и понимая, какие именно куски моих фраз понятны, а какие - нет. А расписывать долго...

Но поскольку в Редмонде я вряд ли появлюсь в ближайшие пару месяцев, то надо бы расписать... Черт. Надо что-то придумать.

109 July 2nd, 2013
да я понимаю. у меня самого висит white paper про leader election - надо написать, а руки не доходят. кстати, если тебе интересно, можно open source implementation забацать, в одиночку-то у меня вряд ли руки дойдут. nugetize it, как у нас говорят.

ну и это. если таки занесёт к нам, дай знать. да в принципе и остановиться у меня можно будет, дом большой.

wizzard0 July 2nd, 2013
leader election, хмм.

в принципе мне очень интересно, хотя бы потому, что с лидером можно значительно упростить одну ебаную хуйню которую из-за ее сложности так никто и не осилил реализовать, а именно http://www.cypherpunks.ca/~iang/pubs/mpotr.pdf

да и вообще штука полезная.

кстати sassa_nf призывается покомментировать, т.к. есть подозрение что он сможет что-то внятное сказать про сабжевый пейпер :)

за приглашение спасибо, в принципе надо попробовать свой шифрованный дедупликатор продать кому-то в штатах, если удастся - то появится и повод приехать, соответственно.

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

sassa_nf July 2nd, 2013
я сперва тоже не допёр. Но смысл этого драфта как раз в том, что не важно, какой механизм мы там придумаем - мы всего лишь оцениваем, какой ключ нужен для некоторым образом идеализированной схемы шифрования. Менее идеальные схемы потребуют ещё более длинный ключ.

Объяснение взаимодействия Sam, Alice, Rob в виде какого-то протокола запутывает. На самом деле нужно считать, что Alice - это Oracle, доступный злоумышленнику.

Дальше чтобы понять, как это Oracle "тырит" биты ключа, когда "на самом деле" мы ведь используем весь ключ целиком, - нужно вспоминать теорию информации, которую у нас и без того преподавали бегло. Идеальный взломщик умеет encrypt(x) разложить на f(x)+noise(x,key), где x и f(x) ему известно, noise(x,y) он умеет обратить, а key - случайная цепочка битов. Тогда по теории информации "выяснить noise(x,key)" равносильно "узнать некоторые биты ключа". Например, если noise(x,key) умеет из 128-битного ключа сгенерировать 16 битов "шума", мы узнаём 16 битов ключа (или, что равносильно, можем подобрать 2^16 ключей, дающих тот же noise). Тогда для нескольких сообщений noise(x,key) мы можем найти по 2^16 ключей. Чем больше одинаковых ключей (чем больше ключей на пересечении этих множеств), тем хуже схема шифрования - мы можем "невозбранно" пользоваться любым из найденных ключей. И наоборот, чем меньше одинаковых ключей среди решений noise(x,key) для разных x (чем меньше ключей на пересечении множеств решений), тем более точно мы узнаём значение key. Catch-22.

wizzard0 July 2nd, 2013
Слушай, ты меня прямо спасаешь %) Спасибо огромное, серьезно.

> которую у нас и без того преподавали бегло
а вы и 109 в одном универе учились? или это образно?

sassa_nf July 2nd, 2013
"это образно? "

это caveat, что если я дурку спорол с объяснением, то сорри, давно было и поверхностно. :)

sassa_nf July 2nd, 2013
"можем подобрать 2^16 ключей"

ой, лажа. мы можем подобрать 2^(sizeof(key)-16) ключей.

wizzard0 July 2nd, 2013
А теперь, внимание, вопрос на миллион - как, обладая этой информацией (о том, что любую деплоенную in the wild *SA фундаментально *возможно сломать*) и возможностью невозбранно устанавливать SSL-коннекты к Google/Paypal/whatever, да что уж там, берем выше, возможностью пособирать сертификаты, подписанные конкретным CA - сделать known-message universal forgery для sha1RSA? (уточняю что именно для sha1RSA, а не для RSA - для него уже есть :))

sassa_nf July 2nd, 2013
спасибо, я хочу умереть от старости

wizzard0 July 2nd, 2013
бггг)

кстати, я спиздел. когда я говорил "для rsa уже есть", я имел в виду https://factorable.net/weakkeys12.extended.pdf

но я сейчас туда глянул, и понял что
а) оно применимо и к sha1RSA,
б) ничем особо нам не помогает.

edit: но тем не менее это чудесный пейпер который я люблю показывать людям, которые утверждают, что с практическим применением RSA все проблемы уже излечили, и что replay атаки бывают только для виртуальных машин и/или специально созданных условий, а с физическими устройствами in the wild не встречаются

%)

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

sassa_nf July 2nd, 2013
о, а я хотел спросить. отлегло. я думал, уже RSA реверснули, а оно слабость реализации...

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