Strong leakage-resilient encryption: enhancing data confidentiality by hiding partial ciphertext

Abstract

Leakage-resilient encryption is a powerful tool to protect data confidentiality against side channel attacks. In this work, we introduce a new and strong leakage setting to counter backdoor (or Trojan horse) plus covert channel attack, by relaxing the restrictions on leakage. We allow bounded leakage at anytime and anywhere and over anything. Our leakage threshold (e.g., 10,000 bits) could be much larger than typical secret key (e.g., AES key or RSA private key) size. Under such a strong leakage setting, we propose an efficient encryption scheme which is semantic secure in standard setting (i.e., without leakage) and can tolerate strong continuous leakage.We manage to construct such a secure scheme under strong leakage setting, by hiding partial (e.g., $1\%$) ciphertext as secure as we hide the secret key using a small amount of more secure hardware resource, so that it is almost equally difficult for any adversary to steal information regarding this well-protected partial ciphertext or the secret key. We remark that the size of such well-protected small portion of ciphertext is chosen to be much larger than the leakage threshold. We provide concrete and practical examples of such more secure hardware resource for data communication and data storage. Furthermore, we also introduce a new notion of computational entropy, as a sort of computational version of Kolmogorov complexity. Our quantitative analysis shows that, hiding partial ciphertext is a powerful countermeasure, which enables us to achieve higher security level than existing approaches in case of backdoor plus covert channel attacks. We also show the relationship between our new notion of computational entropy and existing relevant concepts, including Shannon entropy, Yao entropy, Hill entropy, all-or-nothing Transform, and exposure-resilient function. This new computation entropy formulation may have independent interests.

Appendices

Appendix A: Background

1.1 Appendix A.1: All-or-nothing transform: Rivest’s package transform

To be self-contained, we quote the all-or-nothing transform, called “Package Transform”, proposed by Rivest [20] as below.

• 1. Let the input message be $m_1, m_2, \ldots , m_s$.

• 2. Choose at random a key $K'$ for the package transform block cipher $\textsf {E} (\cdot , \cdot )$.

• 3. Compute the output message $m_1', m_2', \ldots , m_{s+1}'$ as below

  • $m_i' = m_i \oplus \textsf {E} (K', i)$ for $i=1, 2, \ldots , s$;

  • $m_{s+1}' = K' \oplus h_1 \oplus h_2 \ldots \oplus h_s$ where $h_i = \textsf {E} (K_0, m_i' \oplus i)$ for $i=1, 2, \ldots , s$.

Informally, in the above all-or-nothing transform method, if a receiver with key $K_0$ obtains all but a few ciphertext blocks $m_i$’s, then the receiver will not be able to recover the random nonce key $K'$ and thus can not decrypt any ciphertext block, i.e., know nothing about the plaintext.

Appendix B: Our proofs

1.1 Appendix B.1: Proof of Claim 1

Proof of Claim 1

For any nonnegative integer $\ell$, a steal algorithm ${{\textsf {S} }}(\ell )$ can output any message in the set $\{ 0,1 \}^{\le \ell } \setminus \{ \texttt {EmptyString} \}$, i.e., non-empty bit-string with length at most $\ell$. The size of this set is

$$\begin{aligned} \sum _{i=1}^{\ell } 2^i = 2^{\ell +1} - 2. \end{aligned}$$

(33)

Let ${\mathscr {X}}$ be a uniform random variable over $\{ 0,1 \}^{n}$. Let a steal algorithm ${{\textsf {S} }}(n-1)$ output $2^{n}-2$ distinct messages, such that each message can encode a unique value of $\textsf {P} ({\mathscr {X}})$, with two possible values (denoted as $x_0$ and $x_1$) of $\textsf {P} ({\mathscr {X}})$ ignored. For any $x \in \{ 0,1 \}^{n} \setminus \{ x_0, x_1 \}$, we have

$$\begin{aligned} \textsf {Adv} _{\mathscr {A}(n-1), \textsf {P} }^{ \mathtt {out}}(x) = \Pr \left[ {\textsf {R} }\left( {{\textsf {S} }}^{{\mathscr {O}}\big (y \leftarrow \textsf {P} (x) \big )} (n-1) \right) = y \right] = 1. \end{aligned}$$

(34)

Therefore,

$$\begin{aligned} \mathop {\Pr }\limits _{x {\mathop {\leftarrow }\limits ^{R}} \{ 0,1 \}^{n}} \left[ \textsf {Adv} _{\mathscr {A}(n-1), \textsf {P} }^\mathtt{{out}}(x) = 1 \right] = 1 - \frac{2}{2^{n}}. \end{aligned}$$

(35)

Therefore, Claim 1 is proved by combining the above equation and the definition of steal entropy in Eq. (5). $\square$

1.2 Appendix B.2: Proof of Lemma 1

Proof of Lemma 1

Let c be any t-time compressor algorithm with output length $\ell \le \xi$ and d be any t-time decompressor algorithm d. We construct a t-adversary $\mathscr {A}^{*}$ with steal algorithm ${{\textsf {S} }}$ and recovery algorithm ${{\textsf {R} }}$ such that: (1) ${{\textsf {S} }}$ invokes the compressor algorithm c to compress the output of $\textsf {P} (x)$ into $\ell$ bits message. From this $\ell$ bits message, ${{\textsf {R} }}$ invokes the decompressor algorithm d to recover the value x. For adversary $\mathscr {A}^{*}$, for every $\ell$, we define a subset $\mathbf {G}_{\ell } \subset \{ 0,1 \}^{n}$ as

$$\begin{aligned} \mathbf {G}_{\ell } \ {{{\mathop {=}\limits ^{{\small {\mathrm {def}}}}}}}\ \left\{ x \in \{0,1 \}^{n} : \textsf {Adv} _{\mathscr {A}^{*}(\ell ), \textsf {P} }^{ \mathtt {out}}(x) \le \frac{1}{2^{\xi - \ell }} + \epsilon \right\} \end{aligned}$$

(36)

From $\inf {{{\mathbb {S}}}}_{\epsilon , t}^\mathtt{out}(\textsf {P} ) \ge \xi$, we get $\Pr _{x \leftarrow {\mathscr {X}} } \left[ x \in \mathbf {G}_{\ell } \right] \ge 1 - \epsilon$.

We can calculate the success probability of the compressor and decompressor as below:

$$\begin{aligned}&\Pr _{y \leftarrow \textsf {P} ({\mathscr {X}})} \left[ d(c(y)) =y \right] \nonumber \\&\quad = \Pr _{x \leftarrow {\mathscr {X}}} \left[ d(c(\textsf {P} (x))) = \textsf {P} (x) \right] \nonumber \\&\quad = \Pr _{x \leftarrow {\mathscr {X}}} \left[ {\textsf {R} }\left( {{\textsf {S} }}^{{\mathscr {O}}\big (y \leftarrow \textsf {P} (x) \big )} (\ell ) \right) = y \right] \nonumber \\&\quad = \Pr _{x \leftarrow {\mathscr {X}}} \left[ \textsf {Adv} _{\mathscr {A}^{*}(\ell ), \textsf {P} }^{ \mathtt {out}}(x) \right] \nonumber \\&\quad = \Pr _{x \leftarrow {\mathscr {X}}} \left[ \left. \textsf {Adv} _{\mathscr {A}^{*}(\ell ), \textsf {P} }^{ \mathtt {out}}(x) \ \right| \ x \in \mathbf {G}_{\ell } \right] \times \Pr _{x \leftarrow {\mathscr {X}}} \left[ x \in \mathbf {G}_{\ell } \right] \nonumber \\&\qquad + \Pr _{x \leftarrow {\mathscr {X}}} \left[ \left. \textsf {Adv} _{\mathscr {A}^{*}(\ell ), \textsf {P} }^{ \mathtt {out}}(x) \ \right| \ x \not \in \mathbf {G}_{\ell } \right] \times \Pr _{x \leftarrow {\mathscr {X}}} \left[ x \not \in \mathbf {G}_{\ell } \right] \end{aligned}$$

(37)

$$\begin{aligned}&\quad \le \left( \frac{1}{2^{\xi - \ell }} + \epsilon \right) \times \Pr _{x \leftarrow {\mathscr {X}}} \left[ x \in \mathbf {G}_{\ell } \right] + 1 \times \Pr _{x \leftarrow {\mathscr {X}}} \left[ x \not \in \mathbf {G}_{\ell } \right] \end{aligned}$$

(38)

$$\begin{aligned}&\quad \le \left( \frac{1}{2^{\xi - \ell }} + \epsilon \right) \times 1 + 1 \times \Pr _{x \leftarrow {\mathscr {X}}} \left[ x \not \in \mathbf {G}_{\ell } \right] \end{aligned}$$

(39)

$$\begin{aligned}&\quad \le \left( \frac{1}{2^{\xi - \ell }} + \epsilon \right) + \epsilon \end{aligned}$$

(40)

$\square$

1.3 Appendix B.3: Proof of Lemma 2

Sketch Proof of Lemma 2

Let algorithm $\textsf {P}$ be a cryptographically secure pseudorandom number generator, with output length $m=poly(n)$. If a pair of efficient algorithms $c(\cdot ), d(\cdot )$ can compress and uncompress the output of $\textsf {P} ({\mathscr {X}})$, then these two algorithms $c(\cdot )$ and $d(\cdot )$ constitute an efficient distinguisher which can distinguish output of $\textsf {P} ({\mathscr {X}})$ from true randomness, conflicting with assumption that $\textsf {P}$ is cryptographically secure pseudorandom number generator. $\square$

1.4 Appendix B.4: Proof of Lemma 3

Sketch Proof of Lemma 3

Let algorithm $\textsf {P}$ be a cryptographically secure pseudorandom number generator, with output length $m=poly(n)$. This lemma can be easily proved by evaluating the steal entropy of algorithm $\textsf {P}$ and Hill entropy of variable $\textsf {P} ({\mathscr {X}})$. $\square$

1.5 Appendix B.5: Proof of Lemma 5

Proof of Lemma 5

Let the algorithm $\textsf {P}$ be an instance of exposure-resilient function $g(x)=G(f(x))$ as in Lemma 4.6 in Canetti el al. [21], which is quoted as Lemma 4 in this paper, such that the parameters satisfy this condition: $n = \ell + poly(k)$. Clearly, the constructed function $\textsf {P}$ is a computational $\ell$-ERF. On the other hand, under our formulation, the attacker may simply steal k bits value $y=f(x)$ via backdoor and covert channel and then compute and output all of m bits output $\textsf {P} (x) = g(x) = G(y)$. Thus, the steal entropy of in output $\sup {{{\mathbb {S}}}}_{\epsilon , t}^\mathtt{out}(g) \le k.$ $\square$

1.6 Appendix B.6: Proof of Lemma 6

Proof of Lemma 6

Construction of ${\textsf {R} }_1$. We construct ${\textsf {R} }_1$ by repeatedly invoking ${\textsf {R} }_0$ in this way: Given input $\mathtt{Msg}$ and $y=\textsf {P} (x)$, recovery algorithm ${\textsf {R} }_1$ makes N number of independent invocation on randomized algorithm ${\textsf {R} }_0(\mathtt{Msg}, y)$ using independent random seeds, and obtains N outputs , denoted as $({\bar{x}}^{(j)}, \mathbf {I}^{(j)})$, where $j \in [1, N]$. For each bit position $i \in [1, n]$, count how many sets $\mathbf {I}^{(j)}$, $j \in [1, N]$, contains element i and denote this count value as weight $w_i := |\{ \mathbf {I}^{(j)}: i \in \mathbf {I}^{(j)} \}|$. Let $\mathbf {I}$ be the set of $(\ell + \varDelta )$ bit positions i’s from [1, n] with top $(\ell + \varDelta )$ largest weight $w_i$. For each $i \in \mathbf {I}$, make a majority vote on set $\{ {\bar{x}}^{(j)}[i]: i \in \mathbf {I}^{(j)} \}$ of bit values, and denote the resulting bit as ${\bar{x}}[i]$. For each $i \not \in \mathbf {I}$, randomly choose a bit and denoted it as ${\bar{x}}[i]$. ${\textsf {R} }_1$ will output $({\bar{x}} = {\bar{x}}[1]..{\bar{x}}[n], \mathbf {I})$.

Claim 3

Let $N = \varTheta (1/\epsilon )$. If $\mathtt{Msg} \in {\mathbf {G}}_\mathtt{msg}^{{\textsf {R} }_0}(\ell , \varDelta , x, 0.5+\epsilon )$, then $\mathtt{Msg} \in {\mathbf {G}}_\mathtt{msg}^{{\textsf {R} }_1}(\ell , \varDelta , x, 1-negl(\lambda ))$. In other words,

${\mathbf {G}}_\mathtt{msg}^{{\textsf {R} }_0}(\ell , \varDelta , x, 0.5+\epsilon ) = {\mathbf {G}}_\mathtt{msg}^{{\textsf {R} }_1}(\ell , \varDelta , x, 1-negl(\lambda ))$

Claim 3 could be proved easily using Hoeffding’s Inequality and our definition of ${\mathbf {G}}_\mathtt{msg}$.

Construction of ${\textsf {S} }_1$. Make $N'$ number of independent invocation of randomized algorithm ${\textsf {S} }^{{\mathscr {O}}(\textsf {P} (x))}$ and obtains output $\mathtt{Msg}_j$, $j \in [1, N']$. Loop from $j = 1$ up to $N'$, invoke algorithm ${\textsf {R} }_1(\mathtt{Msg}_j, \textsf {P} (x))$ to obtain output $({\hat{x}}^{(j)}, \mathbf {I}^{(j)})$. Check if the following two conditions hold: (1) the size of set $\mathbf {I}^{(j)}$ is at least $\ell + \varDelta$; (2) for each $i \in \mathbf {I}^{(j)}$, ${\hat{x}}^{(j)}[i] = x[i]$. If both of the above two conditions hold, then abort the loop and output $\mathtt{Msg}_j$. Otherwise, for any j, at least one of the above condition does not hold, then fail.

Claim 4

Let $N' = \varTheta (1/\epsilon )$. ${\mathbf {G}}_\mathtt{x}^{{\textsf {S} }_0, {\textsf {R} }_0}(\ell , \varDelta , 0.5+\epsilon , 0.5+\epsilon ) = {\mathbf {G}}_\mathtt{x}^{{\textsf {S} }_0, {\textsf {R} }_1}(\ell , \varDelta , 0.5+\epsilon , 1-negl(\lambda ))$.

Claim 4 can be easily proved using the result of Claim 3 and the definition of ${\mathbf {G}}_\mathtt{x}$: More precisely, just replace set ${\mathbf {G}}_\mathtt{msg}^{{\textsf {R} }_0}(\ell , \varDelta , x, 0.5+\epsilon )$ with ${\mathbf {G}}_\mathtt{msg}^{{\textsf {R} }_1}(\ell , \varDelta , x, 1-negl(\lambda ))$ in Eq. 20.

Claim 5

Let $N' = \varTheta (1/\epsilon )$. ${\mathbf {G}}_\mathtt{x}^{{\textsf {S} }_0, {\textsf {R} }_1}(\ell , \varDelta , 0.5+\epsilon , 1-negl(\lambda ))$ $=$ ${\mathbf {G}}_\mathtt{x}^{{\textsf {S} }_1, {\textsf {R} }_1}(\ell , \varDelta , 1 - negl(\lambda ), 1- negl(\lambda ))$.

Claim 3 could be proved easily using Hoeffding’s Inequality and our definition of ${\mathbf {G}}_\mathtt{msg}$. $\square$

1.7 Appendix B.7: Proof of Theorem 7

Sketch Proof of Theorem 7

Let $\textsf {Enc}$ be any semantic secure bock cipher with block length equal to 128, and Cipher Block Chaining (CBC) mode is chosen to encryption multi-blocks long message. Let $\textsf {P} (x)$ be the suffix of ciphertext $\textsf {Enc} _k(\mathtt{LongMsg})$, by removing the first 128 bits from $\textsf {Enc} _k(\mathtt{LongMsg})$. It is easy to prove the above theorem by analyzing the Steal entropy and Strong Steal entropy of algorithm $\textsf {P}$. $\square$

1.8 Appendix B.8: Proof of Lemma 8

Proof of Lemma 8

An adversary could obtain (e.g., via eavesdropping) almost all ciphertext blocks $m_i$’s with $i \in \mathbf {S} \subset [1, s+1]$ and the size of set $\mathbf {S}$ is close to $s+1$, e.g., $|\mathbf {S}| = s - 10$ (assuming total bit-length of 11 ciphertext blocks is much larger than bit length of key $K'$ ). The adversary could choose to steal the short secret key $K'$ via backdoor algorithm $\textsf {S}$ and the covert channel and decrypt all ciphertext block $m_i$’s with $i \in \mathbf {S}$ using the key K’, although with 11 ciphertext blocks missing. Therefore, by stealing a short key $K'$, the adversary is about to obtain all most all message blocks $m_i$ with $i \in \mathbf {S}$ except 10 or 11 missing message blocks. By definition of strong-steal entropy (respectively, rate) in input, the above adversary is a witness that Lemma 8 holds. $\square$

1.9 Appendix B.9: Proof of Corollary 10

Proof of Corollary 10

This Corollary can be proved by evaluating the infimum of strong steal entropy of $\varPhi _0$ in input using Theorem 9.

Note that $\inf {{{\mathbb {S}}}}_{\epsilon , t}^\mathtt{sin}(\textsc {Suffix}_{\varPhi _0}) \ge \zeta$ trivially implies that $\varPhi _0$ is a $\delta (n)$-steal-resilient encryption, with $\delta (n) = \frac{1}{\rho \tau }$ by Definition 9 and the equality $n = \rho \zeta (1+\tau )$.

Next we will prove $\inf {{{\mathbb {S}}}}_{\epsilon , t}^\mathtt{sin}(\textsc {Suffix}_{\varPhi _0}) \ge \zeta$ using proof by contradiction. Our hypothesis is that: $\inf {{{\mathbb {S}}}}_{\epsilon , t}^\mathtt{sin}(\textsc {Suffix}_{\varPhi _0})$ $\ge$ $\zeta$ does not hold. By Definition 7 (more precisely, Equation (23)), there exists a t-adversary $\mathscr {A} = ({\textsf {S} }, {\textsf {R} })$, such that

$$\begin{aligned}&\forall \epsilon \ge \lambda ^{-c}, \nonumber \\&\Pr _{x \in _R \{ 0,1 \}^{n} } [ x \in {\mathbf {G}}_\mathtt{x}^{{\textsf {S} }, {\textsf {R} }}(\ell , \varsigma (\ell , \epsilon ) + 1 - \ell , 0.5 + \epsilon , 0.5 + \epsilon )] \nonumber \\&\ge 0.5 + 1/poly(\lambda ) \end{aligned}$$

(41)

According to Lemma 6, there exists another $t \cdot \varTheta (\frac{1}{\epsilon })$-adversary $\mathscr {A}' = ({\textsf {S} }', {\textsf {R} }')$ such that

$$\begin{aligned}&\Pr _{x \in _R \{ 0,1 \}^{n} } \Big [ x \in {\mathbf {G}}_\mathtt{x}^{{\textsf {S} }', {\textsf {R} }'}(\ell , \varsigma (\ell , \epsilon ) + 1 - \ell , 1-negl(\lambda ), \nonumber \\&1-negl(\lambda ))\Big ] \nonumber \\&\ge 0.5 + 1/poly(\lambda ) \end{aligned}$$

(42)

For any $x \in {\mathbf {G}}_\mathtt{x}^{{\textsf {S} }', {\textsf {R} }'}(\ell , \varDelta , \alpha , \beta )$, let $({\bar{x}}, \mathbf {I})$ denotes the output of recovery algorithm $\textsf {R} (\mathtt{Msg}, \textsf {P} (x))$, we have

$$\begin{aligned} \forall i \in \mathbf {I},&\Pr [ {\bar{x}}[i] = x[i] ] = \nonumber \\&\Pr \Big [ {\bar{x}}[i] = x[i] \ |\ \mathtt{Msg} \in {\mathbf {G}}_\mathtt{msg}^{{\textsf {R} }}(\ell , \varDelta , x, \beta ) \Big ] \times \nonumber \\&\Pr \Big [ \mathtt{Msg} \in {\mathbf {G}}_\mathtt{msg}^{{\textsf {R} }}(\ell , \varDelta , x, \beta ) \Big ] \nonumber \\&\ge \alpha \cdot \beta \nonumber \\&= (1{-}negl(\lambda )) \times (1{-}negl(\lambda )) \ge 1{-} 2 \times negl(\lambda ). \end{aligned}$$

(43)

This means that, the polynomial time adversary $\mathscr {A}' = ({\textsf {S} }', {\textsf {R} }')$ could steal at most $\ell \le \zeta - 2$ bits of message and output $\ell +2 \le \zeta$ bits of information of x (i.e., x[i] for $i \in \mathbf {I}$) with overwhelming high probability $1- 2 \times negl(\lambda )$, with at least $0.5 + 1/poly(\lambda )$ fraction of input x in the domain $\{ 0,1 \}^{n}$.

According to Theorem 9, and our argument after Property 1 on page 7, any $\zeta$ distinct bits x[j] together will have $\zeta$ bits joint Shannon entropy.

So any $\ell +2$ bits of x[i]’s for at least $0.5 + 1/poly(\lambda )$ fraction of input x in the domain $\{ 0,1 \}^{n}$, will have joint Shannon entropy at least

So collection of x[i]’s in the output of ${\textsf {R} }'$ will have joint Shannon entropy at least

$$\begin{aligned} \log \left( 2^{\ell +2} \times (1- 2 \times negl(\lambda ) ) \times \big ( 0.5 + 1/poly(\lambda ) \big ) \right) \ge \ell +1 . \end{aligned}$$

(44)

However ${\textsf {S} }'(\ell )$ could only encode $\sum _{i=1}^{\ell } 2^{i} = 2^{\ell +1} -2$ distinct messages, it is a contradiction and the hypothesis does not hold. $\square$

Appendix C: Existing semantic secure block cipher is not steal-resilient

It is easy to see that large block size (larger than our target upper bound $\ell$ of information leakage) is a necessary but insufficient condition to be strong steal resilient. Unfortunately, by our knowledge, all of existing widely deployed ciphers have very small block size (e.g., 128 or 256 bits).

Proof (of Claim 2)

The block size of AES is very short, only 128 bits.

Case 1 If we split the long AES ciphertext, without cutting every single ciphertext block. Then the large portion of ciphertext $C_1$ will consist of a lot (at least 3 for large plaintext size n) of complete ciphertext blocks. Adversary could learn the entire decryption key, which is at most 256 bits, via the steal algorithm ${\textsf {S} }(\ell )$ with $\ell = 256$, and decrypt all complete ciphertext blocks in $C_1$. That is, leakage of 256 bits via ${\textsf {S} }$, allows ${\textsf {R} }$ to recover at least $128 \times 3 > 256$ bits of plaintext. Therefore, the supreme of strong steal entropy in input of AES is at most 256, which is a constant independent on plaintext size n. Thus the claim is proved.

Case 2 Suppose we split each AES ciphertext block with 128 bits length. Then the smaller portion is at most 64 bits. Via the leak oracle ${\textsf {S} }(\ell =576)$, adversary could learn (1) the entire decryption key, which is at most 256 bits; and (2) the missing parts (which is in $C_0$) of 5 ciphertext blocks in $C_1$, which is at most $64\times 5 = 320$ bits. Then adversary could decrypt the 5 complete ciphertext blocks to recover $128 \times 5 = 640 > 576=256 + 320$ bits plaintext via ${\textsf {R} }$ algorithm. Therefore, the supreme of strong steal entropy in input of AES is at most 576 bits, which is a constant independent on plaintext size n. Thus the claim is proved.

Case 3 Assume we split some ciphertext blocks and keep some ciphertext blocks complete. For sufficiently large ciphertext size n, we can always find sufficient number of ciphertext blocks, to make proof in either Case 1 or Case 2 work. So the claim is proved. $\square$