ЗАЩИТА ОТ ПАССИВНОГО СНИФФИНГА Российский патент 2016 года по МПК H04L9/28 

Настоящее изобретение относится к защите криптографических алгоритмов от пассивного сниффинга (пассивного прослушивания сети).

Криптографический алгоритм представляет собой алгоритм, который предназначен для защиты информации, например, за счет обеспечения ее конфиденциальности, ее аутентичности или ее целостности, математическими методами. Криптографический алгоритм часто базируется на одном или более ключах, которые могут быть секретными, частными или общественными. Некоторые криптографические алгоритмы не используют ключ, который является подлинным для определенных хэш-функций (таких как SHA-1, MD5, SHA-256, RIPEMD-160 и т.д.). Криптографический алгоритм включает в себя алгоритмы шифрования (которые делают информацию не доступной для понимания) и алгоритмы дешифрования (которые восстанавливают первоначальную информацию из зашифрованной информации), алгоритмы для электронной подписи, верификации подписи, аутентификации и верификация аутентификации и т.д. Некоторые из криптографических алгоритмов, которые основаны на ключах, называются симметричными (например, алгоритмы DES, 3DES, AES, RC4, НМАС и т.д.). Некоторые симметричные алгоритмы являются специализированными (например, алгоритм НМАС используется для подписи/верификации подписи, но не для шифрования/дешифрования). Симметричные алгоритмы получают свое имя исходя из того, что они используют одинаковый ключ (который обычно называется секретным ключом) для шифрования и дешифрования или для подписи или подтверждения подписи и т.д. Поэтому симметричные криптографические алгоритмы требуют того, чтобы обе стороны, использующие их, обеспечивали безопасность своей связи, пользуясь совместно используемыми ключами. Алгоритм AES (усовершенствованный стандарт шифрования) является важным потому, что он представляет собой алгоритм, который был выбран в 2000-м году NIST в качестве стандарта алгоритма симметричного шифрования для правительства Соединенных Штатов Америки. Другие криптографические алгоритмы называются асимметричными (например, DSA, RSA, эллиптическая кривая и другие алгоритмы), так как для поддержания связи стороны используют различные ключи. Каждая сторона имеет личный ключ и связанный с ним общественный ключ. Например, одна сторона может использовать один из своих личных ключей для подписи части информации, а другая сторона использует соответствующий общественный ключ для верификации подписи, или одна сторона может использовать общественный ключ, принадлежащий другой стороне, для шифрования части информации, а другая сторона может использовать свой соответствующий личный ключ для дешифрования части информации.

Криптографические алгоритмы часто описываются в очень точной манере в спецификациях, доступных каждому, так как защита криптографического алгоритма, как правило, не связана с какой-либо секретностью в том, как он работает (алгоритмы, которые считаются защищенным лишь в силу своей секретности, в конечном счете, часто взламываются методом обратной инженерии). Спецификация определяет то, что алгоритм должен производить такой же выход, когда он снабжается некоторой информацией, как и вход. Это обеспечивает взаимную совместимость криптографического алгоритма, которая означает, что различные реализации должны функционировать в обоих направлениях. Например, вполне можно ожидать, что информация, зашифрованная с помощью любой реализации алгоритма шифрования должна быть расшифрована с помощью любой реализации соответствующего алгоритма дешифрования. Однако это не означает, что существует только одна возможная реализация каждого криптографического алгоритма. Напротив, существует множество возможных реализаций каждого криптографического алгоритма, и существует множество различных способов выполнить одно и то же вычисление. Например, чтобы вычислить Х²+2Х+1, можно сначала вычислить Х∗Х, затем 2∗Х, затем сложить эти два члена и затем добавить 1, или вычислить Х+1, полученный результат умножить на Х и затем прибавить 1, или даже вычислить Х+1 и полученный результат возвести в квадрат.

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

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

Пассивный сниффинг может состоять, например, из анализа электромагнитного излучения, излучаемого устройством во время выполнения программы (например, как часть атаки TEMPEST, которая обычно направлена на захват излучений от ЭЛТ-дисплеев, но может быть более обобщенной). Действительно, электромагнитное излучение от электронного устройства, например, процессора, зависит от того, что процессор выполняет в текущий момент времени, например, процессор в текущий момент времени выполняет инструкцию, или процессор выполняет в текущий момент времени обработку данных. Кроме того, можно анализировать другие типы информации, такие как мгновенную потребляемую мощность электронного устройства, и использовать это для того, чтобы различить, какие задачи выполняются на основании электрической мощности, необходимой для этих задач. Можно также измерить испускаемые вибрации (например, некоторые компоненты восприимчивы к вибрации различным образом в зависимости от того, что выполняется), а также температуры и т.д.

Пассивный сниффинг может также включать в себя анализ времени, которое требуется для выполнения некоторых операций. Пассивный сниффинг позволяет сделать выводы из этого анализа, когда эти операции не защищены от атак, которые называются "таймерными атаками". Например, операция верификации пароля, незащищенная от таймерных атак, может сравнивать байты представленного пароля с байтами предполагаемого пароля, байт за байтом и выдает ошибку при несовпадении байта. На основании времени, требуемого для функции верификации, чтобы отреагировать на то, что пароль неправильный, атакующая сторона может сделать вывод, что первые N байтов являются правильными, и повторить попытку, представив вероятный пароль только с модифицированным N+1 до тех пор, пока время отклика слегка не замедлится, что будет указывать на то, что N+1 является теперь правильным, и в этот момент он будет перемещаться на N+2 байт и так далее до тех пор, пока не будет полностью получен пароль. В данном случае, для того чтобы угадать пароль, имеющий длину К (в байтах), даже тогда, когда он представляет собой "сильный пароль" (атаки на словарь невозможны), средняя сложность уменьшается от ½∗(2⁸)^K до более простой средней сложности K∗2⁷. Во избежание таймерных атак можно обеспечить то, чтобы все чувствительные операции имели постоянное время выполнения, или чтобы, несмотря на то, что длительность может быть переменной, она не предоставляло бы никакой информации относительно того, что происходит во время операции. Возможны также дополнительные контрмеры: в предыдущем примере пароль можно заблокировать после определенного числа неудачных попыток, что является обычным подходом при использовании PIN-кодов. Однако, в общем, эти дополнительные являются только дополнительной защитой от таймерных атак, но не заменой. Например, предполагая, что банковская карточка блокирует PIN-код после пяти неудачных попыток, но реализует незащищенную верификацию, как описано выше, кто-нибудь (например, подросток, работник и т.д.) может присвоить банковскую карточку (например, своей матери, своего руководителя и т.д.) каждый раз, когда легитимный владелец выполнил транзакцию, например, оплату за бизнес-ланч в ресторане (которая сбрасывает счетчик неудачных попыток), и затем каждый раз может выполнить четыре попытки. Для четырехзначного PIN-кода в среднем можно выполнить двадцать попыток (означает, что карту можно будет взять 5 раз) и максимум сорок попыток, чтобы определить PIN-код, что довольно легко выполнить.

Основной сниффинг может состоять из простой идентификации специфической характеристики из специфического измерения по отношению к целевому электронному устройству. Это имеет место, например, в случае так называемой SPA (простой анализ питания атак). Например, при модульном возведении в степень, которое выполняется в "примитивной" реализации RSA-алгоритма, потребление электрической энергии сильно отличается в случае, когда бит экспоненты равен 1 (высокое потребление), и когда бит равен 0 (низкое потребление). Фактически в общих реализациях бит 1 включает в себя как операцию возведения в квадрат, так и операцию умножения (которые называются "возведением в квадрат и умножение"), тогда как бит 0 включает в себя только операцию возведение в квадрат. Наблюдая за изменением потребления электроэнергии потребления модульного возведения в степень, можно, таким образом, идентифицировать последовательности единиц и нулей в экспоненте, которые соответствуют флуктуациям при потреблении электроэнергии. RSA-экспонента в случае, когда она относится к частной экспоненте, представляет собой чрезвычайно конфиденциальные данные, которые представляют собой компонент частного RSA-ключа, который, в общем, не предполагается, что он будет известен кому-нибудь вне электронного устройства. Получение частного ключа подписи человека позволяет, таким образом, подписывать от его имени, и получение его частного ключа расшифровывания, позволяет расшифровывать его сообщения.

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

Для защиты от таких атак можно предусмотреть дополнительные меры по обеспечению безопасности непосредственно для электронного устройства. Например, на подаваемое питание можно наложить шум для того, чтобы затруднить анализ питания, потребление мощности можно сгладить (например, с помощью конденсатора), электромагнитное излучение можно ограничить соответствующим экранированием и т.д. Можно также использовать специальный внутренний генератор тактовых импульсов, работающий на случайно выбранной переменной частоте, которая требует такие измерения трудными для использования (так как операции криптографических алгоритмов затем выполняются на скорости, которая сохраняет изменения и которая неизвестна атакующей стороне заранее). Существуют также другие методы, например, состоящие из управления физическим доступом и/или логическим доступом к электронному устройству. Например, смарт-карты, реализующие криптографические алгоритмы на основе частного ключа, обычно защищают важные операции с помощью PIN-кода. Человек, который на время крадет смарт-карту, надеясь извлечь частный ключ и затем вернуть карту владельцу так, чтобы он не узнал об этом, не сможет выполнить соответствующий алгоритм без предоставления правильного PIN-кода (который информированный пользователь знает наизусть и не раскрывает никому), и, таким образом, не сможет выполнить атаку.

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

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

Другая мера защиты (которую можно использовать в добавление к предыдущей) состоит из маскирования чувствительных данных. Чувствительные данные могут представлять собой, например, криптографические ключи и/или входное сообщение, которое необходимо шифровать, например, с помощью криптографического алгоритма, и/или некоторые промежуточные данные, которыми манипулируют во время исполнения криптографического алгоритма. В некоторых случаях атакующая сторона может узнать или выбрать входное сообщение для обработки с помощью криптографического алгоритма, и может затем выполнить гораздо более точное предсказание, которое относится к текущему вычислению. Так как входное сообщение и/или промежуточные данные маскируются способом, который, в принципе, является непредсказуемым для атакующей стороны, то он удаляет некоторую часть информации из атакующей стороны и может, таким образом, значительно усложнить атаку. Более того, при условии, что маскирование является разным для каждого использования криптографического алгоритма, статистический анализ можно усложнить. Например, было предложено несколько способов, которые обеспечивают защиту путем маскирования AES-алгоритма, для защиты от атак по сторонним каналам. Одним традиционным решением является аддитивное маскирование, где манипулированные данные Х заменяются на маскированные данные x+m (+ обозначает в данном случае исключающее ИЛИ). Он легко проходит через линейные операции алгоритма. (Нелинейные) таблицы подстановки S[] затем заменяются на маскированные таблицы, выработанные в процессе обработки после получения новой маски (или полностью предварительно сохраняется в памяти, если объем памяти позволяет это). Таким образом, маскированная нелинейная операция, соответствующая маскированной таблице подстановки S'[], которая применяется к данным х, маскированным с помощью случайной маски m1, можно записать в следующем виде:

у'=S'[x+m₁]=у+m₂=S[x]+m₂,

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

Тем не менее, атаки будут иногда успешно преодолевать трудности, введенные маскированием уровня техники. В частности, некоторые типы атак, такие как атаки НО-DPA (дифференциальный анализ питания высокого порядка), особенно трудно избежать при определенных обстоятельствах. Это объяснено, в частности, в статье Марка Джоя, Паскаля Пайлиеро и Берри Шоенмакерса "Относительно дифференциального анализа питания высокого порядка", опубликованной в Криптографические аппаратные средства и встроенные системы, Чес 2005, конспект лекций по компьютерной науке 3659 (2005), с.293-308. Спрингер Верлаг ("On Second-Order Differential Power Analysis" by Marc Joye, Pascal Paillier and Berry Schoenmakers, published in Cryptographic Hardware and Embedded Systems, CHES 2005, Lecture Notes in Computer Science 3659 (2005), 293-308, Springer Verlag). Поэтому, когда атакующая сторона успешно коррелирует потребление мощности (или другую информацию этого типа) с вычислениями много раз, он иногда может преодолеть маскирование.

Настоящее изобретение улучшает данную ситуацию.

Настоящее изобретение относится к способу защиты при исполнении криптографического алгоритма от пассивного сниффинга, причем упомянутый способ выполняет маскирование данных, обрабатываемых с помощью криптографического алгоритма. Маскирование упомянутых данных включает в себя этап преобразования типа type х'=x·L+c, где х - данные, которые будут маскировать (такие как входные данные в криптографическом алгоритме, промежуточные чувствительные данные или ключ), х' - соответствующие маскированные данные, с - кодовое слово, включенное в линейный код С, и L - матрица, состоящая из линейно независимых векторов, не включенных в линейный код С. Этот способ может состоять из модифицированной реализации алгоритма, например модифицированной в функциональный эквивалентный алгоритм (означая, что он производит тот самый выход для того же самого входа), который включает в себя, по меньшей мере, один этап маскирования посредством преобразования (такого как линейное кодирование), и, по меньшей мере, один соответствующий этап демаскирования путем декодирования. Реализация может быть представлена в форме программной реализации. Она может также представлять собой реализацию в электронной форме, например, микрокодированную реализацию, реализацию FPGA, реализацию ASIC или реализацию за счет расширения узкоспециализированной схемы. Программная реализация обычно представляет собой самую легкую форму для выполнения, но часто менее эффективную с точки зрения скорости выполнения.

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

Преимущество способа также состоит в том, что преобразование типа x·L+c позволяет обнаруживать некоторые ошибки, главным образом в конце алгоритма (но он позволяет также выполнить обнаружение ошибок во время алгоритма). Действительно, если с известно, после приема результата у, то можно верифицировать, что у+с действительно имеет форму x·L для определенного х.

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

Согласно одному варианту осуществления, матрица L выбирается случайным образом один раз только для всех исполнений криптографического алгоритма. Это является преимущественным, так как выработка этой матрицы является слишком медленной, что может представлять собой недостаток из-за того, что это влияет на скорость вычисления, если это повторяется слишком часто. Кодовое слово с добавляет уже некоторую изменчивость, которая делает атаку более сложной. Однако может быть целесообразным изменение матрицы L время от времени (для повышения безопасности). Например, можно вырабатывать новую матрицу L каждый раз, когда на устройство, использующее способ защиты, подается питание, в случае устройств, которые обычно остаются включенными в течение значительного периода времени. В случае типичной смарт-карты, это не будет очень уместно, так как смарт-карты редко снабжаются батарейкой или другим источником электрической энергии, и поэтому типично выключаются в конце каждой транзакции (транзакция обычно заканчивается путем удаления карты из терминала). Можно было бы обеспечить смарт-карты счетчиком, который увеличивал свое значение каждый раз при подаче на нее питания, и вырабатывать новую матрицу каждый раз, когда счетчик достигает определенного порога (например, значения 20). Можно также иметь новую матрицу, которая вырабатывается в случае, когда карта используется в определенных контекстах. Например, когда смарт-карта полностью оказывается внутри АТМ-машины, и транзакция занимает продолжительный период времени даже в случае только механических ограничений по подсчету банкнот, это время можно использовать для выработки новой матрицы. Либо когда смарт-карта, которая использует бесконтактную технологию или служит в качестве билета на общественный транспорт (метро, автобус и т.д.), пополняется, например, один раз в месяц. Напротив, во время быстрой транзакции (например, когда бесконтактная банковская карта используется для покупки батона хлеба в булочной или для оплаты за проезд по автомагистрали, или когда бесконтактная смарт-карта используется для прохождения через турникет метро), несомненно, было бы неуместным вырабатывать новую матрицу, если не будут разработаны гораздо более быстрые протоколы связи, по сравнению с теми, которые существуют в настоящее время. Различение между финансовыми транзакциями может быть основано, например, на их сумме (например, можно решить, что новая матрица не вырабатывается для транзакции менее чем за 15 евро). Можно также использование специальные области для распознавания типов транзакции, хотя в зависимости от контекста, они могут включать в себя неприемлемые архитектурные изменения (например, в банковских компьютерных сетях, которые обычно высоко стандартизированы).

Согласно одному варианту осуществления маскирование (и, следовательно, преобразование) выполняется перед применением криптографического алгоритма (то есть криптографический алгоритм выполняется перед его защитой с помощью способа настоящего изобретения), и операция демаскирования выполняется после применения криптографического алгоритма. Это является преимуществом, так как криптографический алгоритм затем работает в маскированном режиме из конца в конец. Однако можно также обратить внимание только на некоторые части криптографического алгоритма (например, на маскирование только некоторых очень чувствительных подпрограмм). Можно маскировать только линейные операции, которые перезаписываются соответствующим образом (типично f'(x·L)=f(x)·L), что позволяет минимизировать изменения в криптографическом алгоритме, хотя защита затем иногда несколько ухудшается. Демаскирование можно выполнить путем декодирования, например, применяя матрицу контроля по четности для линейного кода.

Согласно одному варианту осуществления криптографический алгоритм представляет собой алгоритм, который реализует нелинейную операцию (такую как таблицу подстановок S-Box алгоритма стандарта шифрования данных (DES), или криптографического алгоритма Blowfish, или нелинейную операцию алгоритма усовершенствованного стандарта шифрования (AES)). Нелинейная операция S заменяется на нелинейную операцию S' таким образом, что S'(x.L+c)=S(x).L+c', где S' - кодовое слово линейного кода С. Действительно, почти все криптографические алгоритмы используют нелинейные операции, так как линейный алгоритм имеет свойства, которые обычно делают его очень предсказуемым, что типично противоречит тому, что ожидают от криптографического алгоритма. Например, если алгоритм шифрования является линейным, то можно узнать шифрование суммы двух сообщений, если известно шифрование каждого сообщения, что в принципе не допустимо. Таким образом, этот вариант осуществления является полезным для обеспечения сквозной (из конца в конец) защиты в нелинейном криптографическом алгоритме, так как он решает проблему демаскирования в случае, когда присутствуют нелинейные операции, которые очень часто встречаются в этом случае.

Согласно одному варианту осуществления криптографический алгоритм включает в себя несколько раундов, причем каждый раунд включает в себя одну и ту же нелинейную операцию S, и линейная операция S заменяется на ту же самую нелинейную операцию S' во время каждого раунда. Это является преимуществом, так как замена нелинейной операции на другую операцию, которая отличается для каждого раунда, является дорогостоящей с точки зрения производительности, при этом выполнение одной и той же замены можно поддерживать приемлемую скорость особенно для устройств, которые имеют ограниченные ресурсы, такие как смарт-карты базового уровня, имеющие очень медленный процессор и небольшой объем памяти.

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

Настоящее изобретение также относится к электронному устройству, включающему в себя блок для исполнения криптографического алгоритма (блок исполнения криптографического алгоритма), а также связанный с ним модуль маскирования. Модуль маскирования выполнен с возможностью применения преобразования типа х'=x·L+c, где х - данные, которые необходимо маскировать, х' - соответствующие маскированные данные, с - кодовое слово, включенное в линейный код С, и L - матрица, состоящая из линейно независимых векторов, не включенных в линейный код С.

Варианты осуществления, описанные выше по отношению к способу, можно перенести на устройство; в частности, согласно одному варианту осуществления модуль маскирования выполнен с возможностью выбора кодового слова со случайным образом во время каждого исполнения криптографического алгоритма. Согласно одному варианту осуществления модуль маскирования выбирает матрицу L случайным образом один раз только для всех исполнений криптографического алгоритма. Согласно одному варианту осуществления модуль маскирования выполнен с возможностью выполнения маскирования перед применением криптографического алгоритма и выполнения операции демаскирования после применения криптографического алгоритма. Согласно одному варианту осуществления криптографический алгоритм исполнительного блока представляет собой алгоритм, реализующий нелинейную операцию S, и модуль маскирования выполнен с возможностью замены нелинейной операции S на нелинейную операцию S' таким образом, чтобы S'(x·L+c)=S(x)·L+c', где с' - кодовое слово нелинейного кода С. Согласно одному варианту осуществления криптографический алгоритм исполнительного блока включает в себя несколько раундов, причем каждый раунд содержит одну и ту же нелинейную операцию S, и модуль маскирования выполнен с возможностью замены нелинейной операции S на ту же самую нелинейную операцию S' во время каждого раунда. Согласно одному возможному варианту осуществления двух предыдущих вариантов осуществления с'=с.

Другие аспекты, особенности и преимущества настоящего изобретения станут очевидными после прочтения описания одного из его вариантов осуществления.

Настоящее изобретение будет также лучше понятно со ссылкой на чертежи, на которых:

фигура 1 иллюстрирует способ согласно настоящему изобретению,

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

На фигуре 1 схематично показаны основные этапы способа согласно настоящему изобретению. В этом способе процесс начинается с маскирования данных CL_TXT (для "открытого текста"), например элемент данных, который необходимо зашифровать, во время этапа MSK, и затем выполняют криптографический алгоритм ALG, который будет защищать (например, алгоритм шифрования, такой как AES), затем результат демаскируется в конце (на этапе U_MSK, для "демаскирования") для того, чтобы восстановить значение CR_TXT (из "шифртекста" или шифрованного текста), который бы нормально получился с помощью алгоритма ALG без маскирования. Другими словами, если два этапа маскирования MSK с помощью линейного кода и демаскирования U_MSK (с помощью соответствующего декодирования) удалены таким образом, чтобы остался только криптографический алгоритм ALG, при этом из входа CL_TXT получается одинаковый выход CR_TXT, что означает, что алгоритм был выполнен более защищенным посредством его маскирования без влияния на его межоперабельность. Операции маскирования MSK можно объединить с операциями демаскирования U_MSK в пределах криптографического алгоритма, таким образом получая конкретную реализацию криптографического алгоритма ALG, который является функционально таким же, как и алгоритмы уровня техники, но который обеспечивает гораздо большую защиту от атак пассивного сниффинга, в частности, от самых сложных атак, таких как атаки HODPA. Представление, показанное на фигуре 1, является упрощенным в том смысле, что в наиболее частых случаях, что оно не представляет собой точно известный криптографический алгоритма ALG, который выполняется на этапе ALG, но представляет собой модифицированную версию этого алгоритма, позволяя обеспечить маскирование/демаскирование при наличии нелинейных операций.

На фигуре 2 показана смарт-карта SC согласно настоящему изобретению. Смарт-карта является возможным примером устройства, для которого настоящее изобретение является особенно преимущественным, принимая во внимание его многочисленные приложения в области криптографии (SIM-карты, аутентифицирующие пользователя мобильного телефона для оператора, банковские карты, аутентифицирующие держателя карты во время финансовой транзакции, карты медицинского страхования и т.д.). Однако настоящее изобретение применимо к любым портативным устройствам, таким как электронный паспорт, электронная виза, электронное водительское удостоверение, USB-ключ безопасности (ММС-карта безопасности), токен безопасности и т.д. Настоящее изобретение можно также применить в персональном компьютере, сервере, SSL-ускорителе и т.д. Большая часть персональных компьютеров не является защищенной в отличие от защищенных устройств, таких как смарт-карта. Это делает компьютеры уязвимыми для атак, которые гораздо легче реализовать чем атаки, от которых защищает настоящее изобретение, такие как атаки, которые реализованы сугубо программными средствами. Эти программные атаки (посредством вируса, вредоносной программы типа "Троянский конь" и т.д.) могут часто выполняться удаленно, не требуя физического доступа. Это может показаться абсурдной попытка обеспечить защиту от сложных и ограничивающих атак, таких как атаки пассивного сниффинга, когда атакующая сторона, расположенная на другом континенте может взять на себя управление компьютером дистанционным способом и отыскать важную информацию таким способом, который гораздо легче и менее опасен для нее (без вмешательства, без кражи устройства и т.д.). Однако некоторые персональные компьютеры (например, компьютеры, используемые в военных средах) имеют высокую защиту от чисто программных атак, и в этом контексте преимущественной является защита их также от атак пассивного сниффинга.

На фигуре 2 также показана поддельная смарт-карта FSC, которая представляет собой просто разъем в форме смарт-карты и имеет электрические контакты в стандартных положениях для того, чтобы эти контакты были подсоединены к соответствующим контактам реальной смарт-карты SC через оборудование HODPA, которое позволяет обеспечить атаку типа HODPA. Таким образом, оборудование HODPA имеет последовательное соединение между реальной смарт-картой SC, на которую нацелена атакующая сторона, и поддельной смарт-картой, устанавливающей физический интерфейс между терминалом, который предполагает принять реальную смарт-карту FSC, и этой реальной смарт-картой SC. Цель поддельной смарт-карты FSC в этом примере заключается в том, чтобы следить за потреблением тока смарт-карты SC без модификации терминала, использующего карту (и, в частности, устройство считывания смарт-карты). В настоящем изобретении смарт-карта SC наиболее устойчива к атакам этого типа, и она очень затруднительна для оборудования HODPA для извлечения целевой информации из смарт-карты SC.

Так как изобретение основано на использовании линейного кода, стоит напомнить, что линейный код представляет собой особый тип кода для коррекции ошибок. Линейный код С представляет собой векторное подпространство n-мерного векторного пространства $$F_q^n$$ , где F_q - конечное поле с q элементами. Это может быть поле F2(q=2), в случае которого линейный код представляет собой двоичный код. Допустим, n-k - размерность вектора подпространства, соответствующего линейному коду С. Линейный код С определяется с помощью порождающей матрицы G. Элемент с (и в более общем смысле любой элемент кода С) можно разбить на линейную комбинацию вида с=m₁v₁+m₂v₂+…+m_n-kv_n-k векторного базиса (v₁, v₂,…, v_n-k), или с=mG, где m=(m₁, m₂,….m_n-k), причем G представляет собой порождающую матрицу (размера (n-k)∗n).

Проверочная матрица также ограничена размером n∗k так, что для каждого элемента с линейного кода С с·Н=0 и взаимно, если с·Н=0, то с - элемент линейного кода С.

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

Согласно одному варианту осуществления настоящего изобретения данные, защищенные с помощью линейного кода, используются только внутренним образом в пределах криптографического алгоритма. Это означает, что отсутствует концепция легитимного отправителя или легитимного получателя данных, защищенных путем кодирования канала для подслушивания, а также концепция частоты появления ошибок. Линейный код используется в процессе вычислений криптографического алгоритма, что, в общем, необязательно для поддержания связи с другими объектами во время исполнения действующего алгоритма. Когда устройство представляет собой многозадачное устройство, это не исключает, что устройство поддерживает связь с внешним миром при исполнении криптографического алгоритма. Это также не исключает, что устройство реализует протокол безопасности (такой как протокол обмена ключами, например, Диффи-Хеллмана (Diffie-Hellman) или протокол, основанный на симметричной криптографии), в котором последовательные криптографические операции выполняются двумя сторонами, которые постепенно обмениваются результатами протокола безопасности для того, чтобы получить, например, общий ключ в конце протокола безопасности. В этом контексте изобретение можно использовать для защиты каждой криптографической операции, выполняемой в соответствии с протоколом. Криптографический алгоритм может иногда ошибочно называться протоколом безопасности, таким как протокол, описанный выше. Однако в смысле настоящего изобретения, он не является криптографическим алгоритмом, а представляет собой протокол, который использует последовательность криптографических алгоритмов. В модифицированном криптографическом алгоритме, в общем, не будет произвольной передачи данных, защищенных канальным кодированием через любой канал связи. В принципе, это означает, что отсутствует потеря данных, не считая, если, например, не присутствует атака, основанная на ошибке (такая как атака DFA), или если криптографический алгоритм выполняется на поврежденном электронном устройстве. При исключении этих особых ситуаций, канал можно рассматривать совершенным виртуальным каналом (так как отсутствует фактическая передача маскированных данных). Однако существует канал передачи для атакующей стороны, пытающейся произвести атаку пассивного сниффинга, который является используемым сторонним каналом (например, электромагнитные передачи или потребление мощности, за которыми следят с помощью атаки HODPA). Этот канал не является совершенным, и его можно, в общем, даже рассматривать как относительно зашумленным и нарушенным многочисленными контрмерами, которые обычно присутствуют в электронных устройствах.

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

- линейный код С устанавливается при наличии порождающей матрицы G с размером (n-k)∗n и проверочной матрицы Н n∗k таким образом, чтобы все ее подматрицы, которые имеют размер (n-mu)∗k (то есть подматрица, имеющая (n-mu) строк и k столбцов), имели ранг k,

- устанавливают L₁, L₂,… L_k линейно независимых k векторов, которые имеют n битов и которые не включены в линейный код С,

- выбирают с=mG, кодовое слово которого выбирается случайным образом,

- чувствительные данные х, представленные в виде вектора (x₁, x₂,…x_k), затем кодируют в виде х'=x·L+c, при x·L=x₁·L₁+…+x_k.L_k. В случае линейного кода С, который представляет собой двоичный код (область F2), операция "+" может представлять собой обычно область исключающего ИЛИ.

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

Чувствительные данные х могут представлять собой, например, открытый текст CL_TXT, который необходимо шифровать с использованием криптографического алгоритма ALG для дальнейшей защиты. Однако они могут также представлять собой другую информацию, например криптографический ключ, манипулируемый во время алгоритма ALG, или подключ, такой как раундовый ключ. Они могут также представлять собой шифрованные данные, которые необходимо дешифровать с помощью криптографического алгоритма ALG (например, алгоритма AES), данные (открытые или зашифрованные), которые необходимо подписать, или подписанные данные, для которых необходимо верифицировать подпись и т.д.

Принимая во внимание порождающую матрицу G для линейного кода С, случайный выбор кодового слова из линейного кода С может просто состоять из случайного выбора вектора m в векторном пространстве $$F_q^{n-k}$$ , затем вычисляют с=mG. Это можно выполнять каждый раз при использовании криптографического алгоритма.

Для того чтобы определить k линейно независимых векторов L₁, L₂,…L_k, не включенных в линейный код С, и которые образуют матрицу L, первый вектор L_test можно случайным образом выбрать и затем можно проверить то, находится ли этот вектор в коде, путем применения проверочной матрицы Н (или другими словами путем вычисления L_testH). Если результат равен нулю, то вектор L_test находится в линейном коде С, и операция повторяется с помощью нового случайного вектора. С другой стороны, определяют L₁=L_test, и выработку вектора L_test повторяют до тех пор, пока не будет найден новый вектор, который не находится в линейном коде С, затем можно выполнить алгоритм, такой как Гауссовский алгоритм оценивания для того, чтобы определить, являются ли линейно независимыми вектора, порожденные до этой точки (в данном случае L₁ и последний L_test). Если они являются линейно независимыми, то последний выработанный вектор L_test отбрасывается и случайным образом выбирается новый вектор (до тех пор, пока не будет найден вектор L_test, который не находится в линейном коде С). Если они не являются линейно зависимыми, то определяется L₂=L_test, и новый вектор L_test выбирается случайным образом до тех пор, пока он не будет находиться в линейном коде, затем вычисляется Гауссовская оценка на основании всех векторов, выработанных до этой точки (L₁ и L₂, которые по своей структуре, как известно, не будут линейно зависимым, плюс последний L_test), и т.д. до тех пор, пока не получат k независимых векторов. Эти k линейно независимые вектора L₁, L₂,…L_k можно выбрать один раз и для всех и каждого целевого устройства. Например, для смарт-карты вектора можно вычислить (по отдельности) для каждой смарт-карты во время этапа персонализации карты упомянутой смарт-карты. Их можно также восстанавливать время от времени так, как было объяснено выше.

Настоящее изобретение является особенно предпочтительным в контексте симметричных алгоритмов шифрования/дешифрования, таких как алгоритм AES.

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

1. AddRK(K0)=AddRoundKey(K0)

2. для i от 1 до 9:

S = SubBytes;

SR = ShiftRows;

MC = MixColumns;

AddRK(Ki).

3. S;

4. SR;

5. AddRK(K10)

Таким образом, после его выполнения, на предварительном этапе, неизвестном здесь, операция расширения ключа, в которой раундовые ключи K0…K10 получают из заданного ключа шифрования, мы видим операцию AddRoundKey, которая состоит из объединения каждого бита состояния с раундовым ключом (посредством операции "исключающее ИЛИ"), После этого, существует последовательность девять раундов, причем каждый раунд включает в себя операцию SubBytes (которая представляет собой нелинейную операцию, в которой каждый байт заменяется на другой байт с использованием таблицы подстановок), операцию ShiftRows, которая реализует перестановку, во время которой каждая строка матрицы состояний сдвигается циклически, операцию MixColumn (которая объединяет четыре байта столбца в каждом столбце матрицы состояния), и в итоге операцию AddRoundKey, которая уже описана выше. В конце девяти раундов, алгоритм AES снова выполняет операцию SubBytes, за которой следует операция ShiftRows и затем операция AddRoundKey.

Согласно одному варианту осуществления алгоритм AES защищает из конца в конец следующим образом.

Сначала выполняют предварительное конфигурирование. В отличие от традиционного аддитивного маскирования уровня техники, операции будут выполняться с использованием промежуточных переменных разной размерности по сравнению с одной размерностью, используемой для промежуточных переменных традиционного алгоритма AES. Это предварительное конфигурирование можно выполнить только один раз (что означает только один раз независимо от числа раз алгоритма AES, который будет впоследствии использоваться). Предварительное конфигурирование состоит, например, из выработки новых операций AddRK', SR' и MC' таким образом, чтобы:

AddRK'(K)=AddRK(K).L

SR'(x·L)=SR(x)·L

MC'(x·L)=MC(x)·L

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

Затем выполняется предварительный этап для каждого изменения маски (это можно выполнять, например, каждый раз, когда используется алгоритм AES, или менее часто, в частности, если выбран достаточно большой параметр n). Предварительный этап может состоять, например, из случайного выбора двух кодовых слов с и с' и выработки S' таким образом, чтобы S'(x·L+c)=S(x)·c' для всех х (в данном случае одна и та же операция S' используется для каждого раунда алгоритма по причинам, которые связаны с производительностью, хотя различные S' можно хорошо использовать для каждого раунда, что обеспечит небольшое общее повышение безопасности).

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

0. Вычислить x·L+с из х

1. AddRK'(К0)

2. для i от 1 до 9:

(a) S';

(b) SR';

(c) МС';

(d) AddRK'(Ki)

(e) x=x+с+МС'(SR'(c'))

3. S';

4. SR';

5. AddRK'(K10).

6. Применить проверочную матрицу Н для получения окончательного результата. Таким образом, маскирование выполняют на этапе 0 с использованием линейного кода. На этапе 2(е) маскирование корректируют, принимая во внимание тот факт, что нелинейную операцию использует постоянную с', которая отличается первоначально (постоянная с), используемая во время первоначального маскирования на этапе 9. На этапе 6 производят проекцию полученных в результате данных с использованием проверочной матрицы. Это позволяет удалить все компоненты, которые находятся в линейном коде, и, таким образом, восстанавливают данные, которые будут получены с помощью алгоритма AES без маскирования. На этапе 6 после применения проверочной матрицы Н можно затем выполнить инверсию результирующей матрицы (x·L).H.

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

0. Вычислить x·L+c₁ из х, где с₁ - случайное кодовое слово

1. AddRK'(K0)+c₂, при с₁+c₂=с

2. для i от 1 до 9:

(a) S';

(b) SR';

(c) МС';

(d) AddRK'(Ki)+c₂

(e) х=х+c₁+MC'(SR'(c'))

3. S';

4. SR';

5. AddRK'(К10)+с₃, при случайных с₃.

6. Применить проверочную матрицу Н для получения окончательного результата.

Код можно выбрать для того, чтобы минимизировать операцию (e).

В некоторых конфигурациях вместо выполнения этапа (e): х=х+с+MC'(SR'(c')), можно применить на этапе (e) функцию D(x,с), которая принимает х и кодовое слово с в качестве входа, но не слово с'. Это можно достигнуть, например, используя проверочную матрицу, которая связана с кодом, включающим в себя все MC'(SR'(cc)), где ее охватывает все слова первоначального кода. Преимущество данного варианта осуществления состоит в том, что он устраняет необходимость сохранения значения с'.

Простая примерная реализация (в частности, где SR' и MC' получены непосредственно из SR и MC) соответствует случаю, где x·L имеет значение [х, 0…0] (х, за которым следует n-k нулей).

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

Таким образом, хотя способ защиты этапа шифрования AES был описан выше, можно также обеспечить безопасность этапа дешифрования AES тем же самым способом. Более того, хотя описанный вариант осуществления относится к алгоритму AES, настоящее изобретение применимо ко всем типам криптографических алгоритмов и, в частности, к алгоритму DES (и его варианту 3DES) и к алгоритму RC4, но также к ассиметричным алгоритмам или к хэш функциям (таким как SHA-1, MD5, SHA-256 или RIPEMD-160), в которых можно желательным образом защитить некоторые линейные функции.

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

Изобретение относится к защите исполнения криптографического алгоритма (ALG) от пассивного сниффинга. Технический результат - эффективная защита от пассивного сниффинга. Способ защиты исполнения криптографического алгоритма (ALG) от пассивного сниффинга реализует маскирование (MSK) данных, обработанных с помощью криптографического алгоритма. Маскирование (MSK) упомянутых данных включает в себя этап линейного кодирования, такой как х'=х·L+с, где х - данные, которые необходимо маскировать, х' - соответствующие маскированные данные, с - кодовое слово, включенное в линейный код С, и L - матрица, состоящая из линейно независимых векторов, не включенных в линейный код С. Настоящее изобретение также относится к устройству (SC), реализующему такой способ. 2 н. и 12 з.п. ф-лы, 2 ил.

1. Способ защиты исполнения криптографического алгоритма (ALG) от пассивного сниффинга, включающий выполнение маскирования (MSK) данных, обработанных с помощью криптографического алгоритма (ALG), отличающийся тем, что маскирование (MSK) данных содержит этап преобразования в виде х'=x.L+c, где х - маскируемые данные (CL_TXT), х' - соответствующие маскированные данные, с - кодовое слово, включенное в линейный код С, и L - матрица, состоящая из линейно независимых векторов, не включенных в линейный код С.

2. Способ защиты по п.1, в котором кодовое слово с выбирают случайно во время каждого исполнения криптографического алгоритма (ALG).

3. Способ защиты по п.1, в котором матрицу L выбирают случайно, только один раз для всех исполнений криптографического алгоритма (ALG).

4. Способ защиты по п.1, в котором маскирование выполняют перед использованием криптографического алгоритма (ALG), а операцию демаскирования (U_MSK) выполняют после использования криптографического алгоритма (ALG).

5. Способ защиты по п.1, в котором криптографический алгоритм (ALG) представляет собой алгоритм, использующий нелинейную операцию S, причем нелинейную операцию S заменяют на нелинейную операцию S' так, что S'(x.L+c)=S(x).L+c', где с' - кодовое слово линейного кода С.

6. Способ защиты по п.5, в котором криптографический алгоритм (ALG) содержит несколько раундов, причем каждый раунд содержит одну и ту же нелинейную операцию S, и нелинейную операцию S заменяют на одну и ту же нелинейную операцию S' во время каждого раунда.

7. Способ защиты по п.5 или 6, в котором с'=с.

8. Электронное устройство (SC), содержащее блок исполнения криптографического алгоритма и связанный с ним модуль маскирования, при этом модуль маскирования выполнен с возможностью реализации преобразования в виде х'=x.L+c, где х - маскируемые данные, х' - соответствующие маскированные данные, с - кодовое слово, включенное в линейный код С, и L - матрица, состоящая из линейно независимых векторов, не включенных в линейный код С.

9. Электронное устройство (SC) по п.8, в котором модуль маскирования выполнен с возможность выбора кодового слова с случайным образом во время каждого исполнения криптографического алгоритма (ALG).

10. Электронное устройство (SC) по п.8 или 9, в котором модуль маскирования выполнен с возможностью выбора матрицы L случайным образом только один раз для всех исполнений криптографического алгоритма (ALG).

11. Электронное устройство (SC) по п.8, в котором модуль маскирования выполнен с возможностью выполнения маскирования (MSK) перед использованием криптографического алгоритма (ALG), и выполнения операции демаскирования (U_MSK) после использования криптографического алгоритма (ALG).

12. Электронное устройство (SC) по п.8, в котором криптографический алгоритм указанного блока исполнения представляет собой алгоритм, использующий нелинейную операцию S, при этом модуль маскирования выполнен с возможностью замены нелинейной операции S на нелинейную операцию S' такую, что S'(x.L+c)=S(x).L+c', где с' - кодовое слово линейного кода С.

13. Электронное устройство (SC) по п.12, в котором криптографический алгоритм (ALG) блока исполнения содержит несколько раундов, причем каждый раунд содержит одну и ту же нелинейную операцию S, а модуль маскирования выполнен с возможностью замены нелинейной операции S на одну и ту же нелинейную операцию S' во время каждого раунда.

14. Электронное устройство (SC) по п.12 или 13, в котором с' равняется с.