Пособие «Защита информации» (МФТИ)

η16

η15

η4

η3

η2

η1

ψ

...

η13

Рис. 7 Функция ψ перемешивающего преобразования

Замечание 3 Функция ψ перемешивающего преобразования не удовлетворяет следующим локальным критериям:

−0-1 сбалансированности (гарантирует, что выходы функции будут 0 или 1 с вероятностью 0,5 когда вход функции выбирается случайно и равновероятно над всеми возможными векторами);

−большой нелинейности (Функция f называется линейной функцией, если f имеет

вид f (xn , xn−1, …, x1 )= an xn an−1xn−1 … a1x1 a0 , где ai GF (2); Если обратить внимание на вид функции ψ, то очевидно, что это линейная функция);

−строгому лавинному критерию (Strict Avalanche Criterion, SAC) (говорят, что f удовлетворяет строгому лавинному критерию, если для каждого 1≤i ≤n,

дополнение xi даст в результате выход f являющийся дополнением для 50% всех возможных входных векторов).

Кроме этого в перемешивающем преобразовании применяется только одна функция ψ, а следовательно оно не обладает следующими общими свойствами:

−линейной неэквивалентности структуры (две функции f и g линейно эквивалентны по структуре, если f можно преобразовать в g линейным

преобразованием координат и дополнениями функций, т.е имеется неособенная n×n матрица A над GF (2) а также вектор B Vn такой что f (xA B)= g (x), или f (xA B) 1= g (x), где x =(xn , xn−1, …, x1 ); этот критерий гарантирует, что функции используемые криптографическим алгоритмом не обладают схожестью структуры);

−взаимной некоррелированности выходов (функции f и взаимно некоррелированы по выходу, если f , g и f g - 0-1 сбалансированные нелинейные функции; гарантирует, что последовательности функций не будут взаимно коррелированны

или через линейные функции, или через смещение в выходных битах). Остается вопрос, из каких критериев исходили конструктора?

Учебный центр “Информзащита”

6

50

б) Подпрограмма генерирования ключей

Данная подпрограмма использует следующие функции и константы: − Константы

C2 ,C4 = {0}256 , C3 = 0xf 0 ff 000 ff 00 f 0 ff 00 f 0 f 0 f 0 ff 0 f 0 f 0 f 0.

− Функции

o P : {01}256 →{01}256 . Пусть X = ξ32 || ξ31 ||

|| ξ1, тогда

P

(

X

)

= ξ

|| ξ

||

|| ξ

, где ϕ i +1+ 4

(

k −1

= 8i + k, i =

0,3, k =1,8.

ϕ(32)

ϕ(31)

ϕ(1)

(

))

oA : {01}256 →{01}256 . Пусть X = x4 || x3 || x2 || x1, тогда

A(X )=(x1 x2 )|| x4 || x3 || x2.

Алгоритм 1 Подпрограмма генерирования ключей

1.U ←mi , V ←hi−1, W ←U V , K1 ← P(W )

2.Для j от 2 от 4 выполняем следующее:

2.1.U ← A(U ) Cj , V ← A(A(V )), W ←U V , K j ← P(W )

3.Выход (K1, K2 , K3 , K4 )

в) Шифрующее преобразование

Основным функциональным предназначением является получение si из hi−1 . Пусть

h

= h4

|| h3

|| h2

|| h1

, где h j

01

64 ,

j =

а s = s4

|| s3

|| s2

|| s1

, где

1, 4,

i−1

i−1

i−1

i−1

i−1

i−1

{ }

i

i

i

i

i

s j

01 64 ,

j =

. Тогда

1, 4

i

{ }

sij ← EK j (hi−j 1 ),

где j =

, EK - шифрование по ГОСТ 28147 – 89 в режиме простой замены.

1, 4

Схематически это изображено на Рис. 8.

h4

h3

h2

h1

i−1

i−1

i−1

i−1

K4

E

K3

E

K2

E

K1

E

si4

si3

si2

s1

i

Рис. 8 Шифрующее преобразование

Замечание 4 Как видно s

= s4 || s3

|| s2

|| s1

- конкатенация 64 битных слов, полученных в

i

i

i

i

i

результате шифрования. Следовательно, в свете замечания 3, si можно было бы атаковать по частям, но это предотвращается казуальным генерированием ключей (в данном случае mi и hi−1 выступают в роли ключа для выведения ключей).

Замечание 5 (S-блоки при шифровании в режиме простой замены) Согласно стандарта ГОСТ 28147 – 89 S-блоки не определены, но указано, что они должны назначаться вышестоящим органом. Следовательно они должны учитываться как данные инициализации функции хэширования, и в определенной степени влияют на ее свойства.

Учебный центр “Информзащита”

7

51

2. Функция сжатия финальной итерации

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

и длины сообщения в битах приведенной по mod 2256 :

									m′×h	×Σ ×L	→ h ,
									l l−1	l l	итог
′	,Σ	, L		{	01	256	,	′	- последний набитый нулями блок (если необходимо, см.
где m , h								m
l l−1	l	l			}			l

Рис. 3). Сначала вычисляется битовая длина последнего (ненабитого) блока сообщения ml ≤256 бит. Если ml < 256 , то производится его набивка справа нулями до

достижения длины 256 бит и получается новый блок ml′←{0}256−ml ml . Вычисляются итоговая контрольная сумма Σl ←Σl−1 ml′ и длина всего сообщения

Ll ← Ll−1 + m′ (mod 2256 ). Параллельно выполняется последняя итерация

hl ←χ(m′, hl−1 ). Затем вычисляются перемешивающие преобразования hl+1 ←χ(Ll , hl )

и hитог ←χ(Σl , hl+1 ), давая в результате итоговую хэш величину hитог . Теперь дадим формальное описание алгоритма:

Алгоритм 2 Вычисление хэш функции по ГОСТ Р 34.11 – 94

Вход: двоичное сообщение M , блоки замен для шифрования в режиме простой замены по ГОСТ 28147-89, начальный вектор IV {01}256

Выход: хэш величина hитог для сообщения M .

1. Инициализация алгоритма h ← IV ,Σ←{0}256 , L ←{0}256 .

2.Функция сжатия внутренних итераций Пока M > 256 выполняем следующее:

2.1.h ←χ(ms , h)(итерация метода последовательного хэширования),

2.2.L ← L + 256(mod 2256 ) (итерация вычисления длины сообщения),

2.3.Σ←Σ ms (итерация вычисления контрольной суммы).

3.Иначе (функция сжатия финальной итерации)

3.1.L ← L + m (mod 2256 ) (вычисление полной длины сообщения),

3.2.m′←{0}256−m m (набивка последнего блока),

3.3.Σ←Σ m′ (вычисление контрольной суммы сообщения),

3.4.h ←χ(m′, h),

3.5.h ←χ(L, h) (MD - усиление),

3.6.hитог ←χ(Σ, h).

4.Выход ( hитог )

Учебный центр “Информзащита”

8

52

Заключение Из приведенного выше описания хэш функции по ГОСТ Р 34.11 – 94 можно сделать следующие выводы:

−Булева функция перемешивающего преобразования линейна и ее применение неоправданно – это приводит к снижению скорости обработки данных из-за большого числа повторений перемешивающего преобразования для достижения “заданного” уровня безопасности (в первую очередь SAC);

−Шифрующее преобразование, при определенных допущениях, невозможно атаковать по частям, а, следовательно, функцию сжатия можно считать стойкой к столкновениям (CRHF);

−Алгоритм хэширования является методом последовательного хэширования с MD – усилением (коэффициент сжатия 2);

−Используется постериорное форматирование сообщения;

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

−IV в стандарте не фиксирован, а это подразумевает, что необходимо выработать правила его использования (см. Замечание 2), к тому же имеется большой класс атак на псевдостолкновения при не фиксированном IV [3];

−скорость обработки данных хэш функцией значительно меньше чем у аналогичных по внешним параметрам HAVAL, SHA-256, а тем более остального MD-семейства, из-за попыток ликвидировать очевидные оплошности конструирования усложнением функции сжатия;

−приблизительная скорость реализации 4/5 от скорости реализации лежащего в основе алгоритма шифрования;

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

−нет обоснования выбора конструкции, функций, констант.

1.ГОСТ Р 34.11 – 94. "Информационная технология. Криптографическая защита информации. Функция хэширования".

2.M. Bellare, R. Canetti, and H. Krawczyk. Keying hash functions for message authentication. Advances in Cryptology - Crypto 96 Proceedings, Lecture Notes in Computer Science Vol. 1109, N. Koblitz ed, Springer-Verlag, 1996.

3.Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone Handbook of Applied Cryptography CRC Press ISBN: 0-8493-8523-7 October 1997, 816 pages

Учебный центр “Информзащита”

9

53

22.2 Протокол "точка-точка"

Обмен ключами Diffie-Hellman чувствителен к вскрытию "человек в середине" . Одним из способов предотвратить это, является необходимость для Алисы и Боба подписывать сообщения, которые они посылают друг другу [500].

Этот протокол предполагает, что у Алисы есть сертифицированный открытый ключ Боба, а у Боба есть се р- тифицированный открытый ключ Алисы . Эти сертификаты подписаны некоторым заслуживающим доверия органом власти, непосредственно не участвующим в протоколе . Вот как Алиса и Боб генерируют секретный ключ k.

(1)Алиса генерирует случайное число x и посылает его Бобу.

(2)Боб генерирует случайное число y. Используя протокол Diffie-Hellman, он вычисляет общий ключ k на базе x и y. Он подписывает x и y и шифрует подпись ключом k. Затем он посылает получившееся вместе с y Алисе.

y,Ek(SB(x,y))

(3)Алиса также вычисляет k. Она расшифровывает оставшуюся часть сообщения Боба и проверяет его подпись. Затем она посылает Бобу подписанное сообщение, состоящее из x и y, зашифрованных общим клю- чом k.

Ek(SA(x,y))

(4)Боб расшифровывает сообщение и проверяет подпись Алисы.

22.3 Трехпроходный протокол Шамира

Этот изобретенный Ади Шамиром но никогда не опубликованный протокол позволяет Алисе и Бобу безопасно обмениваться информацией, не используя предварительного обмена ни секретными, ни открытыми кл ю- чами [1008]. Он предполагает использование коммутативного симметричного шифра , для которого:

EA(EB(P)) = EB(EA(P))

Секретный ключ Алисы - A, а Боба - B. Алиса хочет послать сообщение M Бобу. Вто этот протокол.

(1)Алиса шифрует M своим ключом и посылает его Бобу

C1 = EA(M)

(2)Боб шифрует C1 своим ключом и посылает Алисе C2 = EB(EA(M))

(3)Алиса расшифровывает C2 своим ключом и посылает Бобу C3 = DA(EB(EA(M))) = DA(EA(EB(M))) = EB(M)

(4)Боб расшифровывает C3 своим ключом, получая M.

Коммутативны и обладают совершенной безопасностью одноразовые блокноты, но с этим протоколом они работать не будут. При использовании одноразового блокнота три шифротекста будут выглядеть следующим образом be:

C1 = M A

C2 = M A B

C3 = M B

Ева, записав эти три сообщения, которыми обмениваются Алиса и Боб, просто выполнит XOR всех этих шифротекстов и восстановит сообщение:

C1 C2 C3 =(M A) (M A B) (M B) = M

Очевидно, что такой способ работать не будет .

Шамир (и независимо Джим Омура (Jim Omura)) описал похожий на RSA алгоритм шифрования, который будет работать с этим протоколом. Пусть p будет большим большим простым числом, причем множитель p-1 является большим простым. Выберем ключ шифрования e, взаимно простой с p-1. Вычислим d, для которого выполняется de = 1 (mod p - 1). Для шифрования сообщения вычисляем

C = Me mod p

54

Для дешифрирования сообщения вычисляем

M = Cd mod p

По видимому, у Евы нет способа получить M, не решив проблему дискретного логарифма, но это никогда не было доказано.

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

(1)Алиса запрашивает у Боба (или у KDC) его открытый ключ.

(2)Боб (или KDC) посылает Алисе свой открытый ключ.

(3)Алиса шифрует M открытым ключом Боба и посылает его Бобу.

Трехпроходный алгоритм Шамира не может устоять перед вскрытием "человек в середине" .

22.4 COMSET

COMSET (COMmunications SETup, установление связи) это протокол одновременной идентификации и о б- мена ключом, разработанный для проекта RIPE [1305] (см. раздел 25.7). С помощью криптографии с открытыми ключами он позволяет Алисе и Бобу идентифицировать друг друга, при этом обмениваясь секретным кл ю- чом.

Математической основой COMSET служит схема Rabin [1283] (см. раздел 19.5). Сама схема впервые была предложена в [224]. См. подробности в [1305].

22.5 Обмен зашифрованными ключами

Протокол обмена зашифрованными ключами (Encrypted Key Exchange, EKE) был разработан Стивом Белловином (Steve Bellovin) и Майклом Мерриттом (Michael Merritt) [109]. Он обеспечивает безопасность и проверку подлинности в компьютерных сетях , по новому используя и симметричную криптографию, и криптогр а- фию с открытыми ключами: общий секретный ключ используется для шифрования генерированного случа й- ным образом открытого ключа.

Базовый протокол EKE

Алиса и Боб (два пользователя, клиент и сервер, или кто угодно) имеют общий пароль P. Используя следующий протокол, они могут проверить подлинность друг друга и генерировать общий сеансовый ключ K.

(1)Алиса Случайным образом генерирует пару "открытый ключ/закрытый ключ" . Она шифрует открытый ключ K' с помощью симметричного алгоритма, используя P в качестве ключа: EP(K'). Она посылает Бобу

A, EP(K')

(2)Боб знает P. Он расшифровывает сообщение, получая K'. Затем он генерирует случайный сеансовый ключ K шифрует его открытым ключом, который он получил от Алисы, а затем используя P качестве ключа. Он посылает Алисе

EP(EK'(K)

(3)Алиса расшифровывает сообщение, получая K. Она генерирует случайную строку RA, шифрует ее с помощью K и посылает Бобу

EK(RA)

(4)Боб расшифровывает сообщение, получая RA. Он генерирует другую случайную строку, RB, шифрует обе строки ключом K и посылает Алисе результат.

EK(RA,RB)

(5)Алиса расшифровывает сообщение, получая RA è RB. Если строка RA, полученная от Боба, - это та самая строка, которую она послала Бобу на этапе (3), она, используя K, шифрует RB и посылает ее Бобу.

EK(RB)

(6)Боб расшифровывает сообщение, получая RB. Если строка RB, полученная от Алисы, - это та самая строка, которую он послал ей на этапе (4), завершен. Теперь обе стороны могут обмениваться информацией, и с- пользуя K в качестве сеансового ключа.

55

Протокол Нидхэма-Шрёдера

Протокол Нидхэма-Шрёдера предназначен для решения проблемы аутентификации (см.,

например, http://www.cs.sunysb.edu/~zhaoming/np.html, http://dimacs.rutgers.edu/Workshops/Security/program2/boyd/node14.html, а также [1]).

Протоколу уже более 20 лет. Алгоритм предназначен для организации аутентифицированного канала между разными ЭВМ в сети по схеме точка-точка. Задача решается с помощью одного или двух серверов аутентификации с использованием общедоступных или общих секретных ключей. Данный протокол предоставляет децентрализованную услугу аутентификации.

Операция аутентификации может охватывать несколько процессов.

1.Установление виртуального канала двунаправленного обмена сообщениями между двумя субъектами, работающими на разных ЭВМ.

2.Установление однонаправленного обмена, который, например, имеет место при отправке почты. Здесь ситуация осложняется тем, что субъекты могут не быть одновременно доступны через сеть и не могут непосредственно обмениваться сообщениями.

3.Коммуникация, при которой источник информации и ее целостность может гарантироваться третей стороной.

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

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

При схеме шифрования с одним ключом, предполагается, что секретный ключ известен обоим субъектам обмена (А и В) и серверу аутентификации. Инициатором обмена будем считать субъекта А. Сообщения, посылаемые от А к В, могут быть дешифрованы только В и субъект В должен быть уверен, что сообщение пришло именно от А. В начале предположим, что оба субъекта находятся в области действия общего сервера аутентификации (AS). AS знает секретные ключи субъектов А и В (KA и KB, соответственно).

Обмен начинается с того, что субъект А генерирует свой идентификатор IA1, который будет использоваться только один раз. Первое сообщение, посылаемое от A к AS, содержит:

A→ AS:

(A, B, IA1)

(1)

56

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

		A→ AS:			(A, B, IA1)KA		(1.1)

Получив это сообщение AS , извлекает из базы данных секретные ключи KA и KB, а также вычисляет новый ключ CK (ключ сессии), который будет использован для осуществления процедуры аутентификации. Этот новый ключ должен быть непредсказуемым, он используется только для одной операции аутентификации.

Далее AS посылает субъекту А следующее сообщение:

AS→ A:		(IA1, B, CK, {CK, A}KB)KA		(1.2)

Верхний индекс в данном выражении означает, что содержимое в скобках зашифровано с использованием ключа-индекса. КА и КВ – секретные ключи субъектов А и В, соответственно.

Так как выражение (IA1, B, CK, {CK, A}KB) зашифровано ключом КА, то только субъект А может его дешифровать и прочесть. Субъект А проверяет наличие идентификатора IA1 (это подтверждает то, что данное сообщение является откликом на сообщение А), и имени субъекта, с которым А намерен обмениваться данными (В). В результате дешифровки сообщения от AS А получает во владение рабочий ключ СК. Наличие В в сообщение является обязательным. В противном случае злоумышленник может заменить В на, например, Х в сообщении (1), и в дальнейшем А будет взаимодействовать с Х а не с В, сам того не подозревая. Заметим, что часть текста {CK, A}KB субъект А прочесть не может.

Если все прошло нормально, субъект А посылает В следующее сообщение:

A→ B:		{CK, A}KB

Нетрудно видеть, что содержимое {CK, A}KB является частью сообщения, полученного от AS. Дешифровать это послание может только субъект В, так как оно зашифровано его секретным ключом. После дешифровки В также становится владельцем ключа сессии CK. Наличие А в сообщении подтверждает факт, что код получен именно от данного субъекта. Все обмены между А и В далее будут выполняться с использованием ключа шифрования СK. Чтобы сделать схему симметричной и уменьшить вероятность атаки воспроизведения, В следует послать А свой идентификатор:

B→ A:		{IB}CK

зашифрованный ключом СК. При этом ожидается отклик:

A→ B:		{IB-1}CK

57

Таким образом, в данной версии протокола используется 5 сообщений. Злоумышленник не может имитировать такой обмен, так как не владеет ключом CK. Это число для регулярно взаимодействующих партнеров можно сократить до трех, убрав обмен сообщениями 1.1 и 1.2. При этом ключ СК будет использоваться многократно. Здесь желательно заменить обмены 1.3 и 1.4 на:

A→ B: {CK, A}KB, {IA2}CK

B→ A:		{IA2 –1, IB}CK

Теперь рассмотрим вариант протокола для случая асимметричного шифрования (двух ключевая схема).

Предполагается, что субъекты А и В вычислили пары ключей (PKA-SKA) и (PKB-SKB), соответственно. Имена ключей, начинающиеся с буквы P, относятся к общедоступным ключам (public), а имена, начинающиеся с буквы S, - к секретным. Инициатором, как и в предыдущем случае, будем считать субъект А. Обмен начинается с посылки AS запроса открытого ключа В (PKB).

A→ AS:		(A, B)
AS откликнется сообщением:
AS→ A:		(PKB, B)SKAS			(2.2)

Сообщение зашифровано секретным ключом AS (SKAS). Открытый ключ AS (PKAS) предполагается А известным, что позволяет А успешно дешифровать данное сообщение. Здесь предполагается, что подмена ключей (SKAS-PKAS) злоумышленникомпосредником невозможна.

Шифрование данных с использованием ключа SKAS не гарантирует конфиденциальности, но исключает модификацию сообщения по дороге (ведь никто посторонний не знает ключ SKAS). Важно, чтобы субъект А был уверен, что он получил именно PKB, а не что-то иное. Следующим шагом будет посылка сообщения от А к В:

A→ B:		{IA, A}PKB

Это сообщение может быть дешифровано только субъектом В. Смысл его заключается в том, что А уведомляет В о намерении установить с ним связь, и передает ему свой одноразовый идентификатор IA. Далее В запрашивает у AS открытый ключ А:

B→ AS:		B, A
AS→ B:		{PKA, A}SKAS

58

После этого производится взаимная аутентификация субъектов, завершающая сессию, для чего посылаются сообщения:

B→ A:		{IA, IB}PKA
A→ B:		{ IB }PKB

Таким образом, в этом варианте аутентификация потребовала семи шагов, но 4 из них (2.1, 2.2, 2.4 и 2.5) могут быть устранены, если партнеры помнят общедоступные ключи друг друга. В этом случае схема становится эквивалентной приведенной выше версии с симметричным шифрованием.

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

{{сообщение}SKA}SKB.

В реальной жизни субъекты не всегда могут находиться в пределах зоны ответственности одного общего сервера аутентификации. По этой причине в общем случае каждый из субъектов может иметь свой сервер аутентификации (ASA и ASB). Так как и в этом варианте перед субъектом А стоит задача сформировать для В сообщение типа {CK, A}KB (шаг 1.3). В вычисление таких выражений будут вовлечены оба сервера, так как только ASA может шифровать объекты посредством ключа КА, и только ASB может воспользоваться ключом КВ. Не исключается необходимость обеспечения безопасного обмена между AS. Примерами такого обмена могут служить операции, завершающие сессию аутентификации:

ASA→ ASB:				(CK, A, B, IA1)		(1.11)
ASB→ ASA:				(CK, A)KB, IA1, A		(1.12)

IA1 передается для того, чтобы сохранить состояние ASA между сообщениями 1.11 и 1.12.

При работе с открытыми ключами возможно непосредственное обращение А к ASB, если субъект А владеет общедоступным ключом PKASB. По минимуму аутентификация при асимметричной схеме шифрования требует пересылки трех сообщений.

Протокол Нидхэма-Шрёдера пригоден и для работы с электронными подписями. Электронная подпись, как обычно, формируется на основе дайджеста D (например, MD5) пересылаемого документа. Сначала рассмотрим вариант с традиционной схемой шифрования. Субъект А начинает передачу с посылки AS сообщения:

	A→ AS:				(A, {D}KA)
	AS откликается, послав:
	AS→ A:				{A, D}KAS

59