Инструмент для детектирования шифртекста
Доброго дня! Может кто подскажет...
Исходные данные – блок данных относительно небольшого размера – единицы/сотни килобайт
Задача – определить с высокой вероятностью, является ли данный блок шифртекстом.
Предполагаемое решение:
поскольку одним из требований к шифртексту является "вероятность появления 0 и 1 равны 0,5, причём значение каждого последующего бита не зависит от предыдущих", отличить шифртекст от открытого текста можно по статистике появления 0 и 1, их пар, троек и т.д. Это все интуитивно понятно.
Вопрос:
Нужны ссылки на алгоритмы (может быть opensource реализации) подсчета битовой статистики, а также критерии, по которым принимать решение "открыто/зашифровано".
Заранее спасибо
комментариев: 9796 документов: 488 редакций: 5664
И почему для того, чтобы сделать такую вроде простую вещь, как вменяемое дополнение для RSA-подписи, нужно нагородить дикую конструкцию в виде сети Файстеля из хэшей (сейчас это RSA-OAEP), потому что SHA-2 не проектировался как RO. А SHA3/Keccak решает многие из этих задач сам по себе, потому как максимально близок к RO.
[оффтопик]
[сопли]
[«помогите решить задачу»]
Это всё очень сложные вещи :) Я хотел для себя решить задачу, которая в тысячи раз проще, чем эти протоколы. Поначалу она казалась совсем пустяковой, решаемой на коленке. Чуть позже я поглядел, как подобные задачи решаются в криптографической литературе и увидел, что всё совсем не так просто. Ходил по ссылкам, гуглил, рыл по ключевым словам, но так нигде и не нашёл решение своей задачи. Есть статьи, подходящие очень близко к тому, что надо, но это всё равно не то или попросту неприменимо для нужных параметров. В конце концов, я нарыл какие-то вменяемые обзоры и диссертации, но там всё настолько сложно, что хочется выть. Если сюда добавить осознание того, что хотя литература и открыта, никто, кроме авторов нужного направления в криптографии не понимает, что там происходит... а там сотни статей, в них можно утонуть насмерть и никогда не выплыть :( Наверное, всё, что можно сделать в таких случаях — прорыть топик на обозримую глубину, формализовать задачу на понятном всем языке и
нанять специально обученных людей под её решениепоискать содействия в соответствующих кругах. Но вообще это жутко — осозновать, что количество человек в мире, хорошо понимающих нужные вещи, можно пересчитать по пальцам, а другие заведомо ничего дельного не скажут :( Да и те, кто могут сказать, могут попросту не захотеть помогать или консультировать.Например, реально ли без криптографического или CS образования разобраться с жизнерадостной криптографией? Пытался смотреть диссер Евгения Додиса, которого вы упоминали здесь. С первого нахрапа
мало чтоничего не получилось. Пока гуглил, заметил, что автор, в отличие от своего коллеги, старается не афишировать знание русского, но домашняя страница всё же содержит некоторые утечки, да и профиль на линкедине говорит о молдавском происхождении, хотя есть и иные мнения. Метод огораживания от входящих писем заслуживает отдельной ссылки — unknown, это у всех криптографов так, или просто сказывается студенческая специфика в штатах? Боязно писать таким людям, вдруг ещё неправильно поймут.Лефтовер-хэш-лемма1 гарантирует нам: Золотые слова, аж зачитываюсь! Но покажите мне один, хотя бы один алгоритм, который генерирует нам такой новый секретный ключ, когда к атакующему уже утекло 99% битов от старого ключа (исходный ключ может быть выбран произвольно большим). Все алгоритмы, что видел, работают либо только для фиксированного числа утекших бит, а не процентного, либо для малого процента утекших бит. Мои требования просты:
- Экстрактор должен быть детерминистичным2.
- Безопасность —
Unknown, скажите, я хочу от криптографии невозможного?информационно-теоретическая3ε-безопасность4.Если я всё правильно понял, в криптографии эта проблема называется «(deterministic) bit/block/entropy/randomness extraction problem», а все ноги растут из двух работ: «The bit extraction problem or t-resilient functions» с Голдрайхом в соавторах и «Experimental quantum cryptography»5, позже доделанной до «Practical quantum oblivious transfer», с Беннетом и Брассардом. Причём последние активно ссылаются на Голдрайха, а Голдрайх (вроде бы) на первых, но видно, что и те и те работали независимо. Позже к ним присоединился Маурер («Secret key agreement from public discussion from common information», Trans. Inf. Theory 1993), а Беннет с Брассардом формализовали, что хотели сказать, в «Generalized privacy amplification» (Trans. Inf. Theory 1995). Есть ещё одна из самых первых работ — «How to Reduce your Enemy’s Information», но мне не удалось ни найти её в свободном доступе, ни скачать по подписке. Всё вышеперчисленное — классические работы, на которые все позже многократно ссылаются. Видимо, Додис и другие появились позже, вырастив из этих работ обширную область исследований, но уже применительно не к QKD, а скорее как метод защиты от side-channel-атак и для выполнения криптографических операций в физически плохо изолированных приборах, т.е. где атакующий может много чего подсмотреть касаемо информации о ключах, состояниях шифров и т.д.
В вышеупомянутой работе Голдрайха на стр. 3 написано что, казалось бы, ровно то, что нужно, но дальше авторы приводят формулу для числа выводимых секретных бит: n – t log2n, что для 99%-ой утечки ключа неприменимо. Там же на стр. 6 XOR-лемма есть (её почему-то очень любят во всяких таких работах по экстракторам), но в гугле по поводу XOR-леммы пишут что-то вообще сложное и многостраничное, хотя у Голдрайха она сформулирована как простое и полуочевидное утверждение.
Вышеупомянутая «Practical quantum oblivious transfer» повергает меня в шок и ужас. Авторы буквально издеваются над читателем. Я таких препринтов ещё не видел, а скачать оригинал возможности нет. Препринт начинается тихо и мирно, как любая формальная статья, но потом начинают отовсюду лезть сюрпризы:
- На 10ой стр. доказательство приведено «in sketch» и неполно.
- На стр. 13ой они пишут
Охренеть! Да конечно же, я understand. Они не знают, как изложить своё доказательство, чтобы всем было понятно, а читатели конечно же будут understand — им-то деваться некуда.
- Дальше идёт параграф «for your eyes only», что символично.
- На 20ой стр. они не нашли ничего умнее, чем поставить ссылку [31], по которой написан на французском тот самый бородатый анекдот про Ферма «поля слишком узки, чтобы доказательство поместилось на них». Узость полей — классный аргумент.
В общем, авторы — редкостныемувесельчаки, но понятности от этого не прибавляется.Среди недавних работ есть «Key Derivation and Randomness Extraction» от Chevassut'а, где обсуждается Лефтовер-хэш-лемма (стр. 3), универсальные хэш-фунции (стр. 8) и, самое интересное, «deterministic extractor» (стр. 11). И ещё есть интересный свежак «Non-Malleable Condensers for Arbitrary Min-Entropy and Almost Optimal Protocols for Privacy Amplification», где обсуждаются всякие разные виды экстракторов.
Что касается диссера Додиса, меня внизу 31ой стр. смущает фраза т.к. она кажется конфликтующей с той самой статьёй Реннера и Маурера3, т.е. такое вроде бы невозможно6. Или дело в том, что у Реннера ε-безопасность, а у Додиса — почти всюду вычислительная? У Додиса дан действительно неплохой обзор, но в основном он, как я понял, занимается конструированием вещей, которые лишь вычислительно безопасны7, но не более того.
Есть ещё куча хороших относительно свежих работ по усилению конфиденциальности в конвенциональном QKD-смысле. Они интересны, чтобы уловить какие-то концепты, но вряд ли чем-то конкретным помогут. В части протоколов, как я понял, стадия усиления ещё и происходит чуть ли ни одновременно с исправлением ошибок. Кроме того, там основная задача — вывести общий секретный ключ между сторонами через прослушиваемый канал, пользуясь тем, что взаимная информация между Алисой и Бобом больше оной между Евой и Алисой или Евой и Бобом, но всё это — не мой случай. Наконец, как я понял, все протоколы для усиления конфиденциальности в QKD не являются детерминистичными: Алиса берёт случайные (хэш-)функции из набора, применяет их, потом говорит Бобу, какую функцию она применила — как-то так, что ли, детально не разбирался.
Есть ещё работа «Security Amplification for Interactive Cryptographic Primitives». Интересно, оно имеет какое-то отношение к privacy amplification? На мой поверхностный взгляд — вроде бы нет. Работа грузная, сходу смысл непонятен.
Я интуитивно понимаю, что лефтовер-хэш-лемма верна: если атакующий ничего не знает про достаточно большое (по абсолютному числу) количество бит в ключе, а легитимный владелец ключа знает все биты, то у владельца есть существенное преимущество, что позволяет ему «схэшировать» исходный ключ в меньший, но почти (ε) безопасный. Т.е. если атакующий не знает, допустим, 500 бит из ключа длинной миллион бит, для него это фатально: никак он эти 500 бит не восстановит. Вся трудность — только написать экстрактор, который будет детерминистичной функцией, из которой будет следовать ответ на вопрос: по значению ε и процентному числу бит, известных атакующему, найти, какой длины должен быть исходный ключ, чтобы ужатый ключ имел заданную длину и при этом являлся ε-безопасным по отношению к атакующему.
Для простоты можно сначала рассмотреть ситуацию, где атакующий не знает, какие именно биты в ключе им получены верно, но при этом знает общий процент битов, которые у него верны (типа 99% от общего числа). В более общем же случае можно рассмотреть ситуацию, при которой атакующий знает t «абстрактных» (т.е. в шенноновском смысле) бит информации о ключе длиной n бит.
Unknown, есть ли выход из положения?
1Leftover в этом названии — фамилия или просто английское слово такое?
2Плакали все методы усиления конфиденциальности (privacy amplification), разработанные для QKD-протоколов и основанные на «универсальных хэш-функциях».
3Спасибо Реннеру и Мауреру, плакала горькими слезами информационно-теоретическая безопасность. Но это не страшно, страшно — это если вдруг ε-безопасность обесценится до уровня вычислительной, вот тогда — да, лавры Визнера уже не видать никому и никогда :(
4Если я правильно понял ссылку, то это означает, что атакующий всегда будет знать какую-то долю информации о ключе, но её всегда можно будет сделать сколь угодно малой (хоть и конечной). Точнее, ключевая часть статьи вообще не понята, надо сидеть и вникать, а не фантазировать.
5J. of Crypt., 1992. Статья достаточно понятно написана, для людей и без зауми. Для уяснения основ QKD — самое то.
6Даже в QKD, где нет требования детерминистичности выводимого ключа.
7А это не то, что мне сейчас надо.
[/«помогите решить задачу»]
[/сопли]
[/оффтопик]
Подсказывают, что можно разбить исходный ключ на блоки длиной сколько-то бит, а потом взять XOR от всех битов внутри блока.
У Голдрайха в статье про t-жизнерадостные функции внизу стр. 4 есть «block extraction problem», которая обобщает такую идею, но не понятно, следует ли как-то оттуда (косвенно) решение для целевой задачи — случая произвольного процента (<100%) бит ключа, утекших атакующему. Голдрайх, видимо, просто присваивает каждому блоку некоторое значение бита некоторым способом и затем переформулировывает исходную проблему в терминах бит, соответствующих уже целым блокам.
Большинство тех западных "авторов" и "британских ученых" выдают на гора такие "работы", что порой уже видится злой их умысел чтобы затормозить развитие науки в этой области в других странах, которые молятся на них: "вон на западе, а что мы тут, мы тут лохи, а вот они...". (когда же требуется сделать что-то стоящее – эти "авторы" вдруг начинают писать совсем понятным языком, и решают вполне адекватные задачи, вдруг :) )
комментариев: 9796 документов: 488 редакций: 5664
И даже этих образований м.б. недостаточно. В крипто могут возникать тренды на потребу сиюминутным потребностям индустрии или из желания предвосхитить эти потребности с на ходу придумываемой терминологией и понятиями. Могут развиваться крайне экзотические направления и пр. Уже даже трудно решить, что считать базовым обязательным уровнем для всех.
Даже если вы для них неавторитетны, письмо скорее всего прочтут и что-то ответят, если в нём есть интересное для них предложения, а не просьба. Если есть почти готовая идея очень подходящая к их тематике, сообщение об опечатке или очевидной ошибке в их работе. И чтобы основная идея письма была понятна с первых строк и был хороший профессиональный стиль написания. Тогда шансы есть.
Исходя из общих соображений, с детерминистичными протоколами всегда всё намного хуже и сложнее, чем с рэндомизированными. Это также, как попытка заменить аутентификацию на non-malleability.
Лучше рэндомизировать и аутентифицировать везде, где можно.
P.S. Я специально не занимался экстракторами, но когда то я их совсем не осилил и полностью завалил это направление.
За пределами моей текущей компетенции, надо серьёзно прорабатывать вопрос.
Очень похожую работу встречал и также не осилил. Метода не понял. Названия, авторов, ключевых слов не помню.
Такие работы практически не читаю. Как-то не попадают в сферу интереса.
Они свою науку при этом тормозят сильнее, а на другие страны им начхать. Причины и механизмы другие. Самый известный выметатель сора из избы по этой тематике — Нил Коблиц.
Рэндомизация тут, к сожалению, будет бессмысленной из-за самой постановки задачи. Теоретически можно использовать исходный небезопасный ключ для симметричного шифрования, что соответствовало бы тому, что мы сгенерировали пароль какой-то длины, раскрыли часть символов/битов пароля атакующему, но если пароль достаточно длинный, он всё же достаточно безопасный. Т.е. оставшихся битов может быть так много, что атакующий физически не сможет их сбрутфорсить. Есть ли такие симметричные блочные шифры, куда на вход можно подать такой «небезопасный» пароль большой длины — намного больше, чем 512 бит?
Я хотел получить «универсальный» ящик, который выдаёт ключ заданной длины, удобный для последующего применения в качестве ключа для стандартного блочного шифра, т.е. ключ со стандартной длиной и стандартной безопасностью. Далее такой шифр можно использовать, например, для дискового шифрования.
Хорошо, попробую.
У меня даже нет 100%-ой уверенности в том, что эта задача именно на экстрактор — я так решил, но это не истина в последней инстанции. Обычно экстракторы используют для извлечения рандомных данных из источника, где часть битов неслучайны или подконтрольны атакующему. В моём же случае данные нужны нерандомные — нужно детерминистично извлекать заданную битовую строку, выглядящую для атакующего случайно, если только он не знает её заранее. Вроде бы это подходит под критерий детерминистичного экстрактора.
Печально.
Неужели такая задача достаточно сложна даже для Вас? Есть ещё пара человек, которых можно спросить, но потом останется разве что письма слать :(
Из выше процитированных работ есть вполне неплохие, написанные предельно понятно, но они не по решению той задачи, что мне нужно. Из них можно равзе что общие идеи почерпнуть.
комментариев: 9796 документов: 488 редакций: 5664
Keccak, но это хэш, а не шифр (хотя он много что потенциально в себе таит) и его стойкость как и любого алгоритма в цепочке преобразований размер пароля → размер внутреннего состояния → размер выхода будет ограничена самым узким местом из этих трёх звеньев. Вам бы ещё не хотелось ведь и упереться в чисто вычислительную безопасность, я так понимаю? Иначе вы докажете, что стойкость системы с квантовым каналом всего лишь равна стойкости Keccak.
Вообще, для многих протоколов хорошо бы иметь ещё более универсальную штуку, чем Keccak — шифр/хэш с произвольным размером блока включа, внутренних состояний, входов/выходов и пр. параметров.
Является, но я там плаваю даже в терминологии. Из-за непонимания требований к моделям в том числе.
Бывает синтетическая энтропия, например синтетические векторы инициализации. Но это всегда компромисс, рискованно и хуже доказуемо в плане безопасности.
Да, всё верно. Я хотел сказать, что есть тысячи протоколов, в которых имеется вычислительная безопасность, и которые никому не интересны кроме нескольких человек, которые их разработкой занимаются — взять хотя бы тот же неидеальный бит-коммитмент. И совсем другое дело — предъявить протокол, который даёт безусловную (unconditional) безопасность для какой-то задачи при том, что ни один чисто классический протокол не может быть безусловно безопасным. Как много есть вещей в криптографии с безусловной безопасностью? Я не могу припомнить ничего, кроме одноразового блокнота. Конечно, если совсем никак, то пусть лучше будет вычислительно безопасный протокол, чем вообще никакого.
Ещё у меня создаётся впечатление, что классическая криптография, созданная для обслуживания классических частей QKD и т.п. протоколов вообще слабо контачит с конвенциональной криптографией, которой занимаются обычные нормальные криптографы. Т.е. как только возникает соответствующая классическая задача, вдруг сразу оказывается, что именно её ещё никто не решал, хотя чем-то похожих работ — тонны.
Может быть, когда-нибудь мы доживём и до такого.
Вообще, я тут подумал, направление мысли кажется интересным. Более того, в «P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma» (стр. 2) пишут
А в «On Yao's XOR-Lemma» на стр. 1 пишут
Т.е. смысл вроде как таков: какая бы ни была функция, преобразующая биты, если атакующий не знает некоторую часть битов, с ростом числа битов результат XOR'а значений функции стремится к случайному. В литературе рассматривают функции, имеющие корреляции, и показывают, что даже для этих случаев всё можно сделать безопасным. Метод применяется, как правило, для конструирования PRNG.
P2(p) — чёрный, P3(p) — синий, P4(p) — малиновый, и P5(p) — красный.
Исходя из вышеозвученных идей, можно на коленке сделать простой детерминистичный экстрактор:
Факт 1:
Факт 2:
P 3(p) = p3 + 3 p ( 1 – p )2.
P 4(p) = 6 p2 ( 1 – p )2 + p4 + ( 1 – p )4.
P 5(p) = 5 p ( 1 – p )4 + 10 p3 ( 1 – p )2 + p5.
Экстрактор:
Вопрос:
Unknown, как вам такой метод на ваш криптографический вкус? Вы заставили меня об очень многом подумать своими прогрессивными идеями. Или это первый
блинэкстрактор комом?*Как правильно переводится circuit на русский язык? Повсюду встречаю это слово. Циклы? Раунды? Что это примерно значит?
**Кто-нибудь киньте ссылку на википедию или статьи, где можно об этой задаче почитать. Наверняка ведь кто-то уже это решал лет 40 назад...
комментариев: 11558 документов: 1036 редакций: 4118
Выбирайте. :)
комментариев: 9796 документов: 488 редакций: 5664
Вы там готовите смену парадигмы? Т.е. вот это и это всё внезапно устарело? И так больше аутентифицировать в квантовых каналах нельзя? Или канал какой-то особенный, не такой как у всех?
А вот это не подходит?
Хотя вот ещё что-то такое гуглится. Вместо квантового распределения ключей (QKD) возможна непосредственно прямая передача секретных сообщений по квантовому каналу со взаимной аутентификацией QDC — Quantum Direct Communication.
P.S. Исправил во всех своих предыдущих комментах malleability на non-malleability. Вы поняли термин совершенно правильно, ещё в первом своём вопросе, а не заметили, что меня чего-то переклинило по названию в обратку.
А что, нельзя? Спасибо за ссылки, я их попозже посмотрю. Deterministic QKD — интересная мысль, надо поспрашивать народ, посмотреть ссылки, может оттуда какие-то детали будут полезны.
Встроенный
пунто-свитчерметод коррекции ошибок делает шум в канале ненаблюдаемым, бывает такое. По той же причине возникает и слепота на собственные опечатки :)Основная мысль: то, что нужно — не решение задачи на распределение ключа. Также, это не задача на создание квантовых защищённых банкнот или квантовых билетов, не задача аутентификации, и квантовые каналы ко всему этому отношение имеют очень опосредованное8. С другой стороны, моя задача чем-то очень похожа на все из вышеперечисленных, но не сводится целиком ни к одной из них. Соответственно, взять и сослаться на анализ, уже проведённый в других работах, не получится — в лучшем случае можно творчески осмыслить существующие доказательства, чтобы их адаптировать для своего случая.
Наконец, поскольку задача новая, и никто её раньше не ставил и не решал9, официального названия у неё тоже нет, а какие-то из мной желаемых названий уже недавно кто-то даже успел украсть для своих задач. Конечно, не стоит себя тешить иллюзиями: на уровне «озвучить идею, чтобы потом послать её в очередной говёный журнал с недодоказательством» могут тысячи людей, ничуть не более глупых, чем я. Тут вся соль — в самой постановке такой задачи, для чего надо иметь очень извращённое воображение и долго тусоваться на pgpru, слушая IRL-проблемы других :) Всё это можно будет потом отдельно обсудить, где-нибудь за закрытыми дверями и без
прессылюбопытных раньше времени глаз. Жаль, SATtva так и не сделал поддержку PGP-шифрования форумных сообщений.Хотя порой кажется, что уже всё где-то решено, когда начинаешь смотреть близко, оказывается, что точь-в-точь то, что нужно, никто детально не анализировал и безопасность не доказывал. Например, захотел я узнать решение для оптимального bit value discrimination для стандартного BB84, но нигде не нашёл, хотя есть работа/диссер, где это рассматривают для BB84, сформированного когерентыми состояниями10. Может быть, для стандартного исходного BB84 эта задача где-то и решена, но я не дорылся.
Что ещё важно, на демонстрационном уровне мне не хочется заморачиваться запутанными состояниями, неравенствами Белла и прочим11 — всё это намного менее технологично, чем обычные независимые кубиты. Потенциально можно обобщать на другие задачи и подходы, какие-то идеи уже имеются на этот счёт, но это на будущее. Пока хочется очертить задачу чем-то простым и минимальным и показать безопасность хотя бы для неё.
Ну и, если серьёзно, время поджимает. Не опубликуешь вовремя сам — до этого додумаются и опубликуют другие (если ещё не). В последних работах, в том числе по эксперименту, уже совсем вплотную подошли к тому, что нужно, им лишь немного не хватило додуматься до «идеи». И я рассчитывал, что отставание теории от эксперимента тут имеет запас хотя бы лет 5-10 минимум, но когда я прочитал про «время докогеренции — 1 секунда при комнатной температуре», очень серьёзно задумался12. Понимаете, что такое 1 секунда? Это очень много на фоне того, как сейчас всякую экзотику13 делают — там времена порядка нескольких микро/наносекунд.
8Поначалу даже думал, что вообще не имеют.
9Мои поиски как по классической, так и по квантовой литературе успеха не потерпели.
10Т.е. де-юре это QKD в дискретных переменных, а де-факто там эти дискретные переменные модулируются непрерывными, т.е. название «BB84» там отражает только аналогию.
11По вашим ссылкам всё это есть.
12И те, кто это делает, говорят в том числе на русском. Сильные русскоязычные (хотя многие этого не афишируют, работая в зарубежных группах) есть практически во всех квантовых тематиках. Они могут читать этот форум, но никогда не говорить об этом. Уши буквально повсюду.
13Типа квантовых подписей/аутентификации/вычислений с требованием слепоты.