Sonntag, 19. Januar 2020

Writeup: Out of the sbox - Insomnihack teaser 2020

After playing Insomnihack teaser 2020 CTF yesterday, here is my writeup on how i solved the
"Out of the sbox" crypto challenge.

Spoiler: No Sboxes were harmed during this challenge.

tldr:
Instead of attacking SBoxes (as probaly intended by the author), i reduced the keyspace from 6 Bytes to 4 Bytes and created a distinguisher with only 12 SBox lookups and a few XORs (instead of 28 Sbox lookups for the full cipher). Then bruteforced 4 Bytes.



Now let's explain how this works.


Challenge overview:

When unpacking the zip one will find 3 files:
  • main.py
  • des.py
  • params.py

main.py:

def welcome():
    # Welcome client
    print(WELCOME, flush=True)
    sleep(randint(0, 3))

def challenge():
    # Generate challenge
    key = int.from_bytes(urandom(6), 'big')
    keys = key_schedule(key)
    data = []
    for i in range(50000):
        plaintext = int.from_bytes(urandom(8), 'big')
        ciphertext = enc(plaintext, keys, sboxs, perms)
        data.append((plaintext, ciphertext))

    # Validate data
    inv_keys = reorder_keys(keys)
    inv_perms = reorder_perms(perms)
    inv_sboxs = reorder_sboxs(sboxs)
    for p, c in data:
        assert(p == enc(c, inv_keys, inv_sboxs, inv_perms))

    # Print challenge
    print(str(data) + '\n', flush=True)

    return key

def reward(start, key):

    # Wait for response
    print(TASK, flush=True)
    response = input()

    # Verify response
    if time() - start < 1337 and \
       len(response.strip()) == 12 and \
       search(r'([0-9A-F]{12})', response) and \
       int(response, 16) == key:

        reward = ''.join(open('/home/ctf/flag.txt', 'r').readlines())
        print(reward, flush=True)
    else:
        print(WRONG, flush=True)

if __name__ == '__main__':
    if pow():
        start = time()
        welcome()
        key = challenge()
        reward(start, key)


So after solving the proof_of_work, the start time is saved, a welcome screen is displayed, then a random key is generated.
Next 50000 random plaintexts are generated, encrypted and sent to us together with their ciphertext.
Now we have 1337 seconds (~20min) time to send back the encryption key.


Next up: des.py

Even though the name suggests the DataEncryptionStandard algorithm, DES isn't the encryption used here.



N = 256
ROUNDS = 7

def key_schedule(key):
    keys = []
    for i in range(ROUNDS):
        left = (key >> (16*((i+1) % 3))) & 0x0000FFFF;
        right = (key >> (16*(i%3))) & 0x0000FFFF;

        keys.append((left << 16) | right);

    return keys

def apply_perm32(perm, x):
    out = 0
    for i in range(32):
        out |= ((x & (0x00000001 << i)) >> i) << (perm[i])

    return out

def fbox(x, key, sboxs, perm):
    tmp = x ^ key

    tmp = int(sboxs[0, 0x000000FF & tmp]) | int(sboxs[1, (0x0000FF00 & tmp) >> 8]) << 8 | int(sboxs[2, (0x00FF0000 & tmp) >> 16]) << 16 | int(sboxs[3, (0xFF000000 & tmp) >> 24]) << 24
    out = apply_perm32(perm, tmp);

    return out;

def enc(plaintext, keys, sboxs, perms):
    A = plaintext & 0xFFFFFFFF
    B = plaintext >> 32

    for i in range(ROUNDS):
        y = fbox(A, keys[i], sboxs[i], perms[i])
        tmp = B ^ y
        B = A
        A = tmp

    return A << 32 | B

From a quick glance at enc() we can see that the encryption is a 7 round Feistel Cipher.

The function fbox is really simple:




 Basically it's just:
  • Key Addition
  • Sbox
  • Bytewise rotate left
One note here: There are 7 rounds with 4 SBox lookups per round, but every time a different SBox is used. There are 28 SBoxs in total every of them is used exacltly once during the encryption.


For the sake of completion let's quickly mention params.py:
Here all the 28 SBoxes are stored as well as an overcomplicated notation of the permutation in every round.


First attempts:

At this point it should be clear that the author wants us to do cryptanalysis attacks on the SBoxes.
The first things that come to my mind are differential and linear attacks.
And i indeed computed a DifferenceDistributionTable (DDT) for every SBox.
Every SBox, except for the last for SBoxes, had DDT entries of at lest 10 (some of them even 14).
This means that a certain input differences yields a certain output difference with a propability of 10/256.
With 50000 plain/cipher pairs it is probably now possible to construct a probabilistic attack by constructing a trail and a verifier and doing fancy crypto stuff.

You may have noticed that i say "probably". That is because at this point i realized that i was asleep most of the time during the lecture where i should have leared this and, except for a few buzzwords, i didn't remember much and have no clue how to actually do "fancy crypto stuff" to break the cipher and get the key.

So sorry to disappoint you if you expected fany crypto SBox attacks, but this is not the writeup you are looking for.


Key schedule:

Let's take another look at the cipher.
One of the first things that got my attention was the key_schedule() function.
You input a 6byte key and get 7 4byte round keys.
However taking a closer look, you really only get 3 unique round keys, which then repeat.

Setting the masterkey to 0x554433221100 you get the following roundkeys:
  • 0x33221100
  • 0x55443322
  • 0x11005544
  •  
  • 0x33221100
  • 0x55443322
  • 0x11005544
  •  
  • 0x33221100
Even worse that the keys repeating, is that always two bytes are used together in subsequent keys.
So one should really look at the round keys 2-byte-wise:
  • 3322 - 1100
  • 5544 - 3322
  • 1100 - 5544
  •  
  • 3322 - 1100
  • 5544 - 3322
  • 1100 - 5544
  •  
  • 3322 - 1100

The solution:

Since i'm an engineer and not a math person, my final solution was (a very optimized) bruteforce.

The general idea is that with only 4 key bytes it is possible to run the encryption and decryption such that in the middle round you know some certain state.
By combining the partial state you get through encryption with the partial state you get through decryption, it is possible to compute yet another byte of state, which is otherwise unubtainable using encryption or decryption alone.
With the help of this extra byte (further called "blue"), it is possible to make an equation for yet another keybyte (further called "k4"). This creates a linear dependency of four keybtes to a fifth keybyte.
By recovering k4 is is then possible to again compute more state bytes (further called "yellow").
Now at this point we have one certain byte computed through partial decryption alone as well as a combination of partial decryption and partial encryption (yellow).

So here we can compare the byte we got through partial decryption to yellow and we got a distinguisher!

For the correct keybytes yellow is always equal to the byte got from decryption alone, however if they are not equal, we know that the 4 byte keyguess was incorrect.

So after having verified with our distinguisher that our 4 byte keyguess is a good candidate (note there are a lot of false positives here, thus only "candidate"), we can use blue once again to create and solve an equation for yet another keybyte ("k3").

Finally this allows us to use partial encryption and partial decryption to create a linear dependency between the keybytes, allowing us to bruteforce 4 bytes and compute the matching other 2 keybytes.

Here is a simple graphic to illustrate the attack:




It is best if you open the graphic in another window (or sth) and look at it whilre reading along, as i will explain now what can be seen.

First ignore every color and just look at the general overview drawn with black.
This is the full unrolled feistel cipher.
You can see that every round consists of 2 parts (A and B).
Part B' is just A copied over to B in the next round.
Part A' is computed as A'=F(A) xor B.

Now lets bring in some color. Note the green "filled boxes".
This is what we get "for free" without having to do any computation, since we know the plaintext and the ciphertext.

Now we bring in some state.
Check the brown numbers below the input. We define the state as [7][6][5][4][3][2][1][0].
And also split the state into 8 bytes in every round (where neccessary).

Next up we add the key to every round.
They are written in red at the right side of the F function inbetween the states of each round.
These are the keybytes of the masterkey we need in this round.
Notice, some of them have a green line below them.
These are the bytes we are going to guess initially.
Namely these are K0 K1 K2 and K5.

Now wer can do partial state transitions.
These are the red dots in the round.
If the red dot "floats on the top" of the square indicating a byte in the state, we aquired this byte by encrypting the plaintext.
If the red dot is at the bottom of the square, we got the byte by decrypting the ciphertext.

Since the F function is very simple you can basically just follow along by looking at the sate.
Before i show you an example of how to place the red dots, lets first define how we address the sate.
If i say enc_state_1_0, then i mean the line in the picture prefixed by "1" and the byte index "0" counting from right to left. In case of enc_state_1_0, this is the rightmost byte in the state prefixed with "1" in the picture. To index the leftmost byte in the same line, i say enc_state_1_7.
The "enc" part in this notation is not relevant for the blogpost here, but if you decide to read the final code it will tell you where we got to the state by encrypting (going from top to bottom) or by decrypting (going from bottom to top).

Now an example of how to place the dots.
Lets take a look at the red dot at enc_state_0_1 which is the second byte from the right in the line prefixed with "0".
To set a byte in A we need to know when going from encrption:
  • The byte in the round before, rotated to the right by 1 (here enc_state_plaintext_0)
  • The keybyte below the byte we need in the previous bullet point (here K0)
    • Note: we can see that we know K0 because it has a green line under it
  • The byte at the same position in the (4-byte) word, but in B in the previous round
    (here enc_state_plain_5)
    • This is becase of the xor
To set a byte in B we just copy A from the previous round (this is for encryption).


For the decryption it is kinda similar:
To set a byte in A we copy B from the next round (now going from bottom to top, but still countin from top to bottom).

Here an example to get to dec_state_5_5
To set a byte in B we need to know:
  • The byte at the same position in the (4-byte) word, but in A in the next round
    (here dec_state_6_1)
  • The byte at the position you get when you rotate B to the right by one, but in A in the same round (here dec_state_5_0)
    • Note you would compute A first by copying it from B from the next round
  • The keybte below the byte in the previous bullet point (here K0 again)
Now we can set all the red dots we can reach from encryption and decryption with only the keybytes we know.


Finally it's time to get blue!

Having computed the red dots from both sides, we see that we have:
  • dec_state_2_6 //also called r2
    • Which is the same as dec_state_1_2
  • enc_state_1_7 //also called r1
This together with K0 is what we need to compute blue (which is state_2_3).


Time to get K4 

If we copy over blue (state_2_3) to state_3_7, we can compute K4.

Normally our formula is state_4_3 = SBox[ dec_state_3_2 xor K4 ] xor blue.
But because the SBox here is invertable, we can write
K4 = inv_SBox[ dec_state_4_3 xor blue ] xor dec_state_3_2

You can see the K4 in round 3 has a blue line below it, because we got it through blue.


Adding some orange
Now that we know K4 we can add an orange line below all K4 bytes and copute the orange dots the same way we computed the red dots.

In round 2 we see that we have 2 dots in one square (at state_2_1).
The orange dot we computed is called foo and the red dot we computed is called bar.
If foo != bar then we discard the key candidate.

Next we compute K3 similar to how we computed K4.
The equation is  
K3 = inv_SBox[dec_state_3_0 xor enc_state_2_4] xor blue


Last words

Finally we write a C tool to bruteforce 4 bytes and, if it is a valid key candidate, compute the missing 2 bytes of the key, then verify the key is correct by encrypting and verifying 100 plaintexts.
Add some communication with the gameserver and print the flag. Yay!

Attack takes just a few minutes with 4 threads running on a MacBook Pro 2015.

This challenge kept me busy all day, hope you enjoyed my solution.
I'm curious what the intended way to solve this would have been.

Cheers,
tihmstar



PS: Check out my exploit code
that is, if you manage to compile of course ;)



//
//  main.cpp
//  insomni-crypto
//
//  Created by tihmstar on 19.01.20.
//  Copyright © 2020 tihmstar. All rights reserved.
//

#include <iostream>
#include "sboxes.h"
#include <stdio.h>

#include <sys/socket.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <string.h>
#include <vector>
#include <future>

using namespace std;

uint8_t inverted_sbox1[0x100];
uint8_t inverted_sbox2[0x100];

#define K(byte) ((candidate >> (8*byte)) & 0xff)
#define P(byte) ((plain >> (8*byte)) & 0xff)
#define C(byte) ((cipher >> (8*((byte+4)%8))) & 0xff)


uint64_t encrypt(uint64_t key, uint64_t plain){
    uint32_t A = plain & 0xFFFFFFFF;
    uint32_t B = plain >> 32;
  
    uint32_t keys[7];
    keys[6] = keys[3] = keys[0] = (key & 0xffffffff);
    keys[4] = keys[1] = ((key >> 16) & 0xffffffff);
    keys[5] = keys[2] = (uint32_t)(((key >> 32) & 0xffff) | ((key & 0xffff) << 16));

    for (int i=0; i<7; i++) {
        uint32_t y;
        {
            uint32_t tmp = A ^ keys[i];
            tmp = sboxs[i][0][0x000000FF & tmp] | sboxs[i][1][(0x0000FF00 & tmp) >> 8] << 8 | sboxs[i][2][(0x00FF0000 & tmp) >> 16] << 16 | sboxs[i][3][(0xFF000000 & tmp) >> 24] << 24;
            y = (tmp << 8) | (tmp >> 24);
        }
        uint32_t tmp = B ^ y;
        B = A;
        A = tmp;
    }

    return ((uint64_t)A << 32) | B;
}


static uint64_t debug = 0;

uint64_t check_candidate(uint64_t candidate, uint64_t plain, uint64_t cipher){
//    printf("checking candidate=0x%012llx\n",candidate);
  
    if (candidate == debug) {
      
        printf("");
    }
  
    uint8_t enc_state_0_3 = sboxs[0][2][P(2) ^ K(2)] ^ P(7);
    uint8_t enc_state_1_7 = enc_state_0_3; //r1
    uint8_t enc_state_1_5 = sboxs[0][0][P(0) ^ K(0)] ^ P(5); //r6
    uint8_t enc_state_1_0 = sboxs[1][3][enc_state_0_3 ^ K(5)] ^ P(0); //r5
    uint8_t enc_state_2_4 = enc_state_1_0; //r7

  
  
    uint8_t dec_state_5_7 = sboxs[5][2][C(6) ^ K(2)] ^ C(3);
    uint8_t dec_state_4_3 = dec_state_5_7; //r3
  
    uint8_t dec_state_5_5 = sboxs[6][0][C(4) ^ K(0)] ^ C(1);
    uint8_t dec_state_4_1 = dec_state_5_5;
    uint8_t dec_state_4_5 = sboxs[5][1][dec_state_4_1 ^ K(5)] ^ C(6);
    uint8_t dec_state_3_2 = dec_state_4_5; //r4
  
  
    uint8_t dec_state_4_4 = sboxs[5][3][dec_state_4_3 ^ K(1)] ^ C(4);
    uint8_t dec_state_3_0 = dec_state_4_4;
    uint8_t dec_state_3_5 = sboxs[4][1][dec_state_3_0 ^ K(2)] ^ dec_state_4_1;
    uint8_t dec_state_2_1 = dec_state_3_5;
    uint8_t dec_state_2_6 = sboxs[3][1][dec_state_2_1 ^ K(1)] ^ dec_state_3_2;//r2
  
    uint8_t blau = sboxs[2][2][dec_state_2_6/*r2*/ ^ K(0)] ^ enc_state_1_7 /*r1*/;

    uint8_t k4 = inverted_sbox1[dec_state_4_3/*r3*/ ^ blau] ^ dec_state_3_2/*r4*/;
  
    uint8_t foo = sboxs[2][0][enc_state_1_0/*r5*/ ^ k4] ^ enc_state_1_5/*r6*/;
    uint8_t bar = dec_state_2_1;
  
    if (foo != bar) return 0;
  
    uint8_t k3 = inverted_sbox2[dec_state_3_0/*r8*/ ^ enc_state_2_4/*r7*/] ^ blau;

    return candidate | ((uint64_t)k4 << 32) | ((uint64_t)k3 << 24);
}


#define PORT 1337
//#define HOST "127.0.0.1"
#define HOST "34.65.198.15"

int main(int argc, const char * argv[]) {
    printf("start\n");

    for (int i=0; i<0x100; i++) {
        inverted_sbox1[sboxs[4][2][i]] = i;
        inverted_sbox2[sboxs[3][3][i]] = i;
    }
  
    int sock = 0;
    size_t bufferSize = 0x100 * 50000;
    char *buffer = (char *)malloc(bufferSize);
    struct sockaddr_in serv_addr;
    if ((sock = socket(AF_INET, SOCK_STREAM, 0)) < 0){
        printf("\n Socket creation error \n");
        return -1;
    }
    serv_addr.sin_family = AF_INET;
    serv_addr.sin_port = htons(PORT);
      
    if(inet_pton(AF_INET, HOST, &serv_addr.sin_addr)<=0){
        printf("\nInvalid address/ Address not supported \n");
        return -1;
    }
  
    if (connect(sock, (struct sockaddr *)&serv_addr, sizeof(serv_addr)) < 0){
        printf("\nConnection Failed \n");
        return -1;
    }
  
    read(sock, buffer, bufferSize-1);
  
    string chal = buffer;
    chal = chal.substr(chal.find("\"")+1);
    chal = chal.substr(0,chal.rfind("\""));
    printf("got chal='%s'\n",chal.c_str());
  
//#warning DEBUG
  
    std::string userinput;
    cin >> userinput;
  
    userinput += "\n";
  
    printf("got userinput: %s\n",userinput.c_str());
  
    write(sock, userinput.c_str(), userinput.size());
//    write(sock, "DEBUG\n", sizeof("DEBUG\n")-1);

    read(sock, buffer, bufferSize-1); //"Brace yourself, your favorite oracle has a challenge for you...\n"
  
    printf("reading input...\n");

    ssize_t didRead = 0;
    while(true){
        ssize_t r = read(sock, buffer+didRead, bufferSize-1-didRead);
        didRead += r;
        if (strstr(buffer, "Can you recover the key?")) {
            break;
        }
        printf("reading more...\n");
    };
  
    if (didRead >= bufferSize) {
        printf("we read too much!\n");
        exit(1);
    }
  
    std::string input = buffer;

  
    printf("got input!\n");
  
  
  
    std::vector<pair<uint64_t, uint64_t>> pairs;
  
    ssize_t cpos = -1;
    while (pairs.size() < 100) {
      
        cpos = input.find("(",cpos+1);
        ssize_t ccomma = input.find(",",cpos);
        std::string plain = input.substr(cpos+1, ccomma-cpos-1);
        ssize_t closing = input.find(")",ccomma);
        std::string cipher = input.substr(ccomma+1, closing-ccomma-1);
      
        uint64_t pp = 0;
        uint64_t cc = 0;
      
        char *z = NULL;
      
        pp = strtoull(plain.c_str(),&z,10);
        cc = strtoull(cipher.c_str(),&z,10);

        pairs.push_back({pp,cc});
    }

    ssize_t newline = input.find("Can you recover the key?");
    input = input.substr(newline);
    printf("input=%s\n",input.c_str());
  
    printf("got 100 pairs!\n");
  
    bool keepRunning = true;
  
    int threadsCnt = 4;
  
    std::vector<future<uint64_t>> threads;
  
        for (int i=0; i<threadsCnt; i++){
            threads.push_back(std::async(std::launch::async,[threadsCnt, &pairs, &keepRunning](int worker)->uint64_t{
                uint64_t iter = 0x100000000 / threadsCnt;
                uint64_t witer = iter*worker;
              
              
                uint64_t plain = pairs.at(0).first;
                uint64_t cipher = pairs.at(0).second;
              
              
                for (uint64_t z = 0; keepRunning && z<iter; z++) {
                    uint64_t i = z + witer;
                  
                    if (z % 0x1000000 == 0) {
                        printf("[%d] cand=0x%012llx\n",worker,i);
                    }
                  
                    uint64_t cand = (i >> 8) | ((i & 0xff) << 40);
                    if (uint64_t candidate = check_candidate(cand, plain, cipher)){
//                        printf("key candidate=0x%012llx\n\n",candidate);
                      
                        bool bad_key = false;
                      
                        for (auto &p: pairs) {
                            if (encrypt(candidate, p.first) != p.second) {
                                bad_key = true;
                                break;
                            }
                        }
                      
                        if (!bad_key) {
                            printf("GOT KEY 0x%012llx\n\n",candidate);
                            keepRunning = false;
                            return candidate;
                        }
                    }
                }
              
              
                return 0;
            },i));
        }
  
    printf("waiting for workers to finish...\n");
    uint64_t key = 0;
    for (int i=0; i<threadsCnt; i++){
        threads[i].wait();
        uint64_t lk = threads[i].get();
        printf("lk[%d]=0x%012llx\n",i,lk);
        if (!key){
            if (lk) {
                key = lk;
                printf("FINALLY GOT KEY 0x%012llx\n\n",key);
            }
        }
    }
    printf("all workers finished!\n");

    memset(buffer, 0, bufferSize);
  
    snprintf(buffer, bufferSize, "%012llX\n",key);
    printf("sending: %s",buffer);
  
    write(sock, buffer, strlen(buffer));
  
    printf("response:\n");
    for (int i=0; i< 5; i++) {
        ssize_t s = read(sock, buffer, bufferSize-1);
        if (s <=0) {
            break;
        }
        printf("%s",buffer);
    }
  
      
//    /////// --- --- -- - -- - -
//    uint64_t key = 0x5a4142022e09;
//    uint64_t plain = 0x85d8888f97c18284;
//    uint64_t cipher = 0xf50f82a8f699904e;
//    printf("key=0x%012llx\n\n",key);
//
//
//    //begin
//    uint64_t i = ((key & 0xffffff) << 8) | ((key >> 40) & 0xff);
//    uint64_t cand = (i >> 8) | ((i & 0xff) << 40);
//
//    if (uint64_t candidate = check_candidate(cand, plain, cipher)){
//        printf("key candidate=0x%012llx\n\n",candidate);
//        uint64_t e = encrypt(candidate, plain);
//    }
  
    printf("done!\n");
    return 0;
}










Donnerstag, 12. Dezember 2019

Internet Archive: Thorsten Holz - Transgender Best Of

Internet Archive: Thorsten Holz Transgender Best Of

No comment



Twitter: https://twitter.com/thorstenholz/status/1204712508361191424






Twitter: https://twitter.com/thorstenholz/status/1204489027958845441



Twitter: https://twitter.com/thorstenholz/status/1204710330129166336



Twitter: https://twitter.com/thorstenholz/status/1204703768505401344


Twitter: https://twitter.com/thorstenholz/status/1204684675224129537







Twitter: https://twitter.com/thorstenholz/status/1204492547986472961





Twitter: https://twitter.com/thorstenholz/status/1204686103019696130


Mittwoch, 31. Januar 2018

Modern post exploitation techniques

It's been a while since i posted something on this blog last time, mostly because i was really busy studying.
Soon i will be working on my bachelor thesis and for preparation i wrote a "scientific paper like writeup" about the techniques i developed during the creation of untetherHomeDepot.
Since recently *a lot* of people got interested in jailbreaking and exploiting i thought you might find it interesting and decided to share.

Enjoy reading it and be sure to let me know what you think in the comments section.

Greets
tihmstar






https://drive.google.com/file/d/1guGYQVc5NWar6KGr4lbJnAIM9qIa17vs

Mittwoch, 18. Januar 2017

HALP! i get same nonce/100% nonce collision

Hello everybody,
once again there is an unsolved mystery, so there is once again time for a blogpost!

This time: The mysterious "always same nonce *bug*" or "100% collision with nocestatistics"

So after releasing futurerestore/noncestatistics (basically tools which *bruteforce* apnonces), i got lot's of tweets/emails telling me this is a bug in noncestatistics/futurerestore/calc.exe


So what's really up with this?
Well i can assure you this is neither a bug in noncestatistics, nor in futurerestore and also not a bug in calc.exe
You might be thinking: why is this apnonce thing, which is supposed to be random, always exactly the same?
I assume this is a bug introduced somewhere in 10.x

But let's take a look at what really happens...
If you've seen my talk at 33c3, you probably know what happens if you request an apnonce in normal mode.
Quick recap:
1) you request an apnonce with iTunes/idevicerestore/on device OTA updater
2)lockdownd (i think it's lockdownd, but don't quote me on that) is responsible for answering the request. So lockdownd asks the kernel "hey i need a nonce".
3) kernel does the following:
3.1) if a nonce hasn't been requested since the device booted, choose a random generator and write it to nvram.
3.2) read generator from nvram and derive a nonce from it
3.3) return that nonce to lockdownd

So here you see, that when you request a nonce twice without rebooting a device, you'll get the exact same nonce in normal mode. If you want it to change (in normal mode), you need to reboot.
So far, so good.
Now when you reboot into recovery (iBoot) two things can happen:
1) a generator does not exist in nvram, then *somehow* choose a random nonce (i'm not 100% sure but i think iBoot randomly chooses a generator and then derives a nonce from that, instead of directly deriving a nonce)
or
2) a generator does exist, then derive a nonce from that generator directly

When you go the second route, the generator is cleared from nvram, so if you reboot into recovery again, you can't get the same nonce twice.
This makes totally sense.
The problem is that for some reason apple fucked this up in iOS 10 (WTF APPLE!?!?! it worked perfectly fine in pre-iOS 10).
So the issue now is, that nvram doesn't get cleared so always the same nonce is derived in recovery.
So if this happens to you, you can verify this by changing the generator.
To do this you can reboot into normalmode and request a nonce. This should make the kernel write a different generator to nvram. If the generator still doesn't get cleared in recovery, then you should at least see a different nonce repeating over and over again.

Now i don't know what exactly causes this and i do know that it is possible to not have this problem, to launch the probabilistic attack exploiting bad randomness, however i don't know what exactly you need to do to clear that nonce from nvram without jailbreak.

Can you abuse that for prometheus?
Well, technically you can, because if you request an APTicket for that nonce and get the same on next reboot, you can use that ticket.
The issue here is, that once the nonce changes you'll probably never be able to generate that again (assuming the PRNG isn't horribly broken on post iPhone5s).
So you'd need to avoid requesting an APNonce in normal mode via iTunes (which shouldn't be too big of a problem if you never connect your phone to a computer), but you also need to block the on device OTA updater from requesting a nonce, which might be more of an issue.

This means if you somehow can keep the same generator forever in nvram, you can downgrade iPhone6/iPhone6s and iPhone7 with prometheus without jailbreak. So if you want to look into this, go ahead and share your results with us. (I'd love to see a page on theiphonewiki where people can actively work and share their results about all this)
I personally will not look into this particular bug right now.
Also don't forget that apple introduced this bug with an update and they can easily fix this with another update.

So that's the story with 100% noncecollision. You don't need to worry that noncestatistics, futurerestore or calc.exe might be broken.

greets
tihmstar

Dienstag, 10. Januar 2017

BasebandGoldCertID not found, please spam tihmstar!

Hello everyone,
i've been writing a few blogposts lately, which were really fun and i think i can get used to this :D

Today's topic is tsschecker's BasebandGoldCertID (or short bbgcid).
You might have see this warning in tsschecker already:
Version: 211220dfa58e15d9f15c08a9185b53acadc489de - 182
[TSSC] opening firmware.json
[JSON] counting elements
[JSON] parsing elements
[TSSC] selecting latest iOS: 10.2
[TSSC] using cached Buildmanifest for iPad3,5_10.2
[Error] [TSSC] ERROR: device "iPad3,5" is not in bbgcid.json, which means it's BasebandGoldCertID isn't documented yet.
If you own such a device please consider contacting @tihmstar to get instructions how to contribute to this project.
[WARNING] [TSSR] there was an error getting BasebandGoldCertID, continuing without requesting Baseband ticket
[TSSR] Request URL set to https://gs.apple.com/TSS/controller?action=2
[TSSR] Sending TSS request attempt 1... success

iOS 10.2 for device iPad3,5 IS being signed!

ERROR: device is not in bbgcid.json, it's BasebandGoldCertID isn't documented yet.
So what exactly does this mean?
Again, tsschecker started as a project to analyse apple's tss server. You can send customized requests and see what it responds. Beside APTickets for the main iOS system you also have the baseband.
The baseband is a seperate processor, which has it's own OS. One of it's main tasks is to handle cellular communication like GSM, LTE and stuff like that (note i'm not an expert about baseband).
So basically you have basebands in phone and also in iPads which have 3G or LTE or whatever.
When restoring such a device you also need to restore the baseband, which has it's own seperate restore process. It also uses stuff like APTickets which need to be requested from apple while restoring (i really haven't looked into how this exactly works, these are just general observations).
So we note here: when restoring we also need a ticket for the baseband.

Tsschecker is able to request such tickets even though there are not many customizations yet.

Does that mean i can save a basebandticket?
Yes, you can save a baseband ticket if you want.
So it works as following:
When requesting a baseband ticket you need to send a bunch of values for apple. I figured out that most of these values can either be random, or omitted completely. All except the BasebandGoldCertID. This one has to be a device specifiy value matching the devicemodel.
For example if you want to get a ticket for the iPhone6,2 baseband you need to send the BasebandGoldCertID 3554301762. This is the same for all iPhone6,2 models. If you don't send this exact value for the iPhone6,2 you don't get a ticket.
Normally when you restore a device using iTunes or idevicerestore that value is read from device while restoring, that's why a central database was never needed.
But tsschecker aims to send requests to apple's server without the need of having a real device connected (thus the name "tss checker").
So this is the reason i started to collect BasebandGoldCertIDs.

Cool, does that mean i can downgrade basebande?
No, unlike iOS a downgrade is not possible. This is because the baseband all this ticket and restoring and signing stuff and i don't know of anybody actively looking into it and especially actively working on a downgrade. In theory you can find bugs or something like prometheus in the baseband but right now there isn't any public tool able to downgrade the baseband (correct me if i'm wrong) and also i don't know anyone working on that.

So what are the tickets even used for if i can't downgrade?
Literally nothing. I don't even know if the tickets we are saving right now can be used for downgrades in future or if there's something important i left out/didn't notice. Again, i haven't really looked into baseband.

So why even requesting tickets?
Well the initial idea of this is just to see if the baseband of a specific iOS verison is signed or not (remember "tss checker"? :P).
Right now this feature is used in futurerestore to see if a baseband is really signed before attempting to restore a baseband which was not shipped with the version being restored. (That cool iOS/baseband mismatch thing allowing to downgrade with prometheus)

When i started tsschecker i didn't know this tool would be that popular. I thought i should ask everybody who even cared using this tool to help me collecting bbgcids, but right now i get spammed with emails. This is why i decided to write this blogpost to exaplain what this is all about.

Ok i see. I have a device, which you don't have in your list, how can i help?
Finally the good part :P
Ok so basically you need to take your device and read out the BasebandGoldCertID and send me an email containig the devicemodel and the bbgcid. Then i can put that to tsschecker. You can even make a pullrequest on github with your bbgcid. If you can, please test if you get a ticket before submitting the bbgcid. If you run tsschecker with --no-baseband=2 then it will try to request only a baseband ticket.


How to find BasebandGoldCertID?
There are two easy ways of finding it. The first one is with ideviceinfo:


The second is with latest redsn0w, which you can get here: http://blog.iphone-dev.org/tagged/redsn0w
Make sure to use the "normal" version, not the beta.
Then you click Extras->Even more->Identify








So let's go and collect all BasebandGoldCertIDs

greets
tihmstar

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.

TL;DR
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:
9f4aeec726e7c682339ddb3c6c2dec52662dc517
9e4c518009d00df190a450b3b47691768812360c
a3eb70ccb7f4005d2789604f7724c6f37b4df096
8514e466166d7cc8632e26cc49376adea798ba56
543c6279f80bfd192aa7fd96c31faeb86c62a487
e35948fd9400e7c4732ac2199bf379de81589e59

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

greets
tihmstar

Montag, 2. Januar 2017

Updates on prometheus / Stuck at Waiting for device... / Are my shsh file broken????

Hello everybody,
first of all i wish you a happy new year :D
In the past few days happened quite a bit, i held my talk at 33c3 about downgrading iOS, released futurerestore and img4tool and figured out tsschecker was broken.
Okay first things first. In case you haven't seen my presentation at 33c3 i really recommend doing so, as i'm explaining all downgrade related stuff starting from iOS (or iPhoneOS) 1.
Here's a link: https://media.ccc.de/v/33c3-7888-downgrading_ios_from_past_to_present
Right after the talk i released futurerestore and instantly got spammed with "it's not working i get segfault".
When i got home from 33c3 i figured it was related to build system i'm using for release builds (i'm automatically crosscompiling macos stuff on a linux box on every commit). The issue here was that futurerestore or better said even idevicerestore needs openssl. I've heard that was deprecated in macos a while ago and is not shipped by default (@p0sixninja suggested moving to CoreCrypto on macos).
Anyways, right now i'm simply linking the project to openssl's libcrypto.0.9.8.dylib which needs to be in  /opt/local/lib/ because the one shipped with macos in /usr/lib is missing a symbol. So until i changed stuff in my buildsystem (which is not first priority at the moment) you need to manually install openssl via homebrew or macports and make sure the library is there.
Having fixed that and a bunch of other stuff which i'm not gonna talk about because that's not too interesting, leaves us with one final problem: stuck at "Waiting for device...".
I need to say at this point that figuring out all these issues took a lot of effort, it "worked for me" and for some weird reason didn't work for everyone else. So after ruling out (hopefully) all the bugs in futurerestore which could have caused the "waiting for device" problem i finally realized the bug wasn't in futurerestore but in tsschecker.

When i started tsschecker it was a tool for me to analyze apple's tss server. It was really handy to send lots of different requests and see what response i'd get. The more and more i was working on tsschecker the more useful it became. At first i didn't even plan to use it to save shsh files, but at some point when i was working on prometheus i realized that tsschecker was the only tool which could do what i needed. At that time it was the --apnonce option and later the saving generator feature.
During development of prometheus i used tsschecker a lot and added more and more stuff to it, which in the end turned out to work perfectly with my test device (iPhone5s).
When iOS 10.1.1 jailbreak was announced and i told people that prometheus could upgrade them from one jailbroken iOS to another, everyone got hyped about saving shsh files.
While this would have been no problem with iOS 9, there is something apple changed in iOS10 i didn't notice, as i wasn't even using iOS10 on any of my devices.
Up to iOS 9 apple had a different IPSW for evey devicemodel (like iPhone6,1 iPhone6,2 ...).
With iOS 10 apple started packing lots of stuff into one IPSW making it usable for a lot of devices.
For example the iPad_64bit_10.2_14C92_Restore.ipsw is used for restoring 6 different devices!


As you can see in the image there are 12 different restore configurations (BuildIdentities) packed in one file!
This used to be 2 namely "Erase" and "Update" config, now there are 2 for every supported device.
Each of these configurations need a different APTicket.
What tsschecker would do in past versions is just take the first BuildIdentity and request a ticket for that. Which would have been fine is there was only one device supported per BuildManifest.
The first BuildIdentity in the manifest is often (always?) a config for "Erase", second is for "Update".
That didn't really matter in previous downgrades, as the only difference is the ramdisk hash (one for restore ramdisk, one for update ramdisk). However this does matter for prometheus. But even if tsschecker would pick the "Update" config instead of "Erase" you could simply use -u option in futurerestore and you would keep your data while upgrading (in case this doesn't fuck up the device ;P). The real problem here is that if the first BuildIdentity isn't for your device. For example you have iPad4,2 but the first BuildIdentity is the "Erase" config for iPad4,4.
In this case tsschecker would request a APTicket for iPad4,4 instead of iPad4,2 which renders the APTicket useless to you.
I didn't really notice this until now, as it *just worked* for my device.
This is fixed in latest tsschecker (which is 157 at the time of writing). Right now it properly searches for the correct config. What i noticed here is that there are some models like iPhone8,1 which have different boardconfig ("n71ap" and "n71map"). Those need to be correct too. Tsschecker now has a parameter -B or --boardconfig which lets you specify the boardconfig. It tires to automatically derive boardconfig from devicemodel and devicemodel from boardconfig, but in case there are ambiguities you need to specify the model/boardconfig manually.


So this hopefully save valid shsh files for future, but what about the ones we already saved?
How to verify they are good/bad?

Today i updated img4tool to version 82.
I added -v --verify parameter. This doesn't even comes close to what i plan to check inside IMG4/IM4M files, but today's update should be good enought for us right now.
What we need to do is to verify which of the BuildIdentities match the APTicket we have saved.
To do this we can do: img4tool -v BuildManifest.plist -s my_saved_file.shsh
IMPORTANT: you need to take the BuildManifest.plist from for IPSW your shsh file correcponds to.
If you saved your shsh file for 10.1.1_14B150 then you also need to use the BuildManifest.plist from the 10.1.1_14B150 IPSW.


When you run that command you'll see a bunch of warnings, which you can ignore. I need to figure out in future how to handle a few things but as of right now it works.
When the shsh file matches any of the restore configs in that BuildManifest you'll see something like in this image. What it would do is print you some information about the BuildIdentity which matched.

The important thing here is to check DeviceClass of that shsh file. The given file can only be used to restore ("Erase" install) an iPhone8,1 with boardconfig n61ap.
This is ok right?
Well the poor guy who sent me that shsh file also sent me his futurerestore log:

What you can see right in the very first line is that his phone actually is n71ap, which is not what the APTicket is for. Futurerestore tries to stich that APTicket to iBEC.n71.RELEASE.im4p which is correct for that device, but since the ticket is not for that file verification fails and the device rejects it.
This means the device fails to load iBEC, ramdisk, kernel and doesn't boot into restore mode.
You might be thinking: well let's just boot the other iBEC which the ticket is for.
But that won't work, as there are checks whether the firmware actually belongs to the device or not.
Unfortunally this person is just out of luck :(

Is there anything i can do when my ticket has wrong boardconfig?
Not really, all you can do is make sure that you save for correct boardconfig in future.
Even if that's not what you want to hear: make sure you save shsh for 10.2 while it's signed :/


So that's the story with with bad tickets, if you verified your tickets to be good and you still stuck at "waiting for device..." then just send me a tweet or an email and i'll see how i can help :)

At least there were some people who were able to use prometheus so the work was definetly worth it :D

Keep saving your shsh files
greets
tihmstar