Вопросы по криптоанализу

Это отклонение от случайной равновероятной гаммы?

Пусть имеем шифр, который после 16 раундов(циклов) 36-й бит блока принимает значение 1 с вероятностью 0,52. Явлется ли это различителем?

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

Обычно используются более сложные различители. Например в дифференциальном криптоанализе (DC) используются пары подобранных открытых текстов:

Открытый текст — это набор битов: X = [ X₁, X₂ ... X_n ]
Шифртекст — набор битов (бинарный вектор): Y = [ Y₁, Y₂ ... Y_n ]

в которых известно определённое соотношение (в самом простом случае xor):

delta (X) = X' xor X'', delta (Y) = Y' xor Y''

Соотв., delta (X) = [ delta (X₁), delta (X₂) ... delta (X_n) ]
delta (Y) = [ delta (Y₁), delta (Y₂) ... delta (Y_n) ]

В идеале каждая разность delta (Y) должна быть 1/2.

В реальном шифре исследуются его составные компоненты (S-блоки, блоки смешивания) из них извлекаются данные по тем соотношениям, которые с большой вероятностью отличаются от 1/2, по ним строится характеристика для одного раунда.

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

Почему важен различитель?

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

Линейныё криптоанализ (LC) в простейшем виде — это построение соотношений вида: X₁ xor X₃ xor X₄ = Y₁ xor Y₅, которые имеют вероятность, отличающуюся от идеальной.

В то время как в идеальном шифре любые комбинации xor битов открытого текста между собой должны быть независимы от любых xor-комбинаций битов шифртекста и не показывать никаких отклонений вероятности от 1/2.

Иначе получаем линейные аппроксимации (приближения) — с некоторой вероятностью мы можем делать заключение о битах ключа.
Чем больше собрано известных открытых текстов (для LC), тем точнее.

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

Тем не менее считается, что шифр, имеющий хороший запас прочности против известных видов криптоанализа, часто показывает и стойкость против новых видов криптоанализа.

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

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

каждая разность delta (Y) должна быть 1/2

delta (Y) = Y' xor Y''
xor = 1/2? Битовый вектор = 1/2? Ориганально... ;)

в которых известно определённое соотношение (в самом простом случае xor):

delta (X) = X' xor X, delta (Y) = Y' xor Y

Соотв., delta (X) = [ delta (X1), delta (X2) ... delta (Xn) ]
delta (Y) = [ delta (Y1), delta (Y2) ... delta (Yn) ]

что-то непонятно откуда взялось X' и X''.

почитал википедию, там написано что-то вроде:

dY=F(X) xor F(X+dX)

это напоминает производную функции.

Получается, все биты dY также должны быть равновероятны? Если идет отклонение, то это и есть различитель?

Допустим, чтобы восстановить 128-битовый (разрядный) ключ на надо n пар, а если нам нужно 64 бит, а остальные восстановим грубой силой, то n/2 бит или это зависит от конкретных S-блоков (узлов замен). А если сами S-блоки неизвестны, то дифф и линейный криптоанализ неприменимы?

как выбирается dX? Он отличается от X на 1 бит или необязательно?

p.s. кто-нибудь пытался пройти все этапы self-study course on cryptanalysis of schneier?

delta (Y) = Y' xor Y"
xor = 1/2? Битовый вектор = 1/2?

Конечно же, вероятность того, что любой бит в дельта будет 0 или 1 равна 1/2.

Два блока открытого текста. Из них получаются Y' и Y" — два блока шифртекста. Между ними берётся дельта.

Напоминает. Но тут всё построено на дискретной математике.

Получается, все биты dY также должны быть равновероятны? Если идет отклонение, то это и есть различитель?

Да. Но если известен дифференциал, который пусть и с низкой вероятностью для множества раундов сохраняется, то если пропускать пару открытых текстов X' и X" получать на выходе Y' и Y", причём отсеивать такие, что при определённой X' xor X" будет получаться заранее просчитанная Y' xor Y", то можно вычислить ключ.

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

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

А если сами S-блоки неизвестны, то дифф и линейный криптоанализ неприменимы?

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

В большинстве случаев считается лучше использовать известный S-блок, выполнив доказательства дифференциальной и линейной стойкости полученной на его основе раундовой функции.

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

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

Может вообще использоваться не xor, а что-то более сложное.

Ну немного теории есть, а вот как с практикой?

Вот, например, имеем 8-цикловый rc5 без циклических сдвигов, используются только xor и сложение по модулю 2^32. Очевидно, что он не обладает нелинейностью, а, значит, не обладает диффузией.

Как статистически протестировать алгоритм? На сайте видел упоминание о некой "батарее тестов НИСТ", можно ли ее применять для изучения статистики? Как собрать статистику?

Как можно восстановить ключ из собранной статистики?

Это из примеров Шнайера по криптоанализу для любителей? Если вам интересно как это делается, то можете подглядеть в готовые ответы — кто-то когда-то этот курс прорешал и выложил их в интернет.

Что-то похожее разбиралось в вопросе про ГОСТ.


Любой шифр это какая-то функция C = f( P, k), раундовая функция — это тоже самое: Y = f ( X, k), где X — вход предыдущего раунда, Y — выход с рассматриваемого раунда.

Подключ раунда чаще всего добавляется простым xor: Y = f ( X xor k), так если найти вход и выход можно найти и подключ раунда.

Поскольку например в дифференциальном криптоанализе мы знаем пару, которая даёт на выходе определённый дифференциал, то xor этих значений не зависит от ключа: (X' xor k ) xor (X" xor k) = (X' xor X"). Можно получать частичные сведения о ключе или подбирать его частями по методу счётчиков, сравнивая с тем как меняется значения разности.

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

вопрос про метод встречи посередине. если длина блока 64 бит, а ключ 512 бит, то памяти нужно 2^64 бит или 2^256 бит? Как может уменьшится время взлома, если на процедуру заполнения памяти все равно нужно время, или предполагается, что это будет сделано заранее и память считывается мгновенно?

Вообще meet-in-the-middle актуально для двойного шифрования:

C = E_k1 ( E_k2 ( P )) — алгоритмы могут быть разными!

Вместо перебора ключа состоящего из независимых k1 и k2, на что ушло бы 2²ⁿ шифрований, используется 2ⁿ⁺¹ шифрований и 2ⁿ памяти для хранения пар открытых-шифртекстов.

(Или по другому можно считать, что полный ключ — 2ⁿ, а половины ключа 2^n/2).

Если известно P₁ и P₂ и соотв. C₁ и C₂, то перебираются все K и пары K_e, E_Ke ( P₁ ) сохраняются.
Эти результаты в процессе шифрования сортируются по второму значению, так что к отсортированным данным в виде 2^(n/2) пар доступ будет быстрым. Для каждого ключа ещё раз шифруем 2^(n/2) раз, точнее расшифровываем: D_Kd ( C₁ ) и сразу же достаточно осуществить поиск по второму значению:
K_d, D_Kd ( C₁ ) и K_e, E_Ke ( P₁ )

Если D_Kd ( C₁ ) = E_Ke ( P₁ ), то с большой вероятностью K_e = k1 и K_d = k2, то это скорее всего и есть искомые половины ключа k1 и k2, поэтому и получается, что вместо полного перебора ключа 2ⁿ проводилось только 2^(n/2)+1 шифрований/дешифрований, да и ещё не по двойному алгоритму, а по одинарному, ну и памяти израсходовали столько же: 2^(n/2), так как результаты первого шифрования надо хранить. При первом составлении таблицы шифрования происходит сортировка или используется представление данных, удобное для быстрого доступа.

Т.е. смысл метода в том, что половины ключа подбираются независимо.

Правда нужно произвести ещё по крайней мере одно пробное шифрование, чтобы проверить K_d и K_e на другой паре P₂ и C₂.

Раз перебираются все K и пары K_e, E_Ke ( P₁ ) сохраняются.

То полный размер таблицы будет: (2⁹ + 2⁶) · 2²⁵⁶ — примерно 2²⁶⁵.

и вероятность совпадений будет больше, поэтому желательно больше пар { P₁, ..., P_n } — { C₁, ..., C_n}

Это к вопросу вообще, что такое размен числа операций по перебору ключа на память.

Вторая часть вопроса, можно ли это сделать для одного блочного шифра? Если в нём нет дополнительных уязвимостей или каких-то особенностей в структуре, то нет. Так просто разбить его на две функции, к которым можно независимо подбирать ключи не имеет смысла. Meet-ITM используется как вспомогательная к другим атакам.
Простого примера здесь не привести, смотрите например эти слайды.

Третья часть вопроса, есть ли смысл использовать размер ключа больше размера блока. Простого ответа тоже нет. Много частностей. Если хотите точно не ошибиться, то лучше считать, что размер ключа должен быть равен размеру блока, а его увеличение даёт меньше стойкости, чем при одинаковом увеличении размера блока и ключа, но это суперперфекционизм какой-то, основанный на очень нереалистичных предположения об атаках. Даже в стандарт AES такое допущение заложено не было и при проектировании некоторых лёгких шифров с 64-битным блоком там считается нормально использовать 128-бит ключ.

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

а есть ли смысл запоминать 64*2^n бит, если (к примеру idea, где ключ 128 бит) n>64? Если используется атака на основе выбранных шифртекстов, то можно запомнить результат зашифрования нулевого вектора на всем пространстве ключей, и из этих данных восстановить ключ.

можно ли сказать, что если размер ключа не превышает размер блока в 2 раза, то метод встречи посередине не эффективен?

Выше было показано, что Meet-iTM имеет смысл против каскада из двух шифров.

Вы же хотите рассмотреть вопрос использования Meet-iTM против одного шифра. На что был дан ответ, что неизвестно тривиального решения в данном случае.

Допустим можно разбить шифр на две функции шифрования C = f ( K, P) = f₁ ( k₁ ( f₂ ( k ₂, P ))
Встречное значение: X = E_k1 ( P ) · D_k2 ( C )

То есть зашифровать открытый текст половиной раундов шифра, составить таблицу, а затем расшифровывать шифртекст обратной половиной раундов шифра и искать соответствие в таблице. Т.е. если получится такая встреча посредине при половинном шифровании "сверху вниз" и половинном расшифровании "снизу вверх": E_k1 ( P ) = D_k2 ( P ), то с большой вероятностью найден верный ключ (который нужно составить обратно из k1 и k2), который можно опробовать на другой паре {P, C}.

Но только какой в этом вообще смысл? Что в данном случае k1 и k2? Подключи всех раундов? Так для их вычисления по ключевому расписанию нужно перебирать исходный главный ключ, значит не получится разбить его на две независимые половины и никакой экономии не будет вообще, так как нельзя две части ключа перебирать независимо. Атака не имеет смысла.

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

На ум приходят только три варианта:

1. Слабое ключевое расписание. Когда k1 и k2 можно перебирать не целиком, а по сокращённому правилу.
2. Когда на сокращённую версию шифра уже есть какая-то атака, которая пробивает половину раундов. Тут два подварианта: в довесок к атаке перебирать подключи, "дожать" атаку для усиления эффекта с помощью Meet-iTM. Или второй подвариант — перебирать открытые и шифртексты, восстанавливая по ним k1 и k2, тогда вместо взлома полнораундового шифра с ключом K = n бит, достаточно взломать с двух сторон половину раундов, перебрав число текстов, равное размеру блока (это допущение, но не факт). Тогда, действительно размер ключа больше размера блока даёт меньшую защиту и с помощью размена на объём памяти и число доступных открытых/шифр текстов можно снизить число шагов на перебор ключа. Но это очень маловероятное стечение обстоятельств, что именно такая атака будет существовать и именно в таком виде.
3. Когда есть какие-то особенности шифра, которые обычно не используются ни в каких других атаках, но имеют смысл в Meet-iTM. Это было изобретено Чаумом ещё в восьмидесятые годы против DES и на слайдах по ссылке выше было показано, что эта старая идея может быть усовершенствована и имеет потенциал для исследований и в наши дни.

В чем измеряется криптостойкость алгоритмов? Слышал о вычислительной сложности. Это что, количество элементарных операций или количество операций шифрования?

можно ли сказать, что если размер ключа не превышает размер блока в 2 раза, то метод встречи посередине не эффективен?

Вообще Капитан Очевидность подсказывает, что: Размер любой таблицы T, у которой длина всех строк одинакова — это произведение длины её строки на количество строк.

Длина строки линейно зависит от размера блока b и ключа k, а вот количество строк зависит от размера ключа экспоненциально — 2^k. А произведение линейного растущего множителя на экспоненциально растущий приверно равно второму: T = ( b + k ) · 2^k ≈ 2^k.

Т.е. при всяких там ( 2⁷ + 2⁷) · 2¹²⁸, можно округлённо считать, что результат равен 2¹²⁸ и от того, что размер блока увеличится в два раза и будет скажем 2⁸ — это нам погоды не сделает. Размер таблицы зависит фактически только от размера ключа и если это позволяет вместо перебора полного ключа 2ⁿ делать его сокращённый перебор 2^n/2 — то это существенный прогресс. Для каскада двух шифров — это так и есть. При попытке разбить один шифр на две функции вылезает масса трудностей, перечисленных ранее, так что простой ответ на вопрос про Meet-iTM там неочевиден.

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

Для других доказательство стойкости измеряется таким образом. Пусть по критериям проектирования криптосистемы противнику нужно проделать 2ⁿ вычислительных операций для её взлома, причём желательно, чтобы это 2ⁿ было настолько большое, что ему не хватит не только вычислительных, но даже и энергетических ресурсов Земли и Солнечной системы. Нужно доказать (убедительно показать), что не существует метода взлома, требующих операций меньше, чем 2ⁿ.

При величинах порядка 2¹²⁸ это уже всё настолько не важно. Конечно, количество элементарных операций никто не считает. Количество операций шифрования — как минимум, а то и гораздо большее число вычислительно более сложных действий под видом одной операции.

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