Дифференциальный криптоанализ

Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хэш-функций и поточных шифров).

Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю <math>2^{32}</math>. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.

История

Дифференциальный криптоанализ предложен в 1990 году израильскими специалистами Эли Бихамом и Ади Шамиром для взлома криптосистем, подобных DES. В своей работе они показали, что алгоритм DES оказался довольно устойчивым к данному методу криптоанализа, и любое малейшее изменение структуры алгоритма делает его более уязвимым.

В 1994 году Дон Копперсмит из IBM опубликовал статью, в которой заявил, что метод дифференциального криптоанализа был известен IBM уже в 1974 году, и одной из поставленных целей при разработке DES была защита от этого метода. У IBM были свои секреты. Копперсмит объяснял:

При проектировании использовались преимущества определенных криптоаналитических методов, особенно метода «дифференциального криптоанализа», который не был опубликован в открытой литературе. После дискуссий с АНБ было решено, что раскрытие процесса проектирования раскроет и метод дифференциального криптоанализа, мощь которого может быть использована против многих шифров. Это, в свою очередь, сократило бы преимущество США перед другими странами в области криптографии.

DES оказался криптостойким к дифференциальному криптоанализу, в отличие от некоторых других шифров. Так, например, уязвимым оказался шифр FEAL. Состоящий из 4 раундов FEAL-4 может быть взломан используя всего лишь 8 подобранных открытых текстов, и даже 31-раундовый FEAL уязвим для атаки.

Схема взлома DES

В 1990 году Эли Бихам и Ади Шамир, используя метод дифференциального криптоанализа, нашли способ вскрытия DES, более эффективный, чем вскрытие методом грубой силы. Работая с парами шифротекстов, открытые тексты которых имеют определенные отличия, ученые анализировали эволюцию этих отличий при прохождении открытых текстов через этапы DES.

Анализ одного раунда

Базовый метод дифференциального криптоанализа — это атака на основе адаптивно подобранных открытых текстов, хотя у него есть расширение для атаки на основе открытых текстов. Для проведения атаки используются пары открытых текстов, связанных определенной разницей. Для DES и DES-подобных систем она определяется как исключающее ИЛИ (XOR). При расшифровке необходимо только значение соответствующих пар шифротекстов.

На схеме изображена функция Фейстеля . Пусть <math>X</math> и <math>X'</math> - пара входов, различающихся на <math>\Delta X</math>. Соответствующие им выходы известны и равны <math>Y</math> и <math>Y'</math>, разница между ними - <math>\Delta Y</math>. Также известны перестановка с расширением и <math>P</math>-блок, поэтому известны <math>\Delta A</math> и <math>\Delta C</math>. <math>B</math> и <math>B'</math> неизвестны, но мы знаем, что их разность равна <math>\Delta A</math>, т.к. различия <math>XOR\ K_{i}</math> c <math>A</math> и <math>A'</math> нейтрализуются. Единственные нелинейные элементы в схеме — это <math>S</math>-блоки. Для каждого <math>S</math>-блока можно хранить таблицу, строки которой — разности на входе <math>S</math>-блока, столбцы — разности на выходе, а на пересечении — число пар, имеющих данные входную и выходную разности, и где-то хранить сами эти пары.

Вскрытие раундового ключа основано на том факте, что для заданного <math>\Delta A</math> не все значения <math>\Delta C</math> равновероятны, а комбинация <math>\Delta A</math> и <math>\Delta C</math> позволяет предположить значения <math>A\ XOR\ K_{i}</math> и <math>A'\ XOR\ K_{i}</math>. При известных <math>A</math> и <math>A'</math> это позволяет определить <math>K_{i}</math>. За исключением <math>\Delta C</math> вся необходимая информация для последнего раунда содержится в итоговой паре шифротекстов.

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

Характеристики

Для определения возможных отличий полученных на i-м раунде шифротекстов используются раундовые характеристики.

N-раундовая характеристика представляет собой кортеж <math>\Omega \ = \ (\Omega_{P}, \Omega_{\Lambda}, \Omega_{T})</math>, составляется из различий открытого текста <math>\Omega_{P}</math>, различий шифротекста <math>\Omega_{T}</math> и набора <math>\Omega_{\Lambda} \ = \ (\Lambda_{1}, \Lambda_{2},\ ...\ , \Lambda_{n})</math> различий пропромежуточных результатов шифрования для каждого прошедшего раунда.

Характеристике присваивается вероятность, равная вероятности что случайная пара открытых текстов с различием <math>\Omega_{P}</math> в результате шифрования со случайными ключами имеет раундовые различия и различия шифротекстов, совпадающие с указанными в характеристике. Соответствующая характеристике пара открытых текстов называется «правильной». Не соответствующие характеристике пары открытых текстов зовутся «неправильными».

Примем значение разницы текстов на выходе предпоследнего цикла, используемое при определении возможного подключа последнего раунда, <math>\Delta A = \Omega_{T}</math>. В таком случая «правильная» пара текстов позволяет определить правильный ключ, в то время как «неправильная» пара определяет случайный ключ.

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

• Квартет — структура из четырёх текстов, которая одновременно содержит в себе по две пары текстов для двух разных характеристик. Позволяет сэкономить 1/2 памяти для открытых текстов.
• Октет — структура из 16 текстов, содержащая 8 пар, по 4 на каждую характеристику. Позволяет сэкономить 2/3 памяти для открытых текстов.

Отношение сигнал/шум

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

Для нашей расчётной схемы отношение числа правильных пар S к среднему значению счётчика N будем называть отношением сигнал/шум и будем обозначать <math>S/N</math>.

Чтобы найти правильный ключ и гарантировать наличие правильных пар, необходимы:

• характеристика, обладающая достаточной вероятностью;
• достаточное количество пар.

Число необходимых пар определяется:

• вероятностью характеристики;
• числом бит ключа (бит, которые мы хотим определить);
• уровнем идентификации ошибочных пар (пары не вносят вклада в счётчики, так как отбрасываются раньше).

Пусть размер ключа равен k бит, тогда нам понадобится <math>2^k</math> счётчиков. Если:

• m — число используемых пар;
• <math>\alpha</math> — средняя добавка к счётчикам для одной пары;
• <math>\beta</math> — отношение пар, которые вносят вклад в счётчики ко всем парам (в том числе отброшенным),

то среднее значение счётчика N равно:

<math>N = \frac{m \cdot \alpha \cdot \beta}{2^{k}}.</math>

Если <math>p</math> — вероятность характеристики, то число правильных пар S равно:

<math>S = m \cdot p.</math>

Тогда отношение сигнал/шум равно:

<math>S/N = \frac{m \cdot p}{m \cdot \alpha \cdot \beta / 2^{k}} = \frac{2^{k} \cdot p}{\alpha \cdot \beta}.</math>

Заметим, что для нашей расчётной схемы отношение сигнал/шум не зависит от общего числа пар. Число необходимых правильных пар — в общем, функция отношения сигнал/шум. Экспериментально было установлено, что если S/N=1—2, необходимо 20—40 вхождений правильных пар. Если же отношение намного выше, то даже 3—4 правильных пар может быть достаточно. Наконец, когда оно сильно ниже, число необходимых пар огромно.

S/N	Число необходимых пар
меньше 1	Велико
1—2	20—40
больше 2	3—4

Эффективность взлома

С увеличением числа раундов сложность криптоанализа увеличивается, однако остаётся меньше сложности полного перебора при количестве циклов меньше 16.

Зависимость от количества раундов
Число раундов	Трудоёмкость атаки
<math>4</math>	<math>2^{4}</math>
<math>6</math>	<math>2^{8}</math>
<math>8</math>	<math>2^{16}</math>
<math>9</math>	<math>2^{26}</math>
<math>10</math>	<math>2^{35}</math>
<math>11</math>	<math>2^{36}</math>
<math>12</math>	<math>2^{43}</math>
<math>13</math>	<math>2^{44}</math>
<math>14</math>	<math>2^{51}</math>
<math>15</math>	<math>2^{52}</math>
<math>16</math>	<math>2^{58}</math>

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

Сравнение с другими методами

См. Известные атаки на DES

Дифференциальный криптоанализ и DES-подобные системы

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

• Lucifer, укороченный до восьми раундов, взламывается с использованием менее 60 шифротекстов.
• FEAL-8 взламывается с использованием менее 2000 шифротекстов.
• FEAL-4 взламывается с использованием 8-и шифротекстов и одного открытого текста.
• FEAL-N и FEAL-NX могут быть взломаны при количестве раундов <math>N \leq 31</math>.

Дифференциальный криптоанализ также применим против хеш-функций.

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

Недостатки метода

Метод дифференциального криптоанализа в большей степени является теоретическим достижением. Его применение на практике ограничено высокими требованиями к времени и объёму данных.

Являясь, в первую очередь, методом для вскрытия с выбранным открытым текстом, дифференциальный криптоанализ трудно реализуем на практике. Он может быть использован для вскрытия с известным открытым текстом, но в случае полного 16-этапного DES это делает его даже менее эффективным, чем вскрытие грубой силой.

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

См. также

• Линейный криптоанализ
• Атака методом бумеранга
• Криптоанализ со связанными ключами

Литература

• Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си.
• Панасенко, С. "[www.cio-world.ru/weekly/295841/page2.html Современные методы вскрытия алгоритмов шифрования, часть 3]". Chief Information Officer - 2006. 
• Biham E., Shamir A. Differential cryptoanalysis of the Data Encription Standart.
• Biham E., Shamir A. [sota.gen.nz/crypt_blues/biham91differential.pdf Differential cryptoanalysis of DES-like cryptosystems] (англ.). — 1990.

Отрывок, характеризующий Дифференциальный криптоанализ

Пьер не понимал, в чем дело, и еще меньше, что значило veiller a vos interets, [блюсти ваши интересы,] но он понимал, что всё это так должно быть. Коридором они вышли в полуосвещенную залу, примыкавшую к приемной графа. Это была одна из тех холодных и роскошных комнат, которые знал Пьер с парадного крыльца. Но и в этой комнате, посередине, стояла пустая ванна и была пролита вода по ковру. Навстречу им вышли на цыпочках, не обращая на них внимания, слуга и причетник с кадилом. Они вошли в знакомую Пьеру приемную с двумя итальянскими окнами, выходом в зимний сад, с большим бюстом и во весь рост портретом Екатерины. Все те же люди, почти в тех же положениях, сидели, перешептываясь, в приемной. Все, смолкнув, оглянулись на вошедшую Анну Михайловну, с ее исплаканным, бледным лицом, и на толстого, большого Пьера, который, опустив голову, покорно следовал за нею.
На лице Анны Михайловны выразилось сознание того, что решительная минута наступила; она, с приемами деловой петербургской дамы, вошла в комнату, не отпуская от себя Пьера, еще смелее, чем утром. Она чувствовала, что так как она ведет за собою того, кого желал видеть умирающий, то прием ее был обеспечен. Быстрым взглядом оглядев всех, бывших в комнате, и заметив графова духовника, она, не то что согнувшись, но сделавшись вдруг меньше ростом, мелкою иноходью подплыла к духовнику и почтительно приняла благословение одного, потом другого духовного лица.
– Слава Богу, что успели, – сказала она духовному лицу, – мы все, родные, так боялись. Вот этот молодой человек – сын графа, – прибавила она тише. – Ужасная минута!
Проговорив эти слова, она подошла к доктору.
– Cher docteur, – сказала она ему, – ce jeune homme est le fils du comte… y a t il de l'espoir? [этот молодой человек – сын графа… Есть ли надежда?]
Доктор молча, быстрым движением возвел кверху глаза и плечи. Анна Михайловна точно таким же движением возвела плечи и глаза, почти закрыв их, вздохнула и отошла от доктора к Пьеру. Она особенно почтительно и нежно грустно обратилась к Пьеру.
– Ayez confiance en Sa misericorde, [Доверьтесь Его милосердию,] – сказала она ему, указав ему диванчик, чтобы сесть подождать ее, сама неслышно направилась к двери, на которую все смотрели, и вслед за чуть слышным звуком этой двери скрылась за нею.
Пьер, решившись во всем повиноваться своей руководительнице, направился к диванчику, который она ему указала. Как только Анна Михайловна скрылась, он заметил, что взгляды всех, бывших в комнате, больше чем с любопытством и с участием устремились на него. Он заметил, что все перешептывались, указывая на него глазами, как будто со страхом и даже с подобострастием. Ему оказывали уважение, какого прежде никогда не оказывали: неизвестная ему дама, которая говорила с духовными лицами, встала с своего места и предложила ему сесть, адъютант поднял уроненную Пьером перчатку и подал ему; доктора почтительно замолкли, когда он проходил мимо их, и посторонились, чтобы дать ему место. Пьер хотел сначала сесть на другое место, чтобы не стеснять даму, хотел сам поднять перчатку и обойти докторов, которые вовсе и не стояли на дороге; но он вдруг почувствовал, что это было бы неприлично, он почувствовал, что он в нынешнюю ночь есть лицо, которое обязано совершить какой то страшный и ожидаемый всеми обряд, и что поэтому он должен был принимать от всех услуги. Он принял молча перчатку от адъютанта, сел на место дамы, положив свои большие руки на симметрично выставленные колени, в наивной позе египетской статуи, и решил про себя, что всё это так именно должно быть и что ему в нынешний вечер, для того чтобы не потеряться и не наделать глупостей, не следует действовать по своим соображениям, а надобно предоставить себя вполне на волю тех, которые руководили им.
Не прошло и двух минут, как князь Василий, в своем кафтане с тремя звездами, величественно, высоко неся голову, вошел в комнату. Он казался похудевшим с утра; глаза его были больше обыкновенного, когда он оглянул комнату и увидал Пьера. Он подошел к нему, взял руку (чего он прежде никогда не делал) и потянул ее книзу, как будто он хотел испытать, крепко ли она держится.
– Courage, courage, mon ami. Il a demande a vous voir. C'est bien… [Не унывать, не унывать, мой друг. Он пожелал вас видеть. Это хорошо…] – и он хотел итти.
Но Пьер почел нужным спросить:
– Как здоровье…
Он замялся, не зная, прилично ли назвать умирающего графом; назвать же отцом ему было совестно.
– Il a eu encore un coup, il y a une demi heure. Еще был удар. Courage, mon аmi… [Полчаса назад у него был еще удар. Не унывать, мой друг…]
Пьер был в таком состоянии неясности мысли, что при слове «удар» ему представился удар какого нибудь тела. Он, недоумевая, посмотрел на князя Василия и уже потом сообразил, что ударом называется болезнь. Князь Василий на ходу сказал несколько слов Лоррену и прошел в дверь на цыпочках. Он не умел ходить на цыпочках и неловко подпрыгивал всем телом. Вслед за ним прошла старшая княжна, потом прошли духовные лица и причетники, люди (прислуга) тоже прошли в дверь. За этою дверью послышалось передвиженье, и наконец, всё с тем же бледным, но твердым в исполнении долга лицом, выбежала Анна Михайловна и, дотронувшись до руки Пьера, сказала:
– La bonte divine est inepuisable. C'est la ceremonie de l'extreme onction qui va commencer. Venez. [Милосердие Божие неисчерпаемо. Соборование сейчас начнется. Пойдемте.]
Пьер прошел в дверь, ступая по мягкому ковру, и заметил, что и адъютант, и незнакомая дама, и еще кто то из прислуги – все прошли за ним, как будто теперь уж не надо было спрашивать разрешения входить в эту комнату.


Пьер хорошо знал эту большую, разделенную колоннами и аркой комнату, всю обитую персидскими коврами. Часть комнаты за колоннами, где с одной стороны стояла высокая красного дерева кровать, под шелковыми занавесами, а с другой – огромный киот с образами, была красно и ярко освещена, как бывают освещены церкви во время вечерней службы. Под освещенными ризами киота стояло длинное вольтеровское кресло, и на кресле, обложенном вверху снежно белыми, не смятыми, видимо, только – что перемененными подушками, укрытая до пояса ярко зеленым одеялом, лежала знакомая Пьеру величественная фигура его отца, графа Безухого, с тою же седою гривой волос, напоминавших льва, над широким лбом и с теми же характерно благородными крупными морщинами на красивом красно желтом лице. Он лежал прямо под образами; обе толстые, большие руки его были выпростаны из под одеяла и лежали на нем. В правую руку, лежавшую ладонью книзу, между большим и указательным пальцами вставлена была восковая свеча, которую, нагибаясь из за кресла, придерживал в ней старый слуга. Над креслом стояли духовные лица в своих величественных блестящих одеждах, с выпростанными на них длинными волосами, с зажженными свечами в руках, и медленно торжественно служили. Немного позади их стояли две младшие княжны, с платком в руках и у глаз, и впереди их старшая, Катишь, с злобным и решительным видом, ни на мгновение не спуская глаз с икон, как будто говорила всем, что не отвечает за себя, если оглянется. Анна Михайловна, с кроткою печалью и всепрощением на лице, и неизвестная дама стояли у двери. Князь Василий стоял с другой стороны двери, близко к креслу, за резным бархатным стулом, который он поворотил к себе спинкой, и, облокотив на нее левую руку со свечой, крестился правою, каждый раз поднимая глаза кверху, когда приставлял персты ко лбу. Лицо его выражало спокойную набожность и преданность воле Божией. «Ежели вы не понимаете этих чувств, то тем хуже для вас», казалось, говорило его лицо.
Сзади его стоял адъютант, доктора и мужская прислуга; как бы в церкви, мужчины и женщины разделились. Всё молчало, крестилось, только слышны были церковное чтение, сдержанное, густое басовое пение и в минуты молчания перестановка ног и вздохи. Анна Михайловна, с тем значительным видом, который показывал, что она знает, что делает, перешла через всю комнату к Пьеру и подала ему свечу. Он зажег ее и, развлеченный наблюдениями над окружающими, стал креститься тою же рукой, в которой была свеча.
Младшая, румяная и смешливая княжна Софи, с родинкою, смотрела на него. Она улыбнулась, спрятала свое лицо в платок и долго не открывала его; но, посмотрев на Пьера, опять засмеялась. Она, видимо, чувствовала себя не в силах глядеть на него без смеха, но не могла удержаться, чтобы не смотреть на него, и во избежание искушений тихо перешла за колонну. В середине службы голоса духовенства вдруг замолкли; духовные лица шопотом сказали что то друг другу; старый слуга, державший руку графа, поднялся и обратился к дамам. Анна Михайловна выступила вперед и, нагнувшись над больным, из за спины пальцем поманила к себе Лоррена. Француз доктор, – стоявший без зажженной свечи, прислонившись к колонне, в той почтительной позе иностранца, которая показывает, что, несмотря на различие веры, он понимает всю важность совершающегося обряда и даже одобряет его, – неслышными шагами человека во всей силе возраста подошел к больному, взял своими белыми тонкими пальцами его свободную руку с зеленого одеяла и, отвернувшись, стал щупать пульс и задумался. Больному дали чего то выпить, зашевелились около него, потом опять расступились по местам, и богослужение возобновилось. Во время этого перерыва Пьер заметил, что князь Василий вышел из за своей спинки стула и, с тем же видом, который показывал, что он знает, что делает, и что тем хуже для других, ежели они не понимают его, не подошел к больному, а, пройдя мимо его, присоединился к старшей княжне и с нею вместе направился в глубь спальни, к высокой кровати под шелковыми занавесами. От кровати и князь и княжна оба скрылись в заднюю дверь, но перед концом службы один за другим возвратились на свои места. Пьер обратил на это обстоятельство не более внимания, как и на все другие, раз навсегда решив в своем уме, что всё, что совершалось перед ним нынешний вечер, было так необходимо нужно.
Звуки церковного пения прекратились, и послышался голос духовного лица, которое почтительно поздравляло больного с принятием таинства. Больной лежал всё так же безжизненно и неподвижно. Вокруг него всё зашевелилось, послышались шаги и шопоты, из которых шопот Анны Михайловны выдавался резче всех.
Пьер слышал, как она сказала:
– Непременно надо перенести на кровать, здесь никак нельзя будет…
Больного так обступили доктора, княжны и слуги, что Пьер уже не видал той красно желтой головы с седою гривой, которая, несмотря на то, что он видел и другие лица, ни на мгновение не выходила у него из вида во всё время службы. Пьер догадался по осторожному движению людей, обступивших кресло, что умирающего поднимали и переносили.
– За мою руку держись, уронишь так, – послышался ему испуганный шопот одного из слуг, – снизу… еще один, – говорили голоса, и тяжелые дыхания и переступанья ногами людей стали торопливее, как будто тяжесть, которую они несли, была сверх сил их.