A cryptographic vulnerability in WFS (Wii U File System)

Discussion in 'Wii U - Hacking & Backup Loaders' started by EyeKey, Aug 10, 2017.

  1. EyeKey
    OP

    EyeKey GBAtemp Regular

    Member
    196
    428
    Feb 10, 2017
    Israel
    First of all, for clarification, this thread is just for fun and sharing ideas, so don't except anything practical to came out of this, because nothing will probably do.
    This is about the case when you don't have the key of the filesystem.



    This thread about a theoretical cryptographic issue with the WFS that I thought about today. It is just theoretical, so I do many assumptions that are going to be an issue to do in real scenario. It has some potential but it is problematic because the little to no control that you have on the data that is stored in the file system. I will try to explain it as clear as I can.

    TL;DR: If you can control content of files on the filesystem, you can create your own controlled file system without knowing the key.

    As a note, there is NOTHING that Nintendo can do to fix it (not that they care anymore, but even if they wanted - they can't change the file system)

    So first of all, I want to explain how the WFS is encrypted and verified.
    There are two type of blocks, what I call a metadata block, and a data block. Data blocks are blocks that are dedicated to data of files. Metadata block store any other information that the file system uses.
    There are multiple possible sizes of blocks, but usually a metadata block is 0x2000 bytes, and a data block is 0x2000 or 0x10000 bytes.
    Every block is encrypted with AES-CBC, all the blocks with the same key, but a unique IV for each block. The IV is 16 bytes, 4 dwords:
    IV[0] - used block size. In metadata block it is always 0x2000, in data block it can be less than the real block size if it isn't full. This size is rounded up to the sector size of the disk. (usually 0x200)
    IV[1] - the most complex dword of the IV. I will return to this later.
    IV[2] - number of sectors in the disk - it is known
    IV[3] - sector size of the disk (usually 0x200)

    As you can see, we can easily know IV[0], IV{2], and IV[3].

    Just as a remainder, this is how CBC mode works:
    Encryption:
    [​IMG]
    decryption:
    [​IMG]
    So lets say C[0...n] is 0x10 bytes cipher blocks, and P[0..n] is 0x10 bytes plaintext blocks.
    encryption:
    C[0] = AES_ENC(IV ^ P[0])
    C[1] = AES_ENC(C[0] ^ P[1])
    ...
    C[n] = AES_ENC(C[n-1] ^ P[n])
    decryption:
    P[0] = IV ^ AES_DEC(C[0])
    P[1] = C[0] ^ AES_DEC(C[1])
    ..
    P[n] = C[n-1] ^ AES_DEC(C[n])


    Ok lets talk about another concept in WFS. There are things that are called Areas/Quotas. Quota is just a directory with size limit, and it is pre-allocated. There is the root/main quota, which is just the whole disk, and starts at the first block. Each block is part of a quota. In each quota header there is a random number, lets call it the quota id. There is also a random id in the wfs header for the whole wfs, lets call it wfs id.

    So lets go back to IV[1].
    IV[1] = (wfs_id ^ quota_id) + sector number of block (disk sector, relative to the start of the quota)
    quite ugly, ah?
    IV[1] of the first block is 0, because those ids are still not known.

    Now lets talk about the verification. Each block has a hash, SHA1. The hash of metadata blocks are stored inside them, at offset 0x4-0x18. When the hash is calculated offset 0x4-0x18 are just replaced with 0xFF's.
    The hash of the data blocks are in the metadata blocks that point to them, so it is pretty much impossible to temper with them, because if you change anything you need to change the metadata block also, which is also verified.
    If you change any byte in the metadata block some bytes are going to change and the hash is going to fail.

    Now, for the vulnerability, lets assume that all we can do is control content of files, and we know where the encrypted data is in the encrypted disk.

    So if everything is hashed, encrypted and verified, where is the culprit?
    The concept is simple, we are going to create a fake metadata block, and use file content to encrypt it. the hash is inside the metadata block
    Lets have another assumption, just for a moment. Lets say we know the IV of blocks X, Y. X is a metadata block that we want to change, and Y is a data block with data with our control.
    Lets call T[0..n] the target plaintext that we want the block X will have. We are going to build T as a valid metadata block, we can calculate hash of our T so T[4:0x18] will have the hash of T (it is just SHA1, not HMAC or anything)
    And lets mark P_Y as the plaintext of our block Y, and C_Y as its cipher. The same thing about metadata block X: P_X, C_X.

    I am going to do the equations step by step, without skipping anything, so it looks complex but it isn't.

    so lets do:
    P_Y[0] = T[0] ^ IV_X ^ IV_Y
    P_Y[n>=1] = T[n].
    Now lets check it, lets take a look on the cipher that we will get:
    C_Y[0] = AES_ENC(IV_Y ^ P_Y[0]) = AES_ENC(IV_Y ^ T[0] ^ IV_X ^ IV_Y) = AES_ENC(T[0] ^ IV_X)
    C_Y[n>=1] = AES_ENC(C_Y[n-1] ^ P_Y[n]) = AES_ENC(C_Y[n-1] ^ T[n])
    Now, I claim that C_Y is a valid encrypted X metadata block, and we can replace the encrypted X metadata block with it, lets see what P_X will be:
    C_X = C_Y
    P_X[0] = IV_X ^ AES_DEC(C_X[0]) = IV_X ^ AES_DEC(C_Y[0]) = IV_X ^ T[0] ^ IV_X = T[0]
    P_X[n>=1] = C_X[n-1] ^ AES_DEC(C_X[n]) = C_Y[n-1] ^ AES_DEC(C_Y[n]) = C_Y[n-1] ^ C_Y[n-1] ^ T[n] = T[n]
    Success!

    But wait, the IV contains a random number, how are we going to know it? So here is one idea:
    Lets say that we totally want to control the file system. So lets choose block X as block 0, the first block. We know IV_0 ! (see the explanation above on how the IV is built)
    And about block Y. We don't know IV_Y, but we do know C_Y[0], and C_Y[0] acts as the IV of C_Y[1], so we are going to do the same thing, just start from C_Y[1] instead C_Y[0], and use 0x10000 data block. So lets say that block Y is a 0x10000 bytes block, and we can change its content.
    So lets first do P_Y[0...n] = 0, 0, 0, 0, 0, 0...
    C_Y[0] = AES_ENC(0 ^ IV_Y)
    Now we know C_Y[0] (because we look on the encrypted hard disk and we know where Y is, this was our assumption...)
    Now lets change the content of the file, but this time lets do:
    P_Y[0] = 0
    P_Y[1] = T[0] ^ C_Y[0] ^ IV_0
    P_Y[n>=2] = T[n-1]
    Now lets check it:
    C_Y[0] = AES_ENC(0 ^ IV_Y)
    C_Y[1] = AES_ENC(C_Y[0] ^ P_Y[1]) = AES_ENC(C_Y[0] ^ T[0] ^ C_Y[0] ^ IV_0) = AES_ENC(T[0] ^ IV_0)
    C_Y[n>=1] = AES_ENC(C_Y[n-1] ^ P_Y[n]) = AES_ENC(C_Y[n-1] ^ T[n-1])
    Now lets do:
    C_0[n] = C_Y[n + 1]
    So lets check what P_0 is going to be
    P_0[0] = IV_0 ^ AES_DEC(C_0[0]) = IV_0 ^ AES_DEC(C_Y[1]) = IV_0 ^ T[0] ^ IV_0 = T[0]
    P_Y[n>=1] = C_0[n-1] ^ AES_DEC(C_0[n]) = C_Y[n] ^ AES_DEC(C_Y[n+1]) = C_Y[n] ^ C_Y[n] ^ T[n] = T[n]
    Success again.

    Now that we control block 0, we can repeat it to any other block (because now we will know its IV, because we control the wfs and quota id), and we can fake a whole file system that will be valid.

    Ok, so now the issues. It is really hard to control the content of files. @wiiupoo suggested to do it with system transfer from hacked system (and because of him I thought about all of this). Another option is to find an app that download files to the disk from the internet over http or something like that.
    Changing the content of the file (like the second method requires) is even harder (it isn't possible with system transfer for example), but maybe overwritng the file, deleting/recreating it somehow will do the trick. You just need to have a block of your data in the same place as part as the same quota.

    Finding file in the encrypted disk is easier. The simplest thing to do is to compare the disk before and after creating the file. Another option is play with the IV. The only thing that change in an IV between two blocks in the same quota in the same size is the second dword. But between two adjusted block, there may be only one bit different in the IV (think about it). So you can do two blocks of plaintext with the same first block, except that bit, and you should get two identical first blocks encrypted, and search them later in the disk.

    There are probably more possible variation of the same thing that you can do that may solve part of those issues.


    What you can do with fake filesystem? Well I don't think that it is possible to do the regular contanthax, because even if you buy a game, you won't have the ticket of it, but lets just hint that there are some other good options :)

    If I did any mistake/missed something please correct me.
     
    Last edited by EyeKey, Aug 10, 2017
    Valery0p, Maschell, Tommy084 and 25 others like this.
  2. KiiWii

    KiiWii GBAtemp Psycho!

    Member
    3,818
    1,339
    Nov 17, 2008
    United Kingdom
    Sounds incredible, keep up the great work @EyeKey
     
  3. piratesephiroth

    piratesephiroth I wish I could read

    Member
    3,009
    1,620
    Sep 5, 2013
    Brazil
    I think the only place games can write to is usr\save and I don't recall many games that store downloaded stuff there other than Mario Maker.
     
    SciresM and Tomato Hentai like this.
  4. Trumpasaurus

    Trumpasaurus GBAtemp Regular

    Member
    167
    57
    Jul 8, 2017
    United States
    Can you please not beat around the bush? What are you "hinting" at? What would this hope to accomplish?
    Maybe I'm slow, but I don't know the potential application of this initiative.
     
  5. huma_dawii

    huma_dawii GBAtemp Advanced Maniac

    Member
    1,604
    510
    Apr 3, 2014
    United States
    Florida
    I love seeing this threads where I don't understand a cr*p xD reminds me that this site was for this kind of stuff in the past... developers were able to actually discuss code and stuff here.. now its just whining because we don't get PSX on Retroarch :v
     
    Marko76 and FlappyFalco like this.
  6. Marko76
    This message by Marko76 has been removed from public view by raulpica, Aug 12, 2017, Reason: Flaming -rp.
    Aug 11, 2017
  7. Billy Acuña

    Billy Acuña GBAtemp Addict

    Member
    2,246
    1,337
    Oct 10, 2015
    Mexico
    Following this thread if something cool happens :)
     
  8. GerbilSoft

    GerbilSoft GBAtemp Addict

    Member
    2,085
    2,309
    Mar 8, 2012
    United States
    This is a well known issue with any unauthenticated mode of encryption. If you know the plaintext, you're able to modify it in some ways even without the key. Whether or not the modifications will be useful is another question. Authenticating the encryption would make this attack impractical, but it requires overhead for the authentication data. (HMAC, etc.)

    AES-CBC isn't as vulnerable to known plaintext attacks as some other block cipher modes. In particular, AES-CTR encrypts a counter, not the data; the counter is then XORed with the plaintext to get the ciphertext, or XORed with the ciphertext to get the plaintext. Nintendo 3DS uses AES-CTR for a lot of things, including the FIRM partition. (This is why hardmod sighax installation, and previously hardmod downgrading, was possible.)
     
    zeldaism, TuxSH, DarthDub and 2 others like this.
  9. Billy Acuña

    Billy Acuña GBAtemp Addict

    Member
    2,246
    1,337
    Oct 10, 2015
    Mexico
    For a moment I did think we could fool the WFS :'v
     
  10. EyeKey
    OP

    EyeKey GBAtemp Regular

    Member
    196
    428
    Feb 10, 2017
    Israel
    Yeah, HMAC would solve it, and it won't add any overhead because they already have hashes for ALL the data.
    But what you described wasn't the issue here, in this case you don't change the plaintext that you know, you CAN'T change that plaintext because there is an hash on it in another location. Because it is CBC and there hashes everywhere you can't manipulate the encrypted data in this filesystem at all.
    The type of attack here is using files as encryption service, and using it replace the whole data of other unauthenticated blocks (that contain the regular hash of themselves).
    I described a practical way (assuming you can choose content of files), to create a new valid filesystem (with data totally in your control).
    What he said doesn't change anything that I described. He described another type of attack (I took into account in all my explanations that it is CBC).
     
    Last edited by EyeKey, Aug 11, 2017
    zeldaism, peteruk and DarthDub like this.
  11. Glix

    Glix GBAtemp Regular

    Member
    101
    29
    Jan 11, 2016
    Could this work for save injection? We know what the saves look like, and we can easily use small drives (I still have a Disgo 64mb usb drive!) to keep the surface area small.
     
  12. Cyan

    Cyan GBATemp's lurking knight

    Global Moderator
    18,292
    8,763
    Oct 27, 2002
    France
    Engine room, learning
    That's great to understand all this.
    Cryptography is a thing I want to learn, though I always hit some walls. I'm missing some basic knowledge, I should find a book to learn from the beginning.
     
    peteruk likes this.
  13. wiiupoo

    wiiupoo Member

    Newcomer
    19
    7
    Jul 25, 2016
    United States
    It's not terribly complicated if you work through a small example by hand (backwards & forwards). You don't need a book, a single page will suffice.

    Its just a combination of bitwise operations (mainly XOR), bit substitutions, and bit shifting.

    Lets take a look at the XOR operation, its the same as an OR bool comparison but if both inputs are true/1 then returns false/0 instead of 1.

    0 XOR 0 = 0
    0 XOR 1 = 1
    1 XOR 0 = 1
    1 XOR 1 = 0

    Whats unique about this, compared to OR, is that it is reversible!

    Important: ^ symbol = XOR operation (do not confuse with mathematical exponent operation)

    Going forward (Plaintext ^ Key) = Ciphertext:
    0110 PLAINTEXT
    1010 KEY
    -----------
    1100 CIPERTEXT

    Going backward (Cipertext ^ Key) = Plaintext

    1100 CIPERTEXT
    1010 KEY
    -----------
    0110 PLAINTEXT


    That example wasn't AES, but rather it's a portion of what is happening during AES encryption.

    You can skip reading the mathamatical proofs and manually workout some examples by hand, and you will have a solid understanding on what is actually going on. Without the diving into the proof deepend it actually is really simple.



    ⊕ also means XOR

    If you successfully encrypt/decrypt a single "block" then you basically performed AES-ESB.
    Now AES-CBC, is the same but it has 1 additional step. It uses the previous blocks cipertext as an additional XOR to scramble raw data.

    This scramble many advantage.
    A major one is since without this additonal XOR, if you figured out a plaintext/ciphertext pair, then if it ever repeats, you can identify it in the raw data. Now if each block is XOR'd from the previous block, this repeating pattern attack is no longer possible.
    When performing this additional XOR per block, the XOR input is known as an IV (initialization vector).

    Either way its not too complicated to perform. Most words you will encounter online were covered in this post. While its a simple formula it is VERY effective shutting down many modes of cryptographic attack leaving only bruteforce.
    ---

    On topic, Eyekey I got a little lost following your symbols in my head.
    I will work it out on paper over this weekend to see if its possible.

    Even so, I doubt we will have such block specific access on non exploited consoles (since we have to target block0).
     
    Last edited by wiiupoo, Aug 12, 2017