Determining security key the hardware for digital devices.pdf Серьезной проблемой для электронной и оборонной промышленности в последние годы стали пиратство, перепроизводство и контрафакция, что привело к необходимости защиты проектов СБИС, СнК от несанкционированного вмешательства в цикл проектирования и / или производства интегральных схем [1]. По оценкам Technology Information Handling Services (IHS), финансовый риск из-за контрафактных и несанкционированных микросхем оценивается в более чем 169 млрд долларов в год, что примерно в 10 раз превышает ущерб от пиратства в области ПО [2]. Для оборонной промышленности важнейшей проблемой является возможность использования контрафактных интегральных схем с модифицированными функциями, что в определенное время может деструктивно повлиять на функционирование структуры, ухудшить эксплуатационные характеристики, привести к раскрытию конфиденциальной информации и др. Кроме больших финансовых потерь существует реальная проблема обеспечения национальной безопасности, так как 15% интегральных схем в системах оборонной промышленности являются контрафактными. В связи с этим стала очевидной необходимость защиты проектов на основе создания таксономии нарушений и отклонений, общего подхода к контролю СБИС, СнК, с моделями которых приходится работать при проектировании и организации контроля на всех этапах жизненного цикла цифровой системы с учетом злонамеренных внедрений в цикл проектирования и производства интегральных схем. Как развитие теории контролепригодного проектирования (Design-for-Testability; DfT) в работе [3] предлагается подход к проектированию Design-for-Trust (DfTr), который дополнительно включает средства для контроля и предотвращения аппаратных атак при проектировании и изготовлении СБИС. В последние годы для защиты проектов интегральных схем применяются методы и средства аппаратного кодирования комбинационных блоков. Для обеспечения надежности подобной защиты проектов необходимы средства контроля эффективности применяемых методов кодирования, выявления внесенных троянов на основе создания общего подхода к контролю проектов на всех этапах проектирования и производства. В работе рассматриваются некоторые особенности метода логического кодирования структурных схем цифровых устройств комбинационного типа. Предлагается метод взлома кода при наличии информации о структуре закодированного объекта и возможности доступа к физической модели. Задача решается на основе описания закодированной структуры в виде КНФ-функции разрешения, решения задачи выполнимости (SAT) и физического моделирования объекта. 1. Логическое кодирование ИС как метод аппаратной защиты В работе [2] проанализированы различные модели процесса злонамеренного искажения проекта, описывающие условия, при которых подобное искажение может внедриться в цифровую систему. В числе возможных источников искажений рассматриваются поставщики базовых функциональных блоков интеллектуальной собственности (IP’s), которые приобретаются разработчиками СнК, собственно разработчики СнК, а также кремниевые фабрики - изготовители СнК. Методы несанкционированного доступа в проект могут быть различными, в том числе основываться на применении специальных средств САПР, способных исказить проект на RTL-уровне. В современных условиях наиболее уязвимым этапом может быть этап производства. Одним из методов борьбы с вышеупомянутыми угрозами является логическое кодирование, которое обеспечивает доступ к объекту только авторизованным пользователям [4]. Метод предпола-103 Проектирование и диагностика вычислительных систем / Designing and diagnostics of computer systems гает сокрытие функциональности проекта и использование ключа, применение которого выводит систему в область правильного функционирования. Идея кодирования основана на том, чтобы изменить конструкцию ИС, добавив в нее дополнительные логические элементы и новые входы, называемые ключевыми, т.е. на применении метода обфускации структуры объекта. В такой постановке если злоумышленник не владеет ключом, то ему недоступна внутренняя реализация объекта. Задача структурной обфускации и логического кодирования заключается в том, чтобы затруднить или сделать невозможным получение подлинного ключа. Ключевые входы подсоединяются к защищенной от несанкционированного доступа памяти, а закодированная схема будет работать правильно только в том случае, если на ее ключевые входы поданы подлинные значения. Значения ключевых входов передаются после изготовления микросхем конечным пользователям (рис. 1). Таким образом, логическое кодирование основывается на предположении, что производитель не знает и не может вычислить подлинные значения ключевых входов или, в противном случае, поиск подлинного ключа должен быть для злоумышленника затруднителен. В литературе предложены различные методы кодирования комбинационной логики, в которых используются в качестве ключевых вентилей элементы XOR / XNOR [1, 5-7], AND / OR [8], мультиплексоры [9] или комбинации этих вентилей [10]. Выбор линии для включения вентиля, тип применяемого вентиля существенно влияют на эффективность кодирования. Воздействие неподлинного ключа можно сравнить с влиянием неисправности константного типа на данной линии (см. рис. 1). При выборе в качестве ключевых вентилей XOR или NXOR применение неподлинного ключа приводит к появлению неисправности константного типа в любом случае, при любом входном воздействии, в отличие от вентилей OR, NOR, AND, NAND, что влияет в целом на эффективность кодирования. a b d c e Рис. 1. Логическое кодирование цифровых устройств: а - общая идея кодирования; b - эффекты применения ключевого вентиля XOR-типа; c - NXOR; d - OR; e - NAND Fig. 1. Logic encoding of digital devices: а - general idea of coding; b - effects of applying an XOR-type key gate; c - NXOR; d - OR; e - NAND 104 Золоторевич Л.А., Ильинков В.А. Определение ключа аппаратной защиты цифровых устройств Кроме типа применяемого вентиля существует еще два основных способа увеличить влияние кодовых вентилей на значения выходов схемы. Один из них заключается в выборе линий, сигналы в которых влияют на максимально возможное количество выходов схемы, второй - в повышении чувствительности схемы в ответ на применение неподлинного ключа. Выбор линии для включения вентиля в большой степени влияет на эффективность кодирования. Один из подходов основан на случайном выборе линии схемы [4]. В работе [1] показана недостаточная эффективность этого метода. Во-первых, вставка ключевого вентиля в случайно выбранную линию схемы не может гарантировать необходимое расстояние Хэмминга между истинным выходным вектором и полученным в случае применения неподлинного ключа. В работе [11] для характеристики эффективности выбора линии в схеме для введения ключевого вентиля предложено использовать метрику M = N0P0 * NO + NP * NO, где N0P0 (NP ) - количество входных наборов, которые обнаруживают неисправность типа const 0 (const 1), а NO (NO ) -количество ошибочных бит выходного вектора в результате появления неисправности const 0 (const 1). Данная метрика может быть усовершенствована для получения возможности отслеживать в динамике параметры NO (NO ) для анализа неактивированных выходов при кодировании. Использование метрики M при кодировании можно сформулировать как нахождение множества неисправностей кодируемой схемы, которые вместе будут влиять на 50% выходных линий при их активизации. Кодирование на основе использования метрики M требует моделирования схемы Q = 2s я 2n раз, где s - общее количество линий схемы (переменных полного состояния схемы), n - количество входных переменных схемы. Для примера схемы, рассмотренного ниже, М = 256 я 34 = 8 704. Для реальных схем подобный подход практически не приемлем по причине высоких вычислительных затрат. В то же врмя с целью оптимизации вычислительных процедур предлагается эвристическое решение - сократить количество моделируемых входных наборов до 1 000 [11]. Основная задача, которая должна быть решена при практической реализации данной общей идеи, заключаются в том, чтобы определить оптимальное множество внутренних линий схемы и количество ключевых элементов для создания максимальных трудностей для злоумышленника по поиску подлинного ключа. При включении очередного вентиля при кодировании логических устройств необходимо проводить анализ на появление эффекта маскирования неисправностей, который способен блокировать эффект кодирования [1. Рис. 2]. При наличии избыточности некоторые линии схемы не могут быть активированы ни одним входным набором, поэтому вставка ключевого вентиля в данном случае может быть бесполезной [1. Рис. 1]. В работе [1] на примере рассмотрена возможность повышения эффективности кодирования за счет включения в структуру схемы вентилей управления, которые позволяют активизировать влияние неподлинного состояния каждого отдельного бита ключа на формирование выходного вектора закодированной схемы. Для того чтобы усилить влияние неподлинного бита кодового слова на результат функционирования схемы, управляющие вентили объединяют биты кодового слова в группы, использовав при этом их выходы в качестве входов ключевых вентилей. В таком случае реализуется групповое воздействие нескольких битов кодового слова на активацию ключевого вентиля. Если хотя бы один из ключевых входов, включенных в группу, принимает неподлинное значение, ключевой вентиль окажется активированным. 2. Контроль надежности кодирования комбинационных схем В работе [2] предлагается подход SAT-атаки для определения кода аппаратной защиты комбинационных схем цифровых устройств на структурном уровне. Подход основан на сведении задачи к определению выполнимости булевой функции. Ниже приводится алгоритм декодирования комбинационных схем на основе описания закодированной структуры КНФ-функции разрешения схемы и решения задачи ее выполнимости. Алгоритм проиллюстрирован на примере фрагмента схемы. 105 Проектирование и диагностика вычислительных систем / Designing and diagnostics of computer systems Исходными данными для декодирования структуры цифрового устройства являются структурная реализация закодированной схемы, которая может быть получена методом обратного проектирования (проектирования по прототипу), а также активированный физический образец интегральной схемы, в защищенную от несанкционированного доступа память которой заказчик загрузил подлинное значение ключа. Этот образец может использоваться в виде модели черного ящика Y = eval (X). Основная идея SAT-атаки взлома ключа состоит в том, чтобы определить подлинный ключ, не прибегая к исследованиям на большом интервале входно-выходных переменных [2]. Обозначим Y = f(X) - функцию, реализуемую комбинационной схемой с первичными входами X и выходами Y . КНФ-функции разрешения исходной схемы Cira(X,Y). Сведем задачу получения ключа к описанию закодированной схемы в виде КНФ-представления булевой функции разрешения Сігъ (X,К, Y), где X - первичные входы схемы, X = (х1,х2,...,хп); К - ключевые входы схемы, К = (kl,k2,...,kr); Y - выходные линии схемы, Y = (у1,у2,...,ут). Если F = / (X .Y) - функция, реализуемая исходной схемой, то для любого X F = Cirb(X ,K,Y), если применить к закодированной схеме подлинное значение ключа. Цель злоумышленника состоит в том, чтобы найти такой ключ К = (к1,к2,...,кг), чтобы УХ Сігъ(Х,К,Ү) /\\Сіга(Х,Ү) . Но злоумышленник не может получить формулу Сіга(Х,7), так как ему недоступно структурное описание исходной схемы. Не получив доступа к структуре исходной схемы и не имея, таким образом, возможности построить отношение Cira(X,Y), злоумышленник может наблюдать реакцию схемы на требуемое входное воздействие на активированной НС, выполнив функцию черного ящика еѵаі: Xl=(xl,x2,...,xn)^Yl=(yl,y2,...,ym) . Для заданного набора входных векторов Хх,Х2,...,Хр и соответствующих выходных наблюдений Yl,Y2,..Yp определение ключевого значения, которое согласуется с этимир наблюдениями, является достаточно простым, если свести задачу к решению выполнимости формулы (SAT) ^Cir^X^KJj). Однако если теперь выполнить новое наблюдение на физическом образце схемы eval(Xs) = Y,. то нет гарантии, что удовлетворительное присваивание К для формулы /У f 'irfX^KXf) также будет удовлетворительным присваиванием К для формулы A2i=P+iCirb(Xj’KJj)- Для практической атаки при большом числе входных переменных функция еѵаі может быть определена только на небольшом числе входных векторов Сігь(Х,K,Y) eval(X) = Y , в то время как 3К: УХ Сігъ(X. К.Ү) а Cira(Х.Ү). Решение проблемы заключается в том, что вместо поиска подлинного ключа выполняется определение ключа как члена класса эквивалентности ключей, который дает на выходах правильный результат для всех входных состояний. Определение 1. Два ключа и К2 являются эквивалентными (К1 = К2) тогда и только тогда, когда для входного значения X закодированная схема выдает одинаковое выходное значение Ү, для ключей К1 и К2. Для определения подлинного ключа итеративно исключаются ключи из класса эквивалентности, которые выдают неправильные значения выходов по крайней мере для одного входного шаблона. Класс эквивалентных ключей определяется на некотором вхо дно-выходном векторе решением выполнимости функции Cirb(Xj,K,Yj) полным методом. 106 Золоторевич Л.А., Ильинков В.А. Определение ключа аппаратной защиты цифровых устройств Определение 2. Входной вектор Xd называется различающим, если реакция схемы при использовании ключа К1 равна Yd и отличается от реакции Y2 при использовании ключа К2. При наличии различающего набора можно проверить реакцию активированной схемы для входа Xd и использовать ее, чтобы исключить ключ К1 или К2 как не являющийся подлинным ключом. Приведем алгоритм для нахождения подлинного ключа из класса эквивалентности: 1 /:= 1. 2 ^=сігі(ід1,};)лОг6(ід2/2). 3 Если EJ aEj фҮ2) не выполняется, переход к и. 8 - различающий набор не определен. 4 Решение Fi=Cirb(X,Kl,Yl)/\\Cirb(X,K2,Y2)/\\(Yl^Y2), Xf :=Х . Входной набор Xf является различающим. 5 ff :=eval(Xf). 6 7 = 7 + 1. 7 Ft=Ft_, ^Cirb(XdXJ?)^Cirb(Xd,K2J?) ■ Переход к и. 3. 8 Выход. Каждая итерация алгоритма исключает хотя бы один неверный член рассматриваемого класса. Это связано с тем, что поиск различающего входного набора ведется с условием Yx + Т2, т.е. при одинаковых входных данных выходные должны отличаться для разных ключей. Следовательно, хотя бы один ключ окажется неправильным. Алгоритм завершается, когда определен подлинный ключ из класса эквивалентных ключей. Для полноты изложения рассмотрим получение функции разрешения F. Функция F, называемая функцией разрешения для логической функции f зависит не только от аргументов функции f но и от самой f и принимает значение логической 1 при всех допустимых состояниях входных и выходной переменных [12]. Функция F принимает значение 0 при всех недопустимых состояниях входных и выходной переменных. Приведем функции разрешения F и запрета Ff в виде таблицы истинности для конъюнкцииf = a*b (табл. 1). В табл. 2 приведены КНФ-функций разрешения для некоторых типов вентильных элементов. Таблица 1 Функции разрешения и запрета a b f Ff Ff 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 0 1 Функции разрешения Т аблица 2 № п/п Однобитовые арифметические и логические уравнения КНФ-функций разрешения 1 и > -о II (b V f )(c v f )(b v c v f) 2 f = b * c (b V f )(c V f )(b V c V f) 3 f = a ® b (a V b V f )(a V b V f )(a V b V f )(a V b V f) 4 X II 4 (a V b V f )(a V b V f )(a V b V f )(a V b V f) 107 Проектирование и диагностика вычислительных систем / Designing and diagnostics of computer systems Рассмотрим пример. На рис. 2 приведены схема (рис. 2, а) и вариант ее кодирования, которое выполнено включением дополнительных вентилей XOR (Ві) и NXOR (В:) (рис. 2, Ь). Приведем функцию разрешения закодированной схемы Cirb(X,K,Y). При формировании соответствующей функции разрешения схемы переменные а, Ъ, с - входные переменные, а\\, аг, аз, Ъ\\, Ъг, сі - выходы соответствующих элементов. Cirb = (a v b v a )(a v b v ax )(a v b v ax )(a v b v ax) x x (b v c v a2 )(b v c v a2 )(b v c v a2 )(b v c v a2) x x (a v c v a3 )(a v c v a3 )(a v c v a3 )(a v c v a3) x x (a v k v b2 )(a v k v b2 )(a v k v b )(a v k v k) x x (k2 v a v k )(k v a v k )(k2 v a v k )(k v a v k) x x (k v a2 v b2 v cx )(k v a2 v b2 v cx )(k v a vb v c )(k v a2 v b2 v c) x x (k v a2 v b2 v c v a2 v b2 v c] )(k v a vb v c )(b] v a, v k v q). 1. В качестве входного вектора для поиска ключей используем случайный вектор X = 110 для которого определяем Y с помощью активированной схемы: еѵа/(Х) = 1 , 2. Найдем решение задачи SAT для функции F = Cirbabccx на основе полного алгоритма решения выполнимости: F = axa2a3(k vb2)(k vb2)(k2 vk)(k2 vk)abccx. Функция выполнима при следующих условиях: а) F = klk2ala2a3blb2cl; Кх =11; б) F = kk2ala2a3blb2cl', К2 =01; в) F = kк2аха2а3ЬхЬ2сх; К3 = 00 . Таким образом, определены три ключа, Кх =11, К2= 01, К3= 00, которые составляют класс эквивалентных на данном этапе декодирования. Рис. 2. Комбинационная схема для иллюстрации алгоритма взлома ключа: а - исходная схема; Ъ - закодированная схема Fig. 2. Combination scheme to illustrate the key cracking algorithm: а - original schema; b - coded scheme 3. Определим различающий входной набор для первых двух ключей Кх = 11 и К2 = 01 из найденного класса. Для этого необходимо определить выполнимость функции (1) Fx=Cirb(X,Kjl)^Cirb(X,K2,l)- 108 Золоторевич Л.А., Ильинков В.А. Определение ключа аппаратной защиты цифровых устройств Для решения (1) определяем один из выполнимых вход но-выходных векторов для первого ключа Кх =11. Задача решается на основе неполного алгоритма выполнимости функции Ғ = Cirbkxk2. (2) Получим F = abcklk2ala2a3blb2cl. Таким образом, определены новые входной X = 101 и выходной У = 1 векторы. Проверим выполнимость функции 1' = ('irhabckxk2cx на полученном входном наборе при значении выходного вектора, отличном от полученного в (2), для второго ключа К2 =01. В результате F = abcklk2ala2a3blb2cl . Следовательно, X = 101 является различающим входным набором, так как разным ключам соответствуют разные выходы. 4. Определим вектор Y => X = 101, Y = eval(X) = 1 с помощью активированной схемы. 5. Вычислим функцию (1) для ATj=ll: /у = (lrhabck]k2c] : для К2 =01: /у = ('irhabck]k:c]. Функция /у =Cirbabck\\k2cx не выполняется. Следовательно, ключ К2 =01 исключается из класса эквивалентности. 6. Вычислим функцию (1) для Къ= 00: /у = Cirbabcklk2cl. Функция /у не выполняется, так как ключ Къ = 00 не является подлинным. Поскольку ключи К2 = §\\ и Къ= 00 оказались неверными, подлинным ключом является единственный ключ, оставшийся в классе эквивалентности ключей, - К =11. Заключение В работе рассмотрены некоторые особенности кодирования структурной реализации проекта интегральной схемы на основе использования средств тестового диагностирования. Для оценки надежности кодирования предлагается алгоритм декодирования, основанный на решении SAT КНФ-функции разрешения, описывающей закодированную структуру. Проиллюстрированный на примере алгоритм нахождения правильного ключа из множества ключей класса эквивалентности направлен на решение проблемы декодирования схем практических размеров. Эффективность практического применения данного алгоритма зависит от эффективности этапа поиска различающего входного набора. При выполнении данного этапа целесообразно использовать неполные алгоритмы выполнимости, которые осуществляют поиск выполняющего набора неполным перебором пространства возможных решений. Основное достоинство таких алгоритмов - высокая скорость работы. Однако если алгоритм не находит решения за приемлемое время, применяется полный алгоритм решения выполнимости.

Скачать электронную версию публикации