Attacking a cipher, not knowing what the plaintext should look like – how do you know you’ve successfully decrypted the ciphertext?

Question

I have thought hard at the risks of data being cracked, it seems to me that the biggest risk is still down to absolute security of the key. On the presumption that the key will be kept secure then:

1. When hacking data how do you decide when you have successfully decrypted it without knowing roughly what it was it the first place?

2. If it was a text document would you need to know what language it was in?

3. Is it worth the minimal effort of making the users key more complex before using it to encrypt the data?

OK, I am very definitely not a mathematician, self evident I guess. I am using a library (Lockbox 3, https://sourceforge.net/projects/tplockbox) for the en/decryption and so am dependant upon the implementation being rock solid, another potential hole but I am casting no aspersions on the developers.

If one was attempting to crack the data are there mathematical mechanisms which can be used to decrypt without know anything about the data? I'm not asking for an algorithm, a yes or no will do.

I am asking for a complex subject to be made simple, however I am only after broad answers.

Answer 1

To address your first question, below are two fragments of text. One of them is gibberish I copied from /dev/urandom; the other is a literary quotation of the same number of octets. Each sequence of octets is written with graphic US-ASCII characters verbatim, and with control characters and non-US-ASCII octets written using \xAB hexadecimal notation. Can you tell which is which? (I randomized the order of fragments by flipping a coin, too.)

1. Kas siis selle maa keel / Laulutuules ei v\xc3\xb5i / Taevani t\xc3\xb5ustes \xc3\xbcles / Igavikku omale otsida?

2. \xe4xz\xfd\x11?\xbb\xfa\xeb\xb3a\x02Z\xe0\xdc_\xc3\xd3\x92\xa4ssa\x1an\xab\x1aa\x15\xa8\x02\xa5r}\xbe\x8f\xbc\n\xe5\x80\xd0B\xbeH\x17\xfex\x03\xd6\x99\x1d\xde$ \x89\xb4G\xd1\xea\xfb\x13@~\x87)\xb9\xd9\xcc\x18\x81\x01\x03$\xf23\x91\xb5c\xd0\xd1\x17\x11r\xee1"!\x03UiGB\x16\xc3{\xa0

(No cheating by knowing how to read Estonian! We can do the exercise with a different language if you do read Estonian.)

To address your second question, suppose you didn't know it were Estonian. It is highly unlikely that any language's orthography represented in octet strings has a uniform distribution, so you might, e.g., perform a statistical test to reject the null hypothesis of a uniform distribution, like a standard undergrad-statistician's $\chi^2$ test of bit or octet frequencies. There is no way to make it ‘more complex’—there are already $2^{256}$ possibilities, each one having equal probability.

Finally, to address you third question, your obligation to satisfy the AES-256 contract is to provide a key chosen uniformly at random from all $2^{256}$ possibilities. Normally you do this by asking your computer to do it for you, e.g. by calling on a hardware random number generator or by flipping a coin 256 times to seed your software random number generator.

If, however, you must deterministically derive a key from a password, then you should use a modern password-based key derivation function like scrypt or argon2. A PBKDF is expensive to evaluate, which means the cost of testing a guess for a password is high, with some variations in the cost model—older ones like PBKDF2 consider only time cost on a sequential machine, whereas newer ones like scrypt and argon2 consider area*time cost on an arbitrarily large piece of silicon that may have many CPUs or lots of memory. In some sense, a PBKDF behaves almost as if the password space were larger and the entropy of the password selection process were larger, because the expected cost of an attack is as much higher as if the entropy of the password selection process really were higher.

Answer 2

When hacking data how do you decide when you have successfully decrypted it without knowing roughly what it was it the first place?

In practice there are always large amounts of data that are available. For instance, most data is within a certain structure, for instance JPEG which has a JPEG header to distinguish.

Only if the data is random or close to random and small sized (only a few blocks) it will be hard to test if you've got the right key or not.

If it was a text document would you need to know what language it was in?

No, absolutely not. Text documents in a structured format (PDF, Word, OpenDocument etc.) are very easy to detect. ASCII text usually doesn't contain any data under 20 hex except line terminators or any data over 80 hex. Frequency analysis is easy to perform on the rest.

Knowing the language only makes it slightly easier to determine if you've succeeded or not.

Is it worth the minimal effort of making the users key more complex before using it to encrypt the data?

A real 256 bit key should have 256 bits of randomness. If it does it is impossible to make it any more complex.

A password must be incredibly strong to be used as source to derive a key with 256 bits of randomness. A password based key derivation function (or password hash, if you must) can only strengthen the key material by a constant amount.

However, 128 bits of true key strength is already impossible to break by brute force; 256 bits of key material is overkill until quantum computers become off age. The higher the complexity of the password the better, of course.

Having a key greater than 256 bits is pretty absurd, even if AES would allow it.