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?).
Продолжение следует…
Комментарии (19)
monah_tuk
02.10.2015 16:10Указанные подходы не дают никаких гарантий: C и C++ используют правило “как если бы”, которое позволяет компилятору реализовывать операции произвольным образом, в случае если наблюдаемое поведение программы (время выполнения не считается наблюдаемым поведением в обоих языках) остается неизменным.
У меня резонный (возможно) вопрос: а почему не организовывать сравнение таких переменных как если бы это был просто буффер из 2-4-8 байтов? Стандартная memcmp() возвращает значения <, == или > в зависимости от того «больше», равен или «меньше» буффера переданные для сравнения. Повторить подобное поведение в time-const реализации, думаю, возможно. Или где я не прав?
vilgeforce
02.10.2015 21:30Главное правило: доверьте криптографию профессионалам. Допустить ошибку легко, а найти — очень сложно…
MichaelBorisov
03.10.2015 14:32+5доверьте криптографию профессионалам
Эту фразу можно сравнить с диагностическим сообщением: «Обратитесь к системному администратору». Особенно доставляет, когда ты сам администратор и пытаешься получить хоть какую-то информацию о проблеме.
Профессионалы-то в криптографии не Свыше к нам нисходят. Они тоже люди, им надо где-то учиться, обмениваться опытом.
qw1
04.10.2015 10:17Найти бекдор, оставленный профессионалом, ещё сложнее.
Интересно, почему редко используются комбинации шифров. Например, AES в реализации Microsoft + ГОСТ в какой-то рекомендованной реализации.
d1g1
03.10.2015 14:03+2Выступление «Crypto coding v2» от Жана-Филиппа на ZeroNights 2014 www.youtube.com/watch?v=Ekju_HyytFE
Ivan_83
05.10.2015 12:13Вообще то проще сразу пролистать: https://cryptocoding.net/index.php/Coding_rules
и не утруждать себя чтением сотни публикаций сделанных ради палок на хубре.
Касательно таблиц — далеко не всегда получается от них отказаться, поэтому есть варианты с очисткой кеша и наоборот с тем чтобы помещать в кеш всю таблицу перед обращением.
А в остальном, большая дилемма: сделать чтобы код выполнялся за 0,001 секунды но вот с такими тайминг особенностями или сделать чтобы он выполнялся за постоянное время, пусть даже 1 секунду.
Притом это не совсем шутка, относительно разницы вычислений в ECDSA примерно так и есть.
В этом плане ECDSA с одной стороны очень проблемный алгоритм потому что там десятки если не сотни мест где вычисления оптимизируются в зависимости от входных данных, с другой стороны этого шума много и хз как из него выделять именно ключ, более того, для подписывания (умножение точки на заранее известный скаляр (закрытый ключ)) существует 5+ разных алгоритмов, которые пред вычисляют на основе закрытого ключа типа подключи, которые потом используются для вычисления подписи.
Потом конкретно мой код может очень сильно по разному скомпилироватся в зависимости от опций компилятора (это не считая выбора алгоритма описанного выше) и это тоже будет влиять на генерируемый шум.
Я клоню к тому, что тайминг атаки легко проводить на простые алгоритмы, для которых заранее известно как примерно оно выглядит в коде, для более сложных, типа AES, уже сложнее и обычно атакующему нужно знать реализацию и опять же иметь контроль над входными данными.
Про атаки на RSA в деталях не читал, думаю там тоже была заранее известная реализация (те исследователи знали как она шумит и как это интерпретировать) и контроль на входные данные.
2 lorc:
У этого правила есть три фатальных недостатка:
1. Те кто немного слышал об ошибках реализации и особенностях следуя этому правилу низачто не возьмутся и близко ничего кодить связанного с крипто, ведь у них нет 100+ лет опыта в этой области.
2. Те кто немного умеют писать ХэллоВорд с радостью напишут любое крипто, их сознание не затуманено ограничениями, мифами и фобиями, перед их ногами целый новый мир криптографии и они его завоёвывают!
3. Люди из п1 наивно полагают что всю криптографию пишут люди сильно умнее их… :)
А вообще, это правило относится к созданию криптоалгоритмов, а не к их реализации и уже тем более встраиванию.
Порог для создания реально хороших крипто алгоритмов действительно высок.
С реализацией существующих, а тем более приклеиванием на сопли готовых криптолиб всё сильно проще, это не означает что накосячить там нельзя, просто уровень для правильного реализации / применения требуется намного ниже.
2 dateless:
Мне вот тут тоже некоторые говорят что я спец по крипте, только потому что осилил ECDSA / ГОСТ реализовать с нуля.
Тоже смешно, ибо взять и собрать по готовой схеме совсем не тоже самое что эту схему создать, протестировать и опубликовать для других.
ru_crypt
05.10.2015 13:39Здравствуйте, Иван!
«А в остальном, большая дилемма: сделать чтобы код выполнялся за 0,001 секунды но вот с такими тайминг особенностями или сделать чтобы он выполнялся за постоянное время, пусть даже 1 секунду.»
Во-первых, боюсь, Вы все же существенно преувеличиваете. Как Вы понимаете, аспекты реализации ГОСТ Р 34.10-2001/ГОСТ Р 34.10-2012 и ECDSA практически не отличаются, а вопросы быстродействия в обоих случаях сводятся, в первую очередь, к грамотному выбору методов вычисления кратной точки.
Так вот я не могу привести пример адекватного метода защиты от атак по побочному каналу по времени, которые бы замедляли время работы в тысячу раз. Вопросы построения безопасных реализаций российских криптоалгоритмов регулярно обсуждаются на РусКрипто и CTCrypt, о разнице в три десятичных порядка, к счастью, речь никогда не заходит.
Если Вам подобные методы известны, будем благодарны, если расскажете.
Во-вторых, описанная Вами дилемма может возникать исключительно в двух случаях: написания криптобиблиотечки «для себя»/студентом для сдачи практикума либо в случае написания специальной реализации криптографии для специфичной задачи внутри закрытой со всех сторон системы. В случае же, когда криптографические механизмы планируется применять в широком спектре реальных систем (для которых нельзя раз и навсегда дать гарантии отсутствия нарушителя, имеющего доступ к информации о времени работы), пренебрегать побочкой по времени совершенно недопустимо. И я говорю даже не о сертификации криптосредств (не суть важно по чему — по требованиям ФСБ или по FIPS), а об элементарной ответственности за свой код.
«Про атаки на RSA в деталях не читал, думаю там тоже была заранее известная реализация (те исследователи знали как она шумит и как это интерпретировать) и контроль на входные данные.»
Разумеется, всё противодействие атакам по побочным каналам обязано производиться в предположении, что код реализации нарушителю известен.
dateless
06.10.2015 20:24А есть ли в открытом доступе требования ФСБ к стойкости по второстепенным каналам?
Мне кажется, что ни FIPS, ни Common Criteria четко не определяют требования встраиваемых систем к стойкости по второстепенным каналам (кроме смарт-карт, но они не совсем встраиваемые системы). Такие стандарты еще только пишутся (опять же, по моему опыту).ru_crypt
07.10.2015 11:19В открытом доступе таких требований ФСБ, конечно, нет.
Четкость требований в таких вопросах в принципе невозможна – как и четкость формулировок свыше общих «стойкость к атакам по побочным каналам».
Я говорил о том, что сертифицировать криптосредство, время операции с ключом в котором будет давать существенную информацию о ключе, вы не сможете. Надеюсь, и не захотите.
Но и здесь от размытости формулировок («существенную») не уйти.
dateless
06.10.2015 20:192 Ivan_83
Я с вами соглашусь в некоторой части рассужденй о сложности атак по второстепенным каналам, но мне кажется, вы фактически приходите к выводу, что такие атаки в реальности не страшны (хотя это вечный спор). Это не совсем так. Даже к OpenSSL периодически прикручивают защиту от атак по времени (CVE CAN-2003-0147). Всегда можно придумать модель, в которой вы знаете код, но не знаете ключ. Поэтому изначально протестировав на собственных примерах, можно найти уязвимость.
Реальные атаки по второстепенным каналам практически не встречаются в открытых источниках, возможно, потому что их авторы хотят сохранить анонимность. Обнаружить такие атаки сложно — это же не DDoS.
В Kudelski Security просто так не дают должность Principal Cryptographer, поэтому Jean-Philippe без сомнения хорош.
Как и в любом деле, реализовав крипто алгоритм вы не станете спецом по криптографии, но вы определенно чему-то научитесь. Я не до конца понял, к чему адресованы последние два предложения.
lorc
А где правило номер 0?
«Не используйте самостоятельно имплементированые алгоритмы в продакшене». Ну или более строгий вариант: «Не нужно имплементировать криптоалгоритмы самостоятельно».
Godless
Это, кстати, не очень тривиально для новичков…
toxicdream
Почему? Любой «гений» может додуматься до какого-нибудь шифра Цезаря, а потом еще с пеной у рта доказывать гениальность своего решения…
Godless
Под «Это» я и имел ввиду «НЕ использовать свои реализации»
mibori
еще более строгий: «Не нужно имплементировать криптоалгоритмы».