Ключевое слово 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 в этом случае делает код немного более переносимым.

    Дмитрий Мещеряков,
    департамент продуктов для разработчиков
    ABBYY
    140.22
    Решения для интеллектуальной обработки информации
    Share post

    Comments 21

      –6
      del
        +4
        >> Как и в предыдущем посте, это не гарантирует от оптимизации, потому что сами данные могут и не иметь квалификатора volatile (операция доступа по указателю дает lvalue, тип которой не влияет на сами данные)

        В вашем примере как раз данные и имеют квалификатор volatile, а указатель на них — нет. Соответственно, при разыменовании у вас будет volatile lvalue, и компилятор обязан её прочитать.
          +1
          lvalue имеет квалификатор volatile, а сама переменная — в зависимости от того, как она была объявлена.
            +1
            В данном случае у вас объявлен не-volatile указатель на volatile-данные. Что, собственно, и требуется. Т.е. в этом варианте компилятор обязан прочитать все элементы, тут нет никаких других вариантов.
              +1
              Подскажите, пожалуйста, где именно в Стандарте написано, что при манипуляции с переменной через volatile lvalue компилятор обязан обращаться с ней так, как будто сама переменная объявлена volatile.
                0
                В Стандарте в контексте volatile вообще нет разговора о переменных — там используется термин volatile object. Конкретно, C++11 1.9[intro.execution]/8:
                The least requirements on a conforming implementation are:
                — Access to volatile objects are evaluated strictly according to the rules of the abstract machine.

                и /12:
                Accessing an object designated by a volatile glvalue (3.10), modifying an object, calling a library I/O function, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment. Evaluation of an expression (or a sub-expression) in general includes both value computations (including determining the identity of an object for glvalue evaluation and fetching a value previously assigned to an object for prvalue evaluation) and initiation of side effects.

                  +1
                  Вы пропустили вот эту важную формулировку из /8:
                  These collectively are referred to as the observable behavior of the program.
                  В /8 говорится про необходимость обеспечить выполнение операций доступа к volatile objects (objects — это переменные (1.8/1)), эти операции относятся к наблюдаемому поведению, которое необходимо сохранять, а в /12 говорится, что определенный набор действий относится к побочным эффектам, про их относимость к наблюдаемому поведению и необходимость их сохранить ничего не сказано.
                    0
                    Переменные — это объекты, но объекты — это далеко не только переменные. «An object is a region of storage».
                      +2
                      Да, но lvalue — это не object и не region of storage, в 3.10 говорится, что lvalue designates an object (обозначает объект).
                        +2
                        Тут все упирается в несколько мутное определение понятия object. С одной стороны, написано так:

                        «An object is created by a definition (3.1), by a new-expression (5.3.4) or by the implementation (12.2) when needed.»

                        При этом 12.2 — это исключительно temporaries, поэтому про них можно пока забыть.

                        С другой стороны, если есть вот такой вот код:
                        int* p = (int*)malloc(sizeof(int));
                        

                        То в нем *p — это, определенно, объект (точнее, lvalue, которая его обозначает) — хотя ни объявления, ни new здесь не было.

                        Но есть и 3.8/1, где сказано:

                        «The lifetime of an object of type T begins when:
                        — storage with the proper alignment and size for type T is obtained, and
                        — if the object has non-trivial initialization, its initialization is complete.»

                        Очевидно, что malloc(sizeof(int)) выделяет память достаточного размера и выравнивания для int. Т.е. вроде как у нас есть int. Но эта память имеет размер и выравнивание, подходящие и для const int, и для volatile int, а на 32-битных реализациях — и для long, и для указателей самых разных типов. Возникает вопрос: сколько объектов на самом деле «создал» malloc?

                        На эту тему на comp.std.c++ периодически случаются холивары. Распространено мнение, что это такая как бы квантовая штука — т.е. там одновременно разом существуют объекты всех POD-типов, для которых это валидный storage (размер + выравнивание). Т.е. такой неявный union с соответствующей семантикой, в котором, как и в случае с обычным, можно работать только с объектом одного типа за раз, за исключением случаев, оговоренных семантикой union'ов — разница в cv qualifiers, структуры с common initial sequence и т.д.

                        Если принять это, то в вашем случае там «существует» объект типа volatile char, который и читается через указатель соотв. типа.
                          +5
                          Вот. Мутное определение, холивары и «если принять». Раз в Стандарте не прописано ясно и четко, как вы можете доказать, что volatile lvalue обязывает обращаться с соответствующим объектом как будто тот имеет квалификатор volatile?

                          Нет, я не говорю, что ваши рассуждения лишены здравого смысла, но пока что-то не прописано в Стандарте, утверждать, что именно так правильно и все реализации должны именно так работать, нельзя.
          0
          Проводился ли вообще анализ того, какие оптимизации делают другие компиляторы?

          Скажем, LLVM версии выше 3.0 должна детектировать magic как переменную редукции. Соответственно, использовать векторные инструкции для операции свертки. Условие в цикле тоже вполне себе векторизуется. Так что очень странно, что код (по вашим словам) не был оптимизирован.

          Подробнее можно почитать здесь: llvm.org/docs/Vectorizers.html
            +2
            В данном случае векторизация кода не страшна — для блоков одного размера векторизованный код будет всё равно работать одинаково долго.
              0
              Я понимаю, меня просто удивило почему в листинге не было этого видно. Одно дело, если специально запрещали векторизацию, другое если нет.
                0
                Машинный код в посте получен Visual C++9 исключительно с целью сравнить варианты с break и без.
                0
                В данном случае векторизация кода не страшна — для блоков одного размера векторизованный код будет всё равно работать одинаково долго.
                Зависит от реализации. Даже если magic — переменная редукции, ничто не помешает добавить проверку результатов вычисления на части массива magic_for_array_part == UCHAR_MAX и быстрый возврат результата, потому что такая проверка на результат не повлияет. Будет ли от этого выгода и сделает ли так конкретный компилятор — вопрос, но техническая возможность есть.
              0
              А чего переживать о снижении производительности на пару процентов? Это функция ведь не будет применяться повсеместно — только для каких-нибудь паролей\хешей, которые не так уж и часто надо сравнивать.
                +8
                Насколько мне известно, такие решения обычно принимают на основании результатов профилирования или других измерений, а не на основании субъективной оценки переживаний.
                +6
                Вообще конечно сама идея бредом попахивает. С тайминг-атаками нужно бороться квантованием времени (ну, например, все чувствительные к таким векторам атак ответы функций класть в очередь по времени и отдавать с задержкой не менее 1 мс или там 100 мс).
                А сознательно грузить сервер ненужной работой… гринписа на них не хватает.
                  +1
                  Этот подход подойдет для системы, у которой атакующий может измерять только время ответа. Если атака идет на систему вроде смарт-карты, у которой атакующий может также измерять энергопотребление, ситуация усложняется — переход от активных вычислений к пассивному ожиданию, возможно, будет сопровождаться заметным изменением энергопотребления, в этом случае осуществима та же атака по времени, но время нужно будет измерять не до момента выдачи ответа, а до момента снижения энергопотребления.
                  +1
                  Был у меня случай похожий, когда программист одного прикладного проекта написал тесты, но счётчик цикла, как оказалось по незнанию, «заволотайлить» забыл, что в итоге привело бы к очень грустным последствиям, благо мну этот недочёт заметил сразу.

                  Мораль вообще очень проста, хочешь что бы код делал именно то, что ты написал, используй volatile.

                  Only users with full accounts can post comments. Log in, please.