9
$\begingroup$

I'm working on a cryptosystem which uses IDEA. The designer made the mistake of including a CRC-32B hash of the password unencrypted in the header, so that the system can quickly reject bad passwords. Of course, that opens it up to the obvious attack of brute forcing CRC32 over potential passwords until the right one is found. Which is what I'm trying to do.

Questions:

  1. Is the best way to do this simply to do an exhaustive search of the password space? It would seem to me that since CRC32(x) is related to x in manifest ways (eg XOR is preserved), it might be possible to do a construction where we actively direct the search in the right direction. I don't know enough about CRC32, but it would seem to me something like this is possible.

    Of course, it's not enough to find a string with the same CRC32. It has to be the real password used, otherwise the IDEA decrypt will be gibberish. So this might throw some water on this method. But, regardless, I'd like to know more about it. What do you say?

  2. Failing that, I'll need fast code to brute force the CRC32B. What is the fastest code? My plan is to brute force candidates via CRC32, then try to decrypt via IDEA and measure the entropy to filter out all of the false positives (1 in 4 billion) that will still match CRC.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

Assuming the n-bit CRC of an unknown bit string b is known, one can constructively rebuild any consecutive n bits of b from the rest of the bit string (and the definition of the CRC). Indeed, in the case described, that speeds up password search considerably. One can compute the last 32 bits of the password (likely, 4 characters) from the beginning of the password. If the password is constrained to characters in [20h..7Fh], that will further remove $49/50$ of the candidates.

Many CRCs found in practice (including 32-bit CRC CCITT) are not "XOR-preserving" in the sense $CRC(x \oplus y) = CRC(x) \oplus CRC(y)$.
However it allways holds that $CRC(x \oplus y \oplus z) = CRC(x) \oplus CRC(y) \oplus CRC(z)$ for any $x$, $y$, $z$ of identical length (including with $z$ all-zero); that (and a little linear algebra) is enough to organize the computation. At the end of the day, with $n=32$, one can compute the last 4 bytes by XOR-ing the values found in precomputed tables (one table for each preceding byte, with each table $256·32$ bits).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Fascinating, fgrieu. Can you give me more information? What do you mean "one can constructively rebuild any consecutive n bits of b from the rest of the bit string" - how much of b do you need to know? If you know the first 4 bytes, say, how do you build the rest of b? Remember, I'm looking for all candidates, not just one that happens to work. $\endgroup$
    – S. Robert James
    Commented Sep 16, 2011 at 2:39
  • $\begingroup$ @S. Robert James, You need to know the rest of the string: i.e., all but 32 bits of it. You can do it by solving a system of 32 linear equations (linear over GF(2), i.e., with XOR instead of addition), but in the end, it can be optimized down to table lookups as fgrieu describes. $\endgroup$
    – D.W.
    Commented Sep 16, 2011 at 6:35
  • $\begingroup$ Got it. CRC32 specifies 32 bits, so if I know everything but 32 bits, I can determine the missing 32. The tables show the CRC of one byte and the rest zeroes. I would assume that I need a separate set of tables if the length of the input changes (eg tables for last 4 of 8 bytes, tables for last 4 of 12 bytes). Where can I read more about this? $\endgroup$
    – S. Robert James
    Commented Sep 16, 2011 at 9:17
  • 1
    $\begingroup$ @S. Robert James: Sorry I do not have a reference, but the linear algebra is easy. Assuming the relation I give holds (it does for any CRC variant regardless of polynomial, initialization, finalization details), you can use the CRC function as a "black box" without knowing its internals, and only need to invoke it for the n +1 distinct n bit strings with at most 1 bit set. The rest is Gaussian elimination restricted to bit coefficients, and caching into tables to avoid solving a linear system repeatedly. I won't help with (pseudo-)code for fear of being associated with something nefarious. $\endgroup$
    – fgrieu ♦
    Commented Sep 16, 2011 at 16:15
0
$\begingroup$

IDEA has a key size of 128 bits. Even if the 32-bit CRC fully leaks 32 key bits, that would still leave an effective key size of 96 bits, or 79 billion, billion, billion keys -- that's still too large to brute force.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ The OP seems to plan a brute force attack of the password from which the IDEA key is generated, helped by CRC32; then for each candidate password, build IDEA key, decrypt ciphertext with IDEA and check redundancy of the plaintext obtained. That works irrespective of the IDEA key size. $\endgroup$
    – fgrieu ♦
    Commented Sep 16, 2011 at 2:06
  • 2
    $\begingroup$ Exactly. This is especially so because in this implementation, the key is given as a string ("password"), and then internally hashed to 128 bits. But the space of expected strings is of course much smaller than $2^{128}$. $\endgroup$
    – S. Robert James
    Commented Sep 16, 2011 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.