Scientific journal

Modern high technologies

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

Один из первых двусторонних протоколов открытого распределения ключей предложен в 1976 г. У. Диффи, М. Хеллманом. Протокол основан на трудности решения задачи дискретного логарифма в мультипликативной группе большого порядка с образующей α.

1. A→B: α^x mod p

2. B→A: α^y mod p (DH)

3. A: k_AB = ((a^y)^x) mod p

4. A: k_BA = ((a^x)^y) mod p

Несмотря на то, что задача дискретного логарифма NP-трудна, существует вариант атаки «человек посередине» активного противника (MITM), против которого DH-протокол бессилен, ввиду отсутствия в нем аутентификации сторон. Для проведения атаки противник С не обязан решать задачу дискретного логарифмирования, однако, пользуясь отсутствием аутентификации в (DH), встает посередине между A и В, представляясь для А абонентом В, для В соответственно абонентом А. Далее, не обнаруживая себя, он осуществляет подмену передаваемых значений на свои значения, не решая при этом задачу дискретного логарифма и контролируя после завершения протокола обе части разорванного канала связи между А и В.

1. A→C: α^x mod p

2. C→B: α^x mod p

3. B→C: α^y mod p

4. C→A: mod p (MITM DH)

5. A: k_AC = mod p

6. B: k_BC = mod p

7. C: k_AC = mod p

8. C: k_CB = mod p

В связи с востребованностью DH-протокола в приложениях, приведены многочисленные варианты усиления DH в направлении аутентификации сторон А и В, с относительным сохранением свойств протоколов открытого распределения колючей. Далее мы воспользуемся только описанием направлений усиления, пользуясь детальным обзором в книге [1].

Первые усиления основаны на использовании доверенного центра и введении доверенных сертификатов, связывающих участников протокола X∈{A, B} со значениями ax, ay и подписью доверенного центра SigT:

В первоначальном варианте семействе протоколов MTI [1, с. 174] без участия доверенного центра предполагается у участников протокола секретных ключей, и формулы выработки секретного ключа мультипликативно зависят от их значений. В результате MITM-атаки противника, все стороны протокола получат различные ключи, что будет обнаружено в результате чтения переданных сообщений. В последующих усилениях MTI появляется зависимость и от открытых ключей участников работы протокола.

В нашей работе в рамках модели секретной связи К. Шеннона мы предлагаем аддитивные протоколы порождения симметричного ключа и обмена данными, противодействующие атаке человек посередине. Для этого нами используется предварительно созданная Отправителем А и Получателем В и разнесенная на соответствующие устройства общая память – целочисленное множество значений D = {d1…dn}. Строго говоря, использование общей памяти выходит за рамки протоколов открытого распределения ключей, и само использование общей памяти достаточно сильно идентифицирует канал связи между абонентами А и В. Однако с учетом того, что значения общей памяти, вообще говоря, произвольны и не являются дополнительными идентификаторами, а представленные протоколы не требуют привлечения третьей доверенной стороны – арбитра, а также секретных и публичных ключей абонентов секретной связи, мы считаем, что такой подход имеет право на существование.

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

Определения

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

Определение 1: Назовем общей памятью Отправителя (A) и Получателя (В) – согласованное между Отправителем и Получателем и разнесенное на устройства Отправителя и Получателя числовое множество D = {d1…dn}, n > 1, n < m.

В качестве элементов D могут выступать файлы, расположенные на информационных носителях Отправителя А и Получателя В, и только на них. Смысл значений D = {d1…dn}, n > 1, n < m нас не интересует. После разнесения общей памяти на устройства пользователей множество D = {d1…dn}, n > 1, n < m и его элементы, если это необходимо, снабжаем индексом X∈{A, B} для того, чтобы подчеркнуть, на каком устройстве мы рассматриваем само множество и его элементы. Наличие общих элементов Отправителя А и Получателя В, конечно, выходит за рамки модели секретной связи К. Шеннона, однако не противоречит модели угроз Долев – Яо, предложенной в 1981 г. Д. Долевым и А. Яо для детального описания среды, в которой происходит обмен шифрованными сообщениями, при наличии в ней пассивного или активного противника С.

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

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

(1)

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

(2)

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

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

(3)

где .

В терминах условной энтропии Шеннона, понимаемой относительно вероятностных распределений для значений kE, E, D, первое равенство означает, что неопределенность значения ключа kE по значениям теней E, D полностью снимается. Второе соотношение определяет меру неопределенности симметричного ключа для противника С при перехвате предварительного ключа и несовершенность схемы разделения секрета следует из работы [2].

Доказательство использует технику (2,2) пороговых схем разделения секрета [2], для которых секретным значением является ключ kE. Долями секрета являются соответственно значения D, E.

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

Криптографические протоколы создания симметричного ключа и передачи данных

Пусть противник C в канале связи пассивный, перехватывает весь трафик в канале связи, но не имеет возможности подмены.

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

1.

2. (4)

3.

В силу утверждения 1 противник С не имеет возможности построить значение kBA = kAB.

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

1.

2. если , то стоп

3.

4. (5)

5.

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

7.

8. А: если Ok, то

Нетрудно видеть, что такое усиление протокола (4), в силу свойств и утверждения 1, эффективно противостоит активному противнику в канале связи. В самом деле, противник на шаге (5.1) может легко изменить вектор Е, однако не может построить функцию , так как не имеет доступа к общей памяти в модели Долев – Яо, хотя и знаком с ее описанием. В то же время абонент B, зная , легко может обнаружить факт подмены предварительного ключа E, на шаге (5.2) протокола передачи. Противник также может совершить перехват и подмену на шаге (5.5), разрушая протокол создания симметричного ключа, однако на шаге (5.6) этот факт также будет обнаружен без выработки значения OK.

При обмене сообщениями отправитель посылает получателю сообщение, зашифрованное на выработанном ключе, при этом совместно с зашифрованным сообщением отправляет хэш-функцию на выработанном ключе,

1.

2. (6)

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

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

Дерево Дамгарда – Меркла и контроль целостности общей памяти

Существует принципиальная возможность удаленного контроля целостности общей памяти отправителя и получателя, использующая технику деревьев Дамгарда – Меркла. Дерево Дамгарда – Меркла – бинарное дерево, листовыми вершинами которого являются хэш-значения от элементов общей памяти, а внутренние вершины являются результатом попарной конкатенации пар смежных хэшей на соседнем нижнем этаже бинарного дерева (рис. 1). Структура деревьев Дамгарда – Меркла предложена в работе «A Digital Signature Based on a Conventional Encryption Function» Ральфом Мерклом, и сегодня находит свое применение в контроле целостности больших массивов цифровых данных, в частности в электронных валютах стандарта Bitcoin [3].

Преимущество структур Деревьев Дамгарда – Меркла следующие:

1. Деревья Дамгарда – Меркла позволяют обеспечивать целостность и достоверность данных.

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

3. Доказательства Дамгарда – Меркла требуют малого количества информации, которая должна передаваться по сетям связи.

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

Обозначим дерево Дамгарда – Меркла RDMX(D), X = {A, B}, построенное над общей памятью соответственно Отправителя для X = A и Получателя для X = B. Представленные выше старты протоколов порождения ключа и передачи данных можно завязать на успешное сравнение мастер-хешей RootHash(RDMA(D)) = RootHash(RDMB(D)) в противном случае, проигрывается парный протокол доказательства Меркла, позволяющий выловить различия в общей памяти Отправителя и Получателя.

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

Рис. 1. Дерево Дамгарда – Меркла

Где D1…Dn – элементы общей памяти

Hash 0-0, 0-1 … N-N – листовые вершины дерева Дамгарда – Меркла

Hash 0, 1, N – вершины дерева Дамгарда – Меркла

RootHash – корневой хэш всего дерева Дамгарда – Меркла – мастер-хэ