Оцените блочный шифр

схема была представлена как простое домашнее задание по использованию элементарных криптоаналитических техник для её тривиального взлома

Что имеется ввиду? Это же шифроблокнот. Или как?

Нет, скорее всего просто потоковый шифр на нестойком генераторе гаммы.

По поводу основ и фундаментов:

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

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

Этот теоретический предел роста компьютерных мощностей учитывается при проектировании алгоритмов.

Закономерности пароля тоже не должны влиять на шифр (хотя лучше использовать случайный ключ, получаемый из пароля хэшированием): пространство ключей должно быть плоским, не должно быть слабых ключей или их число должно быть ничтожно мало 2^(-126) степени Вас устроит?

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

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

Но есть и криптографы, которые рассуждают также как и Вы, хотя на другом уровне конечно.

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

А математик и криптограф Нил Коблитц вообще считает, что модель "чёрного ящика" или "случайного оракула" ошибочна и крикует всю криптографию не как науку построенную на знании, а как науку о неизвестном. Как только появляется новый уровень знаний, так все достижения такой с его позиции почти-что псевдонауки, становятся бесполезными.

Кстати существует ещё более жёсткая модель: полупрозрачный ящик: glass-box cryptoanalysys: когда противнику дают подсмотреть часть информации о внутреннем состоянии шифра (например дают частичную утечку информации о битах ключа или части данных в некотором количестве раундов). Даже на это есть запас прочности!

Всем интересующимся фундаментальными проблемами криптографии очень рекомендую простые для прочтения слайды к лекциями New Frontiers in Symmetric Cryptanalysis от Николя Куртуа. Без пустой философии, там заключены глубочайшие мысли о связи между криптографией и математикой, как между двумя разными религиями, о связи криптографии и фундаментальной физики и обозначено много изъянов в самом фундаменте криптографии, хотя приведены и оптимистические взгляды на проблему.

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

Спасибо, unknown, за чёткий и развёрнутый ответ.
Что касается

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

не ясено вот что. Да, есть системы, вполне себе фундаментальные, теоретические, которые могут генерировать что-то типа почти случайного шума: на входе нечто разумное, а на выходе – ужоснах! Примерами такого являются динамически хаос, может какие-нибудь странные аттакторы... Нас заставляли писать решение дифура, описывающего колебание системы, в правой части которого применялась некая сила, кажется, периодическая. при некоторых параметрах начинался хаос... Но: в криптографии нужна обратимость, а не только хаотичность. Итого, утверждается, что возможно сконструировать очень функцию дающую все свои выходы как очень близкие к случайным, и при этом обратимую? Может быть, но для моих скудных познаний факт как минимум нетривиален.

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

Рассуждаете, прямо как один тут небезызвестный Spinore :-)
Использование всего вышеперичисленного в криптографии провалилось и аттракторы и хаотические системы в массе своей некриптостойки. Современные блочные шифры устроены иначе,
Идеальные статистические свойства не гарантируют стойкости.

Но: в криптографии нужна обратимость, а не только хаотичность. Итого, утверждается, что возможно сконструировать очень функцию дающую все свои выходы как очень близкие к случайным, и при этом обратимую? Может быть, но для моих скудных познаний факт как минимум нетривиален.

Сама по себе эта задача давно изучена и уже тривиально. Любую псевдослучайную функий можно превратить в псевдослучайную перестановку (сделать обратимой). Это изобрёл в начале 70-х Хорст Файстель.

Разделите блок на две части: a||b Примените любую необратимую функию (с подключём раунда) к одной половине Y=F(a1, k1) и объедините операцией XOR со второй половиной F(b1 xor Y).
Поменяйте половины местами и так выполните сколько хотите раундов,

Расшифрование пройдёт в обратном порядке: от последнего раунда с шифртекстом к первому с обратном порядком следования раундовых подключей. Операция XOR самообратима и вы будете получать обратные значения от функции каждого раунда.

Более подробно объяснить работу простейшей сети Файстеля надо с картинками и более сложными выкладками.

Есть более сложные сети – сети Лэя-Мэсси, фрактальные и др.

Сейчас используют и более продвинутый дизайн: только на обратимых операциях. И (парадокс) для повышения стойкости даже в сетях Файстеля используют обратимые функции.

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

Недавно был на конференции где были люди занимающимся квантовым крипто, то есть "квантовым распределением ключа" если быть точнее. Я их спросил о смысле всего этого, на что были приведены 2 аргумента:

• Сейчас эта тематика "модная", за неё платят деньги и выдают гранты. Во многом поэтому туда приходят люди и ею занимаются.
• ИБ должна базироваться на каких-то физических незыблемых законах, если по уму, а не на "security via obscurity", поэтому имеет смысл разрабатывать альтернативные способы передачи шифровального ключа и т.д.

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

Рассуждаете, прямо как один тут небезызвестный Spinore :-)

Напомнило анекдот с бэша:

McMillan: Hello
Support: Hello
McMillan: Are you support engineer?
Support: Yes
Support: Do you speak russian?
McMillan: нет
McMillan: no
McMillan: бля, палюсь

Ну да, да, косноязычие не скроешь :) Лингвистически анализ и социнженерия в действии.

Использование всего вышеперичисленного в криптографии провалилось и аттракторы и хаотические системы в массе своей некриптостойки.

Не, ну я просто как пример простейших систем, генерирующих хаос... их привёл.

Сама по себе эта задача давно изучена и уже тривиально. Любую псевдослучайную функий можно превратить в псевдослучайную перестановку (сделать обратимой). Это изобрёл в начале 70-х Хорст Файстель.

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

Есть более сложные сети – сети Лэя-Мэсси, фрактальные

И фракталы уже для криптографии заюзали?! Есть успешные примеры?

http://www.fractals.ru/ – это, правда, не про криптографию, но вам, spinore, понравиться.

это, правда, не про криптографию, но вам, spinore, понравиться.

Да, интересное кольцо ресурсов. Про elementy.ru знал и раньше.

И фракталы уже для криптографии заюзали?! Есть успешные примеры?

Нет. Одно название. Внутри сети Файстеля используют в качестве функции раунда другую вложенную сеть Файстеля. Всего два уровня самоподобия.

Зато гордое название: "Фрактальная сеть". Вот пример такого блочного шифра, кстати неотличающегося стойкостью.

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

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

Вычислительную стойкость действительно нельзя строго доказать

Точнее говоря, доказательство не найдено, поскольку это означало бы решение знаменитой проблемы равенства классов P и NP: есть ли такие задачи, решение которых можно быстро проверить, но нельзя быстро найти?

Впервые вопрос о равенстве классов был поставлен независимо Куком и Левиным в 1971 г. В настоящее время большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в 2002 г. среди 100 учёных, 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что вопрос не зависит от текущей системы аксиом и, таким образом, не может быть доказан или опровергнут.

В настоящий момент проблема равенства классов P и NP является одной из семи проблем, за решение которых Математический институт Клэя назначил премию в 1 млн. долларов США.

Да, P=NP при N=0 и N=1 ;-)

Если P=NP, то практически со всей криптографией можно попрощаться и доставать одноразовые блокноты или прокладывать квантовые или шумовые каналы.

Да, P=NP при N=0 и N=1 ;-)

P=NP ещё и при P=0 :-)

Если P=NP, то практически со всей криптографией можно попрощаться и доставать одноразовые блокноты или прокладывать квантовые или шумовые каналы.

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