Homebrew SigHax Updates and Discussion Thread

[Selver]

We know, a priori, from derrek & co that their estimate for the time to brute force the sighax signature using 10 CPUs and all the optimizations they could think of was 6 months.

We also know, via calculations on how fast we can do modular exponentiations on PC, this equates to about 2^50 signatures to check, using PERFECT code on PC.
This equates to 300 million years, at your claimed rate of ~10000 signatures/day.

The specifics of why your math is wrong is you're assuming generating the signatures to check takes zero time -- it takes a LOT of exponentiations to generate any signatures that even MIGHT be valid. ~16 bits for the 00 02 prefix, and then way more for the ASN.1 structure, since you're not overflowing the first length tag -- many of those must be valid, too, and we don't know which ones.

So, no, bruteforcing sighax is not possible without the bootroms.
@Selver is wrong.

damn SciresM in my thread. But anyways, thank you for clearing this up, i have updated the OP.

Hi @SciresM ,

I'm not offended by being wrong. It's happened before, and will happen again.
Can you help me understand some things, and answer a couple related questions?

NOTE: my 10k / day number relates to number of boots of the 3DS that can be attempted, if relying on standard boot operations to detect success/failure; it's not related to the generation of potential SigHAX sectors to be tried. If this was a source of misunderstanding, please accept my apologies for not having made it more clear.

Based on your description of the need to perform the modular exponentiation, I am presuming you are talking about the need to forge an RSA signature so that the signature itself is acceptable. Obviously, if only able to generate 10k/day, this would be infeasible. But I'd like to drill down to see if we're talking about the same thing....

Can you help me understand which signature must be brute-forced, in order to test a specific corruption of the ASN.1 encoding of the length field?

I ask because, from what I understood, the signature at risk is the FIRM Header's own signature (offset 0x100, size 0x100). Thus, the attempts to check for SigHax would start with modification of *nothing* except that FIRM Header signature.

Of course, there are additional attacks that (due to failure with the ASN.1 decoding) might allow a full signing certificate to be generated, or greatly simplify creation of a hash collision (e.g., BERserk vulnerability, documented in depth by Intel in late 2014), either of which may be considered as resulting in the need for the modular exponentiation that you mention. Can you help me understand how this is not side-stepped by SigHAX, which causes the bootrom to pass the same pointer value to both memory pointers of a memcmp() operation?

Finally, I admit that none of the heuristics are guaranteed to be correct. At the same time, do you believe use of those heuristics would not improve the searching of the potential ASN.1 length value space? I'm interested in your response....

My thanks to you, for any help you provide correcting the understanding I presented.

 

[SciresM]

Hi @SciresM
I'm not offended by being wrong. It's happened before, and will happen again.

This is a super admirable attitude, and I really appreciate it. So: sure.

NOTE: my 10k / day number relates to number of boots of the 3DS that can be attempted, if relying on standard boot operations to detect success/failure; it's not related to the generation of potential SigHAX sectors to be tried. If this was a source of misunderstanding, please accept my apologies for not having made it more clear.

I understood what you meant, but as I'll explain in a bit, the number of testable sectors is inherently tied to the number that we can generate.

Based on your description of the need to perform the modular exponentiation, I am presuming you are talking about the need to forge an RSA signature so that the signature itself is acceptable. Obviously, if only able to generate 10k/day, this would be infeasible.

The problem is, indeed, tied to the fact that we can't generate viable sectors quickly.

Can you help me understand which signature must be brute-forced, in order to test a specific corruption of the ASN.1 encoding of the length field?

Brief interjection -- you speak of "the length field" -- please note, there are many length fields in the ASN.1 structure, and we do not know precisely which one we are meant to overflow (and cannot without boot9).

I ask because, from what I understood, the signature at risk is the FIRM Header's own signature (offset 0x100, size 0x100). Thus, the attempts to check for SigHax would start with modification of *nothing* except that FIRM Header signature.

This is correct, but I think I begin to understand where your lack of understanding stems from.

You are acting as though we can test arbitrary ASN.1 structures, and the difficulty of sighax comes from figuring out which ASN.1 structure is proper.

This is...clearly not the case. We can prove it with some simple critical thought: Suppose we could insert arbitrary ASN.1 structures. Why not just insert an ASN.1 structure, uncorrupted, containing the SHA256 hash of the preceding header? Because, as you'll observe, that would imply that we could sign arbitrary data, in which case we would not need sighax in the first place.

More technically: We do not check the FIRM header's raw signature for valid ASN.1. Suppose the FIRM header's signature is S, and the RSA public key used for FIRM signatures is E, N. We check S^E mod N for the ASN.1 structure, not S.

This is the key insight -- exponentiating S about N transforms it, effectively, for our purposes, into a random 256-byte buffer. If this were not the case (and you could predict the results of S^E mod N), RSA would be broken, and RSA is not broken.

So we cannot check arbitrary ASN.1 structures for validity. We can only check random 256-byte buffers.

The true difficulty of sighax is thus not "what ASN.1 structure is valid" -- the question of sighax, really, is "how do we find (random 256-byte buffer S) such that S^E mod N is a properly malformed ASN.1 structure"? This is a hard problem precisely because RSA is a hard problem -- it's just the discrete logarithm problem again in disguise.

The reason this is not viable pre-bootrom, is that the (high) difficulty of ASN.1 validation (which we cannot do, really, pre-bootroms) becomes downright impossible when you consider that it takes 6 months, on average, on 10 cpus to *generate* the working signature in the first place .Our inability to validate the ASN.1 structures only transforms this difficult problem into an impossible one.

Finally, I admit that none of the heuristics are guaranteed to be correct. At the same time, do you believe use of those heuristics would not improve the searching of the potential ASN.1 length value space? I'm interested in your response....

I do agree that your heuristics seem mostly sane. Except for heuristic 3, which I will explain in the spoiler box.

Your issue is that you are thinking the search space that is difficult to narrow down is the ASN.1 validation search space, when really it's the signature generation search space -- and it is the combination of these two difficult spaces that makes it impossible.

The really big objective thwarting factor to your heuristics is that we do not know precisely which ASN.1 length field we wish to overflow. There are something like 8 possibilities. Also, having thought about this problem quite a bit, even when you maximally reduce the search space there are far, far too many signatures to try -- and I've thought of some better heuristics than you have.

Spoiler: the best heuristic I can think of

Consider, using your naming scheme, that we almost certainly know Z.

"What?", you might say?. I claim that, regardless of what pointer boot9 uses for the calculated hash, 0x1000A040 is almost definitely a valid desired result for Z. The SHA_HASH register always contains the most recently-calculated sha256 hash using the hardware. Unless boot9 is *truly reckless* with regards to race conditions, that should be the hash of the FIRM header.

We can also safely assume that the FIRM header is aligned to 0x10 bytes.

This means that we know the lower 4 bits of L, a 4x improvement over your lower 2 bits.

Note: This invalidates your Heuristic 3.

Further, consider that ram is preserved on reboot, and we can dump ITCM/arm9mem immediately following boot9. This means we can see what portions of arm9mem/ITCM are modified by the bootrom. (spoilers: basically none of them, and we can effectively disregard these two locations as where X is, although to be honest they're so small you might as well include them).

So X is in DTCM, almost certainly.

This, with my better heuristic, reduces our hunt to a mere 0x400 (1024) possible values for L.

I claim that because we do not know precisely which length field to overflow and because the hard part of the problem is really generating the ASN.1 structures to check, not validating them, that even with this massive reduction-via-heuristic of the search space of validating ASN.1 structures sighax is computationally infeasible pre-boot9 dump.

 

[Selver]

This is a super admirable attitude, and I really appreciate it. So: sure.

SciresM, thank you for the technical discussion. It's wonderful to talk about it at depth on this forum.

Below, areas we agreed, highlight of what I overlooked, comments on heuristics, and random thoughts/questions.

... there are many length fields in the ASN.1 structure ...
More technically:
[boot9 does] not check the FIRM header's raw signature for valid ASN.1.
Suppose the FIRM header's signature is S, and the RSA public key used for FIRM signatures is E, N.

We are in total agreement on all these points. I might add that boot9 never really checks for valid ASN.1, but...

[boot9 checks] S^E mod N for the ASN.1 structure, not S.
... exponentiating S about N transforms it ... into a random 256-byte buffer.
... cannot check arbitrary ASN.1 structures ... only check random 256-byte buffers.

You're right. I overlooked this in my excitement, before I experimentally validated. You're right, this is a brute-force search, running the modular exponentiation for each value, and only after this exponentiation can the data be considered for whether it not only has potentially valid ASN.1 data, but has the precise data that would cause the effects desired.
@addi33, please remove my thoughts from the original post, as it's NOT sufficient to brute-force sigHAX without the bootrom dump (or at least, knowing the memory location I called X.

Spoiler: better heuristics

I do agree that your heuristics seem mostly sane. Except for heuristic 3
...
There are something like 8 possibilities [for which ASN.1 length field to overflow] ... and I've thought of some better heuristics than you have.
...
0x1000A040 is ... Z [because it's the] SHA_HASH register
...
FIRM header is aligned to 0x10 bytes ... a 4x improvement over your lower 2 bits.
...
[basically none of] arm9mem/ITCM are modified by the bootrom ... So X is in DTCM, almost certainly. This, with my better heuristic, reduces our hunt to a mere 0x400 (1024) possible values for L.

Very nice. Very nice indeed. My hat's off to you, SciresM.


As an aside, do you happen to know if the RSA public keys are publicly documented?
(both retail/dev, and both nand/wifi flash)

More specifically, are any of these exponents low-order?
(IIRC, E is 41; but my memory is poor, and I don't have them at hand anymore; and fun can be had if E <= 3....)

 

[SciresM]

SciresM, thank you for the technical discussion. It's wonderful to talk about it at depth on this forum.

Pleasure's all mine

As an aside, do you happen to know if the RSA public keys are publicly documented?
(both retail/dev, and both nand/wifi flash)

More specifically, are any of these exponents low-order?
(IIRC, E is 41; but my memory is poor, and I don't have them at hand anymore; and fun can be had if E <= 3....)

Heh, I know there's lots of fun to be had with E <= 3.

That said, E = 0x10001 (65537) for all Nintendo RSA pairs -- you can validate for a few of their, ah, private ones using a tool I published the other week.

And I don't know if they've really been publically documented, before, but if they haven't....

Spoiler: public keys

Spoiler: 3DS Devkit FIRM RSA key

E = 0x10001
N = 0xC11E84E4DAD7EDC8A5D9CB0BE93B9DBC1569F795F68FB7912419BE8FFEBBC11D09F0E378A20CC00B8ECDBA0E694C614ABD13EAE223E40B621F9B631B3134B71273646B4E60410A3D5486FA49EC2D77AD1DBC48E7FB07EF48C3BEC3D6E15B3DCD5E6B46086A3A0EAE254944A5400D945318A48F578EF4CDB4D34EE7159B11958500C49294B8BEFECBB750A0BE8AF5FDC80E4BA941136248CD1AF3C86BA5A0DFF19D3DFDE4D17C1F000D99726BA3057F8638BE4D5EAB93DFF3EEA19F2250A87F31AA2B03719B14C43088426FD52C7B03643B14EC4633CC2C959F5C7B83C567DD7CA12DD6EC170B23C7B19A72BA78CB39685CB6B461E198CF1D69F9D7B0A05E9CEB

Spoiler: 3DS Retail FIRM RSA key

E = 0x10001
N = 0xDECFB6FC3D33E955FDAC90E88817B003A16B9AAB72707932A2A08CBB336FB076962EC4E92ED88F92C02D4D410FDE451B253CBE376B458221E64DB1238182B68162B730F4604BC7F7F0170CB575887793526370F00BC6734341EEE4F071ECC8C132C4DCA9991D31B8A47EDD19040F02A81AAFB3489A29295E4984E09411D17EABB2C0447EA11B5E9D0D1AF9029A2E53032D48967C2CA6D7ACF1ED2B18BB01CB13B9ACA6EE5500377C696162890154779F075D26343AA949A5AFF25E0651B71CE0DEDA5C0B9F98C215FDBAD8A99900ABA48E4A169D662AE85664B2B6C093AF4D38A0165CE4BD62C2466BC95A594A7258FDB2CC36873085E8A1045BE0179BD0EC9B

Sadly I don't know the public keys for wifi flash -- I can't find 'em anywhere, so they're probably another one of those things-we'll-need-the-bootrom-for.

Surely I am allowed to post those, since they are, you know public keys. If not, I'd appreciate if a moderator could let me know so I can remove 'em.

 

[adrifcastr]

@addi33, please remove my thoughts from the original post, as it's NOT sufficient to brute-force sigHAX without the bootrom dump (or at least, knowing the memory location I called X.

thats not needed, I mean its a really nice writeup, , and i have posted SciresMs post just above and also clearly mentioned that its not possible without the bootroms. you have taken a lot of time to write down your thoughts. its a really big post, so I´ll leave it there [/QUOTE]

 

[Selver]

thats not needed, I mean its a really nice writeup, , and i have posted SciresMs post just above and also clearly mentioned that its not possible without the bootroms. you have taken a lot of time to write down your thoughts. its a really big post, so I´ll leave it there

Well, I guess most of the post is accurate, except for a few bits in the final brute-forcing section.

Maybe I'll writeup a replacement for that one section sometime. I'll just post some raw thoughts, which are not guaranteed to be correct....

• cannot choose target ASN.1 data ahead of time with only pubkey; must search random data that (after exponentiation) happens to result in the desired ASN.1 data
• normally, because hash embedded in the ASN.1 data is validated to match target, this is cryptographically sound
• boot9 doesn't modify most ARM9 nor ITCM (based on known bug that doesn't clear RAM on boot, filling with predefined pattern, checking after (presumably A9LH) boot -- based on SciresM comments)
• The location of Z is very likely 0x1000A040 (SHA_HASH register)
• The location of X is in the 16k starting at 0xFFF00000 (DTCM)
• RSA signature is aligned on 16-byte boundary (heuristic) ... only 1024 possible target values remain

S == FIRM header's signature
E,N == RSA public key
S^E mod N == the resulting ASN.1 structure

What matters is getting the pointer / offset value to overflow and point to the SHA_HASH register at 0x1000A040.
FIRM_HEADER is stored at address 0x01FFBB00 (3dbrew.org, check who added this info)?
(Hash would normally be at 0x01FFBC00)?
So... want to have ASN.1 data that meets the following criteria?

Define the final offset as the offset of the length field, for the field that boot9 would identify as the hash, plus that field's own length value.
(33c3 @ xx:xx, Derrek indicated first thing boot9 does is parse the hash...)
The final offset may need to be equal to 0x0E00E440 (0x01FFCB00 + 0x0E00E440 == 0x1000A040).

Thus, would need to check the above for random values R, after doing R^E mod N...
Nasty stuff. Computationally intense, even with optimized maths. Boot9 pseudo-code would help reduce false positive rates. Actual Boot9 addresses used might eliminate false positives?

6 months using 10 cores... that's amazingly good!

 

[Urbanshadow]

Uh, well mannered gentlemans having a meaningful conversation in gbatemp...

This is one of the things you don't see everyday...

 

[The Catboy]

Every time this thread gets bumped and there's not a release, I cry a little.

 

[adrifcastr]

Uh, well mannered gentlemans having a meaningful conversation in gbatemp...

This is one of the things you don't see everyday...

yeah actually I have expected an argument between both of them, but wow, turned out into a meaningful conversation. thats great.

Every time this thread gets bumped and there's not a release, I cry a little.

well, waiting is your best friend in this case.

 

[tunip3]

Everyone seems to be forgetting to Gain arm 9 access for installing Sighax using fast had combined with safe agb firm like it is used with safehax to launch an arm9 payload with arm9 access. So it can be used without a9lh or a hardmod or a firmware below 11.0

 

[rotomington]

Everyone seems to be forgetting to Gain arm 9 access for installing Sighax using fast had combined with safe agb firm like it is used with safehax to launch an arm9 payload with arm9 access. So it can be used without a9lh or a hardmod or a firmware below 11.0

Yes, but we don't have the code needed to exploit the bootrom for sighax. If we don't have the exploit, we can't use the exploit.

 

[rotomington]

Dumb question, but where is Boot9 stored? If it's stored on a chip, could we not just hardmod directly to the chip?

 

[metroid maniac]

Dumb question, but where is Boot9 stored? If it's stored on a chip, could we not just hardmod directly to the chip?

Boot9 is part of the main SoC (System-on-a-chip) which contains all the important hardware on a single chip.

 

[Kyubnyan]

Go on twitter and search for posts with #path2b9 you can find progress on the boorom dump.

 

[tunip3]

Yes, but we don't have the code needed to exploit the bootrom for sighax. If we don't have the exploit, we can't use the exploit.

no i am just talking about the things needed to install because some people are saying that you need full system access so you will need a hardmod, a9lh or 9.2 firmware version i am just stating that it can be done on any firmware version currently

 

[adrifcastr]

btw I have updated the op

 

[Kyubnyan]

btw I have updated the op

Can you tell them to not ask stupid question to hedge in the op?

 

[adrifcastr]

Can you tell them to not ask stupid question to hedge in the op?

k

 

[vinstage]

I can't wait for this release. It sounds pretty ideal for someone who has no idea how to go about CFW :') atleast, I hope I've understood the concept correctly

 

[adrifcastr]

I can't wait for this release. It sounds pretty ideal for someone who has no idea how to go about CFW :') atleast, I hope I've understood the concept correctly

3ds.guide the most idiot/noob proof guide that the world has ever seen. if yo are interested in how it works from a technical view, feel free to ask me or the other people on the temp.