# IND-CPA Security
*by Justine N. Gudito, Mercyd Sinadjan, Sam Bondj A. Tupa*


Knowledge is power.

For example, in the art of war, having information about your enemy’s next move would be crucial to the success of your battle. However, in today’s time, having access to real-time market data is indispensable for your success in trading or investing; and if all things fail, you could always try blackmailing someone with their secrets (definitely not recommended :3). Overall, it is evident that sensitive data or information is valuable and should always be protected.

The concept of protecting sensitive information dates back to 2,000 years ago, when Julius Caesar employed the “Caesar cipher,” which consists of permuting the alphabet by shifting each letter forward by a fixed amount. This concept of writing secret messages to protect information is the very essence of cryptography. Thus, to formally define cryptography, how about decrypting the texts below using the Ceaser Cipher (hint: V):

hwduytlwfumd nx ymj uwfhynhj tk xjhzwnsl htrrzsnhfynts fsi ifyf nsyjlwnyd ns ymj uwjxjshj tk fiajwxfwnjx. Ymnx nx itsj gd htsajwynsl ymj uqfns yjcy nsyt f htiji ktwrfy (hnumjw yjcy), bmnhm hfs tsqd gj ijhtiji gd zxnsl ymj htwwjxutsinsl ijhwduynts pjd.

## IND-CPA Security
Cryptography has come a long way from using the Caesar cipher to today’s vast array of algorithms, protocols, and technologies designed to secure information in the digital world. However, this also means that the number of adversaries and their countermeasures has also increased. Thus, In cryptography, there are three main security properties that we want to achieve, namely integrity, authenticity, and confidentiality (which will be the main focal point of this blog).

Confidentiality is the property that prevents adversaries from reading private data. This means that if a message is truly confidential, then the attacker should not know its contents. However, this does beg the question of what level of degree is it still considered confidential. What if an attacker had read the first half of the message but not the second half, then is it not considered confidential anymore? Thus, the concept of confidentiality is further formalized through the IND-CPA (Indistinguishability under Chosen Plaintext Attack) security game.

---
> The IND-CPA Game:
>1. The adversary Eve chooses two different messages, M0 and M1, and sends both messages to Alice
>2. Alice flips a fair coin. If the coin is heads, she encrypts M0. If the coin is tails, she encrypts M1. Formally, Alice chooses a bit b∈{0,1} uniformly at random, and then encrypts Mb. Alice sends the encrypted message Enc(K,Mb) back to Eve.
>3. Eve is now allowed to ask Alice for encryptions of messages of Eve’s choosing. Eve can send a plaintext message to Alice, and Alice will always send back the encryption of the message with the secret key. Eve is allowed to repeat this as many times as she wants. Intuitively, this step is allowing Eve to perform a chosen-plaintext attack in an attempt to learn something about which message was sent.
>4. After Eve is finished asking for encryptions, she must guess whether the encrypted message from step 2 is the encryption of M0 or M1.
>
>If Eve can guess which message was sent with probability > ½ , then Eve has won the game. This means that Eve has learned some information about which message was sent, so the scheme is not IND-CPA secure. On the other hand, if Eve cannot do any better than guess with ½ probability, then Alice has won the game. Eve has learned nothing about which message was sent, so the scheme is IND-CPA secure.
>
>Source: [Symmetric-Key Cryptography | Computer Security (cs161.org)](https://textbook.cs161.org/crypto/symmetric.html)

---

So, to briefly summarize the whole point of the IND-CPA game is to assess whether an encryption scheme can withstand chosen plaintext attacks to ensure the confidentiality of the encrypted data. Moreover, this also implies that ciphertexts produced by an encryption scheme are indistinguishable from each other, even when generated from different plaintexts. This means that an adversary cannot discern any meaningful information about the plaintexts from the corresponding ciphertexts, regardless of any patterns or similarities between the plaintexts.

Furthermore, before performing IND-CPA there are several considerations to be done such as (1) having the messages M0 and M1 be the same length as attackers could exploit the length differences in distinguishing between messages. Moreover, (2) the adversary is only allotted a practical number of encryption requests due to it being computationally infeasible considering the time and resources required. Additionally, (3) the adversary is considered to win the game only if they only possess a non-negligible advantage to ensure that only significant advantages are considered in evaluating security and are considered threatening. Lastly, (4) prohibiting deterministic schemes from achieving IND-CPA security due to their nature of always producing the same output with the same input. This is considered insecure under IND-CPA due to information leakage.

---

## IND-CPA Insecure

*so when can we say that a mode of block cipher operation is not IND-CPA secure??*
*Let's try to explore that below...*

### Electronic Codeblock (ECB) mode

To determine the usage of the IND-CPA game, let’s first introduce block ciphers which is a building block in implementing an encryption scheme, particularly symmetric-key cryptography. A block cipher is a fixed-size block of data, typically consisting of a specific number of bits that is used to encrypt and decrypt. Encryption takes a plaintext and key, yielding ciphertext, while decryption reverses this process. Thus, to ensure security, block ciphers must map each plaintext to a unique ciphertext per key setting, requiring determinism which often results in a lack of IND-CPA security.

There are multiple modes of operation in building an encryption algorithm using a block cipher such as ECB (Electronic Code Book) and CBC (Cipher Block Chaining). Although, the simplest one would be the ECB which is demonstrated below:

*Source: [Symmetric-Key Cryptography | Computer Security (cs161.org)](https://textbook.cs161.org/crypto/symmetric.html)*

In ECB mode, the plaintext is divided into fixed-size blocks and each block is independently encrypted using the block cipher with a secret key, which results to a ciphertext. The resulting individual ciphertext of each block is being concatenated together which then be the whole ciphertext to be sent to the receiver. However, this mode is flawed because identical plaintext blocks produce identical ciphertext blocks. This makes sense in the context of IND-CPA security because, in IND-CPA, any encryption scheme should ensure that ciphertexts produced from different plaintexts are indistinguishable from each other, even when an adversary has access to an encryption oracle and can interactively encrypt chosen plaintexts. However, ECB mode fails to meet this security requirement due to its deterministic nature.

Moreover, each plaintext block in this mode is encrypted independently using the same key, without any randomness or context from surrounding blocks. This means that identical plaintext blocks will always produce identical ciphertext blocks. As a result, an adversary can discern patterns and redundancies in the plaintext based on repeated ciphertext blocks, even without knowledge of the key. Thus, the lack of variability in the ciphertexts violates the IND-CPA security property, as it enables an adversary to distinguish between different plaintexts by observing their corresponding ciphertexts.

#### ECB mode IND-CPA Game

To show that using the ECB mode is not IND-CPA secure, let’s play the game.

*Alice and Eve playing the IND-CPA game*

1. Suppose Eve selects two distinct messages, ***Mx*** *(“cat”)* and ***My*** *(“dog”)*, which are blocks of the same length, and sends both to Alice.

    Mx = “cat”
	My = “dog”


2. Alice then randomly selects one of the two messages to encrypt by choosing from the two cups, and proceeds with encryption. In ECB mode, each plaintext block is encrypted independently, meaning that even if ***Mx*** and ***My*** contain identical blocks, those blocks will result in the same ciphertext blocks after encryption.

`chosen cup: Mx = “cat”`

    Mx = “cat”
    Mx1 = “c” [shifts five letters up] = “h”
    Mx2 = “a” [shifts five letters up] = “f”
    Mx3 = “t” [shifts five letters up] = “y”
    Cx = “hfy”


3. Alice then sends the ciphertext to Eve. At this point, Eve has the option to send Alice additional plaintexts for encryption. In this scenario, Eve sends Alice *“dodo”*, which could represent a repeating pattern for the first two letters of *“dog”*. Additionally, Eve can resend the two original messages and compare the resulting ciphertexts with the first ciphertext that Alice sent.

    M = “dodo”
    M1 = “d” [shifts five letters up] = “i”
    M2 = “o” [shifts five letters up] = “t”
    M3 = “d” [shifts five letters up] = “i”
    M4 = “o” [shifts five letters up] = “t”
    C = “itit”


4. Upon receiving the ciphertext of *“dodo”*, Eve notices that identical plaintext blocks consistently yield identical ciphertext blocks. Given that *"dodo"* exhibits a repeating pattern *("do")*, resulting in the encryption *("itit")*, Eve deduces that a similar pattern exists in the encryption of *"dog"*, which should be *“it_”*. Consequently, comparing *("itit")* to *(“hfy”)*, it becomes apparent that Alice did not choose *“dog”*.

    C(?) = “hfy”
    Mz= “dodo” = Cz = “itit”(observes the repeating pattern)
    Hence,
    My = “dog” = Cy = “it _”
        My cannot be the chosen message.
    Therefore,*
        “cat” is the chosen message.


5. Hence, Eve concludes that Alice’s selected message is *“cat”*. The deterministic characteristic of ECB enables Eve to identify patterns in the ciphertexts and draw deductions about the plaintexts.

The game we've shown above demonstrates that using ECB mode is not secure under the IND-CPA model. This is because ECB encrypts each block of plaintext independently, which could result in observations that identical plaintext blocks produce identical ciphertext blocks. This deterministic behavior enables an attacker, Eve, to discern patterns in the ciphertexts and make deductions about the plaintexts. In the demonstrated scenario above, Eve successfully deduces tbhe chosen message by observing the repeating pattern in the ciphertexts and inferring the corresponding plaintext. Therefore, the lack of randomness and the deterministic nature of ECB mode make it insecure in the IND-CPA game.

## IND-CPA Secure
*phew! So there are still operations that are IND-CPA secure right?*
*Hmmm... we think we should play again, but this time, using a different mode of block cipher operation!*

### Cipher Block Chaining (CBC) Mode
*Source: [Symmetric-Key Cryptography | Computer Security (cs161.org)](https://textbook.cs161.org/crypto/symmetric.html)*

Cipher Block Chaining (CBC) mode stands as an alternative mode of block cipher operation that achieves IND-CPA security due to its effective encryption strategy. In this mode, each plaintext block (except the first block which is XORed by an Initialization Vector (IV)) is XORed with the ciphertext of the preceding block before encryption. As a result, this introduces a dependency between consecutive blocks, as each block's encryption depends on the ciphertext of the previous block. Thus, changes in one block of plaintext cause unpredictability through subsequent blocks because it prevents patterns from emerging in the ciphertext. This makes it challenging for an adversary to infer information about the plaintext from the ciphertext.

#### CBC mode IND-CPA Game
To show that using the CBC mode is IND-CPA secure, let’s play another IND-CPA game.

*Alice and Eve playing another IND-CPA game*

1. With similar set-up with the ECB simulation, suppose Eve chooses two different messages, ***Mx*** *(“cat”)* and ***My*** *(“dog”)*(distinct blocks of the same length), and she sends both messages to Alice.

    Mx = “cat”
    My = “dog”

2. Alice then chooses which message to encrypt by choosing from the two cups at random and encrypts it. In CBC mode, each plaintext block (except the first one) is XORed with the ciphertext of the previous block before encryption.


    chosen cup: Mx = “cat”
    Mx1 = 01100011, Mx2 = 01100001, Mx3 =01110100
    
    key= [change 0s to 1s and 1s to 0s and convert to hexadecimal]
    
    Cx1= c = 01100011 ⊕ 10001000 =  E(11101011, key) =  00010100 = 14
    Cx2 = a = 01100001 ⊕ 00010100 =  E(01110101, key) =  10001010= 8A
    Cx3 = t = 01110100 ⊕ 10001010 =  E(11111110, key) =  00000001= 1
    
    Cx = 148A1

3. Alice then sends the ciphertext to Eve. This time, Eve can now send more plaintexts to Alice and observe their corresponding ciphertexts. With this, we have shown in the image that Eve sends Alice *“dodo”*, which can be a repeating pattern for the first two letters of *“dog”*. Aside from this, Eve can use the obtained ciphertexts to deduce information about the encrypted message.


        Mz = “dodo”**
        Mz1 = 01100100, Mz2 = 01101111, Mz3 =01100100, Mz4 = 01101111

        Cz1= c = 01100011 ⊕ 10001000 =  E(11101100, key) =  00010111 = 17
        Cz2 = a = 01101111 ⊕ 00010111 =  E(01111000, key) =  10101111 = AF
        Cz3 = t = 01100100 ⊕ 10101111 =  E(11001011, key) =  01100101 = 65
        Cz4 = t = 0110111 ⊕ 01100101 =  E(00101010, key) =  11000011 = C3

        Cz = 17AF65C3


4. Eve observes that identical plaintext blocks do not produce identical ciphertext blocks in CBC mode. She cannot directly infer any patterns in the ciphertext that reveal information about the plaintext blocks.

5. Since Eve cannot discern any patterns in the ciphertexts that directly reveal information about the plaintexts, she cannot reliably determine which message Alice encrypted. So Eve tried to send another message such as *“car”*, *“dog”*, *“rat”*, etc... *(remember that Eve also has limited number of encryption requests)*

6. To no surprise Eve still cannot discern any patterns in the ciphertexts that directly reveal information about the plaintexts. Therefore, Eve cannot win the game due to the difficulty of deriving information about the other blocks in the message without knowing the encryption key. Additionally, the presence of the IV complicates things as it adds randomness to each preceeding encryption.

The game shown above demonstrates that using CBC mode is secure under the IND-CPA model. This is because CBC prevents Eve from distinguishing between encryptions of two chosen plaintexts with a non-negligible advantage. It will be harder for Eve to decide which one Alice picked because the ciphertexts didn't show any pattern that Eve can compare with. Unlike in ECB mode, where identical plaintext blocks always result in identical ciphertext blocks, CBC mode introduces randomness through the Initial Vector (IV) and dependencies between blocks, preventing patterns from emerging in the ciphertext. Hence, CBC mode achieves IND-CPA security by creating interdependencies between encrypted blocks. This breaks patterns in the ciphertext, making it challenging for attackers to discern relationships between plaintext and ciphertext.


# Conclusion
IND-CPA security is crucial for evaluating the vulnerability of block cipher operation modes to attacks. An example of a mode that fails to achieve IND-CPA security is the Electronic Codebook (ECB) mode. ECB mode lacks randomness and operates deterministically. This deterministic nature enables attackers to discern patterns easily, compromising the security of the encryption. When a mode of operation is deterministic, it becomes insecure as patterns can be exploited for decryption without the need for the key.

Consequently, IND-CPA security is achieved when a mode of block cipher operation introduces unpredictability, adding randomness to the encryption process. As demonstrated earlier, Cipher Block Chaining (CBC) mode achieves IND-CPA security by employing an Initialization Vector (IV) alongside the plaintext during encryption. Each subsequent block uses the ciphertext of the previous block, making it challenging to discern patterns in the encrypted message.

An IND-CPA secure mode of operation ensures that encrypted messages remain resistant to pattern analysis and attacks. Ensuring IND-CPA security indicates that a cryptographic system can withstand chosen-plaintext attacks, where an attacker can selectively obtain ciphertexts for chosen plaintexts and analyze them for patterns or vulnerabilities. Modes like CBC achieve this by introducing randomness and unpredictability, making decryption without the key significantly more difficult. Conversely, modes like ECB, lacking randomness and operating deterministically, fail to provide IND-CPA security, rendering them vulnerable to exploitation and decryption attacks. Hence, IND-CPA security is like a building block for creating and testing secure ways to keep information safe with encryption. It's a key rule that helps designers and testers ensure that encryption methods are strong enough to protect data from being easily cracked by attackers.

### *References*

*1. Wagner, D., Weaver, N., Kao, P., Shakir, F., Law, A., & Ngai, N. (2023). [CS 161: Computer Security](https://textbook.cs161.org/). UC Berkeley.*