Когда наступит время подбирать ключи

       

Когда наступит время подбирать ключи


Всегда ли необходимо начинать криптоанализ сразу же после получения шифртекста? Быть может, если немного подождать, итоговый результат будет получен быстрее?

 Группа известных специалистов-криптографов, созданная под эгидой Альянса производителей программного обеспечения для бизнеса (промышленной организации, препятствующей незаконному использованию программного обеспечения), пришла к выводу, что необходимая длина ключа в настоящее время должна быть не менее 75 битов с дальнейшим увеличением в течение последующих 20 лет до 90 битов  [2]. Американцы люди серьезные, и шутить такими вещами не будут. Но попробуйте, уважаемый читатель, разобраться, на чем основано это утверждение, и проверить точность заключения заокеанских специалистов.

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

Еще в 60-х годах некоторые производители электронно-вычислительной техники начали создавать суперкомпьютеры   мощные машины для решения задач с большим объемом вычислений, применявшихся до последнего времени главным образом в военных целях. Как и все самое-самое, это направление развития компьютерной техники всегда вызывало повышенный интерес со стороны как специалистов, так и людей далеких от этой тематики. Видимо, в целях удовлетворения этого интереса с недавнего времени в открытой печати публикуется так называемый TOP 500   обновляемый два раза в год список пятисот самых мощных в мире эксплуатируемых суперкомпьютеров и крупнейших суперкомпьютерных центров (СКЦ) мира. Для составления первого списка используется достигнутая максимальная производительность по тесту Linpack parallel.

Из списка, появившегося летом 1997 года [1], следует, что по быстродействию суперкомпьютеры распределились следующим образом:


с мощностью порядка 1012 FLOPS   1 экз.;

с мощностью порядка 1011 FLOPS   20 экз.;

с мощностью порядка 1010 FLOPS   328 экз.;

с мощностью порядка 109 FLOPS   151 экз.

Таблица 1. Десять самых мощных суперкомпьютеров в мире по состоянию на июль 1997 г.



Рейтинг ТОР500 Наименование машины Страна-обладатель Фирма-производитель Количество процессоров Мощность (GFLOPS)
1 Intel ASCI Red США Intel (США) 7264 1068
2 Hitachi/Tsukuba CP-PACS Япония Hitachi/Tsukuba (Япония) 2048 368
3 SGI/Cray T3E Великобритания Cray (США) 696 265
4 Fujitsu Numerical Wind Tunnel Япония Fujitsu (Япония) 167 230
5 Hitachi SR2201 Япония Hitachi (Япония) 1024 220
6 SGI/Cray T3E Германия Cray (США) 512 176
7 SGI/Cray T3E США Cray (США) 512 176
8 SGI/Cray T3E Германия Cray (США) 512 176
9 SGI/Cray T3E США Cray (США) 512 176
10 SGI/Cray T3E США Cray (США) 512 176
В следующей таблице приведен список первых 15 стран в порядке убывания производительности их самых мощных суперкомпьютеров. Если у некоторой страны имеется несколько суперкомпьютеров, то указывалась производительность самого мощного из них. Понятно, что наличие суперкомпьютеров показывает научно-технический потенциал страны, отражает ее военные возможности.

Таблица 2. Первые пятнадцать стран из списка ТОР 500

Рейтинг в Тор500 Страна Мощность (MFLOPS) Год установки Количество процессоров Наименование компьютера
1 США 1 068 000 1997 7264 Intel ASCI Red
2 Япония 368 200 1996 2048 Hitachi/Tsukuba CP-PACS/2048
3 Великобритания 264 800 1997 696 SGI/Cray T3E900 LC696-128
6 Германия 176 000 1996 512 SGI/Cray T3E LC512-128
17 Франция 115 500 1997 256 SGI/Cray T3E750 LC256-128
28 Финляндия 86 600 1996 192 SGI/Cray T3E750 LC192-128
34 Южная Корея 69 300 1997 128 SGI/Cray T3E900 LC128-128
50 Швеция 55 770 1996 184 SGI/Cray T3E LC184-128
57 Италия 50 430 1996 128 SGI/Cray T3E LC128-128
70 Норвегия 34 650 1997 88 SGI/Cray T3E AC88-128
79 Канада 30 710 1995 16 NEC SX-4/16
80 Дания 30 710 1997 16 NEC SX-4/16
81 Нидерланды 30 710 1996 16 NEC SX-4/16
83 Швейцария 30 710 1996 16 NEC SX-4/16
93 Австралия 27 720 1996 13 VPP300/13
<


Первое место в мире по количеству суперкомпьютеров занимают США   254 (51%). За ними следуют Япония   87 (17,5%), Германия   45 (9%), Великобритания   24 (4,8%), Франция   18 (3,6%), Корея   8 (1,6%), Канада   7 (1,4%), Швеция, Швейцария и Норвегия   по 6 (1,2%). Россия упомянута в этом списке лишь один раз: на 156-ом месте находится компьютер HPC Ultra 10000 (пиковая производительность 16600 MFLOPS), произведенный фирмой SUN и установленный в Национальном Резервном Банке России. Хотелось бы верить, что это положение не совсем соответствует действительности. Интересная деталь: в США отсутствуют компьютеры иностранного производства   американцы работают только на отечественных машинах и к тому же снабжают ими весь остальной мир.

Количество установок суперкомпьютеров возрастает год от года в геометрической прогрессии, причем основной объем опять же приходится на США. Интересно отметить, что главным образом в перечне присутствуют машины, выпущенные в течение последних двух лет, на долю остальных приходится не более четверти списка. Можно констатировать, что за последние 3 4 года список обновился практически полностью. Статистика по годам сложилась следующая: 1997   207 установок (по состоянию на июль 1997 г.), 1996   168 установок, 1995   52 установки, 1994   45 установок, 1993   16 установок, 1992   10 установок, 1991   всего 2 установки, рейтинги которых 128 и 195. Попробуем сделать прогноз увеличения числа суперкомпьютеров на ближайшие два года на основании статистики за последние шесть лет:

45 / 10 = 4,5

52 / 16 = 3,25

168 / 45 = 3,7

207 / 52 = 3,9.

Воспользовавшись средним коэффициентом роста за два года (3,8), вычислим ориентировочные значения установок на 1998 99 гг.:

168 х 3,8 = 638 установок в 1998 г.,

207 х 3,8 = 786 установок в 1999 г.

Таким образом, в ближайшие год-два можно ожидать перерастания списка ТОР 500 в ТОР 1500 (638 + 786 = 1424) или даже более.

Состав производителей суперкомпьютеров в мире представлен следующей иллюстрацией:

В списке значатся 11 фирм, причем четыре лидирующие в нем американские компании обеспечивают более 80% мирового рынка (402 установки из 500). Всего же производители США перекрывают 86% мирового производства суперкомпьютеров (Intel, TMC, DEC, Parsytec в общей сложности составляют 28 установок или 5,6%). Японские фирмы (Fujitsu, NEC, Hitachi) обеспечивают остальные 70 установок в ТОР500 (14%).



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

Таблица 3. Компьютеры из списка ТОР500, принадлежащие организациям, способным заниматься перехватом и дешифрованием информации

Рейтинг Производитель Название Мощность Кем используются Год установки Кол-во процессоров
7 SGI/Cray T3E LC512-128 176 000 Правительство США 1997 512
21 SGI/Cray T3D MC1024-8 100 500 Правительство США 1994 1024
85 SGI/Cray Y-MP T932/321024 29 360 Правительство США 1996 32
86 SGI/Cray Y-MP T932/321024 29 360 Правительство США 1997 32
205 SGI/Cray Y-MP C916/161024 13 700 Правительство США 1992 16
206 SGI/Cray Y-MP C916/161024 13 700 Правительство США 1992 16
207 SGI/Cray Y-MP C916/161024 13 700 Правительство США 1992 16
208 SGI/Cray Y-MP C916/161024 13 700 Правительство США 1992 16
209 SGI/Cray Y-MP C916/16512 13 700 Правительство США 1994 16
374 SGI/Cray POWER CHALLENGEarray 9 398 Правительство США 1995 40
375 SGI/Cray POWER CHALLENGEarray 9 398 Правительство США 1995 40
436 SGI/Cray POWER CHALLENGEarray 7 831 Правительство США 1995 40
437 SGI/Cray POWER CHALLENGEarray 7 831 Правительство США 1995 40
438 SGI/Cray POWER CHALLENGEarray 7 831 Правительство США 1995 40
             
84 TMC CM-5/512 30 400 АНБ (NSA) 1993 512
217 SGI/Cray Y-MP C916/16512 13 700 АНБ (NSA) 1994 16
             
9 SGI/Cray T3E LC512-128 176 000 НАСА (NASA) 1996 512
315 SGI/Cray ORIGIN 2000 10 420 NASA/Langley Research Center, Hampton 1997 32
367 IBM SP2/48 9 530 NASA/Langley Research Center, Hampton 1994 32
             
98 SGI/Cray T3D MC256-8 25 300 Defence Research Agency (Англия) 1994 256
210 SGI/Cray Y-MP C916/16256 13 700 Штаб-квартира Правительственной связи (UK) 1994 16
             
15 SGI/Cray T3E LC256-256 13 870 Океанографический офис ВМС США 1997 256
23 SGI/Cray T3E LC256-128 93 200 СNRS/IDRIS Оrsay, Франция 1996 256
32 SGI/Cray T3E LC200-128 74 480 ARPA, США 1997 200
230 SGI/Cray T3D MC128-8 12 800 Air Force Base Eglin USA 1994 128
30 IBM SP2 P2 83 370 Air Force Base Wright-Patterson USA 1997 256
154 SUN Ultra HPC 10000 16 600 МВД Ю.Кореи 1997 48
155 SUN Ultra HPC 10000 16 600 МВД Ю.Кореи 1997 48
81 NEC SX-4/16 30 710 National Aerospace Laboratory, Нидерланды 1996 16
<


Мы рассмотрели список самых мощных в мире компьютеров столь подробно и разносторонне не случайно. Он послужит нам отправной точкой для исследования стойкости алгоритмов шифрования со случайным ключом в случае использования для их взлома современных ЭВМ.

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

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

Таблица 4. Время (в годах), необходимое в настоящий момент самым мощным суперкомпьютерам для полного перебора ключей

Наименование

машины
Мощн.

(FLOPS)
56 бит = 7.2*Е16

ключей
64 бита = 1.8*E19

ключей
70 бит = 1.18*Е21 ключей 75 бит = 3.78*Е22

ключей
90 бит = 1.24*E27 ключей 256 бит =

1,15*Е77 ключей
Intel ASCI Red 1.068*Е12 0.002 г.

(8,6 часа)
0.534 г.

(3,2 мес.)
35 лет

(17 лет)
1122 г.

(561 г.)
36.8*Е6 3,4*Е57
Hitachi/Tsukuba CP-PACS 3.68*Е11 0,006 г. (25,8 часа) 1,55 г. (9,3 мес.) 101,7 г.

(51 г.)
3257 лет

(1628 лет)
106*Е6 9,9*Е57
SGI/Cray T3E 2.65*Е11 0.008 г.

(34,6 часа)
2.15 г.

(25,8 мес.)
141 г.

(70 лет)
4523 г.

(2261 г.)
148*Е6 1,37*Е58
Fujitsu Numerical Wind Tunnel 2.3*Е11 0.0099 г.

(3,56 суток)
2.48 г.

(29,7 мес.)
162 г.

(81 г.)
5211 г.

(2605 лет)
170*Е6 1,58*Е58
Hitachi SR2201 2.2*Е11 0.0103 г. (3,7 суток) 2.56 г.

(30,7 мес.)
170 лет

(85 лет)
5448 лет

(2724 г.)
179*Е6 1,66*Е58
<


По некоторым оценкам производительность компьютера, деленная на его стоимость, увеличивается в 10 раз за каждые 5 лет. Исходя из этого тезиса в течении следующих 50-ти лет быстродействие компьютеров будет возрастать следующим образом:

2005 год   в 10 раз

2010 год   в 100 раз

2015 год   в 1 000 раз

2020 год   в 10 000 раз

2025 год   в 100 000 раз

2030 год   в 1 000 000 раз

2035 год   в 10 000 000 раз

2040 год   в 100 000 000 раз

2045 год   в 1 000 000 000 раз

2050 год   в 10 000 000 000 раз

и т. д.

Попробуем проверить достоверность этого утверждения. По данным  Большой Советской Энциклопедии  (статья  Цифровая вычислительная машина ), первая электронная ЦВМ   ЭНИАК была построена в 1945 г. и вступила в строй в 1946 г. в США. С этого момента во многих странах начались активные исследования, направленные на создание надежных электронных цифровых элементов и разработку рациональных структур ЦВМ.

Скорость работы машин первого поколения (до середины 50-х годов) не превышала нескольких сотен операций в секунду. Предположим, что быстродействие самых первых машин равнялось 100 операциям в секунду и возьмем эту величину за точку отсчета. Поскольку с тех пор прошел 51 год (10,2 пятилетних периодов), то к 1997 году мощность компьютера должна была возрасти приблизительно до 100 * 1010,2 = 1012,2

операций в секунду, что и подтверждается приведенным выше списком ТОР 500.

В 1951 году Государственная комиссия приняла первую на европейском континенте и в СССР электронно-счетную машину МЭСМ с быстродействием 50 операций в секунду, созданной небольшой группой под руководством академика С. А. Лебедева. К настоящему моменту (97   51 = 46, 46/5 = 9,2) расчетная производительность такого рода машины должна быть 50 * 109,2 = 5 * 1010,2 операций в секунду. Самая мощная на европейском континенте ЭВМ, находящаяся в Великобритании, работает со скоростью 2,6 * 1011.

Таким образом, можно говорить, что прогноз  10 раз за 5 лет  является достаточно обоснованным и достоверно описывает рост вычислительных мощностей на больших промежутках времени.



Определим, что x(t)   непрерывная функция, показывающая быстродействие компьютеров в момент времени t. Исходя из принятой рабочей гипотезы  10 раз за 5 лет  и начальной точки отсчета (t0 = 0 в 1946 г.), функция выглядит следующим образом: x(t) = С0 * 10t/5, где начальная точка отсчета C0 = 100   мощность первого компьютера ЭНИАК.

Введем следующие обозначения:



S

  мощность алфавита, из которого извлекаются символы для ключа;



l

  длина ключа;



||{K}|| = sl

 
мощность множества ключей;



Тм({K}, x(t))

 
максимальное время перебора ключей;



D ({K}, x(t))

 
матожидание дешифрования;



topt

 
оптимальный момент начала дешифрования;



Тб({K}, x(t))

 
время безопасности системы (зависит от двух параметров   времени начала дешифрования t и его длительности D).

При сделанных предположениях время перебора всех ключей в заданном ключевом пространстве в момент t (максимальное время дешифрования сообщения) составит Тм = ||{K}||/x(t), а среднее время дешифрования сообщения   половину максимального времени: D = 1/2 Тм

= 1/2
(||{K}||/x(t)). Исходя из прогноза об увеличении мощности компьютерных средств, можно было бы просто принять за основу, что длительность перебора через 100 лет должна составить некоторое заранее заданное время, например один год, и составить следующее уравнение типа ||{K}||/C1 * x(t+100) > 1, из которого следует, что необходимая длина ключа должна быть 136 137 бит. Однако можно дать более точные и полезные оценки для того, чтобы не расходовать впустую силы на те задачи, время которых еще не пришло.

Конечно, если подождать 100 лет, то силовая атака на криптографический алгоритм, реализация которой сегодня требует многих лет, в тот момент займет лишь несколько секунд, но из-за полной потери актуальности добытой информации исчезнет смысл ее проведения. Учитывая непрерывный рост мощности компьютерных средств, можно предположить, что дешифрование следует начинать не сразу по получении шифртекста, а в тот момент, когда оно потребует наименьшего времени. Выигрыш во многих случаях может быть очень значительным! Например, если на сегодняшний день процесс криптоанализа потребует 100 лет, то через 5 лет компьютерные мощности возрастут в 10 раз, и дешифрование, заняв 10 лет, закончится, в 2015 году. Через 10 лет производительность компьютеров возрастет в 100 раз и полный перебор вариантов, завершившись в течение одного года, даст результат уже в 2011 году. Таким образом, выигрыш во времени по сравнению с первым вариантом составляет 89 лет. Вопрос в том, можно ли еще сократить время криптоанализа за счет оптимального выбора момента его начала и сколько времени (начиная с этого момента) продлится оптимальное дешифрование.



Рабочая модель для расчета времени безопасности системы шифрования (1) состоит из суммы двух действующих факторов   момент начала дешифрования плюс сложность дешифрования. Минимум этой функции назовем максимальным временем безопасности Тб

идеальной системы шифрования. Прилагательное  максимальный  введено только для того, чтобы подчеркнуть идеальность исследуемых алгоритмов   в реальной жизни криптосистемы обладают определенными недостатками, снижающими их криптостойкость. Коэффициент C1 = 31 536 000 возникает при переходе от операций в секунду к операциям в год, и используется в основном для удобства.

(1)

Для определения минимума этой функции найдем ее производную и решим уравнение Тб?  = 0. В результате решения и упрощения получаем следующее значение момента времени topt,

в котором достигается минимум функции Тб, то есть оптимальное время начала криптоанализа:

(2)

Подставив ||{K}|| в эту формулу, можно получить значение момента времени topt. Время безопасности идеальной системы шифрования определяется значением функции Тб в этой точке. Подставив в (1) мощность множества ключей ||{K}|| в исследуемой системе и значение topt

можно найти ее время безопасности Тб.

Среднее время дешифрования определяется по следующей формуле:

(3)

Самое неожиданный и интересный факт, на мой взгляд, заключается в том, что, если подставить значение topt в формулу (3) и произвести необходимые упрощения, то длительность начатого в оптимальный момент дешифрования независимо от длины ключа всегда одна и та же:

5 / ln10 = 2,171472409516 года

(739,13 дней или 19 035,12 часов).

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

Длина ключа (бит) Кол-во ключей Оптимальное время начала дешифрования Длительность дешифрования Окончание дешифрования
56 7,2 * Е 16 43,6 (1989,6 г.) 2,17 45,77 (1991,77 г.)
60 1,15 * E 18 49,6 (1995,6 г.) 2,17 51,77 (1997,78 г.)
62 4,6 * Е 18 52,6 (1998,6) 2,17 54,77 (2000,8 г.)
64 1,8 * Е 19 55,6 (2001,6 г.) 2,17 57,77 (2003,77 г.)
70 1,18 * Е 21 64,7 (2010,7 г.) 2,17 66,87 (2012,87 г.)
75 3,78 * Е 22 72,2 (2018,2 г.) 2,17 74,37 (2020,37 г.)
90 1,24 * Е 27 94,8 (2040,8 г.) 2,17 36,96 (2042,87 г.)
128 3,4 * Е 38 152 (2098 г.) 2,17 94,15 (2100,17 г.)
137 1,74 * Е 41 165,5 (2111,5 г.) 2,17 167,69 (2113,69 г.)
256 1,15 * Е 77 344,6 (2290,6 г.) 2,17 286,79 (2292,77 г.)

Содержание раздела