Для построения AMD кодов используются различные математические объекты: коды аутентификации, разностные структуры, помехоустойчивые коды [7]. Одной из наиболее развитых и эффективных конструкций сильных AMD кодов является конструкция, основанная на полиномах. Наиболее полно этот класс AMD кодов описан в [9]. Значительная часть конструкций, предлагаемых в этой работе, являются оптимальными в смысле вероятности обнаружения ошибки.

Далее будут рассматривать коды над полями характеристики 2. Кодовые слова систематического AMD кода представляют собой конкатенацию информационного сообщения , некоторого случайного числа и значения нелинейной функции , заданной в виде полинома. Сами AMD коды определяются как коды, для которых не существует такой конфигурации ошибок и такого значения , при возникновении которых равенство выполнится при всех возможных значениях . Данное равенство называется уравнением маскирования ошибки (УМО). Способность AMD кода обнаруживать ошибки напрямую зависит от вида его УМО: максимальное количество решений УМО относительно для всех возможных комбинаций и будет максимальным количеством необнаруживаемых кодом ошибок. Вероятность обнаружения ошибки ограничена снизу следующим выражением:

Сильно защищенные коды на базе надежных кодов

Кодовая конструкция

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

Рассмотрим следующую кодовую конструкцию.

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

Таким образом, кодовое слово рассматриваемого кода можно записать как

Теорема. Данный код при является сильным AMD кодом с вероятностью обнаружения ошибки .

Доказательство:

Как уже было написано, обнаруживающая способность AMD кода напрямую зависит от максимального количества корней его уравнения маскирования ошибки. УМО рассматриваемого кода выглядит следующим образом:

Проанализируем количество корней уравнения маскирования ошибки. Согласно теории надежных кодов, количество решений УМО не превышает двух (за счет использования APN функции). То есть, для любой конфигурации ошибок существует не более двух значений , при которых выполнится равенство в УМО.

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

.

Рассмотрим пример: пусть =4, =2, тогда =6. В качестве функции кодирования выберем возведение в третью степень в поле Галуа, . Итоговый код будет иметь скорость , гарантируя при этом вероятность обнаружения любой сильной атаки (алгебраической манипуляции) .

Стоит отметить, что при равномерно распределенной ошибке (слабая модель атаки) вероятность обнаружения ошибки при использовании предлагаемого кода будет равна против в случае сильной атаки. Это следует из свойств надежных кодов [6].

Сравнение с AMD-кодами на базе обобщенных кодов РМ

В данном разделе приводится сравнение описываемой кодовой конструкции с AMD кодами из [9], которые основаны на обобщенных кодах Рида-Маллера.

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

Сравнение кодов с одинаковой скоростью. Пусть есть описанный код с , и , . Согласно [11] можно построить код (увеличив размер случайного числа и проверочной части так, чтобы скорость кодов совпадали) с , и , вероятность обнаружения ошибки которого ограничена снизу величиной . Из этого следует, что при заданной скорости кода конструкция из [9] демонстрирует более высокий уровень защиты от алгебраических манипуляций.

Стоит отметить, что при слабой модели атаки, когда вносимые ошибки равновероятны, предлагаемый код не обнаруживает ошибки с вероятностью в раз меньше, чем коды из [9].

Заключение

Данную кодовую конструкцию можно рассматривать как обобщение надежных кодов на случай сильной модели атаки. С увеличением размера случайного числа обеспечивается рост вероятности обнаружения сильных атак. Частным случаем данной конструкции при являются надежные коды, обнаруживающие только слабые атаки. Несмотря на то, что кодовые конструкции из [11] обладают меньшей избыточностью, обобщенные надежные коды обладают рядом преимуществ:

· возможность и простота динамического изменения скорости кода за счет изменения соотношения количества информационных и случайных битов в кодируемом сообщении. Фактически, кодек обобщенных надежных кодов может содержать в себе некоторый набор кодов с разными характеристиками. Данная особенность позволяет использовать один кодек для различных типов памяти или различных режимов работы устройства;

· процедура исправления повторяющихся ошибок, описанная для надежных кодов в [10]. За счет нее предлагаемый код способен исправлять ошибки, которые проявляются на 3 и более тактах работы устройства, за счет решения системы уравнений. Подобная процедура для кодов из [9] требует значительных аппаратных, информационных и вычислительных затрат [11];

· высокая помехоустойчивость при слабой модели атаки.

Описанный обобщенный надежный код совмещает в себе как надежный, так и сильно защищенный AMD коды, обеспечивая вероятность обнаружения ошибок и , соответственно.

Литература

1. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977, 762 p.

2. J. J. Quisquater and F. Koeune. Side chanel attacks. Report, October 2003.

3. Biham E., Shamir A., Provable Security Against Differential Cryptography // Crypto 1990, Lecture Notes in Computer Science. 1991. V. 537. P. 2-21.

4. C. N. Chen and S. M. Yen. "Differential Fault Analysis on AES Key Schedule and Some Countermeasures". ACISP 2003, LNCS 2727, pp18-129, 2003.

5. P. Dusart, G. Letourneux, O. Vivolo. "Differential Fault Analysis on AES”. Cryptology ePrint Archive, Report 2003/010.

6. K. D. Akdemir, Z. Wang, M. G. Karpovsky, and B. Sunar.  "Design of Cryptographic Devices Resilient to Fault Injection Attacks Using Nonlinear Robust Codes".  Fault Analysis in Cryptography, M.  Joye Editor, 2011.

7. E. Jongsma. "Algebraic Manipulation Detection Codes". Bachelorscriptie, Mathematisch Instituut, Universiteit Leiden, 6 maart 2008.

8. М. Э. Тужилин. Почти совершенные нелинейные функции // ПДМ, 2009, № 3, 14-20.

9. Z. Wang and M. G. Karpovsky, "Algebraic Manipulation Detection Codes and Their Application for Design of Secure Cryptographic Devices", Proc of Int. Symp. on On-Line Testing, 2011.

10. K. Kulikowski, M. G. Karpovsky, "Robust Correction of Repeating Errors by Nonlinear Codes",   Communications, IET, Vol 5 pp2317-2327, 4, 2011.

11. Z. Wang and M. G. Karpovsky, "Reliable and Secure Memories Based on Algebraic Manipulation Correction Codes", Proc Int Symp. on On-line Testing, June 2012.

12. R. Cramer, Y. Dodis, S. Fehr, C. Padro, and D. Wichs, “Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors,” in Proceedings of the theory and applications of cryptographic techniques 27th annual international conference on Advances in cryptology, ser. EUROCRYPT'08, 2008, pp. 471-488.

Размещено на Allbest.ru