The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]



Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Режим отображения отдельной подветви беседы [ Отслеживать ]

Оглавление

Уязвимость в реализациях постквантового алгоритма шифрования Kyber, opennews (??), 09-Янв-24, (0) [смотреть все]

Сообщения [Сортировка по времени | RSS]


30. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Sw00p aka Jerom (?), 10-Янв-24, 04:01 
>вместо обсчета от и до

а где пример трушного кода? ( nooby негодует)

Ответить | Правка | К родителю #13 | Наверх | Cообщить модератору

41. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (39), 10-Янв-24, 11:24 
На правах первой идеи пришедшей в голову...

...
flag = 0;
for (i = 0; i < 100; i++) {
  flag += (input1[i] ^ input2[i]); // input1[i] XOR input2[i] == 0 on match.
}

if (flag != 0) { FAIL! }

Заметьте:
1) в core loop нет условных бранчей, на процах с бранчпредиктором это важно
2) нет зависимости поведения от входных данных, всегда жует 100 байтов хоть что.
3) вердикт выносится после проверки всей чушки "от и до" а математика по всей площади одинаковая.

После этого момента времянки уже не важны - цель срубить итеративный анализ поведения побайтово. В этом смысле идея в том что core loop всегда должен работать одно и то же время. В нем по задумке только (регистровая) математика.

Disclaimer:
1) я не считаю себя профессиональным криптографом.
2) это иллюстративный псевдокод на тему.

Ответить | Правка | Наверх | Cообщить модератору

45. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (45), 10-Янв-24, 12:13 
Как вариант улучшить тело цикла:

...
flag = flag | (input1[i] != input2[i]);
// branchless version of
//   flag = flag || (input1[i] != input2[i]);
// which is no-early-return version of
//   if(input1[i] != input2[i]) return FAIL;
...

Ответить | Правка | Наверх | Cообщить модератору

47. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (39), 10-Янв-24, 13:05 
> flag = flag | (input1[i] != input2[i]);

Эм... != в принципе может быть рассмотрен как условный оператор, кто б его там знает что тот или иной компилер VS проц сделает, и насколько оно константное по времени на всех платформах. Я бы не стал закладываться на то что условный счет гарантировано постоянный по времени. Выглядит как потенциальный conditional.

Вон то - pure math, попытка откосплеить сравнение в стиле как это DJB любит в крипто примерно. Там нет никаких условных вещей в core loop. Только вычисления. Это на более-менее всех процах которые я знаю таки constant time штука. Времянки простых регистровых операций как правило одинаковые для любых данных, а доступ к памяти линейный и не зависит от входных данных, успеха или неуспеха. Core всегда делает одно и то же, а решение с conditional сегментом принимается уже потом - когда по частям угадывать уже не судьба.

Ответить | Правка | Наверх | Cообщить модератору

56. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (45), 10-Янв-24, 16:22 
Но |= всё равно логично использовать вместо +=, чтобы переполнение в ноль было принципиально невозможно.
Ответить | Правка | Наверх | Cообщить модератору

59. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (-), 10-Янв-24, 19:31 
> Но |= всё равно логично использовать вместо +=, чтобы переполнение в ноль
> было принципиально невозможно.

По своему прикольный ход мыслей, спасибо. Впрочем, переполнение можно рубануть и с другого бока. Скажем если максимум 100 символов как в примере - взять flag не менее u16, он никогда не переполнится "by design". Гарантировано математикой. Максимальная сумма 100 байтов - не более 25500. Это точно лезет в u16 или более крупное.

Более того - при написании программ что-то делающих с внешними данными этот момент нехило учитывать везде. Иначе однажды хаксор введет/пришлет не то что вы задумали. И тут окажется что логика отъезжает... и 50/50 что это - вулн, если это дает атакующему что-то полезное.

Ответить | Правка | Наверх | Cообщить модератору

77. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (-), 11-Янв-24, 16:08 
> Более того - при написании программ что-то делающих с внешними данными этот
> момент нехило учитывать везде. Иначе однажды хаксор введет/пришлет не то что
> вы задумали. И тут окажется что логика отъезжает... и 50/50 что
> это - вулн, если это дает атакующему что-то полезное.

p.s. кстати бонусом - кажется ЭТО еще и к rowhammer относительно устойчиво. Чтобы проехало - надо все биты в 0, а вот это для rowhammer'а уже неудобно, в общем фигу атакующим а не доступ :)

Ответить | Правка | Наверх | Cообщить модератору

66. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Sw00p aka Jerom (?), 10-Янв-24, 20:54 
> 2) нет зависимости поведения от входных данных, всегда жует 100 байтов хоть
> что.

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

(0^0), (0^1), (1^0), (1^1) - константны по времени исполнения. Они могут быть константны по времени, а по всяким там энергетическим параметрам они будут такими же? Разве переходной процес из 0 -> 1 и 1 -> 0 константен?

Ответить | Правка | К родителю #41 | Наверх | Cообщить модератору

75. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (-), 11-Янв-24, 15:37 
> а зачем это, зачем делать константой количество циклов,

Чтобы не утекать никакой полезной информации атакующему. А вы что подумали?

> в вашем примере главное не останавливаться при первом же несоответствии,

В том примере главное - не утекать никакой полезной информации атакуюшему через тайминги операций. Чтобы атакующий занимался угадайкой на множестве порядка 256^100.

Этот маневр придумал не я, crypto_memcmp и проч примерно так делают.

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

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

Судя по современному крипто - регистровая математика наиболее безопасная по части постоянных времянок штука в целом. Ну я и откосплеил известный мне маневр в стиле тех граждан.

> Они могут быть константны по времени, а по всяким там энергетическим параметрам
> они будут такими же?

Это уже другой аспект. Energy-aware coding != timing attack. От атакующего который может измерять потребление защититься куда сложнее, но это подразумевает другой уровень интрузива и доступа к системе, против него уже мало что удержится.

А времянки можно иной раз померять даже по сетевым или RF протоколам, ремотно. Или там сидючи на соседней VM с нужной. Поэтому фикс timing attacks намного приоритетнее, подставляет юзерей в довольно большом количестве сценариев на самом деле.

> Разве переходной процес из 0 -> 1 и 1 -> 0 константен?

Нет, однако прецизионный замер потребления проца - это уже довольно интрузивная и нишевая атака.

Я даже знаю кто это делает на коммерческой основе. Но они это делают в тепличных условиях, с специфичным недешевым шмотом, по специфичным поводам. Их полторы фирмы на всю планету с недешевыми расценками, и так вскрывают только очень некоторые вещи в довольно узком диапазоне допущений. А вон тот сервак к ним в лабу утащить на скоростной анализатор? Ну, это как минимум довольно неудобное требование для атакуюшего. Иногда - таки это опция. Но - именно иногда. Там где это реально важно, например, смарткарты, вообще-то этому уделяют внимание на уровне дизайна чипа. И то - с переменным успехом.

Ответить | Правка | Наверх | Cообщить модератору

78. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Sw00p aka Jerom (?), 11-Янв-24, 16:53 
> Чтобы не утекать никакой полезной информации атакующему. А вы что подумали?

1) значение константное, уже утекло знание, что input или равен меньше этой константы
2) это значит, необходимо "расширять" как input1, так и input2, чтобы не было всяких "выходов за границы"
3) параллельно надо "думать", чем же заполнять расширенное "пространство", тоже константными значениями?

> В том примере главное - не утекать никакой полезной информации атакуюшему через
> тайминги операций. Чтобы атакующий занимался угадайкой на множестве порядка 256^100.

if (flag != 0) { FAIL! }

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

https://www.opennet.ru/opennews/art.shtml?num=60334

а вот пример про константность и "добавки":

https://www.opennet.ru/opennews/art.shtml?num=59848


> Этот маневр придумал не я, crypto_memcmp и проч примерно так делают.

ок, ну так давайте разберем все плюсы и минусы данных решений.

> Проца у которого скорость XOR зависела бы от операндов в регистрах я
> еще не встречал.

частичто соглашусь, если он собран из универсального гейта, но где гарантии, что оба "инпута" на элемент приходят "одновременно", опять таки тут всё зависит от гранулярности, разница есть всегда, и кореляция (не только по времени) будет всегда, ибо процесс 0 -> 1 и 1 -> 0 "разный".


> Судя по современному крипто - регистровая математика наиболее безопасная по части постоянных
> времянок штука в целом. Ну я и откосплеил известный мне маневр
> в стиле тех граждан.

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

> Energy-aware coding != timing attack.

принцип один, найти кореляцию между "входом и выходом"

> Нет, однако прецизионный замер потребления проца - это уже довольно интрузивная и
> нишевая атака.

по миганию светодиода восстанавливали

https://www.opennet.ru/opennews/art.shtml?num=59291

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

там вообще беда, в софтверных реализациях можно как-то закрывать вектора атак.


Ответить | Правка | Наверх | Cообщить модератору

79. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (79), 11-Янв-24, 19:56 
> 1) значение константное, уже утекло знание, что input или равен меньше этой константы

Атакующий чаще всего знает лимиты. И даже если это новое знание, круто, знаете что надо угадать из 256^100. Сильно помогло?

> 2) это значит, необходимо "расширять" как input1, так и input2, чтобы не
> было всяких "выходов за границы"

Можно просто зарубать ввод длиннее оговоренного максимума. А если это ключи какие, они могут быть фиксированой длины by design. Иллюстрация не о том.

> 3) параллельно надо "думать", чем же заполнять расширенное "пространство",

Нужность этого зависит от того что это было, к затыканию таймингов не относится.

> if (flag != 0) { FAIL! } такая конструкция порождает новый вид bypass атак,
> когда можно всякими манипуляциями воздействовать на ячейку памяти и изменить
> ее значение, подобно этой:

1) ЭТОТ код относительно устойчив к rowhammer, до кучи. Лучше чем if (flag != 0) {AUTH OK!} у тех позорников, где любой бит сбить и в дамках. А тут удачи подогнать flag в именно ноль, любое иное == FAIL.
2) Это локальная временная "горячая" переменная, скорее всего в регистре. Его rowhammer-ом, как бы это... а в сях так то можно и "register" захинтить.
3) Если кто гасит систему rowhammer, он много чего еще сможет.
4) На допустим MCU вообще DRAM нет :P

> ок, ну так давайте разберем все плюсы и минусы данных решений.

Очевидный трабл - менее эффективно, но за ту оптимизацию - воздается вулном.

> частичто соглашусь, если он собран из универсального гейта,

У ALU логика обычно шириной с регистр и ему похрен что за биты.

> но где гарантии, что оба "инпута" на элемент приходят "одновременно",

Это от структуры системы очень зависит. Даже если cache hit vs cache miss сделает джиттер - это вроде бы не привязано к содержимому input1 или input2, т.е. нового инфо о их содержимом атакующий с этого не получает.

Ключевой вопрос: "что это дает атакуюшему?".

> будет всегда, ибо процесс 0 -> 1 и 1 -> 0 > "разный".

Регистровые операции как правило за 1 такт современными процами молотятся и там пофиг какие биты куда. На электрическом уровне, конечно, разницу бывает видно но это уже иной класс атак.

> в случае с тайминг атаками опасность предоставляют переходы,

Не только. В примере который я привел трабл в том что алго срубается за разное время в зависимости от (не)совпадений (==зависимость от содержимого). Это не столько про переходы сколько про неудачную логическую структуру алго. Он будет уязвим даже на проце где бранчи за постоянное время и не были проблемой. Логично что я для илллюстрации проблемы взял злой пример, уязвимый везде, плюс-минус :).

> тем самым делая тайминг атаки логическими атаками.

Тайминг атаки - это атаки накопления информации о пароле/ключе по сторонним каналам. Переходы и связанные утечки и проблемы - частный случай. Subset.

> принцип один, найти кореляцию между "входом и выходом"

В чем-то да, НО детали и применимость здорово отличаются. Электрические измерения требуют очень плотный физический доступ к атакуемой системе. Надолго. А тайминг атаки можно зачастую эксплуатировать ремотно по сети/RF или с соседней виртуалки. Куда более слабое требование.

> по миганию светодиода восстанавливали

Это тоже требует физический доступ, надолго и атака глючная.

> там вообще беда, в софтверных реализациях можно как-то закрывать вектора атак.

Вон то - одна из ипостасей. Я иллюстрировал ее, а не что-нибудь иное. Разумеется это не гарантирует решения всех проблем человечества и информационной безопасности.

Ответить | Правка | Наверх | Cообщить модератору

80. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (79), 11-Янв-24, 20:22 
> Это от структуры системы очень зависит. Даже если cache hit vs cache miss сделает
> джиттер - это вроде бы не привязано к содержимому input1 или input2, т.е.
> нового инфо о их содержимом атакующий с этого не получает.

Кстати говоря вспомнил что DJB в своих алго любит такое для относительно мелких блоков в криптоалго конопатить более радикально: он копирует input в локальные переменные, работает с ними там, а потом - копирует обратно в output. В случае крипто преобразований вместо вердикта - output еще есть, чуть иной случай но идею показывает.

Ответить | Правка | Наверх | Cообщить модератору

86. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Sw00p aka Jerom (?), 12-Янв-24, 23:34 
> конопатить более радикально

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

Ответить | Правка | Наверх | Cообщить модератору

88. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (-), 14-Янв-24, 15:29 
> конопатить лучше на асм,

Убивает портабельность и читаемость кода -> something to avoid в общем случае.

И я лично использую x86-64, Cortex-M, Cortex-A, MIPS и RISCV(32 и 64). Мне что, 6 версий алго выписывать? Нафиг надо, скажем прямо. А если взять еще AVR какой и чего поэкзотичнее, мм... сколько там кода то на майнтенанс уже? Оно мне надо? Поэтому подбирают конструкции где и на си компилеру сложно сделать что-то не то.

> что там наконопатит компилятор языка Х - "тайна",

Он сделает то же что и человек, только кроссплатформенно. То действо ведет к локальной переменной с всегда одинаковой предысторией "мы ее только что заполнили" и сбивает неопределенность от кеша соответственно.

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

Вот вы этим и занимайтесь, а мне 6-7 а то и больше вариантов кода вместо 1 майнтайнить... ну вы поняли.

Ответить | Правка | Наверх | Cообщить модератору

89. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Sw00p aka Jerom (?), 14-Янв-24, 16:57 
> Оно мне надо?

ну вот, собственно ясно.

Ответить | Правка | Наверх | Cообщить модератору

90. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (-), 14-Янв-24, 23:26 
>> Оно мне надо?
> ну вот, собственно ясно.

Ну дык. Мне асмовый выхлоп прочекать там где оно реально важно, 1 раз на версию компилера - проще чем пачку ассемблерных простынок колупать. А основной повод юзать си - портабельность кода, внезапно.

И возможность отладить код на мощном компе под крутой инструментацией типа asan/ubsan и перенести 1 в 1 на мк знаюя что код переживает fuzzing рандомным входом и проч. На МК с этим значительно душнее например. ASAN туда вообще не лезет, а UBSAN только на минималочках. Ну а кус ассемблерного кода - инвалидирует все результаты проверок.

Так что если вы считаете что вон то отличный курс действий - вот и показывайте личным примером HOW TO для начала. Если вы выложите пару годных криптолиб под свободной лицензией, взяв вон то на себя - окей, я подумаю о использовании либы. А если вопрос в том чтобы я выписывал с дюжи ну разных сегментов кода делающих ОДНО И ТО ЖЕ, при том 95% вероятности что бинарь в итоге этой камасутры будет чуть ли не бит в бит - ненене, Девид Блейн.

Ответить | Правка | Наверх | Cообщить модератору

91. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Sw00p aka Jerom (?), 14-Янв-24, 23:41 
> Ну дык.

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

что за "нечитабельность"? можете пояснить зачем это изменение приняли?

Ответить | Правка | К родителю #90 | Наверх | Cообщить модератору

92. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Аноним (-), 15-Янв-24, 01:45 
> что за "нечитабельность"? можете пояснить зачем это изменение приняли?

Ответил в другом топике где вы спросили то же самое.

Struct в си - они как бы почти то что надо, но специфицированы комитетом придурков из рук вон плохо, особенно в части align и проч. Это тот редкий случай когда C может перестать быть тонким shim над железом и отумничает. Без стандартных средств контроля за этим, только нестандартными extensions.

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

Ответить | Правка | К родителю #91 | Наверх | Cообщить модератору

93. "Уязвимость в реализациях постквантового алгоритма шифрования..."  +/
Сообщение от Sw00p aka Jerom (?), 15-Янв-24, 02:46 
> Но не ассемблерщикам про это вещать - там такого вообще нет. Поэтому код
> на асме это эталоннейшее спагетти.

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

Ответить | Правка | К родителю #92 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру