What's the difference between chosen prefix and second preimage collisions?

They describe different sharacterists of attack:

1.

Collision attack - you want to find two messages with the same signature.

2.

Preimage attack - you want to forge signatore on the document.

2a.

First preimage attack - you only have a signature.

2b.

Second preimage attack - you have an original document as well.

3.

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. 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? 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 but I don't think they used some obsolete Debian installation to generate these numbers.