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

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

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

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

Многие существующие алгоритмы шифрования, которые в настоящее время используются, такие как наиболее широко используемый алгоритм шифрования 'Расширенный стандарт шифрования (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) должны выполняться, r₁, r₂ являются парой входных масок, является маскированным значением, при этом , и s₁, s₂ являются парой выходных масок, и adr является свободным адресом памяти, cmp является битовой переменной, которая индексирует регистр и является выводом функции MIP^I(r ₂ ; adr; b), R_cmp является регистровым адресом регистра микропроцессора. Обычно используются, по меньшей мере, два регистра R₀ и R₁ в микропроцессоре (т.е. cmp может быть 0 или 1; первый регистр R₀ индексируется/адресуется, если cmp=0, и второй регистр R₁ индексируется/адресуется, если cmp=1). R_b является регистровым адресом регистра микропроцессора. Обычно используются, по меньшей мере, два регистра R₀ и R₁ в микропроцессоре (т.е. b может быть 0 или 1; регистр R₀ индексируется/адресуется, если b=0, и регистр R₁ индексируется/адресуется, если b=1). MIP^I(r ₂ ; 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 матрицей байтов s_i,j, называемых 'состоянием'. Для шифрования каждая составная часть алгоритма шифрования AES (за исключением последней составной части) содержит следующие четыре этапа:

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

.

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

.

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

,

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

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

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) разделяется в три составляющие с:

,

где составляющие p₁ и p₂ называются масками.

Три составляющие p₀, p₁ и p₂ должны обрабатываться таким способом, что предыдущее отношение сохраняется на всем протяжении исполнения алгоритма шифрования. Отметим, что аналогично каждый байт 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 второго порядка по маскированному вводу второго порядка может выполняться следующим образом:

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

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

1. b rand(1).

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

(a) ,

(b) .

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

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

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

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

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

.

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

1. .

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

3. .

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

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

.

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

возвратить .

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

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

(a) запись ,

(b) cmp ,

(c) Rcmp .

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

Вариант осуществления функции 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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