Defeat 2FA token because of bad randomness - rhme2 Twistword (Misc 400)

I assume you know what two-factor authentication is. And there are hardware

token

s, for example yubikeys or even the Google authenticator on your phone, that can generate some code that you have to enter as additional proof when you want to gain access to something. In this video we will analyze a bad two-factor implementation and learn something about

randomness

. This example is a special challenge of the ctf embedded hardware riscure. It actually has 400 points. That's an incredible amount of points considering the other challenges I struggled with. But I still solved it. As? I solved the challenge in an unwanted way, which happens to teach you something about

randomness

.

So let's get into it. Twistword. A company is developing a new hardware 2fa

token

for its employees as existing solutions are too expensive. The development team received many complaints about the first version being slow and sometimes not even working. This is most likely due to resource limitations of the board used. He managed to get one of the first boards with a new version of the system that was given to some users to test whether it was an improvement or not. However, is it also safe? Let's take a look at what this looks like on the dashboard.

When you connect, it says: Twisted Inc. Scure Token auth 2.0 Debug build. Again a message that they changed the algorithm. Presumably it now made him smaller and perhaps more unsafe. And then they ask you for your 2-factor authentication token. Now would be the time you take your actual hardware token, generate the key and hand it over. If it matches what the board calculated, enter. But when you enter a wrong one, it will tell you which token was expected. That would be very useful. So what can we do. Well, one of the first things that comes to mind is the Mersenne tornado.

For the title Twistword. Mersenne Twister is a pseudorandom number generator (PRNG). This means you give it some kind of seed and then it will shuffle, flip and rotate the bits, if you so desire, to create new random states. Pseudorandom

because

it is not truly random, the same seed will produce the same values, but it is random enough for many applications. And actually, with 2-factor tokens you want pseudo-random generators,

because

the token generator and the service you want to access have to generate the same value so they can be compared, right? Additionally, when you scroll down a little further you can read the following: The algorithm in its native form is not cryptographically secure.

The reason is that observing a sufficient number of iterations (624 in the case of MT19937, since this is the size of the state vector from which future iterations are produced) allows predicting all future iterations. So this mersenne tornado can be implemented with different values ​​and parameters and MT19937 defines one such implementation. I assumed that for this challenge they used their own parameters and we have to investigate how this attack works, how the state can be recovered with enough samples. Another thought I had was that randomness is really hard to achieve in computers. They are deterministic machines that simply execute instructions, there is nothing random about them.

So what you can do is try to collect entropy from different sources. On PCs you often see them tell you to move the mouse a lot, because that movement is difficult to predict. But what to do with an arduino? I figured one of the most likely ways would be to read an analog value from some of the pins. Its reading of a digital state would be 0 or 1, but the arduino can also read analog values ​​from some pins, well it uses an ADC, an analog to digital converter to convert the voltage on a pin to a digital number.

And if the pins aren't connected, you could pick up interference from background radio noise or something, and that's pretty random. So maybe you just have to connect all the pins to ground, so make them 0. This way the initial random seed will always or often be the same. I thought it was a cool attack, but I felt that for 400 points, it would actually be harder than that. So I assumed it was about figuring out the math. To do this, I first wanted to start by capturing a lot of tokens that I can then work with. The board is very kind in responding with the expected token.

So I wrote two scripts. One would connect via serial and then just enter a wrong string and collect all the expected tokens and the second script I wrote would always reset the serial connection which resets the board and should initialize the PRNG again. I thought maybe I could learn something interesting about initial states. And this data collection takes a while. Especially the method of resetting the serial number is very slow. So I let the data collection happen overnight. The next morning I did a quick first check of the data. I wasn't expecting much because I was sure the real work was just beginning.

Having to investigate how to recover the initial state and data simply helps with testing. So I was casually looking at it if I noticed anything. And what the hell! One of the files contained a duplicate value. This cannot be the case. These numbers are so large that they are very unlikely to be repeated. In fact there were a couple of duplicates. Something smells bad. If it is to calculate the state of the PRNG and predict the next value, this would not happen. So… I took the easy route. I modified my script to now send this duplicate value all the time.

Also, a PRNG, as I said before, starts with a seed and then all subsequent values ​​are predictable, if you know the implementation and parameters. This means that when we got a duplicate value, the next expected token should have also been the same. So if you had saved the first two expected tokens after restarting the board, and found the same first token a second time, you could have used the previous second expected token and won. So let's write a script for that and let it run overnight and I'm sure I'll get another duplicate. This is the script I wrote.

These functions, you already know them, only help me interact with the board, to read what text it sends me. The most important variable here is the list of tokens that I found before. And at first it is empty. I'll also write each pair of tokens I see to a file, so that when I interrupt the script I can simply reload the previous tokens I collected so I don't lose any data. And that's what I do here. So I reran this a couple of times. Just add the pairs I found before to the token list. Anyway. Then in an endless loop I create a new connection to the board.

Then I wait until I receive the text I have to press Enter. Then I read until it wants me to enter a Token and send one of the duplicates I got earlier. Maybe I'll get lucky, but most of the time I won't, so I read the token I expected. Now I extract that token and check my token list, if I found that token before. If I did, I know what the next tab will be. If it's new, I'll just enter an empty token and get the next expected token, which I also extract and save along with the first token in the token list.

And down here I have some nice and elegant debugging results. So in theory this should work. It will just take a while. In my case I think it worked for about 3 hours and then found a duplicate. So my script sent the token it would expect next and, surprise, it's the correct token and we get the flag. That was much easier than I thought. It was not the intended solution either. But it really highlights how difficult it is to properly initialize the PRNG with a truly random seed on this little arduino. I don't know how they tried to get such a good random seed value, but it clearly didn't work.

Randomness is not trivial for computers. Learned lessons. By the way, there was another small annoyance with this challenge. So when I found my first duplicate, it didn't work. I saw that I predicted the correct value, because the second expected token was the same, but it didn't work. And it was a problem with line endings. Let me explain to you what happened. Basically it comes down to not being really user friendly and flexible with respect to input. But basically I expected 32 bytes of input followed by some kind of terminator. Like when you press enter. Typically, it could be a newline, a carriage return, or even a newline or carriage return.

So in this case I was just expecting a carriage return. There are basically two stages when it comes to communicating. The buffer and data that are actually handled. So at first I sent a carriage return and a newline. So the buffer was filled with this data and then the application read 32 bytes for the token and carriage return. And that meant it was done. Now he asked for the second token. Now the new line was still in this buffer, the application never read it. So now I provided the second token, which was written to the buffer, and when the application read 32 bytes, the first byte was a new line.

So obviously the expected token and the one I sent were not correct. This was really frustrating. But I got a hint about that problem and then I was able to solve it in the end.