Ключове слово volatile і атаки за часом

    Ð¢Ð°ÐºÐ¸Ðµ часы плохо подходят для атаки по Ð²Ñ€ÐµÐ¼ÐµÐ½Ð¸У бібліотеці 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 в цьому випадку робить код трохи більш стерпним.
 
 Дмитро Мещеряков,
департамент продуктів для розробників

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

0 коментарів

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