Библиотека Bee2

Криптографические программные библиотеки должны не только точно и эффективно реализовывать криптографические алгоритмы и протоколы, но и соответствовать дополнительным принципам безопасности. Попытка сформулировать и реализовать эти принципы привела к созданию библиотеки Bee2. На сегодняшний день в библиотеке реализованы алгоритмы и протоколы национальных криптографических стандартов (СТБ 34.101.31, 45, 47, 60, 66), а также алгоритмы электронной цифровой подписи, стандартизированные в РФ и Украине.Обсудим принципы построения Bee2.

Переносимость. Библиотека написана на языке Си, без ассемблерных вставок и поэтому компилируется практически на любой аппаратно-программной платформе с помощью средств GCC. Расширения C99 не использованы, и поэтому библиотека компилируется также в среде Visual Studio любой версии.

Контроль памяти. В низкоуровневые функции библиотеки могут передаваться указатели state и stack. Эти указатели ссылаются на память, в которой размещаются состояния алгоритмов / протоколов и могут размещаться локальные переменные. Память может содержать критические объекты (ключи), и поэтому взята под контроль. Функции объявляют о потребностях в памяти через дополнительные сервисные функции (они имеют суффиксы keep и deep). Высокоуровневые функции обрабатывают объявления и определяют общий объем памяти для состояния и стека. Интересно, что объем памяти оказывается довольно небольшим. Так в текущей реализации достаточно сложного протокола BMQV, определенного в СТБ 34.101.66, на максимальном уровне стойкости l = 256 каждой стороне требуется не более 4096 байтов (одной страницы) памяти.

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

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

Регулярные вычисления – это «равномерные» вычисления, схемно одинаковые при обработке любых данных определенной размерности. В Bee2 реализуется программа полной регуляризации. Критические нерегулярные функции, начиная с  простейших функций сравнения буферов памяти, заменяются регулярными аналогами. Регулярные библиотеки, реализующие универсальные алгоритмы арифметики больших чисел, арифметики эллиптических кривых и пр., нам неизвестны. Библиотека Bee2 может быть одной из первых.

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

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

Интерфейсы. Высокоуровневые функции Bee2 организуют максимально полную проверку входных данных. Высокоуровневые функции также объявляют о своих ожиданиях и при их нарушении возвращают соответствующие коды ошибок.

Высокоуровневые функции объединяются в связки. Функции связки используют общее состояние и стек, они похожи на методы класса C++. В необходимых случаях объявляются ожидания относительно последовательности вызовов функций связки.

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

Случайные числа. Случайные числа формируются с помощью доступных источников случайности. В среде Linux обязательно используется системный файл dev/urandom, в среде Windows – сервис CryptGenRandom стандартного криптопровайдера. Дополнительно опрашивается генератор случайных чисел, иногда размещаемый на процессорах Intel, и аккумулируются разности между показаниями высокоточного таймера (регистра RDTSC) при приостановке текущего потока на 0 мс, т.е. при передаче управления ядру операционной системы с немедленным возвратом. Предусмотрена возможность использования любых дополнительных источников случайности.

Данные от источников объединяются, и по ним формируется ключ алгоритма генерации псевдослучайных чисел, определенного в СТБ 34.101.47. При каждом вызове алгоритма кроме ключа, состояния и монотонного счетчика обязательно обрабатываются данные от доступных источников случайности.

Алгоритмы. Большое внимание уделено выбору оптимальных арифметических алгоритмов. Были проведены достаточно подробные вычислительные эксперименты и их результаты учтены в окончательных редакциях программ. Например, при создании кольца классов вычетов целых чисел по модулю m реализуется следующая основанная на экспериментах стратегия выбора функции редукции x ↦ x mod m: если m имеет вид 2^nw – c, где w – длина машинного слова, n ≥ 2 и c < 2^w, то используется редукция Крэндалла; иначе, если m – нечетное, – редукция Монтгомери; иначе, если m > 2^4w, – редукция Барретта, иначе – обычная редукция через деление уголком.

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

В функциях работы с машинными словами активно применяются алгоритмические трюки из прекрасной книги [Уоррен Генри Мл. Алгоритмические трюки для программистов. – М.: Издательский дом «Вильямс», 2003].

Алгебраическая абстракция. Работа с алгебраическими структурами реализована через довольно общие, но и достаточно насыщенные интерфейсы.   Например, интерфейс qr описывает работу с абстрактным кольцом вычетом по модулю его идеала.  Предусмотрены функции сложения, вычитания, аддитивного обращения, умножения, возведения в квадрат, мультипликативного обращения, деления, экспорта в строку октетов и импорта из такой строки. Реализация всех функций интерфейса не обязательна. В Bee2 интерфейс qr инстанциируется многими способами: zm – кольцо вычетов целых чисел, pp – кольцо многочленов, gfp – простое поле из p > 2 элементов, gf2 – поле характеристики 2. Арифметика эллиптических кривых описывается интерфейсов ec, который является надстройкой над qr.

Доверие. Главный фактор доверия к криптографической программе – открытые исходные тексты. Библиотека Bee2 является открытым программным обеспечением, распространяется на условиях GNU General Public License версии 3. Исходные тексты размещены по адресу https://github.com/agievich/bee2.