Brute force cryptanalysis
A naive view of simple substitution ciphers is that they are secure because there are 26! ways to permute the English alphabet, and so an attacker would have to try 26! 4 * 1026 permutations. However, such brute force is not required. In practice, simple substitution ciphers are breakable by hand in a few minutes, and you can find software that automates the process.
However, for modern encryption, apparently brute force is required. If you encrypt a message using AES with a 128-bit key, for example, you can't do much better than try 2128 keys. You might be able to do a little better, but as far as is openly known, you can't do orders of magnitude better.
Even for obsolete encryption methods such as DES it still takes a lot more effort to break encryption than to apply encryption. The basic problem with DES is that it used 56-bit keys, and trying 256 keys is feasible [1]. You won't be able to do it on your laptop, but it can be done using many processors in parallel [2]. Still, you'd need more than a passing curiosity about a DES encrypted message before you'd go to the time and expense of breaking it.
If breaking a simple substitution cipher really did require brute force, it would offer 88-bit security. That is, 26! roughly equals 288. So any cipher offering b-bit security for b > 88 is more secure in practice than breaking simple substitution ciphers would be in naive theory. This would include AES, as well as many of its competitors that weren't chosen for the standard, such as Twofish.
For all the block ciphers mentioned here, the number of bits of security they offer is equal to the size of the key in bits. This isn't always the case. For example, the security level of an RSA key is much less than the size of the key, and the relation between key size and security level is nonlinear.
A 1024-bit RSA modulus is believed to offer on the order of 87 bits security, which incidentally is comparable to 26! as mentioned above. NIST FIPS 184-5 recommends 2048 bits as the minimum RSA modulus size. This gives about 117 bits of security.
The security of RSA depends on the difficulty of factoring the product of large primes [3], and so you can compute the security level of a key based on the efficiency of the best known factoring algorithm, which is currently the General Number Field Sieve. More on this here.
Related posts[1] There are ways to do better than brute force against DES, if you have an enormous number of messages all encrypted with the same key.
[2] In 1998, the EFF built a machine called Deep Crack with 1,856 custom processors that could crack DES encoded messages in nine days, four and a half days on average.
[3] Nobody has proved that breaking RSA requires factoring. Thereis a variation on RSA that is provably as hard as factoring but as far as I know it has never been widely used.
The post Brute force cryptanalysis first appeared on John D. Cook.