Making a USB key from Arduino to bypass password-free authorization.

Bypassing password-free authorization has long excited the minds of computer enthusiasts. When thinking about biometrics, a chill runs down your back: what if they cut off a finger or pull out an eye? And the most humane and no one surprising way is, of course, USB keys.

On the NeoQUEST-2013 full-time tour, we suggested that participants hack authorization based on the USB key made from Arduino created by us. To successfully complete the task, the participants needed to fake the USB dongle themselves, having implemented a rather primitive authorization mechanism on the Arduino, consisting in multiplying several matrices. At first glance, everything is simple, but the task was not without “pitfalls”. How the trivial task of multiplying matrices on Arduino can cause difficulties for tough specialists who can write a driver without problems, hack a botnet, and generally bypass almost any protection technology, read under the cat.

Making a USB key from Arduino

The Arduino we have chosen is a hardware computing platform, the main components of which are a simple I / O board and the development environment in the language Processing / Wiring. It's simple - a small ATmega-based motherboard from Atmel, I / O pins and a USB interface. The programming language is extremely similar to the native and favorite C, and for working with USB no knowledge of the data transfer protocol is required - it is used as a COM port.
')


After reading the specification for the Atmel ATmega328 processor, we found a small flaw in the Arduino, or, with regard to the quest, a zest, namely, the very modest size of RAM (SRAM) - only 2 KB and non-volatile memory (EEPROM) - 1 KB. Therefore, in order to program the multiplication of matrices on the Arduino, it is necessary to remember about the lack of memory: at first glance, it is necessary to store four matrices (the fourth is to store the result of matrix multiplication). For matrices of size 26x26 this will occupy 26 * 26 * 2 * 4 = 5408 bytes. Which is obviously more than 2KB.

The protocol scheme for matrix multiplication is as follows:



In a detailed analysis of the control program, it becomes noticeable that there is a subtle point: instead of matrix No. 3, matrix No. 2 is retransmitted. This reduces storage costs to 4056 bytes.
This is how the function of reading a 20x20 matrix is ​​implemented (hereinafter, we will explain why we decided to use matrices of this size):

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++;
}
}

Having mastered the matrix multiplication algorithm, we discovered that it is possible to store the resulting matrix in one of the multiplying ones, using an additional 26 bytes (one row) - a total of 2,730 bytes. This is more than 2KB, but, oddly enough, less than 3KB! Here we immediately recall that there is an EEPROM, and this is a whole kilobyte of free space! We divide one of the matrices into two parts - one will be stored in SRAM, and the other in EEPROM. The multiplication function of the matrices A and B without using the third matrix is ​​as follows:

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

Job development

The initial idea of ​​the task was to combine the implementation of a cryptoalgorithm on Arduino with reverse engineering, but then we came up with a better task for cryptography (and no one passed!). You could also come up with a task to reduce the complexity of the algorithm, since a simple processor for $ 10 is clearly not very fast ... But tasks of this type have already become boring, and they are enough for various competitions, such as ACM, TopCoder, CodeForces, so we do not dwell on computational complexity become.

So, we have implemented all the components of the task for matrices of size 26x26. The data exchange scheme for matrix multiplication by Arduino is as follows:



After the development of the assignment, we began to "train on cats" (as our cats were our employees, who were not dedicated to Arduino in particular). Here the difficulties were revealed: it turns out that memory problems are not at all obvious. Arduino does not have signals, notifying about errors related to the SRAM overflow, and the board itself in this situation begins to lag, as stated on the official website of the Arduino . Moreover, even when the problem was identified - the thought of using the EEPROM never occurred to any of the "cats" ...

I had to simplify the task and, as it turned out later, it was the right decision, because for one day and 2 hours on the task (the quest participants were in a hurry to escape from prison, they were threatened with execution!) And so there is something to think about. For simplicity, they decided to use a matrix of a smaller dimension - 20x20. The memory cost has thus decreased to 1600 bytes, which does not require the use of an EEPROM. That is why in the code everywhere used matrix size 20x20. The main loop function for implementing the entire algorithm, including displaying the participant 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);
}

Passing the job in full-time tour

So, the boards are purchased, tested, sealed in boxes and transferred to the participants. The quest has begun! For the first few hours of the competition, participants only looked askance at the incomprehensible boxes given to them and were engaged in other tasks. Several times I tried to connect my USB mouse / keyboard to the computer port to open the desired script “show_results.sh”, which stores the keys, but such attempts were stopped.



Then, a few people still began to perform tasks as expected from them:
1. Reverse control program
2. Isolation of the exchange protocol between the controller and the control program
3. Programming the exchange protocol on the controller
4. Profit!

At the third stage, as planned, difficulties arose. The most common and expected question was: “I wrote the correct program, uploaded it to the controller, but it doesn’t work, what is it?”. At a cursory review, it turned out that the guys did everything right: they allocated matrices, each by kilobyte, for receiving and transmitting data, there were also separate buffers (well, no memory care!). Everything overflows, nothing works.

Realizing that the time is not rubber, but the task is to pass, we hinted to the participants: “this board is not as strong as you think”, “look at the specification”. Participants puzzled nodded their heads and went to look for the required information . A few minutes later, their faces lit up with understanding and willingness to solve the problem found. And now, after half an hour, the first participant (AVictor) connected his programmed controller and received his long-awaited task key!

Approximately an hour before the end of the contest, this task submitted to the second participant (bumshmyak). The remaining competitors did not have time to bring the decision to its logical conclusion. Most of them have already reached the finish line, when the problem is resolved and only implementation is necessary, but time flew inexorably.

Finally

At NeoQUEST-2014 expect new interesting tasks, including such “iron” ones like this! Registration for the online tour NeoQUEST-2014 starts in January, and the in-person tour will take place during the period of white nights in St. Petersburg! All updates can be monitored on our website .