Криптостойкость. Взлом. Способы борьбы.

Устойчивость шифра к поиску автокорреляций в сообщении называется криптостойкостью алгоритма. Даже при использовании удачных в этом смысле алгоритмов, если взломщик знает, что исходные (нешифрованные данные) удовлетворяют тому или иному требованию, например, содержат определенное слово или снабжены избыточным кодом, он может произвести полный перебор пространства ключей: перебирать все значения ключа, допускаемые алгоритмом, пока не будет получено удовлетворяющее требо­ванию сообщение. При использовании ключей достаточно большой разряд­ности такая атака оказывается чрезмерно дорогой, однако прогресс вычис­лительной техники постоянно сдвигает границу “достаточности” все дальше и дальше. Так, сеть распределенных вычислений Bovine в 1998 году взлома­ла сообщение, зашифрованное алгоритмом DES с 56-разрядным ключом за 56 часов работы [www.distributed.net]!

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

Упаковка сообщения перед шифрованием и/или дополнение его случайными битами. - еще один способ существенно усложнить работу взломщику. Важно подчеркнуть, впрочем, что количество двоичных разрядов ключа является лишь оценкой объема пространства ключей сверху, и во многих ситуациях эта оценка завышена. Некоторые алгоритмы в силу своей природы могут использовать только ключи, удовлетворяющие определенному условию — например, RSA использует простые числа. Это резко сужает работы по перебору, поэтому для обеспечения сопоставимой криптостойкости разрядность ключа RSA должна быть намного больше, чем у алгоритмов, допускающих произвольные ключи.

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