2024.06 Vol.1

A Line in the Sand

When we analyze the security of a cryptographic scheme, we have to draw somewhat arbitrary lines in the sand. If an adversary had unlimited computation power, any practical encryption scheme is broken. We could use perfect schemes, like a one-time pad, but these are not practical because secret keys need to be as long as the messages they encrypt. Luckily, no one has unlimited computational power. But how do we measure the strength of a scheme? How much power can an adversary throw at a scheme and have it still be considered secure?

The line, which is hand-wavy and kinda just makes things comparable, we have drawn is at polynomial time. Noted as O(n^k) or poly(n). This line is arbitrary since there are other factors in justifying an attack by an adversary, but around this spot is where it becomes reasonable for an attack. An attack goes from negligible to non-negligible and should be considered a threat by a challenger. An attack that requires exponential O(2^n) time on the other hand, which is on the other side of the line, is considered negligible and not worth worrying about.

So why is this the spot where it becomes non-negligible? A cryptographic scheme is made up of tradeoffs to make it practical. Like mentioned above, we could use one time pads everywhere. But then we would need secret keys as big as the messages we want to encrypt and a way to transfer that information. That is tough to do without introducing new attack vectors, and given the size requirements, not very efficient. On the other end of the spectrum, we could use tiny keys to encrypt things, like only 2-bits. This is super cheap, but now an adversary could easily try all possible keys and read the ciphertext. A non-negligible attack. So we need something in the middle.

We can measure an attack by how much more effective it is than just guessing. So if an adversary is guessing the next bit of a message in an encrypted stream, can they guess correctly more than 50% of the time? How much more? That delta is what we call the adversary’s advantage. If an advantage is the reciprocal of a polynomial, 1/poly(n), the challenger (a.k.a. person using the scheme to encrypt data) is in trouble. This means an adversary could spend poly(n) time and have a chance at cracking the cipher, a non-negligible attack. The advantage needs to be on the other side of the line to be considered non-negligible, 1/superpoly(n).

The input n is usually the key size, the security parameter, of the scheme. This is a nice dial to turn for our spectrum of super-secure-but-impractical to super-not-secure-but-practical. Assuming all attacks of a scheme are considered non-negligible, the size of n only needs to be increased a tiny bit for the chances of the attacks to quickly go to 0. For example, many schemes use a 256-bit key which supplies a 2^256 key-space. A 256-bit (32-byte) key is still a relatively small amount of data, but the 1/superpoly(n) attacks would be totally ridiculous to attempt. It is a great middle ground.