Is it generally possible to employ brute force methods when the encryption scheme is not known? Why or why not?

Question

Lets say you are presented with an encrypted string of bits or text, and no other information. What would be necessary before you could apply brute force methods to decrypting the string? How would a cryptanalyst approach such a case? (lets assume the conditions are such that the encryption can be brute forced in a reasonable time frame).

Answer 1

This is called ciphertext-only cryptanalysis^*, and it's pretty difficult unless the cipher is quite weak. Therefore, the first priority for a cryptanalyst in such a situation is usually to try to find more information about the algorithm. Fortunately (for the cryptanalyst), as Kerckhoff's principle suggests, there are often ways to find out how the algorithm works. For example:

• If the string was encrypted (or meant to be decrypted) by a computer program, one could try to obtain a copy of the program and inspect it in a debugger to determine the algorithm.

• Similarly, if the encryption and/or decryption was done by a hardware device, one could try to obtain such a device and reverse engineer it.

• One might also try to obtain a copy of a manual explaining how the cipher is used, or design documents explaining how it works, or even look for hints in public articles written about it. Or one could even try to capture someone who knows how the cipher works and interrogate them.

That said, there are some things that can be done even without knowing the algorithm in advance, particularly if the cipher is a simple one:

• One can look at the character frequencies in the cipher, or more generally at $n$-gram frequencies or at correlations between characters $n$ positions apart. Many simple classical ciphers can reveal characteristic patterns under such an examination, allowing the algorithm and perhaps eventually the key to be guessed.

• More generally, one can look for patterns that may reveal information about the algorithm. For example, modern ciphers usually operate on bytes, or blocks of bytes, while classical ciphers typically use a smaller alphabet of letters and maybe a few symbols. Some modern operating modes may reveal the block size of the cipher; also, comparing the length of the ciphertext with that of the plaintext, if known, may reveal the presence (or absence) of an IV and/or a MAC. And sometimes, e.g. when used in ECB mode, even the output of a modern block cipher may have patterns that can reveal information about the plaintext, and, incidentally, the cipher and mode used.

• Finally, one can simply try known algorithms and variants of them and see if they work. This works particularly well if one has already narrowed the choices down somehow, and/or has additional information available (such as knowing the key but not the algorithm).

For an interesting historical example, see the cryptanalysis of the Enigma (and of the other WWII axis ciphers), which provides examples of several of these methods and their combinations.

^{* The term "ciphertext-only cryptanalysis" is also used for the broader situation where the algorithm is known but no information about the key or the plaintext is available. Even that can be quite challenging, although obviously easier than if even the algorithm used is uncertain.}

Answer 2

If you can't tell what function was applied to create the cipher text, your search space is as many bits as the message. It's the perfect secrecy achieved with a one time pad. (x + y = z, given z what are x and y?) During an exhaustive search the attacker could find as many messages as they were willing to compute, but they will never know which one was right.

That being said, the added clause "lets assume the conditions are such that the encryption can be brute forced in a reasonable time frame" really means you just confine your search to any ciphers that are insecure enough to be cracked in the chosen time frame.

Ilmari's answer is way cooler though. :-)