Symmetric Cryptography

Most of these notes are taken while reading Chapter 3 of Introduction to Modern Cryptography and you'll notice that terms, definitions and theorems are directly adapted from the source. It's advised to read the original source than these incomplete notes.

Computational Security: in contrast to Perfect Secrecy, computational security allows for small probability of leaking information and computational limits on the attacker (efficient adversaries).

A scheme is $(t,ϵ)-$secure if an attacker can break the scheme in at most time $t$ with probability at most $ϵ$.

Asymptotic Approach: rather than concrete-security approach, most cryptographic protocols’ security are defined by security parameter $\lambda$, and running time of adversary, success probability are functions of security parameter, rather than concrete values.

• Efficient adversaries run in polynomial time $\lambda$
• $\text{negl}(\lambda )$: refers to the small success probabilities, less than inverse of $\lambda$.

PPT: probabilistic polynomial-time. Secure scheme: If a PPT adversary succeeds in breaking the scheme with negl probability.

Asymptotic approach

Two things to consider:

• polynomial-time algorithms: any function is polynomially bounded if for any constant $c$, $f(n)<n^c$ for all n. an algorithm runs in polynomial time, if for a polynomial $p$ and input $x\in \{0,1{\}}^{\ast }$, it terminates in $p(|x|)$ steps.
• negligible function: a function $f$ is negligible if for every polynomial $p$, there exists $N$ such that for every $n>N$, $f(n)<\frac{1}{p(n)}$, or from the definition of polynomial function, for all constants $c$, there exists $N$ such that for every $n>N$, $f(n)<n^{-c}$.

Cryptographic algorithms are probabilistic (randomised), that’s why attackers are allowed to be probabilistic as well. This gives attackers more powers and allows to model more practical attacks.

probabilistic (randomised) algorithms are one that use randomness in their logic. Normally, randomness is used in the input.

TODO: explain some examples of negligible functions, and why some functions are preferred over other across different range of inputs.

Main importance of negligible functions is that they obey closure properties:

• ${\text{negl}}_3(n)={\text{negl}}_1(n)+{\text{negl}}_2(n)$ is also negligible.
• ${\text{negl}}_4(n)=p(n)\cdot {\text{negl}}_1(n)$ is also negligible. This means that repeating an experiment that repeats a negligible event any number of times still succeeds with negligible probability.

A scheme is secure if for every PPT adversary $\mathcal{A}$, and $\forall p\exists N$ such that for all $n>N$, the probability of attack's success is less than $\frac{1}{p(n)}$.

Computationally Secure encryption

• Define encryption as $\text{Gen,Enc,Dec}$ and model an adversary $\mathcal{A}$ with additional power being eavesdropping, i.e. it can look at all the messages as an observer, and the adversary is efficient as explained in previous section.
• Define an indistinguishability experiment ${\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{eav}}$ where $\Pi$ is a encryption scheme and $\mathcal{A}$ is a PPT adversary, in which adversary chooses messages $m_0,m_1$ and receives encryption and has to output a bit $b^{\prime }$. According to the definition, $\Pi$ is computationally secure if $\mathrm{Pr}[{\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{eav}}(n)=1]\le \frac{1}{2}+\mathsf{negl}(n)$.
• Define Semantic Security as a slightly weaker notation of Perfect secrecy. Now, define that the notion of indistinguishability is similar to semantic security by two reductions:
  • probability of adversary $\mathcal{A}$ determining the $i$th bit of message $m$ from $\mathsf{Enc}(m)$ is less than $\frac{1}{2}+\mathsf{negl}(n)$, i.e. it’s same as adversary randomly guessing the bit.
  • probability of adversary $\mathcal{A}$ determining the function $f$ on $m$, regardless of its distribution $\mathcal{D}$, from $\mathsf{Enc}(m)$ is equal to adversary ${\mathcal{A}}^{\prime }$ computing $f(m)$ without knowledge of ciphertext.
• Define Semantic security as probability of determining $f(m)$ from $\mathsf{Enc}(m)$ and external knowledge $h(m)$, where $m$ is sampled from PPT algorithm $\text{Samp}$, equal to probability of adversary ${\mathcal{A}}^{\prime }$ computing $f(m)$ from $h(m)$.
• Now, any encryption is EAV-secure iff it is semantically secure in presence of eavesdropper.

Semantically secure encryption

• having defined semantic security, we’re now interested in realising a encryption scheme

• for that we need randomisation and true random generators are difficult to model computationally, that’s why in cryptography pseudorandom numbers are used.

• to construct an EAV-secure encryption scheme using PRG, we need help of reduction proofs.

• Reduction Proofs: To prove that problem X is hard, we reduce the notion of security in problem X to already hard problem X’, and prove that if X is solved, this means X’ is solved, this leads to contradiction.

  • Model adversary A for X which simulates attack for adversary A’ on X’ which A’ succeed with probability $ϵ(n)$, and outputs directly related to the output of X’ with probability $ϵ(n)/p(n)$.
  • Now, if $ϵ(n)$ isn’t negligible, neither is $\frac{ϵ(n)}{p(n)}$, this means, A’ can break X’ if A breaks X. but according to our assumption $ϵ(n)$ is negligible.

• encryption scheme using prg uses keystream as pad generated by PRG and encryption is done using XOR cipher. This is unconditionally secure if $k$ is truly random by one-time pads (OTP).

• To prove it’s EAV-secure, we reduce the problem by introducing a distinguisher $D$ that simulates attack for adversary $\mathcal{A}$ on encryption scheme $\Pi$.

• D only succeeds when $\mathcal{A}$ succeeds, $\mathrm{Pr}[D(G(k))=1]=\mathrm{Pr}[{\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{eav}}=1]$

• using one time pad, we identify that if encryption is done on a uniform string using one time pad, probability is exactly equal to 1/2

• since, G is a PRG, there is a negligible probability of success in distinguishing pseudorandom string to uniform string, this equates to encryption $\Pi$ directly, and thus, it also has slightly higher probability than 1/2.

• define multiple encryption scheme, i.e. eavesdropper shouldn’t be able to distinguish even when same message is encrypted by the scheme.

Chosen plaintext attacks

• multiple encryption indistinguishability refers to probability of adversary to differ between two sets of ciphertexts generated using list of messages chosen by $\mathcal{A}$.
• It’s not possible to have multiple encryption indistinguishability if encryption is stateless and deterministic.
• Chosen Plaintext Attack (CPA) security: only difference with EAV-security is key is derived before adversary chooses messages, and adversary has access to encryption oracle.
  • Encryption oracle ${\text{Enc}}_k(\cdot )$ can be used by adversary to get ciphertext for any message, and the adversary can interact with oracle as many times as it likes.
• CPA indistinguishability experiment ${\text{PrivK}}_{\mathcal{A},\Pi }^{cpa}(n)$:
  • key is chosen by running $\text{Gen}(1^n)$
  • $\mathcal{A}$ is given oracle access to ${\text{Enc}}_k(\cdot )$ chooses messages $m_0,m_1$
  • uniform bit $b\in \{0,1\}$ is chosen and $c\leftarrow {\text{Enc}}_k(m_b)$ is given to $\mathcal{A}$
  • adversary outputs bit $b^{\prime }\in \{0,1\}$, and succeeds if $b^{\prime }=b$.
• CPA security: prob. of success is $\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cpa}}=1]\le \frac{1}{2}+\text{negl}(n)$
• CPA security for multiple encryption: ${\text{LR}}_{k,b}(\cdot ,\cdot )$ oracle access is given to $\mathcal{A}$, which on input two messages $m_0,m_1$ sends encryption of $m_b$ where b is uniform bit chosen at the beginning of experiment
  • CPA-secure for multiple encryptions if $\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{LR-cpa}}=1]\le \frac{1}{2}+\text{negl}(n)$.
• CPA security for multiple encryption means CPA security for single Encryption
• In fact, encryption that are CPA secure are also CPA secure for multiple encryption. Prove this.
• Above is not true for EAV-security, i.e. encryption that are EAV-secure might not be EAV-secure for multiple encryption. Perfect example is one-time pads.

CPA security from PRF

• A CPA-secure encryption function can be formed using any PRF by just XORing the input message with output of PRF where seed for PRF is chosen uniformly. and is padded with encrypted output to form ciphertext, i.e. $c:=⟨r,F_k(r)\oplus m⟩$, and decrypted by again XORing $m:=F_k(r)\oplus s$
• To prove this scheme is CPA secure, we need to prove that $\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cpa}}=1]\le \frac{1}{2}+\text{negl}(n)$
• Common template used throughout proving encryption schemes secure, is to first consider hypothetical true-random variant of the scheme and prove using reduction proofs that adversary doesn’t gain any advantage, and then add pseudorandomness to do probabilistic analysis.
• prove in two steps: first define a distinguisher $D$ that will simulate CPA for adversary $\mathcal{A}$, and use it’s output to determine whether encryption oracle $\mathcal{O}$ is pseudorandom, i.e. $F_k$ or chosen uniformly from ${\text{Func}}_n$.
  • i.e. Prove $\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{cpa}=1]-\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\tilde{\Pi }}^{cpa}=1]\le \text{negl}(n)$
• Let’s explain how $D$ works. $D$ has access to encryption oracle $\mathcal{O}$.
  • Setup $\mathcal{A}(1^n)$. $\mathcal{A}$ queries $\mathcal{O}$ for message $m\in \{0,1{\}}^n$. Choose a uniform $r\in \{0,1{\}}^n$ and obtain $⟨r,y\oplus m⟩$.
  • $\mathcal{A}$ chooses challenge messages $m_0,m_1$. $D$ choose uniform bit $b\in \{0,1\}$ and queries $\mathcal{O}(m_b)$, returns the ciphertext to $\mathcal{A}$.
  • $\mathcal{A}$ continue asking encryption oracle queries until it outputs bit $b^{\prime }$
• There can be two scenarios:
  • When ${\mathcal{O}}^{\prime }s$ function is pseudorandom, ${\mathcal{A}}^{\prime }s$ view as a subroutine in $D$ is identical to CPA experiment of a PRF. Thus, $\mathrm{Pr}[D^{F_k(\cdot )}(1^n)=1]=\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cpa}}(n)=1]$
  • When ${\mathcal{O}}^{\prime }s$ function is random function $f$, then $A^{\prime }s$ view is identical to CPA experiment of random function. Thus, $\mathrm{Pr}[D^{f(\cdot )}(1^n)=1]=\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\tilde{\Pi }}^{\text{cpa}}(n)=1]$
  • Thus, by assumption that $F$ is Pseudorandom, we establish that $\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{cpa}=1]-\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\tilde{\Pi }}^{cpa}=1]\le \text{negl}(n)$.
• Next step is to prove that $\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{cpa}=1]\le \frac{1}{2}+\frac{q(n)}{2^n}+\text{negl}(n)$.
  • Left as exercise for future me.

Ciphers and Mode of Operation

Encrypt arbitrary long messages using symmetric encryption primitives. Two of them are:

• Stream Ciphers
• Block Ciphers

Stream Ciphers

• Instantiation of PRNGs using stream ciphers.
• Deterministic algorithms: $\text{Init(s,IV)}\to st,\text{Next(st)}\to (y,s{t}^{\prime })$
• support arbitrary length messages using $\text{GetBits}(st,1^l)$
• a stream cipher without an IV is a PRG.
• stream cipher with an PRG is a PRF, such that $F_s^l(IV)\stackrel{def}{=}\text{GetBits}(\text{Init}(s,IV),1^l)$
• converse can be also true, i.e. creating stream ciphers using PRF, by concatenating $IV$ with counters.
• Modes of Operation:
  • Synchronised mode: stateful mode, doesn’t need an IV
  • Unsynchronised mode: stateless mode

CCA security

Chosen-Ciphertext attack where the adversary makes the receiver decrypt a ciphertext of its own choice and in turn learns something original message m or key k. This is what is meant by secrecy in cryptographic land.

CPA security and Message authentication deal with message integrity where attacker isn’t able to modify the ciphertext, and if it does, receiver will accept with only negligible probability.

Let’s understand some attacks possible when adversary has access to decrypt a ciphertext of it’s choice, and learns something about the original message, sometimes the complete message.

• Padding oracle attack: most of block cipher mode of operation use padding to turn plaintext into multiple of cipher’s block size. Most common padding used is PKCS#7 which appends a byte equal to number of bytes required to turn plaintext into a multiple, that number of times. CBC mode is prone to padding oracle attack, where attacker can learn complete message.
• CAPTCHA: user can learn captcha’s original image by using captcha server as oracle.

CCA indistinguishability experiment ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cca}}(n)$:

• Key $K$ is generated by $\text{Gen}(1^n)$
• $\mathcal{A}$ has access to encryption $\text{Enc}(\cdot )$ and decryption oracle $\text{Dec}(\cdot )$.
• $\mathcal{A}$ outputs pair of messages $m_0,m_1$
• uniform bit $b\in \{0,1\}$ is chosen and challenge ciphertext $c\leftarrow {\text{Enc}}_k(m_b)$ is computed and given to $\mathcal{A}$
• $\mathcal{A}$ continues to submit encryption and decryption queries to the oracle, but can’t submit queries to chosen messages, i.e. $m_0,m_1$.
• $\mathcal{A}$ outputs bit $b^{\prime }\in \{0,1\}$
• experiment outputs 1 if $b^{\prime }=b$, else 0

$$\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cca}}=1]\le \frac{1}{2}+\text{negl}(n)$$

As demonstrated in Padding oracle attack, that any encryption scheme that satisfies CCA security has to be non-malleable, i.e. any change in the ciphertext shouldn’t directly correspond to change in the plaintext as this allows attacker to gain insights about original message.

owf

References

• Introduction To Mathematical Cryptography : Chapter 8.10
• Introduction to Modern Cryptography: Section 2
• CS276 Luca Trevisan’s lecture notes