Пределы роста
Максимальная силовая атака на основе распределенных вычислений
Вселенная образовалась 20 миллиардов лет тому назад, Земля – 4,5. Обезьяна превратилась в человека – 10 000 лет тому назад и 3000 лет назад тому назад на земле зародилось шифрование. 55 лет назад появился первый компьютер. В результате такого бурного процесса эволюции 20 лет назад для шифровальных алгоритмов требовались ключи длиной 56 бит, сегодня 75, через 20 лет – 90. Уже сейчас существуют алгоритмы с длиной ключа в 128, 168 и 256 бит.
* * *
Спрашивается: если Солнце будет светить еще 100 миллионов лет, то какой величины достигнет длина ключа к тому времени, когда Солнце погаснет?
Проблема поиска ключей симметричной криптосистемы путем перебора всех возможных ключей относится к классу задач, допускающих распараллеливание. Применение распределенных вычислений для организации перебора таких ключей позволяет эффективно решать трудоемкие задачи в этой области. Экспоненциальная динамика роста с течением времени производительности вычислительных систем (10 раз за 5 лет) оказывает еще более существенное влияние на рост производительности системы в целом. Таким образом, прогресс в этой области возможен за счет:
- использования достижений научно-технического прогресса и применения технологических новинок для увеличения производительности отдельного устройства;
- увеличения количества таких устройств в системе.
Других мыслимых способов повышения вычислительной мощности нет.
Таким образом, с точки зрения защиты информации криптографическими методами, анализ потенциальных возможностей метода распределенных вычислений представляет как для криптоаналитиков, так и для разработчиков криптографических систем значительный интерес. Попробуем, поэтому, проанализировать предельные значения двух указанных тенденций. Насколько известно, подобный подход к шифровальным вопросам еще никогда не обсуждался в открытых исследованиях, и может представлять самостоятельный интерес.
* * *
Первая оценка максимальной производительности вычислительного устройства связана с определением максимального быстродействия на основе физических закономерностей нашего мира. Максимальная скорость передачи информации в нашей вселенной – скорость света, максимальная плотность записи информации – бит на атом. Большая скорость передачи информации невозможна на основании законов физики, большая плотность записи невозможна ввиду наличия соотношения неопределенностей Гейзенберга.
Предположим, что размер процессора равен размеру атома. Тогда в наших обозначениях быстродействие гипотетического процессора выразится формулой F = V c /R a = 3 * 1018 операций в секунду, где V c = 3 * 108 м/с скорость света в вакууме, а R a = 10-10 м – размеры атомов. Столько раз за 1 секунду свет пройдет размеры атома. Поскольку период обращения Земли вокруг Солнца, по данным «Советского Энциклопедического словаря», составляет 365,2564 суток или 31 558 153 секунд, то за один год такой процессор выполнит 94 674 459 * 1018 ~ 1026 операций. Более быстрый процессор в нашей вселенной невозможен в принципе, поэтому более быстро производить дешифрование методом тотального перебора ключей также принципиально невозможно!
Кстати, число операций производимых этим процессором в одну секунду сравнимо с легендарным множеством пшеничных зерен, испрошенных в награду за изобретение шахматной игры 264 – 1. Один такой процессор по быстродействию превосходит более двух миллионов самых современных суперкомпьютеров Intel ASCI Red стоимостью 55 млн долл., работающих одновременно, и состоящих из 9152 процессоров Pentium каждый, точное значение – 2242152,466 (по данным ТОР500 от 15 ноября 1997 г.). Производительность одного процессора в системе Intel ASCI Red – 1,456 * 108 операций в секунду.
За 100 лет непрерывной работы гипотетический процессор совершит приблизительно 1028 операций. При условии, что за один такт своей работы он опробывает один ключ, а дешифрование сообщения на найденном ключе происходит мгновенно (!), то он сможет перебрать 1028 ключей. Переведенная на язык битов, длина ключа составит ВСЕГО 93 БИТА!
Очевидно, что создать еще более быстродействующую систему возможно только
- уменьшив размеры атома
- увеличив скорость света
- увеличивая количество процессоров в системе.
Тонкости инженерной реализации первых двух способов – суть промысел Божий, и не будем лишать его этой соблазнительной возможности изменить мировые константы, зато последний способ означает, что функция быстродействия качественно изменяет свой характер роста с экспоненциального на линейный, и вычислительная мощность нашей системы будет определяться только тем, какое количество быстродействующих атомов сможет собрать группа индивидов для реализации своих творческих намерений.
По-видимому все вычислительные возможности человечества накопленные к настоящему моменту составляют в сумме мощность одного такого процессора.
Анализируя предельные значения второй тенденции, можно отметить, что увеличению количества процессоров в системе тоже есть свой предел.
Если взять эти атомы в таком количестве, чтобы их длина (уложенных плотно, без промежутков) равнялась длине Великой китайской стены, протянувшейся на 5000 км, то количество таких атомов составит 5*1016 штук. За год они переберут 5*1042 ключей, что составит около 142 бит, а за 100 лет – 5*1044, что составит 148-149 бит. Вывод из описанного выше может быть только один – практически нецелесообразно создавать шифровальные алгоритмы с «космической» длиной ключа более 150 бит!
Для нашей планеты естественным пределом является площадь земной поверхности. Если выразить поверхность земного шара (считая океаны, пустыни, Арктику с Антарктикой) в квадратных миллиметрах, и на каждый миллиметр поместить по миллиону таких процессоров, то в год мощность такого вычислительного устройства составит 5.1*1052 операций, что эквивалентно длине в 175-176 бит. Если исходить из предположения, что стойкость шифра должна составлять 100 лет, то за указанный период такая система сможет перебрать 5*1054 ключей, что составит 181-182 бита. И это притом, что никакие вычислительные ресурсы процессоров не тратятся на согласование их взаимной работы в системе, на решение задачи расшифрования и т.д.
Еще одна недостижимая, на мой взгляд, оценка возникает из следующих соображений: масса Вселенной – приблизительно 1050 грамм, и почти вся она состоит из водорода. В 1 грамме водорода приблизительно 6*1023 атомов. Если предположить когда-либо в будущем достижение плотности записи бит/атом, то становится очевидно, что Вселенная может содержать максимум 2,53*1071 ключей. Длина ключа в этом случае составит 237,2 бит. Для того, чтобы перебрать все эти ключи со скоростью гипотетического процессора понадобится (в случае ключ/атом) – 6*1047 лет, а в случае бит/атом – 6*1045 лет.
Описанной выше системе «Планета Земля» для реализации перебора понадобится 1,2*1021 лет и 5*1018 лет соответственно.
Итоги
Таким образом, прогноз будущего силовой атаки на основе распределенных вычислений неутешителен. По мнению автора, силовая атака на криптосистемы RC5-32/12/12, RC5-32/12/13, RC5-32/12/14, RC5-32/12/15 и RC5-32/12/16 вряд ли завершится при его жизни.
Возможно она завершится только случайно, поскольку одной из проблем шифровальных систем является отсутствие гарантированной нижней грани для стойкости системы. Верхняя грань у нее есть, это мощность множества ключей, а вот нижняя – отсутствует ввиду того, что ткнув пальцем в небо можно случайно попасть куда надо.
Таблица 1. Длина ключа в битах, обеспечивающая необходимую степень стойкости.
Система | Кол-во проц. | Опер. / сек | Опер. / 1 год | Длина ключа / 1 год | Опер. / 100 лет | Длина ключа / 100 лет |
---|---|---|---|---|---|---|
Один процессор | 1 | 3*1018 | 1026 | 86-87 | 1028 | 90 |
Интернет (50 млн) опер/с | 5*107 | 1,5*1026 | 5*1033 | 111-112 | 4,7*1035 | 118-119 |
Население Земли | 5*109 | 1,5*1028 | 5*1035 | 118-119 | 4,7*1037 | 125-126 |
Китайская стена | 5*1016 | 1,5*1035 | 5*1042 | 142 | 4,7*1044 | 148-149 |
Планета ЗЕМЛЯ | 5,3*1026 | 1,6*1045 | 5,1*1052 | 175-176 | 5*1054 | 181-182 |
Хотелось бы отметить один интересный момент, касающийся определения времени достижения предельных величины производительности вычислительных систем.
Известно, что скорость роста производительности вычислительных систем составляет 10 раз за 5 лет. Таким образом, если учесть, что в 1997 г. для процессора Pentium достигнутая производительность составила около 200 MFLOPS (2*108), и будет возрастать на порядок каждые 5 лет, то не более, чем через (18-8)*5=50 лет можно ожидать прекращения роста производительности вычислительных устройств за счет технологической составляющей. Более вероятно то, что предел миниатюризации элементов может наступить гораздо раньше из-за возникновения различных производственных проблем.
Таким образом, главный вывод данного исследования состоит в том, что предел развития шифровальных систем с симметричным ключом уже не за горами, следовательно замедление и последующая стагнация темпов развития вычислительных устройств сделает ненужным дальнейший рост длины ключа на все грядущие времена!
Следует отметить, что вопросу о пределе научных технологий уделяют внимание и на Западе. По данным газеты ComputerWorld/Россия от 23 декабря 1997 г., статья «Микропроцессоры в третьем тысячелетии»:
«В начале 80-х годов исследователи одной из научных лабораторий США показали, что компьютер в принципе может функционировать по квантовомеханическим законам. В ряде научных центров ведутся активные работы по созданию архитектурных принципов квантовых компьютеров. Пока неясно, смогут ли (и насколько эффективно) машины, использующие совершенно иные физические принципы работы, решать традиционные математические задачи и тем более опередить в этом своих классических конкурентов».
Там же говорится, что компьютер – устройство физическое и его базовые операции описываются законами физики. А с физической точки зрения тот тип транзистора, который является основой современной интегральной схемы, может быть уменьшен еще примерно в 10 раз, до размера 0,03 мк. За этой гранью процесс включения/выключения микроскопических переключателей станет практически невозможным. Поведение транзисторов будет похоже на текущие краны – перемещение электрона с одного конца на другой выйдет из под контроля. Таким образом максимальное быстродействие составит – 1016 операций/секунду, а предел роста – в 2037 г.
* * *
Оценим длину ключа из финансовых соображений. Очевидно, что всякое государство направляет на дешифрование некоторую часть своего дохода, и обладает вследствие этого определенным вычислительным потенциалом. Богатые государства обладают большим потенциалом, бедные – меньшим. Чтобы получить максимальную вычислительную мощность, некоторое государство должно направить весь свой доход на реализацию вычислений. Зная доход некоторого государства (предполагаемого потенциального противника), а также стоимость 1 компьютерной операции можно определить ключ какой длины на сегодняшний день оно способно расколоть. В эти расчеты, для простоты, не входят стоимость электроэнергии, потребляемой устройствами, стоимость людских ресурсов, помещений и других абсолютно необходимых расходов, организационные работы на проведение подобных мероприятий, затраты на создание и оптимизацию программного обеспечения, а также желание налогоплательщиков финансировать подобный проект и т.д.
Приведенная ниже таблица показывает величину золотовалютных резервов десяти наиболее богатых государств мира. Стоимость одного грамма золота при расчетах была принята равной 10 долларам. Исходя из того, что стоимость одного суперкомпьютера Intel ASCI Red составляет 55 миллионов долларов, в графе 5 показано количество таких комплексов, которые может себе позволить купить каждая страна. При этих условиях сложность перебора ключей в год отражена в графах 6 и 7.
Таблица 2. Золотовалютные резервы отдельных стран, по данным международной финансовой статистики (по состоянию на 1995 г. газета "Труд" от 19 октября 1995 г.).
Страна | Резервы золота (тонн) | Валютные резервы (млрд. долл.) | Валютные резервы (млрд. долл.) | Intel ASCI Red | Ключей в год | В битах |
---|---|---|---|---|---|---|
США | 8142,6 | 75,71 | 157,14 | 2857 | 9*Е22 | 76,3 |
Япония | 753,6 | 143,55 | 151,1 | 2747 | 8,66*Е22 | 76,2 |
Германия | 2865,3 | 82,05 | 110,7 | 2012,7 | 6,35*Е22 | 75,7 |
Китай | 395,0 | 59,35 | 63,3 | 1151 | 3,63*Е22 | 74,9 |
Великобритания | 1198,4 | 41 | 53 | 963,63 | 3*Е22 | 74,7 |
Франция | 2545,8 | 26,62 | 52,1 | 947,3 | 3*Е22 | 74,7 |
Италия | 2073,7 | 28,24 | 49 | 891 | 2,8*Е22 | 74,4 |
Нидерланды | 1081,5 | 37,49 | 48,3 | 878,2 | 2,8*Е22 | 74,4 |
Швейцария | 2590,3 | 32 | 57,9 | 507,3 | 1,6*Е22 | 73,7 |
Россия | 241,3 | 10,09 | 12,5 | 227,3 | 7,2*Е21 | 72,6 |
Возможно, за истекший период произошли некоторые изменения в объемах, но в целом, картина сохранилась.
Заключение
В заключение хотелось бы сказать следующее: вопросы сосуществования общества и информационных технологий в современном мире возникли в историческом масштабе относительно недавно, и не всегда еще очевидно, что в их подоплеке зачастую лежат не антропоморфные (субъективная оценках руководством страны важности государственных секретов, международная напряженность противостоящих государств, желание скрыть компрометирующую информацию и т.д.), а физические закономерности нашего мира. Задача поиска таких закономерностей является общей для всего цивилизованного человечества, а перспективы их научного разрешения связаны с осознанием ограничений, налагаемыми законами природы.
Хотелось бы отметить, что всякое шифрование и дешифрование востребованы в обществе не сами по себе, а лишь постольку, поскольку они могут принести прибыль или позволяют избежать убытков, поэтому всегда интересно знать какова же стоимость одного знака шифрованной и дешифрованной информации и во что это обходится налогоплательщикам? Какую часть своего национального дохода развитые государства мира по сравнению с Россией направляют на шифрование и дешифрование? Являются ли рентабельными те организации, которые занимаются этим, или они заведомо убыточны? Конечно, данные вопросы скорее всего являются государственной тайной и тщательно оберегаются, но они не могут не интересовать исследователей. Наиболее интересен, конечно, сравнительный анализ таких данных по различным странам с целью научного обоснования той доли затрат, которая необходима для всякого государства в зависимости от его внутренних возможностей.
P.S.
- Известно, что при принятии стандарта DES в 1977 г. Национальное бюро стандартов США организовало два симпозиума для обсуждения его приемлемости для многих потенциальных пользователей. Один – по математическим аспектам алгоритма с целью поиска в нем слабых мест, второй – по экономическим вопросам, в частности по определению длины ключа. В связи с этим, хотелось бы узнать у ФАПСИ как проходило подобное обсуждение в бывшем СССР? Кто принимал решение об выборе длины ключа? Из каких посылок исходили исследователи, предлагая такую запредельную длину ключа, которая способна только тормозить процессы зашифрования/расшифрования? Автор надеется, что в связи с известными изменениями в общественной жизни, в связи с опубликованием этого стандарта и открытостью в вопросах шифрования, былая секретность уже потеряла свое значение, а ознакомиться с этими сведениями было бы интересно не только ему, но и многим специалистам работающим в этой области.
- Подходы к установлению необходимой длины ключа предложенные в данной статье, по-видимому, будут полезны также при вычислении длины ключа для криптографических систем с открытым ключом, если получить оценку трудоемкости вычисления одного открытого ключа относительно одного симметричного.
- Указанные результаты можно применять и при определении необходимой длины электронной цифровой подписи, гарантирующей сообщение от подделки.
© 1999 Пудовченко Ю.Е.
Опубликована в 2:5085@FidoNet
Опубликована в 2:5085@FidoNet
См. также: "Длина ключа и его полный перебор"[link1], "К вопросу о безопасности 1024-битной версии RSA и 160-битной криптографии на эллиптических кривых"[link2].
[link2] http://www.pgpru.com/biblioteka/statji/stojjkostjrsa1024