Moderator's introduction
Well, I think password cracking has become more or less clear to us all. But now let's narrow down the topic we're talking about a little. Because overall we'll talk about mobile forensics, which is what we started with. Let's narrow the topic. There are always lots of theories that our phone is basically a safe that stores information. And the best safe there could possibly be. But let's remember, a safe generally doesn't run out of charge on its own. And sometimes the battery drains much faster than you could ever crack the password on that phone. How to speed all this up and how to do it all faster, our next speaker, Vyacheslav Chikin from ACE Lab, will tell us. Let's welcome him with a round of applause.
[applause]
Vyacheslav, by and large, all our hopes rest on you. Here you go, your microphone, the clicker.
Talk and Q&A
Good afternoon, thanks, Dmitry. Let's continue the topic of passwords.
The way things are going, device power is growing, capabilities are growing. Whereas before, 70%, or maybe even more, of cases were pattern locks. At most, a short PIN. Now, with the advent of face recognition, fingerprints, and maybe they'll come up with something else, it sometimes happens that even the phone's users themselves forget their password. And often they come up with a lot. Very long, complex passwords, a standard situation.
The person hasn't typed the password, and then the phone asks them to enter it.
This is especially common among teenagers. Recently my son came to me and said: Dad, I forgot my password. Can you crack it? An eight-character password, I think, no big deal, let's give it a try.
I hooked up our system, the phone is supported by our system. In the end I struggled a whole day and still haven't cracked it. I had to dig deeper into this topic.
So, first let's figure out what we can use as password characters. We have digits, the simplest case. Lowercase English letters, uppercase English letters, and special characters. 33 of those, as already mentioned. In total, that's 95 possible characters. But that's not all.
On some phones you can enter various special symbols in a password. You can enter a period, accented letters, little hearts and all the rest. Let's just say, Gen Z are actively using this now. And accordingly, this has to be considered.
But it's not all that complicated and sad here. Because if we take that same period and use it as one of the characters, then during brute-forcing it gets replaced with quotes like these. The heart symbol will be replaced with the letter "E". You can enter either the heart or the letter "E". Keep that in mind. But at the same time, this changes how you build masks for password brute-forcing.
For example, someone might set their password to "Ivan loves Dasha".
On mobile devices, the most common algorithms in use are SHA-256 and scrypt. As for SHA-256, everything's clear there — there are also, let's say, ASICs that you can get to crack passwords, to speed things up. As for scrypt, we'll talk about that a bit more in detail today, because it's the main algorithm used in mobile phones.
So, what is, let's say, the main difficulty, or even, let's say, the nasty thing about scrypt — it's that this algorithm is very hard to speed up and parallelize, because it works with memory. That is, initially some block of data and some salt, generated completely at random, goes into — let's call it that for now — a mutation block, and from it a big, big block of data is assembled; then from that block of data, at random, per the algorithm, blocks are picked, from them a hash is computed a certain way, and in the end we get our scrypt hash, which we brute-force the password against.
So here we immediately see two problems. The first is that we use memory heavily. For example, a graphics card may have loads and loads — thousands of compute cores, but we'll hit the fact that we eat up all the graphics card's memory, and those cores will be jostling, fighting over memory, and we won't get any speedup, any efficiency at all. The second bottleneck of this algorithm is, again, memory. It's that all this data, these random memory requests, start piling up in the memory controller. And we may have a super-powerful modern CPU in there, but all that data just hangs at the bottleneck, the memory controller.
So, let's talk a bit about the scrypt parameters. The first parameter is N, the so-called cost factor. It's the main scrypt parameter. It's all written here, I won't go over it. You can take a photo of all this. The slides will be available afterwards, you'll be able to look through it all. For now, we need to understand that this parameter — a great deal depends on it. That is, the higher this number, the more memory you need, the harder it is for the CPU to brute-force.
It's already noted here as a peculiarity that doubling the value of N doesn't just double the running time, it increases it roughly fourfold. Then r is the block size; that, actually, can be varied if we want more memory or less; in practice it's usually 8.
p — we'll skip that for now; it's for when you need to parallelize and somehow account for parallelizing the algorithm.
So, here are some quick calculations, to make it clear. Now let me explain. This is the formula, all boring, I'll put it a bit differently. So, there's this whole thing now called ASICs. And we too, when we first got into this, thought: wow, that'd be great — forget graphics cards, CPUs, here are ASICs, cryptocurrencies, it's all the rage now, let's hook one up, hack an ASIC somehow, bolt it on, make it work for us. But it's not that simple.
ASICs run — well, take a coin like Dogecoin, it and the others, basically, they all run the same scrypt algorithm with parameters 1024, 1, 1.
But that takes only 130 kilobytes of memory. So everything mines just fine, coins get minted, but for our tasks, unfortunately, that doesn't work.
Our task is a bit more interesting. Our parameters are 2048, 8, 1.
That's for Android with file-based encryption. That's on modern phones, and here a single CPU core or a single GPU core will already be consuming 2 megabytes of memory. Plus, those 2 megabytes, with random access, will start clogging the memory controller. So all of this has to be taken into account. For full-disk encryption — that's for older phones — we already need 32 megabytes of memory per core. If you've used our system, you've seen that on older phones the password takes much longer to crack. That's the reason.
Our system, too, is gradually starting to support parallelization. We ran it on some small setups, made builds, tried cracking passwords.
And we got different results for Windows and for Linux. Possibly because memory is organized differently. We'll have to look at how to optimize that. But on Linux we got much higher numbers — double — on the CPU. As for graphics cards, the results there are the same. If you look at the bottom row — that is, we've got, we tested a Ryzen 9 9950X, and a Core Ultra. Basically, despite their different number of cores, the results came out the same. We're still going to look into this, but most likely, our assumption is that we've simply hit the memory controller wall. It's got DDR5 in there. We'll keep experimenting going forward. For now, these are the results.
The graphics card, for those interested — a 4060 Ti showed only 1,500 passwords. So the logical question here is: what's better to use, graphics cards or CPUs? Well, let's say, whatever you've got. You can basically brute-force on anything. Down the line we'll have the option — say, if there are 10 computers in the office, all of them can be put to work on a single job.
So, back to it. Based on what we've learned today, let's try to picture what we can expect. Say, even if we build a more or less decent machine, it'll do 20 thousand passwords per second. That'd be either two good CPUs or a whole stack of graphics cards. To exhaust an eight-character password, we'd need a full 10 thousand years. Some people count in exponents; we prefer to count in years. Or in millennia, for now.
If there are any questions, I'm ready to answer them. —
— Thank you very much. Right, colleagues — ah, I see a microphone right away. Oh, a hand, I mean. Mic's with me. —
— Good afternoon, thanks for the talk. I have a question about memory — do you mean the CPU cache or RAM? Which memory is being used? —
— We're still going to be researching that, because, to make it… Right now I'm talking only about the CPU, not the GPU. To make it work with the cache, there are some options there too, certain tasks. That is, you need to write specific code in assembly.
We haven't gone down that deep yet. We use standard functions. How they get spread out there, we don't check yet. But yes, the option of using the cache — such options do exist. But then again, the cache isn't that big. So even if it's 2 megabytes, and with 24 cores on modern CPUs, there's a good chance it gets eaten up very fast. Yes, some threads could be sent there; possibly that's what's happening already. Well, let's say, that's a separate research topic, of course. Yes, good question.
Well, it's not really a question, more of a wish. You're known, you've always been known for your ability to work directly with memory, devices, processors. But something like a master password, or the like — haven't you tried digging in that direction? Like in Windows: take the password, change it — do that on a phone. Haven't tried? And aren't going to? I didn't quite follow. Well, look, we change the password. I've got a user, I change the password to my own and then operate with my own password. Have you tried it that way — you can't? So not guessing the password, not brute-forcing, but setting your own. Setting my own password? Yes, but keeping his data. —
— Well, setting your own password is hard. No, but it's not 10,500 years, is it? Maybe it'd even be easier? Ah, well, I was just looking at it from the hardware point of view, and the colleague before me explained how to cut that time down. But for that, again, dictionaries exist, and beyond that it's a creative process. —
— Bypassing it? Well, bypassing is hard — it's math. The math here — take SHA-256, it's a very simple algorithm too. But so far nobody's learned to find collisions for it. There are miners, whole farms, whole cities built to hunt for collisions.
Right, colleagues, more questions? If I see no more hands, let's send Vyacheslav off with applause. Vyacheslav, thanks a lot. You can leave it all over there at the booth. And we've all done great, because we've now reached the end of the first block of the first day of our event. And now we'll have a fairly long break, because, again, as I've already said, the most important thing is networking. You'll have a full 45 minutes to talk. The catering out there's basically laid out. And at 12:05 we'll meet back here in this hall. Thank you.
[A break (12:00–12:30 in the program) is cut from the recording; timecodes run without a gap.]