3

In a brute force program, sequential keys are tested against the public key in order to find the correspondent private key.

My question is, how is the test done with each key that let you conclude you have found the correct key to break into the encrypted text?

I suppose the text is read after each test and if some keywords are found you know this is the correct key, but if this is the way, is easy to counteract this technique scrambling the text with a traditional encryption algorithm and then with the symmetric key.

4

Ideally you need to have some idea of what you are looking for, but in most situations your plaintext should be relatively easy to distinguish. You might be able to identify it because it contains English-language words/grammar, or fits a known file format, for example.

Unicity Distance

If the ciphertext is short enough, the problem might be that there is more than one valid plaintext for a single ciphertext, although only one of these is the intended message. The additional valid keys are spurious. This is the concept of 'unicity distance': the length of a ciphertext needed such that there are no spurious keys.

Consider an attack on the ciphertext string "WNAIW" encrypted using a Vigenère cipher with a five letter key. Conceivably, this string could be deciphered into any other string — RIVER and WATER are both possibilities for certain keys. This is a general rule of cryptanalysis: with no additional information it is impossible to decode this message.

https://en.wikipedia.org/wiki/Unicity_distance

In the event that there are spurious keys, you need an even more specific idea of what you are looking for (e.g. keywords like you suggested).

Otherwise, as an attacker, you need enough ciphertext to meet the unicity distance in order to be sure.

For DES, the unicity distance is 8.2 bytes. For 128-bit ciphers, it is about 19 bytes.

This means that if you are trying to brute-force DES you need two ciphertext blocks. (DES's block length is 8 bytes.) Decrypt the first ciphertext block with one key after another. If the resulting plaintext looks like English, then decrypt the second block with the same key. If the second plaintext block also looks like English, you've found the correct key.

https://www.schneier.com/crypto-gram/archives/1998/1215.html#plaintext

Obscuring The Plaintext

Further obfuscating the plaintext, like you suggested, could therefore be effective in theory as long as the attacker did not have the requisite insider knowledge, and they were not checking for the obfuscation. This has to be carefully considered, because the attacker may have successfully found the correct key, and it's just a question of identifying that they have done so.

Also, we need to consider that certain (or many) methods of obscurity could be identifiable. Something trivial like Base64 encoding would be trivial to identify, and easily programmable as a check. Even if the plaintext was actually another ciphertext, there are potentially techniques for identifying these too (although they are not trivial) (e.g. http://practicalcryptography.com/cryptanalysis/text-characterisation/identifying-unknown-ciphers/).

As a result, although this has the potential to make an attacker's life more difficult, it is obscurity rather than security, and I would still ensure the level of encryption was suitable for purpose even if the plaintext was not obscured - i.e. I don't think it should be relied upon as part of the security mechanism.

1

You have to check the content of the decrypted test block. It depends on its content, how to that.

In the best case, it has some checksum or crc data in it (it is particularly useful in decrypting hard disks - the msdos partition table contains by default a checksum).

Alternatively, you have to do some different. Typically, you can check for headers, or other formats. In most cases it is not so hard.

The probability of a successful check on a random data block should be significantly smaller, as the probability of finding the key by a random search. I.e. if you have a 256-bit cipher, then the checks should give positive with a P << 2^-256 on random data.

The test code should be also fast, because it will run once after every block decode.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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