Getting the 0x31 normal key yourself

What you need

The following will be about understanding what we're doing. If your do not care and wish to just get the damn key, jump to Downloading the New 3DS recovery firmware if you follow the Old 3DS route, else jump to Dumping the keys with GodMode9.

The keyscrambler

The Nintendo 3DS contains an AES engine, handling all crypto on the system. This engine can hold keys securely, once written, they cannot be read back. This engine also contains a keyscrambler. It's a clever solution to update keys without allowing hackers to get the key from the update file. Basically, for each key slots, the software can send two keys, called keyX and keyY. The scrambler then mixes them up using an algorithm written in the hardware (so no dump possible) to generate what is called a normal key. This is the key used and there is no way of getting it without knowing the keyX, the keyY and the secret algorithm.

The algorithm

Luckily for us, the algorithm mixing keys is not very good at his job and the marvelous folks who were hacking the 3DS in those golden days managed to guess how it works and presented it back in 2015 at 32c3. Here is it : normalkey = (((keyX <<< 2) ^ keyY) + C) <<< 87.
That C is a secret constant written in hardware, so again, no dump possible. But let's rearrange the formula a bit and we get C = normalkey >>> 87 - ((keyX <<< 2) ^ keyY). So if we could get a triplet of keyX, keyY and normal key, we could extract the constant from it.

The secret constant

Again from the 32c3 presentation, plutoo teaches us that Nintendo likely rushed the New Nintendo 3DS release and accidentaly included the 0x39 normal key in the firmware 8.1, before replacing it with a keyY in 9.3! And what's even better: 3DS contains a copy of their firmware to boot in recovery mode and this copy is not up to date. Yup, the recovery firmware on 11.14 New 3DS STILL CONTAINS the 0x39 normal key! So we will need to dump the firmware for the keyY and the recovery firmware for the normal key.
Finally, to get the keyX, we need to get the bootrom of the ARM9 processor since the bootrom sets most keyX. I won't get into how this is made possible but it's once again a fantastic story I encourage you to read (more in the credits!). So let's add the ARM9 bootrom to our grocery list.

The 0x31 normal key

This is our final goal, the 0x31 normal key (this key technically is in the Wii U but I did not research nearly enough the Wii U to be bothered trying). This key is what the Nintendo 3DS ultimately uses when reading and generating Mii QR Codes (and many other things). As discussed in the keyscrambler part above, to get a normal key, we will need the 0x31 keyX and keyY. Fortunately, those are found respectively in the ARM9 bootrom and the console firmware, which we already need to find the keyscrambler secret constant.

Downloading the New 3DS recovery firmware

If you have a New 3DS model updated to 11.16.0, you can skip to the next part.

As discussed above, we need one key that is not available in the console you have in your hands. But it's inside a firmware we can easily download straight from Nintendo's servers! Just download this file and that file and place them on your SD card in SD:/gm9/out. It's encrypted but nothing GodMode9 can't handle in a few buttons presses.

Dumping the keys with GodMode9

Let's get our all those keys now. Open GodMode9 in boot9strap context and follow those instructions:

Getting the constant

Apply the following formula using your preffered method of dealing with very large numbers or use this tool I made and fill the Constant form.
normalkey_0x39 >>> 87 - ((keyX_0x39 <<< 2) ^ keyY_0x39)
SHA-256 of the secret constant : 05D6564396705F79890A12CD05DD914B0ADC01CCAA4D5158A90BB32553025997

Getting the 0x31 normal key

Finally, apply the following formula using your preffered method of dealing with very large numbers or use this tool I made and fill the Normal key form.
(((keyX_0x31 <<< 2) ^ keyY_0x31) + secret_constant) <<< 87
SHA-256 of the 0x31 normal key : A2E6468B41CFA903988D4BC89BE0C1CD8AB52A23A3E15361AA1C1ADCE6C9F953


Many thanks to the wonderful folks that made all of this possible! I'm sorry for not naming everyone here, especially after many years far from the scene but feel free to request additions and corrections at this email.