Журнал о системах электронного документооборота (СЭД)
Технологические аспекты безопасности

О невозможности вскрытия шифроалгоритма ГОСТ 28147-89 прямым перебором

  12 комментариев Добавить в закладки

В. Минаков,

ГНИИИ ПТЗИ ФСТЭК России

В настоящее время в РФ существует только один шифроалгоритм, разрешенный для защиты информации, отнесенной к гостайне – это алгоритм, описанный в ГОСТ 28147-89. Рассматривая появление, развитие и дискредитацию других шифроалгоритмов, естественно встает вопрос о стойкости криптоалгоритма ГОСТ 28147-89 современным вычислительным средствам и о предположительном времени его дискредитации.

Дискредитация шифроалгоритма определяется фактом создания вычислительной системы или нахождение определенного алгоритма, с помощью которых злоумышленник может получить доступ к зашифрованной информации, в приемлемое для него время. Как уже неоднократно доказывалось, алгоритм шифрования ГОСТ 28147-89 является криптостойким, т.е. невозможно получить доступ к зашифрованной информации не имея ключа зашифрования, и единственный способ расшифровать информацию – перебирать все возможные варианты ключа, до тех пор пока не будет найден верный.

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

Для расшифрования равно как и для зашифрования блока информации длиной 64 бита требуется произвести минимум 194 операции над числами (для режима простой замены). С учетом операции перебора ключей (изменение значения ключа) для гарантированного расшифрования блока информации длиной 64 бита требуется произвести более Р = 2256 ·195 операций над числами.

Время

Найдем время, которое потребуется для перебора всех комбинаций при современных темпах роста производительности вычислительных устройств [1, 2, 3]. График роста производительности (операций в секунду) вычислительных устройств (систем) от легендарного "Марк-1" до вычислительной системы № 1 в мире по данным [2] на 12.11.2006 г. "DOE/NNSA/LLNL IBM "eServer Blue Gene Solution", представлен на рисунке 1.

Рисунок 1. DIRECTUM-Journal.ru

Рисунок 1

Предположим максимально быстрое экспоненциальное развитие производительности вычислительных систем (график развития показан на рисунке 1 в виде прямой). Пусть РT – максимальная достигнутая производительность вычислительных систем в году T. Тогда производительность системы может быть вычислена по формуле:

Формула

Вычислим год, в котором будет создана вычислительная система, которая сможет перебрать все варианты ключа за период равный 365,25 дням (1 году):

Формула

Энергия

Минимальное количество энергии, которое можно затратить, численно равно постоянной Планка (h). Следовательно, минимальное количество энергии, которое требуется затратить для производства вычислительной системой Р операций, равно:

E = P · h· ν = 1,496 · 1046 Дж

Исходя из количественных расчетов [4], при взрыве сверхновой II типа (массивной звезды) выделяется энергия, оцениваемая как сумма кинетической энергии сброшенной оболочки, энергии, излученной в виде света за все время вспышки и энергии, излученной в виде нейтрино, значение которой достигает величины 2· 1052 эрг (2· 1045 Дж).

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

Вывод

Дискредитация шифроалгоритма ГОСТ 28147-89 путем перебора ключей невозможна ни сейчас и ни в сколь угодно далеком обозримом будущем.

Список литературы

1.   http://www.cisl.ucar.edu/

2.   http://www.top500.org/

3.   http://www.ecmwf.int/services/computing/overview/supercomputer_history.html

4.   Надежин Д. К. Почему взрываются сверхновые звезды? / Земля и Вселенная, 1968 г. № 5

 

Источник: Daily.Sec.Ru

Похожие записи
Комментарии (12)
Наталья Храмцовская 10 ноября 2007 г. 17:54  
Неплохая статья для студента-гуманитария, и откровенно несолидная - для представителя ФСТЭК. Автору неплохо было бы почитать матероиалы о том, как компрометируются и сходят со сцены такие алгоритмы, как  MD5 и SH-1.

Что касается смелых заявлений типа "Дискредитация шифроалгоритма ГОСТ 28147-89 путем перебора ключей невозможна ни сейчас и ни в сколь угодно далеком обозримом будущем" - хочется надеяться, что "сколь угодно далекое будущее" наступит не через пять лет... Никогда не говори "никогда" - на всякий случай :)
Михаил Романов 10 ноября 2007 г. 19:50  
как компрометируются и сходят со сцены такие алгоритмы, как  MD5 и SH-1

Наталья, а можно немного подробнее? Я знаю, что для MD5 существует алгоритм получения документа с требуемой хэш-суммой, однако этот алгоритм дает всего лишь некоторый произвольный поток байт, т.е. о практическо применении речь пока что не идет.
А вот про известные случаи компрментации SH-1 я вообще не слышал... Такие были?

Что касается выводов автора статьи, то, наверное, если сделать оговорку, что "не будут найдены более эффективные методы атаки, кроме атак грубой силы", с ними можно даже согласиться. Тем более, как я понимаю (все-таки не криптоаналитик) почти все современные криптосистемы держатся на вере, что более эффективной техники взлома не существует. Пока что доказательства обратного нет ни для одного алгоритма.
Наталья Храмцовская 10 ноября 2007 г. 20:29  
Последние три года  ведущие криптоаналитики активно "атакуют" SHA-1. Им удалось найти несколько серьёзных недочетов, использование оторых существенно сокращающих время подбора коллизий. С учетом роста быстродействия компьютеров, ожидается, что уже в ближайшие несколько лет подбор коллизий для SHA-1 станет практичеси осуществимым. Поэтому правительство США уже приняло решение о переходе на более криптостойкие (с большей длиной ключа) версии SHA-1. Одновременно ведется поиск новых алгоритмов.

На эту тему, по понятным причинам, много не пишут. Вот несколько ссылок:
http://www.securitylab.ru/news/289448.php
http://offline.computerra.ru/2005/580/37766/

Разработчики немецкой "Энигмы" тоже считали, что ракрыть их шифры невозможно...
Андрей Подкин 12 ноября 2007 г. 13:05  
Технологии взлома не стоят на месте. Про RSA-1024 тоже говорили, что время взлома больше времени устаревания защищаемых документов. Пока Шамир не показал обратного.
Вадим Майшев 12 ноября 2007 г. 15:47  

"Автору неплохо было бы почитать матероиалы о том, как компрометируются и сходят со сцены такие алгоритмы, как  MD5 и SH-1."

А при чем тут MD-5 и SHA-1 (собственно не особо качественные хеш-функции)? Автор анализирует совершенно другой по классу и уровню проработки криптоалгоритм (а именно классический симметричный блочный шифр), и причем довольно правдоподобно!

Артем Старыгин 12 ноября 2007 г. 16:16  

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

1.           Итак, криптоалгоритмы бывают: а) симметричные, b) с открытым ключом (асимметричные), с) хэш-функции.

 

«почти все современные криптосистемы держатся на вере, что более эффективной техники взлома не существует»

 

2.           О вере :) ГОСТ 28147-89, о котором идет речь в статье, относится к симметричным алгоритмам шифрования, такие, как известно, строятся по принципу Кирхгофа, т.е. знание криптоаналитиком самого алгоритма, таблицы замен (если говорить о ГОСТе), соответствующих друг другу блоков открытого текста и шифра, не должно давать способов взлома проще чем «полный перебор».

 

«Технологии взлома не стоят на месте»

 

3.           О взломе. Шифры с открытым ключом. Вот тут действительно нас поддерживает только вера :) Например, RSA построен на предположении о трудности разложения на простые сомножители больших чисел, а ЭльГамаль предполагал, что задача дискретного логарифмирования достаточно сложна. Иными словами нет математического доказательства криптостойкости шифров с открытым ключом, отсюда и сообщения о взломе на которые ссылается Андрей. Ну что ж с этим можно только смириться и периодически обновлять свои криптосистемы. Надо сказать, что так и происходит, например, ГОСТ Р 34.10-94 был обновлен в 2001 году, сравните с ГОСТ 28147-89 принятым на 5 лет раньше и до сих пор не обновленным.

 

«Поэтому правительство США уже приняло решение о переходе на более криптостойкие (с большей длиной ключа) версии SHA-1»

 

4.           О хэш-функциях. К сожалению, мне неизвестны предположения или принципы, по которым они строятся, так что врать не буду, но в статьях, на которые ссылается Наталья речь идет о взломе именно хэш-функций, и какая тут связь с симметричным алгоритмом нашего любимого госта мне не совсем ясно :) Ясно только, что надо увеличивать размер хэша, тут спорить сложно …

 

«Разработчики немецкой "Энигмы" тоже считали, что раскрыть их шифры невозможно»

 

5.           Да действительно считали, но не надо забывать, что для взлома шифра Энигмы англичане под руководством Алана Тьюринга построили первую в мире ЭВМ «Колосс», чем собственно и открыли новую эру в развитии человечества. Делала она, как я понимаю, кстати, как раз полный перебор, а для добывания блоков открытого текста соответствующего шифру приходилось платить многими жизнями, если не ошибаюсь, в художественной интерпретации это было немного показано в фильме «Конвой PQ-17», название фильма могу путать :(

 

Ну и собственно о статье, и криптостойкости ГОСТа, "никогда" я говорить не буду - на всякий случай, ведь всегда есть вероятность того что вдруг начнется новая эра в развитии человечества :)

Андрей Подкин 12 ноября 2007 г. 17:01  
Конечно, симметричное шифрование - это совсем не то, что асимметричное.
Но ведь 3DES или AES стали применяться вместо DES тоже не просто так.
Вадим Майшев 12 ноября 2007 г. 17:21  

Потому и AES (пространство ключей до 2^256~10^77, собственно как и у ГОСТ 28147-89), т.к. у DES всего 2^56~10^17 (а 3DES чуть лучше чем DES) и это без особенностей архитектуры.

Чувствуете разницу для тотального перебора 10^17 и 10^77?

Артем Старыгин 12 ноября 2007 г. 17:32  

Но ведь 3DES или AES стали применяться вместо DES тоже не просто так

конечно не просто, проблема в том,  что перебрать все ключи размером 56 бит стало вполне реально на современной технике, но размер ключа в госте 256 бит, сравните с тем же 3DES у которого всего 168 бит.

Артем Старыгин 13 ноября 2007 г. 14:36  

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

Артем Старыгин 21 ноября 2007 г. 08:24  

2Сергей
в приведенной ссылке речь об алгоритме выработки случайных чисел, к симметричному шифрованию в частности ГОСТ-у прямого отношения это не имеет. Кроме того упоминаются элиптические кривые, которые действительно используются в криптографии с открытым ключом, например в ГОСТ Р 34.10-2001 и международных стандартах принятых несколько ранее. Собственно говоря ГОСТ Р 34.10-2001 тем и отличается от ГОСТ Р 34.10-94, что в его алгоримы добавлены элиптические кривые. Так что я подозреваю, что проблема не в элиптических кривых, а в конкретном алгоритме Dual_EC_DRBG.
 

Сейчас обсуждают
Больше комментариев