Электронное устройство блочного шифрования, подходящее для обфускации

Электронное устройство блочного шифрования, подходящее для обфускации

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

Данное изобретение дополнительно относится к способу электронного блочного шифрования и соответствующему программному обеспечению.

УРОВЕНЬ ТЕХНИКИ

Блочные шифры являются часто используемыми примитивами в криптографии. Блочный шифр является алгоритмом для шифрования или дешифрования блока цифровых данных сообщения под управлением криптографического ключа. Блочный шифр производит действия над блоками цифровых данных сообщения с некоторым размером блока, традиционно измеряемого в битах. Обычные размеры блоков включают в себя 64, 128, 192, и 256 битов. Эта операция является детерминированной биективной (и, таким образом, обратимой) операцией. Известные блочные шифры включают в себя DES и AES.

Например, система распределения контента может шифровать контент перед распределением для противодействия пиратству. Зашифрованный контент может быть распределен через менее защищенные каналы, например, интернет, тогда как ключ, используемый для шифрования, может быть распределен с использованием более защищенного средства, например, систему DRM. Однако, даже распределение ключа не является безопасным. Даже реализации DRM могут быть дизассемблированы для извлечения их секретов, например, их секретных ключей. По этой и другим причинам, существует потребность в защищенном примитиве шифрования/дешифрования, который может быть защищен от обратной разработки.

Одним способом защиты ключа, например, ключа, используемого в реализации DRM, называемого главным ключом, может быть использование реализации блочного шифра. Шифр типа «белый ящик» является программной реализацией блочного шифра, в которой секретный ключ является «конкретизируемым». Конкретизация ключа в некоторой реализации фиксирует ключ и внедряет этот ключ в реализацию посредством частичного вычисления в отношении этого ключа; причем ввод ключа становится ненужным. Вычисления, которые зависят от ключа, выполняются, насколько это возможно, без знания входных данных блока данных сообщения. Обычно, может быть вычислено разворачивание ключа, и раундовые ключи могут быть объединены с другими этапами. Обычно, раундовые ключи могут быть объединены с уровнем подстановки, т.е., посредством сложения раундового ключа с выходными данными блоков подстановки в уровне подстановки.

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

Одним идеальным решением может быть реализация шифра в виде одной большой справочной таблицы. Однако, это неприменимо для реальных блочных шифров. Стратегия «белого ящика», которая подходит для этого идеально, представлена в работе “A White-Box DES Implementation for DRM Applications” под авторством S. Chow, P. Eisen, H. Johnson, and P.C. van Oorschot, 2002, опубликованной в книге Digital Rights Management of the Lecture Notes in Computer Science 2003. Вычисления, в частности, блочные шифры, могут быть реализованы в виде сети справочных таблиц, рандомизированных таким образом, чтобы информация о ключах была распространена по всей сети. Каждый структурный блок может быть выполнен кажущимся независимым от ключа. Таким образом, злоумышленник вынужден анализировать всю сеть для получения информации о секретных ключах. Обфускация сети таблиц возможна посредством добавления в начале и добавления в конце обфусцирующих (запутывающих) преобразований к преобразованиям, записанным в таблицах. Таким образом, каждая отдельная таблица является рандомизированной, пока не будет аннулирована комбинация всех обфусцирующих преобразований. Другой пример приведен в работе “White-Box Cryptography and an AES Implementation” под авторством Chow, Eisen and van Oorschot.

В криптографии по принципу «белого ящика» блочный шифр реализуют в программном обеспечении таким образом, чтобы атакующему было трудно извлечь ключ, даже если он имеет полный доступ к реализации. Однако, авторы изобретения обнаружили, что конкретный вид блочного шифра, так называемые сети подстановки – линейного преобразования (Substitution-Linear Transformation Networks) имеют в этом отношении уязвимые места, которые делают трудновыполнимой защиту с использованием общепринятых технологий по принципу «белого ящика». Для ознакомления с подробностями смотри работу “Cryptanalysis of a Generic Class of White-Box Implementations” под авторством Wil Michiels, Paul Gorissen, and Henk D. L. Hollmann. Проблема относится к способу организации шифров типа SLT (подстановка – линейное преобразование (Substitution-Linear Transformation)), т.е., любая реализация по принципу «белого ящика» блочного шифра типа, описанного выше, с использованием технологий по принципу «белого ящика», например, используемых Chow и др., будет уязвимой.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

Требуется обеспечение улучшенного блочного шифра.

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

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

Блочный шифр также очень хорошо подходит для использования в системе, такой как система, описанная в заявке на патент США, номер заявки 61/740,726, поданной 21 декабря 2012, озаглавленной “Computing device configured with a table network” того же самого заявителя. Кроме того, автоматизированные программные системы обфускации обычно являются более эффективными при использовании с блочными шифрами программной реализации описанного типа, чем с обычными блочными шифрами.

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

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

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Эти и другие аспекты данного изобретения явствуют из вариантов осуществления, описанных ниже, и будут разъяснены со ссылкой на них. На чертежах:

Фиг. 1а является блок-схемой, иллюстрирующей блочный шифр,

Фиг. 1b является блок-схемой, иллюстрирующей раунд блочного шифра,

Фиг. 2-4 и 5а являются блок-схемами, иллюстрирующими уровни подстановки,

Фиг. 5b является блок-схемой, иллюстрирующей уровень подстановки, включающий в себя кодирование,

Фиг. 6 является блок-схемой, иллюстрирующей вычислительное устройство,

Следует отметить, что элементы, которые имеют одинаковые ссылочные позиции в разных фигурах, имеют одинаковые структурные признаки и одинаковые функции, или являются одинаковыми сигналами. Если функция и/или структура такого элемента объяснена, то нет необходимости ее повторного объяснения в подробном описании.

ПОДРОБНОЕ ОПИСАНИЕ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ

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

Фиг. 1а показывает схематичный вид блочного шифра. Блочный шифр содержит некоторое количество раундов; причем показаны раунды 112, 114 и 116 блочного шифрования. Количество раундов зависит от конструкции блочного шифра. Например, в некоторых случаях используют 8 или 12 или 16 раундов. Обычно, количество раундов составляет 8 или больше. Также, показан входной блок цифровых данных 110 сообщения. Входной блок данных сообщения обычно является двоичными данными и имеет фиксированный размер блока. Обычными размерами блоков являются 64, 128, 192 и 256, причем 128 является особенно удобным выбором. Блок данных сообщения, который принимают в качестве входных данных, может быть разделен на слова, например, байты, по 8 битов в каждом, или полубайты, по 4 бита в каждом, и т.д. По окончанию раундов создают выходной блок 120 данных сообщения с соответствующим размером блока.

Начиная с блока 110 данных сообщения, последовательно применяют раунды 112-116, причем каждый раунд создает промежуточный результат с соответствующим размером блока. В случае фиг. 1а, первый раунд 112 применяют для создания первого промежуточного результата, затем раунд 114 применяют к первому промежуточному результату для создания второго промежуточного результата, и т.д. Первый промежуточный блок данных зависит только от входных данных блочного шифра, а каждый следующий промежуточный блок данных зависит от предшествующего промежуточного блока данных; обычно раунды 114-116 зависят только от промежуточного результата, который они принимают в качестве входных данных, и, возможно, раундового ключа.

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

Раунд может содержать уровень подстановки и уровень линейного преобразования. В операции уровня подстановки, блоки подстановки (S-блоки) применяют к блоку данных. Уровень линейного преобразования применяет линейное преобразование ко всему блоку данных.

Для получения защищенных блочных шифров, необходимо реализовать перестановку E_K (биективную функцию), которая является эквивалентной псевдослучайной функции; однако, функция шифрования должна быть также эффективно реализуемой. Нелинейные функции могут быть реализованы эффективно только для малых размеров слов; обычно они реализованы посредством справочных таблиц, и эти таблицы имеют размер, который увеличивается экспоненциально с увеличением размера блока. Линейные функции могут быть реализованы эффективно для больших размеров блоков, но не являются очень безопасными. Распространенные блочные шифры, такие как AES и 3DES объединяют две эти возможности: раунд блочного шифра содержит этап сложения с ключом и два уровня. Первый из этих уровней задают посредством набора блоков подстановки, называемых S-блоками. S-блок является нелинейной функцией малых слов, например, из k битов (обычно размер слова составляет байт или полубайт). Входные данные разделяют на k-битные слова, и каждое слово подают к S-блоку. В AES и DES уровень создает зависимость не между битами разных слов, а только между битами одного и того же слова. Второй уровень выполняет линейную функцию. Линейная функция оперирует полным n-битным блоком данных. Следовательно, этот уровень создает зависимость между битами разных слов. Такие блочные шифры называют сетями подстановки- линейного преобразования (Substitution-Linear Transformation Networks).

Фиг. 1b показывает возможную реализацию раунда блочного шифра SLT-шифра, например, для использования в качестве раунда блочного шифра на фиг. 1а.

Показаны входные данные 130 раунда. Входные данные раунда являются цифровыми, например, двоичными, данными с разрядностью, соответствующей размеру блока. Показанные входные данные приведены в виде некоторого количества входных слов 132-136 раунда. Каждое слово имеет размер блока подстановки, например, 4 или 8 битов. Раунд имеет уровень 140 подстановки. Уровень 140 подстановки содержит S-блоки 142-146. Каждый S-блок применяет функцию входного слова раунда к входному слову раунда. Эти функции обычно являются нелинейными. Например, они являются нелинейными относительно операции XOR (исключающее ИЛИ). Для каждого из слов во входном блоке 130 может быть использован разный S-блок. Может быть также использован один и тот же S-блок для всех слов. Следует отметить, что перед применением уровня 140 подстановки, может быть выполнено сложение с раундовым ключом, например, XOR (сложение по модулю два) раундового ключа, соответствующего размеру блока, с входными данными 130 раунда. Однако, предположим, что раундовый ключ включен в уровень 140 подстановки, с использованием частичного вычисления.

К объединенным результатам S-блоков 142-146 в уровне подстановки, например, объединенным посредством конкатенации результатов, применяют линейное преобразование 150, например, матричную операцию. Эта линейная операция может состоять из многочисленных линейных комбинаций, например, циклического сдвига слов, и т.д., как в AES. Результатом линейного преобразования 150 являются выходные данные 160 раунда, показанные здесь в виде многочисленных выходных слов 162-166 раунда.

Уровень 140 подстановки принимает в качестве входных данных входные данные 130 уровня подстановки, соответствующие, в этом случае, размеру блока, в этом случае, промежуточный результат, и преобразует их в выходные данные уровня подстановки посредством замены многочисленных слов другими словами. S-блоки могут быть справочными таблицами. Уровень 140 подстановки является полностью параллельным, причем каждый S-блок зависит строго только от одного входного слова раунда; причем каждый S-блок создает в качестве выходных данных одно выходное слово раунда. Выходные слова раунда не используются снова в этом уровне подстановки. Другими словами, уровень 140 подстановки не имеет блока подстановки, который выполнен с возможностью приема в качестве входных данных комбинации по меньшей мере части выходных данных более, чем одного дополнительного блока подстановки в том же самом уровне подстановки.

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

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

Фиг. 1b показывает структуру типичной SLT-сети. Входные данные 130 раунда разделяют на m слов x₁,x₂,…,x_m одинакового размера из k битов (следует отметить, что: n=mk), показанных в виде 132-136. Обычная длина слов составляет 4-8 битов (например, 6 битов для 3DES и 8 битов для AES). Входные данные подвергают операции XOR с раундовым ключом (не показано отдельно на фиг. 1b), и результат этой операции подают к m S-блокам S₁, S₂,…,S_m (142-146), т.е., слово 132 подают к S-блоку 142, слово 134 к S-блоку 136, т.е., каждое слово входных данных 130 подают к соответствующему S-блоку. Например, слово i подают к S-блоку S_i. Можно объединять функции сложения с раундовым ключом ⊕K_i и S_i в единственной функции из k на k битов. Обозначим эту функцию T_i. Далее, применяют линейное преобразование 150 к выходным данным S-блоков. Линейное преобразование может быть представлено в виде умножения на матрицу M. Результат дает выходные данные раунда. Выходные данные раунда могут быть использованы в качестве входных данных для следующего раунда, могут быть использованы в качестве выходных данных блочного шифра, или могут быть обработаны и затем использованы в качестве выходных данных блочного шифра. Например, конечное сложение с раундовым ключом или конечная перестановка могут быть применены в конечном раунде, который отличается от предшествующих раундов.

Авторы изобретения обнаружили, что, в общем, блочные SLT-шифры типа, показанного на фиг. 1а и 1b, имеют уязвимые места, связанные с получением обфусцированных реализаций для них, в частности, таких как реализации по принципу «белого ящика». Здесь показаны уровни подстановки, которые лучше подходят для обфусцированных реализаций.

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

Если уровень подстановки будет использоваться в SLT-сети, то уровень подстановки должен быть обратимым. Кроме того, размер входных и выходных данных такого уровня подстановки должен быть равен размеру блока. Однако, если уровень подстановки используют в другой структуре, например, для замены уровня подстановки в сетях Фейстеля, таких как DES, то этот уровень не должен быть обратимым, и размеры входных и выходных данных такого уровня подстановки не должны быть равны размеру блока. Фактически, можно даже допустить, чтобы размер входных данных уровня подстановки не был равен (обычно он больше) размеру выходных данных уровня подстановки.

Следует отметить, что уровни подстановки, описанные здесь, имеют преимущество, состоящее в том, что нелинейная часть кодирований не может быть изолирована от аффинной части входного/ выходного кодирования. Такое разделение является особенно проблематичным в SLT-шифрах, поскольку это прямо приводит к атакам на эти шифры. Однако, такой недостаток является нежелательным в любом блочном шифре, в частности, если они предназначены для реализации контекста модели атаки «белого ящика».

На фиг. 2-4, 5a и 5b показаны примеры уровней подстановки, которые не имеют этого недостатка. Эти уровни подстановки могут быть прямо использованы в SLT-шифре, показанном на фигурах 1a и 1b, посредством замены уровня 140 подстановки на уровень подстановки, показанный ниже. Далее, можно даже удалить линейное преобразование 150, в этом случае некоторые или все раунды содержат только уровень подстановки и, возможно, сложение с раундовым ключом. Это может быть выполнено, например, если уровень подстановки имеет полное рассеивание. Одним способом для установления этого является требование, чтобы каждый бит выходных данных уровня подстановки зависел от каждого бита входных данных уровня подстановки. Одним критерием для обеспечения этого является требование, чтобы для каждого местоположения бита x в выходных данных уровня подстановки и каждого входного местоположения бита y во входных данных уровня подстановки, существовало два входных значения уровня подстановки w1 и w2, которые отличаются по меньшей мере в местоположении бита y, и которые имеют свойство, состоящее в том, что выходные данные уровня подстановки для w1 и w2 отличаются по меньшей мере в местоположении бита x. В идеальном случае, это свойство должно обеспечиваться для каждого раундового ключа, но, в практических целях, может оказаться удовлетворительным, если это обеспечено для одного раундового ключа, например, выбранного случайным образом, или даже фиксированного, например, состоящего из одних нулей.

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

Смотри, например, работу “Avalanche and Bit Independence Properties for the Ensembles of Randomly Chosen n x n S-Boxes” под авторством Işıl Vergili and Melek Yücel; смотри, например, раздел 2.1 для определения лавинного критерия. Предполагается, что лавинный критерий является важным криптографическим свойством блочных шифров, которое обеспечивает то, что небольшое количество различий в битах во входном нешифрованном тексте ведет к лавине изменений, а именно, приводит к большому количеству различий в битах шифртекста. Более формально, функция удовлетворяет лавинному критерию, если всегда, когда один входной бит изменяется, в среднем, изменяется половина выходных битов. Точное удовлетворение этого определения лавинного критерия является нереальным, и допускается некоторый интервал погрешности. Лавинный критерий может быть использован на уровне блочного шифра, а также на уровне S-блока.

В общем, можно использовать уровень подстановки, как описано ниже, в виде большого S-блока, созданного из меньших S-блоков. Большие S-блоки могут быть затем использованы в сети подстановки -линейного преобразования (Substitution-Linear Transformation Network) подобно меньшим S-блокам, а также в сети Фейстеля, или, в общем, в качестве замены блока подстановки. Также, таким образом можно создать блочный шифр, для которого существуют более безопасные обфусцированные реализации. Таким образом, получена новая методика для создания нелинейной функции на основе n битов из малых S-блоков. Эта нелинейная функция больше подходит для обфусцированной реализации. На фиг. 2-4, 5a-5b не используется параллельное применение S-блоков, показанное на фиг. 1b, а используется сетевое применение S-блоков. А именно, вместо прямой подачи выходных данных всех S-блоков для линейного преобразования 150, части выходных данных части S-блоков используют в качестве входных данных других S-блоков.

На этих фигурах S-блоки показаны в виде блоков, стрелка в направлении S-блока показывает ввод в этот S-блок по меньшей мере 1 бита, стрелка из S-блока показывает вывод по меньшей мере одного бита.

Фиг. 2 показывает уровень 200 подстановки. Показаны входные данные 202 уровня подстановки и выходные данные 204 уровня подстановки. Уровень 200 подстановки имеет первый подуровень 210 и второй подуровень 220. Первый подуровень 210 содержит блоки 212-216 подстановки, а второй подуровень 220 содержит блоки 222-226 подстановки.

Каждый блок подстановки в первом подуровне 210 принимает все свои входные данные или часть их из входных данных 202 уровня подстановки. Первый блок 212 подстановки в первом подуровне 210 принимает входные данные только из входных данных 202 уровня подстановки, каждый следующий блок подстановки в первом подуровне 210 принимает входные данные как из предшествующего блока подстановки, так и из входных данных 202 уровня подстановки. Например, блок 212 подстановки принимает входные данные из входных данных 202 уровня подстановки, например, 8 битов. Блок 214 подстановки принимает входные данные из входных данных 202 уровня подстановки, например, 4 бита, и входные данные из выходных данных блока 212 подстановки, например, также 4 бита.

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

Каждый блок подстановки во втором уровне 220 принимает входные данные из соответствующего S-блока в первом уровне 210. Первый блок 226 подстановки принимает входные данные только из соответствующего S-блока 216 в первом уровне 210; каждый следующий блок подстановки принимает входные данные из соответствующего S-блока в первом уровне 210 и предшествующего S-блока во втором уровне 220.

Входные данные S-блоков в первом уровне 210 вместе составляют входные данные 202 уровня. Выходные данные второго уровня 220 вместе составляют выходные данные 204 уровня.

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

Следует отметить также, что выходные данные каждого S-блока во втором подуровне зависят от входных данных каждого S-блока в первом уровне. Этот признак делает очень вероятным, особенно с использованием больших S-блоков, что уровень подстановки также вызовет полное рассеивание (причем каждый выходной бит зависит от каждого входного бита). S-блоки предпочтительно выбирают в виде нелинейных функций. Например, можно взять S-блок AES или случайную нелинейную функцию; возможно, с раундовым ключом, добавленным в нее.

В качестве примера, можно взять в качестве размера блока степень 2, большую, или равную 32, например, 128, и использовать ее также для размера входных данных 202. Каждый S-блок может принимать меньшую степень 2 в качестве входных данных и выходных данных, например, 4 или 8 битов. Когда S-блок принимает входные данные более, чем от одного источника, или отправляет выходные данные более, чем к одному источнику, входные данные или выходные данные поровну разделяют между этими двумя источниками, например, на старшее и младшее полуслово (возможны и другие разбиения).

Фиг. 2 также показывает свойства длинных цепочек зависимых соединений. Например, имеются первый (212), второй (214), третий (224) и четвертый (222) блоки подстановки, имеющие свойство, состоящее в том, что четвертый блок подстановки принимает входные данные из выходных данных третьего блока подстановки, третий блок подстановки принимает входные данные из выходных данных второго блока подстановки, второй блок подстановки принимает входные данные из выходных данных первого блока подстановки. Это затрудняет прослеживание цепочки через S-блоки из-за нерегулярностей, например, в частности, для дифференциального или линейного криптоанализа.

Фиг. 3 показывает уровень 300 подстановки. Показаны входные данные 302 уровня подстановки и выходные данные 304 уровня подстановки. Уровень 300 подстановки имеет первый подуровень 310 и второй подуровень 320. Первый подуровень 310 содержит блоки 312-316 подстановки, а второй подуровень 320 содержит блоки 322-326 подстановки.

Каждый блок подстановки в первом подуровне 310 принимает все свои входные данные из входных данных 302 уровня подстановки. Каждый блок подстановки во втором подуровне 320 принимает все свои входные данные из выходных данных блоков подстановки в уровне 310 подстановки. Каждый блок подстановки во втором подуровне 320 принимает входные данные по меньшей мере из двух или более других блоков подстановки. Например, в первом и втором уровне может быть 8 S-блоков, причем каждый S-блок имеет 8 битов в выходных данных. Каждый S-блок во втором уровне принимает 1 бит из каждого S-блока в первом уровне, так что каждые выходные данные первого подуровня 310 используются только один раз.

Уровень подстановки фиг. 3 не имеет свойства длинной цепочки фиг. 2, однако, он имеет следующее свойство: уровень подстановки содержит первый (312), второй (314), третий (324) и четвертый (322) блоки подстановки, имеющие свойство, состоящее в том, что четвертый и третий блоки подстановки оба принимают входные данные из выходных данных первого и второго блока подстановки.

Фиг. 4 показывает вариант фиг. 2, в котором используются 3 подуровня. Показан уровень 400 подстановки, принимающий входные данные 402 уровня подстановки и создающий выходные данные 404 уровня подстановки. Уровень 400 подстановки содержит первый подуровень 410, имеющий блоки 412-416 подстановки, второй подуровень 420, имеющий блоки 422-426 подстановки, и третий подуровень 430, имеющий блоки 432-436 подстановки. Количество подуровней может быть увеличено более, чем до 3, или даже до, например, 32 (или больше), или 64. Такой уровень подстановки может быть использован без уровня 150 линейного рассеяния.

Следует отметить, что все уровни подстановки, показанные на фиг. 2, 3, и 4, являются обратимыми всегда, когда отдельные S-блоки являются обратимыми.

Фиг. 5а показывает версию фиг. 2, в которой раундовые ключи включены в S-блоки. В этом примере, раундовые слова имеют размер k=8. Количество используемых S-блоков составляет p. Сеть S-блоков состоит из левого (первого) уровня и правого (второго) уровня. В левом уровне, выходной байт S-блока T_i с i<p разделяют на два полубайта (также возможны другие варианты разделения байта на 2 слова). Один полубайт подают в качестве входных данных к S-блоку T_p+1 правого уровня, а другой подают к следующему S-блоку S_i+1 в левом уровне.

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

Предположим, что сеть S-блоков T₁,T₂,…,T_2p описана в приведенном выше разделе. Если принять p=3, то можно построить нелинейную биективную функцию F на основе 16 битов. Для реализации этой функции, необходимо 6 справочных таблиц: по одной для каждого T_i. Эти справочные таблицы состоят из 2⁸ строк, причем каждая строка содержит один байт. Следовательно, требуемый объем памяти составляет 1,536 байт. Для сравнения, для реализации произвольного 16-битного S-блока G посредством единственной справочной таблицы потребуется справочная таблица, состоящая из 2¹⁶ строк, причем каждая строка состоит из 2 байтов. Это подразумевает, что требуемый объем памяти составит 131,072 байт. В более общем виде, требуемый объем памяти для F составляет 2p∙2⁸, в то время как требуемый объем памяти для G составляет 2^4+4p. Следовательно, требуемый объем памяти для F растет линейно относительно p, а требуемый объем памяти для G растет экспоненциально относительно p.

Фиг. 5а принимает входные данные размера k(p+1)/2, предполагая, что все входные/выходные данные разделяют на две части размера k/2. Если желательно иметь степень двойки в качестве входных данных, то необходимо выбрать k и (p+1) в виде степеней двойки.

Уровень подстановки, полученный посредством конструкции фигуры 5а, может быть использован для конструирования блочного шифра на основе n битов из F различными способами. Ограничимся объяснением того, как может быть сконструирован единственный раунд блочного шифра. Полный блочный шифр легко получают посредством последовательности некоторого количества таких раундов. Выберем p таким образом, чтобы F стала функцией n битов, или выберем p таким образом, чтобы F стала функцией l бита, причем l нацело делит n, т.е. n=l⋅r для некоторого r. Сгенерируем r таких функций (обозначенных F₁,F₂,…,F_r). Может быть сконструирована SLT-сеть, показанная на фиг. 1а и 1b, в которой S-блок 142-146 задан посредством F_i и m=r. Полученный шифр лучше подходит для обфусцированной реализации в контексте модели атаки «белого ящика», чем стандартный SLT-шифр, и, в частности, для реализации «белого ящика».

Фиг. 5b. В обфусцированной реализации ключ скрывают от атакующего, который имеет полный доступ к реализации. Широко известная технологи