Security properties of cryptographic methods

In cryptology and cryptanalysis one is interested in the security of cryptological procedures. In general, it is pointless to describe a process as “secure” without defining the concept of security in more detail. A security term does exactly that: It indicates which type of security can be expected against which type of attack. It is also important for a security proof to have a precise definition of the security to be proven.

Security terms for asymmetric encryption methods

Most security terms for public key encryption methods consist of two components. The first describes the target of the attack to be achieved, a security property that the attacker wants to violate (e.g. ciphertext indistinguishability ), the second describes the capabilities of the attacker class under consideration (e.g. chosen plain text attacks ). If no attacker from the class against a certain method (e.g. the RSA encryption method ) reaches the target, the method fulfills the security concept (in this case ciphertext identinguishability against chosen plain text attacks, IND-CPA for short).

Security goals

Two security goals for asymmetric encryption methods are quite obvious: It should not be possible to calculate the secret key from the public one (asymmetry), and nobody should be able to read encrypted messages without the secret key (one-way property).

Unbreakability (UB)

An attacker can break the asymmetry or public-key property of an asymmetric procedure by calculating the secret key from the public one. This security goal is the defining property for all asymmetrical procedures.

If an attacker breaks the asymmetry of the procedure, he has broken all other security goals as well, because he can use the secret key together with the decryption algorithm to decrypt ciphers as if he were the recipient. For this reason, asymmetry is as unbreakability and her break as a complete break called (Total Break).

One-wayness (OW)

An attacker breaks the one- way property of an encryption method if he can determine the plaintext associated with any cipher.

These two security goals are necessary, but too weak for a pure encryption system. An attacker only breaks the one-way property if he can calculate the complete plaintext. However, it is a desirable property that no attacker can calculate any information about the plaintext. This is only possible if the encryption method is probabilistic, because otherwise the attacker can encrypt messages himself and create a ciphertext table that enables him to decrypt messages more frequently. There are three essentially equivalent formulations for these properties. Any attacker who breaks the one-way property also breaks the following security goals.

Semantic Security (SEM)

An encryption method is semantically secure if every attacker can derive any information that he can derive from a cipher about the message if he only knows the length of the cipher. A cipher reveals nothing about a message other than its length.

Real-or-random security (ROR)

An encryption method is ROR-safe if no attacker can distinguish whether a cipher is encrypting a plain text of his own choice or a random message of the same length.

Ciphertext Indistinguishability (IND)

→ Main article : Ciphertext Indistinguishability

An encryption method is indistinguishable from ciphers if no attacker can decide which of two messages of the same length (chosen by himself) a cipher should be encrypted. The security goals of semantic security, real-or-random security and indistinguishability of ciphers are equivalent.

A different property is required for some applications. An example of such an application is an auction. Here it can be sufficient for an attacker to submit a bid that is higher than that of a competitor, even if he does not know anything about his bid.

Non-Malleability (NM)

An encryption method can not be deformed if no attacker can change a cipher in such a way that the plaintexts belonging to the two ciphers are in a relation chosen by him (at least not more often than would be the case with randomly selected plaintexts). Thus, an attacker breaks the security NM when, for example, a message encrypted, from the resultant ciphertext is a cipher text generated and for which decryption is considered . Every successful IND attacker also breaks non-malleability. ${\displaystyle m_{1}}$ ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$ ${\displaystyle m_{2}}$ ${\displaystyle m_{1}<m_{2}}$

Attacker models

Attackers can be classified into three categories according to their strength:

Adaptive chosen plaintext attack (CPA)

With an asymmetric procedure, the attacker always has access to the public key. So he can encrypt messages himself at will. This is known as a free text attack .

Chosen non-adaptive ciphertext attack (CCA1)

The attacker has access to a decryption oracle that decrypts the ciphers chosen by him. He can use this oracle to prepare for the decryption of ciphers.

→ Main article : Chosen ciphertext attack

Adaptive chosen ciphertext attack (CCA2)

The attacker has access to a decryption oracle and is even allowed to choose the cipher depending on the cipher to be decrypted. However, he is not allowed to decrypt the cipher itself. This theoretical restriction is necessary because the concept would otherwise be unsatisfactory.

The practical relevance of this attacker model was demonstrated by Daniel Bleichenbacher's attack against the PKCS # 1 standard .

Relationships between security concepts

Security terms are made up of security objectives and attacker strengths and are usually defined as an experiment or game. In the IND-CCA2 experiment, the attacker gains access to the public key and a decryption oracle (CCA2). Then he has to find two messages of the same length so that he can distinguish between an encryption of and an encryption of . The weaker the security goal and the stronger the attacker, the stronger the security concept. Security is “better” when it holds up against stronger attackers or when the attacker himself cannot achieve low-set goals. ${\displaystyle m_{0},m_{1}}$ ${\displaystyle m_{0}}$ ${\displaystyle m_{1}}$

It follows that both NM-CPA and IND-CCA1 are stronger than IND-CPA. However, the two terms are independent of each other, NM-CPA is neither stronger than IND-CCA1, nor vice versa. The strongest term that can be formed is NM-CCA2. NM-CCA2 is equivalent to IND-CCA2 and ROR-CCA2.

Transformations

There are several transformations in the Random Oracle model that turn an IND-CPA-secure process into an IND-CCA2-secure process.

Security terms for digital signatures

The security terms for digital signatures are structured in the same way as for encryption and consist of a part that describes the security goal and a description of the attacker's strength.

Security goals

Similar to the security goals for encryption, there is also a hierarchy here.

Unbreakability (UB)

Similar to other public key methods, the asymmetry in digital signatures guarantees that the secret signature key cannot be calculated from the public verification key . An attacker who breaks the asymmetry also breaks all other security goals.

Universal Unforgeability (UUF)

An attacker breaks the general unfalsifiability if he can generate a valid signature for a given message.

Selective Unforgeability (SUF)

An attacker breaks the selective infallibility if he can generate a valid signature for a message that he has chosen himself without knowing the verification key . Any attacker who breaks the UUF also breaks the SUF.

Existential Unforgeability (EUF)

A signature process can not be falsified existentially if no attacker can generate any message signature pair. Any attacker who breaks the SUF also breaks the EUF.

Non-Malleability (NM)

A signature method can not be deformed if no attacker can generate another valid signature for the same message for a given message signature pair.

Attacker models

There are three classic attacker models, but there are variations. In order of increasing strength of the attacker, these are:

Key-only attack (KOA)

The attacker only has the verification key. This is the minimum attacker model for a public key process.

Known Message Attack (KMA)

The attacker is familiar with specified plain text signature pairs. This must be assumed if a signature process is used, since signatures are not secret.

Adaptive chosen message attack (CMA)

The attacker has access to a signature oracle with which he can sign messages of his choice. With the term EUF-CMA this leads to a differentiation. In the standard definition, the attacker must produce a signature for a message for which he has not yet received a signature from the signature oracle. In a stronger variant (sEUF-CMA) it is sufficient if he produces a signature for any message that he has not already received from the signature oracle. A message signature pair is therefore valid here even if another signature is already known for the message.

Individual evidence

1. ^ Shafi Goldwasser , Silvio Micali : Probabilistic encryption . In: Journal of Computer and System Sciences . tape 28 , no. 2 , 1984, p. 270–299 ( with.edu [PDF]).
2. ^ Daniel Bleichenbacher: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS # 1 . In: CRYPTO '98 . 1998, p. 1-12 .
3. ↑ ^{a b} Mihir Bellare , Anand Desai, David Pointcheval, Phillip Rogaway: Relations Among Notions of Security for Public-Key Encryption Schemes . In: Advances in Cryptology - Proceedings of CRYPTO '98 . 1998, p. 26-45 ( ens.fr ).
4. ↑ Eiichiro Fujisaki and Tatsuako Okamoto: How to Enhance the Security of Public-Key Encryption at Minimum Cost (English) . In: PKC 99 , Springer Verlag, 1999, pp. 53-68. 
5. ↑ Pascal Paillier and David Pointcheval: Efficient Public-Key Cryptosystems provably Secure Against Active Adversaries (English) . In: ASIACRYPT 99 , Springer Verlag, 1999, pp. 165-179. 
6. ↑ Shafi Goldwasser, Silvio Micali, Ronald Rivest : A digital signature scheme secure against adaptive chosen-message attacks . In: SIAM Journal on Computing . tape 17 , no. 2 , 1988, p. 281-308 .