Оцените блочный шифр
Шифрование========================= a: 01 02 03 04 – Исходные данные.
b: 05 06 07 08 – Пароль.
c: 56 08 30 64 – Случайные данные.
d: 61 14 37 72 – Произведение случайных данных и пароля.
e: 62 16 38 76 – Произведение исходных данных с случайными.
f: 61 14 37 72 62 16 38 76 – Зашифрованные данные.
; Ключ сохроняем простым дописыванием перед шифротекстом.
Расшифрование========================= f: 61 14 37 72 62 16 38 76 – Зашифрованные данные.
g: 61 14 37 72 – Отделяем ключ (первые четыре байта).
b: 05 06 07 08 – Минус пароль.
c: 56 08 30 64 – Получаем случайные данные.
f: 62 16 38 76 – Вычитаем из шифротекста случайные.
a: 01 02 03 04 – Получаем исходные.
В практической реализации размер ключа можно существенно увеличить, как и кол-во проходов. Каждый раз шифруя одинаковый текст одинаковым паролем выход будет разный. Какие недостатки у данного шифра если предположить что длинна ключа равна 256-бит а кол-во проходов 32, а блок подмены достаточно псевдослучаен?
Ссылки
[link1] https://www.pgpru.com/biblioteka/osnovy/vvedenievkripto/glava2/hanaanskijjbaljzam
[link2] http://www.nicolascourtois.me.uk/
[link3] http://www.cryptosystem.net/aes/
[link4] http://www.math.washington.edu/~koblitz/
[link5] http://www.nicolascourtois.com/papers/frontmaths_krakow.pdf
[link6] http://bash.org.ru/quote/165286
[link7] http://www.quadibloc.com/crypto/co040308.htm
[link8] http://ru.wikipedia.org/wiki/Равенство_классов_P_и_NP
[link9] http://www.cs.umd.edu/~gasarch/papers/poll.pdf
Рандомизированное хэширование? В данном случае непрактично.
Ну у вас тут для наглядности сложение по модулю 256, можно было бы и простой xor сделать
d = b + c (mod 256)
e = a + c (mod 256)
f = d || e
Возьмём два блока:
d_1 – e_1 (mod 256) = b_1 – a_1 (mod 256)
d_2 – e_2 (mod 256) = b_2 – a_2 (mod 256)
Но пароль то общий для всех блоков:
b_1 = b_2
d_1 – d_2 – e_2 – e_2 (mod 256) = a_1 – a_2 (mod 256)
Получаем разность исходных текстов между блоками, рандомизирование не сделало эту разность случайной и исходный текст вскрывается статистическим анализом.
Про стойкость к известным и подобранным тестам говорить не стоит.
Число раундов ничего не изменит: все операции линейные.
До размера исходного текста и больше одного раза не использовать :-)
Эх, не криптограф я конечно, но что-то мне напомнило в этом примере давно описанную Циммерманом историю[link1]
Это конечно не камень в Ваш адрес, а просто интересная информация
Да одинаков.
Пожалуйста поясните.
Я не претендую на создание серьезного блочного шифра
Последняя строка должна конечно выводиться вот-так:
(d_1 – e_1) – (d_2 – e_2) (mod n)= (b_1 – a_1) – (b_2 – a_2)(mod n)
d_1 – e_1 – d_2 + e_2 (mod n) = b_1 – a_1 – b_2 + a_2(mod n)
Т.к. пароли одинаковые, то b_1 – b_2 = 0
А разность между открытыми текстами в блоках можно вычислить по d и е:
a_2 – a_1(mod n) = d_1 – d_2 – e_1 + e_2 (mod n)
С точки зрения современной криптографии шифр взломан: происходит полная утечка разностей открытого текста в шифртексте: всю информацию об открытом тексте
Вы выдаёте противнику.
Пусть размер ключа (пароля) и ширина блока (n) – даже неизвестны. но их число небольшое, легко перебрать на компьютере от 0 до тысяч битов.
Ведь мы перебираем не сами ключи (2n), а их вероятный размер n.
В стойком шифре никаких разностей открытого текста в шифртексте быть не может. Но в данном случае, перебирая все значения n, мы найдём такое n, при котором
разности a_2 – a_1 (mod n) будут существенно отличаться от случайных значений. Так мы найдём n. Затем можно составить таблицу разностей частот
скажем для английского или русского теста или вероятных щифруемых заголовков или последовательностей ascii-символов
и попробуем найти блоки с подходящими разностями. Так мы найдём хотя бы в одном блоке a_1, тогда b_1=d_1 – c_1 mod (n).
Если угадали точно, то такой пароль/ключ теперь можно извлечь из любого блока для сравнения, ведь все значения b должны быть равны и вскрыть всю шифрограмму.
Если шифр элементарно вскрывается только на основе шифртекста, то о нём лучше сразу забыть. Ведь настоящий шифр должен быть устойчив к гораздо более
сильным атакам: например с известным открытым текстом (если противник знает хотя бы один блок со значением "a", то нахождение "d" для него ещё более тривиально).
Устойчивость к подобраным открытым текстам тоже обязательна: если зашифровать одни нули, то он тоже должен быть стоек, в отличие от того, что
Вы предлагаете. Я уже не говорю про связанные ключи и устойчивость к серьёзным видам криптоанализа.
Тип обратимой операции неважен, взлом будет примерно такой же, чтобы Вы не выбрали для своей схемы: сложение по модулю любого числа, XOR – это всё линейные операции, сами по себе для шифрования непригодные, если не используются в составе специально подобранных конструкций (блоков диффузии, нелинейного смешения операций разных алгебраических групп и т, д, )
Попытки улучшить эту изначально дефектную схему (например менять пароль по счётчику, добавлять ещё какие-то операции) результата не дадут:
это будет просто запутывание, а не повышение криптостойкости, методика вскрытия тоже будет более запутанной в изложении, но по затратам ресурсов такой же тривиальной.
Если хотите понять устройство блочных шифров то изучите хотя-бы в общем виде такие простые шифры как ГОСТ, DES, затем blowfish, IDEA и RC5, а напоследок AES. Неспроста ведь дизайн шифров
развивался в определённом направлении, шансов сделать здесь какое-то открытие просто по незнанию осталось мало.
Хм... мысль такая в голову пришла: криптография, симметричная, вся... – она основана на security via obscurity? Я так понимаю, нет математического доказательства невзламываемости того же хотя бы AES за число итераций, меньшее чем... чтобы полностью свести взлом алгоритма к проблеме мощностей компьютера? Более сложный вопрос (сразу говорю, что от криптографии я далёк, но математику изучал): в связи с тем, что шифрование – это, как правило обратимая функция типа F(a,b)->c, где "а" – текст, а "b" – пароль, обычно много меньший по размеру чем сам текст, обязательно для шифротекста энтропия будет порядка той же что была в открытом тексте, а "эффективная сложность" шифротекста будет эквивалентна сложности пароля. Это приводит к тому, что симметричное крипто представляет собой некую очень сложную технически функцию, отображающую открытый текст в шифротекст, но её "эффективная мощность" не велика, то есть пространство образов довольно бедное по сравнению с произвольным отображением открытого текста на шифтротекст, где пароль порядка длины текста, или банально, шифроблокнот. В этом смысле вся защита сводится к тому, что сложно детально исследовать и найти симметрии в этой функции, позволяющие ломать... но, однако, можно сказать что они зведомо есть(?). Эх, как бы реализовать в виде слов всю эту кашу что в голове... вот так наверное: стойкость шифра, использующего пароль некоторой длины, не может превышать стойкость одноразового блокнота, применённого к (открытому) тексту с длиной, равной длине пароля. Здесь одноразовый блокнот понимается как функция, мощность образа которой не слабее чем прообраза... собственно, мне кажется что применяя пароль вместо блокнота, можно точно оценить границу понижения криптостойкости как функцию пароля. Правда, терзают меня сомнения... что криптосила всех реальных криптоалгоритмов с паролем далека от той границы... так как действия пароля на кусок открытого текста слабее его шифрования одноразовым блокнотом.
Наверно, больше похоже на бред, но интересно услышать, далёк ли я от понимания происходящего?
s/как функцию пароля/как функцию длины пароля/
Скажете тоже... Для полинезийского пигмея устройство лампочки накаливания — это тоже obscurity, но не из-за сложности самого устройства, а только потому что он в школе не учился.
Конечно, в любой области знаний заключена доля эзотерики (иначе какой-либо научный процесс там бы просто остановился). Вот, например, ещё пару лет назад все были уверены, что хэш-функции являются самой исследованной и понятной областью криптологии...
Это в данном случае называется условной энтропией. Условие — знание Вами пароля.
Да всё Вы правильно говорите, только ничего нового тут нет. Криптология, как и другие "оборонительные" дисциплины, занимается (и будет заниматься) вечной борьбой брони и снаряда. Традиционная криптография издревле старалась большой секрет (открытый текст) превратить в малый (ключ или способ преобразования), что невозможно сделать без потерь в теоретико-информационной стойкости. (Одноразовый блокнот, который Вы назвали, — единственный алгоритм, не подверженный этому правилу, но именно потому, что там "уменьшения секрета" не происходит, и размер ключа равен открытому тексту.)
Это не бред. Это вольный пересказ основ современной криптографии, математически описанных Клодом Шенноном в конце 40-х годов XX века. Эти основы являются фундаментом, а ни как не опровержением современной криптографии, которая вся построена на том, что кроме информационно-теоритической стойкости (перед которой все алгоритмы нестойки, кроме одноразового блокнота), существует ещё и вычислительная стойкость. Которая должна быть выше атаки грубой силой 2256, а не 20, как в Вашем случае.
Вычислительную стойкость действительно нельзя строго доказать. Но можно обосновать, что ни один из известных на данный момент методов криптоанализа либо неприменим к алгоритму, либо неэффективен.
На самом деле это тоже обычное дело даже в инженерной практике: нельзя создать абсолютно надёжный самолёт, мост или даже атомный реактор. Приходиться подразумевать вероятность ошибки в конструкции, даже и фатальной. Главное чтобы она была приемлемо мала.
Блочный шифр работает с блоками: в зависимости от размера блока и ключа мощность функции будет 2128 или 2256, так что "пространство образов" никакое не "бедное", если в функции нет дефектов.
s/"d"/"b"// (нахождение пароля "b")
Всё-таки инженерное дело имеет чуть больше практического опыта, чем современная цифровая криптография. При желании можно получить сколь угодно надёжную конструкцию, заложив в неё несколько дополнительных степеней прочности. (Меры потенциальных физических воздействий на конструкцию вполне известны, можно добавить в расчёт и "внештатные" воздействия типа силы ударной волны от ядерного взрыва.) Побочным эффектом этого станет кратное удорожание, поэтому обычно ищется баланс между стоимостью и "достаточной" прочностью конструкции. (В настоящее время с распространением в гражданском строительстве проектных тендеров любые резервные степени прочности сходят на нет. В итоге получаем события вроде "Трансвааля".)
Есть здесь и сходство с крипто. Если перефразировать Райвеста, можно сделать сколь угодно стойкий шифр, но хитрость заключается в том, чтобы он был стойким, простым и быстрым. Опять же, используя избыточное число раундов или дополнительных внутренних конструкций, удлинив ключ до десятков килобит, можно на порядки повысить стойкость шифра, но только ценой стоимости вычислений.
Отсутствие дефектов – сильное требование :) Ведь мы знаем и образ и прообраз. Хочется получить шифротекст с максимальной энтропией... то есть равнораспределённый по частотам, используя терминологию... В физике хорошо известно, что идеального белого шума не бывает... вот отсюда всё и идёт (я так понимаю...).
Дело же ещё в том, что к криптографии, современной, предъявляются довольно жёсткие методы. Например, если противник имеет чёрный ящик на вход которого он может посылать любой текст, и изучать шифротекст, то он не должен быть способным вычислить пароль или найти его слабости... беда же в том что одни и тем же паролем шифроваться может огромное число блоков, и в этом могут проявиться закономерности самого пароля (что математически вполне естественно)... а увидев закономерности, теоретически можно и сам пароль воссстановить. Более того, мне кажется что можно строго математически показать, что существует такое нереальное число известных входов и соответствующих им выходам из чёрного ящика, после которых можно будет заведомо восстановить пароль! То есть... крипто глубоко математически основано не идеологии security via obscurity и нехватке мощностей, в самом своём фундаменте. Похоже на правду?
s/жёсткие методы/жёсткие требования/
Я здесь не спорю про объективно техническую сторону дела, я про сам матфундамент... про теорию.
Что имеется ввиду? Это же шифроблокнот. Или как?
Нет, скорее всего просто потоковый шифр на нестойком генераторе гаммы.
По поводу основ и фундаментов:
Есть понятие атаки грубой силой: для подбора симметричного ключа 128-бит при затрате минимального кванта энергии поттребуется её столько, что хватит на то, чтобы растопить все льды
Антарктиды,. для подбора 256-битного ключа не хватит энергии солнца, излучаемой за год.
Для защиты симметричного крипто от квантовых компьютеров, достаточно увеличить длину ключа вдвое.
Этот теоретический предел роста компьютерных мощностей учитывается при проектировании алгоритмов.
Закономерности пароля тоже не должны влиять на шифр (хотя лучше использовать случайный ключ, получаемый из пароля хэшированием): пространство ключей должно быть плоским, не должно быть слабых ключей или их число должно быть ничтожно мало 2(-126) степени Вас устроит?
Задача блочного шифра замаскировать любые, сколь угодно сложные, поддающиеся вычислению связи между входом (исходным текстом, ключём, вектором инициализации, иногда твик-вектором) и выходом (шифртекстом), сделав их нахождение вычислительно трудной задачей. И противник в модельных испытаниях может делать с этим чёрным ящиком всё что угодно: подать шифртекст и посмотреть на открытый текст, подать пару открытых текстов, получить пару шифртекстов и прогнать их обратно из выхода на вход в другом порядке (бумеранг-атака) и много всего, до чего простой фантазии не хватит.
Считается, что сконструировать функции, которые делают всё эти преобразования неотличимыми от случайных без дефектов (или с ничтожными дефектами) хотя и сложно, но вполне реально. И делается это не путём усложнения или запутывания проблемы, а на основе строгих математических закономерностей, которые могут быть относительно легко проанализированы, изучены, поняты.
Но есть и криптографы, которые рассуждают также как и Вы, хотя на другом уровне конечно.
Николя Куртуа[link2], автор алгебраического криптоанализа[link3] считает, что симметричные алгоритмы действительно не имеют под собой серьёзной математической базы.
А математик и криптограф Нил Коблитц[link4] вообще считает, что модель "чёрного ящика" или "случайного оракула" ошибочна и крикует всю криптографию не как науку построенную на знании, а как науку о неизвестном. Как только появляется новый уровень знаний, так все достижения такой с его позиции почти-что псевдонауки, становятся бесполезными.
Кстати существует ещё более жёсткая модель: полупрозрачный ящик: glass-box cryptoanalysys: когда противнику дают подсмотреть часть информации о внутреннем состоянии шифра (например дают частичную утечку информации о битах ключа или части данных в некотором количестве раундов). Даже на это есть запас прочности!
Всем интересующимся фундаментальными проблемами криптографии очень рекомендую простые для прочтения слайды к лекциями New Frontiers in Symmetric Cryptanalysis[link5] от Николя Куртуа. Без пустой философии, там заключены глубочайшие мысли о связи между криптографией и математикой, как между двумя разными религиями, о связи криптографии и фундаментальной физики и обозначено много изъянов в самом фундаменте криптографии, хотя приведены и оптимистические взгляды на проблему.
Кажется, он весьма авторитетно подтвердил все Ваши опасения насчёт зыбкого фундамента современной криптографии, который может рухнуть в любой момент, и добавил ещё больше того, что возможно ещё никому не приходило в голову. Хотя это может у него просто такой способ эффектно преподносить материал.
Спасибо, unknown, за чёткий и развёрнутый ответ.
Что касается
не ясено вот что. Да, есть системы, вполне себе фундаментальные, теоретические, которые могут генерировать что-то типа почти случайного шума: на входе нечто разумное, а на выходе – ужоснах! Примерами такого являются динамически хаос, может какие-нибудь странные аттакторы... Нас заставляли писать решение дифура, описывающего колебание системы, в правой части которого применялась некая сила, кажется, периодическая. при некоторых параметрах начинался хаос... Но: в криптографии нужна обратимость, а не только хаотичность. Итого, утверждается, что возможно сконструировать очень функцию дающую все свои выходы как очень близкие к случайным, и при этом обратимую? Может быть, но для моих скудных познаний факт как минимум нетривиален.
Рассуждаете, прямо как один тут небезызвестный Spinore :-)
Использование всего вышеперичисленного в криптографии провалилось и аттракторы и хаотические системы в массе своей некриптостойки. Современные блочные шифры устроены иначе,
Идеальные статистические свойства не гарантируют стойкости.
Сама по себе эта задача давно изучена и уже тривиально. Любую псевдослучайную функий можно превратить в псевдослучайную перестановку (сделать обратимой). Это изобрёл в начале 70-х Хорст Файстель.
Разделите блок на две части: a||b Примените любую необратимую функию (с подключём раунда) к одной половине Y=F(a1, k1) и объедините операцией XOR со второй половиной F(b1 xor Y).
Поменяйте половины местами и так выполните сколько хотите раундов,
Расшифрование пройдёт в обратном порядке: от последнего раунда с шифртекстом к первому с обратном порядком следования раундовых подключей. Операция XOR самообратима и вы будете получать обратные значения от функции каждого раунда.
Более подробно объяснить работу простейшей сети Файстеля надо с картинками и более сложными выкладками.
Есть более сложные сети – сети Лэя-Мэсси, фрактальные и др.
Сейчас используют и более продвинутый дизайн: только на обратимых операциях. И (парадокс) для повышения стойкости даже в сетях Файстеля используют обратимые функции.
Недавно был на конференции где были люди занимающимся квантовым крипто, то есть "квантовым распределением ключа" если быть точнее. Я их спросил о смысле всего этого, на что были приведены 2 аргумента:
В частности, второй аргумент вполне коррелирует с тем, что вы признаёте существенные проблемы в основании классической криптографии (мне они изначально интуитивно показались, если задуматься, ... из ряда общих матсоображений).
Напомнило анекдот с бэша[link6]:
Ну да, да, косноязычие не скроешь :) Лингвистически анализ и социнженерия в действии.
Не, ну я просто как пример простейших систем, генерирующих хаос... их привёл.
Да, математика начала 70ых у нас пока в общую программу не входит. Народ даже от функионального анализа отражается, что уж говорить о более серьёзных вещах.
И фракталы уже для криптографии заюзали?! Есть успешные примеры?
http://www.fractals.ru/ – это, правда, не про криптографию, но вам, spinore, понравиться.
Да, интересное кольцо ресурсов. Про elementy.ru знал и раньше.
Нет. Одно название. Внутри сети Файстеля используют в качестве функции раунда другую вложенную сеть Файстеля. Всего два уровня самоподобия.
Зато гордое название: "Фрактальная сеть". Вот пример такого блочного шифра[link7], кстати неотличающегося стойкостью.
Сомневаюсь что она недоказуема именно концептуально. Сейчас ставятся вопросы о классе задач, которые эффективнее решаются на классической или квантовой машине Тьюринга и почему, пытаются завязаться на то что "мы можем это эффективно считать на той или иной машине Тьюринга лишь потому что там такая физика". Дальше встаёт вопрос зависимости присутствующих эффективных алгоритмов от заданной "физики" для вычислительной машины. Однако, правда конечно в том, что эти вопросы ещё только ставятся и даже для двух более-менее изученных классов машин Тьюринга (классической и квантовой) нельзя дать на него ответ, а лишь можно констактировать что есть некие конкретные задачи которые решаются на одной машине быстрее (эффективнее). В общем, при низведении теории вычислений на низкий уровень уже сейчас осознаётся что ответ на вопрос "почему мы можем эффективно решать эти задачи" есть "потому что у нас такая физика". Если ничего не путаю, то термин Kolmogorov complexity как раз и связан с этой "вычислительной сложностью".
Точнее говоря, доказательство не найдено, поскольку это означало бы решение знаменитой проблемы равенства классов P и NP[link8]: есть ли такие задачи, решение которых можно быстро проверить, но нельзя быстро найти?
Да, P=NP при N=0 и N=1 ;-)
Если P=NP, то практически со всей криптографией можно попрощаться и доставать одноразовые блокноты или прокладывать квантовые или шумовые каналы.
P=NP ещё и при P=0 :-)
Теоретически не исключено, что полином может оказаться столь высокой степени, что на практике это никак не скажется. Хотя обычно, если находится хоть какое-то полиномиальное решение, то затем находится и кубическое.
И даже у полинома небольшой степени могут оказаться неприменимые на практике коэффициэнты.