Donnerstag, 5. Januar 2017

How to downgrade without jailbreak using prometheus

Hello everybody,
since the release of prometheus there has been a lot of confusion about what it can do and what it can't do. A lot of people asked me whether they should upgrade their 9.3.x device to iOS 10.2 to be able to downgrade to iOS 10.1.1. Every time i read this i was like NO DON'T DO THIS! But i can't stop everyone trying. I understand that this stuff is kinda complex, but i didn't think it would be *that hard* to understand. So far i've seen like 1 or 2 persons who kinda understood what they need to do, but even they fucked up in the end.
Let's clearify what prometheus can do and what it can't do.

Q: Can i downgrade without jailbreak?
A: No!

Q: But i saved shsh2 with tsschecker, why can't i downgrade without jailbreak?
A: Just saving shsh2 files is not enough! You need to do more. If you're asking this you surely didn't prepare properly and now it's too late.

Q: But i have iPhone5s/iPad Air and shsh2!
A: That's not a question. Also if you didn't prepare properly you still can't downgrade, even with shsh2!

Long version:
Doing crypto is hard. Doing crypto correctly is even harder!
Apple did a really great job with it's secure bootchain, the design is in theory really secure.
Of course there can always be bugs in the code, which might be exploitable, but that's not what we're gonna talk about in this blogpost. In my talk at 33c3 i described how the bootchain works, so if you haven't seen that i recommend doing so.
Apple uses crypto right in the first step of booting, they hash bootfiles and verify signatures. This makes it impossible to tamper with the data (assuming they did it right). But even when they did everything right, planned every step carefully, hashed every byte of data and verified every file's signature things still can go wrong. Like i said in the beginning, crypto is hard. Many things in cryptography depend on random numbers. When you design some cryptographic protocol you want to have a TRNG (True-Random-Number-Generator). Since those are really hard to make in practise the second best thing you want is a really really good PRNG (Pseudo-Random-Number-Generator).
I've seen many times people fucking this up, so i though "well, let's see if apple did it right".
Even if i didn't expect this to work at all (since 64bit device with SEP have a TRNG !?!??!) i still tried this, because well there's still the chance that apple fucked things up. For some reason iBoot doesn't use the TRNG from SEP but instead falls back to a PRNG (at least that's what i assume, i haven't really verified this). Since iBoot is the third thing to boot (Bootrom->iLLB->iBoot) there isn't really much happening in the device at this point and the entropy is very low. This makes it really hard to make a good PRNG.

So, why do we even need random numbers?
You've all probably heard about this "nonce" i keep talking. What exactly is a "nonce"?
Per definition a nonce is a "Number used ONCE". Often you just want a random number, you use it once and then you throw it away and never use it again.

Ok i see what a nonce is, but why do we need that?
Back in the iOS 4 day we didn't have nonces. We still had hashes and signatures, but no nonces.
This allowed us to do a pretty simple attack against the system, called "replay attack".
Back then you'd save an shsh blob (which was just a signed hash) with TinyUmbreall or something like that and when you'd try to restore you'd simple send the shsh blob you saved to iTunes which would give it to the device. Hash is fine, signature is fine let's restore!
So every time you restore a device you would give it the exact same sequence of bytes. Even if you in theory should ask the tss server on every restore, since the bytes never changed you can save and replay. You can't generate this sequence of bytes yourself, but you can just ask the tss server and save them. This would ultimately be the key to restoring iOS 4 devices. So when apple stops giving out the "keys" (Note: this is just a metaphor, you don't really get keys) you don't care, because you already have them.
Things changed with iOS 5 where apple introduces APTickets which have nonces.
So what does it mean?
When the device boots up it generates a nonce which is a random sequence of bytes.
What iTunes needs to do is to ask the device for the nonce it just generated. When iTunes requests an APTicket is send this nonce to the tss server too. The tss server generates an APTicket with the nonce it got and sends it back to iTunes. So now that ticket contains a bunch of hashes and this specific nonce. The device now verifies the APTicket and reads out the nonce inside. Then it compares the nonce in the APTicket with the one it just generated and if they match it boots the file. If they don't match however the file is rejected and the device doesn't boot up.
(Nonces are not checked on normal boot, but that's not the route we want to go)
The problem here is that even when you save the APTicket, the device would generate a completely different nonce on the next boot which makes that particular APTicket useless.
Since we can't do anthing to correct the nonce inside the APTicket we saved there is only one thing we can try: make the device generate the same nonce again!
Because if the device somehow generates the same nonce, we can again use the APTicket we saved and we win!

Remember i said crypto is hard? Well apple fucked up with random numbers in iPhone5s and iPad Air. Right now these are the only device i know to be vulnerable, but maybe they fuck up something else in future ;)

How exactly did they fuck up?
When generating random numbers it is possible that once in a while a number repeats. This is totally fine, since numbers are random and ideally every number has an equal chance of being generated.
Since nonces are 20bytes long, every nonce has the probability of 2^(-160) being generated.
If we assume that the device first randomly chooses a generator, which is 8byte in size, and then derives a nonce from that by hashing it with SHA1, you still have 2^64 different nonces, which are generated with the probability 2^(-64) each.
This is fine.
The issue here is that in reality for some reason nonces aren't generated with this probability.
I noticed that there are five nonces which together are generated with the probability of 1/5 which is 20% which means that on average every 5th nonce is one of those five nonces.
This is really bad!

To the attack!
Now if we save an APTicket for each of those 5 nonces we need an average of 5 reboots to make the device generate a nonce which is in one of our saved APTickets.
This is cool!

Now this was enough theory, let's get to the practical part!
First of all we need to figure out what nonces are generated the most. This theoretically can change in every iOS update so we need to do this for every new iOS version released!
It definetly changed from iOS 9 to iOS 10, so keep that in mind.

What we need to do is get noncestatistics and let it collect nonces for a few hours.
I'd say with about 500/1000 nonces you're good to go. Basically you just need to find those which are generated most likely.

By running "noncestatistics nonces.txt" it will collect nonces and save them to nonces.txt.
We let this run until we get like 500/1000 nonces and then we stop it with CTRL-C

This will stop collection, kick our device out of recovery mode and boot it back to normal.

Now having all the nonces we need to sort and count them, so let's run "noncestatistics -s nonces.txt".

So i let this run while taking a shit and collected about 400 nonces. Here we can see the ones generated the most. The ones which were generated like 2 or 3 or 4 times we can ignore, since this can always happen when dealing with random numbers, but those with a likelyhood of 12% and 8% are the interesting ones. In this example i figured that my iPhone5s on 10.1.1 generated these nonces quite a few times:

Note: you definetly need to make your own tests, as your device might generate different ones!

Now we save an APTicket for that particular nonce. (be sure to put your real ECID in there)

Repeat this step for all of the nonces up there. Also don't forget to change the filename or move the files into different directories so you don't overwrite them.

If you want to check what nonce is inside your APTicket you can use img4tool:

BNCH is the nonce inside the APTicket.

If you then decide to restore with futurerestore, you can specify all of your saved APTickes to increase the likelyhood of finding a match.
You'd run something like "futurerestore -w -t 1.shsh -t 2.shsh -t 3.shsh -t 4.shsh -t 5.shsh" and of course all the other parameters to futurerestore.
This will reboot your device until it generates a nonce which is in one of your APTickets.

I hope this clears the confusion about why your device never generates the correct nonce and what you need to do to be able to use the collision method in future.
If you still have questions or i forgot to mention something important, feel free to ask me on twitter or send me an email.
Keep in mind that i will ignore stuff like: "tsschecker crashes on windows when i doubleclick it".

Good luck saving APTickets for your colliding nonces