Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

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

Эволюции сетей сотовой подвижной связи характеризуется внедрением современных технологий и услуг, интеграционными и конвергентными решениями. Внедрение интеллектуальных услуг (MMS, SMS, WAP, WEB и др. платформ), разнообразных услуг биллинга заставляют операторов сотовой связи интегрироваться во всемирную сеть Интернет. При рассмотрении всех положительных сторон такого развития СПС нужно сознавать, что интеграция сетей СПС с сетью Интернет и технологиями беспроводного доступа (Bluetooth, Wi-Fi, Wi-Max и пр.) ведет к преемственности угроз информационной безопасности (ИБ), существующих в этих сетях. Разнообразие программно-технических решений дает почву для появления новых атак на сети СПС.

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

В разделе БЖДЧ будут анализированы технические решения, организационно технические и организационные меры обеспечивающие безопасные и безвредные условия труда на рабочем месте с ПК.

1. ОБЗОР МЕТОДОВ ОБЕСПЕЧЕНИЯ БЕЗОПАСНОСТИ В СТАНДАРТЕ GSM

1.1 Общие характеристики стандарта GSM

В стандарте GSM используется узкополосный многостанционный доступ с временным разделением каналов (NB TDMA). В структуре TDMA кадра содержится 8 временных позиций на каждой из 124 несущих.

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

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

В стандарте GSM выбрана гауссовская частотная манипуляция с минимальным частотным сдвигом (GMSK). Обработка речи осуществляется в рамках принятой системы прерывистой передачи речи (DTX), которая обеспечивает включение передатчика только при наличии речевого сигнала и отключение передатчика в паузах и в конце разговора. В качестве речепреобразующего устройства выбран речевой кодек с регулярным импульсным возбуждением/долговременным предсказанием и линейным предикативным кодированием с предсказанием (RPE/LTR-LTP-кодек). Общая скорость преобразования речевого сигнала - 13 кбит/с.

В стандарте GSM достигается высокая степень безопасности передачи сообщений; осуществляется шифрование сообщений по алгоритму шифрования с открытым ключом (RSA).

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

Структурная схема построения сети стандарта GSM представлена на рис. 1.1. Основными элементами этой схемы являются: MS - подвижная станция; BTS - базовая станция; BSC - контроллер базовой станции; ТСЕ -транскодер; BSS - оборудование базовых станций (BSC+ТСЕ+BTS); MSC - центр коммутации подвижной связи; HLR - регистр положения; VLR - регистр перемещения; AUC - центр аутентификации; EIR - регистр идентификации оборудования; ОМС - центр управления и обслуживания; NMC - центр управления сетью; ADC - административный центр; PSTN - телефонная сеть общего пользования; PDN - сети пакетной передачи; ISDN - цифровые сети с интеграцией служб.

Рисунок 1.1 - Структурная схема сети сотовой связи стандарта GSM

1.2 Угрозы передаваемой информации в сетях сотовой связи

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

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

- клонирование модулей SIM;

- хакерский взлом систем автоматизированного расчета с абонентами (биллинга);

- мошенничество с картами предоплаты.

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

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

1.3 Методы обеспечения безопасности в сетях GSM (А3, А5, А8)

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

защита от несанкционированного доступа к мобильной станции (МС) с помощью парольного метода защиты;

идентификация мобильного абонента ССС с помощью его уникального международного идентификационного номера (МИН);

аутентификация (определение подлинности) абонента при каждом вхождении в связь с помощью алгоритма А3;

конфиденциальность передаваемой по радиоканалу информации путём её шифрования с помощью алгоритма А5, где ключ шифрования вычисляется алгоритмом А8;

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

Криптографическая защита информационных ресурсов систем сотовой связи обеспечивается за счет использования алгоритмов А3, А5 и А8, носителем которых, за исключением А5, является SIM-карта абонента.

1.3.1 Алгоритм А3

A3 - алгоритм, используемый в процессе аутентификации в глобальном цифровом стандарте для мобильной сотовой связи GSM. Задача алгоритма - генерация отзыва (SRES - Signed Response) на случайный пароль (RAND -Random), получаемый мобильным телефоном (МС - мобильная станция) от центра коммутации ЦКМС в процедуре аутентификации.

Процедура аутентификации реализуется центром коммутации мобильной сети (ЦКМС) со стороны БС и SIM-картой абонента - со стороны МС. Последовательность действий при выполнении этой процедуры следующая:

МС посылает запрос на БС о предоставлении ей системных ресурсов;

ЦКМС генерирует случайное 128-битное число rand и, используя оборудование БС, посылает его на МС;

МС, используя число rand и индивидуальный ключ аутентификации Кi, по алгоритму А3 определяет отклик SRES (длиной 32 бита) и отправляет этот отклик через БС на ЦКМС;

ЦКМС, имея все необходимые данные о каждом абоненте сети, производя аналогичные действия, также вычисляет SRES. При получении отклика с МС, ЦКМС сравнивает оба значения. Если они совпадают, то соединение устанавливается, в противном случае - связь с МС прерывается.

Рисунок 1.2 - блок-схема алгоритма аутентификации

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

В настоящее время принят следующий формат входных и выходных данных RAND, Ki, SRES алгоритма A3: длина Ki - 128 бит длина RAND - 128 бит длина SRES - 32 бита.

Время выполнения алгоритма A3 должно быть меньше 500 миллисекунд.

В настоящее время известны следующие стандартные реализации алгоритма A3:

· COMP128 (структура этого алгоритма называется «формой бабочки». Состоит из 8 раундов в каждом раунде по 5 итераций)

· COMP128-2 (держится в секрете)

· COMP128-3 (держится в секрете)

· MILENAGE (считается неуязвимым к каким-либо известным атакам)

1.3.2 Алгоритм А5

А5 - это поточный алгоритм шифрования, используемый для обеспечения конфиденциальности передаваемых данных между телефоном и базовой станцией. Шифр основан на побитовом сложении по модулю два (булева операция XOR) генерируемой псевдослучайной последовательности и шифруемой информации. В A5 псевдослучайная последовательность реализуется на основе трёх линейных регистров сдвига с обратной связью. Регистры имеют длины 19, 22 и 23 бита соответственно. Сдвигами управляет специальная схема, организующая на каждом шаге смещение как минимум двух регистров, что приводит к их неравномерному движению. Последовательность формируется путём операции XOR над выходными битами регистров.

Существуют три разновидности алгоритма А5:

1) А5/1(алгоритм для распространения в Европе и США);

сотовый угроза связь псевдослучайный



Рисунок 1.3 - Структурная схема алгоритма А5/1

2) А5/2 (алгоритм с пониженной криптостойкостью, путём добавления ещё одного регистра (17 бит), управляющего сдвигами остальных);

Рисунок 1.4 - Структурная схема алгоритма А5/2

3) А5/3 (основан на алгоритме Касуми);

Как уже упоминалось, данный шифр является шифром Фейстеля с восьмью раундами. В качестве входных данных используются 128-битный ключ K и строка S. Входная строка делится на правую R0 и левую L0 части, равные по 32 бита каждая. На каждом из восьми раундов обе части преобразуются по следующему правилу:

R i = L i - 1; L i = R i - 1 XOR f (L i - 1, RK i) (1.1)

где f определяет функцию раунда, принимающую в качестве аргументов ключ раунда RК i и 32-битное входное значение. Ключ раунда RKi состоит реально из трёх ключей KLi , KOi и KIi , за генерацию которых ответственен элемент распределения ключей (key Scheduling Unit). Функция f состоит из трёх функций FL, FO и FI, которые и используют 3 соответствующих ключа. Функция FL принимает 32-битный входной параметр и с помощью 32-битного ключа KLi генерирует выход также размерности 32 бита.

Рисунок 1.5 - Функция FL

где: ? - функция логического «И»,

U - функция логического «ИЛИ»,

<<< - 1 бит переместить влево.

Функция FO принимает 32-битный входной параметр и два 48-битных ключа KOi и KIi. Последний используется при вызове функции FI.

Рисунок 1.6 - Реализация функции FO

Функция FI принимает 16-битный входной параметр и 16-битный ключ KIi,j и генерирует на их основе 16-битный выход.

а) б)

Рисунок 1.5 - а) Схема реализации шифра Kasumi; б) Функция FI

Из схемы нетрудно выяснить, какие логические операции использует каждая из этих функций. Стоит лишь отметить, что функция FI использует S-box S7 и S9, осуществляющие преобразования входных 7-ми и соответственно 9-ти бит в выходные 7 и 9 бит. На нечётных раундах первой исполняется функция FL, а на чётных - FO.

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

1.3.3 Алгоритм А8

A8 - алгоритм формирования ключа шифрования. По причине безопасности формирование Kc происходит в Sim-карте.

Рисунок 1.6 - Блок-схема вычисления Кс

Фактически алгоритмы A3 и А8 можно было бы реализовать в форме одного-единственного вычисления. Например, в виде единого алгоритма, выходные данные которого состоят из 96 бит: 32 бита для образования SRES и 64 бита для образования Кс. Следует отметить, что длина значимой части ключа Кс, выданная алгоритмом А8, устанавливается группой подписей GSM MoU и может быть меньше 64 бит. В этом случае значимые биты дополняются нулями для того, чтобы в этом формате всегда были использованы все 64 бита.

Всякий раз, когда какая-либо мобильная станция проходит процесс аутентификации, данная мобильная станция и сеть также вычисляют ключ шифрования Кс, используя алгоритм А8 с теми же самыми вводными данными RAND и Ki, которые используются для вычисления SRES посредством алгоритма A3.

2 МЕТОДЫ ОБЕСПЕЧЕНИЯ БЕЗОПАСНОСТИ ИНФОРМАЦИИ

2.1 Поточные шифры

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

2.1.1 Шифр RC4

Это потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколах SSL и TLS, алгоритме безопасности беспроводных сетей WEP, для шифрования паролей в Windows NT). Алгоритм RC4 строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов с равномерным распределением. Длина ключа обычно составляет от 5 до 64 байт. Максимальная длина ключа 256 байт.

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

Ядро алгоритма состоит из функции генерации ключевого потока. Эта функция генерирует последовательность битов (ki), которая затем объединяется с открытым текстом (mi) посредством суммирования по модулю два. Так получается шифрограмма (ci):

 (2.1)

Расшифровка заключается в регенерации этого ключевого потока (ki) и сложении его и шифрограммы (ci) по модулю два. В силу свойств суммирования по модулю два на выходе мы получим исходный незашифрованный текст (mi):

(2.2)

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

RC4 - фактически класс алгоритмов, определяемых размером его блока. Этот параметр n является размером слова для алгоритма. Обычно, n = 8, но в целях анализа можно уменьшить его. Однако для повышения безопасности необходимо увеличить эту величину. Внутреннее состояние RC4 представляется в виде массива слов размером 2n и двух счетчиков, каждый размером в одно слово. Массив известен как S-бокс, и далее будет обозначаться как S. Он всегда содержит перестановку 2n возможных значений слова. Два счетчика обозначены через i и j.

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



Рисунок 2.1 - Реализация шифра RC4

2.1.2 Шифр SEAL

Software-optimized Encryption Algorithm (программно-оптимизированный алгоритм шифрования) - симметричный поточный алгоритм шифрования данных оптимизированный для программной реализации.

Разработан в IBM Филом Рогэвеем и Доном Копперсмитом в 1993 году. Алгоритм оптимизирован и рекомендован для 32-битных процессоров. Для работы ему требуется кэш-память на несколько килобайт и восемь 32-битовых регистров. Cкорость шифрования - примерно 4 машинных такта на байт текста. Для кодирования и декодирования используется 160-битный ключ. Чтобы избежать нежелательной потери скорости по причине медленных операций обработки ключа, SEAL предварительно выполняет с ним несколько преобразований, получая в результате три таблицы определенного размера. Непосредственно для шифрования и дешифрирования текста вместо самого ключа используются эти таблицы. Алгоритм считается очень надёжным, очень быстрым.

Рисунок 2.2 -Реализация алгоритма SEAL

Чтобы избежать потери скорости шифрования на медленных операциях алгоритм использует три таблицы: R, S и T. Эти таблицы вычисляются с помощью процедуры из алгоритма SHA-1 и зависят только от ключа. Заполнение данных таблиц можно описать с помощью функции G, которая из 160-битной строки и 32-битного числа возвращает 160-битное значение .

Процесс шифрования состоит из большого числа итераций, каждая из которых завершается генерацией псевдослучайной функции. Количество пройденных итераций показывает счетчик l. Все они подразделяются на несколько этапов с похожими операциями. На каждом этапе старшие 9 битов одного из регистров (A, B, C или D) используются в качестве указателя, по которому из таблицы T выбирается значение. Это значение складывается арифметически или поразрядно по модулю 2 (XOR) со следующим регистром (снова один из A, B, C или D). Затем первый выбранный регистр преобразуется циклическим сдвигом вправо на 9 позиций. Далее либо значение второго регистра модифицируется сложением или XOR с содержимым первого (уже сдвинутым) и выполняется переход к следующему этапу, либо этот переход выполняется сразу. После 8 таких этапов значения A, B, C и D складываются (арифметически или XOR) с определенными словами из таблицы S и добавляются в ключевую последовательность y. Завершающий этап итерации заключается в прибавлении к регистрам дополнительных 32-битных значений (n1, n2 или n3, n4). Причем выбор конкретного значения зависит от четности номера данной итерации.

При разработке этого алгоритма главное внимание отводилось следующим свойствам и идеям:

· использование большой (примерно 2 Kбайта) таблицы T, получаемой из большого 160-битного ключа;

· чередование арифметических операций (сложение и побитовый XOR);

· использование внутреннего состояния системы, которое явно не проявляется в потоке данных (значения n1, n2, n3 и n4, которые изменяют регистры в конце каждой итерации);

· использование отличных друг от друга операций в зависимости от этапа итерации и ее номера.

Для шифрования и расшифрования каждого байта текста шифр SEAL требует около четырех машинных тактов. Он работает со скоростью примерно 58 Мбит/с на 32-битном процессоре с тактовой частотой 50 МГц и является одним из самых быстрых шифров.

2.1.3 Шифр VMPC

Это потоковый шифр, применяющийся в некоторых системах защиты информации в компьютерных сетях. Шифр разработан криптографом Бартошем Зольтаком в качестве усиленного варианта популярного шифра RC4. Алгоритм VMPC строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов. Основные преимущества шифра, как и RC4 - высокая скорость работы, переменный размер ключа и вектора инициализации (от 128 до 512 бит включительно), простота реализации (буквально несколько десятков строк кода).

Рисунок 2.3 - Реализация VMPC

Основа шифра - генератор псевдослучайных чисел, базой которого является односторонняя необратимая функция VMPC.

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

Данная проблема шифром VMPC в некотором роде решается использованием уникального вектора инициализации для каждого зашифрованного потока.

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

2.1.4 Шифр Trivium

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

Шифр был представлен в декабре 2008 года как часть портфолио европейского проекта eSTREAM, по профилю 2 (аппаратно ориентированные шифры). Авторами шифра являются Кристоф Де Канниэр и Барт Пренил.

Данный потоковый шифр генерирует вплоть до 264 выходного потока из 80 бит ключа и 80 бит IV. Это самый простой шифр проекта eSTREAМ, который показывает отличные результаты по криптоустойчивости.

Изначальное состояние Trivium представляет собой 3 сдвиговых регистра суммарной длины в 288 бит. Каждый такт происходит изменение битов в регистрах сдвига путем нелинейной комбинации прямой и обратной связи. Для инициализации шифра ключ K и инициализирующий вектор IV записываются в 2 из 3х регистров и происходит исполнение алгоритма в течение 4х288 = 1152 раз, что гарантирует зависимость каждого бита начального состояния от каждого бита ключа и каждого бита инициализирующего вектора.

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

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

Программная интерпретация данного алгоритма также достаточно эффективна. Реализация Trivium на языке C на процессоре AthlonXP 1600+ позволяет получить скорость шифрования более 2,4Мбит/с.

В отличие от ранних потоковых шифров, как например RC4, алгоритм Trivium, кроме закрытого ключа (K) также имеет инициализирующий вектор (IV), который является открытым ключом. Применение IV позволяет проводить множество независимых сеансов шифровки/расшифровки используя всего лишь 1 ключ и несколько инициализирующих векторов (по одному для каждого сеанса).

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

Существуют исследования методов атак (например, кубическая атака), которые близки по эффективности к перебору. Кроме того, существует метод атаки, позволяющий восстановить K из IV и ключевого потока. Сложность данной атаки равна 2135 и незначительно уменьшается при увеличении количества инициализирующих векторов, использовавшихся с одним ключом. Возможны также атаки с исследованием псевдослучайной последовательности ключевого потока с целью нахождения закономерностей и предсказания последующих бит потока, но данные атаки требуют решения сложных нелинейных уравнений. Наименьшая полученная сложность такой атаки составляет 2164.

2.2 Применение генераторов ПСП

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

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

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

Приведем конкретные примеры использования случайных чисел в криптологии:

- сеансовые и другие ключи для симметричных криптосистем, таких как DES, Blowfish;

- стартовые значения для программ генерации ряда математических величин в ассиметричных криптосистемах, например, «больших простых чисел» в криптосистемах RSA, El-Gamal;

- случайные слова, комбинируемые с парольными словами для нарушения «атаки угадывания» пароля криптоаналитиком;

- вектор инициализации для блочных криптосистем, работающих в режиме обратной связи;

- случайные значения параметров для многих систем электронной цифровой подписи;

- случайные выборы в протоколах аутентификации, например в протоколе Kerberos;

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

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

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

- период гаммы должен быть достаточно большим для шифрования сообщений различной длины;

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

- генерирование гаммы не должно вызывать больших технических сложностей.

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

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

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

2.3 Линейный конгруэнтный генератор

Из известных процедур генерации последовательности псевдослучайных целых чисел наиболее часто применяется так называемый линейный конгруэнтный генератор. Этот генератор вырабатывает последовательность псевдослучайных чисел Y1, Y2, .... Yi-1,Yi, ..., используя соотношение

(2.3)

где Yi - i-e (текущее) число последовательности; Yi-1 - предыдущее число последовательности; а,b и m - константы; m - модуль;

а - множитель (коэффициент); b - приращение; Yo - порождающее число (исходное значение).

Текущее псевдослучайное число Yi получают из предыдущего числа Yi-1 умножением его на коэффициент а, сложением с приращением b и вычислением остатка от деления на модуль m. Данное уравнение генерирует псевдослучайные числа с периодом повторения, который зависит от выбираемых значений параметров а, и m и может достигать значения m. Если a, b и m выбраны правильно, то генератор будет с максимальным периодом (например, b должно быть взаимно простым с m и коэффициент а должен быть нечетным числом). Значение модуля m берется равным 2n либо равным простому числу, например m=231-1.

Преимуществом линейных конгруэнтных генераторов является их быстрота за счет малого количества операций на бит.

Конгруэнтные генераторы, работающие по алгоритму, предложенному

Национальным бюро стандартов США, используются, в частности, в системах программирования. Эти генераторы имеют длину периода 224 и обладают хорошими статистическими свойствами. Однако такая длина периода мала для криптографических применений. Кроме того, доказано, что последовательности, генерируемые конгруэнтными генераторами, не являются криптографически стойкими.

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

2.4 Линейные рекуррентные генераторы

Существует способ генерации последовательностей псевдослучайных чисел на основе линейных рекуррентных соотношений.

Рассмотрим рекуррентные соотношения через их разностные уравнения

(2.4)

(2.5)

где и каждое hi принадлежат полю GF(q).

Решением этих уравнений является последовательность элементов поля GF(q). Соотношение (2.5) определяет правило вычисления аk по известным значениям величин Затем по известным значениям находят ak+1 и т.д. В результате по начальным значениям можно построить бесконечную последовательность, причем каждый ее последующий член определяется из k предыдущих. Последовательности такого вида легко реализуются на компьютере, при этом реализация получается особенно простой, если все hi и ai значения 0 и 1 из поля GF(2).

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

Исходные величины помещаются в разряды сдвигового регистра, последовательные сдвиги содержимого которого соответствуют вычислению последовательных символов, при этом выход после i-го сдвига равен аi. Данное устройство называют генератором последовательности чисел, построенным на базе линейного сдвигового регистра с обратной связью (linear feedback shift register, LFSR).

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 2.4 - Генератор с регистром сдвига

2.4.1 Регистры Фибоначчи

В литературе значительно чаще обращаются к регистрам Фибоначчи. Функция обратной связи здесь - простое сложение операцией XOR (исключающее или) определенных бит регистра. Перечень этих битов называется отводной последовательностью.

Рисунок 2.5 - Регистр Фибоначчи

N-битовый LFSR может находиться в одном из внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом битов. Только при определенных отводных последовательностях LFSR циклически пройдет через все внутренних состояний. Такие LFSR являются LFSR с максимальным периодом. Для того, чтобы LFSR имел максимальный период, многочлен, образованный от отводной последовательности и константы 1, должен быть примитивен по модулю 2. Степень многочлена является длиной сдвигового регистра. Примитивный многочлен степени - это неприводимый многочлен, который является делителем , но не является делителем для всех , являющихся делителями .

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

Примеры некоторых примитивных полиномов приведены в таблице 2.1.

Таблица 2.1 - Примитивные полиномы

Длина пери ода	Многочлен
22-1	(2, 1, 0)
23-1	(3, 1, 0)
24-1	(4, 1, 0)
25-1	(5, 2, 0)
26-1	(6, 1, 0)
27-1	(7, 1, 0)
28-1	(8, 6, 5, 1, 0)
211-1	(11, 2, 0)
212-1	(12, 7, 4, 3, 0)
213-1	(13, 4, 3, 1, 0)
214-1	(14,12, 11, 1, 0)
216-1	(16, 5, 3,2, 0)
218-1	(18, 7, 0)
220-1	(20,3,0)
221-1	(21,2,0)
222-1	(22,1,0)
223-1	(23,5,0)
224-1	(24, 4, 3, 1, 0)
225-1	(25,3,0)
227-1	(27,8,7,1,0)
230-1	(30,16,15,1,0)
231-1	(31,3,0)
232-1	(32, 7, 6, 2, 0)

Например, запись (14, 12, 11, 1, 0) означает, что следующий многочлен примитивен по модулю 2: .

Первым числом является длина LFSR. Последнее число всегда равно 0, и его можно опустить. Все числа, за исключением 0, задают отводную последовательность, отсчитываемую от левого края регистра. Продолжая пример, запись (14, 12, 11, 1, 0) означает, что для взятого 32-битового регистра сдвига новый бит генерируется с помощью XOR четырнадцатого, двенадцатого, одиннадцатого и первого битов, то результирующая последовательность будет иметь максимальный период - она пройдет через значений до того, как начнет повторяться.

Каждый элемент таблицы 2.1 определяет два примитивных полинома, поскольку если примитивен ,то примитивен и Например, если примитивен, то примитивен и , или если примитивен, то примитивен и . Математически, если примитивен

, (2.6)

, (2.7)

, (2.8)

, (2.9)

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

2.4.2 Регистры Галуа

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

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

Рисунок 2.6 - Регистр Галуа

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

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

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

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

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

Использование LFSR в программной реализации криптосхем намного проблематичней. Эффективны по скорости лишь прореженные полиномы, но они слабы в отношении корреляционных атак; плотные же полиномы обратной связи слишком неэффективны. Стандартный поточный шифр выдает по одному биту за раз, и этот алгоритм приходится итерировать 64 раза для шифрования того, что DES делает за одну итерацию. Фактически оказывается, что несложный LFSR-алгоритм, типа сжимающего генератора в программной реализации оказывается не быстрее, чем значительно более сложный DES.

2.4.3 Генератор Геффа

В этом генераторе потока ключей используются три LFSR, объединенные нелинейным образом. Два LFSR являются входами мультиплексора, а третий LFSR управляет выходом мультиплексора. Если а1, а2 и а3 - выходы трех LFSR, выход генератора Геффа (Geffe) можно описать как:

b= (a1^a2) + ((-a1)^a3). (2.10)

Если длины LFSR равны n1 n2 и n3, соответственно, то линейная сложность генератора равна:

(n1+1)*n2+n1*n3. (2.11)

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

Рисунок 2.7 - Генератор Геффа

Хотя этот генератор неплохо выглядит на бумаге, он криптографически слаб и не может устоять против корреляционного вскрытия. В 75% времени выход генератора равен выходу LFSR-2. Поэтому, если известны отводные последовательности обратной связи, можно догадаться о начальном значении LFSR-2 и сгенерировать выходную последовательность этого регистра. Тогда можно подсчитать, сколько раз выход LFSR совпадает с выходом генератора. Если начальное значение определено неверно, две последовательности будут согласовываться в 50 процентах времени, а если правильно, то в 75% времени.

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

2.4.4 Генератор «стоп - пошел»

Этот генератор использует выход одного LFSR для управления тактовой частотой другого LFSR. Тактовый вход LFSR-2 управляется выходом LFSR-1,так что LFSR-2 может изменять своё состояние в момент времени t только, если выход LFSR-1 в момент времени t-1 был равен 1.

Рисунок 2.8 - Генератор «стоп - пошёл»

2.4.5 Чередующийся генератор «стоп - пошёл»

В этом генераторе используются три LSFR различной длинны.LSFR-2 тактируется, когда выход LSFR-1равен 1, LSFR-3 тактируется, когда выход LSFR-1равен 0.

Рисунок 2.9 - Чередующийся генератор «стоп - пошел»

У этого генератора большой период и большая линейная сложность.

2.4.6 Каскад Голлмана

Каскад Голлманна, представляет собой усиленную версию генератора "стоп-пошел". Он состоит из последовательности LFSR, тактирование каждого из которых управляется предыдущим LFSR. Если выходом LFSR-1 в момент времени t является 1, то тактируется LFSR-2. Если выходом LFSR-2 в момент времени t является 1, то тактируется LFSR-3, и так далее. Выход последнего LFSR и является выходом генератора.

Если длина всех LFSR одинакова и равна n, линейная сложность системы из k LFSR равна n(2n-1)k-1.

Рисунок 2.10-Каскад Голлмана

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

2.4.7 Аддитивные генераторы

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

Начальное состояние генератора представляет собой массив n-битовых слов: 8-битовых слов, 16-битовых слов, 32-битовых слов, и т.д.: Х1 ,Х2, X3, ..., Хm. Это первоначальное состояние и является ключом. i-ое слово генератора получается как:

Xi = (Xi-a + Xi-a + Хi-c+ + Xi-m) mod 2n (2.12)

При правильном выборе коэффициентов а, b, с, . . . , т период этого генератора не меньше 2n-1. Одним из требований к коэффициентам является то, что младший значащий бит образует LFSR максимальной длины.

Например, (55,24,0) - это примитивный многочлен mod 2 из 14-й. Это означает, что длина следующего аддитивного генератора максимальна.

Xi = (Xi-55 +Xi-24) mod2n (2.13)

2.4.7.1 Fish

Fish - это аддитивный генератор, основанный на методах, используемых в прореживаемом генераторе. Он выдает поток 32-битовых слов, которые могут быть использованы (с помощью XOR) с потоком открытого текста для получения шифротекста или с потоком шифротекста для получения открытого текста. Название алгоритма представляет собой сокращение от Fibonacci shrinking generator - прореживаемый генератор Фиббоначи.

Во-первых используйте два следующих аддитивных генератора. Ключом является начальные состояния этих генераторов.

Ai = (Ai-55+Ai-24) mod232

Bi = (Bi-52 +Bi-19) mod 232

Эти последовательности прореживаются попарно в зависимости от младшего значащего бита Вi: если его значение равно 1, то пара используется, если 0 - игнорируется. Сj- это последовательность используемых слов Ai , a Dj - это последовательность используемых слов Вi . Для генерации двух 32-битовых слов-результатов К2j и K2j+1 эти слова используются парами - C2j, C2j+1, D2j, D2j+1.

E2j = C2j + (D2j, ^ D2j+1)

F2j = D2j+1 ^ (Ej, ^ C2j+1)

K2j = E2j + F2j

K2j+1 = C2j+1 + F2j

Этот алгоритм быстр. на процессоре i486/33 реализация Fish на языке С шифрует данные со скоростью 15-Мбит/с. К сожалению он также не безопасен, порядок вскрытия составляет около 240.

2.4.7.2 Mush

Mush представляет собой взаимно прореживающий генератор . Его работу объяснить легко. Возьмем два аддитивных генератора: А и В. Если бит переноса А установлен, тактируется В. Если бит переноса В установлен, тактируется А. Тактируем А и при переполнении устанавливаем бит переноса. Тактируем В и при переполнении устанавливаем бит переноса. Окончательным выходом является XOR выходов А и В. Проще всего использовать те же генераторы, что и в Fish:

Ai = (Ai-55+Ai-24) mod232

Bi = (Bi-52 +Bi-19) mod 232

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

3. МЕТОДЫ ОЦЕНКИ КАЧЕСТВА ГЕНЕРАТОРОВ ПСП

Для исследования ПСП применяются две группы тестов.

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

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

3.1 Графические тесты

а) Гистограмма. Гистограмма позволяет определить равномерность распределения символов в тестируемой последовательности, а также оценить частоту появления конкретного символа. Данный тест незаменим при проверке последовательности на "случайность", а также при исследовании генераторов с произвольным законом распределения символов. Для того чтобы последовательность удовлетворяла свойствам случайности, необходимо, чтобы в ней присутствовали все символы, при этом разброс частот появления символов стремился к нулю. Рассматриваемый тест может принести пользу также в тех случаях, когда оценивается качество последовательности с законом распределения, отличным от равномерного, либо последовательности, в которой некоторые символы вообще отсутствуют, и т. д.

б) Распределение на плоскости. Тест позволяет оценивать равномерность и независимость распределения символов в исследуемой последовательности. Для построения графической зависимости на поле размером 256х256 наносятся точки с координатами

(Qi; Qi+1)

где Qi, - i-й элемент последовательности, , т - длина последовательности. Далее анализируется полученная картина. В случае некачественной последовательности точки распределены неравномерно, либо наблюдается некий узор.

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

в) Байтовая АКФ. Тест проверяет взаимонезависимость элементов изучаемой последовательности на основе анализа всплесков корреляции. Для расчета автокорреляционной функции последовательность нормируется. Пусть [q7…q1q0] -двоичная запись элемента последовательности длиной m, qj {0, 1}, . Тогда нормированное значение этого элемента вычисляется как

(3.1)

После этого вычисляются всплески корреляции

(3.2)

Нетрудно заметить, что при = 0 и = m значение К ()= 1. Во всех остальных случаях для качественной ПСП значения К() должны стремиться к нулю.

г) Битовая АКФ. Тест проверяет взаимонезависимость битов последовательности. Сначала двоичное представление последовательности нормируется: 1 1, 0 -1. Затем вычисляются всплески корреляции по формуле

(3.3)

где М - размер последовательности в битах, а - i-й бит нормированной последовательности. При =0 и = М значение К ()= 1. Во всех остальных случаях для качественной ПСП значения К () должны стремиться к нулю.

д) Проверка на монотонность. Тест проверяет равномерность распределения символов в изучаемой последовательности на основе анализа длин участков возрастания и убывания. В качественной ПСП разброс длин этих участков должен стремиться к нулю.

е) Проверка 0 и 1. Тест проверяет равномерность распределения символов в изучаемой последовательности. Для этого подсчитывается число 0 и 1. В качественной ПСП разброс между количеством 0 и 1 близок к нулю.

ж) Проверка серий. Тест проверяет равномерность распределения символов в изучаемой последовательности, анализируя частоту встречаемости биграмм (00, 01, 10, 11) и триграмм (000, 001, 010, 011, 100, 101, 110, 111). В качественной ПСП разброс между частотами встречаемости биграмм (триграмм) должен стремиться к нулю.

3.2 Оценочные тесты

а) Критерий . Пусть результаты испытаний таковы, что их можно разделить на k категорий. Проводится п независимых испытаний. Обозначим вероятность того, что результат испытания попадет в s-ю категорию, как ps , а число испытаний, которые реально попали в s-ю категорию, как Ys . Сформируем статистику

(3.4)

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

Например, для p= 5% и v = 10 таблица дает значение х = 18.31; это означает что V> 18.31 только в 5% всех случаев.

Для анализа полученного результата используются различные подходы. В [43] предлагается следующий. Если V меньше значения, соответствующего р = 99 %, или больше значения, соответствующего р = 1 %, то результаты бракуются, как недостаточно случайные. Если р лежит между 99 и 95% или между 5 и 1%, то результаты считаются "подозрительными", при значениях, заключенных между 95 и 90 % или 10 и 5 %, результаты "слегка подозрительны"; в остальных случаях результаты считаются случайными.

Однако при таком подходе будет забракована и по-настоящему случайная последовательность, для которой вероятность будет стремиться к 100%. Кроме того, нижняя граница прохождения тестов взята неоправданно малой. Поэтому логичнее оценивать результаты следующим образом. В зависимости от требования к генератору выбирается нижняя граница Рd. Результаты, для которых выполняется p<Pd , бракуются как неслучайные, в противном случае тест пройден.

б) Проверка частот. Тест проверяет равномерность появления символов в изучаемой последовательности. Подсчитывается, сколько раз встречается каждый символ - Ns (s=), после чего применяется критерий с числом категорий, равным 256, и вероятностями 1/256 в каждой категории

(3.5)

где m - число анализируемых байтов. Полученные результаты анализируются при помощи таблицы распределения с числом степеней свободы, равным 255. Имеет смысл провести и проверку частот появления полубайтов. Для этого подсчитывается, сколько раз встречается каждый полубайт - Ns (s=), после чего применяется критерий с числом категорий, равным 16, и вероятностями 1/16 в каждой категории

(3.6)

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

в) Анализ перестановок. Тест проверяет равномерность распределения чисел в исходной последовательности. Разделим исходную последовательность на n групп по t элементов. В каждой группе возможно t! вариантов относительного расположения чисел. Подсчитывается, сколько раз встречается каждое конкретное относительное расположение - Ns , после чего применяется критерий с числом категорий, равным t!, и вероятностями 1/t! в каждой категории.

(3.7)

где m - число анализируемых байтов. Полученные результаты анализируются при помощи таблицы распределения с числом степеней свободы, равным t!-1.

г) Проверка сегментов. Данный тест проверяет равномерность распределения символов в исходной последовательности. Конкретное значение байта [0..255] может принадлежать различным сегментам, [0..127] и [128..255] например. Анализируются следующие друг за другом пары чисел, и определяется принадлежность каждого числа к определенному сегменту.

Пусть имеется два сегмента [0..127] и [128..255]. Каждая пара распределяется по категориям: