Re:The image in this post displays its own MD5 hash
by Retr0id on Saturday September 24, 2022 @06:04AM
(#32961175)
With what time complexity?
[ Parent
| on HN ]
Re:The image in this post displays its own MD5 hash
by orlp on Saturday September 24, 2022 @06:25AM
(#32961247)
O(n^2 * w) where n is the number of equations and w is the number of elements in an equation.
Re:The image in this post displays its own MD5 hash
by Retr0id on Saturday September 24, 2022 @06:32AM
(#32961279)
I see. So in this instance, it's O(32^2 * 36)? That is better than 2^19, depending on implementation efficiency.
Re:The image in this post displays its own MD5 hash
by amluto on Saturday September 24, 2022 @07:28AM
(#32961534)
You’re missing the constant factors. Gaussian elimination on a matrix containing 32-bit elements using xor involves operations that likely take a single cycle. The brute-force and meet-in-the-middle operations involve CRC-ing an entire message, which is vastly slower. (Or it involves optimizing the CRC using essentially the same linear algebra technique, at which would it would be pretty silly to solve a linear system by exhaustive search instead of algebra…)
I would expect the linear algebra approach to win by orders or magnitude.
Re:The image in this post displays its own MD5 hash
by Retr0id on Saturday September 24, 2022 @07:42AM
(#32961604)
I did my meet-in-the-middle using a search tree, so you don't need to re-CRC the whole message at once.
Re:The image in this post displays its own MD5 hash
by orlp on Saturday September 24, 2022 @07:27AM
(#32961530)
Well to make the playing field equal it would be 2^19 times the time to check a solution, which is another factor of 36 times a fairly large constant C. So really you're comparing 2^19*C to 32^2.