Как я могу понять, является ли моя реализация C постоянной времени или нет (т.е. устойчива к атакам по времени)

У меня есть код для полиномиального умножения, и он написан на C. Я слышал, что конкретная инструкция может быть «постоянной по времени» в зависимости от архитектуры и модели процессора, и нет никакой официальной документации для этого поведения.Как я могу понять, является ли мой код постоянным временем или нет?

Примечание. Под «постоянным временем» я подразумеваю программное обеспечение или часть кода, устойчивые к атакам по времени. Я использую UBUNTU на ПК i7 10-го поколения.

К сожалению, из-за отсутствия документации от производителя ЦП вы не можете быть на 100% уверены, какие алгоритмы будут или не будут постоянным временем. Тем не менее, безусловно, существуют эмпирические правила, которые можно использовать для снижения риска возникновения проблем.

1. Все, что связано с разветвленным потоком управления или условным выполнением кода, очевидно, является проблемой.
2. Операции сравнения могут быть проблемой, даже если они не используются напрямую для воздействия на поток управления. Проблема в том, что операторы сравнения обычно сохраняют свои результаты в регистрах флагов, а самый простой способ получить отдельный результат из регистра флагов — это часто ветвление или условное выполнение.
3. Булевы значения могут быть проблемой, потому что компилятор может решить заменить операцию, включающую логическое значение, условным выполнением или ветвлением.
4. Время доступа к памяти может варьироваться в зависимости от адреса, к которому осуществляется доступ, и состояния кэша. Это означает, что код, включающий таблицы поиска, имеет высокий риск того, что время не будет постоянным.
5. Умножение и деление могут быть реализованы с использованием алгоритмов, для завершения которых требуется переменное количество циклов, умножение, как правило, безопасно на современных процессорах «приложений», но может не работать на микроконтроллерах. Я бы не считал деление безопасным на любом процессоре.
6. Битовые сдвиги и повороты на переменное количество позиций могут быть проблемой для некоторых ЦП, поскольку они могут превращаться в циклы (как программные, так и аппаратные).
7. Сложение, вычитание, побитовые операции и битовые сдвиги на константу обычно допустимы.

Возможно, вы захотите взглянуть на https://www.bearssl.org/constanttime.html в котором эти вопросы рассматриваются более подробно.

Обратите внимание, что этот отличный ответ принадлежит Брезгливый Оссифрэйдж что они перестали вносить! Я сделал копию и вставку, а затем создал сообщество. Голосование за этот ответ ничего мне не дает. Если можно, проголосуйте за них информационная безопасность.

Из предоставленного примера кода можно определить правильный пароль, синхронизируя код при различных входных данных.

Во-первых, вы не должны проверять пароль напрямую! В по крайней мере, вы должны сначала хэшировать пароль с помощью хэша пароля, такого как Argon2id, и сравнить хэш пароля ввода с хэшем пароля, который вы сохранили во время регистрации пользователя (или когда пользователь в последний раз менял свой пароль).

Более того, вы должны использовать протокол согласования ключей с аутентификацией по паролю, такой как OPAQUE, но на данный момент это может быть выше вашего уровня оплаты, пока они не получат более широкое распространение и внедрение.

Что я могу сделать, чтобы мой код не был уязвим для таких атак по времени?

Лучший способ начать — использовать библиотечную подпрограмму или примитив, который кто-то еще уже написал и есть причина сохранить. Например, в NaCl/libsodium вы можете использовать crypto_verify_32 для сравнения двух 32-байтовых строк, таких как два хэша Argon2id или два кода аутентификации сообщений HMAC-SHA256. Тогда усилия, направленные на то, чтобы ответить на этот вопрос, можно сосредоточить на одном месте, которое будет привлекать много внимания и внимания и будет идти в ногу с прогрессом.

Но скажем, у вас нет crypto_verify_32, или вы хотите реализовать его самостоятельно. Что ты можешь сделать?

Для начала нужно понять, какие операции имеют побочные каналы. Это соблазнительный сказать — как и другие ответы — что побочный канал возникает только из-за рано прервать. Но это еще не все. В общем, есть много операций (здесь написано на C для иллюстрации), что может занять некоторое время, которое зависит от ценности входов — мы называем эти операции переменное время операций, в отличие от постоянное время^*:

• для (i = 0; i < n; i++) if (x[i] == y[i]) return EFAIL; очевидно берет меньше итераций цикла таким образом, практически гарантировано выполнение с переменным временем в зависимости от секретных значений х[я] и у [я].

• Простое секретно-зависимое условное для (i = 0; i < n; i++) if (x[i]) bad++;, если х[я] является секретным, может работать и в переменном времени даже если цикл не прерывается раньше. Почему?

  • Вот грубое приближение. Машинные инструкции, которые может выполнять ЦП, выглядят примерно так:

    0: тмп := х[я]
            перейти к 1, если tmp равно нулю
            плохо := плохо + 1
    1: я := я + 1
            перейти к 0, если я < n
    

    количество инструкций выполняется в зависимости от того, какое значение х[я] находится на каждой итерации: пропускаем плохо := плохо + 1 на некоторых итерациях. Это хорошая модель того, как ранние атаки например, RSA работал как в Основополагающая статья Кохера об атаках по времени: основной модульный цикл возведения в степень вычисляет (скажем) 2048-битное модульное возведение в квадрат безусловно, но вычисляет 2048-битное модульное умножение условно в зависимости от значения секретного показателя. Пропуск умножения существенно меняет время, затрачиваемое на всю операцию.

  • Однако есть и другая причина, и она связана с предсказание ветвления, ключевой элемент дизайна, благодаря которому современные процессоры работают так быстро при многих рабочих нагрузках, даже если вы пишете одинаковое количество кода (скажем, такое же количество машинных инструкций, и каким-то образом вы гарантируете, что им требуется одинаковое количество циклов для вычислений). ) в каждой ветви условного оператора время, необходимое для выполнения, может зависеть от того, каким путем было выполнено условие.

  • В общем, процессоры плохо держат какие инструкции были выполнены секрет, так что не делайте выбор инструкций зависят от секретов.

• Поиск в таблице/массиве может занять разное время в зависимости от того, какая память была закэширована в кеше ЦП. Следовательно, если расположение в массиве из которого вы читаете, зависит от секрета, время, которое требуется, может зависеть от секрета, который был использован для восстановить ключи AES по времени кэширования.

  (Это делает AES довольно сомнительным дизайном в ретроспективе, с его преднамеренным использованием зависимого от ключа поиска в таблице! NIST's опубликованное обоснование (§3.6.2, Атаки на реализации: роль операций) любопытно утверждает, что поиск в таблице «неуязвим для атак по времени», несмотря на многочисленные сообщения о таких атаках, о которых с тех пор сообщалось.)

• Переключение на переменное расстояние, как х = у << г может занять больше времени на некоторых процессорах, если г больше и меньше времени, если он меньше.

  (Это делает RC5 и финалист AES RC6 довольно сомнительный дизайн в ретроспективе, с их намеренным использованием расстояний вращения, зависящих от ключа!)

• На некоторых процессорах умножение может выполняться быстрее или медленнее в зависимости от того, равна ли верхняя половина входных данных нулю или нет.

• Сложение 64-битных целых чисел на 32-битных ЦП в принципе может занять больше времени в зависимости от наличия переноса. Это потому, что, когда Икс, у, и г, являются 64-битными целыми числами, логика х = у + г может выглядеть примерно так:

  инт перенос = 0;
  х[0] = у[0] + г[0];
  если (предыдущее добавление переполнилось)
    перенос = 1;
  х[1] = у[1] + z[1] + перенос;
  

  Следовательно, это время может зависеть от того, происходит ли перенос суммы младших 32-битных половин в сумму старших 32-битных половин. (На практике это обычно касается только экзотических ЦП или других типов побочных каналов, таких как анализ энергопотребления, которые больше относятся к смарт-картам, чем к ноутбукам и телефонам.)

Это может показаться немного ошеломляющим. Что мы можем сделать?

Есть операции, которые обычно делаю выполняются в постоянное время на большинстве процессоров. Они есть:

• Побитовые операции: х и у, х | у, х ^ у, ~ х, и другие, которые не появляются в C, такие как И-с-дополнением.
• Постоянное расстояние смены и ротации как смена х << 3 или вращениех <<< 3 (не стандартный C, но распространенный в криптографии; это означает (х << 3) | (х >> (32 - 3)), если Икс является 32-битным).
• Часто целочисленное сложение и вычитание: х + у, х - у, когда Икс и у являются (скажем) 32-битными целыми числами без знака на 32-битном ЦП и часто даже 64-битными целыми числами на 32-битном ЦП с помощью инструкций ADD-with-carry.
• Иногда целочисленное умножение, но история про умножение сложный, что неблагоприятно для криптографии, потому что умножение довольно хорошо смешивает биты и обладает полезными алгебраическими свойствами.

Чтобы было ясно: я не имею в виду, что компилятор C гарантирует, что эти операции выполняются в постоянное время, если вы используете их в программе на C; Я просто использую нотацию C для операций, которые процессоры обычно выполняются за постоянное время. (Подробнее об этом предостережении чуть позже.)

«Но подождите, — протестуете вы, — как я могу написать полезную программу из этих операций? Без условностей? Без петель? Никаких массивов?

Во-первых, вам не нужно избегать условных выражений, циклов или массивов. вообще. Они просто не могут зависеть от секретов. Например, для (i = 0; i < 32; i++) ... x[i] ... Это хорошо. Но для (я = 0; я < m [0]; я ++) ... не хорошо, если м[0] должно быть секретным, и for (i = 0; i < m[0]; i++) ... tab[x[i]] ... не хорошо, если х[я] предполагается секретным.

Во-вторых, вы все еще можете построить эти вещи! Это немного сложнее. Например, предположим б является uint32_t, равным 0 или 1. Тогда б - 1 либо -1 = 0xffffffff, либо 0 соответственно, поэтому

х = ((b - 1) & z) | (~(б - 1) и у);

причины х = у если б равно 1 или х = г если б равно 0 — очень похоже на х = (б ? у : г), но без ответвления. Очевидно, для этого необходимо вычислить обе у и г, так что есть некоторое влияние на производительность! Точно так же вы можете найти элемент таблицы, выполнив поиск все элементы таблицы и выберите тот, который вы хотите, с помощью побитовых операций, подобных этой. Не так быстро, как х[я], но и не такой дырявый.

В общем, ты может преобразовать программу с условными операторами в логическую схему без условных операторов, даже если вы этого не сделаете. хочу по соображениям производительности. Есть и другие подобные трюки, которые вы можете делать. Вы можете набросать процедуру равенства памяти с постоянным временем, такую ​​как crypto_verify_32 как это, предполагая, что x и y являются массивами uint8_t:

результат uint32_t = 0;
для (я = 0; я < 32; я ++)
  результат |= х[я] ^ у[я];
return ((результат - 1) >> 8) & 1;

Упражнение. Возвращает ли это 0 для равного и 1 для неравного или 0 для неравного и 1 для равного?

Написание таких программ и внедрение криптосистем, таких как X25519, которые поощрять реализации, которые выглядят так, вместо криптосистем, таких как RSA или AES, которые поощрять реализации, включающие ветки, зависящие от секрета, или поиск таблицы, зависящий от секрета, — это хорошее начало для затыкания побочных каналов синхронизации.

Но есть одна загвоздка! Помните, я сказал, что компилятор C не гарантирует постоянное время? Умный компилятор C, такой как Clang/LLVM, может распознавать что умный crypto_verify_32 цикл выше может быть выполнен более эффективно заставив его прерваться раньше, и может свести на нет тяжелую работу, которую вы проделали, чтобы переписать его как логическую схему, работающую в постоянное время. (В других обстоятельствах это может помочь вам, например, преобразовав х = (b ? y : z); в инструкцию условного перемещения, CMOV, без переходов, но обычно вы не можете полагаться на добрую волю компилятора C.)

Есть несколько трюков, которые вы можете сделать, чтобы помешать этому, например, встроенный фрагмент сборки, который заставляет компилятор отбрасывать примерно все предположения для оптимизации:

результат uint32_t = 0;
для (я = 0; я < 32; я ++)
  результат |= х[я] ^ у[я];
asm volatile("" ::: "память");
return ((результат - 1) >> 8) & 1;

Это может работать или не работать с вашим компилятором. Чтобы быть уверенным, вам действительно нужно изучить сгенерированный компилятором машинный код — и даже в этом случае компилятор может выполнить оптимизацию точно в срок, которая переписать машинный код в соответствии с анализом профилирования, особенно в языках высокого уровня, таких как Java. Таким образом, вы можете действительно хотеть напиши логику на ассемблере (или на таком языке программирования, как qhasm, который может генерировать точно настроенную сборку более надежно, чем компилятор C), и просто вызвать его из C.

Возможно, когда-нибудь компиляторы C примут секрет квалификатор, как константа или же изменчивый, что заставляет компилятор генерировать только известные машинные инструкции — в какой-то модели ЦП! — для выполнения в постоянное время при работе с объектом и не позволяет компилятору использовать ярлыки, такие как досрочные прерывания, зависящие от секрета, из петля. Но этот день еще не настал.

Есть также вопрос, какие машинные инструкции фактически выполняются в постоянное время на ЦП, что иногда задокументировано, а иногда надежно. Таким образом, в дополнение к выполнению инженерия чтобы построить свои программы из логических схем, вам также нужно сделать наука чтобы выяснить, какие операции действительно безопасно использовать на ЦП.

Это возвращает нас к исходной точке: вы действительно хотите сосредоточить усилия на поддержании этого в библиотечной процедуре, чтобы каждому программисту не приходилось отслеживать капризы компиляторов (и конструкций ЦП!) в сгенерированном коде и времени. сами по себе, а вместо этого могут оставить это на усмотрение наш дружелюбный соседский медведь.

Существуют ли другие контрмеры, кроме логики постоянного времени? Иногда да.

• Вы можете внедрить случайный шум в свою логику в надежде, что он запутает измерения злоумышленника. Но в их измерениях уже присутствует шум, как в расписании операционной системы, так что им просто нужно взять больше образцов — и оказывается, что шум — это не очень эффективная мера противодействия боковому каналу.

  В частности, искусственный шум увеличивает затраты злоумышленника не более чем на квадрат отношения искусственного шума к истинному шуму, что намного ниже того, что обычно считается приемлемым разрывом для безопасности в криптографии. Так что в основном это стоит вам много времени, ничего не делая.

• Вы можете использовать алгебраические свойства криптосистемы для ее рандомизации, иногда называемой «ослеплением». Например, вместо вычисления у^д мод п куда г является секретным показателем в RSA, вы можете выбрать р наугад вычислить s := r^e mod n куда e*d = 1 (mod (n)), умножить у к с получить (y * r^e) по модулю n, вычислить (y * r ^ e) ^ d по модулю n = (r * y ^ d) по модулю n, а затем разделить р.

  Многие реализации, такие как OpenSSL, используют этот подход, потому что это простой способ модифицировать существующую реализацию криптосистемы, такой как RSA, которая имеет необходимую алгебраическую структуру. Это не такая уж плохая идея, как случайный шум, но она имеет свои издержки: вам нужно проделать дополнительную работу по рандомизации, вам нужна модульная логика деления или инверсии — а по сторонним каналам все еще может происходить утечка информации о р и г. Например, даже слепое модульное возведение в степень приведет к утечке веса Хэмминга г если вы не предпримете дополнительные контрмеры, такие как добавление случайного числа, кратного (н) к г во-первых, что может обнажить дополнительные боковые каналы, и т.д.

• В конкретном случае сравнения двух байтовых строк на равенство (например, двух кодов аутентификации сообщений) разумным вариантом является их хеширование с помощью семейства псевдослучайных функций, такого как HMAC-SHA256, с использованием одноразового секретного ключа. к, и проверьте, HMAC-SHA256_k(x) == HMAC-SHA256_k(y).

  Вероятность ложного срабатывания 1/2²⁵⁶, что является меньшей вероятностью, чем вам когда-либо приходилось беспокоиться. Вы можете безопасно использовать равенство с переменным временем для HMAC, потому что если Икс является нет равно у, то количество времени даже в наивный подпрограмма равенства строк байтов (при условии, что она не выйдет из строя на первом нулевом байте или что-то в этом роде!) будет независима от значений Икс и у: есть вероятность 255/256, что он остановится после одной итерации, вероятность 65535/65536 после двух итераций, и т.д.

  Конечно, это действительно помогает, только если вы можете реализовать HMAC-SHA256 за постоянное время! К счастью, SHA-256 спроектирован так, чтобы его можно было легко реализовать как логическую схему с постоянным временем, поэтому реализации на C иметь тенденцию быть достаточно устойчивым к сторонним каналам — но, скажем, Python доставит вам неприятности из-за небольшого целочисленного кеша, если не из-за чего-то еще.

_{^* К сожалению, терминология немного запутана. Здесь постоянное время Значит это количество времени не зависит от входных данных, и это не то же самое, что асимптотический понятие «постоянного времени» в компьютерных науках, часто обозначаемое как O(1), что просто означает количество времени может варьироваться в зависимости от входных данных, но ограничено константой. Мне жаль. Не я придумал терминологию. Я мог бы выбрать «фиксированное время». против. «переменное время», но уже слишком поздно, «постоянное время» прочно вошло в литературу.}

Вот мои два цента:

Атака по времени использует время, необходимое для выполнения алгоритма на основе разных входных данных.

Возьмем более простую задачу, например найти, существует ли один символ в секретной строке. В традиционном алгоритме вы перебираете строку и возвращаете логическое значение, как только найдете символ. Это займет больше времени, чем дальше находится символ, что приведет к утечке некоторой информации о секретной строке.

Если бы мы хотели сделать это постоянным временем, мы бы сделали так, чтобы поиск персонажа занимал одно и то же время, независимо от того, находится ли он в начале или в конце, например. повторение всей строки и возврат после завершения итерации.

Еще одна вещь, которая требует больше времени, — это ветки. Ветвь — это часть кода, которая может быть выполнена или нет, т.е. если утверждение.

Пример взят из функции умножения GF(2^8):

с ответвлением:

если ((а >> 7) & 1)
    а = (а << 1) ^ многочлен;
еще
    <<= 1

безветвистый:

const uint8_t маска = -((a >> 7) & 1); // 0xff, если установлен старший бит, иначе 0x00
a = (a << 1) ^ (многочлен и маска); // применяет полином, только если маска равна 0xff

Как видите, код с веткой в ​​одном из случаев может сделать на 1 операцию больше, тогда как код без ветки всегда выполняет одни и те же операции.

То, что вы слышали, верно.

Это тяжелая борьба. Компилятор и аппаратное обеспечение не предназначены для того, чтобы помогать вам, и они преднамеренно предназначены для того, чтобы делать вещи, которые мешают тому, что вы пытаетесь сделать.

• Стандарт C ничего не говорит о времени. Компиляторы не пытайтесь чтобы гарантировать, что, если ваш код C выглядит как алгоритм с постоянным временем, он всегда компилируется в машинный код с постоянным временем.

  Один из подходов состоит в том, чтобы подробно изучить, что может сделать компилятор, и как избежать путаницы при оптимизации. Маркировка функций как нетлайн, например, может быть важным.

  Другой подход заключается в полном исключении компилятора из общей картины. Вы можете один раз скомпилировать код C, чувствительный ко времени, в сборку, проверить сборку, чтобы убедиться, что это все еще алгоритм с постоянным временем, проверить код сборки и использовать его, а не исходный код C, в качестве исходного кода при построении программы.

• На уровне машинного кода есть аналогичная проблема. процессоры не пытайтесь чтобы гарантировать, что постоянная последовательность инструкций всегда выполняется в постоянное время. Многие аппаратные механизмы (в частности, кэши) пытаются ускорить работу, но не всегда добиваются успеха. Код может работать медленнее в очень специфических особых случаях, когда ускорение не сработало. Это может привести к утечке информации.

  Я не знаю, как решить эту проблему, кроме как очень хорошо зная аппаратное обеспечение и измеряя.

Мои скромные 2 цента: методы нарезки, если они доступны в вашем случае: https://timtaubert.de/blog/2018/08/bitslicing-an-introduction/

РЕДАКТИРОВАТЬ

Я не хочу дублировать (ухудшать их) слова, которые вы можете прочитать на связанной странице, но меня попросили нечто большее, чем ссылка, поэтому давайте скажем, что по сути битрезинг имитирует аппаратную реализацию в программном обеспечении: представлен весь алгоритм как последовательность атомарных логических операций, которые затем выполняются за постоянное время. Извините, я не могу предоставить более подробную информацию, только недавно я узнал об этой технике во время семинара по передовым методам прикладной криптографии: я не углублялся, но кажется, что вам нужно, учитывая, что вы хотите сделать устойчивым ко времени просто очень специфическая часть вашего кода, поэтому накладные расходы на реализацию могут быть доступны в вашем случае (конечно, это был бы болезненный кошмар для кода с широким охватом)

Вот хорошая новость: ваш алгоритм не должен быть "постоянным временем". Он просто должен быть независимым от входных данных. Хорошо, если есть случайные вариации; они на самом деле полезны, если случайные вариации больше, чем вариации, зависящие от данных.

Доступ к памяти, как известно, выполняется в переменное время. Так что если у вас есть шаблоны доступа, зависящие от данных, это плохо. Был приведен пример, таблица [x[i]].Доступ к x[i] в ​​цикле не является постоянным временем, но время не зависит от данных. Доступ к таблице [x[i]] зависит от данных, поэтому можно получить информацию о данных.

Операции умножения и деления могут зависеть от данных, поэтому вам нужно это проверить.

Если вы можете принять «вероятно, постоянное время» в качестве ответа (а не «определенно постоянное время»), вы можете экспериментально оценить, является ли ваш код постоянным. Сделайте так, я рекомендую инструмент парень. Чтобы процитировать GitHub Readme:

Как это работает? Короче говоря, этот код принимает два разных входных данных, запускает фрагмент кода много раз для каждого входного значения и измеряет сколько времени это занимает. Если есть статистическая разница в (среднее) время, необходимое для запуска с различными входными данными, реализация считается непостоянной во времени. Подробности читайте в нашей бумаги или посмотрите на источник.

И:

Мой код проходит эти тесты. Означает ли это, что это действительно постоянная времени? Точно нет. [...]

Подобный инструмент есть кт-пушок, который использует нечеткое тестирование серого ящика на основе покрытия для обнаружения утечек времени. Подробнее о методике в статье ct-fuzz: фаззинг для выявления утечек времени.

Как с dudect, так и с ct-fuzz, вы не можете быть на 100% уверены, что ваш код C является постоянным, но если есть серьезные утечки времени, вы их найдете. И если инструмент не может найти никакой утечки синхронизации, то вы можете быть «достаточно уверены» в том, что утечки нет.

Несколько других инструментов можно использовать для статического определения того, является ли часть кода C постоянным временем:

• ctgrind, построенный поверх valgrind, отслеживает каждый бит секретной памяти и проверяет, не зависят ли условные операторы от секретных битов.

• КэшАудит, который, согласно его GitHub Readme:

CacheAudit — статический анализатор побочных каналов кэша. КэшАудит принимает на вход 32-битный двоичный файл программы x86 и конфигурацию кэша, и выводит формальные, количественные гарантии безопасности для полный набор противников кеша, а именно те, которые основаны на наблюдение за состоянием кеша, следами попаданий и промахов и выполнением раз.

Поскольку эти инструменты используют статический анализ, вы можете быть более уверены в отсутствии утечки времени, если инструмент не может ее найти. Однако ни один из этих инструментов не имеет точной аппаратной модели того, что происходит, а что нет. Это означает, что они предполагают, что, например, умножение выполняется за постоянное время. Если умножение на самом деле не является постоянным временем, то эти инструменты не обнаружат потенциальных утечек времени. См. Питера Грина отвечать для получения дополнительной информации о том, какие операции могут иметь утечку, но, вероятно, CacheAudit и ctgrind считают их постоянными.

Вы можете выполнять точные временные измерения, используя встроенную функцию __rdtscp(), а затем делать статистику по результатам.

Эта функция предоставляет внутренний 64-битный регистр, увеличивающийся на каждый такт, при этом тактовая частота является официальной частотой процессора, как показано в /proc/cpuinfo после знака @.

Процессоры 10-го поколения должны иметь флаг Constant_tsc, как показано в /proc/cpuinfo.