Средства и способы взлома шифров

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

Суперкомпьютеры

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

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

Распределенные вычисления

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

.

59Блочные шифры. Как открытый текст представляется при блочном способе шифрования и какие преобразования происходят?

Блочные шифры.

Блочный шифр — разновидность симметричного шифра, оперирующего группами бит фиксированной длины — блоками. Фактически, блочный шифр представляет собой подстановку на алфавите блоков и, как следствие, может быть моно- или полиалфавитной. Характерный размер блоков данных меняется в пределах 64 — 256 бит. Если исходный текст (или его остаток) меньше размера блока, перед шифрованием его дополняют. Блочный шифр является важной компонентой многих криптографических протоколов и широко используется для защиты данных, передаваемых по сети.

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

Эти режимы получили следующие названия:

· режим прямого шифрования, или шифрования с использованием электронной книги кодов ЕСВ (Electronic code book),

· шифрование со сцеплением блоков шифртекста СВС (Cipher block chaining),

· шифрование с обратной связью от шифртекста CFB (Cipher feedback),

· шифрование с обратной связью от выхода OFB (Output feedback).

Основное преимущество прямого блочного шифрования (electronic code book) состоит в том, что в хорошо сконструированной системе блочного шифрования небольшие изменения в шифртексте вызовут большие и непредсказуемые изменения в соответствующем открытом тексте и наоборот.
Вместе с тем, применение блочного шифра в этом режиме связано с серьезными недостатками. Первый из них состоит в том, что вследствие фиксированного характера шифрования даже при сравнительно большой длине блока, например 50-100 бит, возможен криптоанализ "со словарем" в ограниченной форме.
Ясно, что блок такого размера может повториться в сообщении вследствие большой избыточности в типичном тексте на естественном языке. Это может привести к тому, что идентичные блоки открытого текста длиной т бит в сообщении будут представлены идентичными блоками шифртекста, что дает криптоаналитику некоторую информацию о содержании сообщения.
Другой потенциальный недостаток этого шифра связан с размножением ошибок (это одна из проблем для всех видов шифров, за исключением поточных). Результатом изменения только одного бита в принятом блоке шифртекста будет неправильное расшифрование всего блока. Это, в свою очередь, приведет к появлению от 1 до т искаженных бит в восстановленном исходном тексте.
Вследствие отмеченных недостатков, блочные шифры редко применяются в указанном режиме для шифрования длинных сообщений. Однако, в финансовых учреждениях, где сообщения часто состоят из одного или двух блоков, блочные шифры (в частности, алгоритм DES) широко применяются в этом простом варианте. Поскольку такое применение связано с возможностью частой смены ключа шифрования, вероятность шифрования двух идентичных блоков открытого текста на одном и том же ключе очень мала. Наиболее часто блочные шифры применяются в системах шифрования с обратной связью от шифртекста.
Возможно также образование смешанных (гибридных) систем поточного и блочного шифрования с использованием лучших свойств каждого из этих шифров. В таких системах поточное шифрование комбинируется с псевдослучайными перестановками. Открытый текст сначала шифруется как при обычном поточном шифровании, затем полученный шифртекст разбивается на блоки фиксированного размера. В каждом блоке производится псевдослучайная перестановка под управлением ключа (предпочтительны различные перестановки для отдельных блоков).
Порядок следования этих двух операций может быть изменен на обратный без влияния на основные свойства системы. В результате получается шифр, не размножающий ошибки, но обладающий дополнительным свойством, которого нет у поточного шифра. Это свойство заключается в том, что перехватчик не знает, какому биту открытого текста соответствует бит шифртекста. Благодаря этому зашифрованное сообщение становится более сложным и трудным для раскрытия. Но следует отметить, что это уже не подлинный блочный шифр, в котором каждый бит шифртекста является функцией только одного, а не всех битов открытого текста.
Криптосистема с открытым ключом должна быть системой блочного шифрования, оперирующей с блоками довольно большой длины. Это обусловлено тем, что криптоаналитик, знающий открытый ключ шифрования, мог бы предварительно вычислить и составить таблицу соответствия блоков открытого текста и шифртекста. Если длина блоков мала (например, 30 бит), то число возможных блоков будет не слишком большим (при длине 30 бит это 2³⁰-10⁹) и может быть составлена полная таблица, дающая возможность моментального дешифрования любого зашифрованного сообщения с использованием известного открытого ключа.
Было предложено много различных криптосистем с открытым ключом, наиболее известной из которых является система RSA (Rivest, Shamir, Adleman). Криптостойкость этой системы основана на трудности разложения больших чисел на простые сомножители и выборе для ключей шифрования и расшифрования двух больших простых чисел.
Известно, что алгоритм RSA не может быть применен для шифрования с большой скоростью. Наиболее оптимизированная программная реализация этого алгоритма оказывается низкоскоростной, а несколько аппаратных реализации обеспечивают скорость шифрования от 10 до 100 Кбит/с (при использовании простых чисел порядка 2⁷,что представляется минимальной длиной для обеспечения требуемой криптостойкости). Это значит, что применение системы RSA для блочного шифрования ограничено, хотя применение ее для распределения ключей, аутентификации и формирования цифровой подписи представляет интересные возможности. Некоторые известные в настоящее время криптоалгоритмы с открытым ключом допускают более высокую скорость шифрования, чем алгоритм RSA. Однако они пока не являются настолько популярными.