Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Избежать этого можно, шифруя в качестве первого блока какие-то случайные данные . Этот блок случайных данных называется вектором инициализации (initialization vector, IV), инициализирующей переменной или на- чальным значением сцепления. IV не имеет никакого смыслового значения, он используется только для того, чтобы сделать каждое сообщение уникальным . Когда получатель расшифровывает этот блок, он испольтзует его только для заполнения регистра обратной связи . Хорошим IV служит метка времени. Или используйте какие- нибудь случайные биты. С использованием IV сообщения с идентичным открытым текстом при шифровании переходят в сообщения с различным шифротекстом. Следовательно, злоумышленник не сможет предпринять повтор блока, и затру д- нится создание шифровальной книги. Хотя рекомендуется для каждого сообщения, шифруемого одним и тем же ключом, выбирать уникальный IV, это требование не является обязательным . IV не должен храниться в секрете, он может передаваться открыто вместе с шифротекстом . Если вы не по- нимаете почему, рассмотрите следующий довод . Пусть наше сообщение состоит из нескольких блоков : B 1 , B 2 , ..., B i . B 1 шифруется вместе с IV. B 2 шифруется с использованием шифротекста B 1 в роли IV. B 3 шифруется с использованием шифротекста B 2 в роли IV, и так далее. Итак, если количество блоков - n, то n-1 "векторов ини- циализации" открыты, даже если первоначальный IV хранится в секрете. Поэтому причин хранить в секрете IV нет, IV - это просто блок-заглушка, можно считать его нулевым блоком сцепления B 0 Набивка Набивка используется также, как и в режиме ECB, но в некоторых приложениях размер шифротекст должен в точности совпадать с размером открытого текста . Может быть, зашифрованный файл должен занять в точн о- сти тот же объем памяти, что и файл открытого текста . В этом случае последний короткий блок придется ши ф- ровать иначе. Пусть последний блок состоит из l битов. Зашифровав последний полный блок, снова зашифруйте шифротекст, выберите старшие l битов и выполните для них и короткого блока операцию XOR, создавая шиф- ротекст. Эта процедура показана на 5-й. C n-2 P n-2 E k C n-1 P n-1 E k E k C n (j битов длиной) P n (j битов длиной) Выбрать левые j битов Рис. 9-4. Шифрование короткого последнего блока в режиме CBС. Слабость этого способа в том, что хотя Мэллори не сможет раскрыть последний блок шифротекста, он м о- жет систематически изменять его, меняя отдельные биты шифротекста . Если последние несколько битов шиф- ротекста содержат важную информацию, это опасно. Если последние биты просто содержат совет по домово д- ству, то ничего страшного. Лучшим способом является похищение щифротекста (см. 4th) [402]. P n-1 - последний полный блок открытого текста, P n - заключительный, короткий блок открытого текста . С n-1 - последний полный блок шифротекста, С n - заключительный, короткий блок шифротекста . C' - это просто промежуточный результат, не являющийся ч а- стью переданного шифротекста. Преимуществом этого метода является то, что все биты открытого текста соо б- щения проходят через алгоритм шифрования . E k P n-1 C' C n E k C n-1 ? P n D k C n-1 C' P n D k P n-1 C' C n C n-2 ? С n Рис. 9-5. Похищение шифротекста в режиме CBС. Распространение ошибки Режим CBC характеризуется прямой обратной связью шифротекста при шифровании и инверсной обрат- ной связью шифротекста при дешифрировании. При этом приложения должны уметь бороться с ошибками . Единственная битовая ошибка в блоке открытого текста повлияет на данный блок шифротекста и все посл е- дующие блоки шифротекста. Это не важно, потому что дешифрирование инвертирует этот эффект, и восстано в- ленный открытый текст будет содержать ту же единственную ошибку . Чаще встречаются ошибки шифротекста. Они легко появляются из-за шума линий передачи или сбоев ус т- ройств хранения. В режиме CBC ошибка одного бита шифротекста влияет на один блок и один бит восстано в- ленного открытого текста. Блок, соответствующий содержащему ошибку блоку шифротекста, искажается полн о- стью. В следующем блоке искажается единственный бит, находящийся в той же позиции, что и ощибочный бит . Это свойство превращения малой ошибки шифротекста в большую ошибку открытого текста называется распространением ошибки. Это является главным недостатком. Эта ошибка не влияет на блоки, расположе н- ные через один от испорченного и далее, поэтому режим CBC является самовосстанавливающимся. Ошибка влияет на два блока, но система продолжает работать правильно для всех последующих блоков . CBC представ- ляет собой пример блочного шифра, используемого в самосинхронизирующейся манере, но только на блоковом уровне. Хотя режим CBC быстро восстанавливается от битового сбоя, он абсолютно не устойчив к ошибкам синхр о- низации. Если в потоке шифротекста теряется или добавляется бит , то положение всех последующих блоков сдвигаются на один бит, и на выходе дешифрирования будет сплошной мусор . Любая криптосистема, исполь- зующая режим CBC должна обеспечивать целостность блочной структуры либо при помощи кадров, либо с о- храняя данные в структуры из нескольких блоков. Вопросы безопасности Ряд возможных проблем обуславливаются структурой CBC. Во первых, так как блок шифротекста достаточ- но просто влияет на следующий блок, Мэллори может тайно добавлять блоки к концу зашифрованного сообщ е- ния. Конечно, при дешифрировании они превратятся в чепуху, но в некоторых ситуациях это нежелательно . При использовании CBC вы должны структурировать ваш открытый текст так, чтобы вы знали, где находя т- ся концы сообщений, и могли обнаружить добавление лишних блоков . Во вторых, Мэллори может изменить блок шифротекста, изменения определенным образом блоки расши ф- рованного открытого текста. Например, если Мэллори изменит один бит шифротекста, весь блок будет расши ф- рован неправильно, а в следующем блоке в соответствующей позиции будет неправильный бит . Возможны си- туации, когда это нежелательно. Открытое сообщения должно обладать некоторой избыточностью или средс т- вами идентификации. Наконец, хотя структура открытого текста маскируется сцеплением , структура очень длинных сообщений все равно будет заметна. Парадокс дня рождения предсказывает, что после 2 m/2 блоков, где m - размер блока, появ- ляются одинаковые блоки. Для 64-битового блока длина такого сообщения примерно равны 32 Гбайтам . По- добная проблема возникает только для сообщений немаленького размера . 9.4 Потоковые шифры Потоковые шифры преобразуют открытый текст в шифротекст по одному биту за операцию . Простейшая реализация потокового шифра показана на 3-й. Генератор потока ключей (иногда называемый генератором с бегущим ключом) выдает поток битов: k 1 , k 2 , k 3 , ..., k i . Этот поток ключей (иногда называемый бегущим ключом) и поток битов открытого текста, p 1 , p 2 , p 3 , ..., p i , подвергаются операции "исключающее или", и в р е- зультате получаетсяы поток битов шифротекста. c i =p i ? k i При дешифрировании операция XOR выполняется над битами шифротекста и тем же самым потоком кл ю- чей для восстановления битов открытого текста . p i = c i ? k i Так как p i ? k i ? k i = p i это работает правильно. Безопасность системы полностью зависит от свойств генератора потока ключей . Если генератор потока клю- чей выдает бесконечную строку нулей, шифротекст будет совпадать с открытым текстом, и все операция будет бессмысленна. Если генератор потока ключей выплевывает повторяющийся 16-битовый шаблон, алгоритм б у- дет являться простым XOR с пренебрежимо малой безопасностью (см. раздел 1.4). Если генератор потока клю- чей выплевывает бесконечный поток случайных (по настоящему, а не псевдослучайных - см. раздел 2.8) битов, вы получаете одноразовый блокнот и идеальную безопасность . На деле безопасность потокового шифра находится где-то между простым XOR и одноразовым блокнотом. Генератор потока ключей создает битовый поток, который похож на случайный, но в действительности дете р- минирован и может быть безошибочно воспроизведен при дешифрировании . Чем ближе выход генератора по- тока ключей к случайному, тем больше времени потребуется криптоаналитику, чтобы взломать шифр . P i P i C i Дешифрирование Шифрование Открытый текст Открытый текст Шифротекст Поток ключей K i Генератор потока ключей Поток ключей K i Генератор потока ключей Рис. 9-6. Потоковый шифр Однако, если генератор потока ключей при каждом включении создает один и тот же битовый поток , то ис- пользующую его криптосистему взломать нетрудно . Покажем на примере, почему это так. Если к Еве попал шифротекст и соответствующий открытый текст, то она, выполняя операцию XOR над от- крытым текстом и шифротекстом, раскрывает поток ключей . Или, если у нее есть два различных шифротекста, зашифрованных одинаковым ключом, она может выполнить над ними операцию XOR, получая два открытых текста сообщений, над которыми выполнена операция XOR. Это нетрудно взломать, и затем она может пол у- чить поток ключей, выполняя операцию XOR над одним из открытых текстов и шифротекстом . Теперь, перехватив любое другое шифрованное сообщение, она сможет расшифровать его, используя пол у- ченный поток ключей. Кроме того, она может расшифровать и прочитать любое из ранее перехваченных соо б- щений. Когда Ева получит пару открытый текст/шифротекст, она сможет читать все . Поэтому для всех потоковых шифров используются ключи. Выход генератора потока ключей является фун к- цией ключа. Теперь, если Ева получит пару открытый текст/шифротекст , она сможет читать только те сообще- ния, которые зашифрованы тем же ключом . Измените ключ, и противнику придется начать все сначала . Пото- ковые шифры особенно полезны для шифрования бесконечных потоков коммуникационного трафика, напр и- мер, канала Т1, связывающего два компьютера. Генератор потока ключей состоит из трех основных частей (см. 2nd). Внутреннее состояние описывает теку- щее состояние генератора потока ключей. Два генератора потока ключей, с одинаковым ключом и одинаковым внутренним состоянием, выдают одинаковые потоки ключей. Функция выхода по внутреннему состоянию ген е- рирует бит потока ключей. Функция следующего состояния по внутреннему состоянию генерирует новое вну т- реннее состояние. K i КЛЮЧ K Функция выхода Функция следующего состояния Внутреннее состояние Рис. 9-7. Устройство генератора потока ключей. 9.5 Самосинхронизирующиеся потоковые шифры В самосинхронизирующихся потоковых шифрах каждый бит потока ключей является функцией фиксир о- ванного числа предыдущих битов шифротекста [1378]. Военные называют этот шифр автоключом шифротек- ста (ciphertext auto key, CTAK). Основная идея была запатентована в 1946 [667]. Самосинхронизирующийся потоковый шифр показан на 1-й. Внутреннее состояние является функцией пр е- дыдущих n битов шифротекста. Криптографически сложной является выходная функция, которая использует внутреннее состояние для генерации бита потока ключей . P i P i C i K Функция выхода Внутреннее состояние Функция выхода Внутреннее состояние Рис. 9-8. Самосинхронизирующийся генератор потока ключей. Так как внутреннее состояние полностью зависит от предыдущих n шифротекста, дешифрирующий генера- тор потока ключей автоматически синхронизируется с шифрующим генератором потока ключей, приняв n битов шифротекста. В интеллектуальных реализациях этого режима каждое сообщение начинается случайным заголовком дл и- ной n битов. Этот заголовок шифруется, передается и затем расшифровывается . Расшифровка будет неправиль- ной, но после этих n битов оба генератора потока ключей будут синхронизированы . Слабой стороной самосинхронизирующегося потокового шифра является распространение ошибки . Для ка- ждого бита шифротекста, испорченного при передаче, дешифрирующий генератор потока ключей выдает n не- правильных битов потока ключей. Следовательно, каждому неправильному биту шифротекста соответствуют n ошибок в открытом тексте, пока испорченный бит не перестанет влиять на внутреннее состояние . Вопросы безопасности Самосинхронизирующиеся потоковые шифры также чувствительны к вскрытию повторной передачей . Сна- чала Мэллори записывает несколько битов шифротекста . Затем, позднее, он вставляет эту запись в текущий трафик. После выдачи некоторой чепухи, пока принимающая сторона синхронизируется с вставленной записью , старый шифротекст будет расшифрован как нормальный . У принимающей стороны нет способа узнать, что п о- лученные данные являются повторно передаваемой записью . Если не используются метки времени, Мэллори может убедить банк снова и снова зачислять деньги на его счет , повторно передавая одно и то же сообщение (конечно, при условии, что ключ не менялся ). Другие слабые места этой схемы могут стать заметны при очень частой пересинхронизации [408]. 9.6 Режим обратной связи по шифру Блочный шифр также может быть реализованы как самосинхронизирующийся потоковый шифр, такой р е- жим называется режимом обратной связи по шифру ( cipher-feedback, CFB). В режиме CBC шифрование не мог- ло начаться, пока не получен целый блок данных. Это создает проблемы для некоторых сетевых приложений . Например, в безопасной сетевой среде терминал должен иметь возможность передавать главному компьютеру каждый символ сразу, как только он введен . Если данные нужно обрабатывать байтами, режим CBC также не работает. В режиме CFB единица зашифрованных данных может быть меньше размера блока . В следующем примере каждый раз шифруется только один символ ASCII (это называется 8-битовым шифрованием ), но в числе 8 нет ничего волшебного. Вы можете шифровать данные по одному биту с помощью 1-битового CFB, хотя использо- вание для единственного бита полного шифрования блочным шифром потребует много ресурсов, потоковый шифр в этом случае был бы идеей получше . (Уменьшение количества циклов блочного фильтра для повышения скорости не рекомендуется [1269].) Можно также использовать 64-битовый CFB, или любой n-битовый CFB, где n больше или равно размеру блока. На 0-й показан 8-битовый режим CFB, работающий с 64-битовым алгоритмом . Блочный алгоритм в режиме CFB работает с очередью, размер которой равен размеру используемого блока . Сначала очередь заполнена IV, как и в режиме CBC. Очередь шифруется и для крайних левых восьми битов результата выполняется XOR с первыми 8-битовым символом открытого текста для получения первого 8-битового символа шифротекста. Т е- перь этот символ передается. Те же восемь битов также передвигаются на место крайних правых восьми битов очереди, а крайними левыми битами становятся следующие восемь битов . Крайние восемь левых битов отбра- сывается. Следующий символ открытого текста шифруется тем же способом . Дешифрирование является обрат- ным процессом. И шифрующей, и дешифрирующей стороной блочный алгоритм используется в режиме шифр о- вания. Если размер блока алгоритма - n, то -битовый CFB выглядит следующим образом (см. -1-й): C i = P i ?E k (C i-1 ) P i = C i ?E k (C i-1 ) Самый левый байт Сдвиговый регистр c i p i k i Шифрование (а) Шифрование Ключ К Самый левый байт Сдвиговый регистр p i c i б) Дешифрирование Ключ К k i Шифрование Рис. 9-9. Режим 8-битовой обратной связи по шифру. P n-1 E k C n-1 P n E k C n P n+1 C n+1 Рис. 9-10. n-битовый CBF с n-битовым алгоритмом. Как и режим CBC, режим CFB связывает вместе символы открытого текста так, что шифротекст зависит от всего предшествующего открытого текста . Вектор инициализации Для инициализации процесса CFB в качестве входного блока алгоритма может использоваться вектор ин и- циализации IV. Как и в режиме CBC IV не нужно хранить в секрете. Однако IV должен быть уникальным. (В отличие от режима CBC, где IV не обязан быть уникальным, хотя это и желательно.) Если IV в режиме CFB не уникален, криптоаналитик может раскрыть соответствующий о т- крытый текст. IV должен меняться для каждого сообщения. Это может быть последовательный номер, увелич и- вающийся для каждого нового сообщения и не повторяющийся в течение времени жизни ключа . Если данные шифруются с целью последующего хранения, IV может быть функцией индекса, используемого для поиска да н- ных. Распространение ошибки В режиме CFB ошибка в открытом тексте влияет на весь последующий шифротекст, но самоустраняется при дешифрировании. Гораздо интереснее ошибка в шифротексте . Первым эффектом сбоя бита шифротекста явл я- ется сбой одного бита открытого текста. Затем ошибка попадает в сдвиговый регистр , и пока сбойный бит не выйдет из регистра, будет формироваться неправильный шифротекст . В 8-битовом режиме CFB из-за сбоя единственного бита портятся 9 байтов расшифрованного открытого текста . Потом система восстанавливается, и весь последующий шифротекст расшифровывается правильно . В общем случай в n-битовом режиме CFB одна ошибка шифротекста влияет на дешифрирование текущего и следующих m/n-l блоков, где m - размер блока. Более тонкой проблемой, связанной с такого рода распространением ошибки, является то, что если Мэллори знает открытый текст сообщения, он может поиграть битами данного блока, заставляя их расшифровываться в нужные ему данные. Следующий блок при дешифрировании превратится в чепуху , но вред уже будет причинен. К тому же, он может, оставаясь необнаруженным, менять последние биты сообщения . CFB самовосстанавливается и после ошибок синхронизации . Ошибка попадает в сдвиговый регистр и, пока она находится там, портит 8 байтов данных . CFB представляет собой пример блочного шифра, который можно использовать как самосинхронизирующийся потоковый шифр (на уровне блоков ). 9.7 Синхронные потоковые шифры В синхронном потоковом шифре поток ключей генерируется независимо от потока сообщения . Военные называют этот шифр ключевым автоключом (Key Auto-Key, KAK). При шифровании генератор потока клю- чей один за другим выдает биты потока ключей . При дешифрировании другой генератор потока ключей один за другим выдает идентичные биты потока ключей . Это работает, если оба генератора синхронизированы . Если один из них пропускает один из циклов, или если бит шифротекста теряется при передаче , то после ошибки ка- ждый символ шифротекста будет расшифрован неправильно . |