Homebrew AES key scrambler

[Suiginou]

The AES key scrambler is annoying, I think we all agree on that. It's the reason we need a physical 3DS to decrypt titlekeys or do NCCH crypto. For other things, we need a physical 3DS not only because the key scrambler is unknown but also the keys are set by the bootroms, which we simply don't have, except maybe Yellows8.

Terminology: The scrambler function is used over keyX and keyY to yield a normalkey. The normalkey is then used to perform AES operations.

What we have

@Reisyukaku released a pastebin (username is the same on pastebin as on here) with a link to a Google Docs spreadsheet that contains the constant C and a list of known/unknown keyX/keyY.

Base formula: normalkey = (((keyX ROL 2) XOR keyY) + C) ROL 87

C is kept secret for whatever reason. You're on your own to find it. I have no idea why people are making a big deal about this, but whatever. I'll post it here when it lands on 3dbrew.

Some pointers:
In N3DS NATIVE_FIRMs 8.1 and 9.0, a normalkey for slot 0x39 can be found for NFC crypto. In N3DS and O3DS NATIVE_FIRMs, the key for 0x39 instead was changed to the corresponding keyY. This is embarrassing, Nintendo.

You have an easier time a physical N3DS to do the decryption of the arm9bins for 8.1/9.0/9.3+ on N3DS NATIVE_FIRM, however. However, the keys for 8.1-9.0 NATIVE_FIRM decryption have been leaked, so you can do it on an O3DS as well. Furthermore, there is a fully decrypted (arm9bin included) NATIVE_FIRM image floating around the Internet.

plutoo detailed in his part of the 32C3 talk (starts around 1h19min58s in) that (x <<< 2) ^ y0 < (x <<< 2) ^ y1, where y0 == y1 except for one bit and y0 shares that bit with keyX. This works because xor yields 0 for an identical bit.

@Myria elaborated on how their team found keyX and C.

@windwakr published a tool that aids in finding C as well.

For verification of your progress:

SHA-1(keyX_{0x39}) = cd40801bb34b8a9fe5bd58ad60471f6b88764c57
SHA-1(keyY_{0x39}) = 801fc53b2273939c6a193f3669e07ba990c6b57d
SHA-1(normalkey(keyX_{0x39}, keyY_{0x39})) = d659322804415d53ce0c7f6699e3e2d6c8777056
SHA-1(C) = 90ee1ff29fd7032176ad6d2222fa01c84ba6bf88

What can be done with it

0x16: arm9loader keyslot, used starting with 9.5. For firmware version 9.5, keyX and keyY are known. This is not yet the case for 9.6 and later (and as far as I know they use the OTP region somehow), however.
0x25: The 7.x keyslot. We have the keyX readily available on the Internet, the keyY is just taken from the signature of the NCCH to decrypt.
0x39: All keys known for Amiibo NFC key generation. For download play traffic, the keyX is the same, but the keyY differs. The DLP keyY is stored in NATIVE_FIRM somewhere.

 

[Duo8]

0x25: The 7.x keyslot. We have the keyX readily available on the Internet, the keyY is just taken from the signature of the NCCH to decrypt. The normalkey is unknown.

If the normal key is the result of keyx and keyy is it not possible to just run them through the scrambler then get the result?
Is it known whether dev units have the same keyscrambler or not?
What if the keyscrambler was built to prevent exactly this?

One of those times one'd wish the decapping wasn't a scam

 

[Suiginou]

If the normal key is the result of keyx and keyy is it not possible to just run them through the scrambler then get the result?
What if the keyscrambler was built to prevent exactly this?

See OP:

Reading the AES registers out isn't possible, inconveniently.

You can only write, but not read normalkeys. There's a slight weakness regarding that but only for the DSi keyslots (section "DSi / 3DS-TWL key-generator" on 3dbrew/3DS_System_Flaws#Hardware), so it's useless in this scenario.

Is it known whether dev units have the same keyscrambler or not?

As far as I know, that's unknown. If retail NCCHs/CIAs run without modification, it's likely they have the same key scrambler.

 

[Duo8]

As far as I know, that's unknown. If retail NCCHs/CIAs run without modification, it's likely they have the same key scrambler.

But dev units don't run retail content. Either the keys or the scrambler or both.
Also, again, is it possible that it was built to prevent guessing?

 

[Suiginou]

But dev units don't run retail content. Either the keys or the scrambler or both.

And pretty much no way of finding that out unless we have a way to dump bootroms.

Also, again, is it possible that it was built to prevent guessing?

Probably. Maybe. Who knows, not like it makes much of a difference.

 

[windwakr]

It has been revealed today by plutoo, during their talk at 32c3 that the 3DS' AES keyscrambler is:

(((keyX ROL 2) XOR keyY) + SECRET) ROL 87

He revealed that there are 3DS AES normalkeys embedded somewhere in the Wii U for some of the keyslots in the 0x31-0x39 range. One of those is also embedded in the 8.1 3DS firmware(N3DS only?).

Using the normalkey and some messing around with different keyYs, you can work out the secret value.

 

[OctopusRift]

That's really cool guys. Actual progress... NOW GET ME A 9.6+ N3DS OTP DUMP.

 

[Bug_Checker_]

Spoiler

The AES key scrambler is annoying, I think we all agree on that. It's the reason we need a physical 3DS to decrypt titlekeys or do 7.x crypto. For other things, we need a physical 3DS not only because the key scrambler is unknown but also the keys are set by the bootroms, which we simply don't have, except maybe Yellows8.

We don't know the 3DS key scrambler, however. It's not the same as the DSi key scrambler, either (normalkey = ((keyX ^ keyY) + 0xFFFEFB4E295902582A680F5F1A4F3E79) ROL 42, as documented on http://problemkaputt.de/gbatek.htm#dsiaesioports).

Terminology: The scrambler function is used over keyX and keyY to yield a normalkey. The normalkey is then used to perform AES operations.

Reading the AES registers out isn't possible, inconveniently. However, reversing the AES key scrambler might be possible if we have at least three keys: a keyX, a keyY and the resulting normalkey.

There's a function called AesKeyScrambler in makerom, but this does not seem to match the actual hardware key scrambler.

This is a list of key slots with sources for keyX/keyY/normalkey that could possibly be used. So far, I've never found a complete set of keyX/keyY/normalkey, however. If someone can come up with a method to find such a tuple, that would help.

0x25: The 7.x keyslot. We have the keyX readily available on the Internet, the keyY is just taken from the signature of the NCCH to decrypt. The normalkey is unknown.
0x3D: Dev unit common key: The dev unit common keyYs are readily available on the Internet, but it's unclear whether it's set as a normalkey or derived from the retail common keyYs on dev units; there is no dev CDN it seems and tickets from dev units are also hard to come across. The keyX is missing as well.

It may be easier for people searching to look for :

FFFEFB4E295902582A680F5F1A4F3E79h

http://ngemu.com/threads/dsi-aes-unit-fully-reversed.169857/

 

[KazoWAR]

I am a little confused. He gave us the formula for the key scrambler and tells us how to brute force it to solve for KeyX and C, but only tells us where to find one NKey and KeyY pair, in the 2 3ds firmwares. but his example showed using 2 pairs of keys to bruteforce it. he also said normal keys are in the wiiu but said since the one pair is in the 2 N3DS fimwares, the wii u is no longer needed.

 

[windwakr]

I am a little confused. He gave us the formula for the key scrambler and tells us how to brute force it to solve for KeyX and C, but only tells us where to find one NKey and KeyY pair, in the 2 3ds firmwares. but his example showed using 2 pairs of keys to bruteforce it. he also said normal keys are in the wiiu but said since the one pair is in the 2 N3DS fimwares, the wii u is no longer needed.

Like he said in the presentation, a small change in keyY is a small change in the normalkey. So, you can change one bit in the keyY and bruteforce the new normalkey from the old one, by flipping a bit or two.

 

[KazoWAR]

Like he said in the presentation, a small change in keyY is a small change in the normalkey. So, you can change one bit in the keyY and bruteforce the new normalkey from the old one, by flipping a bit or two.

but how do we see this second normal key? the whole point of the keyscrabmler and hardware AES was to hide the normal keys.

keyY goes in, XORPAD comes out

 

[windwakr]

but how do we see this second normal key? the whole point of the keyscrabmler and hardware AES was to hide the normal keys.

keyY goes in, XORPAD comes out

After changing a bit in the keyY, encrypt something(like all 00s) and save the output. The randomly flip a bit or two in the normalkey you have until encrypting using that with the same input gives the same output as the 3DS.

 

[KazoWAR]

After changing a bit in the keyY, encrypt something(like all 00s) and save the output. The randomly flip a bit or two in the normalkey you have until encrypting using that with the same input gives the same output as the 3DS.

Oh! I get it now.

 

[Suiginou]

Clearly, plutooo made some progress. To solve the equataion normalkey = (((keyX <<< 2) ^ keyY) + C) <<< 87, we still need a triplet, but he gave us pretty much a good framework.

The problem is now finding a normalkey with a keyX or a keyY.

 

[KazoWAR]

Clearly, plutooo made some progress. To solve the equataion normalkey = (((keyX <<< 42) ^ keyY) + C) <<< 87, we still need a triplet, but he gave us pretty much a good framework.

The problem is now finding a normalkey with a keyX or a keyY.

He said in the talk, nintendo in a rush to support amiibo, used a normal key in the NFC crypto for Firmware 8.1, but later fixed it by changing it to a keyY in 9.3. so you can get the key pair from those 2 firmwares.

also its (((keyX <<< 2) ^ keyY) + C) <<< 87

I have a pretty good understanding of what to do math wise. I just dont have the key pair and the means to generate the 128 xorpads.

 

[Suiginou]

He said in the talk, nintendo in a rush to support amiibo, used a normal key in the NFC crypto for Firmware 8.1, but later fixed it by changing it to a keyY in 9.3. so you can get the key pair from those 2 firmwares.

You're aware the ARM9 NATIVE_FIRM part is like 558 kByte of code mixed with data and finding the key in there is a needle in a haystack.

 

[Duo8]

You're aware the ARM9 NATIVE_FIRM part is like 558 kByte of code mixed with data and finding the key in there is a needle in a haystack.

Unless they obfuscated it a disassembly should show.

 

[Suiginou]

Unless they obfuscated it a disassembly should show.

$ arm-none-eabi-objdump -b binary -m arm -D arm90.bin|wc -l
142684

I'm not sure how fast you can read disassemblies, but one hundred and forty-two thousand instructions mixed with data (plus a few redumps because objdump isn't clever enough to detect switches to Thumb mode) seems like a lot to sift through.

When I have time, I'll instead try:

1. Encrypt all-0 with keyslot 0x39 as-is. Save that result.
2. Read ARM9 binary for firmware 9.3. For each offset, read 16 bytes, set those as keyY and see if encrypting all-0 matches the result from before.
3. Read ARM9 binary for firmware 9.0. For each offset, read 16 bytes, set those as normalkey and see if encrypting all-0 matches the result from before.

EDIT: That plan seems to have failed with the step for the 9.3 keyY already.

 

[Xenon Hacks]

I still don't understand the whole 87 rotation equation bit or how the Wii U came into play

 

[Suiginou]

I still don't understand the whole 87 rotation equation bit or how the Wii U came into play

The 87 rotation was derived just by observing output when flipping bits in the keyY.

The Wii U didn't come into play at all in the end. Originally, the plan was to use the Wii U to obtain normalkeys to then derive a keyX from a keyY and normalkey to find the constant. Because the Wii U and the 3DS can communicate with each other and/or have to support the same features, such as decrypting Mii QR codes, but the Wii U doesn't use a key scrambler, the Wii U must hold the corresponding normalkey, whereas the 3DS may just derive the key from a set of keyX/keyY.