6.2.5. Защита от атак с использованием побочных каналов

Существует целый класс атак, называемых атаками с использованием побочных каналов. Основные два вида таких атак:

• Атаки измерения энергии и радиоизлучения (особенно успешны при взломе смарт-карт).

• Атаки измерения времени (тайминг-атаки, дающие представления об ориентировочном размере секретного ключа).

Защита от атак первого вида криптографическими средствами не обеспечивается. Необходимо предусматривать экранирование физически при помощи конструктивных доработок.

Для борьбы с тайминг-атаками применяются два метода:

• Добавление в конец каждого вычисления случайной задержки.

• Стандартизация времени выполнения операции.

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

Контрольные вопросы

1. Какие бывают виды криптографических протоколов?

2. Для чего предназначен «билет» в протоколе Kerberos?

3. Для чего применяется протокол X.509?

4. Для чего нужна схема предварительного распределения ключей?

5. Для чего нужна схема разделения секрета?

6. В чем отличие между канальным и абонентским шифрованием?

7. Перечислите атаки с использованием побочных каналов.

7.КРИПТОАНАЛИЗ И ПЕРСПЕКТИВНЫЕ НАПРАВЛЕНИЯ В КРИПТОГРАФИИ

7.1. Основные методы криптоанализа.

7.1.1. Атаки на симметричные криптоалгоритмы.

7.1.2. Атаки на хэш-функции и коды аутентичности.

7.1.3. Атаки на асимметричные криптосистемы.

7.2. Перспективные направления в криптографии.

7.2.1. Эллиптические кривые.

7.2.2. Эллиптические кривые над конечными полями.

7.2.3. Алгоритм цифровой подписи EC-DSA.

7.2.4. Квантовая криптография.

7.1. Основные методы криптоанализа

7.1.1. Атаки на симметричные криптоалгоритмы

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

1. Атака с использованием только шифрованного текста (ciphertext-only attack). Самая сложная атака, при которой злоумышленник обладает минимальным объемом информации. Цель атаки – нахождение ключа и/или открытого текста.

2. Атака с известным открытым текстом (known plaintext attack). Злоумышленник знает один или произвольное количество открытых текстов и соответствующих им шифртекстов. Цель атаки – нахождение ключа и/или открытых текстов, зашифрованных на том же ключе.

3. Атаки с избранным открытым текстом (chosen plaintext attack): автономная (offline) и оперативная (online). Злоумышленник имеет возможность сам выбирать один или произвольное количество открытых текстов и вычислять соответствующий ему шифртекст. Набор открытых текстов подготавливается заранее (автономно) или генерируется в процессе атаки (оперативно). Цель атаки – нахождение ключа.

4. Атака с избранным шифрованным текстом (chosen ciphertext attack). Злоумышленник имеет возможность выбирать как открытый текст (получая соответствующий ему шифрованный текст), так и шифрованный текст (с получением соответствующего ему открытого текста). Цель атаки – нахождение ключа.

5. Различающие атаки (distinguishing attack). Любые нетривиальные методы, позволяющие обнаружить различие между идеальным и реальным шифром. Цель атаки – дискредитация криптосистемы.

6. Атаки на основе коллизий. Атака на основе парадокса задачи о днях рождения (birthday attack) на хэш-функции. Двусторонняя атака или «встреча посередине» (meet-in-the-middle attack) на код аутентификации. Цель – подмена-имитация сообщений.

Отдельно различают атаки с использованием активного аппаратного воздействия на криптосистему при помощи различных излучений, вызывающих помехи и ошибки. Данные атаки возникли в связи с массовым использованием интеллектуальных электронных карточек (smart cards).

Метод прямого перебора (brute force).

Данный метод используется при атаках типа 1 и 2. В случае атаки типа 2 на основе полного шифртекста или его фрагмента и соответствующего ему открытого текста осуществляют последовательное расшифрование на всем множестве возможных ключей до совпадения открытого текста. При этом длина известного фрагмента открытого текста должна превышать расстояние единственности. В случае атаки типа 1 при неизвестном открытом тексте вычислительная сложность метода увеличивается, так как необходимо введение дополнительного критерия на «осмысленность» открытого текста.

Метод прямого перебора возможен только при известном алгоритме шифрования и алгоритм, лежащий в его основе, является экспоненциальным.

Стойкость криптосистемы по отношению к методу прямого перебора полностью определяется мощностью ключевого пространства |K| или энтропией ключа (при переборе со словарем). Минимальные требования к энтропии ключа современных симметричных криптосистем – 128 бит. В настоящее время рекомендуется использовать 256-битовые ключи.

Таблица 13. Мощностные характеристики пространства ключей.

Криптосистема	|K|	Среднее время перебора для INTEL ASCI RED
DES	7,21·10^16	9,4 ч
IDEA	3,4·10^38	1,3·10^21 лет
ГОСТ 28147-89	1,16·10^77	1,7·10^58 лет

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

Цель статистического криптоанализа – получение открытого текста или некоторой вероятностной информации о нем. Два основных метода статистического криптоанализа:

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

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

Анализ поточных криптосистем.

При проведении криптоанализа поточных алгоритмов решаются следующее задачи:

1. Распознавание ЛРП:

Если s₀,s₁,… - линейная рекуррентная последовательность с минимальным многочленом m(λ) степени n, то ганкелев определитель

равен 0 для всех k  n + 1 и всех t  0. С другой стороны, если s₀,s₁,… - последовательность независимых случайных величин 0 < p(s_t = 0) < 1, то

при T → ∞ для любого фиксированного натурального k.

2. Оценка параметров ЛРП.

Производится на основе алгоритма Берленкемпа-Мэсси, который позволяет по 2k-отрезку s₀,…,s_2k-1 линейной рекуррентной последовательности определить минимальный многочлен m(λ) если степень последнего не превышает k.

3. Определение начального состояния ЛРП.

Производится на основе опробования различных начальных векторов S₀ и сравнения результатов генерации s₀,s₁,… с известными фрагментами перехваченной искаженной последовательности (шифртекста). Задача упрощается при малом количестве ненулевых коэффициентов характеристического многочлена, что свойственно часто употребляемым прореженным многочленам.

4. Корреляционный анализ (применяется для комбинированных генераторов различных типов).

Анализ блочных криптосистем.

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

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

Первые открытые упоминания в литературе с 1990 года в работах Мерфи, Бихема и Шамира. Методика анализа строится индивидуально для каждого алгоритма и основана на знании пар сообщений m и m’ для которых известны соответствующие шифртексты E_k(m) и E_k(m’) и XOR-разности между ними с рассмотрением разности между промежуточными частями блоков сообщений.

Для двухветвевой сети Файстеля Δm_i = m_i  m’_i. При этом для каждого раунда в отдельности справедливо следующее:

Δm_i+1 = m_i+1  m’_i+1 = Δm_i-1  [f(m_i,K_i)  f(m’_i,K_i)]

Предполагается, что для многих пар входных данных функции f, имеющих одну и ту же XOR-разность, при использовании одного и того же подключа одинаковой оказывается и XOR-разность для соответствующих выходных пар. Формально говорят, что X влечет Y с вероятностью р, если для относительной доли р входных пар с XOR-разностью Х для соответствующих выходных пар XOR-разность оказывается равной Y. Предположим теперь, что имеется ряд значений X, которые с высокой вероятностью влекут определенные разности выходных значений. Тогда если нам с большой вероятностью известны значения Δm_i-1 и Δm_i то мы с большой вероятностью можем определить и Δm_i-₁. А если удастся найти достаточно много таких значений разности, становится возможным определить подключ, используемый функцией f.

Общая стратегия дифференциального криптоанализа основывается на представленной выше методике для каждого раунда шифрования в отдельности. Процедура начинается с рассмотрения двух сообщений открытого текста m и m' с заданной разностью и имеет своей целью получение вероятностных оценок разностей промежуточных результатов последовательно раунд за раундом с тем, чтобы определить вероятностную оценку для разности соответствующих шифрованных текстов. На самом деле получаются вероятностные оценки для двух 32-битовых половинок сообщения (m₁₇ || m₁₆). После этого выполняется шифрование m и m’, чтобы определить реальные разности при неизвестном ключе, а затем , сравнить результат с вычисленными вероятностными оценками. Если результаты совпадают, т.е.

Е_к(m)  Е_к(m’) = (Δm₁₇||m₁₆),

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

Линейный криптоанализ.

Более новым направлением в криптоанализе является линейный криптоанализ. Метод линейного криптоанализа заключается в построении линейной аппроксимации преобразования, выполняемого в ходе шифрования DES. Данный метод позволяет найти ключ DES при наличии 2⁴⁷ известных фрагментов открытого текста, тогда как для дифференциального криптоанализа требуется 2⁴⁷ фрагментов избранного открытого текста.

Пусть для шифра с n-битовыми блоками открытого и шифрованного текста и m-битовым ключом блок открытого текста будет обозначен Р[1],...,Р[n], блок шифрованного текста - С[1],..., С[n], а ключ - К[1],..., K[n]. Тогда определим

A[i,j,…,k] = A[i]  A[j] ...A[k].

Целью линейного криптоанализа является нахождение подходящего линейного уравнения вида

Р[α₁, α₂„..., α_a]  С[β₁, β₂,..., β_b] = К[γ₁, γ₂,..., γ_c],

выполняющегося с вероятностью р  0,5 (где х = 0 или 1, 1 ≤ а, b ≤ n, 1 ≤ с ≤ т, а α, β и γ представляют фиксированные битовые позиции в блоках). Чем больше значение р отклоняется от 0,5, тем более подходящим считается уравнение. После этого вычисляются значения левой части данного уравнения для большого числа пар соответствующих фрагментов открытого и шифрованного текста. Если результат оказывается равным 0 более чем в половине случаев, полагают, что K[γ₁, γ₂,..., γ_c] = 0. Если же в большинстве случаев получается 1, полагают, что K[γ₁, γ₂,..., γ_c] = 1. Достаточное количество полученных таким образом равенств образуют систему, решением которой определяется ключ. Ввиду линейности получаемых уравнений, проблему можно решать для каждого раунда шифрования в отдельности, а полученные результаты затем объединить.