В библиотеке OpenSSL есть довольно любопытная функция с многообещающим именем CRYPTO_memcmp(). Комментарии к ней объясняют, что обычная memcmp() обладает фатальным недостатком™ – время ее работы зависит не только от размера сравниваемых блоков, но и от их содержимого, а это может помочь атакующему осуществить так называемую атаку по времени.
Аналогичные функции есть в ряде других проектов — поиск по запросу constant time memcmp дает несколько тысяч результатов.
Не будем подвергать сомнению необходимость использования функции CRYPTO_memcmp(), а вместо этого рассмотрим, решает ли она поставленную ей задачу.
Сначала сравним «обычную» и «защищенную» реализации memcmp().
«Обычная» устроена так:
int memcmp( const void* f, const void* s, size_t length )
{
const unsigned char* first = f;
const unsigned char* second = s;
while( length != 0 ) {
if( *first > *second )
return 2;
if( *first < *second )
return -5;
length--;
first++;
second++;
}
return 0;
}
Функция может возвращать ноль, отрицательное целое и положительное целое (не обязательно 1 и -1). Естественно, как только найдено первое отличие, продолжать цикл не имеет смысла, поэтому цикл прерывается и функция возвращает управление.
Для сравнения, вот как устроена CRYPTO_memcmp():
int CRYPTO_memcmp( const void* f, const void* s, size_t length )
{
size_t i;
const unsigned char* first = f;
const unsigned char* second = s;
unsigned char magic = 0;
for( i = 0; i < length; i++ ) {
magic |= (first[i] ^ second[i]);
}
return magic;
}
Первое отличие – он возвращает только «ноль» и «не ноль», поэтому для прямой замены memcmp() не годится. Во всех случаях использования этой функции в OpenSSL данное отличие учтено – функция используется только для проверки равенства блоков.
Второе отличие – здесь нет выхода из цикла кроме как после прохождения обоих блоков данных целиком. Ради этого отличия функция и сделана.
УВЫ.
Оптимизирующий компилятор имеет право «сломать» CRYPTO_memcmp() и сгенерировать для нее такой же машинный код, как для обычной memcmp() (естественно, с поправкой на небольшое отличие в семантике их возвращаемых значений). Далее будет подробно рассмотрено, какие возможности есть у компилятора для такой оптимизации. На момент написания поста ни один распространенный компилятор, представленный на gcc.godbolt.org, не делает таких оптимизаций. Тем интереснее – можно запасаться попкорном и следить за их развитием.
Теперь снова посмотрим на реализацию CRYPTO_memcmp(). Одновременно посмотрим на Стандарт C99. В нем нет такого определения «наблюдаемого поведения», как в 1.9/6 Стандарта C++03, зато в 5.1.2.3/3 сказано, что компилятор может удалить код, который не приводит к «нужным побочным эффектам». Далее в 5.1.2.3/6 перечислены минимальные требования, которые включают в себя требования «стабильности volatile объектов в точках следования в том смысле, что в точке следования предыдущие операции доступа закончены, а последующие не начинались». По сути это требование аналогично требованиям 1.9/6 из C++03 – про доступ к объектам, не имеющим квалификатора volatile, снова ничего не сказано.
Пристально смотрим на этот замечательный цикл:
/* i variable value not used after the loop */
for( i = 0; i < length; i++ ) {
magic |= (first[i] ^ second[i]);
}
Задумано, что он заставит компилятор сгенерировать код, который целиком проходит оба блока данных. Но Стандарт не требует ничего подобного. Здесь всего лишь способ вычисления значения переменной magic. С точки зрения Стандарта этот код полностью эквивалентен такому коду (значение переменной i после выхода из цикла может отличаться от первого варианта кода, но это значение после цикла не используется, следовательно, оптимизация допустима):
/* i variable value not used after the loop */
for( i = 0; i < length; i++ ) {
magic |= (first[i] ^ second[i]);
if( magic == UCHAR_MAX )
break;
}
У компилятора достаточно данных для такой оптимизации. Очевидно, что операция |= может либо оставлять разряды переменной magic без изменения, либо проставлять их в 1. Проставлять их в 0 она не может. Как только все разряды установлены, дальнейшие изменения значения переменной magic невозможны.
Может ли компилятор решиться на такую оптимизацию? Второй вариант кода может быть медленнее в случаях, когда данные в сравниваемых блоках одинаковы или первое отличие находится далеко от начала. А мы проверим – скомпилируем оба варианта кода компилятором Visual C++ 9 и для начала убедимся, что машинный код различается так, как мы ожидали.
Так выглядит машинный код цикла без break:
00AF10D3 mov bl,byte ptr [eax+edi]
00AF10D6 xor bl,byte ptr [eax]
00AF10D8 inc eax
00AF10D9 or dl,bl
00AF10DB sub ebp,1
00AF10DE jne wmain+0D3h (0AF10D3h)
Так – в случае цикла с break:
00AF1116 mov edx,dword ptr [esp+1Ch]
00AF111A mov dl,byte ptr [eax+edx]
00AF111D xor dl,byte ptr [eax]
00AF111F or bl,dl
00AF1121 cmp bl,0FFh
00AF1124 je wmain+12Ch (0AF112Ch)
00AF1126 inc ecx
00AF1127 inc eax
00AF1128 cmp ecx,esi
00AF112A jl wmain+116h (0AF1116h)
Во втором случае 10 инструкций вместо 6 и честно добавлены сравнение (инструкция cmp) и условный переход (следующая за cmp инструкция je).
Это должно быть медленнее на десятки процентов и никто на такое не пойдет, правда?
Но в самом худшем случае (при побайтово равных блоках) на Intel Core i5 660 второй код медленнее первого на не более чем 3 процента (естественно, на других процессорах результат может отличаться) – на втором коде хорошо работает предсказание ветвлений, это дает возможность обойтись без сброса конвейера процессора, снижения скорости почти нет. Если отличий между элементами наберется на UCHAR_MAX, а для этого достаточно всего одной пары байт, в которой значение одного байта является поразрядным отрицанием значения другого байта, можно рассчитывать на ускорение (если различие окажется не слишком далеко от начала, конечно, но при различиях на уровне 3 процента в самом худшем случае «не слишком далеко» находится где-то на отметке 97% от начала).
Разработчики компилятора могут добавить эвристику, которая всегда будет в таких случаях компилировать первый вариант кода как второй.
Еще в компиляторе может быть технология профилирования кода (что-то вроде PGO в Visual C++), которая позволяет выполнить код на тестовом пакете и затем оптимизировать его под наиболее типичные сценарии. В этом случае у компилятора будут объективные данные, которые позволяют оценить, есть ли выгода от преобразования кода.
А еще вспомним, что выше показан код для Intel Core i5, а его архитектура – не единственная в мире, на каком-то другом процессоре может быть инструкция, например, объединяющая в себе |=, сравнение и переход, с нулевыми накладными расходами по сравнению с |=. Компилятор, хорошо заточенный под такую архитектуру, непременно использует такую инструкцию и скомпилирует первый вариант кода как второй.
Выше рассмотрены три очевидных способа оптимизации кода, использующие только код ее самой.
Медленно помешивая, добавляем LTO, LTCG или как там называется оптимизация нескольких единиц трансляции в вашем компиляторе. Используя эту технологию, компилятор может одновременно анализировать как код самой функции, так и вызывающий код. Вызывающий код будет выглядеть примерно так:
if( CRYPTO_memcmp( first, second, size ) != 0 ) {
/* blahblhablah */
}
И здесь совершенно очевидно, что цикл в функции эквивалентен такому:
for( i = 0; i < length; i++ ) {
if( first[i] != second[i])
return 3;
}
С таким знанием компилятору гораздо проще применить перечисленные выше три оптимизации.
Такой код как в CRYPTO_memcmp() является непереносимым. Он работает в соответствии с ожиданиями только на конкретных компиляторах с конкретными параметрами сборки.
Как обычно, нужно использовать ключевое слово volatile.
Полностью соответствующий Стандарту способ – добавить переменной magic квалификатор volatile. В этом случае компилятор будет обязан сгенерировать код, который обеспечивает выполнение операций |= на каждой из заданного числа итераций цикла. Компилятор вынужден разместить переменную magic в автоматической памяти и для каждой итерации сгенерировать соответствующий код обновления значения переменной. От этого на Intel Core i5 660 код цикла замедляется примерно вдвое. Насколько это существенно для работы остального кода, нельзя сказать без тщательного профилирования.
Если выяснено, что добавление квалификатора volatile переменной magic приводит к неприемлемому замедлению кода, можно с учетом оговорок ниже попробовать использовать «указатели на volatile»:
int CRYPTO_memcmp( const void* f, const void* s, size_t length )
{
size_t i;
const volatile unsigned char* first = f;
const volatile unsigned char* second = s;
unsigned char magic = 0;
for( i = 0; i < length; i++ ) {
magic |= (first[i] ^ second[i]);
}
return magic;
}
Если const volatile вызывает у вас недоумение – напрасно. const указывает, что данные не могут изменяться из вашего кода, а volatile указывает, что они в принципе могут изменяться и без вашего кода, поэтому чтения оптимизировать нельзя.
Как и в предыдущем посте, это не гарантирует от оптимизации, потому что сами данные могут и не иметь квалификатора volatile (операция доступа по указателю дает lvalue, тип которой не влияет на сами данные), но шансы есть – обычно компиляторы внимательно относятся к коду с такими указателями и код чтений не оптимизируют.
Использование volatile в этом случае делает код немного более переносимым.
Дмитрий Мещеряков,
департамент продуктов для разработчиков
Автор: DmitryMe
