Транспондер DST40: принцип работы, история появления и взлома, а также немного практики по брутфорсу

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

Вот тогда и появилась на свет идея создания компактного радиомодуля (далее по тексту — транспондера), встраиваемого прямо в ключ зажигания автомобиля. В автомобиль же устанавливался иммобилайзер, общающийся с транспондером по радиоканалу. Иммобилайзер посылал в транспондер запрос, а транспондер отвечал неким кодом, без получения которого иммобилайзер не позволял запустить двигатель. Однако поначалу транспондеры всё равно были довольно примитивными, сравнительно легко клонируемыми устройствами. Достаточно было наличие радиоперехватчика и светлой головы на плечах, чтобы разобраться в алгоритме обмена и сымитировать ответ транспондера. Требовалось кардинальное изменение алгоритма общения иммобилайзера с транспондером.

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

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

Часть первая: Индеец Джо

Итак, спрос рождает предложение: постепенно на рынке начали появляться системы, использовавшие шифрование в процессе передачи данных по радиоканалу. Эти системы, по сути, выполняли процесс беспроводной идентификации владельца ключа. При этом секретный ключ, хранящийся в транспондере, не передавался в эфир в каком-либо виде, а использовался для криптографического «подписывания» запроса, полученного от иммобилайзера. Одну из таких систем разработали инженеры корпорации Texas Instruments. Разработанный ими транспондер получил название Digital Signature Transponder (сокращённо — DST).

Транспондер DST получился весьма малогабаритным, что позволило без особых проблем встраивать его в различные компактные токены: например, в автомобильные ключи зажигания или в брелки для ключей. На приведённой фотографии, в ручке возле лезвия, видно закрытое заглушкой отверстие, через которое транспондер помещается внутрь ключа. А использование в его конструкции схемы хеширования сделало процесс радиосниффинга совершенно бесполезным (до поры, до времени — но об этом чуть позже), потому что через эфир передавались настолько разные блоки данных, что логически проследить хоть какую-нибудь зависимость в них стало ну просто невозможно.

Состоит транспондер из следующих основных компонентов:

• Антенна и приёмо-передатчик (далее по тексту — трансивер): предназначены для запитывания транспондера и для связи с базовой станцией по радиоканалу.
• Схема шифрования: предназначена для хеширования запроса, полученного от базовой станции.
• Энергонезависимая перезаписываемая память: предназначена для хранения ключа шифрования и некоторых дополнительных параметров (например, серийного номера транспондера и ID производителя).

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

Алгоритм работы всей системы беспроводной аутентификации такой:

• Базовая станция передаёт немодулированный радиосигнал такой мощности и длительности, чтобы его хватило для запитывания всей электронной схемы транспондера, находящегося в зоне действия трансивера базовой станции.
• Базовая станция, с помощью генератора случайных чисел, формирует 40-битный запрос, запоминает его и передаёт в эфир, используя амплитудную модуляцию радиосигнала.
• Трансивер ещё некоторое время излучает немодулированный радиосигнал — чтобы транспондеру хватило питания для выполнения вычислительных операций.
• Транспондер, получив от базовой станции запрос, выполняет его хеширование по алгоритму DST40, используя 40-битный ключ шифрования, хранящийся в его энергонезависимой памяти: в результате получается так-называемая «подпись».
• Транспондер передаёт цифровую подпись и служебную информацию в базовую станцию.
• Базовая станция выполняет хеширование только что переданного в транспондер запроса с помощью такого же ключа шифрования, который хранится и в ней: если результат совпал с полученным от транспондера, то аутентификация считается успешной. Если данная базовая станция используется в качестве иммобилайзера автомобиля, то после успешной аутентификации она передаёт в центральный компьютер автомобиля разрешение старта двигателя.

Не совсем понятно, на чём основывались соображения инженеров-разработчиков, но факт остаётся фактом: длина ключа шифрования, используемого в процессе хеширования, составляет всего 40 бит (вот, кстати говоря, почему алгоритм получил название DST40). Такая длина ключа шифрования, с современной точки зрения, является совершенно недостаточной для обеспечения хоть сколько-нибудь приличной безопасности. Но в то время, по всей видимости, инженерам-разработчикам так не казалось. Кроме того алгоритм DST40 является сугубо проприетарным и раскрывается производителям только под строжайшие подписки о неразглашении.

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

В результате транспондеры DST40 стали исключительно популярны. Их взяли на вооружение ряд крупных автомобильных корпораций (например, Toyota, Ford, Lincoln, Nissan и другие). Многие миллионы автомобилей, иммобилайзеры которых используют транспондеры DST40, постепенно наводнили не только рынки США, но и рынки других стран, активно импортирующих автомобили из США. Мало того, эти транспондеры также стали использоваться в системе бесконтактной оплаты SpeedPass, стремительно завоёвывающей различные фаст-фуды, супермаркеты, рестораны и бензозаправки в США.

Часть вторая: И грянул гром!

Всем давно известно, что индеец Джо остаётся неуловимым лишь до того момента, пока он никому не нужен. Так и в этой истории алгоритм DST40 оставался невзломанным лишь до тех пор, пока за него не взялись молодые, энергичные ребята.

Произошло это в 2004 году. К тому времени уверенность инженеров Texas Instruments в стойкости алгоритма DST40 стала настолько большой, что их просто распирало от гордости и от желания хоть с кем-нибудь поделиться своими достижениями. И они решили командировать одного из сотрудников немецкого подразделения компании — доктора Ульриха Кайзера — на четвёртую конференцию по AES с небольшим обзорным докладом о DST40. Именно этот доклад стал началом конца индейца Джо.

Дело в том, что на этой конференции присутствовал эксперт по криптографии, преподаватель Университета информационной безопасности Джонса Хопкинса (США), профессор Эви Рубин (Aviel D. Rubin). Ему было достаточно одного взгляда на общую схему алгоритма, чтобы увидеть в ней серьёзные прорехи в безопасности. Вот так выглядела эта схема:

Несмотря на то, что схема была весьма общей и в ней отсутствовали многие тонкие детали, намётанный глаз опытного криптографа сразу же зацепился за несколько уязвимостей: во-первых, было видно, что по каждому такту регистры ключа шифрования и запроса/ответа подвергались минимальным модификациям — всего лишь в одном бите. Во-вторых, было очевидно наличие «слабого» ключа шифрования, состоящего из одних нулей — в процессе хеширования он так и останется обнулённым до самого конца. Это открывало возможность проведения над транспондером различных криптоаналитических опытов, способных раскрыть его внутреннюю структуру. И, в-третьих, длина ключа составляла всего 40 бит, что по меркам 2004-го года было совершенно недостаточно, чтобы противостоять брутфорсу, выполняемому с помощью аппаратных средств.

Конечно же, Эви понимал, что крупную компанию, занимающую значительный сегмент в производстве подобных устройств, невозможно убедить в слабости и уязвимости алгоритма просто словами. Вот тогда ему и пришла в голову идея взломать DST40 на практике — что явилось бы самым неопровержимым аргументом. Прежде всего, он решил собрать команду из нескольких студентов университета. Он выбрал наиболее энергичных и способных парней, которым и предложил заняться этим делом: покопаться в алгоритме, а заодно и подтянуть теоретические знания и практические навыки по криптографии и криптоанализу. Так появилась на свет команда, в которую вошли (на приведённой фотографии в порядке слева-направо) Адам Стаблфилд (Adam Stubblefield), Эви Рубин (Aviel D. Rubin), Стивен Боно (Stephen C. Bono) и Мэтью Грин (Matthew Green).

Следующим шагом стало приобретение у Texas Instruments набора разработчика TI Series 2000 — LF RFID. В этот набор входил приёмо-передатчик для общения с транспондерами и несколько транспондеров, которые, впрочем, были совершенно бесполезны, так как не выполняли шифрование по алгоритму DST40. Так что нужные транспондеры парням пришлось приобрести отдельно.

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

Вместо этого они решили использовать для взлома метод «предсказателя» или «чёрного ящика». Говоря простым языком, они стали проводить различные эксперименты, записывая в транспондеры разные ключи шифрования, а также передавая в них разные запросы и изучая полученные из них результаты хеширования.

Из схемы Кайзера было видно, что основой схемы шифрования является широко используемая в других алгоритмах шифрования сеть Фейстеля на логических элементах с фиксированными таблицами истинности. Для полного взлома алгоритма парням необходимо было решить три задачи:

• Проверить, соответствует ли схема Кайзера действительности.
• Определить пути разводки сигналов от каждого из битов регистров ключа и запроса к логическим элементам.
• Вычислить таблицы истинности всех логических элементов.

Не буду детально углубляться в описание проводимых экспериментов: кому интересно, могут сами ознакомиться с ними в этом документе, представленном публике на 14 симпозиуме по безопасности USENIX, проходившем в Балтиморе в 2005 году.

Скажу только, что в результате парням удалось успешно решить все три задачи и восстановить полную схему соединений функциональных блоков, входящих в модуль шифрования DST40, включая таблицы истинности этих блоков. Причём следует заметить, что реальная функциональная схема оказалась не полностью соответствующей схеме Кайзера. Отличий обнаружилось несколько:

• После старта хеширования на схему подаётся не 400, а 200 тактовых импульсов.
• Регистр запроса по каждому такту сдвигается не на один, а сразу на два бита.
• Логический элемент, обозначенный на схеме Кайзера «F21» имеет не один, а два выхода, которые, прежде чем попасть в самые левые (по схеме) два бита регистра запроса, XOR-ятся с двумя самыми правыми битами из этого-же регистра.
• Для вычисления очередного левого (по схеме) бита ключа шифрования используются не те биты, что показаны на схеме.

Также парням удалось выяснить алгоритм модификации ключа шифрования: ключ изменяется по каждому третьему такту, начиная со второго.

Мало того, обнаружилось, что результирующий хеш передаётся транспондером в эфир не полностью — не все 40 бит, а только 24 из них. Следствием этого является появление большого количества ложных результатов при дальнейшем переборе всех возможных комбинаций ключей шифрования. Однако это не стало слишком большой проблемой — достаточно было очередной найденный ключ проверить ещё раз, но уже с другой парой запрос/ответ. Если вторая проверка также давала совпадение, то ключ считался найденным.

Далее парни разработали аппаратный брутфорсер ключей на базе платы с FPGA XILINX на борту, которая обошлась им по цене чуть менее $200. На кристалле этой FPGA им удалось разместить 32 хеширующих ядра, синхронно работающих на частоте 100 МГц. Каждое из ядер перебирало свой поддиапазон ключей шифрования. В идеале одна такая плата должна была перебирать весь диапазон ключей примерно за 19 часов работы: (2⁴⁰x200) / (100x10⁶x32x3600) = 19.09 часа. Но в реальности часть времени уходила на накладные расходы — получение команд от компьютера. Поэтому полный перебор занимал почти 21 час. Для ускорения процесса перебора были приобретены ещё 15 таких же плат. В каждую из них они запрограммировали по 32 таких же ядра, объединили платы друг с другом в одну сеть и получили в результате кластер из 512 параллельно работающих ядер. В этом случае каждому ядру предстояло выполнить максимум 2⁴⁰ / 512 = 2³¹ полных циклов хеширования. Этот кластер справлялся с задачей менее чем за полтора часа.

Первым подопытным кроликом стал ключ зажигания от автомобиля Ford Escape SUV модели 2005 года, оснащённый именно таким транспондером. С помощью набора разработчика в ключ были переданы два случайных запроса и получены два соответствующих им ответа. Эти две пары запросов/ответов стали исходными данными, поданными на брутфорсер перед стартом перебора. Менее чем через час после старта перебора секретный ключ был успешно найден.

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

На приведённом ниже видеоролике Адам и Мэтью демонстрируют процесс старта двигателя с помощью симулятора:



Затем с помощью этого симулятора они успешно приобрели бензин на заправке с системой оплаты SpeedPass:



После успешного проведения всех этих экспериментов было решено опубликовать полученную информацию. В то время Эви входил в совет директоров ассоциации USENIX — поэтому вполне логичным решением стала публикация данной информации на очередном симпозиуме по безопасности USENIX.

Однако, дабы предотвратить стремительное крушение платёжных систем и не дать ворам в руки средство для лёгкого взлома иммобилайзеров, парни не стали публиковать всю информацию. Например, не была опубликована финальная функциональная схема хеширования. Единственное, что они предоставили в качестве подтверждения правдивости своих слов — это формулы, описывающие алгоритм хеширования ключа и таблицы истинности функциональных элементов, составляющих сеть Фейстеля. Этого было совершенно достаточно, чтобы инженеры из Texas Instruments осознали полное фиаско алгоритма DST40.

Часть третья: А не извлечь ли из этого пользу?

Шёл 2009 год. По земле с грохотом катилась набирающая силы волна кризиса. Два человека, назовём их, условно, Стив и Джон, активно искали варианты получения дополнительного заработка. Нашумевшая история со взломом транспондеров DST40 натолкнула их на мысль, что на этом деле можно маленько заработать. Идея заключалась в том, чтобы предлагать установку систем дистанционного запуска двигателя владельцам автомобилей, оснащённых подобными иммобилайзерами. В тот момент времени подобные системы уже существовали, однако все они требовали жертвования одним ключом от автомобиля: его необходимо было разместить в салоне в непосредственной близости от устройства дистанционного запуска. Понятно, что это лишало использование иммобилайзера какого-бы то ни было смысла и вынуждало автовладельца устанавливать в автомобиль отдельную сигнализацию. В данном же случае автовладельцам предлагалась система, лишённая этих недостатков: предполагалось, что она будет сама имитировать ключ зажигания, причём будет делать это только в момент получения команды на дистанционный запуск двигателя.

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

Затем они изготовили две конструкции:

первая из них представляла собой программатор транспондеров DST40. Она позволяла считывать открытую информацию из транспондеров, передавать в транспондер запрос и получать из него результат хеширования — подобно тому, как это делает автомобильный иммобилайзер, а также позволяла записывать в транспондер открытую информацию вместе с ключом шифрования. С помощью программатора были получены две пары запросов/ответов для ключа зажигания от автомобиля Toyota Camry 2005 года выпуска.

Вторая конструкция представляла собой брутфорсер, построенный на основе FPGA-чипа Xilinx Spartan 3E. Брутфорсер позволял методом перебора находить ключ шифрования, хранящийся в транспондере. Для этого на вход брутфорсера подавались исходные данные в виде двух комбинаций запросов/ответов и ключа шифрования, с которого нужно было начать перебор. Работал брутфорсер на частоте 135 мегагерц, вмещал на кристалле FPGA 32 хеширующих ядра и выполнял полный перебор всех комбинаций примерно за 14 часов.

Результат был, прямо скажем, не вселяющим оптимизма: ждать по нескольку часов, когда брутфорсер сделает свою работу, было не очень приятным занятием. Поэтому Стив и Джон обратили свои взоры на другой участок передачи данных — между центральным компьютером Тойоты и блоком иммобилайзера. После проведения небольшого обследования и нескольких тестов выяснилось, что этот участок хоть и имеет некоторую маскировку передаваемых данных, но настолько примитивную, что не составило никакого труда разобраться в ней и внедрить своё устройство в разрыв этого тракта. Пока устройство работало в режиме ожидания, оно просто транслировало данные от компьютера к иммобилайзеру и обратно сквозь себя. Если же оно получало команду на дистанционный завод двигателя, то отключало иммобилайзер и начинало общаться с компьютером самостоятельно — имитируя положительные ответы от иммобилайзера. А самое главное во всём этом процессе было то, что ответ иммобилайзера зависел только и только от запроса компьютера. Ключ зажигания стал попросту не нужен.

Программатор и брутфорсер остались невостребованными.

Часть четвёртая: Чисто спортивный интерес

Прошло ещё несколько лет после описанных выше событий и вот однажды мне в руки попала плата DE0-Nano-SoC. Её сердцем является чип Altera Cyclone V SE 5CSEMA4U23C6N. Он содержит в себе двухъядерный HPS-процессор (Hard Processor System) ARM Cortex-A9 и FPGA с 15094 адаптивными логическими модулями (ALM). В комплекте с платой производитель даёт ОС Linux, развёрнутую на карту памяти MicroSD. Это позволяет легко реализовать пользовательский интерфейс — не тратя на это много времени. После освоения этого дивайса мне вспомнилась та история про взлом транспондера DST40 и возник чисто спортивный интерес — сколько можно выжать хешей в секунду при брутфорсе ключей DST40 с помощью такого устройства?

Имея на руках нарисованную Стивом и Джоном схему, а также две пары запросов/ответов, полученных ими из ключа Тойоты, я взялся за дело. Сначала был избран простой путь экстенсивного наращивания количества хеширующих ядер, коих на кристалл FPGA этой платы поместилось целых 128 штук:

На этой схеме отображены следующие компоненты:

• HPS-процессор — выполняет программу dst40. Она запрашивает исходные данные у пользователя, загружает их в регистры блока управления, запускает/останавливает процесс перебора и выводит информацию о текущем состоянии на экран.
  
• Блок управления. Его задачей является подготовка исходных данных для всех хеширующих ядер, управление их работой, проверка результатов и передача их в HPS.
  
• Хеширующие ядра. Каждое ядро формирует исходный ключ из двух частей: 7-битной фиксированной старшей части, совпадающей с порядковым номером ядра (00H для ядра номер 0, 7FH для ядра номер 127) и 33-битной переменной младшей части, полученной из блока управления. Ядра выполняют хеширование запроса по алгоритму DST40, в конце этого процесса сравнивают результат хеширования с ответом и передают результат сравнения в блок управления.
  

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

1. Программа запрашивает у пользователя исходные данные: два запроса, переданных в транспондер и два соответствующих им ответа, полученных из транспондера, а также ключ шифрования, с которого следует начать перебор.
2. Программа загружает первый запрос/ответ и ключ в блок управления и запускает процесс перебора. После этого ждёт, когда блок управления сообщит ей об обнаружении совпадения или об исчерпании перебираемых ключей.
3. Блок управления выставляет запрос/ответ и ключ на входы исходных данных всех ядер и даёт им команду начать хеширование.
4. Каждое ядро выполняет хеширование запроса. На это уйдёт 200 тактов. По окончанию работы каждое ядро сравнивает результат хеширования с ответом и отправляет результат сравнения в блок управления.
5. Блок управления оценивает результаты работы всех ядер: если совпадений не найдено, то инкрементирует ключ и переходит к шагу 3 алгоритма.
6. Если же хотя-бы одно ядро обнаружило совпадение, то блок управления передаёт в программу найденный ключ вместе с номером ядра, обнаружившим совпадение.
7. Программа передаёт вторую пару запрос/ответ в блок управления и даёт ему команду продолжать поиск с текущего ключа.
8. Блок управления выполняет шаги с 3 по 5 алгоритма. Если совпадение опять обнаружено — информация об этом передаётся программе.
9. Программа сравнивает ключ и номер ядра с предыдущими — если совпадают, значит ключ найден. Процесс перебора завершён. Если не совпадают, то поиск продолжается.

Аппаратная часть конструкции заработала на тактовой частоте 200 мегагерц. В результате скорость перебора составила 128x200x10⁶ / 200 = 128 миллионов хешей в секунду. Устройство выполнило полный перебор всех вариантов за 2 часа 24 минуты. Это, конечно, было весьма неплохим результатом, но всё-таки не настолько хорошим — чтобы на этом остановиться.

Дальше я опишу несколько шагов, предпринятых для ускорения процесса перебора. Итак…

Шаг первый

Начнём с оптимизации алгоритма. Взглянем ещё раз на приведённую выше схему хеширования. Мы видим, что результат хеширования считывается из младших 24 бит регистра запроса/ответа. Старшие 16 бит не используются. Возникает закономерный вопрос: зачем выполнять последние 8 тактов, если их результат потом выбрасывается? Ответ: совершенно незачем. Достаточно подать на схему 192 такта, а затем забрать результат хеширования из старших 24 бит регистра. Так и поступим: это даст нам совершенно бесплатный четырёхпроцентный прирост скорости.

Шаг второй

Посмотрим на таблицы истинности логических элементов, приведённых в самом конце документа.


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


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

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

Шаг третий

У программистов, пытающихся выжать максимум скорости из зацикленного куска программы, есть такой способ оптимизации как «разворачивание циклов». Заключается он в том, что счётчик циклов уменьшается в N раз, а последовательность команд, выполняемых в этом цикле, повторяется друг за другом N раз. Это позволяет уменьшить избыточность, вносимую командами обслуживания счётчиков цикла.

Попробуем и мы воспользоваться этим методом: развернём весь 192-тактовый цикл в одну сплошную линию. Реализация этого варианта вполне возможна, так как работа каждого цикла зависит только от результатов выполнения предыдущего цикла и больше ни от чего другого:

В этой схеме каждый блок логики с названием «ЦИКЛ N» включает в себя всю сеть Фейстеля, используемую в алгоритме DST40. Понятно, что длина логических цепей станет ненормально большой и скорость тактирования придётся значительно снизить. Однако, такая схема будет выдавать результат по каждому такту, а не по каждому 192-му такту, как это было исходно — стоит попробовать!

Реализуем такую схему и испытаем: как и ожидалось, тактовую частоту пришлось уменьшить до 2 мегагерц, а логики получилось так много, что на кристалл еле-еле поместилось 8 ядер. 16 миллионов хешей в секунду — это совершенно несерьёзно!

Выбросить эту идею на свалку? Ни в коем случае! Есть ещё один козырь, который теперь можно вытащить из рукава. Называется он конвейер. Полагаю, многим из читателей о конвейерах известно. А если неизвестно, то рекомендую почитать о них в замечательной статье Ивана Шевчука aka ishevchuk — "Пару слов о конвейерах в FPGA".

Итак, нарежем логическую цепь на 192 звена, на стыках между которыми поставим по два сорокабитных регистра:

Компилируем. Заработала эта конструкция на той же самой частоте, что и исходная конструкция из 128 ядер — 200 мегагерц. Но теперь новые исходные данные поступают на её вход по каждому такту. Результат также теперь снимается с выходов схемы по каждому такту (начиная с 192 такта). Ускорение составило 192 раза! Ура, ура! Однако, не всё так радужно, как хотелось бы. Схема ядра распухла настолько, что на кристалл поместилось всего одно ядро. Результирующая скорость перебора составила 200 миллионов хешей в секунду.

Не будем отчаиваться — поищем компромисс. Давайте внимательно посмотрим на получившуюся схему ещё раз. В глаза бросается то, что вся цепь из 192 звеньев как бы состоит из 64 одинаковых блоков по 3 звена: в первом звене блока регистр ключей не изменяется, во втором — сдвигается на 1 бит, а в третьем опять не изменяется. Попробуем изменить схему: уберём регистры, режущие эти блоки на три части. Таким образом количество звеньев цепи сократится до 64, а длина логических цепей каждого звена увеличится втрое. Результатом этого станет необходимость в понижении тактовой частоты, но в то же самое время размер ядра должен будет значительно сократиться.

Реализуем такую схему и получаем в результате возможность разместить на кристалле четыре таких ядра. Анализатор TimeQuest позволил запустить эту схему на 125 мегагерцах. Но так как ядер стало четыре и схема даёт по четыре результата на каждом такте (начиная с 64-го), то суммарная скорость перебора составила 4x125x10⁶ = 500 миллионов хешей в секунду. Уже весьма неплохо!

Шаг четвёртый

Ну и финальный штрих — оверклокинг! Куда же без него? 125 мегагерц, полученные на предыдущем шаге — это частота, при которой ещё не ругается анализатор TimeQuest. Но чипы Cyclone V имеют весьма приличный «запас прочности» по скорости. Воспользуемся этим и будем поднимать тактовую частоту схеме до тех пор, пока она не начнёт ошибаться — пропускать мимо ушей правильные комбинации исходных данных. Чтобы оценить корректность работы схемы, программа в HPS-процессоре была заменена на тестовую: в каждом цикле она формировала случайные пары ключей/запросов, вычисляла ответ, грузила всё это добро в конвейер и запускала схему. Если через 64 такта схема не сообщала об успешном обнаружении совпадения — тест считался не пройденным — частоту схемы нужно было понижать. Таким способом была найдена предельная частота, на которой схема сохраняла работоспособность: 170 мегагерц. На 175 мегагерцах схема начинала сбоить. На 170 мегагерцах скорость перебора составила 4x170x10⁶ = 680 миллионов хешей в секунду. С перебором всех возможных вариантов ключей устройство справлялось менее чем за 27 минут.

Ниже приведён видеоролик, демонстрирующий использование данного брутфорсера на практике:

Часть пятая: заключительная

Итоговая эффективность брутфорсера на базе DE0-Nano-SoC превысила эффективность 512-ядерного кластера, построенного командой Эви, примерно в 90 раз (конструкция получилась в 30 раз дешевле и втрое быстрее) — что на современном этапе, впрочем, совсем неудивительно.

Если кто желает «покопаться» в исходниках, то это можно сделать вот здесь. Там же в директории bin лежит скомпилированная прошивка для заливки в FPGA (тактовая частота ограничена величиной 150 МГц — для надёжности) и скомпилированная программа для запуска на HPS под Linux-ом.

Засим разрешите откланяться! Всем здоровья и удачи! Спасибо за внимание!