The Basics of Crypto 3: What is Security in Cryptography

The short answer to this is something is considered secure in cryptography when breaking it is impractical in a reasonable time frame. So say for example it will take approximately one billion years to crack the key of some cryptosystem then it can be considered secure as nothing that is relevant today will be relevant in a billion years. Obviously we will get more in depth into this, but the above summary is accurate and if that is all you came for feel free to skip the rest.

Informational Security

Informational security can be described as theoretical security and something can be considered to be informationally secure if it can never be broken regardless of how much time and computational power the attacker has. So if an attack would take a billion years to succeed then it is not informationally secure. An example of one informationally secure cryptosystem is the one time pad. It is informationally secure because every potential plaintext is equally likely so even brute forcing the entire key space would yield nothing of value. Some additional reading material can be found here.

Computational Security

Computational security can be described as practical security and the example in the opening paragraph is of a computationally secure cryptosystem. A cryptosystem that cannot be broken in the time the encrypted data is actually useful can be considered to be computationally secure. Obviously there needs to be a way of measuring how computationally secure something is so a user can select the correct cryptosystem for the task at hand, selecting a cryptosystem designed to protect information that has a lifespan of less than ten seconds should not be used for long term encrypted file storage etc.

We measure computational security in bits. We can say that a cryptosystem that takes X operations to successfully attack is described as X-bit security. So if a cryptosystem takes 1000 operations to attack it would be considered to be 9-bit secure. You come to the number 9 in the previous example for 9-bit secure by taking the binary logarithm of the number of operations.

Hint: Binary logarithm just means how many digits would it take to express the decimal number in binary format. So for example if it took 5 operations to break the system then in binary 101 = 5 so the system would be 3-bit secure.

It is important to remember that key size is not the equivalent of bit security. Bit security is a representation of the number of operations needed to break a cryptosystem, as an example RSA using a 512 bit key size provides less than 100-bit security, 100-bit security is more than strong enough to withstand attack for far longer than is necessary for any practical use but it is not 512-bit security.

Bit security does not give a completely accurate representation of how long it will take to break a cryptosystem. One thing to take into account include computational time of each operation, for example if algorithm A takes twice as long to complete an operation as algorithm B but has a bit security that is 75% of algorithm B's it will take longer to break algorithm A then algorithm B. Other things include parallelism, memory requirements, if precomputation such as hash tables are applicable etc.

Heuristic Security

Sometimes no security proofs are applicable for an algorithm which can be for any number of reasons. There is no security proof for the commonly used AES (advanced encryption standard) system which people use to securely encrypt communications every day in a variety of ways.

However in such cases we can be reassured by the fact that vast numbers of professional crypt analysts have spent vast amounts of hours attempting to break the system, published the findings and not been successful. In these situations we can say that a cryptosystem is heuristically secure. Can we be certain these systems are secure? Obviously not certain but we can be sure beyond any reasonable doubt.

In conclusion for most situations you will be choosing between an encryption scheme with either 128 bit or 256 bit security, sometimes you will have access to higher and occasionally the options for 80 or 64 bit will not have been disabled yet. For the vast majority of situations going for 256 bit and above is more than secure enough for the vast majority of uses, 80 and below are generally not secure enough for real world applications.