When attacking keyed algorithms, how is it known when the output is correct?

Question

I've been reading a little bit about cryptanalysis, and I'm wondering how attacking algorithms that work on keys is performed.

It's obvious how algorithms like MD5 are attacked, in pseudocode:

hashed = 'blablabla'
while guess != hashed:
    guess = md5(inc(guess))
print('{hashed} is {guess}')

But I can't see how you'd perform a similar attack on, for example, XTEA. To attack it through the deciphering process you'd have nothing to compare the guess to, and to attack it through the enciphering process you'd have to guess if encipher(key, data) == enciphered_data, i.e. guess both the content of the data and the key, which seems like it would take an incomputable amount of time, especially if data is, say, a 64-bit block.

Is brute-forcing such a large space truly the only option?

Answer 1

Usually, the brute-force attack is performed with known-plaintext where a message $m$ and its ciphertext $c = \operatorname{XTEA}(k,m)$ is available. Indeed, one may need more than one to exactly found the key since a key selects permutation and at the point $m$ there can be more than one permutation selected by different keys that maps to the same ciphertext.

In ciphertext only attack, you may need some additional information to test the outcome, the candidate plaintext. Options are;

1. The encoding : for example in ASCII encoding the MSB is usually 0.

2. The padding : Block cipher if not used in streaming mode like the CTR mode, then a padding is needed. The padding can be used to identify the correctness. The padding can be PKCS#5 as in the RSA DES challenge which was a known plaintext attack and bruteforced.

3. The language : if the target language is known than the current plaintext during the search can be tested for words like the string command in the Linux

Each of the options can increase your change. Having more ciphertext messages can eliminate more false candidate. Keep in mind that, however, if an option is not 100% correct, that can cause to find the key.

If there is no options, there is no test a validity of a candidate key.

In academical history, T.Siegenthaler use ASCII to break combined LFSR with a ciphertext only attack.

• Decrypting a Class of Stream Ciphers Using Ciphertext Only

Is brute-forcing such a large space truly the only option?

If there is no weakness in the algorithm, the above is the only way. For the attacks in XTEA, listed from the Wikipeida

• In 2004, Ko et al. presented a related-key differential attack on 27 out of 64 rounds of XTEA, requiring $2^{20.5}$ chosen plaintexts and a time complexity of $2^{115.15}$ (Ko et al., 2004).
• In 2009, Lu presented a related-key rectangle attack on 36 rounds of XTEA, breaking more rounds than any previously published cryptanalytic results for XTEA. The paper presents two attacks, one without and with a weak key assumption, which corresponds to $2^{64.98}$ bytes of data and $2^{126.44}$ operations, and $2^{63.83}$ bytes of data and $2^{104.33}$ operations respectively.

Those require much more than one known-plaintext to execute an attack, and this is common if you are executing a brute force attack.

And, final note

If a cryptographic algorithm or scheme is breakable with ciphertext only attack, turn back an run.

We need at least CPA secure ciphers in modern cryptography.