FPGA (по-русски ПЛИС) по сути является конструктором. Чип большей частью состоит из типовых блоков, каждый из них программируется из флеш-памяти после включения. Это позволяет создать на его основе практически любое цифровое устройство.

В среде разработки Quartus от Altera можно рисовать различные логические примитивы и соеденять их "проводами", но это используется только для демонстрации. Давным давно для этого существуют HDL - языки, описывающие логические примитивы разного уровня и соеденения между ними. Наиболее известные - VHDL и Verilog. Даже программируя на них, в силу очень низкого уровня (крайне низкого уровня) создать что-либо практичное не очень легко. Процедурный подход становится просто бессмысленным. Однако немало криптографических алгоритмыов традиционно очень хорошо описываются примитивными логическими операциями.

Создание на FPGA устройства, которое будет выполнять процедуру шифрования по алгоритму DES не сложно. Это устройство будет иметь условно два входа - ключ и входные данные и один выход - результат.

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

FPGA можно переконфигурировать условно бесконечное количество раз и пробовать разные возможности имплементации алгоритма, но для этого в них есть коммутирующая логика, которая также программируется при включении, указывающая какие примитивы с какими соеденять. Отправив сигнал из одного места в другое, вплоть до 80% пути он будет идти по этой логике и только 20% времени будет выполняться полезная работа. Этого не будет в ASIC (заказных чипах созданных по вашему проекту), где будет только то что нужно. Таким образом был создан например EFF DES cracker [2].

Итак, алгоритм хеширования паролей [3] в СУБД Oracle (версий до 11) базируется на хорошо известном алгоритме DES. Позже, в версии 11, там был введен также SHA1, но старая схема продолжает использоваться повсеместно, потому что, по иронии судьбы, новый SHA1 перебирается намного быстрее. Итак, как алгоритм работает: к строке содержащей имя пользователя прибавляется строка с паролем. Полученная строка шифруется алгоритмом DES в режиме CBC ключом 0x0123456789ABCDEF. Результат действия последнего вызова шифрующей функции DES образует новый ключ. Строка с именем пользователя и паролем снова шифруется, но уже с новым ключем. Результат последней итерации и является хешем.

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

Начинаем с функции DES [4]. Если не вдаваться в очень непростые особенности этого алгоритма шифрования (с момента создания DES и до наших дней, так и не появилось сколь-нибудь практичного способа взлома кроме как полным перебором ключей), для нас он состоит из трех функций: функция подготовки входных данных (initial permutation), функция шифрования повторяющаяся 16 раз (в алгоритме DES 16 "раундов") и функции подготовки выходных данных (final permutation).

Решение "в лоб" - это расставить все 16 одинаковых блоков в ряд, но это не обязательно самый лучший вариант. Второй вариант это поставить только один блок и создать цикл из 16-и итераций, и каждый раз результат подавать снова на вход этому блоку. С программистской точки зрения эти решения равноценны. Причем даже первый вариант предпочтительнее, потому что мы можем слегка сэкономить на том времени, которое процессор будет тратить на обеспечение цикла (проверить текущее значение и если менее 16, то перейти на начало цикла). Но, как я упоминал, в FPGA имеется коммутирующая логика, и было бы очень хорошо использовать её как можно меньше и реже. Таким образом, блок использующий как можно меньше примитивов будет более выгодным в итоге. На входе нашего блока будет 64-х битный регистр (можно сказать, состоящий из D-триггеров), куда мы после каждой итерации будем отправлять результат. Здесь также будет счетчик, сбрасываемый в 0 при RESET, и останавливающийся на 16-й итерации.

Интересен также вопрос с перестановочным таблицами DES (S-боксы). Всего в алгоритме используется 8 таблиц, индекс 6-битный, выход 4 бита. Существуют решения, в которых, для оптимизации (например: [5]), таблицы раскладываются в логическую функцию, и полученная схема не требут никаких таблиц вообще. Это подходит для современных процессоров, которые могут исполнять несколько инструкций одновременно, и тем более не обращаться ни к памяти ни к кешу. И там это действительно может помочь. Однако в случае с FPGA ситуация обратная. Известно что Quartus (среда разработки от Altera которая собственно и подготавливает файл прошивки для FPGA) напротив, когда это возможно, раскладывает логические функции в таблицы, и часть примитивных блоков их для этого имеют (LUT/ALUT). Подробнее об этом: [6].

Для иллюстрации, предположим что нам нужно создать устройство складывающее два четырехбитных числа по модулю 2 (XOR). Можно создать 4 примитива, каждый из которых будет обрабатывать свой бит, но значительно проще создать таблицу с 8-битным индексом и 4-битным выходом.

Таким образом, таблицы DES лучше оставить как есть.

Следующий вопрос это создание устройства, которое будет выполнять шифрование в режиме Cipher Block Chaining [7] (CBC). Здесь пока что ничего особенного, мы ставим еще один счетчик, который будет подавать на вход в блок DES исходные данные сложенные по модулю 2 (XOR) с предыдущим результатом или не делать этого если входной блок является первым.

Следующий вопрос это собственно хеш-функция от Oracle, которая уже будет брать на вход текстовую строку и выдавать результат. Здесь будет просто две фазы - первая это шифрование строки с ключом 0x0123456789ABCDEF и вторая фаза - шифрование её же, но с ключом полученным в конце первой фазы.

Итак, мы получили такое устройство. Для имени пользователя SYS и пароля не длиннее 9 символов, оно будет работать с таким количеством тактов: 16*4*2=128. 16 раундов DES, 4 итерации в CBC для шифрования 12 символов и 2 фазы.

Здесь начинается наиболее сложное. В чипе Stratix II EP2S60 можно имплементировать 60 таких блоков одновременно. Стоит задача распараллеливания. Выражаясь криптографическим языком, множество всех перебираемых нами паролей это keyspace, и нам нужно порезать этот keyspace на 60 частей, вернее даже резать его на ходу, в процессе работы. Более того, 60 не является константой. Может появиться необходимость запрограммировать совсем другой чип, в котором поместится 10 таких блоков или больше сотни.

По стандарту Oracle, первый символ пароля может быть только латинской буквой (таких 26) а остальные символы могут быть латинскими буквами, цифрами или символами "#", "$", "_" (таких 39). Имея в условии задачи только 26 или 39 блоков задача упростилась бы, мы могли бы просто подавать на каждый блок свой символ и за один раз обрабатывать 26 или 39 паролей.

Здесь мы переходим ко второй части проекта, которая более уже напоминает embedded-программирование. Нам нужен процессор, компилятор с языка вроде Си и что-то еще. Для таких целей Altera имеет софт-процессор Nios II [8] (а их конкурет Xilinx - MicroBlaze). Это типичный RISC-процессор, но он отличается от обычного тем, что его не существует "в железе", он написан на языке HDL и он конфигурируемый. Например можно включать и отключать некоторые его фичи, менять размер кеш-памяти, установить адрес в памяти откуда он будет стартовать и добавлять отладочные фичи. От всего этого будет зависеть, сколько места он будет занимать в FPGA и как быстро работать. Также Альтерой дописан back-end к известному компилятору GCC. Еще нам нужна шина, к которой будет подключаться процессор, DDR-память, девайсы вроде контроллера ethernet, светодиоды, кнопки, и прочее. Эта шина у Альтеры называется Avalon [9]. Также есть программа SOPC Builder [10] для соеденения всех этих модулей, раздачи всем адресов, прерываний и прочего.

Также в шину Avalon мы подключим все то что мы сделали до этого.

Итак, теперь у нас есть возможность писать на Си, и через порты обращаться к нашим блокам и читать результат.

Возвращаемся к проблеме распараллеливания. Проблем на самом деле даже несколько: 1) нужно раздать всем 60-и блокам свою часть пароля; 2) прочитать результат от всех и сравнить его с эталоном и если сошлось, то сказать об этом пользователю.

Время работы всего устройства в общем, можно разделить на время работы блоков шифрования и того что происходит уже на более высоком уровне в процессоре Nios II. Как я указал выше, для вычисления всего одного хеша, в случае с коротким именем пользователя, нужно хотя бы 128 тактов. Решение "в лоб" это раздать каждому блоку свой вариант пароля (а их 60), подождать 128 тактов и у каждого прочитать результат. Первая и третья задачи будут занимать отнюдь не 128 тактов а намного больше, и из-за этого у нас будет слишком низкий КПД. Третью задачу (сравнение с эталоном) можно решить очень просто: добавить в каждый блок компаратор и память для эталона, и тогда он будет сам сравнивать выход блока с эталоном и выставлять бит в еденицу в каком-то общем регистре: его-то и будет читать Nios II по шине и если все биты в 0, то продолжать далее. Но первая задача все еще стоит.

Для этого мы делаем следующее: у каждого блока на входе ставим немного памяти для входных данных. Из программы на Си мы сможем писать в память для каждого отдельного блока, так и для всех одновременно (выставив специальный бит в адресе). Теперь мы делаем следующее. К примеру, мы перебираем все трехсимвольные пароли. На старте мы записываем в память первого блока имя пользователя плюс "AA". В память второго блока - "AB", третьего "AC", и так далее для всех. Это относительно медленная процедура. Затем мы записываем во все блоки одновременно "A" в позиции третьего символа пароля и запускаем цикл. После 128 тактов, если ничего не найдено, мы записываем во все блоки одновременно "B" (а символы в первой и второй позициях все еще остаются там же). Затем "C", и так далее. Здесь мы уже кое-чего добились. Основную часть времени нашего устройства теперь составляет записать по одному адресу одного байта + 128 тактов + чтение из регистра всех результатов одновременно.

Еще кое-что. Вернемся снова к самому алгоритму кеширования. Для того чтобы получить хеш для пользователся SYS и пароля ABCDEFHJ, нужно составить строку "SYSABCDEFGHJ", нужно зашифровать её в режиме CBC (три итерации работы DES) и еще раз (для второй фазы алгоритма). Как видно, в первой фазе, на первой итерации шифруется SYSA, на второй BCDE, на третьей FGHJ. Мы знаем что большую часть времени меняется только последний символ в этой строке, то есть результат на первой и второй итерации CBC в первой фазе будет один и тот же. Таким образом, результат второй итерации можно закешировать и также сэкономить немало времени: на длинных именах пользователей это почти половина времени. Для этого на каждой препоследней итерации CBC, результат от DES мы будем ложить в регистр и в следующий раз брать оттуда. А если процессор записал что угодно в позициях, которые попадают не под последнюю итерацию, кеш сбрасывать.

Вот практически и все.

Для пользователя мы делаем web-интерфейс. Для этого можно взять пример от Altera. Там также имеется NicheStack TCP/IP Stack [11], известный в embedded-программировании. Web-страницу мы создаем "на ходу" (никакой абстракции файлов здесь просто нет) и обрабатываем HTTP GET-запросы. И еще нам нужно одновременно "раздавать" пароли и обрабатывать web-запросы от пользователя. Так что здесь мы можем использовать операционную систему MicroC/OS-II [12]. В основном, её фичи сильно отличаются от обычных ОС, потому как она предназначена для embedded-устройств. От нее мы будем импользовать только переключение задач.

Использованная плата: Nios II Development Kit, Stratix II Edition [13]. Из того что я использовал на плате: чип EP2S60, DDR-память, ethernet-контроллер, RS-232 порт, в который выдается отладочная информация.

Ссылки:

[1] Oracle Password Benchmarks

http://blog.red-database-security.com/2009/10/06/oracle-password-benchmarks/

[2] EFF DES cracker

http://en.wikipedia.org/wiki/EFF_DES_cracker

[3] Описание алгоритма его создателем (Bob Baldwin)

http://groups.google.com/group/comp.databases.oracle/msg/83ae557a977fb6ed

[4] Data Encryption Standard

http://en.wikipedia.org/wiki/Data_Encryption_Standard

[5] Bitslice DES

http://www.darkside.com.au/bitslice/

[6] Stratix II Performance and Logic Efficiency Analysis

http://www.altera.com/literature/wp/wpstxiiple.pdf

[7] Block cipher modes of operation

http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation

[8] Nios II Processor

http://www.altera.com/products/ip/processors/nios2/ni2-index.html

[9] Avalon Interface Specifications

http://www.altera.com/literature/manual/mnl_avalon_spec.pdf

[10] Literature: SOPC Builder

http://www.altera.com/literature/lit-sop.jsp

[11] NicheStack homepage

http://www.iniche.com/nichestack.php

[12] MicroC/OS-II homepage

http://micrium.com/page/products/rtos/os-ii

[13] Nios II Development Kit, Stratix II Edition

http://www.altera.com/products/devkits/altera/kit-niosii-2S60.html