6 ms·

The 3DS Cryptosystem

120 points by yifanlu 11y ago

bostik 11y ago
That was an amusing read. The big takeaways are even deliciously quotable: The irony is that the feature designed to bring more security was the one that completely broke it. Too much complexity: having lots of blocks that say “AES” and “RSA” in your plan might impress the boss, but it just adds to the attack surface. Always go with the simplest plan that secures against your threat model. Security is hard to get right, and retrofitting security features into existing systems is ripe with very subtle traps. Add backwards compatibility into the mix and you've probably created a fragile Frankenstein.
- lazaroclapp 11y ago
  A fact that needs to be remembered when people ask for centralized key escrows and gratuitous backdoors in encryption systems. I know this gets mentioned twice a week now a days in HN, but it literally can´t be repeated enough.
- justifier 11y ago
  i suppose a handheld gaming device could be considered low consequence on the spectra of encryption use, which may simply answer my own question.. but being someone interested in factorisation i am baffled as to why anyone has or is using rsa my intended inference is that factoring numbers is deterministically achievable in sub polynomial time, and having your crypto rely on 'it's hard for me it must be impossible for you' reads so sophomoric
  - eximius 11y ago
    That is what all cryptography is based on? And I don't know what subpolynomial time nonsense you're talking about.
    - tptacek 11y ago
      If you're going to be rude, at least be correct. All cryptography is not in fact based on factoring; in fact, most public-key crypto isn't.
      - eximius 11y ago
        I wasn't referring to factoring. I quite like lattice based and ECC systems. I was referring to 'if it's hard for me it must be hard for you'. ALL cryptography is based off of that assumption. edit: I can't seem to reply to you again, so I'll edit. This is all a big miscommunication. I was more confused than hostile, though I recognize how it came off poorly. I genuinely thought he had some fundamental understandings due to the combination of things he said. I was mistaken and my response came off poorly.
        tptacek 11y ago
        That's a reading of the original comment so uncharitable as to seem tendentious. The commenter was specific about factoring; they were not calling into question the entire idea of a trapdoor function.
    - justifier 11y ago
      > subpolynomial time nonsense what exactly do you mean by this?
      - tptacek 11y ago
        The original poster probably meant to write "sub-exponential". The commenter to whom you're responding may or may not have known what the correct term was; we'll never know, because they chose snarky incivility instead of correction.
        justifier 11y ago
        i am the original poster :p and the 'sub' was misplaced, i actually asked instead of editing the original in case this was the reason i was called out so i could explain my typo for clarification the original should simply read 'polynomial time'
  - tptacek 11y ago
    The 3DS is higher stakes than virtually any other cryptosystem. Nintendo spends billions bringing it to market. Game consoles live or die based on third party developer support, and one of the important promises console developers make to entice developers to their platforms is that they will carefully steward those developers IP. What's more interesting to me is that the 3DS system is nonrenewable. As the author of this post correctly points out, all DRM systems inevitably fall, but they accomplish their commercial purpose as long as that fall happens far enough into the future that the developers make their money. Smart systems trying to employ DRM this way build, from the beginning, mechanisms to refresh and re-complicate their DRM systems on a title-by-title basis. I actually agree with you "in the large" about RSA (factoring doesn't seem like a hard enough problem anymore), but in the particulars, nobody is breaking RSA-2048 any time soon. Unlike strong curves, though, it seems plausible that RSA-2048 (and beyond) could fall before quantum computing.
  - yifanlu 11y ago
    First, the 3DS mostly uses RSA for code signing, something I didn't really touch on since there's no serious mistakes there. Second, while RSA does not fair well against quantum attacks, as of today, there is still no way of factoring a 2048 bit key that won't take you at least (being generous) hundreds of years (provided no quantum computers). So if you have proof that it's (today) achievable in polynomial time, please email me ;) But turning the question around, what do you think we should do to achieve asymmetric encryption? If you don't want it to break with Shor, then RSA and ECDSA are off the table. If you want small message size, you can't use Lamport.
    - justifier 11y ago
      if i had that proof an email would be unnecessary, you'd already know :p to address your question i'll say this, crypto is only interesting to me in securing my own work and because my interests are in number theory that, due to rsa popularity, would incidentally affect crypto i lack an intimate familiarity with the optimisation requirements of rolling production crypto, meaning i can comfortably ignore any message size restraints for my personal uses instead of implying i know how crypto should be enacted.. with my current knowledge and interest i would be wholly unable to deduce as you did in your article.. i was simply stating that i am interested in factoring large integers and i wonder why anyone thinks open problems in number theory are a sound means of crypto superb write up by the way
      - yifanlu 11y ago
        > i wonder why anyone thinks open problems in number theory are a sound means of crypto The short answer is that the numbers are so large that with current state of the art means (which I'm sure you know a lot about), factoring a 2048 bit number takes around 1000 years and 4096 bit keys takes about 2^32 times more years. Even if computers get faster every 10 years, you can see that it won't improve much. That's why we use number factoring for crypto; because it takes so long to break. However, as you've pointed out, since the problems are open, the calculations are meaningless. And of course all this analysis goes out the window with quantum computers. But the unfortunate truth (the "biggest embarrassment of computer science" as Dan Boneh calls it) is that we don't actually have any proof that security exists. All crypto is built on open problems. So better choose open problems that's been open for a long time.
SXX 11y ago
For anyone interested there is PS3 security explained and it's one more proof that complexity don't make system more secure: http://www.psdevwiki.com/ps3/Boot_Order#Chain_of_trust_Diagram http://www.psdevwiki.com/ps3/Boot_Order#Chain_of_trust_Diagr... http://www.psdevwiki.com/ps3/Keys http://www.psdevwiki.com/ps3/Keys
anon4 11y ago
Still, it held off for 4 years. That's pretty much the usual lifetime of a console generation, so I'd say the system was a success.
- Macha 11y ago
  It held off for 4 years before completely irreparably being broken. Many smaller breaks happened in that 4 years.
- kanetw 11y ago
  It was broken much, much earlier. At first you required an external device (special cartridge) or hardware mods, but there was a software exploit via the web browser for over a year now.
  - kevingadd 11y ago
    In addition to being broken earlier, it's been trivial for even a casual user to pick up the exploits and use them to run arbitrary software on the device. There's a long-running website out there you can load in the 3DS web browser to exploit your device with a single click.
- yifanlu 11y ago
  Well the first break that brought piracy happened about two years after launch. Also, the Vita, which launched around the same time is sill unhacked pretty much. It's a shame that there's not as much good games on there for it to be a commerical success. In fact the Vita does so many things right that the 3ds fails at (security wise).
wizzard0 11y ago
Another illustration of the classic thesis "security should be built from the ground up and can't be added later". Also shows the importance of minimizing the attack surface. Would love to hear some inside stories about discussions that ultimately led to these implementation decisions.
tptacek 11y ago
https://www.thoughtcrime.org/blog/the-cryptographic-doom-principle/ https://www.thoughtcrime.org/blog/the-cryptographic-doom-pri...
- cmrx64 11y ago
  I was hoping I'd find this link here. It never fails to deliver.
  - tptacek 11y ago
    You could see it in the very first diagram, with "AES-CTR" and no other blocks. And, sure enough... At this point, the term "CTR" has become a design smell.
    - yifanlu 11y ago
      As a simplification, I did not draw any of the blocks contributing to code signing. RSA is used everywhere to ensure that the code is signed. If you consider the signature as the MAC, it does "Authenticate Then Encrypt" (the signature is over the NCCH or FIRM header. The header contains hash + size of each section.)
      - tptacek 11y ago
        Help me understand a bit more about how a bogus key was able to generate a gibberish text segment that code could successfully return into if all program text was protected by RSA signatures. I may have misread the article.
        yifanlu 11y ago
        So we have FIRM, the main firmware image. It has three segments: 1) main ARM11 kernel modules, 2) ARM11 kernel, 3) ARM9 kernel/ARM9 process. The FIRM header has a SHA256 hash over all the segments and the size of all segments. The FIRM header also has a RSA2048 signature over the header. Then everything (sig + header + FIRM) is encrypted with AES-CTR and placed on the NAND. On system start, the whole chunk is decrypted, the signature is verified, and everything works as expected. Until in the New 3DS, they decide to also additionally encrypt segment 3 (the ARM9 stuff) with a separate key on the NAND. That's what led to the whole mess. So I guess their mistaken assumption was that since FIRM was signed, the encrypted ARM9 section was protected. However, they didn't take account of the fact that the key to decrypt it can be corrupted. It's a bit subtle.
userbinator 11y ago
Finally, I will summarize the findings and provide a few tips to fellow engineers in hopes that these kinds of mistakes will not be made again. On the other hand, those of us who like to actually own our hardware very much hope that these mistakes do happen again. :-)
- venomsnake 11y ago
  And I would prefer a legal solution to that. Cryptography is great when you control the keys. Do not allow restricted devices on the mass market if the legal owner is unable to override the restrictions.
  - andrepd 11y ago
    Why should restricted devices be forbidden? The device is on the market, you know beforehand it's restrictions, and you are free to buy it or not.
    - venomsnake 11y ago
      Because the feudal model of today must be destroyed since i consider it harmful.
      - andrepd 11y ago
        Calling a voluntary consumer purchase a "feudal model" is really stretching it.
Jasper_ 11y ago
A funny thing about the key generator. There was originally a project within the community to raise the funds to do a successful decap of the AES engine and key generator. They successfully raised the $2000 before the person claiming to do a decap (Jl12) stole all the money and disappeared off the face of the earth. http://web.archive.org/web/20121227085042/http://3dbrew.org/wiki/Fundraiser http://web.archive.org/web/20121227085042/http://3dbrew.org/... http://web.archive.org/web/20140209211220/http://3dbrew.org/wiki/Fundraiser http://web.archive.org/web/20140209211220/http://3dbrew.org/...
- DanBC 11y ago
  Here's a thread about depackaging the CPU. https://news.ycombinator.com/item?id=7479582 https://news.ycombinator.com/item?id=7479582 http://gaasedelen.blogspot.co.uk/2014/03/depackaging-nintendo-3ds-cpu.html http://gaasedelen.blogspot.co.uk/2014/03/depackaging-nintend...
- AdmiralAsshat 11y ago
  All that goodwill pissed away for a paltry 2k? I mean, at least get into five figures if you're planning a heist like that.

120 points by yifanlu 11y ago

That was an amusing read. The big takeaways are even deliciously quotable: The irony is that the feature designed to bring more security was the one that completely broke it. Too much complexity: having lots of blocks that say “AES” and “RSA” in your plan might impress the boss, but it just adds to the attack surface. Always go with the simplest plan that secures against your threat model. Security is hard to get right, and retrofitting security features into existing systems is ripe with very subtle traps. Add backwards compatibility into the mix and you've probably created a fragile Frankenstein.

lazaroclapp 11y ago
A fact that needs to be remembered when people ask for centralized key escrows and gratuitous backdoors in encryption systems. I know this gets mentioned twice a week now a days in HN, but it literally can´t be repeated enough.
justifier 11y ago
i suppose a handheld gaming device could be considered low consequence on the spectra of encryption use, which may simply answer my own question.. but being someone interested in factorisation i am baffled as to why anyone has or is using rsa my intended inference is that factoring numbers is deterministically achievable in sub polynomial time, and having your crypto rely on 'it's hard for me it must be impossible for you' reads so sophomoric
- eximius 11y ago
  That is what all cryptography is based on? And I don't know what subpolynomial time nonsense you're talking about.
  - tptacek 11y ago
    If you're going to be rude, at least be correct. All cryptography is not in fact based on factoring; in fact, most public-key crypto isn't.
    - eximius 11y ago
      I wasn't referring to factoring. I quite like lattice based and ECC systems. I was referring to 'if it's hard for me it must be hard for you'. ALL cryptography is based off of that assumption. edit: I can't seem to reply to you again, so I'll edit. This is all a big miscommunication. I was more confused than hostile, though I recognize how it came off poorly. I genuinely thought he had some fundamental understandings due to the combination of things he said. I was mistaken and my response came off poorly.
      - tptacek 11y ago
        That's a reading of the original comment so uncharitable as to seem tendentious. The commenter was specific about factoring; they were not calling into question the entire idea of a trapdoor function.
  - justifier 11y ago
    > subpolynomial time nonsense what exactly do you mean by this?
    - tptacek 11y ago
      The original poster probably meant to write "sub-exponential". The commenter to whom you're responding may or may not have known what the correct term was; we'll never know, because they chose snarky incivility instead of correction.
      - justifier 11y ago
        i am the original poster :p and the 'sub' was misplaced, i actually asked instead of editing the original in case this was the reason i was called out so i could explain my typo for clarification the original should simply read 'polynomial time'
- tptacek 11y ago
  The 3DS is higher stakes than virtually any other cryptosystem. Nintendo spends billions bringing it to market. Game consoles live or die based on third party developer support, and one of the important promises console developers make to entice developers to their platforms is that they will carefully steward those developers IP. What's more interesting to me is that the 3DS system is nonrenewable. As the author of this post correctly points out, all DRM systems inevitably fall, but they accomplish their commercial purpose as long as that fall happens far enough into the future that the developers make their money. Smart systems trying to employ DRM this way build, from the beginning, mechanisms to refresh and re-complicate their DRM systems on a title-by-title basis. I actually agree with you "in the large" about RSA (factoring doesn't seem like a hard enough problem anymore), but in the particulars, nobody is breaking RSA-2048 any time soon. Unlike strong curves, though, it seems plausible that RSA-2048 (and beyond) could fall before quantum computing.
- yifanlu 11y ago
  First, the 3DS mostly uses RSA for code signing, something I didn't really touch on since there's no serious mistakes there. Second, while RSA does not fair well against quantum attacks, as of today, there is still no way of factoring a 2048 bit key that won't take you at least (being generous) hundreds of years (provided no quantum computers). So if you have proof that it's (today) achievable in polynomial time, please email me ;) But turning the question around, what do you think we should do to achieve asymmetric encryption? If you don't want it to break with Shor, then RSA and ECDSA are off the table. If you want small message size, you can't use Lamport.
  - justifier 11y ago
    if i had that proof an email would be unnecessary, you'd already know :p to address your question i'll say this, crypto is only interesting to me in securing my own work and because my interests are in number theory that, due to rsa popularity, would incidentally affect crypto i lack an intimate familiarity with the optimisation requirements of rolling production crypto, meaning i can comfortably ignore any message size restraints for my personal uses instead of implying i know how crypto should be enacted.. with my current knowledge and interest i would be wholly unable to deduce as you did in your article.. i was simply stating that i am interested in factoring large integers and i wonder why anyone thinks open problems in number theory are a sound means of crypto superb write up by the way
    - yifanlu 11y ago
      > i wonder why anyone thinks open problems in number theory are a sound means of crypto The short answer is that the numbers are so large that with current state of the art means (which I'm sure you know a lot about), factoring a 2048 bit number takes around 1000 years and 4096 bit keys takes about 2^32 times more years. Even if computers get faster every 10 years, you can see that it won't improve much. That's why we use number factoring for crypto; because it takes so long to break. However, as you've pointed out, since the problems are open, the calculations are meaningless. And of course all this analysis goes out the window with quantum computers. But the unfortunate truth (the "biggest embarrassment of computer science" as Dan Boneh calls it) is that we don't actually have any proof that security exists. All crypto is built on open problems. So better choose open problems that's been open for a long time.

SXX 11y ago

For anyone interested there is PS3 security explained and it's one more proof that complexity don't make system more secure: http://www.psdevwiki.com/ps3/Boot_Order#Chain_of_trust_Diagram http://www.psdevwiki.com/ps3/Boot_Order#Chain_of_trust_Diagr... http://www.psdevwiki.com/ps3/Keys http://www.psdevwiki.com/ps3/Keys

anon4 11y ago

Still, it held off for 4 years. That's pretty much the usual lifetime of a console generation, so I'd say the system was a success.

Macha 11y ago
It held off for 4 years before completely irreparably being broken. Many smaller breaks happened in that 4 years.
kanetw 11y ago
It was broken much, much earlier. At first you required an external device (special cartridge) or hardware mods, but there was a software exploit via the web browser for over a year now.
- kevingadd 11y ago
  In addition to being broken earlier, it's been trivial for even a casual user to pick up the exploits and use them to run arbitrary software on the device. There's a long-running website out there you can load in the 3DS web browser to exploit your device with a single click.
yifanlu 11y ago
Well the first break that brought piracy happened about two years after launch. Also, the Vita, which launched around the same time is sill unhacked pretty much. It's a shame that there's not as much good games on there for it to be a commerical success. In fact the Vita does so many things right that the 3ds fails at (security wise).

wizzard0 11y ago

Another illustration of the classic thesis "security should be built from the ground up and can't be added later". Also shows the importance of minimizing the attack surface. Would love to hear some inside stories about discussions that ultimately led to these implementation decisions.

tptacek 11y ago

https://www.thoughtcrime.org/blog/the-cryptographic-doom-principle/ https://www.thoughtcrime.org/blog/the-cryptographic-doom-pri...

cmrx64 11y ago
I was hoping I'd find this link here. It never fails to deliver.
- tptacek 11y ago
  You could see it in the very first diagram, with "AES-CTR" and no other blocks. And, sure enough... At this point, the term "CTR" has become a design smell.
  - yifanlu 11y ago
    As a simplification, I did not draw any of the blocks contributing to code signing. RSA is used everywhere to ensure that the code is signed. If you consider the signature as the MAC, it does "Authenticate Then Encrypt" (the signature is over the NCCH or FIRM header. The header contains hash + size of each section.)
    - tptacek 11y ago
      Help me understand a bit more about how a bogus key was able to generate a gibberish text segment that code could successfully return into if all program text was protected by RSA signatures. I may have misread the article.
      - yifanlu 11y ago
        So we have FIRM, the main firmware image. It has three segments: 1) main ARM11 kernel modules, 2) ARM11 kernel, 3) ARM9 kernel/ARM9 process. The FIRM header has a SHA256 hash over all the segments and the size of all segments. The FIRM header also has a RSA2048 signature over the header. Then everything (sig + header + FIRM) is encrypted with AES-CTR and placed on the NAND. On system start, the whole chunk is decrypted, the signature is verified, and everything works as expected. Until in the New 3DS, they decide to also additionally encrypt segment 3 (the ARM9 stuff) with a separate key on the NAND. That's what led to the whole mess. So I guess their mistaken assumption was that since FIRM was signed, the encrypted ARM9 section was protected. However, they didn't take account of the fact that the key to decrypt it can be corrupted. It's a bit subtle.

userbinator 11y ago

Finally, I will summarize the findings and provide a few tips to fellow engineers in hopes that these kinds of mistakes will not be made again. On the other hand, those of us who like to actually own our hardware very much hope that these mistakes do happen again. :-)

venomsnake 11y ago
And I would prefer a legal solution to that. Cryptography is great when you control the keys. Do not allow restricted devices on the mass market if the legal owner is unable to override the restrictions.
- andrepd 11y ago
  Why should restricted devices be forbidden? The device is on the market, you know beforehand it's restrictions, and you are free to buy it or not.
  - venomsnake 11y ago
    Because the feudal model of today must be destroyed since i consider it harmful.
    - andrepd 11y ago
      Calling a voluntary consumer purchase a "feudal model" is really stretching it.

Jasper_ 11y ago

A funny thing about the key generator. There was originally a project within the community to raise the funds to do a successful decap of the AES engine and key generator. They successfully raised the $2000 before the person claiming to do a decap (Jl12) stole all the money and disappeared off the face of the earth. http://web.archive.org/web/20121227085042/http://3dbrew.org/wiki/Fundraiser http://web.archive.org/web/20121227085042/http://3dbrew.org/... http://web.archive.org/web/20140209211220/http://3dbrew.org/wiki/Fundraiser http://web.archive.org/web/20140209211220/http://3dbrew.org/...

DanBC 11y ago
Here's a thread about depackaging the CPU. https://news.ycombinator.com/item?id=7479582 https://news.ycombinator.com/item?id=7479582 http://gaasedelen.blogspot.co.uk/2014/03/depackaging-nintendo-3ds-cpu.html http://gaasedelen.blogspot.co.uk/2014/03/depackaging-nintend...
AdmiralAsshat 11y ago
All that goodwill pissed away for a paltry 2k? I mean, at least get into five figures if you're planning a heist like that.