Teoria_chisel_i_kriptozashita

2.Математические (известные нарушителю алгоритмы решения возникающих при криптоанализе задач, а также возможности создавать новые алгоритмы).

3.Технические (инструмент, реализующий атаку).

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

Вслучае криптосистем на эллиптических кривых специфическими являются математические возможности нарушителя.

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

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

апользователи системы — по полномочиям доступа, то в рамках вырожденной модели возможностей получается модель безопасности БеллаЛападулы.

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

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

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

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

10.Модель несанкционированной подмены передаваемой информации

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

71

раскрытия содержания «истинной» информации, нарушитель посылает заведомо ложную, которая может иметь неприятные последствия для пользователя данной сети или канала связи.

Пользователь А передает файл у пользователю В, который получает-

ся из открытого текста х путем шифрования его по правилу
у= Φ(х(m)) ,	(10.1)

где m — ключ шифрования.

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

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

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

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

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

72

жет изменить их) и у (которое может изменить), но не знает m. Сторона А знает у, m и Φ( , ).

Если нарушитель попытается послать стороне А ложное сообщение уo' , для которого может не быть исходного сообщения х' , удовлетворяю-

щего уо' = Φ(х' ,m), и тогда сторона А обнаружит обман нарушителя. Но

если нарушитель сможет решить уравнение (10.1), то тогда он может успешно заменить истинное сообщение ложным, но правильно зашифрован-

ным уо' = Φ(х' ,m). Возникает задача получения Φ( , )такого, чтобы было

невозможным для нарушителя обмануть сторону А, не будучи обнаруженным.

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

Задача похожа на обычно встречающуюся в криптографии ситуацию, когда ключ m используется для шифрования открытого текста х в кодированную форму у= Φ(х(m)) . Но существует значительное отличие. Так как нарушитель уже знает х, то большинство стандартных криптогра-

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

Чтобы затруднить возможность нарушителю раскрыть ключ, используя уравнение (10.1), сторона А должна сконструировать такую функцию

Φ( , ), чтобы (10.1) имело бы несколько решений для m. Тогда нарушитель вероятнее всего, выберет неправильный ключ mо и сторона А обна-

ружит, что зашифрованное нарушителем послание уo' не соответствует правильному ключу. Как можно ожидать, для обеспечения нескольких решений уравнения (10.1) сторона А должна использовать большое число К возможных ключей.

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

ро для оптимальной стратегии нарушителя обозначим ро' . Покажем, что ро ≥ К−0,5 . Равенство в этом случае достигается только жестким ограни-

чением числа N возможных посланий х. Более полезные коды должны выбираться, исходя из компромисса между тремя конфликтующими параметрами: малое ро , малый К и большое N. Рассмотрим два таких случая: слу-

чайный код и систематический.

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

73

мем, что х равновероятно одному какому-либо значению из N возможных

значений и что нарушитель выбирает ложное послание х' случайно из остальных N – 1 возможностей. Тогда ро является средней из вероятностей

успеха ро(х, у,х' ), когда нарушитель замещает х на х' , зная у.

Для подтверждения подлинности (аутентификации) сообщения принята специальная форма построения файла, записываемая как

у= (х; z),

(10.2)

т.е. у является соединением незашифрованного текста х и некоторого количества дополнительных цифр или букв z. Здесь z — некоторая функция

от х и m, которую будем называть аутентификатором.

Хотя уравнение (10.2) является особым случаем (10.1), без существенной потери общности можно распространить шифрование и на эту осо-

бую форму. Действительно, если некоторые другие Φо(х,m)в уравнении (10.1) дают хороший код, можно всегда создать код вида (10.2), выбирая

z = Φо(х, у), т.е.

y = Φ(x,m)= [x;Φo(x,m)].

Включение х в виде части у не оказывает существенной помощи на-

рушителю; так как он уже знает х. К тому же известное х не может помешать стороне А в раскрытии обмана нарушителя. Таким образом, новый код по крайней мере одинаково хорош для А, как и старый код.

Использовать или не использовать код в форме (10.2) — это предмет договора. Однако уравнение (10.2) имеет специальное свойство, которое характерно для всех кодов. Оно заключается в том, что различные откры-

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

Φ(m1 ,х1 ) ≠ Φ(m2 ,x2 )

(10.3)

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

левом столбце, а зашифрованные послания у — как точки в правом столбце. Стрелки, направленные слева направо, будут отображать наименование ключей 1,...,К, используемых для отображения процесса кодирования ка-

ждого х в у. Согласно выражению (10.3), закодированные послания у делятся на несвязные кластеры, причем каждый кластер содержит все возможные представления каждого х.

Оценим вероятность обмана. Пусть нарушитель успешно обманывает сторону А с вероятностью ро ≥ К−1 для наугад выбранного ключа mo

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

74

ключей, которые удовлетворяют уравнению (10.1). Обычно нарушитель не нуждается в выборе при mo = m правильного ключа, так как он получает удовлетворение, если

Φ(х' ,то )= Φ(х' ,m).

(10.4)

Нарушитель выбирает для mo одно из значений 2, 3, 4, 5 или 6. Если m = 2, тогда подходят выбранные mo = 2, 4 или 6.

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

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

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

ро = К−1 . Действительно, теперь покажем, что нарушитель всегда может

использовать стратегию с вероятностью
р ≥ К−0,5 .	(10.5)
о

Для доказательства формулы (10.5) установим несколько естественных ограничений на поведение стороны А и нарушителя:

а) нарушитель не пытается обмануть сторону А заменой х на х' = х. Если допустить, что нарушитель «обманывает» в каком-либо виде с вероятностью ро =1, то, исходя из выражения (10.5), это дает слабый результат;

б) все N посланий х равновероятны. Хотя это требование может быть ослаблено, некоторые условия, подобные этому, должны быть поставлены. Для страховки сторона А может использовать одно специальное послание

х1 только в исключительных случаях. В этом случае сторона А может присвоить всем ключам, имеющим код х1 , одинаковое значение у1 , а всем другим посланиям — код х' . К различных ключей для шифрования тогда должны давать вероятность ро < К−0,5 , но сторона А при этом по-

лучит минимум информации от каждого послания; в) другим ограничением на сторону А может быть случайное ис-

пользование К ключей с равной вероятностью и независимо от х. Исчезает необходимость этого ограничения на сторону А для доказательства выражения (10.5). Если сторона А использует ключи в каком-либо другом направлении, это только помогает нарушителю увеличить ро ;

75

ро .

г) докажем, что (10.5) выполняется, даже если нарушитель выбирает

х' случайно из N – 1 равновероятных посланий, но отличных от х. Это только усиливает (10.5) за счет возможности использования лучшей стратегии для нарушителя.

Зная, как послания х,х' и ключ m распределены, можно вычислить совместную вероятность Р(х, у,х' ). Эта вероятность является весом, используемым для усреднения ро(х, у,х' ) в выражении

	ро =	∑Р(х, у,х' )ро(х, у,х' ),	(10.6)
		х,у,х'
как было указано ранее.
Вероятность р (х, у,х' )		того, что нарушитель добьется успеха при
	о
замене	х' , зная х и у, зависит от того, как нарушитель		распорядится
х, у,х'	, чтобы создать ложное шифрованное сообщение уo'		. Нарушитель

должен знать функциюΦ( , ) и распределение ключей. Исходя из этого, он может вычислить распределение условной вероятности P(y' | x, y,x' ) пра-

вильно зашифрованного ложного послания у' = Φ(х' ,m). Нарушитель максимизирует возможность своего успеха при использовании ложного

послания уо , которое максимизирует	P(y' | x, y,x' ). Таким образом, на-
рушитель достигает вероятности	'	'
′			(10.7)
po (x, y, x ) = MaxP(y | x, y,x )

и максимизирует рo в формуле (10.6). Так как (10.7) оптимально для нарушителя, присвоим этому значению ро специальное обозначение

Найдем связь ро со средней неопределенностью U, которую имеет

нарушитель относительно шифрованного ложного послания y' . U — это условная энтропия

U = H(y' | x, y,x' ) = − ∑P(x, y,x' , y' )logP(y' | x, y,x' ).		(10.8)
x,y,x' ,y'
Если нарушитель выбирает	уо , то в соответствии с выражением
(10.6) получим
p = р ≥ 2−U .		(10.9)
o	о

76

Равенство в уравнении (10.9) справедливо, если и только если возможные шифрованные сообщения y' для всех (x, y,x' ), у которых

P(x, y,x' ) ≠ 0 , равновероятны и равны точно 2U .

Доказательство не требует выполнения ограничений (a), (б), (в), (г).

Используем выражение (10.7)	для записи	Р(у' | х, у,х' ) ≤ p	o	(x, y,x' ) в
	по y' и используя свойство
выражении (10.8). Суммируя			выпуклости
функции −log p , получим
'	'	'		′
U ≥ − ∑ P(x, y,x )logpo(x, y,x ) ≥ −log ∑P(x, y,x )po (x, y, x ).
x,y,x'		x,y,x'

Отсюда выражение (10.9) следует из (10.6).
	Вывод использует два неравенства. Оба превращаются в равенства,
если	равенством		становится	выражение	(10.9).
Р(у' | х, у,х'		)= po (x, y,x' ) удовлетворяет всем возможным			y' для дан-
ных	x, y,x' .	Для условия	выпуклости	необходимо, чтобы	все члены

−log po(x, y,x' ) были равны U.

Теперь установим границу po* через неопределенность H(m), кото-

рая связана с выбором ключа.

Предположим, что удовлетворяются уравнение (10.7) и ограничения a), б), в), г). Тогда

	–	1H(m)
p = р ≥ 2		2	.	(10.10)
o	o

Сначала заметим, что y' определяется из выражения y' = Φ(m,x' ) , если (m,x' ) известны. Тогда y' содержит меньше информации, чем (m,x' ):

U = H(y' | x, y,x' ) ≤ H(m,x' | x, y,x' )= H(m | x, y,x' ).	(10.11)
Но условная вероятность для данных x, y,x' зависит только от x, y ,
так что выражение (10.11) превращается в
U ≤ H(m | x, y).	(10.12)
Также
H(m) ≥ H(m | x)= H(m, y | x)= H(y | x)+ H(m | x, y),
так что условие (10.12) обеспечивает
U ≤ H(m) − H(y | x).	(10.13)

Но

U = H(y' | x, y,x' ) ≤ H(y' | x' ).

77

Благодаря ограничению г) x' равновероятно одному из N посланий. Тогда из условия б) х и x' должны иметь одинаковые распределения, то-

гда H(y' | x' ) ≤ H(y | x) и окончательно
U ≤ H(y | x).	(10.14)
Теперь сравним выражения (10.13) и	(10.14). Если

H(y | x) ≤ 1 H(m), тогда U ≤	1 H(m), как следует из (10.13). В остальных
2	2
случаях справедливо выражение (10.10).
Граница (10.10) подтверждает формулу (10.9) и фактически сводится
к ней, когда выполняется ограничение (с).		p = K −0,5 ,
Код, оптимальный для нарушителя, имеет			т.е. мини-
		o
мально возможное значение, но использует только N =1+ K 0,5			посланий.
Коды с N >> K представляют больший интерес.		Рассмотрим, насколько

возможно увеличение соответствующей вероятности po , когда конструи-

руемые коды будут случайными. Теперь N не имеет ограничений на свое значение и может быть как угодно большим. Главным результатом будет

− 1

тот, что для po не требуется значительно превышать K 2 .

Случайный код может иметь один свободный параметр А. Каждому х допускается число возможных видов кодирования, определяемое количе-

ством свободных параметров. Для каждого из К ключей у в выражении (10.1) выбирается случайным образом в зависимости от количества свободных параметров. Выбор К производится независимо. При благоприятной возможности одно из возможных значений А не выбирается из К проб. В этом случае код обеспечивает вероятность po , зависящую от случайно-

го выбора. Определим ожидаемое значение Е(ро ). Особые коды с заданными N и К и имеющие po менее, чем эти прогнозы, действительно существуют.

Все данные относительно Φ( , ), которые необходимы нарушителю

для замены х'	на х, содержатся в таблице, показывающей, как шифрован-
ные послания	у, у' зависят от ключа m. Рисунок 5 представляет собой

удобную таблицу, представляющую массив из А× А ячеек, где каждая ячейка, содержащая список всех ключей, определяет пары ( у, у' ). Рисунок

78

5 соответствует паре сообщений, обозначенных х,х' . Пусть v(у, у' ) будет числом ключей в ячейке ( у, у' ).

Зная у, нарушитель проверяет соответствующий столбец на рисунке 5. Так как Кключей принимаются одинаковыми, то

Р(у' | х, у,х' )= v(у, у' )/ ∑v(y, y1 ).	(10.15)
у1

Оптимальная стратегия, с помощью которой нарушитель достигает границы (10.7), требует выбора уо для максимизации v(у, у' ). На рисунке 5 строка уо пересекает столбец у в ячейке с наибольшим числом ключей.

В таких ячейках должно выполняться условие k >1 в строке у, тогда В может свободно выбрать одну из k строк случайным образом.

у

у'	—	3,	5	7
	—	2, 4, 6		—
	1		—	8

Рис. 5. Таблица ключей

Е(ро ) теперь может считаться решением задачи распределения ключей. Представим, что правильным ключом будет ключ 1, и он занимает ячейку в столбце 1 и строке 1. Распределим оставшиеся К - 1 ключей случайным образом по А2 ячейкам. Пусть рn,k будут вероятности того, что ячейка (1, 1) содержит v(1,1)= n ключей таких, что k −1 других ячеек в столбце 1 содержат n ключей. Более того, все А - k остальных ячеек в столбце 1 содержат менее, чем n ключей. Тогда

Е(ро )= ∑k −1 рn,k	(10.16)
n,k

является вероятностью того, что нарушитель выбирает первую строку по уо . Точная формула для рn,k весьма громоздка. Не составляет труда смоделировать экспериментальное распределение на компьютере, чтобы оценить Е(ро ), когда К меньше нескольких сотен. Это было проделано [11], но только для проверки на возможность более простой аппроксимации. Когда А велико, то каждый ключ имеет малую вероятность А−2 , относящуюся к ячейке ( у, у' ). После огромного числа независимых испыта-

79

bnk −1ВnА−−1k

рn,k

ний, число v(у, у' ) ключей в ячейке имеет приблизительно пуассоновское распределение со средним

λ= (К −1)А−2 .

(10.17)

Соответственно, будем рассматривать числа v(у, у' ) как независимые переменные, имеющие распределение Пуассона со средним λ. Число v(у, у' ) особое, поэтому начальное распределение получим, размещая ключ 1 в ячейку (1,1); v(1,1) −1 является переменной Пуассона для этой ячейки. Аппроксимация Пуассона имеет тот недостаток, что общее число

ключей ∑v(y, y' ) является случайной величиной. Однако среднее число

y,y'

ключей равно К и весьма высока вероятность того, что при большом числе ключей К действительное их число практически равно К. Результат аппроксимации будет хуже для малого числа К, чем для большого. Аппроксимация распределением Пуассона и модель должны давать то же самое Е(ро ) в пределах нескольких процентов даже для K = 25.

Для упрощения написания выражения предположим, что bn и Вn означают вероятности того, что случайная переменная Пуассона имеет значение n или близко к нему.

		b	= λne−n / n!
		n
тогда		Вn = bо +b1 +...+bn ,
		= b bk −1ВА−k А−1 .
р	n,k				(10.18)
		n−1	n n−1
			k −1

В выражении (10.18) bn−1 — это вероятность того, что ячейка (1,1) содержит n ключей, —это вероятность того, что множество

k −1других ячеек имеет n ключей, но все другие А−k имеют k −1 ключей или менее, а биномиальные коэффициенты вычисляют различные множества из k −1 ячеек. Теперь подставим (10.18) в (10.16). Суммированием по k получим

∞	}.
Е(ро )= ∑(n / λA){BnА − ВnА−1		(10.19)

n=1

В таблице 1 приводятся значения Е(ро ), вычисленные по формуле (10.19). Для фиксированных К широкий минимум Е(ро ) возникает около

80