Почему реализация актуальна для атак по времени?

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

Уточнение. Контекст — это криптографическая подпись несекретных сообщений.

В первоначальном ответе @poncho отмечается, что злоумышленники не всегда могут позволить себе роскошь определять реализацию «пользователя».

На самом деле меня интересует этот вопрос именно в той самой реальной ситуации, когда злоумышленником является пользователь, и имеет возможность выбрать свою реализацию - в криптографическом подписывании несекретных сообщений. Моя цитата ниже касается NaCl, который включает в себя реализацию ed25519. В случаях использования, над которыми я работаю, вы можете предположить, что «злоумышленник»/пользователь имеет открытое текстовое сообщение, подпись и открытый ключ. Все три необходимы для того, чтобы подпись была даже полезной. Единственное, чего им не хватает, так это закрытого ключа.

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

Например.

• Если алгоритм не может математически определить достоверность набора входных данных до последнего шага, то он по своей природе невосприимчив к атакам по времени. Насколько я понимаю, все алгоритмы SHA, одобренные NIST на момент ФИПС-180-4 находятся в этой группе.
• Если алгоритм может математически идентифицировать неверный ввод в каждом добавочном байте/слове/блоке некоторого обрабатываемого потока, он чрезвычайно чувствителен к атакам по времени.
• В худшем случае минимальное количество операций, необходимых для определения успеха или неудачи, зависит от каждого инкрементного бита в секретном ключе.

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

Точно так же, если алгоритм по своей природе невосприимчив к атакам по времени (например, он не может определить достоверность или недействительность до последнего шага), то по определению невозможно создать реализацию, восприимчивую к атакам по времени, намеренно или случайно.

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

Я что-то упустил здесь?

Ссылка: Даниэль Бернстайн / NaCl

раздел функций документов для оригинала Даниэля Бернстайна библиотека NaCl, которая является эталонной реализацией ed25519 Алгоритм подписи, который он и соавторы изобрели, делает многочисленные заявления о превосходстве их выполнение что делает его устойчивым к временным атакам (выделено мной):

Нет веток, зависящих от данных

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

Нет зависимых от данных индексов массива

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

Это должен быть (длинный) комментарий, но у меня нет места. Это предназначено для объяснения того, почему идея позволить злоумышленнику выбрать базовую реализацию слишком сильна — она «тривиально» ломает любой примитив.

Для любого криптографического примитива, если злоумышленник хочет извлечь ключ $k\in \{0,1\}^n$ для некоторых $n$, и может:

1. Выбирайте произвольные сообщения (как минимум сообщения, содержащиеся в $\{0,\dots,n-1\}$) в любой рассматриваемый примитив,

2. Произвольно изменить выполнение алгоритма (но не поведение ввода-вывода математической функции, реализуемой алгоритмом)

3. Имеет доступ к любому качественному методу измерения времени вообще

довольно просто изменить реализацию алгоритма, чтобы полностью слить секретный ключ в $n$ запросы. Если $\mathcal{O}(к, м)$ является "старым" примитивом, определите "новый" примитив через:

О'(к, м)
    если m в {0,...,n-1} и k[m] == 1:
        подождите (Т)
    вернуть О (к, м)

Здесь T — некоторая неуказанная константа, которая «достаточно велика», чтобы злоумышленник мог надежно измерить разницу между алгоритмом, принимающим $\ll Т$ время или $\ок Т$ время выполнять. $\mathcal{O}'$ явно имеет точно такое же поведение ввода-вывода, что и $\mathcal{O}$.

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

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

Хотя «восприимчивость к атакам по времени» четко не определена, существуют примитивы, которые сложнее реализовать с постоянным временем. Обычно это означает одно из двух:

1. Накладные расходы при переходе от непостоянного времени к постоянному времени велики.
2. Легко сделать ошибку при переходе от непостоянного времени к постоянному времени.

Однако это не формальные свойства проблем, а эмпирические наблюдения практиков. Первую проблему можно было бы формализовать (в частности, в большом промежутке между схемой минимального размера, вычисляющей что-то, и ТМ минимального размера в модели ОЗУ, вычисляющей что-то), но я обычно не вижу, чтобы люди пытались это сделать. (не похоже, что это будет интересно разработчикам).

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

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

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

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

Если алгоритм может математически идентифицировать неверный ввод в каждом добавочном байте/слове/блоке некоторого обрабатываемого потока, он чрезвычайно чувствителен к атакам по времени.

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

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

Если злоумышленник атакует систему пользователя (который имеет доступ к секретному значению), он не может попросить пользователя перейти на более удобную (для злоумышленника) реализацию; он должен использовать то, что есть у пользователя.

если алгоритм по своей природе невосприимчив к атакам по времени (например, он не может определить достоверность или недействительность до последнего шага), то по определению невозможно создать реализацию, восприимчивую к атакам по времени, намеренно или случайно.

Нет, это неправда; вы можете легко ввести временные вариации, которые не имеют ничего общего с действительностью или недействительностью.

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

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