Question

Part II: What is security and security in the NIST standard (HD tasks)

The importance of defining security is that, if you don’t know what security means, then you never know whether you have achieved your security goal or not in real applications. Let’s work through the strict definitions of security under different attack assumptions gradually and then see how the NIST standard applies the definitions (implicitly). From a high-level-point of view, any private key cryptosystem Π (for example, AES) can be defined as a collection of three algorithms (Gen, Enc, Dec) over the message space M (the symbol means “belong to”):

Gen (key-generation algorithm): an algorithm produces the key k;

Enc (encryption algorithm): takes key k and message mM as input; outputs

ciphertext c (c C, C is the ciphertext space);

Dec (decryption algorithm): takes key k and ciphertext c as input; outputs m or “error”.

The correctness of Enc and Dec indicates that, for all mM and k output by Gen, Deck(Enck(m)) = m.

First, let’s consider the case of security definition under Ciphertext-Only-Attack (in short as COA, and COA is also called eavesdropping attack). It starts with a game between the adversary A and a Challenger C. The Challenger C is in charge of Π, so he can do encryptions and decryptions. And all the technique details of Π are known to the Adversary A but the key, A wants to learn the information about plaintext as much as he can through interaction with C. In the case of COA, the interactions can be captured by this game: COA-Game:

The attacker A chooses two message m0 and m1 of equal length, say n bits, and sends them both to C.

The challenger C tosses a coin and determines a random bit b (say for example, “head” as “1” and “tail” as “0”). Then he set cb = Enck(mb) and sends cb to A.

The attacker tries his best to work out b and outputs another bit b’. If b’ = b, then A wins this game.

We say the cryptosystem Π= (Gen, Enc, Dec) is perfect indistinguishable under the COA attack if the probability that A wins the above COA-Game is ½, formally, we denote this as

Prob(ACOA(b’= b)) = ½.

1. Prove that the one-time-pad (OTP) is perfect secure under COA attack, i.e., the challenge ciphertext cb could come from either m0 or m1 with equal probability from the best of the attacker’s knowledge.

The definition of perfect indistinguishable is too strong to be applied in real life, and so does the OTP. So, we need to relax it to a more realistic definition, and it is called computational   indistinguishable   in   the   literature.   Informally,   computational indistinguishable means that we allow a tiny chance (for example, ½^128) that the attacker A can tell the cb is from m0 or m1 better than random guessing. That is, the cryptosystem Π= (Gen, Enc, Dec) is computational indistinguishable under the COA attack if the probability that A wins the above COA-Game is ½ + neg. Formally, we denote it as

Prob(ACOA(b’= b)) = ½ + neg.,

where neg. is a negligible probability (say for example, ½^128). In short, we write computational indistinguishable under the COA-Game as COA-IND.

Answer 1

The problem refers to the COA-Game and indistinguishability under the COA Game.

Let us first understand some terms to properly answer the question if One Time Pad is secure under a COA attack.

(1) What is COA?

-> COA is known as Cipher Text Only attack or Known cipher text attack in which the attacker is assumed to only know the set of cipher texts.

(2) What is COA - Game and COA - IND?

-> A COA-Game refers to a protocol in which an interaction between an attacker and a challenger takes place. In COA-IND game the attacker sends two messages M1 and M2 to the challenger to encrypt the messages. The challenger randomly chooses one of the Message to encrypt and then sends the encrypted message to the attacker. Now the attacker has to choose by doing some polynomial bound operations that which of the message M1 or M2 corresponds to the received encrypted message from the challenger.

If the attacker correctly chooses the message with probabilty = 1/2 then the attacker wins the game.

(3) What is OTP (One Time pad)?

One Time pad is a type of Vignere Cipher that enforces encryption technique on a given plain text.

Now lets us prove that OTP cipher is completely secure under any attack including Cipher Text Only attack.

1. One Time pad uses a random key to encrypt a message that is same in length as the message.

1. The key is only known to the sender and receiver.

1. The key is used only one time and then destroyed by both the sides.

1. Key are completely random bearing no relation to any of the plan text or cipher text.

So in case of Cipher text only attack, it doesnt matter if the attacker has a set of cipher text because as long as the key remains a secret the attacker will not to be able to break the encryption using any cryptanalysis or brute-force attack. So playing the COA game using OTP encryption, the attacker will never be able to come up with an outcome where the probability is < = 1/2.

So in ideal conditions, meaning the key remains a secret, OTP is pratically unbreakable.