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 ) it would boot the OS just fine, since it would operate the same from there on.

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.

Eh, guess I'll defer to the more knowledgeable. I don't exactly have a degree on the subject

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.

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 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 - 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, 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.

Quote from: calcforth on November 15, 2010, 04:07:53 pm

How the 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 and second 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.

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