Атака «встреча посередине» с частичным соответствием

Частичное сопоставление — это метод, который можно использовать при атаке MITM . Частичное сопоставление — это промежуточные значения атаки MITM, $i$ и $j$, вычисленные на основе открытого текста и зашифрованного текста, сопоставляются только по нескольким выбранным битам, а не по полному состоянию.

Использование

Ограничением атак MITM является количество промежуточных значений, которые необходимо сохранить. Чтобы сравнить промежуточные значения $i$ и $j$, все $i$необходимо сначала вычислить и сохранить, перед каждым вычислением $j$ можно сравнить с ними. Если оба субшифра, идентифицированные в результате атаки MITM, имеют достаточно большой подключ, то необходимо хранить невозможное количество промежуточных значений. Хотя существуют такие методы, как алгоритмы обнаружения циклов. что позволяет выполнить MITM-атаку, не сохраняя ни всех значений $i$ или $j$Эти методы требуют, чтобы субшифры атаки MITM были симметричными. Таким образом, это решение, которое позволяет выполнить MITM-атаку в ситуации, когда мощность подключей достаточно велика, чтобы сделать количество временных значений, которые необходимо сохранить, невозможным. Хотя это позволяет хранить больше временных значений, его использование по-прежнему ограничено, поскольку оно позволяет выполнить MITM-атаку только на субшифр с еще несколькими битами. Например: если хранится только 1/8 промежуточного значения, то подключ должен быть всего на 3 бита больше, прежде чем в любом случае потребуется тот же объем памяти, поскольку $2^{-3}=1/8$

В большинстве случаев гораздо более полезная функция, обеспечиваемая частичным сопоставлением при атаках MITM, — это возможность сравнивать промежуточные значения, вычисленные на разных раундах атакуемого шифра. Если распространение в каждом раунде шифра достаточно низкое, возможно, в течение нескольких раундов можно будет найти биты в промежуточных состояниях, которые не изменились, с вероятностью 1. Эти биты в промежуточных состояниях все еще можно сравнивать.

Недостаток обоих этих вариантов использования заключается в том, что для ключевых кандидатов будет больше ложных срабатываний, которые необходимо протестировать. Как правило, вероятность ложного срабатывания определяется вероятностью $2^{-|i|}$, где $|i|$ это количество совпадающих битов.

Пример

Пошаговый пример полной атаки на КТАНТАН: см. пример на странице MITM с 3 подмножествами . В этом примере рассматривается только та часть, которая требует частичного сопоставления. Полезно знать, что КТАНТАН — это 254-раундовый блочный шифр, в котором каждый раунд использует 2 бита из 80-битного ключа.

В атаке с тремя подмножествами на семейство шифров KTANTAN необходимо было использовать частичное совпадение для организации атаки. Частичное сопоставление было необходимо, поскольку промежуточные значения открытого и зашифрованного текста в MITM-атаке вычислялись в конце 111-го раунда и в начале 131-го раунда соответственно. Поскольку между ними был промежуток в 20 раундов, их нельзя было сравнивать напрямую.

Авторы атаки, однако, выявили некоторые полезные характеристики КТАНТАНА, которые имеют место с вероятностью 1. Из-за низкой диффузии за раунд в КТАНТАНЕ (безопасность заключается в количестве раундов), они выяснили это путем вычислений вперед от раунда. 111 и обратно, начиная с раунда 131, что в раунде 127 8 бит из обоих промежуточных состояний останутся неизменными. (Это было 8 бит в раунде 127 для КТАНТАН32. Это было 10 бит в раунде 123 и 47 бит в раунде 131 для КТАНТАН48 и КТАНТАН64 соответственно). сравнивая только 8 бит каждого промежуточного значения, авторы смогли организовать MITM-атаку на шифр, несмотря на то, что между двумя субшифрами было 20 раундов.

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