Обратите внимание, что этот отличный ответ принадлежит Брезгливый Оссифрэйдж что они перестали вносить! Я сделал копию и вставку, а затем создал сообщество. Голосование за этот ответ ничего мне не дает. Если можно, проголосуйте за них информационная безопасность.
Из предоставленного примера кода можно определить правильный пароль, синхронизируя код при различных входных данных.
Во-первых, вы не должны проверять пароль напрямую! В по крайней мере, вы должны сначала хэшировать пароль с помощью хэша пароля, такого как 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/2256, что является меньшей вероятностью, чем вам когда-либо приходилось беспокоиться. Вы можете безопасно использовать равенство с переменным временем для HMAC, потому что если Икс
является нет равно у
, то количество времени даже в наивный подпрограмма равенства строк байтов (при условии, что она не выйдет из строя на первом нулевом байте или что-то в этом роде!) будет независима от значений Икс
и у
: есть вероятность 255/256, что он остановится после одной итерации, вероятность 65535/65536 после двух итераций, и т.д.
Конечно, это действительно помогает, только если вы можете реализовать HMAC-SHA256 за постоянное время! К счастью, SHA-256 спроектирован так, чтобы его можно было легко реализовать как логическую схему с постоянным временем, поэтому реализации на C иметь тенденцию быть достаточно устойчивым к сторонним каналам — но, скажем, Python доставит вам неприятности из-за небольшого целочисленного кеша, если не из-за чего-то еще.
* К сожалению, терминология немного запутана. Здесь постоянное время Значит это количество времени не зависит от входных данных, и это не то же самое, что асимптотический понятие «постоянного времени» в компьютерных науках, часто обозначаемое как O(1), что просто означает количество времени может варьироваться в зависимости от входных данных, но ограничено константой. Мне жаль. Не я придумал терминологию. Я мог бы выбрать «фиксированное время». против. «переменное время», но уже слишком поздно, «постоянное время» прочно вошло в литературу.