If you ever wanted to know what’s stored in a DVD’s BCA, you’ve probably read it out using your favourite device. Here I present you a different approach: reading it out by scanning the area and running “pattern recognition” on the image.

Here is a part of a Wii game that I’ve scanned:

Image

After filtering and thresholding it looks like this:

Image

The black and white image is then fed into a tool I wrote that will estimate the midpoint and the major and minor axes of the inner ellipse, detect all the BCA cuts around it, mark them and spit out the timing between the cuts. This timing can then be decoded into the actual data that is stored in the area. Note that the thick cuts are actually two normal ones that my scanner’s resolution didn’t pick up anymore, the tool will detect that too. Here is a part of a generated image (the blue lines are the detected cuts):

Image

And here is a complete output too:

Image

Shamir’s Secret Sharing

March 30, 2013

To be able to understand what is going to follow, I first have to do a little mathematics:

Let’s define a polynomial over a finite field P \in \mathbb{F}_q[X] of degree k as P(X) = a_0 + a_1 X + a_2 X^2 + \dots + a_k X^k (a_0,\dots,a_k \in \mathbb{F}_q) where q is a prime number and \mathbb{F}_q is a finite field with q elements. If we have (X_i) (X_i \ne X_j for i \ne j) and (Y_i = P(X_i)) with i = 1,\dots,k we can use Lagrange interpolation to directly calculate a_0: a_0 = \sum_i Y_i \cdot \prod_{i \ne j} (-X_j)(X_i - X_j)^{-1}.

But what are we going to use this for? Consider you want to divide a secret into n different parts and you want that k \leq n parts are required to reconstruct the secret. This is what is called a (n,k) threshold scheme. We can use our little mathematics from above to implement such a scheme. Choose the secret S and create a random polynomial of degree k - 1 with a_0 = S. To create the parts (shares) Y_i evaluate the polynomial at random X_i and distribute the pairs (X_i, Y_i) to the different participants (the X_i can be public, the Y_i are private to each one). To reconstruct the secret, k of the participants can share their Y_i and then use the explicit formula from above ([AS]).

Here is an example run along with some source of my implementation:

//...
bn_t *N = bn_from_str(bn_alloc(32),
    "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
    "FFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F");
bn_t *s = bn_from_str(bn_alloc(32),
    "098765432100DEADBEEF000000000000"
    "000000000000CAFEBABE001234567890");

//Create random polynomial.
poly_t *p = ssecrets_create_poly(s, 3, N);

bn_t **lx = (bn_t **)malloc(sizeof(bn_t *) * 4);
bn_t **ls = (bn_t **)malloc(sizeof(bn_t *) * 4);

u32 i;
for(i = 0; i < 3; i++)
{
    //Evaluate at random x.
    lx[i] = bn_reduce(bn_rand(bn_alloc(N->n)), N);
    ls[i] = ssecrets_create_share(p, lx[i]);
    bn_print(stdout, "P(", lx[i], ") = ");
    bn_print(stdout, "", ls[i], "\n");
}

//Reconstruct secret.
bn_t *cs = ssecrets_calc_secret(lx, ls, 3, N);
bn_print(stdout, "secret = ", cs, "\n");
//...

/*
* P(9EF35877FC0E2DB6B76BFF03B8CFA2EADD90190719DA598482D1569C6F9CA1EF) =
* B451E41F20E5E85EC35CB94E6E88E292B25CBF67B687D93B6B42D18EEE26A8A9
*
* P(810A3DB3AB3E4EA758A535A0616A6C9E1FE08B610D5F0496911A1AFFD3BC8136) =
* B1B26A93205BD5416288A8EB0DE050C76D501247A8BE7BD4BA4416FEB743C90D
*
* P(37D9B47A812B434077C025ADA5300EA41778036222ECD4853E4D64CB92CDF135) =
* 9D58638CB24E0783966106ED8BB9D21F8F308C845829E6DD3CF1F7AD0C0499BB
*
* secret =
* 098765432100DEADBEEF000000000000000000000000CAFEBABE001234567890
*/

References:

 

First one needs to understand, that an ideal decompiler, that will recover the original source code, is impossible to create. The process of compilation is removing a lot of high level information, such as used data types or loop types. Then optimization could re-arrange code/data flow, eliminate common subexpressions, perform function inlining, etc. Therefore any output of our decompiler will most likely not match the original source code, but if we do it right, we can get a (very) close approximation.

So what is it, that I’m doing at the moment?

Currently the decompiler will need to be fed with an ELF binary, that has its section headers present and from them it will extract information about executable and data regions. For every executable region it will then extract subroutines and split every of them into basic blocks. A basic block is a piece of code, that only contains simple operations and ends with a branch. This basics blocks might get split again, if a branch to any of its operation occurs from inside the subroutine. This way we will collect a list of all the basic blocks, can link them according to their exit branches and end up with the control flow graphs of all the subroutines. For identification of high level statements like ifs and loops (see [REC] for loop detection) we compute DFS and dominator trees and for later use the frontiers of each block (see [DOM] for used algorithms). Next we perform register liveness analysis to identify subroutine arguments and return values (see [LIV] for used algorithm). Now we can translate all the assembler instructions into simplified operations, e.g. translate “ori rt, ra, 0″ into “rt <- ra” and identify local stack variables in that process too, following IBM’s SPU ABI specifications (see [ABI]).

More additional steps are then required to produce high level code, as you can see in the following list (entries marked with (DONE) are finished and working already):

  • Extract text/data regions (DONE)
  • Extract subroutines (DONE)
  • Extract basic blocks (DONE)
  • Create control flow graphs (DONE)
  • Compute (reverse) DFS/dominator/frontier information (DONE)
  • Extract high level statements using (reverse) DFS/dominator trees (DONE)
  • Local and global liveness analysis to find subroutine arguments (DONE)
  • Extract and simplify operations from every basic block (DONE)
  • Transform operations into SSA form using frontier information (PARTIAL)
  • Perform constant/expression propagation and dead code elimination (PARTIAL)
  • Transform operations from SSA form
  • Build expression tree from optimized operations
  • Output high level (pseudo-)code from restored expressions

I’m currently looking into methods that don’t need SSA form to perform propagation, but if they don’t work (too well) I’ll have to stick with SSA. Here is the output of a little argument test program and here is the original source (R ~ register, S ~ stackvar, I ~ immediate).

After SPU decompilation is working, I plan to refactor the source code to make it more generic, so it’s easier to port it to other CPU architectures (e.g. PPC).

References:

The Exploit

November 20, 2012

As the exploit that was used to dump lv0ldr/bootldr/howeveryouliketocallit is public now, let’s have a closer look at it to understand what’s going on. Here is what I have reversed from lv0 (it shares the syscon portion of the code with its SPU counterpart):

//In .data section.
static u8 tmp_pkt[0x800];

//Get size from sc packet.
#define GET_SIZE(pkt) ((pkt[4] << 8) | pkt[5])

int read_cmpl_msg(/*...*/, u8 *payload_buf /*r5*/, int min_size /*r6*/, /*...*/)
{
    u16 pkt_size;

    //Get packet header.
    memcpy_aligned_64(tmp_pkt, MMIO_SC_PKT, 0x10);

    //Check packet size.
    pkt_size = GET_SIZE(tmp_pkt);
    if(pkt_size - 4 < min_size || pkt_size + 8 > 0x800)
        return ERR;

    //Run first sc_checksum.
    if(!sc_checksum(...))
        return ERR;

    //Read packet again (plus header!).
    pkt_size = GET_SIZE(tmp_pkt);
    memcpy_aligned_64(tmp_pkt, MMIO_SC_PKT, size + 0x1B);

    //Get size again (not checked now).
    //I suspect that this is actually a compiler 'quirk' and not a
    //programmer mistake. The original source probably accesses the
    //packet size through a structure and the compiler noticed the
    //non const access of the packet and generated this read of the
    //size member because it could have changed.
    pkt_size = GET_SIZE(tmp_pkt);

    //Let's have some fun (payload_buf on caller stack).
    memcpy(payload_buf, tmp_pkt + 8, size - 4);

    //Run second sc_checksum.
    if(!sc_checksum(...))
        return ERR;

    //...
}

The syscon library implements some high level functions, e.g. to shutdown the console on panic or to read certain configuration values. Every of this functions internally uses another function to exchange packets with syscon and the exchange function uses the read_cmpl_msg one to get the answer packet. The top-level function will pass a fixed size buffer to the exchange function. So if we are able to control syscon packets, e.g. by emulating MMIO (and thanks to IBM we are), we can change the packet size between the two packet readings and overwrite the caller stack. And if we first copy a little stub to shared LS and let the return address point to it, we can easily dump the whole 256 kB.

Nothing more left to say now, let’s wait and see if this is going to be fixed in future firmware versions (we just have to check lv0 fortunately).

Exploiting (?) lv2

September 19, 2012

A long while ago KaKaRoTo pointed me to a stack overflow he found while reversing lv2_kernel. But there are two problems:

  1. The vulnerability is in a protected syscall (the SELF calling it got to have the 0x40… control flags set). So you’d first need to find a suitable usermode exploit (don’t ask us), that gives you code execution with the right privileges.
  2. The payload data is copied to lv2 heap first and the function will do a free call on it before the payload has any chance to get executed. This might not sound like a problem but it looks like lv2’s heap implementation will overwrite the free’ed space with 0xABADCAFE and thus destroy the payload.

Here is my sample implementation for 3.41 lv2_kernel (although the vulnerability should be present in all versions of lv2 up to the latest firmware), maybe someone of you will find a way to overcome problem (2.) and can get something nice out of it because right now it’s only good to crash lv2.

eEID Cryptography

July 11, 2012

When metldr is encrypted at factory, a special keyset is set in the binary before encryption. Later when an isolated loader is loaded by metldr, it will copy the keyset to LS offset 0x00000. It consists of eid_root_key and eid_root_iv. To not having to use the same key for all eEID parts, several subkeys are generated from special data called individual information seed. These seeds are stored in the metadata header of isolated modules loaded by isoldr. When isoldr will load a module, it will call a subroutine that encrypts each seed chunk (0x40 bytes) using eid_root_key and eid_root_iv. Then the so-called individual infos are passed in registers r7 to r22 (= 0x100 bytes in total) to the loaded module where they are used further. Usually isolated modules have a seed section of 0x100 bytes but all of them (except sb_iso_spu_module) have all zeroes but the first 0x40 bytes chunk. You can, for example, find the recently published EID0 seed in the metadata section of aim_spu_module. Appliance info manager is used to get e.g. the target ID or the PSID from EID0. This explains why the seed can also be found in isoldr directly, since that one is checking EID0 too.

As you can probably think, a fair amount of reversing time and knowledge has gone into finding this, so stop calling us *swearwords* for not releasing information that could potentially lead to more piracy, because we think that this would do more harm to the “scene” than just keeping some information in private (for now). Also I can only encourage everyone that thinks about us this way or is greedy demanding for developers/reverse engineers to release their stuff, to fire up isoldr in IDA or disassemble it with objdump and try to reverse all this from start to end. We’ll see, who is able to pull this through on his own…

Thanks to oct0xor we could get our hands on the decrypted TB payload (stage 2). Of course the first thing to do is to fire it up in IDA, our favourite tool of the trade. The entry code of the payload looks like this:

1337C0DE00000000 _start:
1337C0DE00000000
1337C0DE00000000 .set var_58, -0x58
1337C0DE00000000 .set arg_10,  0x10
1337C0DE00000000
1337C0DE00000000         mflr      r0
1337C0DE00000004         bl        loc_1337C0DE00000008
1337C0DE00000008 1337C0DE00000008 loc_1337C0DE00000008:
1337C0DE00000008         mflr      r3
1337C0DE0000000C         lis       r4, 0 # 8
1337C0DE00000010         addi      r4, r4, 8 # 8
1337C0DE00000014         subf.     r3, r4, r3
1337C0DE00000018         beq       skip_reloc
1337C0DE0000001C         li        r6, 0
1337C0DE00000020         oris      r6, r6, 0x1337
1337C0DE00000024         ori       r6, r6, 0xC0DE
1337C0DE00000028         lis       r4, 1 # 0xA848
1337C0DE0000002C         addi      r4, r4, -0x57B8 # 0xA848
1337C0DE00000030         lis       r5, 1 # 0x10D18
1337C0DE00000034         addi      r5, r5, 0xD18 # 0x10D18
1337C0DE00000038         subf.     r5, r4, r5
1337C0DE0000003C         beq       skip_reloc
1337C0DE00000040         srdi.     r5, r5, 3
1337C0DE00000044         mtctr     r5
1337C0DE00000048         add       r4, r4, r3
1337C0DE0000004C
1337C0DE0000004C reloc_loop:
1337C0DE0000004C         ld        r5, 0(r4)
1337C0DE00000050         srdi      r7, r5, 32
1337C0DE00000054         cmpw      r7, r6
1337C0DE00000058         bne       skip_rewrite
1337C0DE0000005C         clrldi    r5, r5, 32
1337C0DE00000060         add       r5, r5, r3
1337C0DE00000064         std       r5, 0(r4)
1337C0DE00000068
1337C0DE00000068 skip_rewrite:
1337C0DE00000068         addi      r4, r4, 8
1337C0DE0000006C         bdnz      reloc_loop
1337C0DE00000070
1337C0DE00000070 skip_reloc:
1337C0DE00000070         std       r0, arg_10(r1)
1337C0DE00000074         stdu      r1, -0x80(r1)
1337C0DE00000078         std       r2, 0x80+var_58(r1)
1337C0DE0000007C         lis       r4, 1 # 0x17E40
1337C0DE00000080         addi      r4, r4, 0x7E40 # 0x17E40
1337C0DE00000084         add       r2, r4, r3
1337C0DE00000088         bl        payload_main

In the first loop it will relocate itself using 0x1337C0DE as an identifier for the upper 32 bits and rewrite that to the actual base. The disassembly above was already loaded using 0x1337C0DE00000000 as base. While scrolling through the data section at the end of the payload one quickly figures out that the RTOC is 0x1337C0DE00017E40.

As I was analyzing the code I found a sub that was basically just a really big switch with random looking case values. Once I reversed the sub at 0x1337C0DE00002578 and some of the following ones and analyzed their usage in the switch sub, I knew that I was looking at a fricking virtual machine.

1337C0DE00002578 vm_push_word_0:
1337C0DE00002578         ld        r11, off_1337C0DE00010128 # stack_ptr
1337C0DE0000257C         ld        r9, 0(r11)
1337C0DE00002580         addi      r0, r9, 4
1337C0DE00002584         std       r0, 0(r11)
1337C0DE00002588         stw       r3, 4(r9)
1337C0DE0000258C         blr

Paranoid TB developers even used XOR-tables to obfuscate the VM instructions and data. The virtual machine is mostly stack based but the instructions let you work using registers too. The next thing to do is to reverse all the instructions and write a disassembler and emulator. Here is some code to unscramble the embeded vm binary for further investigation. I’m going to write more about this topic in the future.

Follow

Get every new post delivered to your Inbox.