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.

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.