jul 21, 2016

If we don’t carefully distinguish between **necessary** and **sufficient** when we are analyzing information assurance systems, we may become dangerously confident in a system that is actually quite weak.

Cryptography enthusiast Edgar Allan Poe wrote, in “A Few Words On Secret Writing” in *Graham’s Magazine* in July 1841:

“Few persons can be made to believe that it is not quite an easy thing to invent a method of secret writing which shall baffle investigation. Yet it may be roundly asserted that human ingenuity cannot concoct a cipher which human ingenuity cannot resolve.”

A *monoalphabetic substitution cipher* is a simple pencil-and-paper system with an impressively long name. First, write the alphabet as the first line of a table. Then, write a second line where you have randomized the order. I used the `shuf`

program to randomize the list:

Cleartext: | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |

Ciphertext: | T | W | K | D | E | I | F | H | O | X | Z | B | G | U | A | M | Y | R | L | C | J | V | S | Q | P | N |

Encrypt by scanning through your input, looking up each ‘cleartext’ letter in the top row of this table and writing down the corresponding ciphertext letter below it. Decrypt by finding the ciphertext letter in the bottom row and writing the ‘cleartext’ letter above it. (Have a second version of the table with the columns sorted by the ciphertext line to make this much easier.)

A naïve analysis makes this look impressively secure. There are this many possible permutations of a 26-character alphabet, and each is effectively an encryption key:

26! = 1×2×3×…×25×26 = 403,291,461,126,605,635,584,000,000

That’s a little larger than the number of possibilities for an 88-bit key:

2^{88} = 309,485,009,821,345,068,724,781,056

26! = 403,291,461,126,605,635,584,000,000

2^{89} = 618,970,019,642,690,137,449,562,112

It’s dangerously tempting to simply compare the numbers of possible keys. Since 56 + 32 = 88, and 2^{32} is 4,294,967,296, we might conclude that this would be over 4 billion times stronger than DES, and a little over 2^{8} or 256 times stronger than the 80-bit Skipjack cipher designed by the NSA for the Clipper chip.

Well, sure, *if* the only way to attack the problem was to try every possible permutation while checking for readable output, then a brute-force search for the permutation would take that much more work than trying all possible DES or Skipjack keys. But we don’t have to!

Edgar Allan Poe’s story *“The Gold Bug“* contains a good explanation of how to ‘cryptanalyze’ and fully break a monoalphabetic substitution cipher when you have only a few dozen characters of ciphertext.

My description above intentionally falls into the logical trap of only considering an attack that would be **sufficient** to solve the problem, while Poe’s story describes a much easier approach that uses logic and statistics to limit our work to what is **necessary.**

Let’s consider RSA. Its security is based on the difficulty of factoring large numbers. We say things like this:

If you could factor a 300-digit number into its prime factors, you could derive an RSA private key from the corresponding public key. Prime numbers and factoring have fascinated mathematicians since ancient Greece, but we don’t know of a practical way of solving the factoring problem on the scale of 2048 to 4096 bit RSA keys. Therefore we don’t have to worry about an attacker doing it.

Well, sort of. The statements about factoring are all correct. However, while solving the factoring problem would be *sufficient* to break RSA, is it really *necessary?*

It is, as far as we know, but maybe there’s an easier way to break RSA that no one has yet thought of.

See the recent paper by Cormac Herley, “The Unfalsifiability of Security Claims.” He writes: *“There is an inherent asymmetry in computer security: things can be declared insecure by observation, but not the reverse. There is no observation that allows us to declare an arbitrary system or technique secure.”* The result is that new security measures may be added “just in case” but there is no way to formally show that one is unhelpful. Furthermore, *“deciding the relative importance of defensive measures reduces to a subjective comparison of assumptions.”*

If these types of issues interest you, check out Learning Tree’s System and Network Security Introduction course.