Security models

To prove the security of the cryptosystems, we need a formal security model which must specify the interaction mechanism followed by an adversary/ attacker to interact with the legitimate users of that cryptosystem. Further, it must specify what the adversary should achieve to break the cryptosystem [11]. For example: In an encryption system the adversary may want to find the ciphertext of the messages of her choice by using something called the encryption oracle; this represents the interaction made by the adversary with the cryptosystem. Secondly, in order to break the cryptosystem, the adversary must correctly identify that the challenge ciphertext (for which the adversary has never queried before) is the encryption of the plaintext message earlier chosen by the adversary.

Security goals of a public-key cryptosystem

For any public-key encryption scheme, the following security goals must be kept in mind while designing a cryptosystem:

  • • Indistinguishability of encryptions/ciphertexts: This is also known as semantic security and it states that given the encryption of two messages or two ciphertexts, the adversary should not be able to distinguish between them. Simply, we can say that given a challenge ciphertext, the adversary should not be able to get any information about the underlying plaintext.
  • • Non-malleability: It requires that given the challenge ciphertext, the adversary should not be able to convert it into another valid ciphertext such that the plaintexts of these two ciphertexts are meaningfully related to each other.

Security attacks on a public-key cryptosystem

Depending upon the level of facilities provided to an adversary, the attacks on public-key cryptosystems are divided into three main categories:

  • • Chosen-plaintext attack (CPA): The facility given here is that the adversary knows the public key. The public key can be used to just encrypt the messages of her choice and the cryptography community says that the adversary has access to the encryption oracle. Later, the adversary chooses two messages of her choice, called challenge messages, which she sends to the challenger. The challenger then returns the challenge ciphertext to the adversary. Now, we say that a public-key cryptosystem is secure under CPA if it is hard for the adversary to relate the challenge ciphertext with its underlying plaintext. The restriction on the adversary is that she cannot generate the ciphertexts (have access to the encryption oracle) for the challenge messages of her choice. Here, we have restricted the power of adversary to the maximum extent. But in practice, the adversary can have much more power and thus CPA secure schemes may not be secure in practical scenarios.
  • • Non-adaptive chosen-ciphertext attack (CCA1): Here, the power of the adversary is increased by providing her access to the decryption oracle in addition to the facilities provided in CPA security. She can use it to get the decryption of ciphertexts of her choice. However, a restriction has been placed on when she can use the decryption oracle. Here, the adversary can use the decryption oracle only before the challenge ciphertext is produced.
  • • Adaptive chosen-ciphertext attack (CCA2): The restrictions of CCA1 security are completely relaxed and now the adversary can have access to the decryption oracle even after she gets the challenge ciphertext. But the obvious restriction remains that she cannot query the decryption oracle for the challenge ciphertext.

The public-key encryption schemes which are indistinguishable under CCA2 are assumed to be most secure. The reason is obvious because here the adversary can operate with full power and yet she cannot distinguish that the challenge ciphertext is the encryption of which two challenge messages generated by her.

Mathematically, this whole definition of IND-CCA2 (indistinguishability against CCA2) can be modeled as a game between the challenger, C, and an adversary, A as follows:

  • • Setup: C runs KG(X) —> [pk, sk), keeps sk and gives pk to A.
  • • Phase 1: Au[pk, C) —> m and outputs two messages {m0, mu state] of her choice but she had not queried decryption oracle for them. Au denotes adversary’s access to decryption oracle.
  • • Challenge: C selects {0,1) —> b, and runs encryption algorithm to get challenge ciphertext, E(pk, mh) —> C
  • • Phase 2: Au(pk, C) -» m but С Ф C*.
  • • Guess: A(C', m0, mu state) —> b'.

Adversary wins the game if b' = b, i.e. when its guess is correct. Since there are

two messages, therefore with a probability of anyone can guess. Hence, we

need to subtract this probability from the total probability of correctly guessing b and this is known as the adversary’s advantage, Aaft/f'L)~CCA2 against IND-CCA2.

The cryptosystem is said to be secure against CCA2 attack if the advantage of the adversary in winning the game is negligible.

ElGamal cryptosystem

The EIGamal encryption was invented in 1985 by Taher EIGamal [12] and it is very similar to the Diffie-Hellman key-exchange algorithm with a slight reordering of steps as shown in Figure 2.3.

EIGamal cryptosystem

Figure 2.3 EIGamal cryptosystem.

Here, the key Ke is called the ephemeral key and exists only for a short duration, i.e. when Alice wants to send some new message then at that time a different i value is selected which will result in a different ephemeral key. The key Km is called the session key, which is just like the key КАц in the DH key-exchange algorithm. The ElGamal encryption scheme is a probabilistic encryption scheme unlike the schoolbook RSA encryption scheme and this feature comes into the picture by choosing a random i value every time the encryption algorithm is called, whereas in RSA the encryption of the same message is always fixed.

Correctness Proof: Bob computes, У • Kllmodp = X ■ Km (KEd)~'modp = X ■ p' • (a')”'d modp = Xmodp.

We will present the detailed security analysis of this scheme in Chapter 4 where we will discuss provable security in detail.

< Prev   CONTENTS   Source   Next >