Nintendo Switch RSA-PKCS#1 Public Key Recovery
This is a short writeup of a fun (but ultimately pretty useless) attack I implemented on the Nintendo Switch a few months ago resulting in the recovery of some otherwise unobtainable RSA public keys. Since public keys aren't private keys, this is pretty useless, apart from letting us validate some signatures on PC. Even so, the attack is a pretty cool one, so I thought I'd write it up.
Every Switch gamecart has a unique certificate (called its "CERT"), storing an RSA signature followed by some kind of unknown but unique encrypted data. I was trying to reverse how these certificates work, and the obvious first step was to try to see how they were validated. However, when I tried looking through the FileSystem (FS) module, which should be responsible for validating these certificates, I found no references to the format at all. The "CERT" magic number was nowhere to be seen, and I couldn't find an RSA modulus that validated the signatures I had. This was interesting, but I still thought that the validation had to be done by the OS, so I started looking for other validation code for the gamecard format...and found none at all.
However, I did make an interesting discovery -- FS was loading a blob into a static buffer that Nintendo kindly left in symbols for: "nn::gc::detail::EmbeddedDataHolder::g_FwWriterBuffer".
Some background context: the Nintendo Switch has a special piece of hardware for interfacing with game cartridges (the "gamecard controller"); this hardware is an application-specific integrated circuit (ASIC), running a custom firmware written by Nintendo. The ASIC is responsible for all interactions between the OS and gamecarts -- FS makes requests to the ASIC, which reads data from the inserted gamecard and delivers it back to the system. Apparently, FS was responsible for loading some kind of firmware onto the ASIC.
Cursory inspection of the blob proved somewhat uninteresting -- at first glance, it looked like an 0x100 RSA signature, an 0x80 plaintext header (with a "LAFW" magic number, and "IDIDIDIDIDIDIDID" present at +0x30), followed by a large amount of encrypted data. Interestingly, there was no code anywhere in FS to validate the signature on this blob, and no code to decrypt it.
This implied, though, that Nintendo's ASIC was more complex than I thought -- it isn't just a simple state machine! It runs a firmware, and it knows how to verify and decrypt that firmware! In addition, I could see from reversing FS that communications between FS and the ASIC used RSA-OAEP with a console unique keypair for encryption in addition to AES-CBC; I could thus be pretty sure the ASIC was capable of complex logic. The keys used to talk to the ASIC are stored encrypted in a blob using keydata available only to TrustZone; these keys have changed only once, in system update 4.0.0 -- this was also the only system update to modify the LAFW firmware blob. To this day, I haven't actually made any additional progress figuring out how the ASIC works -- I have no idea what changed in the encrypted firmware blob between 3.0.2 and 4.0.0, and no idea why they changed the encryption keys FS uses to talk to the ASIC.
All that said, though, I still wanted to be able to validate gamecard-related formats; this seemed tough, though, because I had no way of validating RSA signatures without the accompanying public key. Luckily, though, I was aware of an attack that I thought I'd never get the chance to try in practice that would let me recover the public keys!
Most of the RSA signatures present on the console use a signature padding scheme called "Probabilistic Signature Scheme" (PSS). However, back on the 3DS (and for older consoles), Nintendo used a different scheme called PKCS#1! It stood to reason that Nintendo probably designed the ASIC early on when making the Switch, and so it might use this older padding scheme. FS's code seemed to corroborate this -- there was some "dead" code related to verifying signatures with this scheme that nothing seemed to use...maybe it was a left over?
RSA signature validation has the following parameters: S (the signature), E (the public exponent), N (the public modulus), as well as data to verify. Normally, we view a verifier as being in possession of S, E, N, and the data. In our case, though, we have S and the data, and want to find some way to calculate E and N. E, at least, is easy -- Nintendo consistently uses 65537 (0x10001) as its public exponent. This means our task simplifies to just trying to find some way to find N.
One of the interesting qualities about the PKCS#1 padding scheme is that it is deterministic: that is, for a given message, there is exactly one correct signature S that exponentiates to message exactly one correct message M (with S ^ E % N == M) that validates the data provided. But this means that given the data to verify, we can calculate M! It turns out this is all we need to find N!
Staring at the equation S ^ E % N == M, we can rewrite as follows: (S ^ E) - M % N == 0. In other words, N is a divisor of X = ((S ^ E) - M). Now, consider the case where we have two signatures, and their associated data -- S1, and S2. Given their associated data, we can calculate their associated messages, M1 and M2. From earlier, we know that N is a divisor of X1 = ((S1 ^ E) - M1), and N is also a divisor of X2 = ((S2 ^ E) - M2). This means that N is a common divisor of X1 and X2, and while factoring large numbers is a very hard problem, finding the Greatest Common Divisor is extremely easy -- there are well-known, efficient algorithms to do so. Thus, in theory, given two signatures S1 and S2, we can calculate X1 and X2, and from there find GCD(X1, X2) == N and recover the public key!
This worked like a charm, in practice. From my dumped copies of The Binding of Isaac and Breath of the Wild, I had two gamecard header signatures and two cert signatures, and thus was able to recover both validating public keys. In addition, thanks to 4.0.0 updating the gamecard firmware, I had two signatures for the LAFW blobs (even though I didn't know what data was signed). I tried a simple brute force attack checking every possible length of data for the blobs, though, and this succeeded! It turns out that the ASIC's firmware blobs' signatures are over the entire rest of the blob (the plaintext header and the encrypted body), and so that public key was recoverable too.
The public keys are reproduced here, for posterity:
Gamecart HEAD Public Modulus: 98C726B60D0A50A739210AE32FE43E2E5BA28675AA5CEE34F1A33A7EBD904EF78DFA17AA6BC6366D4C9A6D572F80A2BC384DDA99A1D8C3E2997936719020259D4D11B82E636B5AFA1E9C04D1C5F09CB10FB8C17BBFE8B0D22B4701226B23C9D0BCEB756E417D4C26A47321B4F014E5D98DB364EEA8FA841BB8B87C886BEFCC9704049A672FDFEC0DB25FB5B2BDB54BDE0E88A3BAD1B4E09181A784EB77858BEFA5E327B2F2822B29F1752DCECCAE9B8DED5CF18EDB9AD7AF421452CDE3C5DDCE081217D07F1AAA1F7DE09354C8BC738ACBAD6E93E219726BD345F8733D2B6A55D23A8BB08A42E33DF19223422EBACC9C9AC1DD62869C2EE12D6F626751080ECF Gamecart CERT Public Modulus: CDF32CB0F5147834E502D0296AA5FD976AE0B0BBB03B1A80B7D758927984C036B15523D8A5609126481A804AEA00982AEC521772924DF542A78A6F7FD248518EDFCBBF77F618BDE500D9708CEF57B296D03683889CC5FBA03381A21223C6C7860A98574D2EB5AE64E46FC2C5AC6A1DDBA5AF1222AB1F51C80E0DC9F503E8D2FC84622655A4C3E2A898056723FDA546407851093D9174D6D054230DA0FB07D0AA9D504E2B269A14E56C73662418A1939C2A4040056BF145DF228B4061A4110603A55384C012E1889D5555074088018CABA2FDFD194825AB5959286368691B99738DAB5AFA71601B12E79970F1992A50188B6B6190E27E8B90D4D5C0CB7C0806D9 Gamecart LAFW Public Modulus: D22D7401FBCF35216CA400E436DEB004230AA9AB6A796920C95EC795CBE611ADC1B795AC196EC7AE512BB6799397A99F8A845FF75FC2A7FAC4E238B92A58B207A8519480F2C301E47DCA969DBBA11AEDB7657BC4736D961F2C87290E7CFF9278E6F63EBEA5AB2E43D67D8CC7FB44EB817912EF27DD13496E2BEE4A33F28D71807FE66521BA8ADB663F2FD71C7D9C623BB6CEED95042E1E0E914ED9C9C497D31E9A1B541C9A8F216870BD4AD5D43F9F11EE545D43956276C7A5742E2F6DD39C804E4AE385E83C94211DC4C7204D9FE99801B8AEC07AAE4C6C52869C4699791EA47ECE7F5851873E6D3D9CC4E97A00E43525641CB5F7D97C869474D155DC6B1AE3
As mentioned up above, this attack is pretty much entirely useless: it allows one to verify Nintendo's signatures for gamecart images (XCI), CERTs, and gamecart controller firmware (LAFW), and that's pretty much it.
I do think it's a great demonstration of why one should avoid using a deterministic padding scheme (it can leak information about the keys involved!), though, and makes a great case for non-deterministic padding schemes like RSA-PSS :)