close

Вход

Забыли?

вход по аккаунту

?

Атака с открытым текстом на модель скрытой передачи информации.

код для вставкиСкачать
2007
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№44
УДК 681.322, 681.51
Е.Г.Василенко
АТАКА С ОТКРЫТЫМ ТЕКСТОМ НА МОДЕЛЬ СКРЫТОЙ ПЕРЕДАЧИ ИНФОРМАЦИИ
Институт электронных и информационных систем НовГУ
The resistance of model of latent digital data transmission to the plaintext attack is explored in the general case. It’s proved, the
model shouldn’t be applied as separate crypto algorithm.
ции значащих элементов, незначащие обозначены
* ).
Термин «атака с открытым текстом» будет использоваться нами в нетрадиционном значении. Действительно, поскольку рассматриваемая криптосистема никоим образом не кодирует исходное сообщение, то секретный ключ может быть легко определен
при знании пары символов исходного сообщения.
Под открытостью текста будем понимать возможность идентификации одного или нескольких символов исходного сообщения в передаваемом.
В статье исследуется стойкость модели скрытой передачи информации [1,2] к атаке с открытым
текстом. Напомним сущность модели. Модель необходимо включает в себя источник шума, два управляющих генератора разрядности n (расположенных в
передатчике и приемнике соответственно) и секретный ключ K разрядности m , m ≤ n . Перед началом
работы оба генератора с помощью синхропосылки
переводятся в режим синхронизма. Далее в канал передается шумовой сигнал из источника шума до тех
пор, пока m разрядов выхода генератора не совпадут
с ключом K . В этом случае передается пакет данных.
Схема рассматриваемой модели представлена на
рис.1.
Как следует из описания модели, секретный
ключ K содержит m значащих и n − m незначащих
символов и может быть представлен в виде вектора
размерности n (см. рис. 2, где a1 , a2 ,K, a m — пози-
Рис.2. Секретный ключ K
Рис.1. Система скрытой передачи информации
23
2007
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
Итак, пусть злоумышленник (З-к) получил
информацию о том, что несколько пакетов в передаваемом наборе данных являются данными из источника информации, а следовательно, выход
управляющего генератора (УГ) в эти моменты времени содержит в себе ключ K . Для оценки рассматриваемой модели важно выяснить: насколько
полученные сведения упростят в среднем для З-к
вскрытие криптосистемы? Решение этой задачи и
является целью статьи.
Проведем анализ исходя из следующих предположений, типичных для анализируемой модели.
— З-к не известно число значащих элементов
ключа m (величина m является секретной и в значительной мере определяет стойкость модели).
— З-к может проверить, является ли данный
n -разрядный вектор ключом K за одну итерацию.
Действительно, даже если модель скрытой передачи
информации является частью более общей криптосистемы, число вычислительных операций, затрачиваемых на проверку, не зависит от параметров модели и
выражается константой. Для простоты полагаем ее
равной единице.
— Пакеты информации о ключе, получаемые
З-к, могут дублироваться. Поскольку З-к не управляет процессом получения дополнительной информации о ключе, то он и не может исключить дубли заранее. Кроме того, в противном случае вычисления существенно усложняются, а наша задача состоит лишь
в исследовании общей закономерности.
— Ключ распределен равновероятно.
Пусть З-к располагает некоторым набором из
s векторов размерности n , являющихся выходными значениями УГ. Обозначим их v1 , v2 , K, v s . Каждый из них содержит в себе значащие элементы
секретного ключа K . Разумеется, З-к сначала выделит общую составляющую этих векторов Vs и в
дальнейшем будет осуществлять криптоанализ уже
на ее основе.
Опишем это более формально. Для пары двоичных векторов vi , v j введем операцию « ∧ » со сле-
№44
Рис.3. Пример выполнения операции « ∧ »
Обозначим через Ls число значащих элементов вектора Vs . Очевидно, Ls ≥ m , причем Ls = m
означает, что криптосистема вскрыта. Определим
распределение случайной величины Ls .
P( Ls = l ) =
n
∑ P( L
s −1
k =l
= k ) ⋅ P(k ⎯
⎯→
l ),
s
(1)
⎯→
l ) — вероятность того, что число знагде P(k ⎯
s
чащих элементов вектора Vs −1 составляло k , а тот же
параметр для вектора Vs уменьшился до l . По определению
P( L1 = n ) = 1.
(2)
⎯→
l ) в действительности не завиВероятность P(k ⎯
s
сит от значения s и определяется формулой
P( k → l ) =
C kk−−ml
.
(3)
2 k −m
Используя выражения (1) и (3), определим среднюю
длину значащей части Vs :
дующей таблицей истинности:
0 1
0 0 *
1 * 1
Таким образом, элементы вектора-результата могут
принимать значения из множества { 0,1, * } , где под *
будем понимать незначащий символ. Пример выполнения этой операции над тремя 6-мерными векторами
приведен на рис.3.
Итак, Vs = v1 ∧ v2 ∧ K ∧ v s .
Вектор Vs содержит ту же информацию о
ключе K среди своих значащих элементов, что и
исходный набор из s векторов. Естественно, чем
больше значащих элементов содержит Vs , тем
труднее будет вскрыть криптосистему. Будем искать зависимость среднего числа операций при
взломе перебором от числа известных З-к векторов
s.
M s (l ) =
n
∑ P( L
s
l =m
l + m⎞ 1
m
= l ) ⋅ l = M s−1 ⎛⎜
⎟ = ⋅ M s−1 (l ) + . (4)
⎝ 2 ⎠ 2
2
В силу (2) получаем окончательный результат:
m ⋅ ( 2 s −1 − 1 ) n − m
= s −1 + m.
(5)
2 s −1
2 s −1
2
Построим график зависимости (5) при заданных n и m (рис.4).
Ms( l ) =
24
n
+
2007
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№44
1. Попробовать на роль ключа сначала все варианты с k − 1 значащими элементами, потом с
k − 2 и так далее, до тех пор пока не подберем ключ.
Назовем эту стратегию нисходящей.
2. Начать с одного элемента и рассматривать
варианты в порядке возрастания числа значащих
символов. Назовем эту стратегию восходящей.
Начнем с нисходящей стратегии. Очевидно,
что число вариантов оценивается сверху величиной
~
C desc ( k ) =
k −m
∑C
k −s
k .
s =0
Действительно, ключ K будет найден лишь на последней из итераций s = 0,K, k − m , причем на по-
следней итерации потребуется в среднем 0,5 Ckm опе~
раций. Отсюда же следует, что Cdesc ( k ) является
точной верхней оценкой для числа операций при использовании нисходящей стратегии:
~
Cdesc ( k ) = sup Cdesc ( k ).
Рис.4. График зависимости средней длины значащей части
вектора Vs ( n = 128 , m = 32 )
Таким образом, средний размер значащей части
ключа экспоненциально падает до величины m с ростом знаний о ключе. Но неверно было бы определять
сложность вскрытия только объемом исходных данных,
при которых З-к полностью получит ключ. Следует
также учитывать и вероятность того, что З-к подберет
ключ и при неполных данных о нем. Следовательно,
средняя сложность вскрытия определится по формуле
Comp( s ) =
n
∑ P( L
s
k
Рассуждая подобным образом, получим точную верхнюю оценку вариантов и для восходящей
стратегии:
~
C asc ( k ) =
(6)
Аналогично (6) определим верхние оценки
средней сложности вскрытия при использовании нисходящей и восходящей стратегий:
где C ( k ) — число операций, необходимых для вскрытия криптосистемы, если число значащих элементов
Vs составляет k .
~
Compdesc ( k ) =
∑ P( L
s
= k ) ⋅ 2k .
n
∑ P( L
s
~
= k ) ⋅ C desc ( k ),
k =m
Попробуем для начала использовать одну из
оценок для C (k ) , чтобы получить общее представление о характере изменения зависимости (6). Ясно, что
C (k ) < 2 k .
(7)
Используя (7), найдем верхнюю оценку для (6):
n
s
k
s =0
= k ) ⋅ C ( k ),
k =m
~
Comp( s ) =
m
∑C .
~
Compasc ( k ) =
n
∑ P( L
s
~
= k ) ⋅ C asc ( k ).
k =m
К сожалению, не удалось получить более удобные
аналитические выражения для этих оценок и установить аналитически взаимное поведение этих функций. Для иллюстрации построим графики этих выражений при различных значениях n , m .
(8)
k =m
Поскольку мы ищем аналитическое выражение для
(8), без знания выражения функции распределения
P( Ls = k ) здесь не обойтись. Опираясь на те же соображения, что и при вычислении значений зависимости (6), получим:
P( Ls = l ) = Cnl −−mm ⋅ 2( s −1)⋅( m − n ) ⋅ ( 2 s −1 − 1 ) . (9)
Подставляя (9) в (8) и суммируя, находим:
1 n−m
~
C omp ( s ) = 2 m ⋅ ⎛⎜1 + s −1 ⎞⎟ .
⎝ 2 ⎠
Отсюда видно, что сложность вскрытия экспоненциально падает с ростом числа s известных З-к векторов
~
УГ. Однако lim C omp ( s ) = 2 m , поскольку это верхняя
n −l
s →∞
оценка. Возможно ли получить более точную оценку?
Предположим, что З-к знает, что среди k значащих элементов ключа есть некоторое количество
лишних. Каким образом он будет отбрасывать неподходящие варианты, чтобы минимизировать время
перебора? Возможны две простых стратегии.
Рис.5. Графики двойных логарифмов оценок сложностей при
n = 128 , m = 16
Как видно из рис.5, если полученные З-к знания
о ключе невелики (при малых s) и длина значащей части
25
2007
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
ключа существенно меньше размерности выходного
вектора УГ, то нисходящая стратегия по сложности
близка к полному перебору, и наоборот, как только знания о ключе достигают некоторой критической отметки,
к полному перебору сводится восходящая стратегия.
Очевидно, при изменении соотношения n и m взаимное
расположение графиков будет меняться (см. рис.6, 7).
№44
Естественно, при возрастании значащей части ключа нисходящая стратегия становится более
предпочтительной. Но поскольку объем выходного
потока информации экспоненциально зависит от
длины значащей части ключа, то, скорее всего,
значение m при кодировании будет невелико, и З-к
предпочтет использовать восходящую стратегию
перебора. В этой связи наибольшее внимание следует уделить рис.5, поскольку значения n = 128,
m = 16 наиболее близки к тем, которые могут быть
использованы на практике. При ближайшем рассмотрении выясняется, что стойкость данной криптосистемы к рассматриваемой атаке оставляет желать лучшего. Обладая информацией о всего лишь
5 пакетах, З-к может уменьшить число рассматриваемых комбинаций до порядка 108 (с первоначальных 1038 ), и перебор вполне может быть реализован даже на обычном персональном компьютере. А поскольку при расчетах мы опирались на
предположение, что управляющий генератор является идеальным и, более того, никоим образом не
использовали свойства исходного сообщения, то
все приведенные оценки сложности вскрытия являются верхними.
Рис.6. Графики двойных логарифмов оценок сложностей при
n = 128 , m = 64
Вывод
Рассмотренную криптосистему следует использовать только в сочетании с другими шифрами.
А поскольку шифр, как правило, порождает выходную последовательность, различимую со случайной
последовательностью статистическими тестами, то
при формировании шумовой последовательности
обязательно нужно учитывать свойства исходного
сообщения.
1.
Рис.7. Графики двойных логарифмов оценок сложностей при
n = 128 , m = 96
2.
26
Кирьянов Б.Ф. Микропроцессорные средства в задачах
имитации и обработки случайных сигналов. Ч.2. Новгород: НПИ, 1989. 48 с.
Жгун Т.В., Кирьянов Б.Ф. // Вестник НовГУ. Сер.: Математика и информатика. 2002. №22. С.50-53.
Документ
Категория
Без категории
Просмотров
6
Размер файла
341 Кб
Теги
атаки, скрытое, передача, текстом, модель, информация, открытый
1/--страниц
Пожаловаться на содержимое документа