СПОСОБ ПРИМЕНЕНИЯ КОНТРМЕР ПРОТИВ АТАК ПО СТОРОННИМ КАНАЛАМ Российский патент 2016 года по МПК G06F21/00 H04L9/06 

Описание патента на изобретение RU2586020C2

Область техники

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

Уровень техники

Многие существующие алгоритмы шифрования, которые в настоящее время используются, такие как наиболее широко используемый алгоритм шифрования 'Расширенный стандарт шифрования (AES)', являются уязвимыми для разностного анализа мощности (DPA). DPA является атакой по сторонним каналам, которая состоит в том, что сначала измеряют потребляемую мощность микропроцессора, когда криптографический алгоритм исполняется, и затем выполняют статистический анализ, чтобы восстанавливать секретные ключи, используемые в криптографическом алгоритме для шифрования. Как только секретные ключи определяются, является возможным дешифровать зашифрованную информацию.

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

Общий способ для защиты алгоритмов секретных ключей против DPA состоит в маскировании каждой промежуточной переменной с помощью случайной маски. Маскированные данные и случайная маска затем обрабатываются отдельно и в итоге рекомбинируются в конце алгоритма. Атакующий, пытающийся анализировать потребляемую мощность микропроцессора в одиночной точке, будет получать случайные значения (случайные значения данных и случайные значения маски); поэтому такое маскирование будет защищенным против DPA первого порядка.

Контрмера маскирования характеризуется количеством случайных масок, используемых, чтобы защищать заданную чувствительную переменную; маскирование с d случайными масками называется маскированием порядка d. Маскирование порядка d может взламываться только посредством анализа стороннего канала порядка (d+1), т.е. атаки, которая требует обработки d+1 переменных одновременно. Количество исполнений, требуемых, чтобы взломать контрмеру, растет экспоненциально с порядком d. Поэтому порядок d является хорошим защитным критерием. Однако на практике наиболее эффективные контрмеры имеют только порядок d=1.

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

Делались дополнительные разработки в контрмерах; одна из наиболее недавних контрмер против атак по сторонним каналам является контрмерой с порядком d=2.

Для любой контрмеры маскирования главной трудностью является защищать нелинейные части алгоритма; для Расширенного стандарта шифрования (AES) нелинейные части алгоритма являются, по существу, функциями SBOX. Используемый способ состоит из осуществления итераций по всей функции SBOX для каждого поиска SBOX, с использованием алгоритма сравнения, который реализуется как подпрограмма. Алгоритм сравнения вызывается для каждого ввода SBOX, при этом является возможным показать, что контрмера может сопротивляться любой атаке по сторонним каналам второго порядка.

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

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

Сущность изобретения

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

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

Функция сопоставления по месту может быть рандомизированной по битам функцией сопоставления по месту (MIP I (data; adr,b)).

Рандомизированная по битам функция сопоставления по месту может определяться как

,

где adr является адресом в памяти, data является переменной, которая может храниться по адресу в памяти, и b является значением, которое возвращается, если переменная data равняется фактическим данным, которые присутствуют по адресу adr в памяти; иначе возвращается дополнение b. b может быть битовым значением.

Может существовать следующее отношение:

,

где является дополнением b.

Упомянутая, по меньшей мере, одна из нелинейной функции может содержать функцию compare b, определенную посредством

,

где x является первой входной переменной функции compare b и y является второй входной переменной функции compare b, и b является значением, которое возвращается, если x равняется y, так что функция compare b может реализовываться посредством: записи переменной x по адресу adr в памяти; исполнения рандомизированной по битам функции сопоставления по месту, определенной как

,

и возвращения MIP I (y; adr,b).

Нелинейная функция может содержаться в операции SubByte. Нелинейная функция может содержаться в операции SubByte алгоритма AES.

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

Алгоритм блочного шифра может являться алгоритмом Расширенного стандарта шифрования (AES).

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

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

,

где b является переменной, которая представляет случайный бит, который индексирует регистр, и a является переменной, которая представляет индекс, который определяет количество, сколько раз этапы (a)-(c) должны выполняться, r1, r2 являются парой входных масок, является маскированным значением, при этом , и s1, s2 являются парой выходных масок, и adr является свободным адресом памяти, cmp является битовой переменной, которая индексирует регистр и является выводом функции MIPI(r 2 ; adr; b), Rcmp является регистровым адресом регистра микропроцессора. Обычно используются, по меньшей мере, два регистра R0 и R1 в микропроцессоре (т.е. cmp может быть 0 или 1; первый регистр R0 индексируется/адресуется, если cmp=0, и второй регистр R1 индексируется/адресуется, если cmp=1). Rb является регистровым адресом регистра микропроцессора. Обычно используются, по меньшей мере, два регистра R0 и R1 в микропроцессоре (т.е. b может быть 0 или 1; регистр R0 индексируется/адресуется, если b=0, и регистр R1 индексируется/адресуется, если b=1). MIPI(r 2 ; adr; b) является рандомизированной по битам функцией сопоставления по месту, определенной как

.

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

Краткое описание чертежей

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

фиг.1 показывает псевдокод для шифрования AES;

фиг.2 показывает псевдокод для дешифрования AES;

фиг.3 показывает таблицу, содержащую количество переносов памяти (фаза предварительной обработки), количество операций XOR и переносов памяти (главная фаза) и память, требуемую для исходного варианта осуществления функции compare b и варианта осуществления функции compare b согласно настоящему изобретению;

фиг.4 показывает таблицу, содержащую количество операций XOR, количество переносов памяти и память, требуемую для полного второго варианта осуществления алгоритма Ривайна-Доттакса-Проуффа (Rivain-Dottax-Prouff) (RDP2), который использует способ настоящего изобретения для осуществления функции compare b.

Подробное описание возможных вариантов осуществления

Будет подробно описываться использование способа настоящего изобретения в алгоритме шифрования AES. Однако следует понимать, что способ настоящего изобретения не ограничен использованием с алгоритмом шифрования AES; способ настоящего изобретения может использоваться в любом алгоритме блочного шифра.

[0025] Алгоритм шифрования AES работает над 4×4 матрицей байтов si,j, называемых 'состоянием'. Для шифрования каждая составная часть алгоритма шифрования AES (за исключением последней составной части) содержит следующие четыре этапа:

1. AddRoundKey: к каждому байту состояния применяется операция XOR с раундовым ключом ki,j, выведенным из плана смены ключей

.

2. SubBytes: каждый байт состояния обновляется с использованием 8-битной функции S-box

.

Функция S-box определяется как

,

где Aff является аффинной функцией над GF(28), и

является обратной функцией над GF(28) (с ).

3. ShiftRows: байты состояния циклически сдвигаются в каждой строке на некоторое смещение; первая строка остается неизменной.

4. MixColumns: байты состояния модифицируются столбец за столбцом следующим образом:

.

Псевдокод для шифрования AES с 128-битным ключом дан на фиг.1. Матрица слов 'w' содержит раундовые ключи , которые генерируются посредством алгоритма плана смены ключей.

Для дешифрования каждый раунд (за исключением последнего) содержит следующие операции:

1. InvShiftRows: является обратной для операции ShiftRows (этап 3 шифрования). Байты состояния (набор промежуточных переменных, используемых в шифровании AES, как определено в абзаце [0025]) циклически сдвигаются в каждой строке на некоторое смещение; первая строка байтов остается неизменной.

2. InvSubBytes: является обратной для операции SubByte (этап 2 шифрования). Обратное S-box применяется над каждым байтом состояния с:

.

3. AddRoundKey: операция равняется своей собственной обратной.

4. InvMixColumns: является обратной для операции MixColumns (этап 4 шифрования). Байты состояния модифицируются столбец за столбцом следующим образом:

Псевдокод для обратного шифра дается на фиг.2.

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

1. SubWord: берет четырехбайтное входное слово и применяет S-box (S(x)) к каждому из четырех байтов.

2. RotWord: берет слово как ввод и выполняет циклическую перестановку, чтобы возвратить .

3. Xor с Rcon: берет в качестве ввода 32-битное слово, и к нему применяется операция xor с раундовой постоянной матрицей слов Rcon[i]= для раунда . Мы ссылаемся на [5] для полного описания плана смены ключей.

Как описано во введении, принцип контрмеры маскирования состоит в том, чтобы маскировать каждую промежуточную переменную с помощью одной или более случайных масок. В случае контрмеры маскирования с порядком d=2 используются две маски, что дает в целом три составляющие. Более точно, любая переменная состояния p (представленная как байт в AES) разделяется в три составляющие с:

,

где составляющие p1 и p2 называются масками.

Три составляющие p0, p1 и p2 должны обрабатываться таким способом, что предыдущее отношение сохраняется на всем протяжении исполнения алгоритма шифрования. Отметим, что аналогично каждый байт k раундового ключа должен разделяться в три составляющие , так что .

Линейные части блочного шифра легко обрабатываются. Функция f называется линейной, когда выполняется следующее:

Уравнение (1).

Тогда для такой линейной функции, когда заданы как ввод три составляющие так, что:

является достаточным вычислить и отдельно, и, формируя Уравнение (1), получаем:

.

Поэтому три выходные составляющие и являются действительным разделением выходного f(p). Для шифрования AES операции AddRoundKey, ShiftRows и MixColumns являются линейными функциями и могут, поэтому, обрабатываться таким способом. Однако операция SubBytes (такая как функция S-box в случае AES) является нелинейной и должна обрабатываться другим образом.

Чтобы обрабатывать нелинейные операции, такие как функция S-box в случае AES, алгоритм может определяться следующим образом:

.

Отметим, что для AES n=m=8. Алгоритм предпочтительно содержит маскированную функцию compare b, определенную следующим образом:

,

где x и y являются входными переменными функции compare b.

Вычисление маскированной функции S-box второго порядка по маскированному вводу второго порядка может выполняться следующим образом:

Ввод: маскированное значение , где r1; r2 являются парой входных масок, и являются парой выходных масок.

Вывод: вывод маскированной функции S-box

1. b rand(1).

2. Для a=0 по 2n-1 делать

(a) ,

(b) .

3. Возвратить Rb.

При этом являются входными переменными функции compare b, , тогда cmp=compare b(, r2)=compare b(r2; r2)=b, что дает , как требуется.

В этом конкретном варианте осуществления необходимо проявлять осторожность при реализации функции compare b. Именно функция compare b (x; y) предпочтительно не должна реализовываться посредством вычисления напрямую, так как в вышеописанном алгоритме это сводится к вычислению a), которое, комбинируясь с , дает утечку второго порядка.

Теперь будет описываться способ, реализующий функцию compare b, чтобы предотвращать любую утечку стороннего канала первого порядка на

Напомним, что функция compare b определяется как

.

Способ осуществления требует таблицу T из 2n битов в RAM. Таблица T предварительно обрабатывается следующим образом:

1. .

2. Для i=0 по 2n-1 делать .

3. .

Это завершает этап предварительной обработки.

В конце этого этапа предварительной обработки таблица T удовлетворяет:

.

Затем функция compare b реализуется как:

возвратить .

В этом случае все промежуточные переменные в вычислении являются независимыми от ; это предотвращает любую утечку стороннего канала первого порядка на .

Вышеупомянутый вариант осуществления compare b является известным в данной области техники. Неблагоприятно, вышеупомянутый вариант осуществления compare b является неэффективным; алгоритм compare b требует 2n битов RAM; на практике, однако, может являться более удобным использовать 2n байтов RAM, так как иначе должны использоваться способы битного доступа, что может являться обременительным для реализации защиты. Предварительная обработка требует 2n+1 переносов памяти; такая предварительная обработка должна делаться до каждого вызова алгоритма RDP2. Каждый вызов compare b затем требует две операции XOR и один перенос памяти. Для AES с n=8 функция compare b, поэтому требует 256 байтов RAM и 257 переносов памяти в течение предварительной обработки. В целом, алгоритм RDP2 тогда требует 6·2n операций XOR, 3·2n+1 переносов памяти и генерирование n+1 случайных битов.

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

Любой процессор имеет обычные инструкций dataсчитывание(adr) и запись(data; adr), которые считывают и записывают некоторые данные по некоторому адресу adr в памяти. В способе сопоставления по месту процессор имеет дополнительную функцию MIP(data; adr), которая работает следующим образом:

.

Другими словами, данные сопоставляются в местоположении памяти adr, и значение по адресу adr никогда не покидает память.

В настоящем изобретении обеспечивается дополнительная функция MIP I, которая является рандомизированной по битам версией функции MIP, определенная следующим образом:

.

Предпочтительно имеется следующее отношение:

.

С использованием функции MIP I функция compare b может просто реализовываться следующим образом, где adr является свободным адресом в памяти.

compare b(x; y):

1. запись (x; adr),

2. возврат MIP I (y; adr; b).

Как только x записывается по адресу adr в памяти, функция MIP I (y; adr; b) возвращает b, если x=y, и иначе, как требуется функцией compare b.

С использованием функции MIP I вычисление маскированной функции S-box второго порядка по маскированному вводу второго порядка становится следующей:

Ввод: маскированное значение , пара выходных масок , свободный адрес памяти adr.

Вывод: вывод маскированной функции S-box

1. b rand(1).

2. для a=0 по 2n-1 делать

(a) запись ,

(b) cmp ,

(c) Rcmp .

3. Возвратить Rb.

Вариант осуществления функции compare b на основе функции MIP I удовлетворяет такому же свойству, что и исходный вариант осуществления функции compare b; именно все промежуточные переменные являются независимыми от .

Отметим, что рандомизированная функция MIP I (y; adr; b) является предпочтительной. Если вместо этого используется функция MIP(y; adr) (посредством сначала вычисления MIP(y; adr) и затем возврата MIP(y; adr) ), то вариант осуществления будет небезопасным, так как промежуточная переменная MIP(y; adr) не является независимой от .

Фиг.3 показывает таблицу, которая сравнивает эффективность исходного варианта осуществления функции compare b и варианта осуществления функции compare b согласно настоящему изобретению (т.е. с использованием функции MIP I). Ясно, что требуется меньше операций и меньше RAM, чтобы реализовывать функцию compare b согласно настоящему изобретению.

Фиг.4 показывает таблицу, которая сравнивает эффективность алгоритма маскирования, исходно реализованного, и алгоритма маскирования, осуществленного согласно настоящему изобретению (т.е. с использованием функции MIP I). Для AES с n=8 настоящее изобретение требует 1 байта RAM (вместо 2n), 1024 операций XOR (вместо 1536) и 512 переносов памяти (вместо 769). Если операции XOR и переносы памяти имеют одну и ту же стоимость, вариант настоящего изобретения является на 33% более быстрым исходного варианта осуществления. Таким образом, для одного и того же уровня защиты настоящее изобретение обеспечивает более быструю контрмеру, которая требует меньше RAM.

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

Похожие патенты RU2586020C2

название год авторы номер документа
СПОСОБ КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ 2018
  • Стахов Сергей Валентинович
  • Плясов Александр Александрович
  • Андреев Алексей Евгеньевич
RU2738321C1
КРИПТОГРАФИЧЕСКОЕ УСТРОЙСТВО, ПРИСПОСОБЛЕННОЕ ДЛЯ ВЫЧИСЛЕНИЯ ЦЕЛЕВОГО БЛОЧНОГО ШИФРА 2016
  • Ритман Рональд
  • Де Хог Себастиан Якобус Антониус
RU2711193C2
ЗАЩИТА ОТ ПАССИВНОГО СНИФФИНГА 2011
  • Шабанн Эрве
  • Бринже Жюльен
  • Ле Тан Ха
RU2579990C2
СПОСОБ И УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ КРИПТОГРАФИЧЕСКОГО ВЫЧИСЛЕНИЯ 2005
  • Дотта Эмманюэлль
  • Шабанн Эрве
  • Карлье Венсан
RU2357365C2
УСТРОЙСТВО И СПОСОБ ВЫЧИСЛЕНИЯ БЛОЧНОГО ШИФРА 2018
  • Ритман, Рональд
  • Бодландер, Мартен, Петер
  • Де Хог, Себастиан, Якобус, Антониус
RU2696334C1
ЭЛЕКТРОННОЕ УСТРОЙСТВО БЛОЧНОГО ШИФРОВАНИЯ, ПОДХОДЯЩЕЕ ДЛЯ ОБФУСКАЦИИ 2014
  • Михилс Вильхельмус Петрус Андрианус Йоханнус
  • Гориссен Паулус Матхиас Хюбертус Мехтилдис Антониус
RU2666281C2
Способ шифрования данных 2018
  • Рыбкин Андрей Сергеевич
RU2710669C1
СПОСОБ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ЦИФРОВОЙ ИНФОРМАЦИИ В ВИДЕ УЛЬТРАСЖАТОГО НАНОБАР-КОДА (ВАРИАНТЫ) 2013
  • Пряхин Евгений Иванович
  • Ларионова Екатерина Владимировна
  • Захаренко Евгений Анатольевич
RU2656734C2
СПОСОБ БЛОЧНОГО ПРЕОБРАЗОВАНИЯ ЦИФРОВЫХ ДАННЫХ НА ОСНОВЕ РЕГИСТРА СДВИГА ДЛИНЫ ВОСЕМЬ С 32-БИТОВЫМИ ЯЧЕЙКАМИ И С ТРЕМЯ ОБРАТНЫМИ СВЯЗЯМИ 2022
  • Задорожный Дмитрий Игоревич
  • Коренева Алиса Михайловна
  • Фомичев Владимир Михайлович
RU2796629C1
ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО И СПОСОБ 2016
  • Де Хог Себастиан Якобус Антониус
  • Ритман Рональд
  • Толхэйзен Людовикус Маринус Герардус Мария
  • Холманн Хендрик Дирк Лодевейк
RU2708439C1

Иллюстрации к изобретению RU 2 586 020 C2

Реферат патента 2016 года СПОСОБ ПРИМЕНЕНИЯ КОНТРМЕР ПРОТИВ АТАК ПО СТОРОННИМ КАНАЛАМ

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

Формула изобретения RU 2 586 020 C2

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

2. Способ по п. 1, в котором функция сопоставления по месту является рандомизированной по битам функцией сопоставления по месту (MIPI (data; adr,b)).

3. Способ по п. 2, в котором рандомизированная по битам функция сопоставления по месту определяется как

где adr является адресом в памяти, data является переменной, которая может храниться по адресу в памяти, и b является значением, которое возвращается, если переменная data равняется фактическим данным, которые присутствуют по адресу adr в памяти; иначе возвращается дополнение b.

4. Способ по п. 3, в котором MIPI (data; adr; b)=MIP (data; adr) , где является дополнением b.

5. Способ по п. 2, в котором упомянутая по меньшей мере одна из нелинейной функции содержит функцию compareb, определенную посредством

где х является первой входной переменной функции compareb и у является второй входной переменной функции compareb, и b является значением, которое возвращается, если х равняется у, и является значением, которое возвращается, если х не равняется у, так что функция compareb может реализовываться посредством: записи переменной х по адресу adr в памяти; исполнения рандомизированной по битам функции сопоставления по месту, определенной как

и возвращения MIPI (у; adr,b).

6. Способ по п. 1, в котором нелинейная функция содержится в операции SubByte.

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

8. Способ по п. 1, в котором алгоритм блочного шифра является алгоритмом Расширенного стандарта шифрования (AES).

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

Документы, цитированные в отчете о поиске Патент 2016 года RU2586020C2

Способ приготовления лака 1924
  • Петров Г.С.
SU2011A1
Способ приготовления лака 1924
  • Петров Г.С.
SU2011A1
Станок для изготовления деревянных ниточных катушек из цилиндрических, снабженных осевым отверстием, заготовок 1923
  • Григорьев П.Н.
SU2008A1
Способ обработки целлюлозных материалов, с целью тонкого измельчения или переведения в коллоидальный раствор 1923
  • Петров Г.С.
SU2005A1

RU 2 586 020 C2

Авторы

Корон Жан-Себастьен

Даты

2016-06-10Публикация

2012-07-25Подача