Proven security

Proven security is a concept in modern cryptology . In the history of cryptography there are many examples of systems that were believed to be secure by their inventors but could nonetheless be broken. It is therefore desirable to convince yourself of the security of a system by means of a formal proof . To do this, both the cryptographic system and the security to be achieved must be formalized.

Perfect security

Claude Shannon defined perfectly secure encryption methods in 1949 and showed the conditions under which they exist. A perfectly secure encryption process is characterized by the fact that a ciphertext generated with it does not allow any conclusions to be drawn about the corresponding plain text. With such a method, it is mathematically proven that an attacker who knows the ciphertext cannot gain any further information about it apart from the length of the plaintext. He cannot decrypt the ciphertext or even break the entire procedure. Shannon was able to prove that the one-time pad is perfectly safe.

Asymptotic security

An information-theoretical proof guarantees security against attackers who are not limited in their computing power. Such an attacker could, however, simply try out all possible keys with a method like AES . With real computers that would take too long. To make the concept of security more realistic, the attacker is therefore limited in his computing power, depending on the key length used (or a security parameter ). Then it is shown that the system is secure against such an attacker. It only shows that the effort for an attacker grows much faster than the effort for the user. By choosing the appropriate key length, attacks can be practically ruled out. However, the key length must be adapted to the available computing power, which is one of the reasons why the key length of 768 bits previously used for RSA is now considered unsafe. Because only the asymptotic behavior is examined here , the security is also called asymptotic or complexity-theoretical .

For most cryptographic methods, the security of the system cannot be proven without further assumptions. One of the earliest assumptions used is that the factorization problem is severe. The proof of security is then a reduction between breaking the system and solving the problem. For example, it can be proven that any attacker who can calculate the secret one from the public key of the RSA cryptosystem can also solve the factorization problem (more precisely, an efficient solver can be constructed from a successful attacker). Since, according to the assumption, there cannot be such a solver, there cannot be a successful attacker either. Security here no longer means that it is completely impossible for the attacker to break the system, but that this is practically impossible. In other words, its probability of success is negligibly small.

Concrete security

In the case of asymptotic security proofs, it is only shown that a system is secure above a certain value of the security parameter (the key length). If you want to instantiate such a system, you have to choose a specific parameter. For this purpose, the proof must be provided more precisely and a narrow upper limit must be specified for the attacker's probability of success depending on the resources used (runtime, number of oracle inquiries). If such a dependency can be specified, one speaks of concrete security.

example

The simulator S generates the IND-CPA “interface” for the attacker A from the problem P.

The Elgamal encryption scheme is IND-CPA -safe assuming that the Decisional Diffie-Hellman problem is difficult. The proof consists of a reduction in which a solver for the DDH problem is constructed from every successful attacker against the security of the system. Because DDH was believed to be severe, it is clear that such an attacker cannot exist.

There is an attacker A, of whom nothing is known, except that he wins the IND-CPA experiment against ElGamal. So when it receives a public key it issues two messages . If you then give him the encryption of one of the two under the public key, he can with probability say which message was encrypted. ${\ displaystyle m_ {0}, m_ {1}}$ ${\ displaystyle 1/2 + \ epsilon}$

From this attacker A one now constructs a solver S for DDH as follows. This receives a description of a group with producer and a triple as input. S now simulates the key generation and gives A as the public key. S does not know the corresponding secret key, but A cannot know that. A outputs two messages after a while . S must now simulate the encryption. He chooses a random bit and sets the cipher . The attacker A then returns a bit . If so, the cipher cannot be distinguished from a normally generated one. If there is a random group element, the attacker can only guess and wins with probability 1/2. The strategy of S is therefore as follows: If A was successful and returns the correct bit, S suspects that . If A is wrong, S suspects that it was a random element. The probability of success of S is then . ${\ displaystyle g}$ ${\ displaystyle (g ^ {x}, g ^ {y}, g ^ {z})}$ ${\ displaystyle g ^ {x}}$ ${\ displaystyle m_ {0}, m_ {1}}$ ${\ displaystyle b}$ ${\ displaystyle g ^ {y}, g ^ {z} m_ {b}}$ ${\ displaystyle b '}$ ${\ displaystyle g ^ {z} = g ^ {xy}}$ ${\ displaystyle g ^ {z}}$ ${\ displaystyle g ^ {z} = g ^ {xy}}$ ${\ displaystyle g ^ {z}}$ ${\ displaystyle 1/2 + \ epsilon / 2}$

discussion

The paradox of provable security is that a system proven to be secure is not necessarily really secure. This is because several assumptions and formalizations are necessary to prove a proof. The system, the attacker and the security goal must be formally described (such as IND-CPA security for encryption) and the evidence is only a reduction of a problem whose severity was assumed. An attacker who is stronger than the one assumed in the evidence can potentially break the system. It can also happen that the security goal has not been sufficiently formulated, i.e. a lesser success is sufficient for the attacker. If the security goal is, for example, "No attacker should be able to derive plain text from a ciphertext", the evidence does not make a statement about an attacker who only wants to learn the first three letters of the plain text. Another problem is that the real cryptosystem does not exactly map the formal one, because mistakes were made either in the implementation of the formal or in the formalization of an existing system. A rather unlikely way to break the system anyway is to solve the math problem that underlies security. Finally, of course, the proof can simply be wrong. Despite these numerous problems, evidence of security is a valuable tool in modern cryptology.

Individual evidence

^ Claude Shannon: Communication Theory of Secrecy System . In: Bell System Technical Journal . tape 28 , no. 4 , 1949, pp. 656-715 ( netlab.cs.ucla.edu [PDF; 549 kB ]).

[1] Claude Shannon: Communication Theory of Secrecy System . In: Bell System Technical Journal . tape 28 , no. 4 , 1949, pp. 656-715 ( netlab.cs.ucla.edu [PDF; 549 kB ]).