Разработка ядра Linux - Роберт Лав

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

Рис. Б.1. Прохождение энтропии через пул энтропии ядра

Для доступа к пулу энтропии, как из пространства ядра, так и из пространства пользователя, ядро предоставляет набор интерфейсов. Когда выполняется обращение к этим интерфейсам, ядро вначале вычисляет хеш-значение SHA данных из пула. Алгоритм SHA (Secure Hash Algorithm, алгоритм вычисления безопасного хеш- значения) — это алгоритм вычисления дайджеста сообщения (профиля сообщения, message digest), который был разработан Агентством национальной безопасности (National Security Agency, NSA) и утвержден в качестве федерального стандарта США Национальным институтом стандартов и технологий (NIST) (федеральный стандарт по обработке информации, FIPS 186). Вычисление дайджеста сообщения выполняется с помощью специального алгоритма, который принимает сообщение переменного размера (большое или маленькое) и выдает на выходе хеш-значение фиксированного размера (обычно размером 128 или 160 байт). Это фиксированное значение и представляет собой дайджест. Входное сообщение не может быть реконструировано по его хеш-значению. Более того, простое изменение входного сообщения (например, изменение одного символа) приведет к радикальному изменению хеш-значения. Алгоритмы вычисления дайджестов сообщений могут использоваться по-разному, включая проверку подлинности данных и дактилоскопию. Другие алгоритмы вычисления дайджестов — это MD4 и MD5. Пользователю возвращается хеш-значение SHA пула, к содержимому пула энтропии непосредственно обращаться нельзя. Считается, что по хеш-значению невозможно получить никакую информацию о состоянии пула. Поэтому если известно несколько значений из пула, то это не дает никакой информации о прошлых и будущих значениях. Ядро может использовать оценку энтропии и отказаться выполнить запрос на считывание данных из пула, если значение энтропии равно нулю. По мере того как из пула считываются данные, оценка энтропии уменьшается. Это реакция на то, что о пуле становится известно больше информации.

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

Почему это реализовано в ядре?

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

Проблема с загрузкой системы

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

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

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

Интерфейсы для ввода энтропии

Ядро экспортирует следующее семейство интерфейсов, которые могут использоваться драйверами и системами для ввода данных в пул энтропии.

void add_interrupt_randomness(int irq);

void add_keyboard_randomness(unsigned char scancode);

void add_mouse_randomness(__u32 mouse_data);

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

Функция add_keyboard_randomness() использует скан-коды и интервалы времени между нажатиями клавиш для ввода энтропии в пул. Интересно, что эта функция достаточно интеллектуальна и игнорирует повторение символов при постоянном нажатии клавиши, потому что повторяющиеся скан-коды и интервалы времени вносят мало энтропии.

Функция add_mouse_randomness() использует позицию указателя мыши и интервалы времени между прерываниями для заполнения пула. Параметр mouse_data — это позиция указателя, которая возвращается аппаратным обеспечением.

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

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