Реферат: Длина ключа и его полный перебор

1. Введение

1.1. Что такое бит?

Бит является фундаментальной единицей информации. Онможет принимать значения 0

или 1. В течение сорока последних лет компьютеры работаютсбинарными данными, то

есть с наборами битов (а не с цифрами от 0 до 9, как этопринято у людей; можно

сказать, что компьютеры имеют только два пальца).Битыпозволяют кодировать целые

числа, символы, и т.д… Вся информация, проходящая черезкомпьютер, превращается

в биты.

8 бит образуют байт; это дает 256 комбинаций и позволяеткодировать числа от 0

до 255 или символы (включая разницу между прописными истрочными буквами, символы

с надстрочными знаками и другие).

1024 байта образуют один килобайт (кБ). 1024 используетсявместо 1000 так как

1024 является степенью числа 2, то есть«круглым» числом, еслиработать по

основанию 2. 1024 килобайта образуют мегабайт (МБ), или1048576 байт. 1024

мегабайта образуют гигабайт (ГБ), или 1073741824 байта.1024 ГБобразуют терабайт

(ТБ). Дальнейшее умножение малоупотребительно, т.к.дорогостояще со всех точек

зрения. Типичная емкость жестких дисков широкораспространенных внастоящее время

компьютеров составляет десять гигабайт. Развитая сетьможет пропускать десять

мегабайт в секунду между двумя машинами.

1.2. Что такое криптографический ключ?

Криптографические операции, такие как шифрование иподписание данных электронной

цифровой подписью, могут быть осуществлены толькоопределеннымилицами,

располагающими некоторыми секретами. В прошлые века этимсекретом был сам способ

преобразования данных. Однако более рационально и более

эффективноконцентрировать этот секрет в виде наборабитов, а сам алгоритм делать

общедоступным.

Действительно, сохранять в тайне алгоритм проблематично,и, кроме того,

необходима численная оценка его безопасности. Сам фактпубликации

алгоритмапозволяет «бесплатно» получитьпризнание его надежности

криптографическим сообществом.

Ключ, таким образом, является концентрацией секрета, этотнабор битов является

«эссенцией» конфиденциальности.

1.3. Что такое полный перебор?

Взломать криптосистему, значит суметь осуществитьнекоторые операции, требующие

(в теории) знания секрета (ключа), не имея информации опоследнем.Наиболее

полным взломом является взлом, в результате которогостановится известен ключ,

что дает взломщику те же полномочия, что и законномувладельцуключа.

Полный перебор является наиболее простым методом этойточки зрения: он состоит в

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

правильный. Этот метод является наиболее общим, и можетбыть распараллелен

(вычисления могут быть распределены на много машин).Кроме того, он наиболее

реалистичен: если рассматривать случай симметричнойсистемы шифрования (которая

ставит в соответствие блоку, состоящему изнесколькихбайтов, другой блок той же

длины, но преобразованный к «нечитаемому» видупри помощи ключа), достаточно

перехватить пару открытыйтекст/зашифрованный текст, тоесть блок из несколько

байтов и соответствующих им зашифрованных. Например, еслипередается картинка в

формате JPG, то началосообщения представляет собойстандартный заголовок JPG,

формат которого всем хорошо известен.

С точки зрения статистики, надо перебрать примернополовину возможных ключей,

прежде чем найдется правильный. Если длина ключасоставляет 56 битов, это

означает, что в среднем необходимо провести 2^55итераций, что составит

36028797018963968.

1.4. Является ли полный перебор единственновозможнымметодом криптоанализа?

Нет. Но другие методы сильно зависят от конкретногоалгоритма. Некоторые,

такиекак линейный или дифференциальный криптоанализ,требуют огромного числа пар

открытый/зашифрованный текст, представляя, таким образом,чисто

теоретическийинтерес.

Кроме того, существуют криптосистемы (в частности, системыасимметричные,

называемые еще «системами с открытым ключом»),для которых всесочетания битов не

образуют правильного ключа. Типичный пример — RSA, гдеключ представлен большим

числом, полученным из двух больших простыхчисел.Совокупность наборов из 1024

бит, которые являются двоичной записью этих чисел,гораздо меньше 2^1024. Полный

перебор абсурден в этом случае.

1.5. 128-битный ключ в два раза устойчивее квзлому, чем64-битный?

НЕТ! Это распространенная ошибка. Каждый дополнительныйбит удваивает количество

возможных ключей и затраты на полный перебор. Ключ длиной128 битявляется в

18446744073709551616 раз более сложным для подбора, посравнению с ключом длиной

64 бита (который уже не назовешь совсем легким).

1.6. PGP должно быть очень устойчив, так какиспользуетключи 1024 бита.

Стоп! Давайте разберемся! «1024 бит» в PGP — это ключ RSA или DSS, то есть ключ

асимметричного алгоритма. Атака методом полного переборане самыйлучший вариант

в этом случае.

Кроме того, асимметричные алгоритмы относительномедленны, и «внутри» PGP

использует симметричный алгоритм (исторически IDEA, затемCAST) размер ключа

которого составляет 128 бит.

2. Текущее положение дел

2.1. Какова максимальная длина ключа длясимметричныхкриптосистем, которая

поддается программному взлому методомполного перебора?

Известно, что два ключа по 56 бит были подобраны полнымперебором на обычных

компьютерах типа PC. Специализированная машина(построенная EFF) помогла

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

Ключи были для алгоритма DES. Качественный ПК или рабочаястанция могут

перебирать с максимальной скоростью нескольких миллионовключей в секунду.

Еслипринять среднюю скорость один миллион ключей всекунду на машину, то легко

видеть, что для подбора ключа 10000 машин должны всреднем затратить 42 дня.

Полный перебор ключа длиной 64 бита для RC5 (для которогосложность полного

перебора несколько выше, чем для DES) в настоящее времяпродолжается, и

будетдлиться, по крайней мере, еще нескольких лет.Напоминаем, что подбор ключа

размером 64 бита, является в 256 раз более трудоемким,чем подбор ключа длиной

56 бит.

2.2. То же, с использованием специальнойаппаратуры?

Американская группа EFF, инвестировала 250000$ в созданиеспециализированной

машины под названием «Deep crack»(«глубокий взлом»), которая в состоянии

перебрать все ключи алгоритма DES приблизительно за тридня. В ней использованы

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

от взлома DES (в частности, они ничего «незнают» о RC5).

Все остальные машины того же рода — из области слухов.DES используется уже

более 20 лет, и можно предположить, что, вероятно, машинеEFF

предшествовалидругие прототипы, разрабатываемыесекретными службами. В любом

случае, скоро уже 15 лет периодически упоминаютсяпринципы построения такой

машины.

2.3. А для несимметричных криптосистем?

В принципе, существуют две математические задачи,используемые в асимметричных

шифрах: факторизация и дискретное логарифмирование.RSAиспользует первую, DSS

вторую. Другие упоминаемые задачи (вариации двухпредыдущих, использование

эллиптических кривых, задача об укладке ранца, минимизациясети (задача

коммивояжера), обратное распознавание (permutedperceptrons problem — см.

примечания) относительно редко используются внастоящеевремя.

Рекорд факторизации датируется 22-ым августа 1999: числоразмером 155 десятичных

цифр (512 бит) было факторизовано за шесть месяцеввычислений напарке

приблизительно из 600 машин, некоторые из которых могутбыть квалифицированны

как «быки» (в частности Cray с 2 ГБпамяти).Примененные алгоритмы гораздо более

сложны, чем полный перебор, и требуют большого количестваоперативной памяти с

хорошей скоростью доступа.

Дискретное логарифмирование менее исследовано, на еговзлом осуществлено меньше

инвестиций, чем на факторизацию. Рекорд — порядка 95десятичных цифр.

2.4. Что относительно «кофейника»Шамира?

Представленный на Eurocrypt'99 в Праге (в начале мая1999), этот аппарат

ускоряет физическими средствами исследование гладкихчисел (то есть

полученныхпроизведением только маленьких простых чисел),которые получают обычно

методом решета. Эти числа являются основой несколькихалгоритмов факторизации и

решенийзадачи дискретного логарифмирования.

Сам аппарат еще не построен, описаны только его принципы.Существуют технические

проблемы для реализации прототипа (Arjen Lenstra высказалнекоторыевозражения, с

которыми Adi Shamir согласился).

По общему мнению, этот метод позволил бы факторизовать числоприблизительно в

600 бит, со средствами, которые позволили установитьрекорд в 465 бит (вфеврале

1999), если все проблемы с реализацией будут решены.Отмечено, что решето заняло

приблизительно 60% времени для рекорда в 512 бит.

Все же шоу было очень увлекательным. Phil Zimmerman,автор PGP, заметил, что

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

этихпроблемах, так как это увеличивает степень доверия ктакого рода системам.

3. То, что будет возможным в будущем

3.1. Что такое закон Мура?

Закон Мура (Moore) является оценкой развитиявычислительной техники во времени.

В базовом варианте он гласит, что для заданной стоимости(в широкомсмысле,

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

и т.д.) вычислительная мощность увеличивается в 8 разкаждые 3 года.Говоря более

точно, можно сказать, что через каждые три года,технологические достижения

позволяют разместить в 4 раза больше логических элементоввмикросхеме заданной

стоимости, одновременно ускоряя ее быстродействие в 2раза.

Этот закон замечательно подтверждался в течение последних15 лет. Следует

отметить, что центральные микропроцессоры компьютеровобщего назначения

неполностью следуют этому закону, потому что они не могуттак же быстро

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

такжепотому, что вычисления, которые эти процессорыобычно производят, имеют

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

большихрегистров).

Это касается, таким образом, систем, описываемых втерминах логических

элементов, специализированных на конкретном алгоритме.Таким образом, это посути

ASIC (Application Specific Integrated Circuit — специализированные микросхемы) и

FPGA (Field Programmable Gate Arrays — программируемыелогическиеинтегральные

схемы); то есть перепрограммируемые цепи, выполняющие теже задачи, что и ASIC,

но вдвое более дорогие при заданной мощности,однакоявляющиеся многоцелевыми).

3.2. Какова предполагаемая стоимость полногоперебора сиспользованием

специализированного оборудования?

Если закон Мура будет продолжать выполняться (и неимеется веских оснований для

обратного, так как он учитывает качественные достижения,а не толькоувеличение

точности обработки кремния), можно достичь машины EFF(четверть миллиона

долларов, для 56 бит за 3 дня) и добавлять 3 бита каждые3 года (3бита = 2^3 =

8; что дает в 8 раз больше возможных вариантов ключей).

Заметим, что для сохранения закон Мура, качественныедостижения должны

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

плотностиэлементов на кристалле кремния (замедлениевследствие туннельного

эффекта). В ряде разрабатываемых методов предполагаетсяосуществить замену

кремния наарсенид галлия, что позволит достичь болеевысокой плотности

элементов, замену алюминия медью, которая позволяетработать гораздо более

быстро, построениеоптической логики (оптический элементпереключается

приблизительно в 100 раз быстрее электронного, но егостоимость выше более чем в

100 раз).

Таким образом, можно считать, подобрать полным перебором128-битный ключ так же

«легко», как сейчас 56-битный, станет возможнымчерез 72 года. Этаоценка

является «наилучшей», в то время как многиеисследователи этой тематики

полагают, что закон Мура будет выполняться в лучшемслучае ещенесколько лет

(действительно, все качественные изменения, привнесенныеза последних 15 лет,

были просто нереализованными, известными с 1975 года, иихзапас почти исчерпан в

настоящее время).

3.3. А с использованием квантовыхкомпьютеров?

Квантовые компьютеры, реализуемые через суперпозициюсостояний одной частицы,

являются более мощной вычислительной моделью, чем машинаТьюринга ипозволяют

осуществить многие операции (среди которых полный переборключей такого

«безграничного» алгоритма, как DES) засубэкспоненциальное время.

Квантовые компьютеры очень соблазнительны, но они несуществуют. Был построен

двухбитовый квантовый регистр, но имеются достаточномощныепрепятствия для

построения машины, способной сломать DES (главнымобразом, инициализация этого

монстра, которая не может быть распараллелена, изанимает, таким образом, 2^n

операций для ключа n битов).

Это не имеет большого значения для другого типа квантовойкриптографии, который

служит для «неперехватываемой» передачи данныхпо оптоволокну(используя принцип

неопределенности Гейзенберга).

4. Различные слухи

4.1. NSA/DST/другие могут ломать ключи до128 бит.

Имеются очень сильные возражения против такого родавысказываний. Среди

классических можно выделить одно, предполагающее наличиепроцессора

сэнергопотреблением в 10 раз меньше, чем у классических(таким могли бы

располагать секретные службы, имеющие преимущество).Энергетические затраты

наполный перебор 128-битного ключа, если их перевести втепловую форму,

заставили бы исчезнуть под водой Нидерланды в результатетаяния полярных льдов.

Что касается 256-битных ключей, то если предположить, чтозатраты на анализ

одного ключа равны энергии перехода электрона с однойорбиты атома на другую, то

количества великодушно предоставляемой Солнцем энергиинедостаточно для

осуществления такого перебора за разумное время.

Некоторые легко манипулируют количеством битов, легкоотнося 20 бит на

использование сверхпроводников или оптических элементов,20 других наприменение

суперэффективных алгоритмов, и 30 последних потому что«это уже немного» (да,

просто помножим на 1 миллиард, этодействительно«немного»).

Напомню, что число битов экспоненциально. Это означает,что затраты на перебор

каждых n битов пропорциональны 2^n. Чтобы это было легчепредставить, напомним,

что:

  64 бита: 18446744073709551616 возможных ключей

  128 бит: 340282366920938463463374607431768211456возможных ключей

  256 бит:

  115792089237316195423570985008687907853269984665640564039457584007913129639936

  возможных ключей

4.2. NSA/DST/другие обладают квантовымикомпьютерами.

Очень маловероятно. Если это правда, то технологическиедостижения опережают

всех как минимум лет на 10. Другими словами, онирасполагали бы тогда

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

Некоторые упоминают возможность получения внеземнойтехнологии, либо через Людей

в Черном, либо непосредственно через Phil Zimmerman, ихпосла на этойпланете.

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

Атлантов (конечно, Атлантида была затоплена именно врезультатеперебора ключа

«классическими» методами, см. выше).

Сталкиваясь с проявлениями абсурда и дилетантства в этойобласти, хочется

посоветовать держаться подальше от подобного родаспекуляций, чтобыневыглядеть

клоуном. Если хочется оценить что в состоянии сделатьNSA, надо дать ему 3 года

времени в соответствии с законом Мура и хороший бюджет.Это позволитсделать

задачу с 64 битами решаемой. 80 бит останутсянедостижимыми.

4.3. NSA/DST/другие достигли методовкриптоанализа, недоступных другим.

NSA (в лице Don Coppersmith) объявил в 1987 году, чтознали уже в 1977 о

дифференциальном криптоанализе, обнародованном Бихамом иШамиром (E. Biham,

A.Shamir) именно в этом 1987 году. Алгоритм DES,разработанный в 1977,

специально защищен от такой атаки.

Тем не менее, уточним, что такая атака требует огромногоколичества пар

открытый/зашифрованный текст, и, в любом случае,нереальна. Кроме того, DES

небыл защищен против линейного криптоанализа, открытого в1993 Matsui, что

ограничивает научное превосходство NSA 15 годами.Наконец, этот последний

способкриптоанализа также нереален, т.к. требует 64 ТБизвестного открытого

текста, что в несколько десятков миллионов раз превышаетобъем Библии.

Подобные слухи ходили также про факторизацию, дискретноелогарифмирование и

средства от прыщей. Легко можно встретить такие слухи вупоминаниях

омеждународных заговорах злодеев, которые хотят знать всеобо всех в этом мире.

В любом случае, с определенного момента, гораздо дешевлеустановить видеокамеру

в вашем офисе, чем заставлять «молотить»квантовыйкомпьютер. Знаете ли Вы, что

восстановление изображения Вашего монитора возможно сдистанции 100 метров? То

же самое касается и сигналов клавиатуры, когда Выпечатаете. Необходимо иметь

хорошо спроектированную сетку Фарадея, чтобы защищатьсяот этого. Шифрование

позволяет установить защищенный каналмежду двумя точками,но не защищает сами

точки.

4.4. Я работаю на NSA/DST/других и поэтомупытаюсь убедитьобщественность, что

128-битное шифрование надежно.

Niark niark niark. Я обманщик, не так ли?

© Автор: Thomas Pornin (thomas.pornin@ens.fr); оригинал:

www.dmi.ens.fr/~pornin/faq-cle.html

©Владислав Мяснянкин, перевод на русский язык.

Примечания переводчика.

  Пожалуйста, не присылайте мне замечания/комментарии посодержанию документа. Я

  только перевел его. Пишите непосредственно автору (нафранцузском или

  английском языке) — адрес в заголовке.

  EFF — Electronic Frontier Foundationhttp://www.eff.org/

  NSA — National Security Agency www.nsa.gov/

  DST — Direction de la Sйcuritй du Territoire

  www.chez.com/icebreaker/dst/

  Я не нашел русского термина для «PermutedPerceptrons Problem» и перевел как

  «задача обратного распознавания». Если естьболее правильный перевод — буду

  рад услышать. Что это такое можно посмотреть напримерна

 http://cgi.dmi.ens.fr/cgi-bin/pointche/papers.html?Po95a (на английском).

  Если вы найдете неточности в употреблении терминов илипредложите более

  «благозвучный» вариант их перевода, это будетвоспринято с благодарностью.

  Неконструктивная критика и флейм пойдут на /dev/null.