Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

KEY CRYPTOGRAPHIC PROTOCOLS FOR SHARED MEMORY, AND TRANSPORT PROTOCOL. MONITOR THE INTEGRITY OF THE DYNAMIC SHARED MEMORY BETWEEN SENDER AND RECEIVER IN A IN A SYMMETRICAL CRYPTOGRAPHIC CHANNEL

Aleksandrov A.V. 1 Sorokin I.I. 1
1 Vladimir State University
The article is devoted to the description of key and transport cryptographic protocols developed for cryptographic systems using shared memory of the Sender (A) and Receiver (B) in the cryptographic symmetric channel of secret communication. The proposed bilateral protocols cover the following tasks: creation of a symmetric key (key protocols), message exchange protocol (transport protocols), protocol of remote control of the shared memory integrity based on the use of Damgard – Merkle hash tree technique using the transport protocol. Two variants of the key generation protocols are proposed – trustworthy and verifiable, differing in the degree of trust between the Sender (A) and Receiver (B). The developed protocols are sufficiently stable against enemy MITM-attacks in the communication channel. With the use of the design of Damgard – Merkle hash trees, there is a fundamental possibility of specifying different values of the shared memory with the help of Merkel’s proof procedure. It is indicated that with the introduction of a dynamic component in the shared memory, it is possible to eliminate the traditionally complex problem of symmetric cryptography: the transfer of a symmetric session key from the Sender (A) to the Receiver (B), or the creation of a symmetric key as a result of playback of a confidential protocol, in a sense analogous to the Diffie-Hellman protocol.
cryptographic protocol
shared memory
dynamic shared memory
Diffie-Hellman protocol
hash function
Damgard-Merkle tree
Merkle proof

В статье [1] представлены некоторые результаты по использованию общей памяти в криптографических протоколах, использующих симметричное шифрование, и, в частности, показано, что общую память отправителя и получателя можно использовать для противодействия MITM-атакам противника в канале связи. Метод применения общей памяти в криптографических протоколах сравнительно нов, поскольку выводит за пределы модели секретной связи К. Шеннона, и идеологию открытого распределения ключей. Однако использование ОП памяти не противоречит криптографической модели угроз Долева-Яо (1976 г.), в которой противник не имеет доступа к устройствам, принадлежащим отправителю и получателю. В работе [1] также отмечено, что общий подход использования общей памяти и соответствующие протоколы – нуждаются в проработке и детализации.

Воспроизведенный в [1] протокол создания симметричного ключа на основе предварительного здесь мы называем доверительным. Такой протокол в потенциале своего использования может оказаться слаб по отношению к Получателю – В-лгуну – участнику протокола, меняющего корректные данные протокола и заинтересованного в корректном завершении его работы. Кроме того, В-лгун может входить в сговор с противником в канале связи, становясь более опасным, чем сам противник. Для закрытия подобной слабости здесь мы приводим проверяемый ключевой протокол, по своей симметрии похожий на протокол Диффи – Хеллмана, встроенного в TLS протоколы [2]. Проверяемый протокол, в отличие от протокола Диффи – Хеллмана, не использует трудность дискретного логарифма, а основан на невозможности противника в канале связи получить доступ к значениям общей памяти.

Деревья Дамгарда – Меркла, которые находят широкое применение в качестве базовой основы криптовалют Bitcoin и Etherium [3] и контроля целостности больших массивов данных, мы используем для построения протоколов контроля целостности и удаленной синхронизации общей памяти.

Цель исследования: Разработка криптографического протокола передачи и создания ключа с использованием общей памяти у отправителя и получателя, а также транспортного протокола. Такой протокол планируются как альтернатива протоколу Диффи – Хеллмана и его использование в гибридных криптографических системах. Предложения по удаленному контролю целостности общей памяти на устройствах отправителя и получателя.

Общая память и определения

Повторим основные определения из предыдущей статьи [1] и работы [4], и для этого обозначим здесь и далее m > 1 размер симметричного криптографического ключа k, aleks01.wmf функции симметричного шифрования/расшифрования и пусть Hk(S) – ключевая хэш-функция, сильно сопротивляющаяся поиску коллизий.

Определение 1. Назовем общей памятью Отправителя (A) и Получателя (В) – согласованное между Отправителем и Получателем и разнесенное на устройства Отправителя и Получателя числовое множество aleks02.wmf n > 1, n < m. Верхний индекс X = {A,B} указывает, на каком устройстве располагается общая память.

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

Определение 2. На основании общей памяти создадим предварительный ключ

aleks03.wmf (1)

Сеансовый ключ генерируется по формуле

aleks04.wmf (2)

где, напомним, m – размер сеансового ключа шифрования.

Утверждение 1. Пусть aleks05.wmf n > 1, n < m – общая память, созданная на устройствах отправителя и получателя (DA = DB) в модели секретной связи К. Шеннона, E – предварительный ключ, kE – сеансовый ключ. Тогда противник С по значению предварительного ключа E ≠ 0 не может построить симметричный ключ kE. Это можно выразить в терминах условной энтропии К. Шеннона. H(S|Si): меры неопределенности значения S при условии обладания значением Si

aleks06.wmf (3)

где aleks07.wmf.

Доказательство использует технику (2-2) пороговых схем разделения секрета, для которых секретным значением является ключ kE. Долями секрета являются соответственно значения aleks08.wmf, aleks09.wmf.

В силу разбалансированности размеров долей секрета друг относительно друга, такая схема разделения секрета является неидеальной и несовершенной, но является пороговой. Из несовершенности вытекает, что противник С, перехватывая вектор E получает некоторую информацию δ о значении ключа, но недостаточную, чтобы уточнить его значение. Техника несовершенных и почти совершенных схем разделения секрета исследована, в частности, в [5].

В терминах условной энтропии К. Шеннона, понимаемой относительно вероятностных распределений для значений kE, E, D, первое равенство в (3.1) означает, что неопределенность значения ключа kE по значениям теней E, D полностью снимается. Второе соотношение, важное для противника С в канале связи, определяет меру неопределенности симметричного ключа для противника С при перехвате предварительного ключа.

Точную оценку δ в терминах формул воспроизвести достаточно сложно, так как значения общей памяти заранее не определены. Но мы можем указать максимально возможное значение δ = 1. Для этого нами построены примеры. Пусть Е – множество предварительных ключей, K – множество сеансовых ключей, которые можно получить с использованием формулы (2). Очевидно, мощность множества aleks10.wmf,
а множества aleks11.wmf, здесь исключен случай нулевого вектора. В построенных нами примерах пересечением множеств предварительных и сеансовых ключей является пустое множество.

E ∩ K = Ø. (4)

Отметим, что согласно принципу Керхгоффса в криптографии, противник сможет знать и формулу (4). Это дает ему информацию о множестве сеансовых ключей, так что при брутфорсинге симметричных ключей он может отбросить случаи ключей из интервала [1; 2m] и проводить атаку на ключи на множестве [2n + 1; 2m].

Далее, пусть распределение значений симметричных ключей из множества K – равномерно и равновероятно на [2n + 1; 2m]. В этом случае, хорошо известно, энтропийные оценки (3) принимают максимальные значения, в которых вместо условной энтропии участвует мера Хартли. Грубые оценки мер Хартли для множеств [1; 2m] и [2n + 1; 2m] дают неравенство aleks12.wmf, где случай равенства достигается для случая n = m – 1. Это завершает доказательство утверждения 1.

Из утверждения 1 следует, что неопределенность значения симметричного ключа для противника С при перехвате предварительного ключа E снимается не более чем на один бит. В работе [6] описывается лгун в схемах разделения секрета.

Доверительный ключевой и транспортный протоколы

Доверительные протоколы создания симметричного ключа и передачи сообщения уже были предложены в статье [1]. Эти протоколы мы назвали доверительными, за счет того, что одна из сторон обмена сообщениями Отправитель А или Получатель В всецело доверяет противоположной стороне. Кто-либо из них может подменить данные при передаче сообщения. В протоколе (5) все проверки, и заключение об успешности завершения работы протокола происходят на стороне Получателя В, так что он в потенциале может быть лгуном.

Доверительный протокол создания симметричного ключа безопасный по отношению к противнику в канале связи:

1. aleks13.wmf.

2. В: aleks14.wmf если aleks15.wmf,
то стоп.

3. aleks16.wmf.

4. aleks17.wmf. (5)

5. aleks18.wmf.

6. В: если aleks19.wmf, то de ← kВА,
иначе стоп.

7. aleks20.wmf.

8. A: если aleks21.wmf то de ← kAВ.

Доверительный протокол обмена сообщениями:

1. aleks22.wmf.

2. aleks23.wmf. (6)

3. B: если aleks24.wmf то Ok.

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

Протоколы (5), (6) эффективно противостоят MITM-атаке за счет использования ключевой хэш-функции aleks25.wmf с ключом de – предыдущим сгенерированным сеансовым ключом. Активный противник, вмешиваясь в процесс передачи сообщений, может лишь портить пересылаемые данные, при этом Отправитель и Получатель на этапах (5.6) и (6.3) определят факт подмены сообщения.

Протокол (6) назовем транспортным протоколом, а фраза ТРАНСП(S) означает передачу сообщения S с помощью этого протокола.

Проверяемый ключевой протокол

Определение 3. Лгуном в протоколе называем законного участника протокола, заинтересованного в подмене данных в рамках действия протокола и корректном завершении работы протокола. Протоколы с лгунами естественным образом возникают в протоколах схем разделения секрета и впервые рассматривались в работе [7].

В предыдущих протоколах предполагается, что отправитель А выступает в роли «дилера» ключа, так как он генерирует предварительный ключ. В свою очередь получатель В осуществляет все сравнения хэш-значений в протоколах и ему же принадлежит роль определения корректности завершения работы протоколов (5), (6). Роли А и В в протоколах неравноправны и основаны на значительном доверии А к В и соответственно В к А. Поэтому представленные выше протоколы мы можем назвать доверительными. В отличие от противника С, В-лгун имеет доступ к общей памяти D, что позволяет ему строить ключ kBA = kAB, а также знает ключ de и может получить aleks26.wmf. Для противодействия В-лгуну необходимы усиления приведенных протоколов в виде двусторонних проверок передаваемой информации. Этим достигается определенная симметрия доверия А и В так, как это происходит в протоколе Диффи – Хеллмана:

1. aleks27.wmf.

2. aleks28.wmf. (7)

3. aleks29.wmf.

4. aleks30.wmf.

Как можно заметить, в (7) протоколе доверие между А и В критично, и в случае обмана одного из участников обмена сообщениями, общий ключ на шаге 4 корректно выработан не будет Протокол в определенном смысле симметричен по отношению доверительности участников протокола.

Обозначим ⊕ – оператор поразрядного сложения исключающего ИЛИ. Приведем проверяемый протокол, аналог протокола (7), устойчивый к атакам В-лгуна:

1. aleks31.wmf.

2. B: aleks32.wmf если aleks33.wmf,
то стоп.

3. aleks34.wmf.

4. aleks35.wmf. (8)

5. aleks36.wmf.

6. B: если aleks37.wmf, то OK1, иначе стоп.

7. aleks38.wmf. (9)

8. A: Если aleks39.wmf то aleks40.wmf, иначе стоп.

9. A: запрашивает aleks41.wmf.

10. aleks42.wmf.

11. aleks43.wmf.

12. A: Если aleks44.wmf то de ← kBA, иначе стоп.

13. aleks46.wmf.

14. A: Если aleks47.wmf то de ← kBA, иначе стоп.

Утверждение 2. Пусть aleks49.wmf сильно сопротивляется поиску коллизий, тогда в проверяемом ключевом протоколе ни А, ни В не могут быть лгунами без их обнаружения на другой стороне.

Динамическая общая память.
Контроль целостности общей памяти

Обозначим дерево Дамгарда – Меркла DMX, построенное над общей памятью соответственно Отправителя для X = A и Получателя для X = B. Свойства этих деревьев хорошо известны и использованы в работе [1] для определения целостности общей памяти на устройствах А и В.

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

Для контроля целостности общей памяти Отправителя и Получателя предлагается использовать следующий протокол:

1. B: запрашивает Root_Hash(A).

2. A → B: ТРАНСП (aleks50.wmf (Root_Hash(A)).

3. B: сравнивает полученный Root_Hash(A) со своим Root_Hash(B). (10)

3.1. B: если Root_Hash(A) = Root_Hash(B),
то OK (Shared_Memory(A) = Shared_Memory(B));

3.2. B: если Root_Hash(A) ≠ Root_Hash(B), то применяем ДОКАЗАТЕЛЬСТВО_МЕРКЛА (Shared_Memory(A) ≠ Shared_Memory(B)).

Протокол либо успешно завершает работу на этапе (3.1), когда корневые хэши Отправителя и Получателя равны, а значит и общая память в целом у них совпадает, либо на этапе (3.2) запускаем протокол доказательства Меркла, так как корневые хэши не совпадают, следовательно, общая память у Отправителя и Получателя различна.

ДОКАЗАТЕЛЬСТВО_МЕРКЛА:

1. B запрашивает хэши всех элементов общей памяти.

2. A → B: ТРАНСП (aleks51.wmf (Shared_Memory(A)[i])).

3. B: сравнивает полученный хэш aleks52.wmf (Shared_Memory(A)[i]) со своим aleks53.wmf (Shared_Memory(A)[i]). (11)

3.1. B: если aleks54.wmf (Shared_Memory(A)[i]) =
= aleks55.wmf (Shared_Memory(A)[i]), то обращаемся к следующему элементу общей памяти;

3.2. B: если aleks56.wmf (Shared_Memory(A [i]) ≠
aleks57.wmf (Shared_Memory(A)[i]) зануляем бит в предварительном ключе, соответствующий несовпадающему элементу памяти.

Проигрывание протоколов (10), (11) позволяет удаленно синхронизировать общую память на устройствах А и B. Сначала применяется протокол, который дает понять, нарушена ли целостность памяти (10). Если не нарушена – то достаточно только применения протокола (10), в противном случае – после протокола (10) применяем протокол (11) для игнорирования несовпадающих элементов общей памяти предварительным ключом, зануляя соответствующую компоненту предварительного ключа.

Динамическая общая память

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

aleks58.wmf (12)

где di – элемент общей памяти;

S – успешно переданное последнее сообщение.

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

Пусть размер симметричного ключа шифрования m = 128. Количество элементов общей памяти n = 40.

Общая память D = {80, 65, 33, 86, 35, 22, 49, 95, 86, 33, 25, 80, 27, 68, 8, 44, 69, 28, 65, 21, 91, 2, 34, 74, 74, 35, 67, 1, 37, 72, 8, 93, 66, 43, 60, 66, 14, 15, 36, 60}.

В данном примере первые 30 элементов (d1…d30) общей памяти постоянны и в статье [1] эту область памяти мы назвали статической компонентой, а последние
10 ({d31…d40} или {8, 93, 66, 43, 60, 66, 14, 15, 36, 60}) – динамической компонентой, имеющей структуру – очередь.

Предварительный ключ E = 1011000101111001011011011100001010100110. Получим сеансовый ключ на основании имеющихся данных по формуле (2): k = 1057.

Передадим с использованием транспортного протокола сообщение S = «101» и изменим общую память согласно (12). Динамическая компонента принимает следующий вид: {101, 8, 93, 66, 43, 60, 66, 14, 15, 36}.

Структура общей памяти изменится в соответствии с формулой (12).

Измененная общая память D' = {80, 65, 33, 86, 35, 22, 49, 95, 86, 33, 25, 80, 27, 68, 8, 44, 69, 28, 65, 21, 91, 2, 34, 74, 74, 35, 67, 1, 37, 72, 101, 8, 93, 66, 43, 60, 66, 14, 15, 36}.

Таким образом, у нас изменилась общая память, предварительный ключ остался прежним, следовательно, и мы имеем согласованное изменение значений сеансового ключа (2): k = 1138 на устройствах Отправителя и Получателя.

Заключение

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

Использование динамической общей памяти (12) снимает одну из традиционных и трудных проблем симметричной криптографии – безопасную передачу и/или создание симметричного ключа по двустороннему криптографическому протоколу, заменяя проблему передачи/создания синхронным преобразованием общей памяти на двух устройствах. Однако здесь возникает следующая важная задача – постоянное поддержание целостности общей памяти на устройствах Отправителя и Получателя, для чего предлагается использовать протоколы (10), (11).

Благодаря протоколам (10), (11) мы можем удаленно контролировать общую память у Отправителя А и Получателя В. Протокол (10) позволяет определить, совпадает ли общая память на устройствах А и В, а протокол (11) – избавиться от несовпадающих элементов при создании предварительного ключа.

Работа выполнена при поддержке и финансировании Российского фонда фундаментальных исследований, грант № 18-01-00596А.