Обход беспарольной авторизации уже давно будоражит умы компьютерных энтузиастов. При мыслях о биометрике по спине проходит холодок: ну а вдруг как отрежут палец или вырвут глаз? А самый гуманный и уже никого не удивляющий способ — это, конечно, USB-ключи. На очном туре NeoQUEST-2013 мы предложили участникам взломать авторизацию на базе созданного нами USB-ключа, сделанного из Arduino. Для успешного прохождения задания участникам нужно было самим подделать USB-ключ, реализовав на Arduino довольно примитивный механизм авторизации, заключающийся в перемножении нескольких матриц. На первый взгляд, всё просто, однако задание было не без «подводных камней». О том, как тривиальная задача перемножения матриц на Arduino может вызвать затруднения у крутых специалистов, способных без проблем написать драйвер, хакнуть ботнет, и вообще обойти практически любую технологию защиты, читайте под катом.
Делаем USB-ключ из Arduino
Выбранный нами Arduino – это аппаратная вычислительная платформа, основными компонентами которой являются простая плата ввода/вывода и среда разработки на языке Processing/Wiring. Всё просто – небольшая плата на базе процессора ATmega от Atmel, пины ввода/вывода и USB-интерфейс. Язык программирования чрезвычайно похож на родной и любимый С, а для работы с USB не требуется никаких познаний о протоколе передачи данных – он используется как COM-порт.
Почитав спецификацию на процессор Atmel ATmega328, мы нашли у Arduino маленький недостаток или, применительно к квесту — «изюминку», а именно – совсем скромные размеры оперативной памяти (SRAM) – всего 2 КБ и энергонезависимой памяти (EEPROM) – 1 КБ. Поэтому, чтобы запрограммировать перемножение матриц на Arduino, необходимо помнить про недостаток памяти: на первый взгляд, необходимо хранить четыре матрицы (четвертая – для хранения результата умножения матриц). Для матриц размером 26х26 это будет занимать 26*26*2*4 = 5408 байт. Что, очевидно, больше, чем 2КБ.
Схема протокола для перемножения матриц размером выглядит следующим образом:
При подробном анализе управляющей программы становится заметно, что есть тонкий момент: вместо матрицы №3 повторно передается матрица №2. Это позволяет уменьшить затраты на хранение до 4056 байт.
Так реализована функция считывания матрицы размером 20х20 (далее мы поясним, почему мы решили использовать именно матрицы такого размера):
void read_matrix_a(){ int i = 0; int j = 0; while(j < 20) { while (Serial.available() < 20 * 2) // ожидание, пока во входном буфере не появится 40 байт { // 40 байт -- одна строка матрицы из 20 элементов типа int } for(i = 0; i < 20; i++) { unsigned int tmp1 = Serial.read(); // считывание очередного байта из буфера unsigned int tmp2 = Serial.read(); mat_a[j][i] = tmp1 * 256 + tmp2; // формирование элемента матрицы } j++; }}Поразбиравшись с алгоритмом перемножения матриц, мы обнаружили, что можно хранить результирующую матрицу в одной из перемножающихся, используя дополнительно лишь 26 байт (одна строка) – итого, 2730 байт. Это больше, чем 2КБ, но, как ни странно, меньше, чем 3КБ! Тут сразу же вспоминаем, что есть EEPROM, а это целый килобайт свободного места! Разбиваем одну из матриц на две части – одна будет храниться в SRAM, а вторая в EEPROM. Функция перемножения матриц А и B без использования третьей матрицы выглядит так:
void matrix_multiply(){ int i, j, r; int out_counter; for(i = 0; i < 20; i++) // бежим по всем строкам матрицы A { curr_mul_string = i; // запоминаем номер текущей строки for(j = 0; j < 20; j++) tmp_string[j] = mat_a[curr_mul_string][j]; // сохраняем текущую строку в отдельный массив for(j = 0; j < 20; j++) // бежим по матрице B { unsigned long sum = 0; for(r = 0; r < 20; r++) // цикл перемножения элементов { sum += (get_a(i,r) % 32768) * (get_b(j, r) % 32768); sum %= 32768; } set_a(i, j, sum); // запись результата умножения в матрицу A } }}// функции get_a(x, y), get_b(x, y) возвращают значение элемента (x, y) соответствующей матрицы// функция set_a(x, y, val) устанавливает значения элемента (x, y) матрицы AРазработка задания
Первоначальная идея задания заключалась в сочетании реализации криптоалгоритма на Arduino с reverse engineering, однако потом мы придумали задание на криптографию покруче (и его никто не прошел!). Ещё можно было придумать задание на уменьшение сложности алгоритма, поскольку простой процессор за 10 $ явно не отличается быстродействием… Но задачи такого типа уже приелись, их и так хватает на различных соревнованиях, типа ACM, TopCoder, CodeForces, поэтому на вычислительной сложности мы зацикливаться не стали.
Итак, мы реализовали все компоненты задания для матриц размером 26х26. Схема обмена данными при перемножении матриц на Arduino выглядит следующим образом:
После разработки задания мы стали «тренироваться на кошках» (в роли кошек выступали наши же сотрудники, не посвященные в особенности Arduino). Тут и обнаружились сложности: оказывается, проблемы с памятью совсем не очевидны. Arduino не имеет сигналов, оповещающих об ошибках, связанных с переполнением SRAM, а сама плата в такой ситуации начинает лагать, о чем говорится на официальном сайте Arduino. Более того, даже когда проблема была идентифицирована – мысль об использовании EEPROM так и не пришла никому из «кошек» в голову…
Пришлось упрощать задание и, как оказалось впоследствии, это было верным решением, ведь для одного дня и 2х часов на задание (участники квеста торопились сбежать из тюрьмы, над ними висела угроза казни!) и так есть над чем подумать. Для упрощения решили использовать матрицы меньшей размерности – 20х20. Затраты на память, таким образом, уменьшились до 1600 байт, что не требует использования EEPROM. Именно поэтому в коде везде использованы матрицы размером 20х20. Основная функция-цикл для реализации всего алгоритма, включая вывод ID участника:
// основная функция-циклvoid loop() { int i,j; read_matrix_a(); // считываем матрицу A read_matrix_b(); // считываем матрицу B read_matrix_c(); // считываем матрицу C (заглушка) matrix_multiply(); // перемножаем матрицы A и B с записыванием результата в A matrix_multiply(); // перемножаем матрицы A (с новыми значениями) и B с записыванием результата в A write_matrix_a(); // выводим результат Serial.write(0xB4); // вывод ID участника Serial.write(0x36); Serial.write(0x5F); Serial.write(0x24);}Прохождение задания в очном туре
Итак, платы куплены, протестированы, запечатаны в боксы и переданы участникам. Квест начался! За первые несколько часов соревнования участники лишь косо посматривали на непонятные выданные им коробочки и занимались другими заданиями. Несколько раз порывались подключить свою USB-мышку/клавиатуру к порту компьютера, чтобы открыть желанный скрипт «show_results.sh», хранящий в себе ключи, но подобные попытки были пресечены.
Затем, несколько человек всё-таки принялись выполнять задания так, как от них ожидали:
1. Реверс управляющей программы
2. Выделение протокола обмена между контроллером и управляющей программой
3. Программирование протокола обмена на контроллере
4. Profit!
На третьем этапе, как и планировалось, возникли трудности. Самый распространенный и ожидаемый вопрос звучал так: «я написал корректную программу, залил на контроллер, а она не работает, что такое?». При беглом просмотре выяснялось, что ребята делали все правильно: выделяли матрицы, каждая по килобайту, для приема-передачи данных тоже были отдельные буферы (ну никакой заботы о памяти!). Всё переполняется, ничего не работает.
Понимая, что время не резиновое, а задание проходить надо, мы намекали участникам: «эта плата не такая сильная, как вы думаете», «посмотрите спецификацию». Участники недоуменно кивали головами и шли искать требуемую информацию. Через несколько минут их лица озарялись пониманием и готовностью решать найденную проблему. И вот, спустя полчаса, первый участник (AVictor) подсоединил свой запрограммированный контроллер и получил свой долгожданный ключ от задания!
Примерно за час до конца контеста это задание покорилось второму участнику (bumshmyak). Остальные соревнующиеся не успели довести решение до логического завершения. Большинство из них уже вышли на финишную прямую, когда проблема устранена и необходима лишь реализация, но время летело неумолимо.
В заключение
На NeoQUEST-2014 ожидайте новых интересных заданий, в том числе и таких «железных», как это! Регистрация на онлайн-тур NeoQUEST-2014 стартует в январе, а очный тур состоится в период белых ночей в Петербурге! За всеми обновлениями можно следить на нашем сайте.
