Cryptography for Mere Mortals #2
An occasional feature, Cryptography for Mere Mortals attempts to provide clear, accessible answers to questions about cryptography for those who are not cryptographers or mathematicians.
Q: How does one “attack” encryption?
A: Either by:
1) analyzing a large number of ciphertexts and matching plaintexts and looking for patterns, or
2) brute force—trying all the possible keys.
Note that the analysis approach involves some “cheating”: it’s not particularly likely that a random attacker will have this much information to work with. But if the crypto resists analysis even under those circumstances, it’s at least as secure in a more realistic scenario.
What does this analysis consist of? Consider a simple substitution algorithm, one that replaces 1 with 9, 2 with 8, and so forth. Given a large number of SSNs, one might be able to draw some conclusions based on the fact that some SSN ranges are not valid, and thus figure out the substitution. That’s how you do cipher puzzles in the newspaper: you look for two-letter words and see if “an”, “of”, “if” and so on make sense for them, you look for the commonest character and see if it works to be “e”, and so forth. Now, with AES or DES or any modern algorithm, that doesn’t help much, since they’re very far from being simple substitutions. But people who are much smarter than your humble correspondent can apparently start to discern patterns from some weak algorithms, if they have those large numbers of plaintexts and matching ciphertexts. This vastly oversimplifies the analysis process, but the basic principles are similar.
The brute force approach is why we use keys of 128 bits or longer: because with current technology, trying all the possible keys (or even the average of half of all possible keys) will take until the heat-death of the universe, by which time that SSN is likely not of much interest.
With Format-Preserving Encryption, the brute force approach is even less useful. As noted in the previous entry in this series, Format-Preserving Encryption makes it even harder to discern keys that are invalid: if you know you’re decrypting an SSN, with traditional AES you can ignore any keys that don’t produce a nine-digit number on decrypt. But with FPE, they all produce nine-digit numbers, so you lose that filtering ability. Sure, you can discard the outputs that fall into the unassigned SSN ranges, but that’s a small percentage—far fewer than the number of non-numeric outputs that traditional AES would have produced.