Безпечне криптопрограммирование. Частина 1

В даному пості ми хотіли б познайомити користувачів Хабра з базовими правилами програмування криптографічних алгоритмів. Цей набір правил під назвою «Стандарт криптографічного програмування» («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.8 o допускала витік інформації про логарифме (секретному випадковому числі) в алгоритмі 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?).

Продовження слідує…

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.