Инструмент для детектирования шифртекста

Где-то был обзор всех методов информационно-теоретической безопасности, а их много (ну как много, штук 5-6), не только одноразовый блокнот. Они довольно непрактичны (местами даже наивны) и могут быть атакованы за пределами теоретических моделей (т.е. их практическая реализация отчасти бессмысленна). Хотя сами теоретические модели могут быть полезны. Боюсь представить, что вы там хотите изобрести — информационно стойкую безопасность без одноразового блокнота, квантового, шумового канала :) Над этим тоже работают давно. В конце постинга — пара ссылок.

Пусть мы хотим безопасно закодировать 128 бит, а информационный допуск для Евы — 10-3 бит информации обо всём 128-битном ключе вместе взятом. Чему равно n?

Главное, чтобы затраты на построения информационно-стойкого канала не превысили затраты на его взлом :)

Надо и ваши ссылки тоже внимательно обдумать, и этот обзор поискать.

Я хотел получить «универсальный» ящик, который выдаёт ключ заданной длины, удобный для последующего применения в качестве ключа для стандартного блочного шифра, т.е. ключ со стандартной длиной и стандартной безопасностью. Далее такой шифр можно использовать, например, для дискового шифрования.

Вообще этот Keccak, выч. стойкость которого ограничена кроме ключа (который м.б. произвольной длины), внутренним состоянием. Вырабатываемую им гамму бесконечной длины нельзя напрямую использовать в дисковом шифровании, т.к. это PRF, а не PRP. Но если очень хочется, то можно вытащить его внутреннюю PRP и сделать на её основе аналог блочного шифра, а гамму использовать в кач-ве ключевого расписания. Правда, она не оптимизирована для инвертируемости.

1. Экстрактор должен быть детерминистичным

2. Безопасность — информационно-теоретическая ε-безопасность.

По поводу п.1:
Generalized Strong Extractors and Deterministic Privacy Amplification.
По поводу п.2:
Unconditional authenticity and privacy from an arbitrarily weak secret.

Насколько я въезжаю в тему, в этой области работы ведуться лет тридцать и тот же Маурер в этом смысле знаком. Но представление об этом у меня смутное.

Жаль, SATtva так и не сделал поддержку PGP-шифрования форумных сообщений.

Создать закрытое обсуждение ничто, однако, не мешает. :) Можете там и зашифрованные сообщения выкладывать, если считаете нужным.

Да, было бы интересно почитать. Но информация такого рода, пожалуй, уже давно в википедии, или нет?


Доктор unknown, откуда у вас такие картинки статьи?! Большое спасибо, я был очень впечатлён. Видимо, ранее я не по тем ключевым словам гуглил, или просто недогуглился до этого. Действительно, Реннер рассматривал похожие вещи, оттуда можно много что позаимствовать, но именно эту статью Реннера я не видел...


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


Вчерашний диалог с начальством в столовой:
— Я тут внезапно услышал про такую вещь, как детерминистичное QKD. Странно, что никто никогда про такое мне не рассказывал, это что-то интересное?
— Детерминистичное QKD? Нет, не слышали.
— Несколько статей есть на тему, какие-то китайцы, статья в Fisica Scripta...
— Китайцы в Fisica Scripta?^* А-ха-ха :) Нет, мы бы такое даже не стали читать.

Нет, я не буду таким категоричным, надо всё же посмотреть на работы, как время будет. Да и Реннер рассматривает что-то очень похожее, но при этом использует чуть другой термин.


To unknown: я ещё в августе почти написал этот внутренний креатив, но меня немного нехватило докончить, я отвлёкся и всё зависло. С тех пор текст устарел, появилось много нового и интересного. Старые протоколы были сломаны, новые придуманы. Первый протокол был вообще без экстракторов — это я только потом понял, что без них не получится. Сейчас кое-как взял себя в руки, потратил ночь и довёл до ума. Новое добавлялось поверх старого, могут быть повторения и неконситентности в тексте, но я старался в меру сил. Сразу извиняюсь за то, что там много букв. Если gpg не расшифрует, сообщите. Инструкция: gpg -d, результат — ps-файл. Ссылка. Электронно подписано.

^*На самом деле, один из лучших трэшовых журналов. Из полного трэша это наименьший трэш, но у нас всем, что меньше PRA или PRA Rapid Communications, брезгуют, PRA — нижняя граница. Если результат нельзя пропиарить как очень существенный, то пойдёт в PRA, если можно — в PRL. Если очень круто и концептуально — в Nature-серию. Сейчас сделали очередную работу по каналам и гадаем, удастся ли её пропихнуть в PRL, и как её лучше пропиарить, чтоб повысить шансы на принятие (результат явно неубедителен на PRL, хотя и неплох). И когда смотришь, какую посредственность удаётся другим пропихнуть в PRL, желание отставать не возникает.

QDC, они просят не путать.

Нет, её там не было. Хотя wiki быстро пополняется всякой крипто-экзотикой, но там вроде до сих пор шумовое крипто отсутствует как класс.

Потому что Маурер ведущий специалист по этой теме. Даже Чаум когда-то этим занимался, был и его какой-то протокол, но сильно устаревший. Надо повспоминать кого-нибудь ещё.

Вот Information-Theoretic Key Agreement: From Weak to Strong Secrecy for Free к примеру, сразу глядите в картинку, чем экстракторы отличаются от универсальных хэш-функций.

Аналогично.

Спасибо, тоже интересная работа. Внизу на стр. 4:

we propose a generic procedure for amplifying the secrecy of any information-theoretic key agreement, requiring an amount of communication which is negligible compared to the length of the resulting key.

И у Реннера-Вольфа¹ на стр. 12:

However, the use of extractors (see Section 3.2) instead of universal hashing for privacy amplification allows to keep the fraction of channel uses for communicating the error-correction and privacy-amplification messages arbitrarily small.

Т.е. экстракторы всё равно рассматриваются в контексте коммуникаций между Алисой и Бобом. Т.е. ключевая проблема всех этих работ — дистиллирование секрета между Алисой и Бобом посредством коммуникаций через канал с подслушивающей стороной и/или при знании ими какого-то изначального секрета. В моём же случае эффективно выходит так, как будто бы Алиса посылает сообщение Бобу, но Боб вообще свалил за пивом и не слушает её, но, тем не менее, её всё равно слушает Ева. И как тут адаптировать техники, разработанные для совсем других сценариев, надо думать. Например, можно ли провести стандартный reconciliation, а потом сделать детерминистичный privacy amplification / deterministic extractor на обоих сторонах (Алиса и Боб) без коммуникации между ними?

Вроде бы для протокола с (детерминистичными ли?) экстракторами где-то пишут, что они всё равно требуют доступа к какому-то небольшому количеству «true random bits» / «catalyst randomness», недоступных атакующему и при этом заранее известных Алисе и Бобу:

Another randomness-extraction technique, which has attracted a lot of attention recently in the context of derandomization of probabilistic algorithms, are extractors, which allow, by using only very few additional truly random bits, for extracting a weakly random source's complete min-entropy. © Стр. 11.¹

---

Roughly speaking, an extractor allows to efficiently isolate the randomness of some source into virtually-random bits, using a small additional number of perfectly-random bits as a catalyst, i.e., in such a way that these bits reappear as a part of the almost-uniform output. © Стр. 13.²

Там про экстракторы якобы пишут следующее: экстрактор имеет два аргумента, где один — источник слабо безопасных случайных чисел (PRNG, доступный на частичное чтение атакующему?), а второй — некий небольшой секрет. Тогда, если атакующий имеет доступ только к источнику, но не имеет к секрету, владелец секрета может получить для себя из источника настоящие случайные (ε-безопасные) биты, используя экстрактор, причём информация атакующего об этих битах будет сколько угодно мала. При всём этом подчёркивается, что количество извлечённых из источника бит будет существенно больше, чем число бит в секрете.


Интересный параллелизм со стр. 3-4¹, где тоже жалуются:

Note that all previously described protocols--interactive or one-way--for authentication with a partially secret key work only under the assumption that the key is more than "half secret" [24], [17].

In contrast to privacy amplification over an authenticated channel, privacy amplification secure against active adversaries has so far been known possible only for keys offering a relatively high secrecy level initially (at least two thirds of the key should be unknown to the adversary), and the length of the extractable secret was only a small fraction of the key's entropy [14], [24], [17].

Our results can alternatively be interpreted as realizing encryption and authentication using private keys generated by weak random sources--instead of highly compromised keys--as studied in [18], [7]. In [18] it was shown that weakly random keys from certain sources with substantial min-entropy do not allow for information-theoretically secure (one-way) encryption; in [7], it was proven that a weakly random key allows for (one-way) authentication only if its min-entropy exceeds half its length. Therefore, the results of [18] and [7] suggest that not all private keys with substantial randomness--i.e., min-entropy--are useful for basic cryptographic tasks. This is true, however, only in the one-way communication model: Our results add to this picture by showing that if two-way communication is allowed (and perfect randomness is available locally), then keys from all sources with non-negligible min-entropy allow for both authentication and encryption.

Да, припоминаю, что пытался нагуглить статью в вики про шумовое крипто ещё тогда, когда мы его обсуждали с вами в прошлый раз, и был очень удивлён тому, что ничего не нашёл.

---

¹«Unconditional Authenticity and Privacy from an Arbitrarily Weak Secret».
²«Information-Theoretic Key Agreement: From Weak to Strong Secrecy for Free».

Опасаюсь, что наличие "true random bits catalyst" или "partially correlated random bits" и интерактивного двустороннего взаимодействия — принципиальное ограничение. Но надо перелопачивать тему.

Вопрос только в том, является ли мне нужная вещь экстрактором. Если нет, то не стоит экстраполировать на себя то, что известно про экстракторы. Если да, то опасаться нечего: кустарный экстрактор уже приведён.

Пусть Алиса имеет 1 бит, а Ева может угадать её бит с вероятностью ½ + ε, где ε ∈ [0,½]. Можно посчитать,³ что при этом Ева знает I(ε) бит информации о бите Алисы, где


Естественно, что I(0)=0⁴ и I(0.5)=1⁵. Пусть XOR не используется, Ева угадывает бит в 80% случаев, а длина ключа составляет 128 бит, тогда Ева знает nI(ε) = 128 I(0.3) ≈ 35.6 бит. Таким образом, только 92.4 бит = (128 – 35.6) бит являются для Евы секретом. Чтобы их подобрать, Ева вынждена совершить в среднем 2^92.4-1 ≈ 2^91.4 операций про брутфорсу ключа.

Давайте посмотрим, как работает вышеприведённая схема, когда применяется тот самый XOR-экстратор, и используется 5 бит для записи одного секретного бита. Если Ева угадывает каждый бит с вероятностью 80%, то она угадывает значение XOR от этих 5ти бит с вероятностью P₅(0.8) ≈ 0.54. Таким образом, для так закодированного бита Ева узнаёт только I(0.54-½) ≈ 0.0046 бит информации о нём. Т.е. в этом случае для 128 битного ключа Ева узнает лишь 0.0046⋅128 = 0.5888 бит информации о нём. Теперь, при желании Евы сбрутфорсить ключ ей придётся в среднем совершить примерно 2^128-0.5888-1 ≈ 2^126.4 операций по брутфорсу. Как видим, уже даже пятикратный XOR даёт хорошее приближение к безопасности. Итак, исходный текст был длиной 128⋅5 = 640 бит, из которых мы извелкли 128 бит информации, безопасность которых от Евы составляет 0.5888 бит.

Остаётся важным вопрос, поставленный там же: как оценить асимптотику P_n(p) при больших n? С ростом числа бит в XORе будет расти и число членов в обрезанном биноме, причём там коэффициенты — что-то типа C_n^k. К чему суммируются частичные суммы ряда, составленного из таких C_n^k, домноженных на степени p и ( 1 – p ), — не ясно. Решалась ли где-то такая «классическая» задача? Unknown, не могли бы вы её погуглить, когда у вас будет время, а то у вас намного плодотворней гуглёж получается по сравнению с моим.

---

³Используя, например, взаимную информацию между Алисой и Евой.
⁴Если Ева не знает ничего про бит Алисы и просто кидает монетку, пытаясь его угадать, то она не получает никакой информации.
⁵Т.е. если Ева угадывает бит с вероятностью 100%, то она знает 1 бит Алисы полностью.

Точнее говоря, было бы идеальным уметь обращать явную функцию x = P_n(p), т.е. находить по ней n = f ( x, p ) — число битов в XOR-строке, нужных для угадывания XOR-значения с вероятностью x, при условии, что противник угадывает каждый бит с вероятностью p. Что-нибудь известно про такую обратную функцию в комбинаторике/криптографии?

Вроде бы для протокола с (детерминистичными ли?) экстракторами где-то пишут, что они всё равно требуют доступа к какому-то небольшому количеству «true random bits» / «catalyst randomness», недоступных атакующему и при этом заранее известных Алисе и Бобу:

Нет, не требуется, есть seeded экстракторы, а есть полностью детерминированные.

В моём же случае эффективно выходит так, как будто бы Алиса посылает сообщение Бобу, но Боб вообще свалил за пивом и не слушает её, но, тем не менее, её всё равно слушает Ева. И как тут адаптировать техники, разработанные для совсем других сценариев, надо думать.

Судя по приведённым ниже материалам есть экстракторы и под вашу задачу. Боб может идти за пивом.

Опасаюсь, что наличие "true random bits catalyst" или "partially correlated random bits" и интерактивного двустороннего взаимодействия — принципиальное ограничение. Но надо перелопачивать тему.

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

С ростом числа бит в XORе будет расти и число членов в обрезанном биноме, причём там коэффициенты — что-то типа C_n^k. К чему суммируются частичные суммы ряда, составленного из таких C_n^k

Решалась ли где-то такая «классическая» задача? Unknown, не могли бы вы её погуглить, когда у вас будет время, а то у вас намного плодотворней гуглёж получается по сравнению с моим.

Yao's XOR Lemma?

В любом случае, делать на ней экстракторы уже не модно.

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

Ну и весь препринт монографии теории псевдослучайности от этого автора тоже доступен.

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

Условия существования детерминированных экстракторов:

We observe that no deterministic extractor exists if the sampler is allowed to use more computational resources than the extractor. On the other hand, if the extractor is allowed (polynomially) more resources than the sampler, we show that deterministic extraction becomes possible. This is true unconditionally in the nonuniform setting (i.e., when the extractor can be computed by a small circuit), and (necessarily) relies on complexity assumptions in the uniform setting.

Интересно, что одноразовый блокнот при определённых условиях — пример детерминированного экстрактора.

Отсюда выводятся и схемы разделения секрета, например гаммы R₁, R₂, … R_n могут быть перексорены для создания общей гаммы и розданы разным людям, а некий секрет зашифрован этой гаммой. Для расшифрования все гаммы должны быть снова собраны вместе и снова перексорены. Если хотя бы одной не хватает или кто-то её испортил, то секрет останется информационно-стойко зашифрованным.

Популярно также информационно-стойкое разделение секрета по Шамиру, которое позволяет выбрать сколько хранителей m из n могут собрать секрет. А кто-то предлагает и проактивное разделение, на случай, если противник будет охотиться за секретами.

Так что, информационно-теоретические протоколы существуют, но хорошего обзора всё никак не найти.

Unknown, огромное вам человеческое спасибо! Последняя информация от Вас послужила последней каплей и ключевые слова были найдены. Теперь у меня появилась почти полная уверенность в том, что я в курсе всего, что и кем было сделано в моём направлении, а что не рассматривалось. Как гласит народная мудрость, «сколько ни старайся, сколько ни пытайся быть оригинальным, учиться и думать нестандартно, всегда найдётся конкретный индюк, который сделает это раньше тебя, быстрее тебя и лучше тебя».

Что касается конкретно экстракторов... э-э-э, я недооценил масштаб катастрофы. Реальные экстракторы, используемые в проблемах такого класса, очень нетривиальны — теорема Дворецкого, геометрический/асимптотический функциональный анализ, в одном шаге от Гротендика и фундаментальной математики. Как Вам такой экстрактор? Собственно, результат 2006-2007г.

Второй индюк, который всё это применил и решил целевую задачу, также локализован. Сейчас следствие разбирается, как далеко он зашёл (а зашёл он очень далеко). В частности, первая статья в этом направлении — 2004г, основные результаты — 2010г, адаптация под криптографию — 2011г. Диссер по этим результатам защищён 4 месяца назад, и сложность там впечатляет. Естественно, руководство всем этим делом, как и инициация идей шла от теоретиков, которые первые из первых в мире, их фамилии у всех на слуху. Короче, поздно я раскачался.

Есть некоторая надежда, что протокол под мою задачу напрямую не следует из его результатов. Во всяком случае, заземление в практику в диссере у него только через бит-коммитмент. Как и следовало ожидать, большая часть того, что я успел нарыть, а также большая часть предсказаний и обобщений там рассмотрены. Всю ночь читал статьи и бился головой об стол: именно то, что я предполагал, и использовалось: и leftover lemma там, и ε-экстракторы и позиционирование как криптопримитива, который может использоваться в более сложных протоколах.

Но что меня больше всего во всём этом потрясло — это тот факт, что квантовое шифрование может быть эффективным: при шифровании n бит с безусловной безопасностью требуется, оказывается, ключ длиной всего-то в полиномиальный логарифм от n, представляете?! Впрочем, там есть некоторые тонкости, которые стоит обдумать... т.е. не факт, что такой полиномиальный логарифм целесообразен для моего случая. Тем не менее, сам факт того, что люди не только предъявили какой-то один протокол, но и строго доказали его оптимальность (универсальная граница после оптимизации по всевозможным типам операций, измерений и пр.), впечатляет. Чувствую, что если попрёт в таком духе, то твёрдотельные накопители на каких-нибудь спинах с встроенным шифрованием — вопрос недалёкого будущего, т.е. квантово шифроваться будут не только коммуникации, но и хранение полученной информации.

В общем, полчилось то, чего и следовало ожидать: если идея на поверхности, её моментально расковыряют. Я пока пребываю в глубоком трансе. Как соберусь с мыслями, напишу детали. Пока что есть небольшая надежда, что ещё не всё расковыряли, хотя обещанной «смены парадигмы», конечно, уже не будет 100%. Мировые новости молчат про смену парадигмы полиномиальный логарифм в применении его к криптографии, да? :)

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

Причём в качестве пароля можно будет использовать кличку собаки или слово из словаря. На стойкость системы в целом это слабо повлияет. Чем не направление для смены парадигмы?

Нет, с кличкой собаки вряд ли заработает — нужна тру рандомность :) И ещё поди наверняка нужна запутанность, технологичность которой в больших масштабах тоже под вопросом.

Где-то потерял ссылку, как этим летом в лабораторных условиях испытывали квантовую память. Сначала, как я понимаю, традиционно охлаждали материал до низких температур, а затем подняли до комнатной и при комнатной температуре память держалась около 40 мин. Причём, материал использовали какой-то доступный (кремний с фосфором?).

Оно много где было (например, здесь). Всё бы ничего, но кубитов там «10 billions», и все в одинаковом состоянии ⇒ для спецзадач не годится (для квантовых вычислений и просто памяти, может, и подошло бы, не знаю). Декогеренция — 39 минут при комнатной температуре и 3 часа при криогенных температурах.

/comment58879:

Вместо квантового распределения ключей (QKD) возможна непосредственно прямая передача секретных сообщений по квантовому каналу со взаимной аутентификацией QDC — Quantum Direct Communication.

/comment58935:

Deterministic QKD — интересная мысль, надо поспрашивать народ

Вчерашний диалог с начальством в столовой:
— Я тут внезапно услышал про такую вещь, как детерминистичное QKD. Странно, что никто никогда про такое мне не рассказывал, это что-то интересное?
— Детерминистичное QKD? Нет, не слышали.
— Несколько статей есть на тему, какие-то китайцы, статья в Fisica Scripta...
— Китайцы в Fisica Scripta? А-ха-ха :) Нет, мы бы такое даже не стали читать.

Нет, я не буду таким категоричным, надо всё же посмотреть на работы, как время будет. Да и Реннер рассматривает что-то очень похожее, но при этом использует чуть другой термин.

/comment58938

Детерминистичное QKD

QDC, они просят не путать.

И вот теперь египтяне: Quantum Secure Direct Communication using Entanglement and Super Dense Coding.

Quantum secure direct communication (QSDC) (Bostrцm, 2002, Deng, 2008) is another branch of quantum cryptography. Different from QKD, QSDC allows the sender to transmit directly the secret message (not a random key) to the receiver in a deterministic and secure manner. If it is designed carefully, a QSDC protocol can also attain unconditional security (Deng, 2003).

The main objective of our research is to introduce a new protocol that guarantees more security of the transmission than the QKD and also saves more time, cost and gives more efficiency for the transmission, as it is using the super dense coding technique that transmit two classical bits by sending one quantum bit. In our protocol of the quantum secure direct communication we use the maximally entangled Bell states to encode the message bits on the basis of the super dense coding theorem, and then transmitting them on two quantum channels to the other side with less probability of the eavesdropping, and with no need for a pre-shared key that in turn needs many rounds to distribute, and also a public discussions to verify the correctness of the key.

Тем более, кто-то ☺ здесь недавно ссылки на кодирование в квантовом канале приводил, а в QDC используется как раз "The super dence coding procedure".

Also, for efficiency purposes super dense coding is used, which is also based on entanglement, to double the transmission speed by sending two classical bits over one quantum channel. This protocol uses one step or one pass to end the message in a secure manner.