В данном посте мы бы хотели познакомить пользователей Хабра с базовыми правилами программирования криптографических алгоритмов. Этот набор правил под названием «Стандарт криптографического программирования» (“Cryptography coding standard”) был создан в 2013 году по инициативе одного из гуру современной криптографии Жана-Филиппа Омассона. Несмотря на то, что описанные в нем подходы хорошо известны тем, кто профессионально занимается разработкой систем защиты, новичкам и студентам, думаем, будет интересно ознакомиться с предлагаемым текстом, являющимся переводом набора правил с сайта cryptocoding.net.

1. Сравнивайте строки секретных данных за постоянное время

Проблема

Побайтовое сравнение строк может быть использовано для реализации атак, использующих информацию о времени выполнения программы (так называемых тайминг-атаки), например, для подделки кодов аутентификации сообщений MAC (см. об уязвимости в криптобиблиотеке Google Keyczar).

Встроенные реализации функционала сравнения, такие как функция memcmp , метод Arrays.equals (Java) или оператор == (Python), обычно не выполняются за постоянное время. Рассмотрим, например, реализацию [memcmp] из Microsoft CRT:

EXTERN_C int __cdecl memcmp(const void *Ptr1, const void *Ptr2, size_t Count)
{
    INT v = 0;
    BYTE *p1 = (BYTE *)Ptr1;
    BYTE *p2 = (BYTE *)Ptr2;
 
    while(Count-- > 0 && v == 0) {
        v = *(p1++) - *(p2++);
    }
 
    return v;
}

Решение

Используйте функции сравнения, выполняемые за фиксированное время, такие как предлагаемая в библиотеке NaCL:

int crypto_verify(const unsigned char *x,const unsigned char *y)
{
  unsigned int differentbits = 0;
#define F(i) differentbits |= x[i] ^ y[i];
  F(0)
  F(1)
  F(2)
  F(3)
  F(4)
  F(5)
  F(6)
  F(7)
  F(8)
  F(9)
  F(10)
  F(11)
  F(12)
  F(13)
  F(14)
  F(15)
  return (1 & ((differentbits - 1) >> 8)) - 1; /* returns 0 if equal, 0xFF..FF otherwise */
}

Более общая версия этого же подхода следующая:

int util_cmp_const(const void * a, const void *b, const size_t size) 
{
  const unsigned char *_a = (const unsigned char *) a;
  const unsigned char *_b = (const unsigned char *) b;
  unsigned char result = 0;
  size_t i;
 
  for (i = 0; i < size; i++) {
    result |= _a[i] ^ _b[i];
  }
 
  return result; /* returns 0 if equal, nonzero otherwise */
}

Рассмотрим примеры реализации функций сравнения и тестов для 32-битных значений, выполняемых за фиксированное время:

#include <stdint.h>
 
/* Сравнение беззнаковых величин */
/* Возвращает 1 если условие выполнено, 0 в противном случае*/
int ct_isnonzero_u32(uint32_t x)
{
    return (x|-x)>>31;
}
 
int ct_iszero_u32(uint32_t x)
{
    return 1 ^ ct_isnonzero_u32(x);
}
 
int ct_neq_u32(uint32_t x, uint32_t y)
{
    return ((x-y)|(y-x))>>31;
}
 
int ct_eq_u32(uint32_t x, uint32_t y)
{
    return 1 ^ ct_neq_u32(x, y);
}
 
int ct_lt_u32(uint32_t x, uint32_t y)
{
    return (x^((x^y)|((x-y)^y)))>>31;
}
 
int ct_gt_u32(uint32_t x, uint32_t y)
{
    return ct_lt_u32(y, x);
}
 
int ct_le_u32(uint32_t x, uint32_t y)
{
    return 1 ^ ct_gt_u32(x, y);
}
 
int ct_ge_u32(uint32_t x, uint32_t y)
{
    return 1 ^ ct_lt_u32(x, y);
}
 
/* Сравнение знаковых величин */
/* Возвращает 1 если условие выполнено, 0 в противном случае*/
int ct_isnonzero_s32(uint32_t x)
{
    return (x|-x)>>31;
}
 
int ct_iszero_s32(uint32_t x)
{
    return 1 ^ ct_isnonzero_s32(x);
}
 
int ct_neq_s32(uint32_t x, uint32_t y)
{
    return ((x-y)|(y-x))>>31;
}
 
int ct_eq_s32(uint32_t x, uint32_t y)
{
    return 1 ^ ct_neq_s32(x, y);
}
 
int ct_lt_s32(uint32_t x, uint32_t y)
{
    return (x^((x^(x-y))&(y^(x-y))))>>31;
}
 
int ct_gt_s32(uint32_t x, uint32_t y)
{
    return ct_lt_s32(y, x);
}
 
int ct_le_s32(uint32_t x, uint32_t y)
{
    return 1 ^ ct_gt_s32(x, y);
}
 
int ct_ge_s32(uint32_t x, uint32_t y)
{
    return 1 ^ ct_lt_s32(x, y);
}
 
/* Generate a mask: 0xFFFFFFFF if bit != 0, 0 otherwise */
uint32_t ct_mask_u32(uint32_t bit)
{
    return -(uint32_t)ct_isnonzero_u32(bit);
}
 
/* Возвращает x или y в зависимости от значения параметра bit*/
/* Эквивалентно: return bit ? x : y */
uint32_t ct_select_u32(uint32_t x, uint32_t y, uint32_t bit)
{
    uint32_t m = ct_mask_u32(bit);
    return (x&m) | (y&~m);
    /* return ((x^y)&m)^y; */
}

Указанные подходы не дают никаких гарантий: C и C++ используют правило “как если бы”, которое позволяет компилятору реализовывать операции произвольным образом, в случае если наблюдаемое поведение программы (время выполнения не считается наблюдаемым поведением в обоих языках) остается неизменным. Например, рассмотрим следующий вариант ct_select_u32:

uint32_t ct_select_u32(uint32_t x, uint32_t y, _Bool bit)
{
    uint32_t m = ct_mask_u32(bit);
    return (x&m) | (y&~m);
}

Если мы теперь скомпилируем данный код с параметрами clang-3.5 -O2 -m32 -march=i386, то получим в результате:

ct_select_u32:                          
	mov	al, byte ptr [esp + 12]
	test	al, al
	jne	.LBB0_1
	lea	eax, dword ptr [esp + 8]
	mov	eax, dword ptr [eax]
	ret
.LBB0_1:
	lea	eax, dword ptr [esp + 4]
	mov	eax, dword ptr [eax]
	ret

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

Избегайте ветвлений программы, зависящих от секретных данных

Проблема

Если условное ветвление программы (if, switch, while, for) зависит от секретных данных, то исполняемый код, так же как и время его исполнения, зависит от секретных данных.

Классическим примером использования этой уязвимости являются тайминг-атаки на алгоритмы возведения в степень на основе возведения в квадрат и умножения (или удвоения и сложения для алгоритмов, использующих эллиптические кривые).

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

Решение

Утечкам по времени выполнения программы можно противодействовать, вставляя операции-пустышки в ветви программы с тем, чтобы гарантировать фиксированное время ее выполнения. Однако гораздо более надежным является полностью избегать ветвлений, например, путем реализации условных операторов в виде прямолинейной программы. Например, выбор из двух входов |a| и |b| в зависимости от управляющего бита |bit| можно реализовать следующим образом:

unsigned select (unsigned a, unsigned b, unsigned bit) 
{
    /* -0 = 0, -1 = 0xff....ff */
    unsigned mask = - bit;
    unsigned ret = mask & (a^b);
    ret = ret ^ a;
    return ret;
}

Для процессоров Intel возможно более быстрое решение, которое основано на использовании инструкций условного перехода CMOV.

Избегайте обращений к таблице с адресацией, зависящей от секретных данных

Проблема

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

Решение

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

Избегайте циклов, в которых граничное значение счетчика зависит от секретного значения

Проблема

Цикл с граничным значением счетчика, которое зависит от секретного значения непосредственно делает программу уязвимой к атакам по времени выполнения. Например, реализация лестницы Монтгомери (алгоритма возведения в степень) в OpenSSL 0.9.8o допускала утечку информации о логарифме (секретном случайном числе) в алгоритме ECDSA, которую можно было использовать, чтобы получить секретный ключ TLS сервера. Соответствующий программный код представлен ниже. Здесь |scalar| – секретное случайное число, а |scalar->d| – указатель на массив его битов:

/* find top most bit and go one past it */
i = scalar -> top - 1; j = BN_BITS2 - 1;
mask = BN_TBIT ;
while (!( scalar -> d[i] & mask )) { mask >>= 1; j --; }
mask >>= 1; j - -;
/* if top most bit was at word break , go to next word */
if (! mask )
{
  i - -; j = BN_BITS2 - 1;
  mask = BN_TBIT ;
}
for (; i >= 0; i - -)
{
  for (; j >= 0; j - -)
  {
    if ( scalar ->d[ i] & mask )
    {
      if (! gf2m_Madd ( group , & point ->X , x1 , z1 , x2 , z2 , ctx )) goto err ;
      if (! gf2m_Mdouble ( group , x2 , z2 , ctx )) goto err ;
    }
    else
    {
      if (! gf2m_Madd ( group , & point ->X , x2 , z2 , x1 , z1 , ctx )) goto err ;
      if (! gf2m_Mdouble ( group , x1 , z1 , ctx )) goto err ;
    }
    mask >>= 1;
  }
  j = BN_BITS2 - 1;
  mask = BN_TBIT;
}

Решение

Удостоверьтесь, что число итераций во всех циклах ограничено константой (или по крайней мере, некоторой несекретной переменной).

В частности, удостоверьтесь, насколько это возможно, что границы циклов и ситуации, в которых значения счетчика превосходят эти границы или не достигают их, не зависят от контролируемых пользователем входных данных (никому ведь не нужен свой авторский Heartbleed?).

Продолжение следует…