Omnimaga
Calculator Community => Other Calc-Related Projects and Ideas => Topic started by: willrandship on November 11, 2010, 10:15:08 pm
-
While on Hackspire, I noticed this log file of the boot sequence of the nspire. (obtained through an rs232 cable linked to the dock
http://hackspire.unsads.com/files/log-philippburch-serial-boot.txt (http://hackspire.unsads.com/files/log-philippburch-serial-boot.txt)
Notice under "Boot Loader Stage 2" It says "Using Production Keys"
Something occurred to me: why state you are using a default if you can't change it?
Since the Boot2 is upgradeable, this means you could change the OS license key, and it appears you don't even need to go that far. The Boot1 is most likely capable (or maybe even some file in the system :D) of forcing the boot2 to use a different key when loading the OS. That means two things:
1. If we discover the RSA key to the OS, TI could change it on us with a boot2 v2.5
2. If we can figure out how to force our own key, we could easily install our own OS!
Thoughts?
-
Well, the solution then is if we want to crack a key, crack the one for boot2 instead of the one for the OS. The key in the boot1 isn't going to change, for sure.
-
It would still take those 1000 Intel Core i666 8.60 GHz 128-cores computers to factor it, right?
-
Right, but I was thinking more of the possible security hole. Imagine how awesome it would be if all we had to do to make our own OS took 4 steps:
1. Send Ndless and Keychange to your calc
2. Install Ndless, run Keychange
3. Access Maintenance Menu (runs from Boot1, I think) and delete os
4. Install the new OS
-
Maintenance Menu is actually in boot2, I think (which is why it doesn't come up until the loading bar is half full)
-
So, essentially, we would need to make a boot2 with the same hash/signature as the real boot2. Quite possible if we knew what method it used to hash it.
-
Hmm..that could be troubling. As long as it does it before it checks RSA encryption, though, it should still work fine.
How dare you ninja me :P
Not quite what I meant, Graphmastur. My point was that the Boot2 has another option for what key it uses than the default. The question lies in what accomplishes this change. It can't be the boot1, since it's read-only, and it can't be the boot2, since it is the boot2 whose actions change. There's probably a configuration somewhere in the /phoenix folder that allows you to use a different key.
Is disassembling illegal? As long as we're not using their code for anything, it's not a copyright violation, right?
If it isn't, then we could disassemble the boot2 bin and see what exactly it is doing at that stage.
-
Does anyone know of a good ARM disassembler? Any that I can find only take .elf files, and I was hoping for one for .bin files.
-
Will this (http://www.softpedia.com/get/Programming/Other-Programming-Files/DISARM.shtml) work?
-
That one sorta works. I ran it at the school's pc, and it just spits out the output into the command line. Unfortunately, the windows command line erases after ~200 lines, so I lose most of it. It should really save it to a file.
It runs in Wine though :D I'm going to see if I can get it to record.
-
program.exe arguments > output.txt
-
Eh, I got it through the linux terminal. Hallelujah for infinite backscrolling!
Here's the file. does it looks like complete nonsense to any of you? I'm afraid I don't really know asm that well.
-
Yep, it's complete nonsense. What were you disassembling?
Edit:
Never mind, I see now. Are you sure about that "infinite backscrolling"? I only see 195 lines in that text file.
-
It went all the way back to the input command. This was only the boot2. I'll try again though.
Just the Boot2.bin file extracted from the OS upgrade. Oh, wait, that was encrypted, wasn't it?
-
It went all the way back to the input command. This was only the boot2. I'll try again though.
Just the Boot2.bin file extracted from the OS upgrade. Oh, wait, that was encrypted, wasn't it?
It was compressed with a weird compression algorithm. Goplat managed to decompress it, though. You should E-mail him about the format.
-
Is that stuff legal to post on the forums, though? (The boot 2 disassembly file above) ???
-
It's not a real dissassembly, don't worry. It's as if I disassembled a zip file containing the 84+ ROM :P Garbage
-
Since the Boot2 is upgradeable, this means you could change the OS license key, and it appears you don't even need to go that far. The Boot1 is most likely capable (or maybe even some file in the system :D) of forcing the boot2 to use a different key when loading the OS. That means two things:
1. If we discover the RSA key to the OS, TI could change it on us with a boot2 v2.5
2. If we can figure out how to force our own key, we could easily install our own OS!
Thoughts?
Well, the scheme is not unique for TI, it's used everywhere: PSP, Wii, XBox360, some phones, etc. The idea is that "recovery menu" is already non-trivial piece of code and so it's not a good idea to store it in ROM. ROM only contains boot1 which checks RSA signature of boot2 and then jumps to it - nothing else. So yes, if the RSA key of boot1 will not be broken TI can easily make it impossible to change anything by upgrading boot2 (this is what Nintendo does with Wii - not very successfully). The problem here is the fact that brute force will not work: you'll need a lot of power (US$100,000 prize was left unclaimed). There are a lot of research in this area and the general consensus says that we'll have some new clever algorythm capable of cracking 1024 bit key in the next 10 years or so (that's why serious cryptographers recommend to start switching to 2048 bit keys), but it's probably not a good idea to wait for it :)
-
I'm not talking about cracking a current key, I'm talking about the possibility of the boot2 and boot1 allowing for other keys than the current one.
Edited to remove offensive content. Sorry, I was having a really bad day.
-
the problem here is that many of us barly understand any of this.
-
Is it just me or is everyone here deaf? I'm not talking about cracking a current key, I'm talking about the possibility of the boot2 and boot1 allowing for other keys than the current one.
What happybobjr said. I myself barely understand any of that stuff, plus the topic about the RSA cracking is several pages long, so not everyone will feel like reading through it. So it's pretty obvious people will not undertand/interpret the content of this topic perfectly. No need to be harsh on people.
-
Does anyone know the hash method used for signing the os/boot2? We could focus efforts on trying to crack the hash,if it is feasible.
-
The hash method is SHA-256 (http://hackspire.unsads.com/wiki/index.php/OS_upgrade_files).
-
So, could we attack boot2 by writing our own code, and appending more data to the end until we find something with the same hash as boot2?
-
So, could we attack boot2 by writing our own code, and appending more data to the end until we find something with the same hash as boot2?
If you can break SHA-256 that way, then yes. Although it would be insanely hard.
-
So how hard would it actually be? Would it involve doing 2^256 trials, or is there a faster way?
-
So how hard would it actually be? Would it involve doing 2^256 trials, or is there a faster way?
Harder than factoring the number for RSA. Not a single collision method has been found as far as we know.
-
Is it just me or is everyone here deaf? I'm not talking about cracking a current key, I'm talking about the possibility of the boot2 and boot1 allowing for other keys than the current one.
Sorry, my fault. Finally wrapped the mind around the question: the answer is so obvious to me that I never imagined that it's not obvious to everyone.
Here is the part I missed:My point was that the Boot2 has another option for what key it uses than the default. The question lies in what accomplishes this change. It can't be the boot1, since it's read-only, and it can't be the boot2, since it is the boot2 whose actions change.
Sorry to disappoint you but there are probably just one key in boot1 and boot2 loaders (unless someone did huge mistake while building them). And the to change it you indeed must change boot1. And indeed it can only be done on factory which build these things.
The message about "Production Keys" is not for end user - it's for service center. If the Nspire does not say these messages then most probably someone took MB from prototype (http://datamath.org/Graphing/NSpire_CASE.htm) and put it in regular Nspire: service center is not supposed to repair such devices.
WTF? Who will need all this crap? Well, the hardware is not developed in a day, you know. And original TI-Nspire hardware was different from what you can buy today in stores. Take a look (http://datamath.org/Graphing/NSpire_CASE.htm). These prototype devices are sold on ebay from time to time (there are couple (http://cgi.ebay.com/TI-Nspire-CAS-Graphing-Calculator-/250726740599) of them (http://cgi.ebay.com/Texas-Instruments-TI-Nspire-CAS-Plus-New-Inspire-/300492955674) right now) - and since they require different signature they are sold for cheap: you can not install a production OS on them (different key prevents it and even if you'll manage to overcome this limitation it still will not work because hardware is different). I don't know how boot log looks on these devices, but most likely it does not say "Using Production Keys".
Since this approach is pretty typical in hardware development I was sure it was discussed to death already... but now looking back I see that indeed it was never explicitly explained... at least not in this thread.
As for breaking the key...
So how hard would it actually be? Would it involve doing 2^256 trials, or is there a faster way?
Well, the fastest known way involves 2^253.5 trials which still makes it totally impossible. Better to find some other kind of weakness... perhaps something similar to what Nintendo did (they used strncmp to compare sha1sums so the attack become 2^8 trials, not 2^70+ trials).
-
Yeah but this is SHA-256, so it would be even harder. Especially with no collisions ever being found. Yeah...
-
Umm, calcforth, there are actually 3 keys for all the calc. One verifies the boot2, one verifies the OS for the CAS, one for the nonCAS.
Of course the boot message isn't for end users. We got it through a hookup to the expansion port on the bottom, that we found out happened to have an RS232 serial connection, and it just happened to automatically display boot debugging information through it.
Everyone knows about the CAS+ and the evaluation editions. They don't have anything to do with this, and I don't see why you bothered mentioning them at all.
I was never talking about breaking the key.
@Graphmastur
Yeah, these things are designed to be as collision-free as possible. :(
-
So how much work is it to compute a hash compared to doing a trial division?
-
Probably around the same. Of course, an extremely similar file would be much easier to compute than an extremely difficult one, and if we made the boot2 simply accept our own OS's key (which could be an extremely close semiprime number, but one we know the factors of :P) it would boot the OS just fine, since it would operate the same from there on.
-
Probably around the same. Of course, an extremely similar file would be much easier to compute than an extremely difficult one, and if we made the boot2 simply accept our own OS's key (which could be an extremely close semiprime number, but one we know the factors of :P) it would boot the OS just fine, since it would operate the same from there on.
Huh? I don't get the similar semiprime thing.
-
Well, the idea they're saying is that you make a boot2 that has an RSA key (which is a semiprime, the product of two primes) that you know the two prime factors of. This allows you to make your own OS. I was simply stating that a semiprime that is closer would be easier to make a hash match than one farther away from the original.
Example:
17*11=187 original key
11*11=121 as a replacement would not match the hash as easily as, say, 17*13 which = 221. You can get closer with larger numbers.
-
"Closeness" doesn't make any difference, it's pass or fail.
-
Eh, guess I'll defer to the more knowledgeable. I don't exactly have a degree on the subject :P
-
(Note, for discussion about the actual key factoring issue, we should use that thread (http://ourl.ca/6236), to make sure we do not confuse users in this one.)
-
So, could we attack boot2 by writing our own code, and appending more data to the end until we find something with the same hash as boot2?
SHA-256, and SHA-512 (SHA-384 is essentially the same as SHA-512) are both cryptographic Hashes. They currently have no known weaknesses. In other words, no one has ever cracked the algorithms themselves. The ONLY known way to do it is with brute force methods. As has been mentioned, that's not going to happen anytime soon. There's a reason why the SHA-256 is still widely used. I believe the NSA still recommends it, actually. However, if (and this is a big if) someone discovered a way to reliably make collisions in SHA-256, then we could conceivably launch a successful birthday attack in reasonable time using Chabaud-Joux techniques (basically testing weak versions of the hash until you have an algorithm that can short circuit the real one) that would theoretically allow us to install another OS. That's probably not going to happen in the next decade. At the very best, we'll see hints that the hash has the possibility of compromising collisions.
-
I'd like to know, how much work is it brute forcing a collision say, compared to factoring a 512 bit key? Also, I found this: http://eprint.iacr.org/2004/304.pdf (http://eprint.iacr.org/2004/304.pdf), which has an algorithm to reduce the number of steps before a collision occurs.
-
However, if (and this is a big if) someone discovered a way to reliably make collisions in SHA-256, then we could conceivably launch a successful birthday attack in reasonable time using Chabaud-Joux techniques (basically testing weak versions of the hash until you have an algorithm that can short circuit the real one) that would theoretically allow us to install another OS.
How the collision attack (http://en.wikipedia.org/wiki/Collision_attack) will help us? I can imagine just one scenario: if we'll have friend at TI who will produce two images (one legitimate update and one with non-checking boot2, for example) and will submit the legitimate update using education.ti.com ... But it's probably will be easier for him to just sign non-checking boot2 directly? What we need is called second preimage attack (http://en.wikipedia.org/wiki/Preimage_attack) - and it's quite different kettle of fish!
I'd like to know, how much work is it brute forcing a collision say, compared to factoring a 512 bit key?
They are lightyears apart. Facts:
1. MD4 was perceived weak 20 years ago, was replaced with MD4 in 1992 and broken in 1995 (few seconds on typical computer).
1. MD5 was perceived weak 15 years ago, was replaced with SHA1 in early 2000th and finally "totally broken" in 2009 (few seconds on typical computer).
2. SHA1 was perceived weak 5 years ago, was replaced with SHA-256 closer to 2010 - still unbroken.
Given these facts and the claims about "utter failure" of MD4, MD5 and SHA1 you should expect that second preimage attack is now easy too, right? Wrong: only MD4 is "kinda broken" (can be theoretically broken using million computers and about thousand years... hundred years if you are lucky).
Also, I found this: http://eprint.iacr.org/2004/304.pdf (http://eprint.iacr.org/2004/304.pdf), which has an algorithm to reduce the number of steps before a collision occurs.
This is good algorythm, but it does not buy us much: successor to Deep Thought is still not powerful enough to solve this problem... and sadly, it's already busy trying to solve another problem.
I'm pretty sure cryptographers will eventually solve this problem (I mean: they already can break MD4... kinda), but I doubt it's good idea to bet everything on this outcome.
P.S. Collision attack has it's uses - but sadly they lie very far from the need to sign Nspire ROM. Better to try to find some kind of programming error... at least for now.
-
How the collision attack (http://en.wikipedia.org/wiki/Collision_attack) will help us?
Because they let you use your own file instead of the original message without changing the hash. As I said, it would only allow the theoretical possibility of installing an OS. In practice, it would be next to useless. I only mentioned it because it's a lot easier to launch a birthday attack than a preimage attack. Reducing the computation time for a preimage to a reasonable time would require exploiting the algorithm. That's just not going to be possible anytime in the next few years, at the very least.
@fb39ca4, your link does describe a way to reduce computation time, but the result is still in the realm of near impossible.
-
How the collision attack (http://en.wikipedia.org/wiki/Collision_attack) will help us?
Because they let you use your own file instead of the original message without changing the hash.
How? I think you are confusing collision attack (http://en.wikipedia.org/wiki/Collision_attack) and second preimage attack (http://en.wikipedia.org/wiki/Preimage_attack). Collision attack: Alice sends message A to Bob and when Bobs does as it says Alice shows another message B (with the same hash!) in court and says: sorry, this is what I meant, blame Bob for his poor judgment. Second preimage attack: Alice sends message A to Bob but Bob replaces it without another message B and when Alice complains shows that other message (with the same hash!) in court and says: sorry, this is what I've got. Nleash developers play Bob here, not Alice!
As I said, it would only allow the theoretical possibility of installing an OS. In practice, it would be next to useless.
What use will it have? Even theortical? The boot2 hash one particular hash and this is the only hash we know how to present to boot1. We can not change it thus we can not use collision attack. It's as simple as that.
-
Oops, you're right. Thank you for pointing that out.
However, if we could generate an OS with the same Hash as the current OS (a collision), then we could install that OS and the boot code wouldn't realize it. The problem is that any collision is likely to be complete gibberish codewise.
-
However, if we could generate an OS with the same Hash as the current OS (a collision), then we could install that OS and the boot code wouldn't realize it. The problem is that any collision is likely to be complete gibberish codewise.
No, no - this is not how it works. For MD5 there are so-called "chosen-prefix collisions": files with predermined content and only few bytes of garbage at the end. But still both files are produced by "Alice" - and it does not help us any. And for second preimage attack (this is what we need)... it's not realy practical even for MD4, let alone MD5... and SHA256 is much harder then these!
Only proprietary "tip-sikrit" algorythms (like GSM's A5/X) are easily exploited... but it looks like industry finally learned to use public well-test cryptoalgorithms. So instead of direct attack we are left only with possible bugs in OS... but it sure is a big attack vector still :)
-
The OS is only checked at boot. It's well known how to wipe and replace data. Thus, an OS that has the same hash *could* be replaced. As I said, it will never work in real life.
-
What's the difference between chosen prefix and second preimage collisions?
-
Not really sure how to explain that.
Can anyone tell me which key we need to factor mod 4 and mod 12? Posting the key itself would also be nice. ;-)
-
What's the difference between chosen prefix and second preimage collisions?
Finding the second preimage is basically finding a message of known content that has the same hash as the original message. It's a more specific category of collision attacks, where you simply find an arbitrary message that has the same hash as the original message.
Looking back, I guess I was using the terms incorrectly.
-
Here's the three Keys
From hackspire's perl script (in hex)
boot2.img
c3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8bbcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209cdf80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7
TI-Nspire.cer
aba7f0b8c7feb6e33438af5c25c67389eaf4d73f80cd0a37922493431cde03b34da448bdb05387cf7a8c59ee12d9613429a2b07ea385752f079892da1ae76c2b158f2d7169aae066432fe44f797df39dd6a0d7b2e2091281b30efac247c51576ebc93ec456de2e27d36b713844336b65af67ee58e6107a6a1deb954a91095295
Nspire.cer #2 (CAS Nspire's, I think)
b15e01c47c421be62f4e769b3ac98f4f983a820b0c181e35715d84a4f1acf0527eeddfabf9f66e73bedb55376e22f860c34dc70ce239157297056d4ecf46535778c3917647b5a6bb9c5638cdeff3e309ff66878fd4f233cf157d7af4136f307df90ec6ae6eaff6bead6d52f423a37dac59ff38ae876008103728f2bd674e858f
I stuck them in code tags so they wouldn't word wrap, and so they'd be smaller.
Also, Goplat gave me code for a boot2 extractor, so I have a good disassembly this time :P I won't post it though, since it's apparently illegal. It does look more valid this time, though. Not much coming from me :P I've never coded assembly before.
-
Thoughts?
In RSA encryption. I have heard of certain implementations that used a not so pseudo random number generator to generate primes, thus if one knows how were generated the random primes we could guess "some" (still a lot) of the primes with an certain size (around 400 to 600 bits) and with naive trial division factor it. I doubt we know how TI generated the primes.
And I have heard of a case where they cracked RSA with 1024 bits secret key this way. (don't ask me from where)
-
TI only needed to generate a few primes, though, to make the key. Their job was relatively easy.
-
If TI used random.com to generate the primes, we're screwed.
-
Why? Because it's not going to follow an algorithm? Those vary anyways.
-
If TI used random.com to generate the primes, we're screwed.
Believe it or not, there are better ways to generate primes than even Random.com
If we're lucky, TI took the easy way out and used a simple deterministic algorithm, assuming that no one would know what their algorithm was.
-
Well, even if we found it would it be so easy? We don't even know where they started, or stopped at!
-
Because it measures atmospheric interference, rather than using an algorithm.
-
TI only needed to generate a few primes, though, to make the key. Their job was relatively easy.
I know just a few primes are needed. (and with certain cares for vulnerabilities like some numbers allow to decrypt by encrypting the message over and over some n times)
I think you did not get to the point. I guess I was guessing bad. xD If we knew the method they used to generate the primes, we could come with a narrower list of primes to try factor the secret key. In the particular case of Nspire, this idea is almost certainly useless.
But there was one case they managed to factor a RSA 1024 this way, probably incomparable to the case of Nspire.
-
We know that it's 1024 bits. That narrows it down to a few thousand primes or so, assuming they didn't pad lower numbers to meet the bit requirement. If they did pad lower numbers, then it's hopeless for the next few decades or so.
-
If they padded lower numbers, wouldn't it no longer be prime?
I see your point now, Galandros.
-
If they padded lower numbers, wouldn't it no longer be prime?
I see your point now, Galandros.
You can pad zeros onto the beginning of a number to increase the bits in it without changing the value. For example, 1000, 01000, 001000, 0001000, and 00001000 are all equivalent, but they each take increasingly more bits to encode.
-
We'd actually be looking for primes in the range of 512 bits. And apparently, there's 4.35 x 10^151 of them.
-
What's the difference between chosen prefix and second preimage collisions?
They describe different sharacterists of attack:
1. Collision attack (http://en.wikipedia.org/wiki/Collision_attack) - you want to find two messages with the same signature.
2. Preimage attack (http://en.wikipedia.org/wiki/Preimage_attack) - you want to forge signatore on the document.
2a. First preimage attack (http://en.wikipedia.org/wiki/Preimage_attack) - you only have a signature.
2b. Second preimage attack (http://en.wikipedia.org/wiki/Preimage_attack) - you have an original document as well.
3. Chosen prefix collision attack (http://en.wikipedia.org/wiki/Collision_attack#Chosen_prefix_collision_attack) - collision attack where you want to have valid document (you dictate what you put in document and pad it with some "garbage" to alter signature)
4. Chosen prefix preimage attack (first or second) - the same as with collision attack: you want not random document with given signature but proper document with given signature.
They actually created different valid PDF files which had the same MD5SUM yet different predictions for the outcome of the 2008 US Presidential elections :-) See here (https://documents.epfl.ch/users/l/le/lenstra/public/papers/lat.pdf). As for preimage attacks - they are much harder and there are trouble with a simple preimage attacks, let alone collision prefix ones...
In RSA encryption. I have heard of certain implementations that used a not so pseudo random number generator to generate primes, thus if one knows how were generated the random primes we could guess "some" (still a lot) of the primes with an certain size (around 400 to 600 bits) and with naive trial division factor it. I doubt we know how TI generated the primes.
And I have heard of a case where they cracked RSA with 1024 bits secret key this way. (don't ask me from where)
You mean Side-Channel Attack (http://www.springerlink.com/content/w023k52252r2564v/)? This is a joke: they basicaly need to make random generator so non-random to show feasibility that it's pointless. In partucular it was never shown with normal multi-tasking OS: all demos included two programs run on bare metal with special scheduler. Otherwise noise from scheduler kills the side channel quite efficently.
And again: it only works if you can put trojan program on the system which genrates primes - I very much doubt we'll be able to do that.
If we're lucky, TI took the easy way out and used a simple deterministic algorithm, assuming that no one would know what their algorithm was.
Well, stuff happens (http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-0166) but I don't think they used some obsolete Debian installation to generate these numbers.