Hacker News new | past | comments | ask | show | jobs | submit login

> If I can crack a DES password in 4 days, I can crack a 3DES password in 12

It's multiplicative, not additive. 3DES is about 2^56 times as difficult to crack as DES. (Not 2^112 times because there is an attack that effectively limits it to twice the effective bits of DES, rather than the three times you might expect at first).






> there is an attack that effectively limits it to twice the effective bits of DES

* Meet-in-the-Middle attack.

https://en.wikipedia.org/wiki/Meet-in-the-middle_attack

This attack is surprisingly simple, if you encrypt the message twice by

    ciphertext = encrypt(encrypt(message, key1), key2)
Then,

    decrypt(ciphertext, key2) == encrypt(message, key1)
An important security property all symmetric ciphers should offer is immunity to chosen-plaintext attack, if the attacker controls "message", it shouldn't make the cipher more easy to crack.

But in this case, the attacker can obtain all the 2^56 possible encryption of message by enumerating key1, put it in a lookup table (assume the table-lookup time is O(1)) , then we can try all possible decryption of ciphertext by enumerating key2. Then compare it with the lookup-table for a match, bingo!

If key is 56-bit, the attacker gets 2^56 outputs for the left side, 2^56 outputs for the right side, total number of operations is 2 x 2^56 == 2^57, not 2^112.

To increase the security claim to 2^112, we need triple encryption, not double encryption, thus 2DES is never used.

The idea that simple double-encryption doesn't work because of such a simple attack shocked a lot of newcomers.


This is mostly irrelevant in the context of password hashing however. We're simply feeding passwords into a blackbox at X/s until we get a match. 3DES runs at approximately X/3 compared to DES. If it takes 4 days to feed a bajillion passwords into DES, it takes 12 days to feed the same number into 3DES.

It might be relevant, because the original asker said "with a sufficiently long password". (Implicitly: with a password longer than 8 characters that the original DES scheme would allow.)

It's more complicated than this, because there are known attacks against 3DES. It's at most 2^28 times more complex, AFAIK, but there are probably better attacks than the few I know.

Are any of these attacks relevant to password cracking?

> It's multiplicative, not additive. 3DES is about 2^56 times as difficult to crack as DES. (Not 2^112 times because there is an attack that effectively limits it to twice the effective bits of DES, rather than the three times you might expect at first).

If you’re using 3 different keys, yes, that makes sense. But if you’re just keystretching one key, wouldn’t it just take 3 times as long because you encrypt, decrypt, encrypt (3 processes)?




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: