книги / Практическая криптография

172	Глава 9. Проблемы реализации. Часть I

казалось бы, очень простое правило может решить половину проблем без­ опасности вашей системы.

9.4.5Тестирование

Развернутое тестирование — обязательная часть любого хорошего про­ цесса разработки программного обеспечения. Тестирование помогает найти ошибки в коде программы, однако оно бессильно в поиске “дыр” безопасно­ сти. Никогда не путайте тестирование с анализом безопасности. Эти процессы прекрасно дополняют друг друга, но между ними нет ничего общего.

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

Второй набор тестов разрабатывается самим автором модуля. Эти те­ сты предназначены для проверки каких-либо ограничений реализации. На­ пример, если внутренние механизмы модуля используют буфер размером 4 Кбайт, то дополнительная проверка границ в начале и в конце буфера по­ может выявить любые ошибки, связанные с управлением буфером. Иногда для разработки подобных конкретных тестов требуется хорошо знать внут­ реннюю структуру модуля.

Мы часто пишем последовательности тестов, основанные на применении генератора случайных чисел. Более подробно генераторы псевдослучайных чисел (pseudorandom number generator — PRNG) рассматриваются в главе 10, “Генерация случайных чисел”. Использование генератора псевдослучайных чисел позволяет легко получать большое количество тестов. Если мы сохра­ ним начальное число, которое использовалось генератором псевдослучайных чисел, то сможем повторить ту же последовательность тестов, что очень удоб­ но для тестирования и отладки. Дальнейшие детали этого процесса зависят от специфики тестируемого модуля.

И наконец, чрезвычайно полезно создать какой-нибудь “быстрый тест”, ко­ торый будет выполняться при каждом запуске программы. В одном из своих последних проектов Нильс должен был реализовать шифр AES. При запуске

9.4 Качество кода

173

казалось бы, очень простое правило может решить половину проблем без­ опасности вашей системы.

9.4.5 Тестирование

Развернутое тестирование — обязательная часть любого хорошего про­ цесса разработки программного обеспечения. Тестирование помогает найти ошибки в коде программы, однако оно бессильно в поиске “дыр” безопасно­ сти. Никогда не путайте тестирование с анализом безопасности. Эти процессы прекрасно дополняют друг друга, но между ними нет ничего общего.

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

Второй набор тестов разрабатывается самим автором модуля. Эти те­ сты предназначены для проверки каких-либо ограничений реализации. На­ пример, если внутренние механизмы модуля используют буфер размером 4 Кбайт, то дополнительная проверка границ в начале и в конце буфера по­ может выявить любые ошибки, связанные с управлением буфером. Иногда для разработки подобных конкретных тестов требуется хорошо знать внут­ реннюю структуру модуля.

Мы часто пишем последовательности тестов, основанные на применении генератора случайных чисел. Более подробно генераторы псевдослучайных чисел (pseudorandom number generator — PRNG) рассматриваются в главе 10, “Генерация случайных чисел”. Использование генератора псевдослучайных чисел позволяет легко получать большое количество тестов. Если мы сохра­ ним начальное число, которое использовалось генератором псевдослучайных чисел, то сможем повторить ту же последовательность тестов, что очень удоб­ но для тестирования и отладки. Дальнейшие детали этого процесса зависят от специфики тестируемого модуля.

И наконец, чрезвычайно полезно создать какой-нибудь “быстрый тест”, ко­ торый будет выполняться при каждом запуске программы. В одном из своих последних проектов Нильс должен был реализовать шифр AES. При запуске

174	Глава 9. Проблемы реализации. Часть I

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

9.5 Атаки с использованием побочных каналов

Существует целый класс атак, называемых атаками с использованием по­ бочных каналов (side-channel attacks) [48]. Такие атаки становятся возможны­ ми, когда у злоумышленника появляется дополнительный канал информации об интересующей его системе. Например, злоумышленник может измерить, сколько времени уходит у системы на то, чтобы зашифровать сообщение. Если криптографический алгоритм встроен в смарт-карту, злоумышленник может узнать, сколько электричества потребляет смарт-карта в течение опре­ деленного времени. В качестве побочных каналов могут выступать магнит­ ные поля, радиоизлучение, потребление энергии, время выполнения операции и даже помехи, вызываемые на других каналах данных.

Неудивительно, что атаки с использованием побочных каналов часто ока­ зываются удачными по отношению к системам, которые проектировались без учета таких атак. Особенно успешными в этой области оказались атаки из­ мерения энергии (power attacks), применявшиеся для взлома смарт-карт [56].

Защитить систему от всех видов атак с использованием побочных ка­ налов очень сложно, а то и вообще невозможно. Тем не менее существует несколько простых мер предосторожности, которые позволяют значительно снизить риск нападения. Когда-то давным-давно Нильс работал над внед­ рением криптографических механизмов в смарт-карты. В то время одно из правил проектирования требовало, чтобы последовательность, в которой про­ цессор выполняет инструкции, зависела только от той информации, которая и так известна злоумышленнику. Это сводило на нет назначение таймингатак (timing attacks — атаки, основанные на сравнительных измерениях вре­ мени) и значительно усложняло проведение атак измерения энергии, потому что анализ последовательности выполняемых инструкций больше не позво­ лял получить никаких сведений о неизвестной информации. Разумеется, это не полное решение проблемы, и современные приемы измерения энергии лег­ ко справляются со взломом тогдашних смарт-карт. Тем не менее это было лучшее, что мы могли сделать для защиты смарт-карт в те дни. Спасение от атак с использованием побочных каналов всегда подразумевает применение некоторой комбинации контрмер. Одни из них осуществляются посредством

9.6 Заключение

175

программного обеспечения, которое реализует криптографическую систему, а другие — с помощью самого аппаратного обеспечения.

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

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

ирадиоизлучение. (Смарт-карты, в свою очередь, особенно чувствительны

кизмерению энергопотребления.)

9.6Заключение

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

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

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

Часть II

Согласование ключей

Глава 10

Генерация случайных чисел

Чтобы сгенерировать ключ, нам нужен генератор случайных чисел (ran­ dom number generator - RNG), Генерация действительно хорошей случайно­ сти — неотъемлемая и к тому же наиболее сложная часть многих криптогра­ фических операций.

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

Многим криптографическим функциям требуются хорошие генераторы случайных чисел. В главе 1, “Наша философия проектирования”, рассмотрен безопасный канал общения и его компоненты. Мы предположили, что у нас существует ключ, известный пользователям А и Б. Этот ключ должен быть где-нибудь сгенерирован. Для выбора ключей системы управления ключами используют генераторы случайных чисел. Если генератор не слишком хорош, будет получен слабый ключ. Именно это произошло с одной из ранних версий обозревателя Netscape [37].

Мера случайности называется энтропией (entropy) [90]. Мы не будем при­ водить здесь математические детали этого вопроса, просто попытаемся сде­ лать все, чтобы вы получили представление о том, что же такое энтропия. Если у нас есть 32-битовое слово, которое выбирается совершенно случайным образом, значит, оно имеет 32 бита энтропии. Если же 32-битовое слово может принимать только четыре значения, вероятность появления каждого из кото­ рых составляет 25%, тогда это слово обладает лишь двумя битами энтропии. Энтропия показывает не количество битов в значении, а то, насколько вы не уверены в этом значении. Для большей наглядности энтропию можно пред­ ставить в качестве среднего числа битов, необходимых для того, чтобы задать

10.1 Истинно случайные числа

179

значение при использовании идеального алгоритма сжатия. Обратите внима­ ние, что энтропия значения зависит от того, сколько вы знаете об этом значе­ нии. Случайное 32-битовое слово обладает 32 битами энтропии. Теперь пред­ положим, что о значении этого слова точно известно следующее: 18 бит слова равны 0, а 14 бит — 1. Таким требованиям удовлетворяют около 228,8 значе­ ний, а следовательно, энтропия слова будет составлять лишь 28,8 бит. Дру­ гими словами, чем больше известно о значении, тем меньше его энтропия.

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

Н (Х ) : = - £ Р (Х = х) log2 Р (Х = х), X

где Р (Х = х) — вероятность того, что переменная X принимает значение х. Мы не будем пользоваться этой формулой, поэтому запоминать ее нет необ­ ходимости. Именно на это определение ссылаются математики, когда говорят об энтропии. В математике существует еще несколько определений энтропии; выбор того или иного определения зависит от того, чем занимается конкрет­ ный ученый. И не путайте нашу энтропию с понятием энтропии в физике, где этот термин касается термодинамики.

10.1Истинно случайные числа

Видеальном мире следовало бы использовать “истинно случайные” числа.

Ксожалению, наш мир не идеален и найти в нем действительно случайные данные весьма сложно.

Обычные компьютеры имеют несколько источников энтропии. В качестве примеров таких источников часто приводят точное время нажатия клавиши и точное время перемещения мыши. В свое время некоторыми учеными даже проводились исследования по поводу случайности колебаний времени досту­ па к жесткому диску, вызванных турбулентностью внутри его корпуса [19]. Все эти источники энтропии несколько сомнительны, так как в определенных ситуациях злоумышленник может выполнить измерения над источником слу­ чайности или повлиять на этот источник.

Многие разработчики весьма оптимистично относятся к количеству эн­ тропии, которое может быть извлечено из разных источников. Мы видели программное обеспечение, которое генерировало 1-2 байта случайных данных на основе времени одного нажатия клавиши. К сожалению, мы не разделяем этого оптимизма. Время нажатия клавиш профессиональной машинисткой можно предсказать с точностью до нескольких миллисекунд. А частота ска­ нирования клавиатуры ограничивает точность, с которой можно измерить

180	Глава 10. Генерация случайных чисел

время нажатия клавиши. Печатаемые данные также нельзя назвать случай­ ными, даже если пользователь просто нажимает первые попавшиеся клави­ ши. Что еще хуже, всегда существует угроза того, что у злоумышленника имеется дополнительная информация о “случайных” событиях. Звуки, изда­ ваемые при нажатии клавиш, можно записать на микрофон, что позволит определить точное время нажатия каждой клавиши. Будьте очень осторож­ ны, оценивая количество энтропии, которым обладают те или иные данные. В конце концов, мы имеем дело с очень умным и активным злоумышлен­ ником.

Существует множество физических процессов, которые ведут себя слу­ чайным образом. Например, согласно законам квантовой физики поведение некоторых частиц является полностью случайным. Было бы очень хорошо измерить это случайное поведение, чтобы затем использовать его в своих системах. Технически это, конечно же, возможно. К сожалению, у злоумыш­ ленника и здесь найдутся свои подходы. Во-первых, он может попытаться по­ влиять на поведение квантовых частиц, чтобы оно стало предсказуемым. Вовторых, он может попросту украсть наши измерения. Если злоумышленнику удастся заполучить измерения, тогда данные все равно останутся случайны­ ми, но, с его точки зрения, не будут обладать какой-либо энтропией. (Если злоумышленник знает точное значение, то для него это значение не обладает энтропией.) Вероятно, злоумышленник способен создать сильное радиоизлу­ чение, которое будет смещать показания наших приборов. Мы даже можем описать несколько атак, использующих законы квантовой физики. Напри­ мер, для нарушения случайности, которую мы пытаемся измерить, может быть использован парадокс Эйнштейна-Подольского-Розена [5, 11). Анало­ гичные соображения применимы и к другим источникам энтропии, таким, как тепловые помехи резистора или туннельный эффект в полупроводнико­ вом стабилитроне.

Некоторые современные компьютеры обладают встроенными генератора­ ми истинно случайных чисел [41]. Это, несомненно, дает им значительные преимущества перед использованием отдельных генераторов, поскольку су­ щественно затрудняет проведение некоторых типов атак. Тем не менее такой генератор случайных чисел все еще будет доступен операционной системе, по­ этому для получения безопасных данных приложение должно ей полностью доверять.

10.1.1 Проблемы использования истинно случайных чисел

Помимо сложности получения истинно случайных данных, существует еще несколько проблем их использования на практике. Во-первых, они не всегда доступны. Если случайные числа генерируются на основе времени на­

10,1 Истинно случайные числа

181

жатия клавиш, вы не получите никаких данных, когда пользователь вдруг прекратит печатать. Это может стать настоящей проблемой, если ваше при­ ложение является Web-сервером, установленным на компьютере, у которого нет клавиатуры. Еще одна схожая проблема связана с тем, что объем истинно случайных данных всегда ограничен. Если вам понадобится большое количе­ ство случайных данных, придется подождать, пока они будут сгенерированы, что совершенно неприемлемо для многих приложений.

Вторая проблема состоит в том, что источники истинно случайных дан­ ных, такие, как физические генераторы случайных чисел, могут сломаться или отказать. Иногда поведение генератора может стать предсказуемым. По­ скольку генераторы истинно случайных чисел довольно замысловаты, они могут выходить из строя гораздо чаще, чем классические компоненты ком­ пьютера. Если ваша система напрямую зависит от генератора истинно слу­ чайных чисел, вам крупно не повезет в случае отказа последнего.

И наконец, третья проблема — это сложность оценки энтропии, которая может быть извлечена из конкретного физического события. Если только в качестве генератора случайных чисел не используется выделенное, специ­ ально спроектированное для этого оборудование, определить количество по­ лучаемой энтропии будет крайне сложно. Мы еще вернемся к этому вопросу немного позднее.

10.1.2Псевдослучайные числа

Альтернативой истинно случайным числам являются так называемые псевдослучайные числа. В действительности псевдослучайные числа вообще не являются случайными. Они вычисляются с помощью детерминированно­ го алгоритма на основе некоторого начального числа (seed). Зная начальное число, можно предсказать все последующие псевдослучайные числа. Класси­ ческие генераторы псевдослучайных чисел (pseudorandom number generator — PRNG) никак не защищены от умного злоумышленника. Они разрабатыва­ лись для устранения статистических искажений, а вовсе не для того, чтобы отражать атаки. Второй том книги Дональда Кнута (Donald Knuth) The Art of Computer Programming [54] содержит подробное описание генераторов слу­ чайных чисел, но все они анализируются только на предмет статистической случайности. Мы должны исходить из предположения, что наш противник знает алгоритм, используемый для генерации случайных чисел. Может ли злоумышленник, зная несколько псевдослучайных чисел, сгенерированных алгоритмом, предугадать некоторые биты будущих (или прошлых) случай­ ных значений? Для большинства классических генераторов псевдослучайных чисел ответ может быть положительным. Для криптографических генерато­ ров псевдослучайных чисел это недопустимо.

182	Глава 10. Генерация случайных чисел

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

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

10.1.3Истинно случайные числа и генераторы псевдослучайных чисел

Истинно случайные числа будут использоваться нами только для того, чтобы получить начальное число, подающееся на вход генератора псевдослу­ чайных чисел. После того как у нас появится начальное число, генератор сможет произвести на свет любое нужное количество случайных (а точнее, псевдослучайных) чисел. При необходимости мы можем прибавлять истин­ но случайные числа к*начальному числу генератора псевдослучайных чисел. Это гарантирует, что выходные данные последнего никогда не станут полно­ стью предсказуемыми, даже если злоумышленник каким-либо образом узнает начальное число.

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

защищенным по вычислениям (computationally secure). Это различие, одна­ ко, имеет значение только для закостенелых теоретиков. Все криптографиче­ ские протоколы почти всегда основаны на вычислительных приближениях. Устранение такого приближения для одного конкретного типа атак не при­ несет существенного улучшения. Более того, генерация истинно случайных чисел, необходимых для обеспечения безусловной защищенности, настолько