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

<img src=«habrastorage.org/files/517/368/9a4/5173689a45614ede98883121cd77379a.jpg» title=«Кадр з фільму „Стережись автомобіля'“ align=»right"/>Давним-давно, ще в дев'яностих роках минулого століття, яка набирає обертів автомобільний ринок потребував появі серйозних протиугінних систем (далі по тексту — іммобілайзерів). Для автовикрадачів в ті часи не було особливих перешкод, що заважали завести двигун механічною копією ключа або навіть зовсім без ключа — простим замиканням проводів. Потрібні були іммобілайзери, здатні утруднити процес старту двигуна та подальшого викрадення автомобіля без рідного ключа запалювання.

Ось тоді і з'явилася ідея створення компактного радіомодуля (далі по тексту — транспондера), що вбудовується прямо в ключ запалювання автомобіля. В автомобіль ж встановлювався іммобілайзер, спілкується з транспондером по радіоканалу. Іммобілайзер посилав в транспондер запит, а транспондер відповідав певним кодом, без отримання якого іммобілайзер не дозволяв запустити двигун. Однак спочатку транспондери все одно були досить примітивними, порівняно легко клонируемыми пристроями. Досить було наявність радиоперехватчика і світлої голови на плечах, щоб розібратися в алгоритмі обміну і зімітувати відповідь транспондера. Потрібно кардинальна зміна алгоритму спілкування іммобілайзера з транспондером.

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

Далі по тексту всі картинки будуть клікабельними, щоб при бажанні їх можна було детально розглянути.

Частина перша: Індіанець Джо
Отже, попит народжує пропозицію: поступово на ринку почали з'являтися системи, використовували шифрування в процесі передачі даних по радіоканалу. Ці системи, по суті, виконували процес бездротовий ідентифікації власника ключа. При цьому секретний ключ зберігається в транспондері, не передавався в ефір у якому-небудь виді, а використовувався для криптографічного «підписування» запиту, отриманого від іммобілайзера. Одну з таких систем розробили інженери корпорації 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 з них. Наслідком цього є поява великої кількості помилкових результатів при подальшому переборі всіх можливих комбінацій ключів шифрування. Однак це не стало занадто великою проблемою — достатньо було черговий знайдений ключ перевірити ще раз, але вже з іншою парою запит/відповідь. Якщо друга перевірка також давала збіг, то ключ вважався знайденим.

Далі хлопці розробили апаратний брутфорсер ключів на базі плати з XILINX FPGA на борту, яка обійшлася їм за ціною трохи менше $200. На кристалі цієї FPGA їм вдалося розмістити 32 хеширующих ядра, синхронно працюють на частоті 100 МГц. Кожне з ядер перебирало свій піддіапазон ключів шифрування. В ідеалі одна така плата повинна була перебирати весь діапазон ключів приблизно за 19 години роботи: (240x200) / (100x106x32x3600) = 19.09 години. Але в реальності частину часу йшла на накладні витрати — отримання команд від комп'ютера. Тому повний перебір займав майже 21 год. Для прискорення процесу перебору були придбані ще 15 таких же плат. У кожну з них вони запрограмували з 32 таких же ядра, об'єднали плати один з одним в одну мережу і отримали в результаті кластер з 512 паралельно працюючих ядер. У цьому випадку кожному ядру належало виконати максимум 240 / 512 = 231 повних циклів хешування. Цей кластер справлявся із завданням менше ніж за півтори години.

Першим піддослідним кроликом став ключ запалювання від автомобіля 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 мегагерц. В результаті швидкість перебору склала 128x200x106 / 200 = 128 мільйонів хешів в секунду. Пристрій виконав повний перебір всіх варіантів за 2 години 24 хвилини. Це, звичайно, було досить непоганим результатом, але все-таки не настільки хорошим, щоб на цьому зупинитися.

Далі я опишу кілька кроків, зроблених для прискорення процесу перебору. Отже…

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

Крок другий
Подивимося на таблиці істинності логічних елементів, наведених в самому кінці документа.

Уважно подивимося на таблицю істинності функції Fe
00000: 0
 
00001: 0
 
00010: 1
 
00011: 1
 
00100: 0
 
00101: 0
 
00110: 1
 
00111: 1
 
01000: 0
 
01001: 0
 
01010: 0
 
01011: 0
 
01100: 1
 
01101: 1
 
01110: 1
 
01111: 1
 
10000: 1
 
10001: 1
 
10010: 1
 
10011: 1
 
10100: 0
 
10101: 0
 
10110: 0
 
10111: 0
 
11000: 1
 
11001: 1
 
11010: 0
 
11011: 0
 
11100: 1
 
11101: 1
 
11110: 0
 
11111: 0
 


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

Тепер таблиця істинності придбала ось такий вигляд
0000: 0
 
0001: 1
 
0010: 0
 
0011: 1
 
0100: 0
 
0101: 0
 
0110: 1
 
0111: 1
 
1000: 1
 
1001: 1
 
1010: 0
 
1011: 0
 
1100: 1
 
1101: 0
 
1110: 1
 
1111: 0
 


Очевидного приросту швидкості це не дає. Однак, як відомо, будь-яке зменшення кількості комбінаторної логіки в синхронних схемах позитивно позначається на можливості нарощування тактової частоти.

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


Крок третій
У програмістів, які намагаються вичавити максимум швидкості з зацикленого шматка програми, є такий спосіб оптимізації як «розгортання циклів». Полягає він у тому, що лічильник циклів зменшується в 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-го), то сумарна швидкість перебору склала 4x125x106 = 500 мільйонів хешів в секунду. Вже досить непогано!

Крок четвертий
Ну і фінальний штрих — оверклокінг! Куди ж без нього? 125 мегагерц, отримані на попередньому кроці — це частота, при якій ще не лається аналізатор TimeQuest. Але чіпи Cyclone V мають досить пристойний «запас міцності» за швидкості. Скористаємося цим і будемо піднімати тактову частоту схемою до тих пір, поки вона не почне помилятися — пропускати повз вуха правильні комбінації вихідних даних. Щоб оцінити коректність роботи схеми, програма в HPS-процесорі була замінена на тестову: в кожному циклі вона формувала випадкові пари ключів/запитів, обчислювала відповідь, грузила все це добро в конвеєр і запускала схему. Якщо через 64 такту схема не повідомляла про успішне виявлення збігу — тест вважався пройденим — частоту схеми потрібно було знижувати. Таким способом була знайдена гранична частота, на якій схема зберігала працездатність: 170 мегагерц. На 175 мегагерцах схема починала давати збої. На 170 мегагерцах швидкість перебору склала 4x170x106 = 680 мільйонів хешів в секунду. З перебором всіх можливих варіантів ключів пристрій справлялося менш ніж за 27 хвилин.

Нижче наведено відеоролик, що демонструє використання даного брутфорсера на практиці:



Частина п'ята: заключна
Підсумкова ефективність брутфорсера на базі DE0-Nano-SoC перевищила ефективність 512-ядерного кластера, побудованого командою Еві, приблизно в 90 разів (конструкція вийшла у 30 разів дешевше і втричі швидше) — що на сучасному етапі, втім, зовсім не дивно.

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

Отже дозвольте відкланятися! Всім здоров'я і удачі! Спасибі за увагу!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.