И Кузнечик рунету

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

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

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

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

У всех других sbox алгоритмическая сложность больше 256, так что можно. Например, в статье приведён способ оценки нелинейности (а это важнейший параметр sbox) и он у кузнечика неоправдано низок, при выборе из случайных последовательностей его бы отбросили.

У всех других sbox алгоритмическая сложность больше 256

Пока не нашли, но это не значит, что её там нет (сильной структуры).

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

потому что 256 байт - это нерепрезентативная выборка.

Ты сам понимаешь значения терминов, которые употребляешь? Нерепрезентативная выборка чего? Какой генеральной совокупности?

256 байт - это 2048 бит - 2048 подбрасываний монет. Сколько по твоему должно быть испытаний для того, чтобы выборка была репрезентативной? 2049? 2050 бит? Ты в состоянии привести расчет?

Я тебе уже приводил рассчет, что вероятность сжатия в 4 раза 2048 бит - 2^-1500. Это невозможное событие.

Случайная последовательность может и сжиматься, на то она и случайная.

Вероятность того, что случайная последовательность в 256 байт может быть сжата в 4 раза - 2^-1500. Это невозможное событие. Думаю, с такой вероятностью вообще все наблюдаемые закономерности являются «случайными» и все что ты наблюдаешь вокруг себя является флуктуацией.

Пока не нашли, но это не значит, что её там нет (сильной структуры)

ЯННП. Как раз доказали, что верхняя оценка сложности — 60. Ищи, не ищи, но она может только уменьшиться.

ЯННП. Как раз доказали, что верхняя оценка сложности — 60. Ищи, не ищи, но она может только уменьшиться

Я про другие sbox-ы говорю. Для них верхняя оценка пока больше 256.

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

Строк с такой сложностью среди случайных последовательностей быть не может.

256 байт - это огромное число. Пусть за один такт одно ядро выполняет 4 инкремента. Тогда ~1GGz процессор «переберет» 4 байта за 1 сек. 64-ядерный 4 GGz - 5 байт за секунду.

В год 8-битных и 32-битных микроконтроллеров выпускается 24 миллиарда. Сосчитаем их за 64-ядерные. Пусть это дает нам 13 байт в секунду. Пусть в таком объеме они выпускались 256 лет. Это дает 14 байт в секунду. Пусть это будет 18 байт в год. 19 в столетие.

За столетие простейшая программа двухбайтовая программа add ar, 1; jmp -1; переберет 20 байтов. Это 2^160 вариантов. Вероятность встретить число с искомой сложностью 2^-1500. Посчитай (1 - 2^-1500)^(2^160). Среди случайных последовательностей такого числа встретиться не может.

Ты упёрся в какую-то одному тебе понятную стенку и долбишься в неё. Алгоритмическая сложность так не считается. Если тебя интересует, сколько вообще из 256 байт существует вариантов с алгоритмической сложностью в 64, то тебе надо не биты считать, а решить одну довольно нетривиальную задачу — а сколько вообще разных генераторов 256 байтовых последовательностей можно уместить в 64 байта? Возьмём алгоритм, которым Лео Перрин генерировал sbox от кузнечика, там 32-две байтовые константы, не все из них можно свободно менять, но не суть важно, уменьшим в 4 раза ради компенсации, это даст 8 байт, которые можно задать произвольно, генерируя кузнечикоподобные sbox'ы, что даёт 2¹¹ вариантов различных последовательностей сложностью в 60. Точно также надо поступить для всех других возможных алгоритмов, которые можно уместить в 64 байта. Так что твоя оценка на очень много двоичных порядков расходится с реальностью. Насколько, правда, сказать нереально, потому что я не знаю, как оценить количество алгоритмов.

а решить одну довольно нетривиальную задачу — а сколько вообще разных генераторов 256 байтовых последовательностей можно уместить в 64 байта?

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

Эту «страшную нетривиальную задачу» можно решить очень просто. 64-байтовых алгоритмов существует не более 2^512. Как, видишь, ничего загадочного.

Ты упёрся в какую-то одному тебе понятную стенку и долбишься в неё

Эта «стенка» называется «статистика» и в ней нет ничего более непонятного, чем в статистике бросков монетки.

256 байт - это 2048 бит - 2048 подбрасываний монет

Sbox - это не просто случайное число, оно еще должно удовлетворять различным критериям. Так что твой рассчет - туфта.

Sbox - это не просто случайное число, оно еще должно удовлетворять различным критериям. Так что твой рассчет - туфта.

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

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

«Случайно» же такая коллизия возникнуть не может, это чисто теорема Байеса, основания статистики. Апостериорное правдоподобие «случайного совпадения» 2^-1500. https://en.wikipedia.org/wiki/Maximum_a_posteriori_estimation

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

Не уверен, что все. И они не являются оценками снизу.

любой Sbox представим в линейном виде. просто в «другой системе координат». 256-входный Sbox при этом ещё и поддаётся расчёту.

и также напомню,что в 2006м году даже в педивикии было написано как ломать TEA. а потом стерли даже историю изменений и он снова «очень хороший».

было написано как ломать TEA

где-нибудь про это можно почитать ?

Верни старую аву.

Мог ли их породить случайный процесс?

С некоторой вероятностью случайный процесс может породить и Войну и мир, что он таки и сделал в нашей вселенной.

Вот этот случай и должен быть судя по логике вещей.

Опять пустопорожняя болтовня? Я привел конкретные данные, есть матаппарат, можно всё посчитать и проанализировать. А ты занимаешься балабольством.

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

Ты даже некорректно задаешь вопросы

Некорректно только для тех, кто читать не умеет. Закончим на этом.

А эта чем тебе не нравится, источающая уныние и концептуальная, очень хорошо лору подходит.

какая алгоритмическая сложность у числа пи?

Веселее была.

Не выше 10, а что?

а в числе пи есть всё, даже война и мир.

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

берешь алгербу по модулю 2. И=умножение, XOR=сложение. каждому байту K ставишь в соответствие 256 битный вектор, равный (1<<K). Sbox - это матрица. в каждом столбце и строке по одной единице. Всё, он линеен.

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

Поэтому эти шифры в принципе говно.