Персоналии

Преподавание криптографии в ВУЗах имеет один существенный недостаток. Нам не преподают историю и биографии людей, делавших эту науку до нас. А это, бесспорно, является упущением!
Итак, первая порция ссылок на хотя бы краткие биографии.

Тьюринг

Шеннон

Шнайер

Диффи

Хеллман

Поллард

Пожалуй, имеет смысл немного поговорить про КП

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

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

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

Управление ключами и классификация ключей

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

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

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

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

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

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

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

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

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

Система предварительного распределения ключей должна обладать двумя свойствами:

Устойчивость - учёт возможности раскры­тия части ключей при компрометации, обмане или сговоре абонентов

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

Пересылка ключей

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

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

центры распределения ключей – самостоятельно генерируют ключи,

центры перешифрования клю­чей – генерация ключей осуществляется самими абонентами.

1. Типы систем распределения ключей

Передача ключей с использованием симметричного шифрования

Двусторонние протоколы - передача ключей осуществляется при непосредственном взаимодействии,

Протоколы с централизованным распределе­нием ключей - предусмотрена третья сторона, иг­рающая роль доверенного центра.

Двусторонние протоколы

Раз­личают протоколы, в которых стороны заранее располагают какой-либо известной им обоим секретной информацией, и протоколы, не требующие этого условия.

Пусть стороны А и В заранее обладают общей секретной информацией. Допустим, что это — секретный ключ k_АВ..

Тогда для передачи ключа k стороны могут использовать одностороннюю передачу:

А→В: E_kAB(k,t,id(B)),

где Е — алгоритм шифрования, t — метка времени, В — идентификатор абонента id(В) (для краткости вместо id(B) будем использовать лишь один символ В).

Метки времени – защита от повторной передачи сообщения.

Идентификатор адре­сата позволяет абоненту А установить, что сообщение получено именно от абонента В.

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

А→В: kh_kAB(t,B).

Если дополнительно требуется аутентификация сеанса, то можно использовать следующий протокол типа "запрос-ответ":

(1) В → А: r_B,

(2) А→В:Е_kАВ(k r_B,,В),

где r_B — случайное число, сгенерированное абонентом В и переданное абоненту А в начале сеанса. При использовании хэш-функции подобный протокол может выглядеть так:

1. B→A: r_B,

2. А→В: kh_kAB(r_B,,B).

Если требуется двусторонняя аутентификация, то можно предоставить стороне А генерацию r_А и введения его в сообщение на шаге (2) протокола.

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

Пусть абонентами А и В помимо случайных чисел r_А и r_B генерируются также случайные числа k_A и k_B соответст­венно. Тогда в результате выполнения протокола

1. В→А: r_{B ,},

2. A→B:E_kAB(k_A ,r_A , r_B ,B),

(3) В→ А: E_kAB(k_B ,r_B , r_A ,A),

каждая из сторон может вычислить общий ключ с помощью некоторой функции f по правилу k= f(k_A,k_B).

В этом протоколе ни одна из сторон не может знать зара­нее значения ключа.

"Бесключевой" протокол А.Шамира позволяет передать ключ без использования какой-либо общей секретной информации.

1. А→В:Е_kА(k),

2. В→А:Е_kB(Е_kА(k)),

3. A→B:D_kА(E_kB(E_kA(k))),

Где E - коммутирующее шифрующее преобразование. Это означает, что при всех сообщениях х и ключах k1 и k2 выполняется равенство

E_k1(E_k2(x)) = E_k2(E_k1(x)).

В протоколе Шамира рекомендуется использовать преобразование вида

Е_kА(k) = k^a mod р

, в котором константа а определяется ключом k_A.

Трехсторонние протоколы

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

Один из первых протоколов такого типа - протокол Нидхема и Шрёдера:

1. А→Т:А,В, r_A,

2. T→A: Е_kAT(r_A,B,k,Е_kBT(k,A)) ,

3. A→B: Е_kBT(k,A) ,

(4) B→А: Е_k(r_B) ,

(5) А→В:Е_k(r_B – 1) .

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

Слабость этого протокола заключается в возможности повторной передачи абоненту В сообщения, переданного на шаге (3). При этом абонент В не имеет возможности устано­вить, что полученный ключ k уже был использован. Поэтому в случае компрометации этого ключа злоумышленник может аутентифицироваться и передавать сообщения от имени А.

Недостаток этого протокола устранен в протоколе Kerberos:

(1) А→Т: А,В, r_A,

2. Т→А: Е_kAT (k, r_A,L,B), билет,

3. А→В: билет, аутентификатор,

4. В→А: E_k(t,k_B).

Здесь "билетом" названа величина Е_kBT(k,A,L), “аутентификатором” — величина E_k(A,t,k_A), t — метка времени; L — период времени действия билета, r_A— случайное число, сгенерированное абонентом А и вставленное в переда­ваемое сообщение для взаимной аутентификации, а k_A и k_B — случайные числа, сгенерированные абонентами А и В соот­ветственно, и используемые либо в качестве ключа шифрова­ния информации другой стороне, либо для выработки общего ключа k_AB = f(k_{A ,} k_B) с помощью некоторой функции f.

В полном протоколе Kerberos описанный выше базовый протокол используется два раза. Дело в том что в нем преду­смотрено два сервера (см. рис. 51). Первый — "сервер аутен­тификации", обозначаемый AS, выдает так называемые "биле­ты для получения билетов" (TGT), содержащие ключи, предна­значенные для длительного использования. Второй сервер, "сервер выдачи билетов" (TGS), выдает обычные билеты для доступа к сетевым ресурсам и обращения к другим поль­зователям.

Рис. 1

Сообщения, передаваемые согласно этому протоколу, вы­глядят следующим образом:

(1) A→AS: A, TGS ,r_А,

(2) AS→A: Е_kA,AS (k_A,TGS, r_A,L₁,TGS),

3. А → TGS: tgt, аутентификатор₁, B , r_A`,

4. TGS→A: Е_kA,TGS (k, r_A`,L₂,B), билет,

5. А→В: билет, аутентификатор₂,

6. В→А: E_k(t₂,k_B),

где

tgt = Е_kA,TGS (k_A,TGS,A,L₁),

аутентификатор₁ = Е_kA,TGS (A,t₁),

билет = Е_kB,TGS (k,A,L₂),

аутентификатор₂ =Е_k(A,t₂,k_A).

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

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

(1) А→В:r,А,В, Е_kAT(r_A,r,A,B),

(2) В→Т. r,A,B,E_kAT(r_A,r,A,B),E_kBT(r_B,r,A,B),

(3) T→B: E_kAT(r_A,k), E_kBT(r_B,k),

(4) В→А: E_kAT(r_A,k).

Пользователь А генерирует два случайных числа: первое (r_А) используется, как и раньше, для взаимной аутентификации, а второе (r) — для аутентификации сеанса связи (вместо него может быть использована метка времени).

Этот протокол можно дополнить еще одним шагом для обеспечения взаимной аутентификации сторон и подтвержде­ния правильности полученного ключа:

(4') В→А: E_kAT(r_A,k),E_k(r,r_B),

(5)А→В: E_k(r).

Передача ключей с использованием асимметричного шифрования

Рассмотрим варианты использования асимметричного шифрования для передачи секретных ключей симметричных криптосистем.

Протоколы без использования цифровой подписи

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

А→В: E_kB(k,t,A),

где Е — алгоритм шифрования с открытым ключом, t — метка времени.

Для осуществления взаимной аутентификации и под­тверждения правильности получения ключа исполь­зуется протокол из работы Нидхема и Шрёдера:

1. А→В: E_B(k_1,A),

2. В→А: Е_А(k₁, k₂)_,

3. А→В:Е_B(k₂).

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

Протоколы с использованием цифровой подписи

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

А→В: E_B(k,t_,S_A(B,k,t)) (шифрование подписанного ключа);

А→В: E_B(k_,t)_,S_A(B_,k_,t) (зашифрование и подпись ключа);

А→В: t,E_B(A,k),S_A(B,t,E_B(A,k)) (подпись зашифрованного ключа).

Сертификаты открытых ключей

Как правило, при использовании открытых ключей хра­нят не сами ключи, а их сертификаты. Сертификат пред­ставляет собой набор данных

С_А = (A,k_A,t,S_KTA(A,k_A,t)),

состоящий из идентификатора абонента А_, его открытого ключа k_А и, быть может, еще какой-либо дополнительной информации, например, метки времени t выдачи сертификата и сро­ка его действия, заверенных цифровой подписью доверенного центра ТА или заслуживающего доверия лица.

Международный стандарт CCITT Х.509 определяет сле­дующий протокол аутентификации с одновременным распре­делением ключей:

1. А→В: С _А, D_A, S_A (D_A ),

2. В→А: C_b,D_b,S_b(D_b),

3. A→B: r_B ,B,S_A(r_B,B),

где C_A и C_B — сертификаты сторон, S_A и S_B — цифровые подписи сторон,

Da=(t_A,r_A,B, data₁ ,E_B(k₁)), Db=(t_B ,r_B,A,r_A, data₂,E_A(k₂)) — наборы передаваемых и подписываемых данных. В поля data заносится дополнительная информация для аутентифи­кации источника. Третий шаг протокола требуется стороне В для подтверждения того, что она действительно взаимодейст­вует со стороной А.

Открытое распределение ключей

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

Алгоритм открытого распределения ключей Диффи - Хеллмана. Для его вы­полнения стороны должны договориться о значениях боль­шого простого числа р и образующего элемента α мультипликативной группы Z*_p= {1,2,..., p — 1}. Для выработки об­щего ключа k они должны сгенерировать случайные числа х, 1≤х≤р-2,и y, 1≤y≤р-2, соответственно. Затем они должны обменяться сообщениями в соответствии с протоколом:

1. А→В: α^x mod p

2. В→А: α^y mod p.

Искомый общий ключ вычисляется по формуле:

k = (α^у)^х = (α^х)^у mod р

Недостатком этого протокола является возможность ата­ки типа "злоумышленник в середине". Выбрав числа х* и у* и подменив сообщения α^x* mod р и α^y*mod р на α^х* mod р и α^у* mod р соответст­венно, он может сформировать ключи

k₁=(а^х)^y*modр

и

k₁=(а^y)^x*modр

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

Рассмотрим два протокола, устраняющие этот недоста­ток. Первый протокол, называемый STS (station-to-station), предполагает, что пользователи применяют цифровую под­пись, которой подписываются передаваемые по протоколу Диффи—Хеллмана сообщения:

1. А→В: α^x mod р,

2. В→А: α^ymodp, E_k(S_B(α^y,α^x)),

3. A→B:E_k(S_A(α^x, α^y)).

Здесь S_A и S_B — цифровые подписи пользователей А и В соответственно, k — искомый общий ключ. Шифрование значений подписей пользователей введено для того, чтобы обеспечить взаимное подтверждение правильно­сти вычисления значения ключа.

Еще один подход также предполагает наличие у абонен­тов открытых ключей, но вместо цифровой подписи предла­гается использовать модифицированную процедуру выработ­ки общего ключа. Протокол MTI (Т. Мацумото, И. Такашима и X. Имаи).

Пользователи А и В имеют секретные ключи a и b

1 ≤ a≤ р-2,1≤ b ≤ p - 2 ,

соответственно, и публикуют свои открытые ключи z_A= α^a mod р и z_B=α^bmodp. Для выработки общего секретного ключа k они должны сгенерировать случайные числа х, 1 ≤ х≤р-2, и у, 1≤у≤р-2, соответственно, а затем обменяться сле­дующими сообщениями:

1. А→ В: α^x mod p,

2. В→А: α^ymod p.

Искомый общий ключ вычисляется по формуле:

k =(α^y)^az^x_B = (a^x)^bz^y_A = α^xb+ya mod p.

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

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

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

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

Выбирается поле F, имеющее конечное, но достаточно большое число элементов, и фиксируется п различных эле­ментов r₁,...r_nЄ F_, отличных от нуля. Каждый элемент r_i ставится в соответствие i-му абоненту сети, i =. Эти элементы не явля­ются секретными и могут храниться на общедоступном сер­вере сети. Далее, выбирается многочлен над полем F степени 2m, 1 ≤ т < п, вида

где a_ij = a_ji, i≠j, i,j=. Его коэффициенты являются сек­ретными и должны храниться только в центре распределения ключей. Каждый абонент А получает в качестве ключевых материалов набор коэффи­циентов многочлена:

Для связи между абонентами А и В теперь можно исполь­зовать общий ключ к_АВ:

который могут вычислить оба абонента.

При использовании данной схемы каждый абонент дол­жен хранить m+1 секретных значений вместо п-1, общее же число секретных коэффициентов многочлена f равно т(т+1)/2.

Схема Блома предварительного распределе­ния ключей между п абонентами, использукпцая многочлен степени m, 1≤m<n, является стойкой к компрометации ключей т абонентов. Это означает, что при раскрытии ключевых материалов, принадлежащих любым m абонентам, злоумышленник, зная их значения, не сможет определить ни один из ключей для связи между остальными (n-m) абонен­тами.

Схемы разделения секрета

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

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

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

Возможные атаки на протоколы распределения ключей

При анализе протоколов обычно рассматривают несколь­ко видов атак.

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

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

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

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

В целом при анализе протоколов распределения ключей применяют различные методы:

1. Эвристические подходы, основанные на имеющемся наборе практических приемов и известных атаках, зарекомендовавших себя при анализе дру­гих протоколов.

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

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

4. Барроузом, Абади и Нидхемом (Burrows, Abadi, Needham) предложен формальный метод анализа протоколов, получивший название BAN-логики. В нем все шаги протокола и передаваемые сообщения записываются в некотором стан­дартном формализованном виде, а затем осуществляется их формальный анализ при некоторых типовых предположениях о возможном поведении сторон. Данные формальные доказа­тельства относятся в основном к корректности протоколов и не всегда могут рассматриваться как доказательство их безо­пасности.