CSE442T Introduction to Cryptography (Lecture 22)

Chapter 7: Composability

So far we’ve sought security against

Adversary knows $c$, but nothing else.

Attack models

Known plaintext attack (KPA)

Adversary has seen $(m_1,Enc_k(m_1)),(m_2,Enc_k(m_2)),\cdots,(m_q,Enc_k(m_q))$.

$m_1,\cdots,m_q$ are known to the adversary.

Given new $c=Enc_k(m)$, is previous knowledge helpful?

Chosen plaintext attack (CPA)

Adversary can choose $m_1,\cdots,m_q$ and obtain $Enc_k(m_1),\cdots,Enc_k(m_q)$.

Then adversary see new encryption $c=Enc_k(m)$. with the same key.

Example:

In WWII, Japan planned to attack “AF”, but US suspected it means Midway.

So US use Axis: $Enc_k(AF)$ and ran out of supplies.

Then US know Japan will attack Midway.

Chosen ciphertext attack (CCA)

Adversary can choose $c_1,\cdots,c_q$ and obtain $Dec_k(c_1),\cdots,Dec_k(c_q)$.

Definition 168.1 (Secure private key encryption against attacks)

Capture these ideas with the adversary having oracle access.

Let $\Pi=(Gen,Enc,Dec)$ be a private key encryption scheme. Let a random variable $IND_b^{O_1,O_2}(\Pi,\mathcal{A},n)$ where $\mathcal{A}$ is an n.u.p.p.t. The security parameter is $n\in \mathbb{N}$, $b\in\{0,1\}$ denoting the real scheme or the adversary’s challenge.

The experiment is the following:

• Key $k\gets Gen(1^n)$
• Adversary $\mathcal{A}^{O_1(k)}(1^n)$ queries oracle $O_1$
• $m_0,m_1\gets \mathcal{A}^{O_1(k)}(1^n)$
• $c\gets Enc_k(m_b)$
• $\mathcal{A}^{O_2(c)}(1^n,c)$ queries oracle $O_2$ to distinguish $c$ is encryption of $m_0$ or $m_1$
• $\mathcal{A}$ outputs bit $b'$ which is either zero or one

$\Pi$ is CPA/CCA1/CCA2 secure if for all PPT adversaries $\mathcal{A}$,

where $\approx$ is statistical indistinguishability.

Note that $Dec_k^*$ will not allowed to query decryption of a functioning ciphertext.

You can imagine the experiment is a class as follows:

n = 1024
 
@lru_cache(None)
def oracle_1(m,key,**kwargs):
    """
    Query oracle 1
    """
    pass
 
@lru_cache(None)
def oracle_2(c,key,**kwargs):
    """
    Query oracle 2
    """
    pass
 
class Experiment:
    def __init__(self, key, oracle_1, oracle_2):
        self.key = key
        self.oracle_1 = oracle_1
        self.oracle_2 = oracle_2
 
    def sufficient_trial(self):
        pass
 
    def generate_test_message(self):
        pass
 
    def set_challenge(self, c):
        self.challenge = c
 
    def query_1(self):
        while not self.sufficient_trial():
            self.oracle_1(m,self.key,**kwargs)
 
    def challenge(self):
        """
        Return m_0, m_1 for challenge
        """
        m_0, m_1 = self.generate_test_message()
        self.m_0 = m_0
        self.m_1 = m_1
        return m_0, m_1
 
    def query_2(self, c):
        while not self.sufficient_trial():
            self.oracle_2(c,self.key,**kwargs)
 
    def output(self):
        return 0 if self.challenge==m_0 else 1
 
if __name__ == "__main__":
    key =  random.randint(0, 2**n)
    exp = Experiment(key, oracle_1, oracle_2)
    exp.query_1()
    m_0, m_1 = exp.challenge()
    choice = random.choice([m_0, m_1])
    exp.set_challenge(choice)
    exp.query_2()
    b_prime = exp.output()
    print(f"b'={b_prime}, b={choice==m_0}")

Theorem: Our mms private key encryption scheme is CPA, CCA1 secure.

Have a PRF family $\{f_k\}:\{0,1\}^{|k|}\to\{0,1\}^{|k|}$

$Gen(1^n)$ outputs $k\in\{0,1\}^n$ and samples $f_k$ from the PRF family.

$Enc_k(m)$ samples $r\in\{0,1\}^n$ and outputs $(r,f_k(r)\oplus m)$. For multi-message security, we need to encrypt $m_1,\cdots,m_q$ at once.

$Dec_k(r,c)$ outputs $f_k(r)\oplus c$.

Familiar Theme:

• Show the R.F. version is secure.
  • $F\gets RF_n$
• If the PRF version were insecure, then the PRF can be distinguished from a random function…

$IND_b^{O_1,O_2}(\Pi,\mathcal{A},n), F\gets RF_n$

• $Enc$ queries $(m_1,(r_1,m_1\oplus F_k(r_1))),\cdots,(m_{q_1},(r_{q_1},m_{q_1}\oplus F_k(r_{q_1})))$
• $Dec$ queries $(s_1,c_1),\cdots,(s_{q_2},c_{q_2})$, where $m_i=c_i-F_k(s_i)$
• $m_0,m_1\gets \mathcal{A}^{O_2(k)}(1^n)$, $Enc_F(m_b)=(R,M_b+F(R))$
• Query round similar to above.

As long as $R$ was never seen in querying rounds, $P[\mathcal{A} \text{ guesses correctly}]=1/2$.

$P[R\text{ was seen before}]\leq \frac{p(n)}{2^n}$ (by the total number of queries in all rounds.)

This encryption scheme is not CCA2 secure.

After round 1, $O^n,1^n\gets \mathcal{A}^{O_1(k)}(1^n)$,

$(r,m+F(r))=(r,c)$ in round 2.

Query $Dec_F(r,c+0\ldots 01)=0\ldots 01 \text{ or } 1\ldots 10$.

$c+0\ldots 01-F(r)=M+0\ldots 01$

Encrypt then authenticate

Have a PRF family $\{f_k\}:\{0,1\}^|k|\to\{0,1\}^{|k|}$

$Gen(1^n)$ outputs $k_1,k_2\in\{0,1\}^n$ and samples $f_k$ from the PRF family.

$Enc_{k_1,k_2}(m)$ samples $r\in\{0,1\}^n$ and let $c_1=f_{k_1}(r)\oplus m$ and $c_2=f_{k_2}(c_1)$. Then we output $(r,c_1,c_2)$. where $c_1$ is the encryption, and $c_2$ is the tag. For multi-message security, we need to encrypt $m_1,\cdots,m_q$ at once.

$Dec_{k_1,k_2}(r,c_1,c_2)$ checks if $c_2=f_{k_2}(c_1)$. If so, output $c_1-f_{k_1}(r)$. Otherwise, output $\bot$.

Show that this scheme is CPA secure.

1. Show that the modifier version $\Pi'^{RF}$ where $f_{k_2}$ is replaced with a random function is CCA2 secure.
2. If ours isn’t, then PRF detector can be created.

Suppose $\Pi^RF$ is not secure, then $\exists \mathcal{A}$ which can distinguish $IND_i^{O_1,O_2}(\Pi'^{RF},\mathcal{A},n)$ with non-negligible probability. We will use this to construct $B$ which breaks the CPA security of $\Pi$.

Let $B$ be the PPT algorithm that on input $1^n$, does the following:

• Run $\mathcal{A}^{O_1,O_2}(\Pi'^{RF},\mathcal{A},n)$
• Let $m_0,m_1$ be the messages that $\mathcal{A}$ asked for in the second round.
• Choose $b\in\{0,1\}$ uniformly at random.
• Query $Enc_{k_1,k_2}(m_b)$ to the oracle.
• Let $c$ be the challenge ciphertext.
• Return whatever $\mathcal{A}$ outputs.