DES-CBC with random IV - how big is the keyspace? Can COTS tools crack it?

Question

I've spent the night reversing the implementation of the 'Basic Text Encryptor' from Jasypt [1]. The algorithm is defined in documentation as 'PBEWithMD5AndDES'.

The implementation is this:

• A random 64-bit salt is generated
• The secret is generated as

secret = password + salt
for i in range(0, 1000):
    secret = md5(secret)

• The first 8 bytes of the secret are then used as the DES passphrase, and the last 8 bytes of the secret are used as the IV, and used to encrypt data with DES-CBC.

Given this, am I correct in thinking the total keyspace for the implementation is 120 bits (56+64)?

I have written a proof of concept reversal in python, but I'm interested in calculating how long it would take to brute force a real key. So far I've been unable to induce hashcat into decrypting something encrypted with this algorithm, and I'm unsure if it even can.

My questions are:

• Is the keyspace really 120 bits?
• Am I missing something or is hashcat not capable of cracking this?
• Can other tools crack it?
• Is it even possible to deduce correct outputs without making assumptions on expected output (eg all output must be ASCII data, or match a file header)

Edit: To reduce any confusion, my decryptor is as follows

import base64
import hashlib
from Crypto.Cipher import DES

passphrase = "123456" # Key used to encrypt
# Salt randomly generated at encrypt-time, and stored at
# the beginning of the encrypted data:
salt = base64.b64decode("vqmy2fiCipU=")
enc_b64 = "vqmy2fiCipVBIhiAzDfvTL0301DLgTqd"
enc_data = base64.b64decode(enc_b64)
if (salt != enc_data[0:8]):
    raise Exception("Salt does not match enc_data salt")
enc_data = enc_data[8:]

m = hashlib.md5()
m.update(passphrase.encode())
m.update(salt)
result = m.digest()

for i in range(1, 1000):
    m = hashlib.md5()
    m.update(result)
    result = m.digest()

# value of result is: md5("123456" + salt) iterated 1,000 times.

key = result[:8]
iv = result[8:16]
des = DES.new(key, DES.MODE_CBC, iv)
print(des.decrypt(enc_data).decode())
# > Hello World

[1] http://www.jasypt.org/api/jasypt/1.8/org/jasypt/util/text/BasicTextEncryptor.html

Answer 1

Is the keyspace really 120 bits?

No. It's still 56 bits, at least when multiple blocks are encrypted. For CBC mode then you can try and decrypt a block with the key, XOR it with the previous ciphertext block you should get a plaintext block. If you did this for the last plaintext block you'll have the PKCS#5 padding to find. If that's correct then you can start looking if you can produce valid plaintext.

If only one block is encrypted then the IV acts as a one-time-pad. In that case you will have to guess the password (presuming you have the salt of course).

Am I missing something or is hashcat not capable of cracking this?

Could be. But it would probably not be that hard for an accomplished programmer to program it in. Hashcat seems to focus on the password hash itself. Assuming the password is not too complex, guessing it may still be the best way to try and decrypt the ciphertext.

Can other tools crack it?

Well, cracking single DES can be done by specialized hardware for sure (a list is here). Asking for resources like that is off-topic though.

Is it even possible to deduce correct outputs without making assumptions on expected output (eg all output must be ASCII data, or match a file header)

Well, other than the padding, yes, you must be able to test if the plaintext is comprehensible in some kind of way. However, if you decrypt many blocks the plaintext is likely not all that random, so you could test for that. If it compresses well, for instance, it may be worth another look (but compression is generally pretty expensive).