# Writeup 1: IND-CPA Security ###### tags: `Block Ciphers`, `IND-CPA`, `ECB`, `CTR` --- <div style="text-align: justify"> The IND-CPA (Indistinguishable under Chosen-Plaintext Attack) is a "security game" of sorts that simulates a scenario where an adversary (Eve) sends two plaintext messages to a supposed victim (Alice) who then selects one of these at random. <div style="text-align: center;"> <img src = "https://hackmd.io/_uploads/SkoK4l96a.png"> </div> To illustrate this game, let's consider an example where Eve provides two messages "kain" and "kana" to Alice. These two messages must be of the same length. Alice, in turn, randomly chooses one of the messages, let’s say the message “kain.” She encrypts it using her encryption scheme and sends the resulting ciphertext back to Eve. <div style="text-align: center;"> <img src = "https://hackmd.io/_uploads/H1VgHx5pp.png"> </div> Now, Eve's ultimate goal is to guess which of the two original messages she received—whether it was the message "kain" or "kana." If Eve successfully identifies the original message that Alice encrypted, then she wins the game. On the other hand, if Eve's guess is incorrect, Alice emerges victorious. Throughout the game, Eve can repeatedly request Alice to encrypt any message of her choice but is only limited to a practical number of encryption requests. <div style="text-align: center;"> <img src = "https://hackmd.io/_uploads/By8jsVmaa.png"> </div> The IND-CPA security game serves as a crucial evaluation mechanism for cryptographic techniques and algorithms, ensuring their effectiveness in defending against chosen plaintext attacks. In this example, Eve's success in correctly guessing the original message highlights a potential vulnerability in the encryption scheme, emphasizing the importance of robust cryptographic designs that withstand adversarial attempts to distinguish between encrypted messages. However, despite all of these, the probability of Eve to win is negligible, which implies an extremely low probability. Something is considered “IND-CPA secure” if the encryption system is strong. Even if Eve knows the encryption method and can ask for encrypted messages, she cannot get any information about the original message from the ciphertext, even if she can choose the message to be encrypted. This security ensures that confidential information stays safe, even when potential attackers try to exploit vulnerabilities by using chosen plaintexts. ## Block Ciphers Block ciphers are like digital secret codes used to keep information safe. They take a fixed-size piece of data and scramble it using a secret key, producing encrypted output. This process helps secure communication between two parties, like for instance, Alice and Bob. However, despite this, block ciphers pose some challenges, and different modes of operation are used to add additional security layers to keep digital conversations and transactions private. ### Electronic Code Book (ECB) <div style="text-align: center;"> <img src = "https://hackmd.io/_uploads/ByFYXNu6T.png"> </div> The Electronic Codebook (ECB) mode is a straightforward and widely used block cipher mode for encrypting plaintext. In this mode, the plaintext is broken into several blocks. Each block of plaintext is independently encrypted using the same key, which produces a corresponding block of ciphertext. This process is repeated for every block in the message. ### Why ECB Mode is NOT IND-CPA Secure? *Deterministic Encryption*: The encryption of a specific plaintext block consistently yields the same ciphertext block with the same key. Consequently, if an adversary observes repeated occurrences of identical plaintext blocks, they can easily observe patterns within the ciphertext. This deterministic behavior violates the indistinguishability required for IND-CPA security. *No Mixing of Blocks*: Each plaintext block is encrypted independently, leading to identical plaintext blocks generating identical ciphertext blocks. The absence of inter-block mixing enables adversaries to identify repeated patterns in the ciphertext, potentially revealing information about the original plaintext structure. Going back to Eve and Alice for example, if Eve observes repeated blocks in the ciphertext, she can infer patterns in the data, potentially compromising the confidentiality of the messages. This determinism makes ECB vulnerable to known-plaintext attacks, as Eve can detect repeated patterns and make educated guesses about the original messages. <div style="text-align: center;"> <img src = "https://hackmd.io/_uploads/rJyChyc6a.png"> </div> <br> ECB mode's simplicity is overshadowed by its critical flaw: if any block in the message is repeated, their corresponding ciphertext blocks will also be repeated. This leakage of information exposes repeated structures within the message, compromising its confidentiality and integrity. ### Other Modes of Operation ECB is not the only application of block ciphers in cybersecurity; as a matter of fact, there are quite a few other options. One of these options is known as CBC (Cipher Block Chaining). <div style="text-align: center;"> <img src = "https://hackmd.io/_uploads/SyP6skc6a.png"> </div> CBC is an alternative mode of operation that solves one fundamental issue with ECB - its determinisic nature. This is due to the **initialization vector** (IV), which introduces an element of randomness and unpredictability to the encryption flow as shown in the image above. The IV is supposed to be a unique value for every encryption, which basically means that if you wanted to encrypt the same plaintext message more than once, despite both messages having the exact same contents, a different IV gets generated for each respective encryption. The way it works is before the plaintext message enters the block cipher, it gets XOR'd with the initialization vector to produce some random and unique value. CBC also ensures that the other blocks are non-deterministic by taking the generated ciphertext and using it as the IV for the next block until the last one, hence forming a "chain" of blocks. With that being said, it begs the question: **is it IND-CPA secure?** Assuming that the IV is never reused, then by definition, **yes!** The CBC method is IND-CPA secure. No matter how many times Eve requests Alice for an encryption, she will always get a different result. Each encryption is always performed with a unique IV, so there is no way for Eve to match an encryption she obtained previously with any future encryptions she asks from Alice. At best, the probability of Eve winning is at most 50/50 - thus, all she can really do is guess. To put things into perspective, let's picture a hypothetical scenario where Eve (who has no prior knowledge of Japanese) sends two English words and Alice would give back the Japanese translations for these words. Imagine if every time you asked Alice for a translation, she would give a random Japanese word. In actuality, this wouldn't really make sense, but for the sake of example, let's say that for the word *cry*, Alice would first give the translation 泣く, then for every subsequent time Eve asks for a translation, Alice would give 聞く、忘れる、覚えてる、殺す、逃げる and so on. Eve would have absolutely no way of identifying the correct translation. This analogy describes how the unpredictability of the initialization factor ensures IND-CPA security, since all Eve can realistically do is guess. The only way CBC becomes non IND-CPA secure is if IV was reused. However, this wouldn't make sense as it defeats the purpose of the IV in the first place, which is to make the encryption process non-deterministic. Another mode of operation is CTR (Counter). <div style="text-align: center;"> <img src = "https://hackmd.io/_uploads/rkPUjg9aa.png"> </div> This mode of operation also uses the concept of an IV, which in this case is referred to as the "nonce". It also solves the problem of determinism by introducing the nonce and incrementing the counter per block to ensure a different output for each block cipher in the encryption flow as shown above. It is different from the aforementioned modes of operation. It does not form a chain like CBC and behaves in a similar fashion to the OTP wherein the block cipher functions as sort of a random number generator, producing new keys for the OTP. Like the CBC, it is also IND-CPA secure for very similar reasons; as long as the nonce is not reused, its non-deterministic nature will always guarantee that a different encryption is produced every time. To give us a better understanding of the similarities/differences between these three modes of operation, here is a summarized comparison: | EBC Mode | CBC Mode | CTR Mode | | -------- | -------- | -------- | | If any block in the message is the same, their corresponding ciphertext blocks will also be identical. | Uses an IV for each ciphertext block.| Involves an IV chosen uniformly for each encryption.| |This leakage of information indicates repeated parts in the message, potentially exposing its structure to adversaries. | Provides randomized encryption by XORing each plaintext block with the previous ciphertext block. | Employs a sequence of values from encrypting the IV as a one-time pad.| | |Leakage in CBC mode reveals if two messages start with the same blocks up to their first difference. | Reusing the IV leads to catastrophic leakage equivalent to reusing a one-time pad. | | Sequential in nature and not parallelizable for encryption but parallelizable for decryption. | Offers parallelizable encryption due to its independent block encryption approach. | ## Conclusion The IND-CPA game is a good way of understanding a method/algorithm's security when faced with an adversary like Eve. When it comes to block ciphers, we have shown that EBC is not IND-CPA secure, mainly due to its deterministic nature. However, other modes of operation have rectified this through the introduction of the initialization vector. Both CBC and (among other modes of operation) are examples of systems that are IND-CPA secure.