Comment by brokenmachine
3 days ago
It's fairly trivial, but still significantly harder than computing a single CRC.
From stackoverflow:
Because a 32-bit CRC yields only 2³² (approx. 4.29 billion) possible outputs, the Birthday Paradox dictates a 50% chance of an accidental collision after processing just ~77,000 unique inputs.
I've done it for shits and giggles and from memory it took my desktop PC maybe 10 minutes to generate a collision.
You're missing the point though.
Noise is not the only thing they should be protecting against.
The point is that AMD is executing code based on checking using an algorithm that has barely any protection from malicious inputs, which is stupid, and not fixing it just compounds that stupidity.
A cryptographic signature protects against both noise and malicious inputs.
You can do it with a single GF(2) multiplication, ignoring the complications of reflection and such. A normal CRC is just the special case of making the remainder 0 (again ignoring complications). You can also brute force it, but that's a bit slow for 64 bit CRCs and well, nanoseconds vs minutes in your example.
Sorry, can you point to the comment where I tried to defend AMD's use of CRCs in this particular application? I think I've made it pretty clear that I don't think they're appropriate for cryptographic applications. I was just talking about the math.
Different tools for different purposes. You probably don't want to be using your mac scheme for noise resistance, because then you're paying a cost in either buffer space, PDU size, or retransmits, and your error correction capabilities are nil. CRCs allow some error correction (albeit rarely used and inefficient for multibit errors vs FECs), good bit error detection properties, and are cheap. It's common to use both at different layers of a protocol stack.