СПОСОБ ПРИМЕНЕНИЯ КОНТРМЕР ПРОТИВ АТАК ПО СТОРОННИМ КАНАЛАМ
METHOD OF USING COUNTERMEASURES AGAINST ATTACKS BY THIRD-PARTY CHANNELS

Область техники
Настоящее изобретение относится к способу принятия контрмер против атак по сторонним каналам для блочных шифров и, в частности, но не исключительно, к способу принятия контрмер, который использует функцию сопоставления по месту.
Уровень техники
Многие существующие алгоритмы шифрования, которые в настоящее время используются, такие как наиболее широко используемый алгоритм шифрования 'Расширенный стандарт шифрования (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
(data; adr,b))
I
Функция сопоставления по месту может быть рандомизированной по битам функцией сопоставления по месту (.
Рандомизированная по битам функция сопоставления по месту может определяться как
,
adr
data
b
data
adr
b. b
где  является адресом в памяти,  является переменной, которая может храниться по адресу в памяти, и  является значением, которое возвращается, если переменная  равняется фактическим данным, которые присутствуют по адресу  в памяти; иначе возвращается дополнение  может быть битовым значением.
Может существовать следующее отношение:
,
b
где  является дополнением .
compare
b
Упомянутая, по меньшей мере, одна из нелинейной функции может содержать функцию , определенную посредством
,
compare
compare
compare
b
b
b
adr
где x является первой входной переменной функции  и y является второй входной переменной функции , и b является значением, которое возвращается, если x равняется y, так что функция  может реализовываться посредством: записи переменной x по адресу  в памяти; исполнения рандомизированной по битам функции сопоставления по месту, определенной как
,
MIP
(y; adr,b)
I
и возвращения .
Нелинейная функция может содержаться в операции SubByte. Нелинейная функция может содержаться в операции SubByte алгоритма AES.
Алгоритм блочного шифра может дополнительно содержать одну или более линейных функций. По меньшей мере, одна из упомянутой одной или более линейных функций может маскироваться посредством применения операции XOR к переменным функции.
Алгоритм блочного шифра может являться алгоритмом Расширенного стандарта шифрования (AES).
Согласно дополнительному аспекту настоящего изобретения обеспечивается машиночитаемый носитель, содержащий компьютерную программу, которая сконфигурирована с возможностью осуществлять способ согласно любому из вышеупомянутых способов.
Согласно дополнительному аспекту настоящего изобретения обеспечивается способ вычисления маскированной функции Sbox второго порядка из маскированного ввода второго порядка, содержащий этапы
,
a
adr
r
; adr; b
r
; adr; b
1
2
1
2
2
cmp
0
1
0
1
b
0
1
0
1
2
I
I
где b является переменной, которая представляет случайный бит, который индексирует регистр, и  является переменной, которая представляет индекс, который определяет количество, сколько раз этапы (a)-(c) должны выполняться, r, r являются парой входных масок,  является маскированным значением, при этом , и s, s являются парой выходных масок, и  является свободным адресом памяти, cmp является битовой переменной, которая индексирует регистр и является выводом функции MIP(), R является регистровым адресом регистра микропроцессора. Обычно используются, по меньшей мере, два регистра R и R в микропроцессоре (т.е. cmp может быть 0 или 1; первый регистр R индексируется/адресуется, если cmp=0, и второй регистр R индексируется/адресуется, если cmp=1). R является регистровым адресом регистра микропроцессора. Обычно используются, по меньшей мере, два регистра R и R в микропроцессоре (т.е. b может быть 0 или 1; регистр R индексируется/адресуется, если b=0, и регистр R индексируется/адресуется, если b=1). MIP() является рандомизированной по битам функцией сопоставления по месту, определенной как
.
Согласно дополнительному аспекту настоящего изобретения обеспечивается машиночитаемый носитель, содержащий компьютерную программу, которая сконфигурирована с возможностью выполнять вышеупомянутый способ вычисления маскированной функции Sbox второго порядка.
Краткое описание чертежей
Изобретение будет более хорошо пониматься с помощью описания одного варианта осуществления, данного в качестве примера и проиллюстрированного посредством фигур, на которых:
фиг.1 показывает псевдокод для шифрования AES;
фиг.2 показывает псевдокод для дешифрования AES;
compare
compare
b
b
фиг.3 показывает таблицу, содержащую количество переносов памяти (фаза предварительной обработки), количество операций XOR и переносов памяти (главная фаза) и память, требуемую для исходного варианта осуществления функции  и варианта осуществления функции  согласно настоящему изобретению;
compare
b
фиг.4 показывает таблицу, содержащую количество операций XOR, количество переносов памяти и память, требуемую для полного второго варианта осуществления алгоритма Ривайна-Доттакса-Проуффа (Rivain-Dottax-Prouff) (RDP2), который использует способ настоящего изобретения для осуществления функции .
Подробное описание возможных вариантов осуществления
Будет подробно описываться использование способа настоящего изобретения в алгоритме шифрования AES. Однако следует понимать, что способ настоящего изобретения не ограничен использованием с алгоритмом шифрования AES; способ настоящего изобретения может использоваться в любом алгоритме блочного шифра.
i,j
[0025] Алгоритм шифрования AES работает над 4×4 матрицей байтов s, называемых 'состоянием'. Для шифрования каждая составная часть алгоритма шифрования AES (за исключением последней составной части) содержит следующие четыре этапа:
AddRoundKey
i,j
1. : к каждому байту состояния применяется операция XOR с раундовым ключом k, выведенным из плана смены ключей
.
SubBytes
2. : каждый байт состояния обновляется с использованием 8-битной функции S-box
.
Функция S-box определяется как
,
8
где Aff является аффинной функцией над GF(2), и
8
является обратной функцией над GF(2) (с ).
ShiftRows
3. : байты состояния циклически сдвигаются в каждой строке на некоторое смещение; первая строка остается неизменной.
MixColumns
4. : байты состояния модифицируются столбец за столбцом следующим образом:
.
Псевдокод для шифрования AES с 128-битным ключом дан на фиг.1. Матрица слов 'w' содержит раундовые ключи , которые генерируются посредством алгоритма плана смены ключей.
Для дешифрования каждый раунд (за исключением последнего) содержит следующие операции:
InvShiftRows
1. : является обратной для операции ShiftRows (этап 3 шифрования). Байты состояния (набор промежуточных переменных, используемых в шифровании AES, как определено в абзаце [0025]) циклически сдвигаются в каждой строке на некоторое смещение; первая строка байтов остается неизменной.
InvSubBytes
2. : является обратной для операции SubByte (этап 2 шифрования). Обратное S-box  применяется над каждым байтом состояния с:
.
AddRoundKey
3. : операция равняется своей собственной обратной.
InvMixColumns
4. : является обратной для операции MixColumns (этап 4 шифрования). Байты состояния модифицируются столбец за столбцом следующим образом:
Псевдокод для обратного шифра дается на фиг.2.
В заключение, план смены раундовых ключей  основывается на следующих операциях:
SubWord
1. : берет четырехбайтное входное слово и применяет S-box (S(x)) к каждому из четырех байтов.
RotWord
2. : берет слово  как ввод и выполняет циклическую перестановку, чтобы возвратить .
Xor с Rcon
3. : берет в качестве ввода 32-битное слово, и к нему применяется операция xor с раундовой постоянной матрицей слов Rcon[i]= для раунда . Мы ссылаемся на [5] для полного описания плана смены ключей.
Как описано во введении, принцип контрмеры маскирования состоит в том, чтобы маскировать каждую промежуточную переменную с помощью одной или более случайных масок. В случае контрмеры маскирования с порядком d=2 используются две маски, что дает в целом три составляющие. Более точно, любая переменная состояния p (представленная как байт в AES) разделяется в три составляющие  с:
,
1
2
где составляющие p и p называются масками.
0
1
2
Три составляющие p, p и p должны обрабатываться таким способом, что предыдущее отношение сохраняется на всем протяжении исполнения алгоритма шифрования. Отметим, что аналогично каждый байт k раундового ключа должен разделяться в три составляющие , так что .
Линейные части блочного шифра легко обрабатываются. Функция f называется линейной, когда выполняется следующее:
Уравнение (1).
Тогда для такой линейной функции, когда заданы как ввод три составляющие  так, что:
Уравнение (1),
является достаточным вычислить  и  отдельно, и, формируя  получаем:
.
AddRoundKey
ShiftRows
MixColumns
SubBytes
Поэтому три выходные составляющие  и  являются действительным разделением выходного f(p). Для шифрования AES операции ,  и  являются линейными функциями и могут, поэтому, обрабатываться таким способом. Однако операция  (такая как функция S-box в случае AES) является нелинейной и должна обрабатываться другим образом.
Чтобы обрабатывать нелинейные операции, такие как функция S-box в случае AES, алгоритм может определяться следующим образом:
.
compare
b
Отметим, что для AES n=m=8. Алгоритм предпочтительно содержит маскированную функцию , определенную следующим образом:
,
compare
b
где x и y являются входными переменными функции .
Вычисление маскированной функции S-box второго порядка по маскированному вводу второго порядка может выполняться следующим образом:
Ввод
1
2
: маскированное значение , где r; r являются парой входных масок, и  являются парой выходных масок.
Вывод
: вывод маскированной функции S-box
1. b  rand(1).
2. Для a=0 по 2n-1 делать
(a) ,
(b) .
b
3. Возвратить R.
compare
compare
compare
b
b
2
b
2
2
При этом  являются входными переменными функции , , тогда cmp=(, r)=(r; r)=b, что дает , как требуется.
compare
compare
b
b
В этом конкретном варианте осуществления необходимо проявлять осторожность при реализации функции . Именно функция (x; y) предпочтительно не должна реализовываться посредством вычисления  напрямую, так как в вышеописанном алгоритме это сводится к вычислению a), которое, комбинируясь с , дает утечку второго порядка.
compare
b
Теперь будет описываться способ, реализующий функцию , чтобы предотвращать любую утечку стороннего канала первого порядка на
compare
b
Напомним, что функция  определяется как
.
n
Способ осуществления требует таблицу T из 2 битов в RAM. Таблица T предварительно обрабатывается следующим образом:
1. .
n
2. Для i=0 по 2-1 делать .
3. .
Это завершает этап предварительной обработки.
В конце этого этапа предварительной обработки таблица T удовлетворяет:
.
compare
b
Затем функция  реализуется как:
возвратить .
В этом случае все промежуточные переменные в вычислении являются независимыми от ; это предотвращает любую утечку стороннего канала первого порядка на .
compare
compare
compare
compare
compare
b
b
b
b
b
n
n
n
n
n
Вышеупомянутый вариант осуществления  является известным в данной области техники. Неблагоприятно, вышеупомянутый вариант осуществления  является неэффективным; алгоритм  требует 2 битов RAM; на практике, однако, может являться более удобным использовать 2 байтов RAM, так как иначе должны использоваться способы битного доступа, что может являться обременительным для реализации защиты. Предварительная обработка требует 2+1 переносов памяти; такая предварительная обработка должна делаться до каждого вызова алгоритма RDP2. Каждый вызов  затем требует две операции XOR и один перенос памяти. Для AES с n=8 функция , поэтому требует 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
adr
I
compare
b
С использованием функции  функция  может просто реализовываться следующим образом, где  является свободным адресом в памяти.
compare
b
(x; y):
x; adr
1. запись (),
MIP
(y; adr; b).
I
2. возврат
adr
MIP
(y; adr; b)
I
compare
b
Как только x записывается по адресу  в памяти, функция  возвращает b, если x=y, и  иначе, как требуется функцией .
MIP
I
С использованием функции  вычисление маскированной функции S-box второго порядка по маскированному вводу второго порядка становится следующей:
Ввод
adr
: маскированное значение , пара выходных масок , свободный адрес памяти .
Вывод
: вывод маскированной функции S-box
1. b  rand(1).
n
2. для a=0 по 2-1 делать
(a) запись ,
cmp
(b) ,
(c) Rcmp .
b
3. Возвратить R.
compare
compare
b
b
MIP
I
Вариант осуществления функции  на основе функции  удовлетворяет такому же свойству, что и исходный вариант осуществления функции ; именно все промежуточные переменные являются независимыми от .
MIP
(y; adr; b)
MIP(y; adr)
MIP(y; adr)
MIP(y; adr)
MIP(y; adr)
I
Отметим, что рандомизированная функция  является предпочтительной. Если вместо этого используется функция  (посредством сначала вычисления  и затем возврата ), то вариант осуществления будет небезопасным, так как промежуточная переменная  не является независимой от .
compare
compare
compare
b
b
b
MIP
I
Фиг.3 показывает таблицу, которая сравнивает эффективность исходного варианта осуществления функции  и варианта осуществления функции  согласно настоящему изобретению (т.е. с использованием функции ). Ясно, что требуется меньше операций и меньше RAM, чтобы реализовывать функцию  согласно настоящему изобретению.
MIP
I
Фиг.4 показывает таблицу, которая сравнивает эффективность алгоритма маскирования, исходно реализованного, и алгоритма маскирования, осуществленного согласно настоящему изобретению (т.е. с использованием функции ). Для AES с n=8 настоящее изобретение требует 1 байта RAM (вместо 2n), 1024 операций XOR (вместо 1536) и 512 переносов памяти (вместо 769). Если операции XOR и переносы памяти имеют одну и ту же стоимость, вариант настоящего изобретения является на 33% более быстрым исходного варианта осуществления. Таким образом, для одного и того же уровня защиты настоящее изобретение обеспечивает более быструю контрмеру, которая требует меньше RAM.
Различные модификации и изменения для описанных вариантов осуществления изобретения должны быть очевидными для специалистов в данной области техники без отхода от объема изобретения, как определяется в прилагаемой формуле изобретения. Хотя изобретение было описано в соединении с конкретными предпочтительными вариантами осуществления, следует понимать, что изобретение, как заявлено, не должно неподобающим образом ограничиваться таким конкретным вариантом осуществления.