Lecture 3 Important Terms part3

8-Security of Algorithms.
Different algorithms offer different degrees of security; it depends on how hard they are to break. If the cost required to break an algorithm is greater than the value of the encrypted data, then you’re probably safe. If the time required to break an algorithm is longer than the time the encrypted data must remain secret, then you’re probably safe. If the amount of data encrypted with a single key is less than the amount of data necessary to break the algorithm, then you’re probably safe.
I say “probably” because there is always a chance of new breakthroughs in cryptanalysis. On the other hand, the value of most data decreases over time. It is important that the value of the data always remain less than the cost to break the security protecting it.
Lars Knudsen classified these different categories of breaking an algorithm. In decreasing order of severity :
1.  Total break. A cryptanalyst finds the key, K, such that DK(C) = P.
2.  Global deduction. A cryptanalyst finds an alternate algorithm, A, equivalent to DK(C), without knowing K.
3.  Instance (or local) deduction. A cryptanalyst finds the plaintext of an intercepted ciphertext.
4.  Information deduction. A cryptanalyst gains some information about the key or plaintext. This information could be a few bits of the key, some information about the form of the plaintext, and so forth.
An algorithm is unconditionally secure if, no matter how much ciphertext a cryptanalyst has, there is not enough information to recover the plaintext. In point of fact, only a one-time pad is unbreakable given infinite resources. All other cryptosystems are breakable in a ciphertext-only attack, simply by trying every possible key one by one and checking whether the resulting plaintext is meaningful. This is called a brute-force attack .
Cryptography is more concerned with cryptosystems that are computationally infeasible to break. An algorithm is considered computationally secure (sometimes called strong) if it cannot be broken with available resources, either current or future. Exactly what constitutes “available resources” is open to interpretation.
You can measure the complexity of an attack in different ways:
1.  Data complexity. The amount of data needed as input to the attack.
2.  Processing complexity. The time needed to perform the attack. This is often called the work factor.
3.  Storage requirements. The amount of memory needed to do the attack.
As a rule of thumb, the complexity of an attack is taken to be the minimum of these three factors. Some attacks involve trading off the three complexities: A faster attack might be possible at the expense of a greater storage requirement.
Complexities are expressed as orders of magnitude. If an algorithm has a processing complexity of 2128, then 2128 operations are required to break the algorithm. (These operations may be complex and time-consuming.) Still, if you assume that you have enough computing speed to perform a million operations every second and you set a million parallel processors against the task, it will still take over 1019 years to recover the key. That’s a billion times the age of the universe.
While the complexity of an attack is constant (until some cryptanalyst finds a better attack, of course), computing power is anything but. There have been phenomenal advances in computing power during the last half-century and there is no reason to think this trend won’t continue. Many cryptanalytic attacks are perfect for parallel machines: The task can be broken down into billions of tiny pieces and none of the processors need to interact with each other. Pronouncing an algorithm secure simply because it is infeasible to break, given current technology, is dicey at best. Good cryptosystems are designed to be infeasible to break with the computing power that is expected to evolve many years in the future.