Дифференциальный протокол первичной защиты ключа шифрования-дешифрования

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:13, 2 декабря 2015.
A Forward-Secure Symmetric-Key Derivation Protocol
A Forward-Secure Symmetric-Key Derivation Protocol.PNG
Авторы Eric Brier[@: 1],
Thomas Peyrin[@: 2].
Опубликован 2010 г.
Сайт Universität Trier
Перевели Arseniy Kolobaev
Год перевода 2015 г.
Скачать оригинал

Аннотация.

В данной статье мы изучаем интересную и очень полезную ключевую проблему управления. Сервер делится ключом шифрования-дешифрования с клиентом, чья память приурочена к регистру хранения ключа R. Хотелось бы, чтобы клиент отправлял личные сообщения, каждый раз используя новый ключ производный от оригинального полученного ключа и определённый строкой (ресурс, содержащий ценную информацию) общего доступа, отправленной вместе с сообщением. Сервер может обработать только вычисления N, чтобы найти производный ключ, отвечающий данному сообщению. Наконец, алгоритм нужно предварительно обезопасить со стороны клиента: даже если произошла утечка всей памяти клиента, для атакующего должно быть невозможно получить предварительно использованные ключи обмена информацией. Данные N и R, общее количество ключей T, которые может использовать система, должны быть настолько большими, насколько это возможно.
На практике такой дифференциальный протокол первичной защиты ключа шифрования-дешифрования уместен, в частности в сфере оплат, где клиентами являются ограниченные в памяти терминалы оплаты, где распространение ключей шифрования-дешифрования на участке является очень дорогим процессом. В настоящее время широко распространён один стандарт: схема передаваемого уникального ключа транзакции (ПУКТ), определённый в Американском национальном институте стандартов (АНИС) Х9.24. Тем не менее, этот алгоритм сложный для понимания, не расширяемый и предлагает скромные характеристики.
Здесь мы приводим новую конструкцию, Оптимальный-ПУКТ (или О-ПУКТ), который не только проще и более расширяем, но также более эффективен с точки зрения и требований памяти клиента, и вычислений сервера, когда общее количество ключей T фиксировано. Наконец, мы также доказываем, что наш алгоритм оптимален в отношении памяти клиента R / вычислений сервера N / количестве ключей T, которые система может использовать.

Ключевые слова:

  • управление ключами
  • дифференцирование ключей
  • ПУКТ
  • первичная защита

Введение

Одна из самых сложных частей информационной безопасности связана с практической криптографией в управлении ключами. Может существовать множество различных сценариев, и к каждому из них часто применяются различные методы. Для банковской индустрии вполне нормально сталкиваться с жёсткими ограничениями, связанными с управлением ключами. Финансовые сделки происходят в терминале оплаты, который считывает магнитную карту пользователя и информацию на чипе карты. Чтобы подтвердить верность ввода PIN пользователем, протоколы основываются на обычно используемой криптографии ключей шифрования-дешифрования. Также из-за недавних разрушительных атак на операционные отделы серверов оплаты, индустрия нашла усиленные средства защиты информации обладателя карты, которая отсылается в банк. Ведущие решения, применяющие шифрование с сохранением формата, также основаны на криптографии ключей шифрования-дешифрования.

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

С недавних пор индустрия отметила рост обходных атак, осуществимых и разорительных методов, цель которых – выявление секретного ключа внутри криптографических модулей, путём анализа нестандартных информационных каналов, как например, время вычислений, мощность потребления, электромагнитная эмиссия и др. Так как среда терминалов оплаты не может считаться надёжной, обходные атаки должны быть серьёзно приняты во внимание. По этой причине банковская индустрия активно рекламировала улучшенный и более безопасный протокол управления ключами: схема передаваемого уникального ключа транзакции (ПУКТ), определённый в Американском национальном институте стандартов Х9.24.

Идея ПУКТ – выделить из оригинального распространённого ключа уникальный ключ для каждой операции. Эта опция значительно снижает возможность обходных атак, для которых должны быть выявлены многие следы вычислений процессов шифрования с одинаковым ключом шифрования-дешифрования. Более того, этот метод создан как способ первичной защиты стороны клиента (сервера рассматривают локализованными в безопасной среде): если внутреннее содержимое клиента выявлено, атакующий не сможет найти ни одного операционного ключа, использованного ранее. Алгоритм может содержать до миллиона различных ключей, что кажется разумным предельным значением для количества операций, происходящих во время срока службы терминала оплаты. Таким образом, дорогой процесс введения ключа может быть осуществлён только один раз.

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

Наше дополнение. В данной статье мы предлагаем улучшение техники ПУКТ, описанной в Американском национальном институте стандартов Х9.24. Наш дифференциальный протокол первичной защиты ключа шифрования-дешифрования предлагает расширяемость, упрощённость и рост производительности памяти / вычислений. Также проблема, изучаемая здесь нами, более глобальна, чем просто частный случай терминалов оплаты в банковской индустрии: ограниченные в памяти клиенты, которые хотят разделить с ограниченным в вычислениях сервером ключи шифрования-дешифрования уникальные для каждого сообщения, отправленного способом первичной защиты. После описания нашего нового предложения О-ПУКТ, мы показываем, что он оптимален в отношении памяти клиента R / вычислений сервера N / количестве ключей T, которые может использовать система. Следует отметить, что мы ограничиваем себя в использовании ключа шифрования-дешифрования только в криптографии. Для первичной защиты схем расшифровки используется, например, открытый шифровальный код.

Последнее слово техники

Цели и трудности

ПУКТ – схема ключа шифрования-дешифрования, предлагающая несколько хороших опций для операций платёжной индустрии (или любой ассиметричной ситуации, где один сервер безопасно обменивается информацией со многими ограниченными в памяти клиентами). Во-первых, ключи шифрования-дешифрования для каждой платёжной операции различны. Более того, включена функция первичной защиты: если внутреннее состояние терминала оплаты полностью или частично так или иначе подвергнуто опасности, никакая полезная информация о ключах, использованных при осуществлении предыдущих операций, не может быть получена из-за этой утечки. Обычно схема ПУКТ используется для различения ключей шифрования-дешифрования в случае зашифровки PIN-кодов (для идентификации пользователя), а в последнее время и для различения ключей шифрования-дешифрования, шифрующих конфиденциальную банковскую информацию, например личный номер счёта (ЛНС), дату истечения срока хранения данных и т.д.

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

где является псевдослучайной функцией. В Приложении А мы даём информацию о том, как F получается на практике. Таким образом, система запускается, передавая БКД на сервер, и – каждому клиенту. Это распространение ключей находится вне рамок данной статьи, но в целом оно производится со стороны клиента в безопасном помещении введением кода вручную или удалённым введением кода с использованием криптографии открытого шифровального кода. Следует отметить, что когда операция происходит в направлении от клиента к серверу, идентификация клиента также должна быть отправлена, чтобы сервер мог должным образом изменить оригинально распределённый ключ . Процесс идентификации показан на рисунке 1. Проблема, исследуемая в данной работе, может быть сужена до ситуации с одним клиентом. Поэтому в дальнейшем мы будем рассматривать два явления: сервер S и клиент C, который изначально распределяет ключ IK.

Рис. 1 Идентификация сервера и клиентов.

Мы бы хотели выделить уникальные операционные ключи способом первичной защиты, используя только функцию F как пульт управления. Существует естественный и неэффективный метод достижения этого: клиент С поддерживает внутреннюю структуру одного ключа, идентифицированного с помощью IK. Внутренняя структура после проведения j-ой операции определяется как , и получается, что . Затем ключ, использованный в операции j, просто хранится во внутренней структуре, , и мы совершенствуем внутреннюю структуру с помощью . В каждой операции клиент отправляет величину j, так что сервер может понять, какой ключ произведён для этой операции. Ясно, что каждый производный ключ будет уникальным (исключая случайности), и это является особенностью первичной защиты: F является необратимым процессом, таким образом никто не сможет получить информацию о предыдущих ключах, выявляя внутреннюю структуру. Также ясно, что это крайне неэффективно со стороны сервера. Если кому-то захочется провести пусть даже миллион операций, в худшем случае серверу возможно придётся провести миллион вычислений F, чтобы получить ключ.

Идея АНИС X9.24 ПУКТ в том, чтобы позволить клиенту хранить больше информации, чем один ключ, чтобы снизить стоимость вычислений со стороны сервера. Точнее ПУКТ позволяет серверу хранить регистры хранения ключа R = 21, а серверу –производить вычисления максимально в десять раз быстрее (N = 10) для одного варианта ключа (кроме ). В целом может быть осуществлено T = 1048575 операций.

В данной работе мы покажем, что ПУКТ не является оптимальным в изучении следующего: при данных по максимуму регистрах хранения ключа R в одном клиенте С и N вычислениях величины F на сервере S для одного исходного ключа, каким является количество T удалённых ключей, которые может содержать система в момент осуществления функции первичной защиты, если вся зашифрованная в C информация подвергнута опасности? Мы предлагаем оптимальный алгоритм, названный Оптимальный-ПУКТ (или О-ПУКТ), который может содержать до производных ключей. Например, с реальными данными ПУКТ, R = 21 и N = 10, мы можем создать T = 44352164 ключей. В другом случае если целью является производство около миллиона ключей, можно использовать наше решение только с регистрами хранения ключа R = 13. Наше решение более привлекательно не только в сфере памяти и вычислений, но проще для восприятия и применения. Наконец Оптимальный-ПУКТ абсолютно расширяем и зависит от ожидаемой / желаемой памяти / сложностей расчётов в системе, он предлагает очень ценные возможности для практического применения.

Описание АНИС X9.24 ПУКТ

Для полноты и будущего сравнения в данном разделе мы предлагаем описание реального алгоритма ПУКТ, определённого в документе АНИС X9.24-2009. Мы предлагаем распределённый ключ шифрования-дешифрования IK, безопасно переданный клиенту и серверу. Мы определяем hw(x) как массу Хемминга для слова x. Представление основы 2 обозначено , например 12 на основе 2 записывается как , наиболее важный бит помещается слева. Также для мы определяем y = x , являющийся величиной x с минимально значимым «1» битом, заданным для нуля. Например, если , мы имеем и .

Чтобы определить производный ключ, для каждой операции от клиента к серверу отправляется 21-битный счётчик tc. Затем для операции j отправляется величина счётчика tc = j, и используется ключ, идентифицированный с помощью j. Первоначальный ключ IK считается ключом, определённым с помощью j = 0. ПУКТ верно определяет иерархию ключей: каждый ключ, использованный в операции , является дочерним по отношению к ключу, определённому с помощью (говоря, что A является дочерней по отношению к B, мы имеем ввиду, что A напрямую произведена от B с F). Например, ключ, определённый с помощью имеет четыре дочерних ключа, определённых с помощью и , так как . Точнее мы имеем:

Перед описанием процесса со сторон сервера и клиента можно задаться вопросом, почему нужен 21-битный счётчик (20 бит было бы достаточно). Причина в том, что не все величины счётчика и соответствующие ключи будут использованы. В действительности только величины счётчика с ненулевой массой Хемминга меньшей или равной 10 будут рассмотрены и могут быть нацелены на общее количество ключей

Со стороны сервера. S получает 21-битную операцию счётчика tc. Сервер произведёт ключ операции только с hw(tc) расчётами F (так как мы приняли hw(tc) ≤ 10, у нас есть свойство, при котором требуется N = 10 расчётам F). Во-первых, S устанавливает позицию бита наиболее значимым «1» битом tc и рассчитывает и . Это продолжается до тех пор, пока hw(tc) «1» биты счётчиков не подействуют. Затем последний ключ, хранящийся в , становится распределённым ключом для данной операции. Можно видеть, что серверное производство состоит из следующей иерархии ключей, начинающейся с IK и кончающейся . Например, если , сервер сначала рассчитывает , затем и затем .

Со стороны клиента. Производство со стороны клиента немного сложнее. Во-первых, клиент определяется следующим образом: каждый регистр r заполнен величиной с , например каждый регистр r заполнен . Затем IK стирается из памяти клиента. Можно заметить, что эти ключи R = 21 являются материнскими для всех будущих ключей. Для первой операции ключ, отвечающий tc = 1, помещается в первый регистр (так как ключ, хранящийся в этом регистре, является . Как только операция завершена, содержание этого регистра стирается, чтобы сохранить первичную защиту: только IK является материнским для , и он уже стёрт. Следует отметить, что можно легко стереть , потому что у него нет дочерних ключей, так что при последующем произведении никто не потеряет никакой важной информации. Затем, когда tc = 2, как ключ операции используется содержимое регистра 2. При этом, так как является материнским по отношению к , то создаётся , который хранится в регистре 1. Этот процесс продолжается, пока все регистры больше перестанут содержать информацию.

В итоге для операции j клиент берёт и использует ключ , находящийся в журнале r, где r является позицией минимально значимого бита «1» операции. Затем перед стиранием из памяти клиент производит и хранит все r – 1 дочерние ключи в последних значимых регистрах r – 1. Первичная защита всегда поддерживается, так как после использования ключа операции всегда нужно быть уверенными в том, что этот ключ и его «мать» (или «бабушка») больше не появятся в памяти клиента. Также следует помнить, что все величины счетчика с массой Хемминга определённо строго увеличены в 10 раз. В таблице 1 мы даём иллюстрацию хронологического доступа к регистрам ключей.

Новое предложение: О-ПУКТ

Основная идея

Нашу основную идею по улучшению ПУКТ можно понять с помощью простого наблюдения: для самой первой операции ПУКТ tc = 1, ключ , находящийся в первом регистре, используется и сразу стирается. Заметим, что у этого ключа нет дочерних в иерархии ключей, и что его «матерью» является IK (он находится на расстоянии 1 от IK). Иначе говоря, сервер может получить из IK только с одним вычислением F. Вместо стирания напрямую и так как мы всё ещё далеки от достижения 10 вычислений F со стороны сервера, мы могли бы произвести другой ключ из и поместить его в первый регистр. Развивая эту идею, мы могли бы создать ещё 9 ключей только с помощью первого регистра. Теперь это может быть распространено также на другие регистры. Как только первый регистр получает ключ, находящийся на расстоянии 10 от IK, мы больше не можем производить. Затем нам придётся использовать ключ, находящийся во втором регистре, но перед его стиранием из памяти клиента мы можем произвести из него два новых ключа, которые поместим в первый и второй регистры. Эти два новых ключа находятся на расстоянии 2 от IK. Мы снова можем производить множество ключей, используя только первый регистр, но на один меньше, чем ранее, так как мы начали с ключа на расстоянии 2 (а не 1) от IK. В итоге эта идея повторяется для всех регистров.

Таблица 1. Хронологические доступы регистрам ключей на стороне клиента для ПУКТ. Величина i в ячейке значит, что ключ произведён и сохранён в соответствующем столбце регистра в соответствующем ряду цикла. «X» значит, что для данной операции клиент использовал ключ, находящийся в соответствующем регистре, и стёр его содержания.

Таблица 1

Описание

Чтобы сохранить расширяемость алгоритма, Оптимальный-ПУКТ будет определён как совокупность схем управления ключами. Каждый член совокупности определён количеством R регистров ключей, доступных со стороны клиента, и числом N максимальных вычислений, призванных производить один ключ со стороны сервера. Более того, позже мы покажем, что каждый член может содержать максимальное количество ключей Что касается оригинального ПУКТ, мы предлагаем, чтобы распределённый ключ шифровки-дешифровки IK был секретно передан клиенту и серверу. Чтобы определить производный ключ, для каждой операции от клиента к серверу отправляется строка общего доступа st. Сообщение состоит из целых чисел притом, что для . Целое число является расстоянием от IK ключа, хранящегося в регистре i памяти клиента до проведения операции. Например, личное сообщение самой первой операции будет , второй и т.д.

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

Обращаясь к осуществлению новой операции, клиент создаёт st = D и ищет последний значимый регистр, содержащий соответствующее расстояние строго меньшее, чем . Этот регистр, определяемый нами как , содержит ключ шифровки-дешифровки TK, который будет использован. Затем как только завершается транзакция,

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

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

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

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

Таблица 2. Пример развития регистров ключей и таблиц расстояний со стороны клиента с параметрами и . Мы обозначаем ключом, использованным в цикле . «X» в столбцах развития регистров ключей значит, что клиент стирает содержание этого регистра. (in out – ввод/вывод ком. переводчика).

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

  • Пока , рассчитывает и .
  • Если , тогда является ключом, распределённым на клиент так, что программа может остановиться.
  • Сервер находит максимально значимую позицию как например . Если , тогда он рассчитывает и изменяет частные переменные и . В противном случае является ключом, распределённым на клиент так, что программа может остановиться.

Этот алгоритм в точности следует имплицитному процессу, представленному клиентом, чтобы произвести ключ шифровки-дешифровки из исходного ключа . Например, повторное использование сценария из таблицы 2 предполагает, что сервер получает . Сначала он установит и рассчитает . Затем он не переходит в новый цикл до первого «если». Он рассчитывает и так как , ключ является ключом, распределённым на клиент. В таблице 3 мы даём более сложный пример.


Таблица 3. Пример производства ключа со стороны сервера с параметрами системы и . Ключ произведён через 8 вычислений. (in out – ввод/вывод ком. переводчика).

Анализ действия

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

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

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

Единственный способ для регистра удержать ключ на расстоянии – изменить ключ на расстоянии , сохранённый в регистре . Таким образом, для и мы имеем:

что упрощается до

Мы определяем функцию , а известно, что:

где произведён индукцией из . Таким образом, используя мы получаем:

Так как у нас есть и , мы заключаем, что для и

Общее количество ключей, хранящихся системой, рассчитывается так:

Наконец, используя тождества и , мы получаем:

Доказательство оптимальности

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

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

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

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

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

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

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

TemplateTheoremIcon.svg Теорема Теорема 1.
Алгоритм первичной защиты ПУКТ с регистрами клиента и максимальными вычислениями сервера может произвести наибольшее количество различных ключей с помощью .
Доказательство
Пусть является оптимальным алгоритмом, например достигающим максимальной величины ключей , хранимых системой. Мы докажем эту теорему через несколько очень простых лемм, относящихся к .


TemplateLemmaIcon.svg Лемма «Лемма 1.»
После идентификации осуществления регистры клиента заполнены новыми различными ключами . Доказательство. Ясно, что не заполнение всех регистров во время фазы идентификации является неоптимальным методом. Пусть будет таким первичным алгоритмом защиты ПУКТ. Мы можем предварительно создать другой алгоритм первичной защиты ПУКТ , который создаёт строго больше ключей, чем : во время фазы идентификации сохраняется ещё один ключ производный от в одном из регистров, не заполненных . Он использует этот ключ для самой первой операции и стирает содержимое соответствующего регистра. Когда ключ использован и стёрт из памяти клиента, идентично . В итоге в процессе создаётся ещё один ключ.


TemplateLemmaIcon.svg Лемма «Лемма 2.»
Когда производит ключи на стороне клиента во время изменения регистров, он запоминает только недавно произведённые ключи в свободных регистрах. Доказательство. В действительности пусть будет алгоритмом первичной защиты ПУКТ, который запоминает недавно произведённый ключ в несвободном регистре во время одной операции. Мы можем заведомо создать другой алгоритм ПУКТ , который создаёт строго больше ключей, чем : идентично , но вместо непосредственного стирания этого конкретного регистра он сначала использует ключ, хранящийся там, и стирает содержимое регистра, когда операция завершена. В итоге в процессе создаётся ещё один ключ.


TemplateLemmaIcon.svg Лемма «Лемма 3.»
Когда производит ключи на стороне клиента во время изменения регистров, все предварительно свободные регистры заполняются в конце процесса. Доказательство. Пусть является алгоритмом первичной защиты ПУКТ, который не заполняет все свободные регистры, производя новые ключи во время одной операции. Мы можем заведомо создать другой алгоритм ПУКТ , который создаёт строго больше ключей, чем : идентично , но в качестве альтернативы заполняет один из свободных регистров, которые не заполняет новым отличным ключом (это возможно, так как мы предположили, что обладает неким содержанием ключа для производства в данное время). Затем во время следующей операции будет использовать , сотрёт его и, наконец, продолжится в качестве в предыдущей операции. В итоге в процессе создаётся ещё один ключ.


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

TemplateLemmaIcon.svg Лемма «Лемма 4.»
Ключ шифровки-дешифровки, выбранный , всегда является одним из ключей на максимально возможном расстоянии от (отличного от ). Доказательство. Пусть является алгоритмом первичной защиты ПУКТ, который берёт ключ шифровки-дешифровки из регистра , содержащего ключ на расстоянии от , где dmax обозначает максимально возможное расстояние среди регистров . из предыдущих лемм мы знаем, что после стирания все свободные регистры должны быть заполнены ключами производными из . Мы можем заведомо создать другой алгоритм ПУКТ , который создаёт строго больше ключей, чем : идентично , но в качестве альтернативы осуществляет ещё одну операцию. Сначала берёт ключ шифровки-дешифровки из ряда регистров, содержащих ключи, находящиеся на расстоянии от . Мы определяем этот регистр как . затем стирание просто состоит из стёртых . Для следующего цикла берёт ключ шифровки-дешифровки из и осуществляет изменение в точности, как . Единственная разница для состоит в том, что будет также изменён, потому что теперь он свободен. Изменение производится с помощью , находящегося на расстоянии : мы создаём вызовы , чтобы осуществить производство, так что в итоге содержит ключ на расстоянии . Таким образом, на этой позиции создаёт ещё на один ключ (например, ) больше, чем за время достижения одной позиции расстояния в таблице (так как находится на расстоянии и для , и для ).


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

Обсуждения

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

а со стороны клиента это

В случае О-ПУКТ мы имеем

а для классического ПУКТ мы имеем , где .

Таблица 4. Сравнение ПУКТ (параметры ) и О-ПУКТ (параметры и )

Таблица 4.

В сравнении с классическим ПУКТ, если мы используем тоже самое количество регистров для О-ПУКТ, нам нужно будет совершить максимально только вычислений, чтобы получить такое же количество ключей . Если мы допустим такое же максимальное количество вычислений для О-ПУКТ, тогда нам нужно содержать только регистров ключей, чтобы получить такое же количество ключей: . Таблица 4 даёт цифровое представление о и . Таким образом, осуществление улучшения двояко: для фиксированных и не только О-ПУКТ обладает меньшим максимальным количеством вычислений на стороне сервера, но и среднее значение вычислений также меньше. Наконец, мы предлагаем пример, для которого О-ПУКТ предлагает лучшие результаты в сравнении с каждым осуществляемым аспектом ( и даёт и ).

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

Предложенное нами применение О-ПУКТ требует от клиента отправлять строку или целые числа в промежутке . Это может быть кодировано в биты. Алгоритм прост в понимании и применении, но он не оптимален в отношении размера сообщения, так как . например, классический ПУКТ отправить 21-битный счётчик в то время, как О-ПУКТ (с параметрами ) требует 48 бит.

Можно обдумать несколько вариантов, если размер сообщений является практической проблемой. Например, самый просто способ уменьшить размер сообщения – максимально использовать доступную память на стороне сервера. Например, вместо отправки таблицы до осуществления операции, клиент может просто отправить счётчик операции (таким образом, получаем кодированные биты, наименьший возможный размер сообщения). Сервер мог бы взять соответствующую таблицу из полученного счётчика операции. Это очень просто может быть сделано через просмотр таблицы. Эта таблица, заполненная в процессе идентификации системы, может требовать бит (приблизительно 5Мб для О-ПУКТ с параметром ).

Благодарност

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

Приложение A: как реализовать F на практике?

В АНИС X9.24 описанное применение ПУКТ предполагает получение 112-битных TDES ключей (128-битные ключи с 8-битным опознавателем). Поэтому сама функция основана на TDES. Получаемый 128-битный ключ (первый ввод) делится на две 64-битные части и , а новый ключ произведён с помощью

где является известной величиной, зависящей от счётчика (второй ввод), а –фиксированная постоянная. Затем опознаваемые биты и упорядочиваются.

В качестве функции мы советуем использовать обычно применяемые алгоритмы MAC такие, как CBC-MAC или HMAC с вводимыми MAC-ключами и с операционным вводом, как ввод сообщения MAC.

Контакты авторов материала

  1. Ingenico, France, E-mail: forename.name@ingenico.com
  2. Ingenico, France, E-mail: forename.name@ingenico.com

Литература

  1. Bellare, M.: New Proofs for NMAC and HMAC: Security Without Collision- Resistance. Cryptology ePrint Archive, Report 2006/043 (2006), http://eprint.iacr.org/
  2. Bellare, M., Kilian, J., Rogaway, P.: The Security of Cipher Block Chaining. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 341–355. Springer, Hei- delberg (1994)
  3. Canetti, R., Halevi, S., Katz, J.: A Forward-Secure Public-Key Encryption Scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 255–271. Springer, Heidelberg (2003)
  4. Brier, E., Peyrin, T., Stern, J.: BPS: a Format Preserving Encryption Proposal. NIST submission (April 2010), http://csrc.nist.gov/groups/ST/toolkit/BCM/modes_development.html
  5. American National Standards Institute. ISO 9564-1:2002 Banking – Personal Iden- tification Number (PIN) management and security – Part 1: Basic principles and requirements for online PIN handling in ATM and POS systems (2002)
  6. American National Standards Institute. ANSI X9.8-1:2003 Banking - Personal Identification Number Management and Security - Part 1: PIN protection prin- ciples and techniques for online PIN verification in ATM and POS systems (2003)
  7. American National Standards Institute. ANSI X9.24-1:2009 Retail Financial Ser- vices Symmetric Key Management Part 1: Using Symmetric Techniques (2009)
  8. Kocher, P.C.: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp.104–113. Springer, Heidelberg (1996)
  9. Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
  10. Bellare, M., Rogaway, P., Spies, T.: Format-preserving Feistel-based Encryption Mode. NIST submission (April 2010), http://csrc.nist.gov/groups/ST/toolkit/BCM/modes_development.html
  11. NIST. FIPS 198 – The Keyed-Hash Message Authentication Code, HMAC (2002) 12. National Institute of Standards and Technology. SP800-67: Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher (May 2004), http://csrc.nist.gov
  12. Quisquater, J.-J., Samyde, D.: ElectroMagnetic Analysis (EMA): Measures and Counter-Measures for Smart Cards. In: E-smart, pp. 200–210 (2001)