Регуляризация Bee2

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

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

В библиотеке Bee2 намечена и постепенно реализуется программа регуляризации. На первом этапе мы проводим анализ кода и находим нерегулярные функции. Первичные источники нерегулярности:

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

Вторичный источник — флуктуации времени загрузки данных из массивов в связи с логикой работы кэш-памяти современных процессоров. Флуктуации невелики, и этот источник пока не считается опасным.

Выделенная на первом этапе функция f() представляется в двух редакциях: регулярной и ускоренной нерегулярной. Имена редакциям назначаются с помощью макросов SAFE и FAST соответственно: если директива SAFE_FAST не включена, то
SAFE(f) == f && FAST(f) == f_fast,
если включена, то
SAFE(f) == f_safe && FAST(f) == f.
Базовое имя f всегда поддержано и является именем по умолчанию.

Директива SAFE_FAST дополнительно используется для нерегулярного ускорения обычных (одноредакционных) функций. Основное назначение директивы — анализ падения производительности при регуляризации. Директиву следует включать только тогда, когда регулярность библиотеки не имеет значения. Директива будет поддерживаться вплоть до завершения регуляризации Bee2.

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

Условные обозначения

• [n]a — длинное беззнаковое число, для представления которого в памяти компьютера необходим массив машинных слов длины n. Машинное слово a[0] является младшим, a[n-1] – старшим.

• [type]var — объявление переменной типа type с именем var. Для этого примера достаточно одного типа word — слово машинной длины.

• true = 1, false = 0.

Регуляризация

Нерегулярный алгоритм. Для сравнения по модулю необходим алгоритм сравнения двух чисел.

• Алгоритм cmp(a, b)
• Входные данные: [n]a, [n]b — сравниваемые числа.
• Выходные данные:
  • -1, если a < b
  • 0, если a = b
  • 1, если a > b
• Шаги:
  1. [word]less ← 0, [word]greater ← 0;
  2. Для i = n-1, n-2, …, 0:
     1. less ← less | ~greater & (a[i] < b[i]);
     2. greater ← greater | ~less & (a[i] > b[i]);
  3. Возврат ((less == 0) – 1) | (greater ≠ 0);

Приведенный алгоритм регулярен.

Теперь рассмотрим нерегулярный алгоритм сложения с приведением по модулю. Условимся, что числа [n]a и [n]b меньше модуля [n]m. Из этого следует, что [n]a + [n]b < 2 * [n]m. То есть, если возникает выход за пределы модуля, то вычитаем этот модуль только один раз.

• Входные данные: [n]a, [n]b — слагаемые, [n]m — модуль, [n]c — буфер, в котором после выполнения алгоритма можно считать результат [n]a + [n]b mod [n]m.
• Выходные данные: [n]c ← [n]a + [n]b mod [n]m
• Шаги:
  1. [word]carry ← 0;
  2. Для i = 0, 1, …, n-1:
     1. c[i] ← a[i] + carry;
     2. carry ← c[i] < carry;
     3. c[i] ← c[i] + b[i];
     4. carry ← carry | (c[i] < b[i]);
  3. Если cmp(c, m) ≥ 0 или carry ≠ 0:
     1. [word]borrow ← 0, [word]temp ← 0
     2. Для i = 0, 1, …, n-1:
        1. temp ← m[i] + borrow;
        2. borrow ← temp < borrow;
        3. borrow ← m[i] + temp;
        4. c[i] ← c[i] - temp;
     3. temp ← 0
  4. carry ← 0;
  5. Возвратить c.

Источники нерегулярности. В этом алгоритме источник нерегулярности – условный переход на шаге 3. Необходимо вычитать модуль, когда результат сложения больше либо равен модулю. Но на самом деле результатом сложения является некоторое число [n+1]d, в котором первые n слов совпадают со словами числа [n]c, а d[n] = carry. При carry = 1 заведомо выполняется условие [n]a + [n]b >[n]m. Модифицируем алгоритм таким образом, чтобы вычитать либо 0, либо модуль в зависимости от результата сравнения.

• Шаги:
  1. [word]carry ← 0;
  2. Для i = 0, 1, …, n-1:
     1. c[i] ← a[i] + carry;
     2. carry ← c[i] < carry;
     3. c[i] ← c[i] + b[i];
     4. carry ← carry | (c[i] < b[i]);
  3. [word]subFlag ← carry | сmp(c, m) ≥ 0;
  4. [word]borrow ← 0, [word]temp ← 0
  5. Для i = 0, 1, …, n-1:
     1. temp ← m[i] * subFlag + borrow;
     2. borrow ← (temp < borrow) | (c[i] < temp);
     3. c[i] ← с[i] – temp;
  6. temp ← 0, borrow ← 0, subFlag ← 0, carry ← 0;
  7. Возвратить c.

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

Оптимизация. Уменьшим количество циклов, объединив сложение и сравнение. Так как сравнение чисел происходит от старших слов к младшим, а сложение от младших к старшим, необходимо модифицировать алгоритм сравнения.

• Шаги:
  1. [word]carry ← 0, [word]subFlag ← 1;
  2. Для i = 0, 1, …, n-1:
     1. c[i] ← a[i] + carry;
     2. carry ← c[i] < carry;
     3. c[i] ← c[i] + b[i];
     4. carry ← carry | (c[i] < b[i]);
     5. subFlag ← subFlag & (m[i] == c[i]);
     6. subFlag ← subFlag | (m[i] < c[i]);
  3. subFlag ← subFlag | carry;
  4. [word]borrow ← 0, [word]temp ← 0;
  5. Для i = 0, 1, …, n-1:
     1. temp ← m[i] * subFlag + borrow;
     2. borrow ← (temp < borrow) | (c[i] < temp);
     3. c[i] ← с[i] – temp;
  6. temp ← 0, borrow ← 0, subFlag ← 0, carry ← 0;
  7. Возвратить c.

Можно еще улучшить время работы данного алгоритма. Известно, что побитовое умножение работает быстрее обычного умножения. Поэтому преобразуем алгоритм так, чтобы вместо умножения использовать побитовое умножение. Мы используем умножение на subFlag, который равен 0 или 1, при вычитании модуля. То есть надо так преобразовать subFlag, чтобы все биты этого числа были равны либо нулю, либо единице. Для беззнаковых чисел такое преобразование есть результат выражения 0 - subFlag. Еще избавимся от переменной borrow. Ее роль будет выполнять переменная carry. Изменим имя переменной subFlag на mask, чтобы оно лучше отражало ее новый смысл.

• Входные данные: [n]a, [n]b — слагаемые, [n]m — модуль, [n]c — буфер, в котором после выполнения алгоритма можно считать результат [n]a + [n]b mod [n]m.
• Выходные данные: [n]c ← [n]a + [n]b mod [n]m
• Шаги:
  1. [word]carry ← 0, [word]mask ← 1;
  2. Для i = 0, 1, …, n-1:
     1. c[i] ← a[i] + carry;
     2. carry ← c[i] < carry;
     3. c[i] ← c[i] + b[i];
     4. carry ← carry | (c[i] < b[i]);
     5. mask ← mask & (m[i] == c[i]);
     6. mask ← mask | (m[i] < c[i] );
  3. mask ← mask | carry;
  4. mask ← 0 - mask;
  5. [word]temp ← 0, carry ← 0;
  6. Для i = 0, 1, …, n-1:
     1. temp ← m[i] & mask + carry;
     2. carry ← (temp < carry) | (c[i] < temp);
     3. c[i] ← с[i] – temp;
  7. temp ← 0, mask ← 0, carry ← 0;
  8. Возвратить с.