Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Почему даже в книге по криптографии снова эти докучливые рассуждения о генерации случайных чисел? Генератор случайных чисел встроен в каждый компилятор, обычный вызов функции. Почему бы не использ о- вать его? К сожалению, эти генераторы случайных чисел почти наверняка недостаточно безопасны для крипт о- графии и, возможно, даже не совсем случайны . Большинство из них весьма плохи. Генераторы случайных чисел на самом деле совсем не случайны, потому что им и не нужно быть такими . Для большинства приложений, например, компьютерных игр, требуется так мало случайных чисел, что их н е- случайность вряд ли будет заметна. Однако, криптография очень чувствительна к свойствам генераторов сл у- чайных чисел. Примените плохой генератор, и у вас появятся таинственные корреляции и странные результаты [1231, 1238]. Если ваша безопасность зависит от генератора случайных чисел, таинственные корреляции и странные результаты являются абсолютно не тем, чего бы вы желали добиться. Проблема в том, что генератор случайных чисел не создает случайной последовательности . Он, возможно, не выдает ничего даже отдаленно напоминающего случайную последовательность . Конечно, невозможно созда- вать на компьютере что-то по настоящему случайное. Дональд Кнут приписывал фон Нейману следующие слова: "Каждый, кто занимается арифметическими методами получения случайных чисел, определенно грешит " [863]. Компьютеры - это детерминированные бестии : закладывается известный материал, выполняются полн о- стью предсказуемые действия, и что-то отличное выползает с другого конца. Подача одного и того же на вход в двух различных случаях приведет к одному и тому же результату . Заложите одинаковые исходные данные в два идентичных компьютера, и оба они подсчитают одно и то же. Компьютер может находиться только в огран и- ченном числе состояний (очень большом, но все же ограниченном) , и выдаваемый результат всегда будет строго определяться исходными данными и текущим состоянием компьютера . Это значит, что любой генератор слу- чайных чисел на компьютере (по меньшей мере, на конечном автомате), по определению, периодичен. А все, что периодично, по определению, предсказуемо . А все, что предсказуемо, не может быть случайным . Для на- стоящего генератора случайных чисел нужно подавать на вход что-нибудь случайное, компьютер же не может обеспечить это требование. Псевдослучайные последовательности Лучшее, что может сделать компьютер - это генератор псевдослучайных последовательностей. Что это такое? Многие пытались дать его формальное определение, но я уклонюсь от этого. Псевдослучайная послед о- вательность - это что-то, выглядящее как случайное . Период последовательности должен быть достаточно в е- лик, поэтому конечная последовательность разумной длины - которая в действительности и используется - не периодична. Если вам нужен миллиард случайных бит, не пользуйтесь генератором последовательности, повт о- ряющейся каждые шестнадцать тысяч бит . Эти относительно короткие непериодические подпоследовательности должны быть, насколько это возможно, неотличимы от случайных последовательностей . Например, в них должно быть примерно одинаковое количество единиц и нулей, около половины серий (последовательностей одинаковых бит) должны быть единичной длины , четверть - состоять из двух бит, восьмая часть - из трех, и т.д. Эти последовательности должны быть несжимаемы . Распределение длин серий для нулей и единиц должно быть одинаковым [643, 863, 99, 1357]. Эти свойства могут быть измерены опытным путем и затем сравнены с ожидаемыми статистически с помощью статистики хи-квадрат . Для наших целей генератор последовательн о- сти считается псевдослучайным, если он обладает следующим свойством : 1. Он выглядит случайно. Это означает, что он проходит все тесты на случайность, которые нам удалось найти. (Начните с приведенных в [863].) Множество усилий было затрачено на создание хороших псевдослучайных последовательностей на компь ю- тере. Обсуждение генераторов в большом количестве можно найти в академической литературе вместе с ра з- личными тестами на случайность. Все эти генераторы периодичны (этого невозможно избежать), но, если их период 2 256 и выше, они могут быть использованы в самых серьезных приложениях . Проблема именно в этих таинственных корреляциях и странных результатах . Каждый генератор псевдослу- чайных последовательностей создает такие странности, если вы используете его определенным образом. А это именно то, что нужно криптоаналитику для взлома системы . Криптографически безопасные псевдослучайные последовательности Криптографические приложения предъявляют к генератору псевдослучайных последовательностей более высокие требования по сравнению с другими приложениями . Криптографическая случайность не ограничивае т- ся статистической случайностью, хотя и включает ее . Чтобы последовательность была криптографически безопасной псевдослучайной последовательностью, она должна обладать следующим свойством : 2. Она непредсказуема. Должно быть очень трудно (с точки зрения применения вычислительных мо щ- ностей) предсказать, каким будет следующий случайный бит, даже если полностью известен алгоритм или устройство, генерирующее последовательность, и все предыдущие биты потока. Криптографически безопасные псевдослучайные последовательности не должны сжиматься..., если вам н е- известен ключ. Ключом обычно является заданное начальное состояние генератора . Как и любой криптографический алгоритм, генераторы криптографически безопасных псевдослучайных п о- следовательностей представляют собой предмет вскрытия . Так же как криптографический алгоритм, может быть взломан и генератор криптографически безопасных псевдослучайных последовательностей . Создание ус- тойчивых к вскрытию генераторов является основой криптографии . Настоящие случайные последовательности Теперь мы вторгаемся в область, принадлежащую философам . Существует ли такая вещь как случайность ? Что такое случайная последовательность? Как узнать, что последовательность случайна ? Является ли "101110100" более случайной чем "l01010101"? Квантовая механика убеждает нас в том, что в реальном мире существует настоящая случайность. Но как сохранить эту случайность в предопределенном мире компьютерных микросхем и конечных автоматов? В сторону философию, с нашей точки зрения генератор последовательности действительно случаен, если он обладает третьим свойством: 3. Создаваемая им последовательность не может быть уверенно воспроизведена. Если вы запускаете г е- нератор случайных чисел дважды с одним и тем же входом (по крайней мере, насколько это в челов е- ческих силах), то вы получите две совершенно независимые случайные последовательности. Выход генератора, удовлетворяющего всем трем приведенным требованиям, будет достаточно хорош для одноразового блокнота, генерации ключа и других криптографических применений, требующих генерации де й- ствительно случайных последовательностей . Трудность в том, чтобы понять, действительно ли последовател ь- ность случайна? Если я повторно зашифрую строку, используя DES и заданный ключ, я получу хороший, вы- глядящий случайным образом результат, вы не сможете сказать, что он не случаен, пока вы не наймете взло м- щика DES из NSA. Глава 3 Основные протоколы 3.1 Обмен ключами Общепринятой криптографической техникой является шифрование каждого индивидуального обмена соо б- щениями отдельным ключом. Такой ключ называется сеансовым, так как он используется для единственного отдельного сеанса обмена информацией. В разделе 8.5 говорится о том, что сеансовые ключи полезны, так как время их существования определяется длительностью сеанса связи . Передача этого общего сеансового ключа в руки обменивающихся информацией представляет собой сложную проблему . Обмен ключами с помощью симметричной криптографии Этот протокол предполагает, что пользователи сети, Алиса и Боб, получают секретный ключ от Центра ра с- пределения ключей (Key Distribution Center, KDC) [1260] - Трента наших протоколов. Перед началом протокола эти ключи уже должны быть у пользователей . (Протокол игнорирует очень насущную проблему доставки этих секретных ключей, предполагается, что ключи уже у пользователей, и Мэллори не имеет о них никакой инфо р- мации.) (1) Алиса обращается к Тренту и запрашивает сеансовый ключ для связи с Бобом. (2) Трент генерирует случайный сеансовый ключ. Он зашифровывает две копии ключа: одну для Алисы, а другую - для Боба. Затем Трент посылает обе копии Алисе. (3) Алиса расшифровывает свою копию сеансового ключа. (4) Алиса посылает Бобу его копию сеансового ключа. (5) Боб расшифровывает свою копию сеансового ключа. (6) Алиса и Боб используют этот сеансовый ключ для безопасного обмена информацией. Этот протокол основан на абсолютной надежности Трента, для роли которого больше подходит заслуж и- вающая доверия компьютерная программа, чем заслуживающий доверия человек. Если Мэллори получит до с- туп к Тренту, скомпрометированной окажется вся сеть. В его руках окажутся все секретные ключи, выделенные пользователям Трентом, он сможет прочесть все переданные сообщения, которые ему удалось перехватить, и все будущие сообщения. Ему останется только подключиться к линиям связи и подслушивать зашифрованный поток сообщений. Другой проблемой такой системы является то, что Трент потенциально является ее узким местом. Он должен участвовать в каждом обмене ключами. Если с ним что-то случится, это разрушит всю систему . Обмен ключами, используя криптографию с открытыми ключами Базовая смешанная криптосистема обсуждалась в разделе 1.5. Для согласования сеансового ключа Алиса и Боб применяют криптографию с открытыми ключами, а затем используют этот сеансовый ключ для шифров а- ния данных. В некоторых реализациях подписанные ключи Алисы и Боба доступны в некоторой базе данных . Это значительно облегчает протокол, теперь Алиса, даже если Боб о ней никогда не слышал, может безопасно послать Бобу сообщение: (1) Алиса получает открытый ключ Боба из KDC. (2) Алиса генерирует случайный сеансовый ключ, зашифровывает его открытым ключом Боба и посылает его Бобу. (3) Боб расшифровывает сообщение Алисы с помощью своего закрытого ключа. (4) Алиса и Боб шифруют свой обмен информацией этим сеансовым ключом. Вскрытие "человек-в-середине" В то время, как Ева не может сделать ничего лучшего, чем пытаться взломать алгоритм с открытыми кл ю- чами или выполнить вскрытие с использованием только шифротекста , у Мэллори гораздо больше возможностей. Он не только может подслушать сообщения Алисы и Боба, но и изменить сообщения, удалить сообщения и создать совершенно новые. Мэллори может выдать себя за Боба, сообщающего что-то Алисе, или за Алису, сообщающую что-то Бобу. Вот как будет выполнено вскрытие: (1) Алиса посылает Бобу свой открытый ключ. Мэллори перехватывает его и посылает Бобу свой собстве н- ный открытый ключ. (2) Боб посылает Алисе свой открытый ключ. Мэллори перехватывает его и посылает Алисе Бобу собстве н- ный открытый ключ. (3) Когда Алиса посылает сообщение Бобу, зашифрованное открытым ключом "Боба", Мэллори перехватыв а- ет его. Так как сообщение в действительности зашифровано его собственным открытым ключом, он ра с- шифровывает его, снова зашифровывает открытым ключом Боба и посылает Бобу. (4) Когда Боб посылает сообщение Алисе, зашифрованное открытым ключом "Алисы", Мэллори перехват ы- вает его. Так как сообщение в действительности зашифровано его собственным открытым ключом, он расшифровывает его, снова зашифровывает открытым ключом Алисы и посылает Алисе. Это вскрытие будет работать, даже если открытые ключи Алисы и Боба хранятся в базе данных . Мэллори может перехватить запрос Алисы к базе данных и подменить открытый ключ Боба своим собственным . То же самое он может сделать и с открытым ключом Алисы . Или, еще лучше, он может исподтишка взломать базу данных и подменить открытые ключи Бобо и Алисы своим . Теперь он может преуспеть, просто дождавшись, пока Алиса и Боб начнут обмениваться сообщениями, и начав перехватывать и изменять эти сообщения . Такое вскрытие "человек-в-середине" работает, так как у Алисы и Боба нет способа проверить, действ и- тельно ли они общаются именно друг с другом . Если вмешательство Мэллори не приводит к заметным задер ж- кам в сети, оба корреспондента и не подумают, что кто-то, сидящий между ними, читает всю их секретную по ч- ту. Протокол "держась за руки" Протокол "держась за руки", изобретенный Роном Ривестом (Ron Rivest) и Эди Шамиром (Adi Shamir) [1327], предоставляет неплохую возможность избежать вскрытия "человек-в-середине" . Вот как он работает: (1) Алиса посылает Бобу свой открытый ключ. (2) Боб посылает Алисе свой открытый ключ. (3) Алиса зашифровывает свое сообщение открытым ключом Боба. Половину зашифрованного сообщения она отправляет Бобу. (4) Боб зашифровывает свое сообщение открытым ключом Алисы. Половину зашифрованного сообщения он отправляет Алисе. (5) Алиса отправляет Бобу вторую половину зашифрованного сообщения. (6) Боб складывает две части сообщения Алисы и расшифровывает его с помощью своего закрытого ключа. Боб отправляет Алисе вторую половину своего зашифрованного сообщения. (7) Алиса складывает две части сообщения Боба и расшифровывает его с помощью своего закрытого ключа. Идея в том, что половина зашифрованного сообщения бесполезна без второй половины, она не может быть дешифрирована. Боб не сможет прочитать ни одной части сообщения Алисы до этапа (6), а Алиса не сможет прочитать ни одной части сообщения Боба до этапа (7). Существует множество способов разбить сообщение на части: — Если используется блочный алгоритм шифрования, половина каждого блока (например, каждый второй бит) может быть передана в каждой половине сообщения. — Дешифрирование сообщения может зависеть от вектора инициализации (см. раздел 9.3), который может быть передан во второй части сообщения. — Первая половина сообщения может быть однонаправленной хэш -функцией шифрованного сообщения (см. раздел 2.4), а во вторая половина - собственно шифрованным сообщением. Чтобы понять, как такой протокол помешает Мэллори, давайте рассмотрим его попытку нарушить протокол . Как и раньше, он может подменить открытые ключи Алисы и Боба своим на этапах (1) и (2) . Но теперь, пере- хватив половину сообщения Алисы на этапе (3), он не сможет расшифровать ее своим закрытым ключом и сн о- ва зашифровать открытым ключом Боба . Он может создать совершенно новое сообщение и отправить половину его Бобу. Перехватив половину сообщения Боба Алисе на этапе (4), Мэллори столкнется с этой же проблемой . Он не сможет расшифровать ее своим закрытым ключом и снова зашифровать открытым ключом Алисы . Ему придется создать совершенно новое сообщение и отправить половину его Алисе . К тому времени, когда он пе- рехватит вторые половины настоящих сообщений на этапах (5) и (6), подменять созданные им новые сообщения будет слишком поздно. Обмен данными между Алисой и Бобом изменится радикально . Мэллори может попытаться избежать такого результата. Если он достаточно хорошо знает обоих корреспо н- дентов, чтобы сымитировать их при обмене данными , они могут никогда не заметить подмены. Но все-таки это сложнее, чем просто сидеть между корреспондентами, перехватывая и читая их сообщения . Обмен ключами с помощью цифровых подписей Использование цифровой подписи в протоколе обмена сеансовым ключом также позволяет избежать вскр ы- тия "человек-в-середине". Трент подписывает открытые ключи Алисы и Боба . Подписанные ключи включают подписанное заверение подлинности. Получив ключи, и Алиса, и Боб проверяют подпись Трента . Теперь они уверены, что присланный открытый ключ принадлежит именно указанному корреспонденту . Затем выполняется протокол обмена ключами. Мэллори сталкивается с серьезными проблемами. Он не может выдать себя за Алису или Боба, ведь он не знает их закрытых ключей. Он не может подменить их открытые ключи своим, потому что при подписи его ключа Трент указал, что это ключ Мэллори. Все, что ему остается - это прослушивать зашифрованный поток сообщений или испортить линии связи, мешая обмену информации Алисы и Боба . Трент выступает участником этого протокола, но риск компрометации KDC меньше, чем в первом протоколе. Если Мэллори компрометирует Трента (взламывает KDC), он получает только закрытый ключ Трен- та. Этот ключ позволит ему только подписывать новые ключи, а не расшифровывать сеансовые ключи ил ч и- тать произвольный поток сообщений. Для чтения сообщений Мэллори придется выдать себя за пользователя сети и обманывать честных пользователей, шифруя сообщения своим поддельным открытым ключом . Мэллори может предпринять такое вскрытие . Используя закрытый ключ Трента, он может создать поддел ь- ные подписанные ключи, чтобы обмануть Алису и Боба . Затем он может либо подменить этими ключами н а- стоящие ключи в базе данных, либо перехватывать запросы пользователей к базе данных и посылать в ответ поддельные ключи. Это позволит ему осуществить вскрытие "человек-в-середине" и читать сообщения польз о- вателей. Такое вскрытие будет работать, но помните, что для этого Мэллори должен уметь перехватывать и изменять сообщения. В ряде сетей это намного сложнее, чем просто пассивно сидеть, просматривая сообщения в сети по мере их поступления. В широковещательных каналах, таких как радиосеть, почти невозможно подменить одно сообщение другим - хотя можно забить всю сеть . В компьютерных сетях это менее сложно и, кажется, с каждым днем становится проще и проще. Обратите внимание на подмену IP-адреса, вскрытие маршрутизатора и т.п. Активное вскрытие не обязательно означает, что кто-то засовывает зонд в люк, да и выполнять их теперь могут не только правительственные агентства. Передача ключей и сообщений Алисе и Бобу не обязательно выполнять протокол обмена ключами перед обменом сообщениями. В этом протоколе Алиса отправляет Бобу сообщение без предварительного протокола обмена ключами : (1) Алиса генерирует случайный сеансовый ключ, K, и зашифровывает M этим ключом. E K (M) (2) Алиса получает открытый ключ Боба из базы данных. (3) Алиса шифрует K открытым ключом Боба. E B (K) (4) Алиса посылает Бобу шифрованные сообщение и сеансовый ключ. |