-
Notifications
You must be signed in to change notification settings - Fork 21
/
Copy pathindex.html
223 lines (223 loc) · 19.8 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
<!DOCTYPE html>
<!-- Akai (pandoc HTML5 template)
designer: soimort
last updated: 2016-05-06
last adapted: 2016-11-01 -->
<html>
<head>
<meta charset="utf-8">
<meta name="generator" content="pandoc">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<meta name="author" content="Mort Yao">
<meta name="dcterms.date" content="2017-01-01">
<title>The Adversarial Computation</title>
<link rel="canonical" href="https://www.soimort.org/mst/3">
<style type="text/css">code { white-space: pre; }</style>
<link rel="stylesheet" href="//cdn.soimort.org/normalize/5.0.0/normalize.min.css">
<link rel="stylesheet" href="//cdn.soimort.org/fonts/latest/URW-Palladio-L.css">
<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css">
<link rel="stylesheet" href="/__/css/style.css">
<link rel="stylesheet" href="/__/css/pygments.css">
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_CHTML-full" type="text/javascript"></script>
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
<script src="//cdn.soimort.org/jk/latest/jk.min.js"></script>
<script src="/__/js/main.js"></script>
<link rel="icon" href="/favicon.png">
<link rel="apple-touch-icon" href="/favicon.png">
<link rel="alternate" type="application/atom+xml" href="/feed.atom">
</head>
<body>
<article>
<header>
<h1 class="title"><a href="https://www.soimort.org/mst/3">The Adversarial Computation</a></h1>
<h1 class="subtitle"><a href="https://www.soimort.org/mst/3">Build me an unbreakable cryptosystem.</a></h1>
<address class="author">Mort Yao</address>
<h3 class="date">2017-01-01</h3>
</header>
<div id="content">
<p><a href="https://wiki.soimort.org/comp/">Theory of computation</a> (computability and complexity) forms the basis for modern cryptography:</p>
<ul>
<li>What is an <a href="https://wiki.soimort.org/comp/algorithm/">algorithm</a>?
<ul>
<li>An algorithm is a <em>computational method</em> for solving an <em>abstract problem</em>.</li>
<li>An algorithm takes as input a set <span class="math inline">\(I\)</span> of <em>problem instances</em>, and outputs a solution from the set <span class="math inline">\(S\)</span> of <em>problem solutions</em>.</li>
<li>An algorithm is represented in a well-defined <a href="https://wiki.soimort.org/comp/language/">formal language</a>.</li>
<li>An algorithm must be able to be represented within a finite amount of time and space (otherwise it cannot be actually used for solving any problem).</li>
<li>An algorithm can be simulated by any <em>model of computation</em>:
<ul>
<li><em>Turing machine</em> is a model implemented through internal <em>states</em>.</li>
<li><em>λ-calculus</em> is a model based on pure <em>functions</em>.</li>
<li>All Turing-complete models are equivalent in their computational abilities.</li>
</ul></li>
<li>Computability: Not every abstract problem is solvable. Notably, there exists a decision problem for which some instances can neither be accepted nor rejected by any algorithm. (<em>Undecidable problem</em>)</li>
<li>Complexity:
<ul>
<li>The complexity class P is closed under polynomial-time reductions. Hence, proof by reduction can be a useful technique in provable security of cryptosystems.</li>
<li>If one can prove that P = NP, then one-way functions do not exist. This would invalidate the construction of cryptographically secure pseudorandom generators (PRG). (<em>Pseudorandom generator theorem</em>)</li>
</ul></li>
<li>In many scenarios, we assume that an algorithm acts as a stateless computation and takes independent and identically distributed inputs. It differs from a computer program conceptually.</li>
<li>An algorithm can be either <em>deterministic</em> or <em>probabilistic</em>.
<ul>
<li>For probabilistic algorithms, the source of randomness may be from:
<ul>
<li>External (physical) input of high entropy.</li>
<li>Pseudorandomness: Since everything computational is deterministic, the existence of pseudorandomness relies on the (assumed) existence of one-way functions and PRGs.</li>
</ul></li>
</ul></li>
</ul></li>
</ul>
<p>Generally, pseudorandom generators used in probabilistic algorithms yield random bits according to the uniform distribution, so it is worth mentioning:</p>
<ul>
<li>Basic probability theory
<ul>
<li><a href="https://wiki.soimort.org/math/probability/#discrete-uniform-distribution">Discrete uniform distribution</a>. <span class="math inline">\(\mathcal{U}\{a,b\}\)</span>. The probability distribution where a finite number of values are equally likely to be observed (with probability <span class="math inline">\(\frac{1}{b-a+1}\)</span>).</li>
</ul></li>
</ul>
<p>Cryptographic schemes are defined as tuples of deterministic or probabilistic algorithms:</p>
<ul>
<li><a href="https://wiki.soimort.org/crypto/intro/">Principles of modern cryptography</a>
<ul>
<li>Formal description of a <em>private-key encryption scheme</em> <span class="math inline">\(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\)</span> with message space <span class="math inline">\(\mathcal{M}\)</span>.
<ul>
<li><span class="math inline">\(\mathsf{Gen}\)</span>, <span class="math inline">\(\mathsf{Enc}\)</span>, <span class="math inline">\(\mathsf{Dec}\)</span> are three algorithms.</li>
<li>Correctness: <span class="math inline">\(\mathsf{Dec}_k(\mathsf{Enc}_k(m)) = m\)</span>.</li>
<li>For the correctness equality to hold, <span class="math inline">\(\mathsf{Dec}\)</span> should be deterministic.</li>
<li>Assume that we have access to a source of randomness, <span class="math inline">\(\mathsf{Gen}\)</span> should choose a key at random thus is probabilistic. If <span class="math inline">\(\mathsf{Gen}\)</span> is deterministic and always generate the same key, such an encryption scheme is of no practical use and easy to break.</li>
<li><span class="math inline">\(\mathsf{Enc}\)</span> can be either deterministic (e.g., as in one-time pads) or probabilistic. Later we will see that for an encryption scheme to be CPA-secure, <span class="math inline">\(\mathsf{Enc}\)</span> should be probabilistic.</li>
</ul></li>
<li><strong>Kerchhoffs’ principle (Shannon’s maxim)</strong> claims that a cryptosystem should be secure even if the scheme <span class="math inline">\((\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\)</span> is known to the adversary. That is, security should rely solely on the secrecy of the private key.</li>
<li>Provable security of cryptosystems requires:
<ol type="1">
<li>Formal definition of security;</li>
<li>Minimal assumptions;</li>
<li>Rigorous proofs of security.</li>
</ol></li>
<li>Common attacks and notions of security:
<ul>
<li><strong>Ciphertext-only attack</strong>.
<ul>
<li>A cryptosystem is said to be <em>perfectly secret</em> if it is theoretically unbreakable under ciphertext-only attack.</li>
<li>A cryptosystem is said to be <em>computationally secure</em> if it is resistant to ciphertext-only attack (by any polynomial-time adversary).</li>
</ul></li>
<li><strong>Known-plaintext attack (KPA)</strong>. A cryptosystem is <em>KPA-secure</em> if it is resistant to KPA.
<ul>
<li>KPA-security implies ciphertext-only security.</li>
</ul></li>
<li><strong>Chosen-plaintext attack (CPA)</strong>. A cryptosystem is <em>CPA-secure</em> (or <em>IND-CPA</em>) if it is resistant to CPA.
<ul>
<li>IND-CPA implies KPA-security.</li>
</ul></li>
<li><strong>Chosen-ciphertext attack (CCA)</strong>. A cryptosystem is <em>CCA-secure</em> (or <em>IND-CCA1</em>) if it is resistant to CCA; furthermore, a cryptosystem is <em>IND-CCA2</em> if it is resistant to adaptive CCA (where the adversary may make further calls to the oracle, but may not submit the challenge ciphertext).
<ul>
<li>IND-CCA1 implies IND-CPA.</li>
<li>IND-CCA2 implies IND-CCA1. Thus, IND-CCA2 is the strongest of above mentioned definitions of security.</li>
</ul></li>
</ul></li>
</ul></li>
<li><a href="https://wiki.soimort.org/crypto/perfect-secrecy/">Perfect secrecy</a>
<ul>
<li>Two equivalent definitions: (proof of equivalence uses Bayes’ theorem)
<ul>
<li><span class="math inline">\(\Pr[M=m\,|\,C=c] = \Pr[M=m]\)</span>. (Observing a ciphertext <span class="math inline">\(c\)</span> does not leak any information about the underlying message <span class="math inline">\(m\)</span>)</li>
<li><span class="math inline">\(\Pr[\mathsf{Enc}_K(m)=c] = \Pr[\mathsf{Enc}_K(m')=c]\)</span>. (The adversary has no bias when distinguishing two messages if given only the ciphertext <span class="math inline">\(c\)</span>)</li>
</ul></li>
<li><strong>Perfect indistinguishability</strong> defined on adversarial indistinguishability experiment <span class="math inline">\(\mathsf{PrivK}_{\mathcal{A},\Pi}^\mathsf{eav}\)</span>:
<ul>
<li><span class="math inline">\(\Pr[\mathsf{PrivK}_{\mathcal{A},\Pi}^\mathsf{eav} = 1] = \frac{1}{2}\)</span>. (No adversary can win the indistinguishability game with a probability better than random guessing)</li>
</ul></li>
<li>Perfect indistinguishability is equivalent to the definition of perfect secrecy.</li>
<li>The adversarial indistinguishability experiment is a very useful setting in defining provable security, e.g., the definition of computational indistinguishability: (for arbitrary input size <span class="math inline">\(n\)</span>)
<ul>
<li><span class="math inline">\(\Pr[\mathsf{PrivK}_{\mathcal{A},\Pi}^\mathsf{eav}(n) = 1] \leq \frac{1}{2} + \mathsf{negl}(n)\)</span> where <span class="math inline">\(\mathsf{negl}(n)\)</span> is a negligible function.</li>
</ul></li>
<li>Perfect secrecy implies that <span class="math inline">\(|\mathcal{K}| \geq |\mathcal{M}|\)</span>, i.e., the key space must be larger than the message space. If <span class="math inline">\(|\mathcal{K}| < |\mathcal{M}|\)</span>, then the scheme cannot be perfectly secure.</li>
<li><strong>Shannon’s theorem</strong>: If <span class="math inline">\(|\mathcal{K}| = |\mathcal{M}| = |\mathcal{C}|\)</span>, an encryption scheme is perfectly secret iff:
<ul>
<li><span class="math inline">\(k \in \mathcal{K}\)</span> is chosen uniformly.</li>
<li>For every <span class="math inline">\(m \in \mathcal{M}\)</span> and <span class="math inline">\(c \in \mathcal{C}\)</span>, there exists a unique <span class="math inline">\(k \in \mathcal{K}\)</span> such that <span class="math inline">\(\mathsf{Enc}_k(m) = c\)</span>.</li>
</ul></li>
</ul></li>
</ul>
<p>A brief, formalized overview of some classical ciphers, and their security:</p>
<ul>
<li><a href="https://wiki.soimort.org/crypto/one-time-pad/">One-time pad (Vernam cipher)</a>: XOR cipher when <span class="math inline">\(|\mathcal{K}| = |\mathcal{M}|\)</span>.
<ul>
<li>One-time pad is perfectly secret. The proof simply follows from Bayes’ theorem. (Also verified by Shannon’s theorem. While one-time pad was initially introduced in the 19th century and patented by G. Vernam in 1919, it was not until many years later Claude Shannon gave a formal definition of information-theoretical security and proved that one-time pad is a perfectly secret scheme in his groundbreaking paper. <a href="#ref-shannon1949communication"><span class="citation" data-cites="shannon1949communication">[1]</span></a>)</li>
<li>One-time pad is deterministic. Moreover, it is a reciprocal cipher (<span class="math inline">\(\mathsf{Enc} = \mathsf{Dec}\)</span>).</li>
<li>One-time pad is <em>not</em> secure when the same key is applied in multiple encryptions, and it is <em>not</em> CPA-secure. In fact, an adversary can succeed in such indistinguishability experiments with probability 1.</li>
</ul></li>
<li>Insecure historical ciphers:
<ul>
<li><a href="https://wiki.soimort.org/crypto/classical/shift/">Shift cipher</a>: Defined with key space <span class="math inline">\(\mathcal{K}=\{0,\dots,n-1\}\)</span>. (<span class="math inline">\(n=|\Sigma|\)</span>)
<ul>
<li><span class="math inline">\(|\mathcal{K}|=n\)</span>, <span class="math inline">\(|\mathcal{M}|=n^\ell\)</span>.</li>
<li>Cryptanalysis using frequency analysis.</li>
</ul></li>
<li><a href="https://wiki.soimort.org/crypto/classical/substitution/">Substitution cipher</a>: Defined with key space <span class="math inline">\(\mathcal{K} = \mathfrak{S}_\Sigma\)</span> (symmetric group on <span class="math inline">\(\Sigma\)</span>).
<ul>
<li><span class="math inline">\(|\mathcal{K}|=n!\)</span>, <span class="math inline">\(|\mathcal{M}|=n^\ell\)</span>.</li>
<li>Cryptanalysis using frequency analysis.</li>
</ul></li>
<li><a href="https://wiki.soimort.org/crypto/classical/vigenere/">Vigenère cipher (poly-alphabetic shift cipher)</a>: Like (mono-alphabetic) shift cipher, but the key length is an (unknown) integer <span class="math inline">\(t\)</span>.
<ul>
<li><span class="math inline">\(|\mathcal{K}|=n^t\)</span>, <span class="math inline">\(|\mathcal{M}|=n^\ell\)</span>. (Typically <span class="math inline">\(t \ll \ell\)</span>)</li>
<li>Cryptanalysis using Kasiski’s method, index of coincidence method and frequency analysis.</li>
</ul></li>
</ul></li>
</ul>
<p>Lessons learned from these classical ciphers: While perfect secrecy is easy to achieve (one-time pads), designing practical cryptographic schemes (with shorter keys, and computationally hard to break) can be difficult.</p>
<section id="where-do-random-bits-come-from" class="level2">
<h2>Where do random bits come from?</h2>
<p>The construction of private-key encryption schemes involves probabilistic algorithms. We simply assume that an unlimited supply of independent, unbiased random bits is available for these cryptographic algorithms. But in practice, this is a non-trivial issue, as the source of randomness must provide high-entropy data so as to accommodate cryptographically secure random bits.</p>
<p>In the perfectly secret scheme of one-time pads, the key generation algorithm <span class="math inline">\(\mathsf{Gen}\)</span> requires the access to a source of randomness in order to choose the uniformly random key <span class="math inline">\(k \in \mathcal{K}\)</span>. Practically, high-entropy data may be collected via physical input or even fully written by hand with human labor.</p>
<p>Theoretically, without external intervention, we have:</p>
<p><strong>Conjecture 3.1.</strong> <em>Pseudorandom generators exist.</em></p>
<p><strong>Theorem 3.2. (Pseudorandom generator theorem)</strong> <em>Pseudorandom generators exist if and only if one-way functions exist.</em></p>
<p>Pseudorandomness is also a basic construction in CPA-secure encryption algorithms (<span class="math inline">\(\mathsf{Enc}\)</span>), e.g., in stream ciphers and block ciphers.</p>
<p>So what is an acceptable level of pseudorandomness, if we are not sure whether such generators theoretically exist? Intuitively, if one cannot distinguish between a “pseudorandom” string (generated by a PRG) and a truly random string (chosen according to the uniform distribution), we have confidence that the PRG is a good one. Various statistical tests have been designed for testing the randomness of PRGs.</p>
</section>
<section id="pseudorandomness-and-ind-cpa" class="level2">
<h2>Pseudorandomness and IND-CPA</h2>
<p>It holds true that:</p>
<p><strong>Corollary 3.3.</strong> By redefining the key space, we can assume that any encryption scheme <span class="math inline">\(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\)</span> satisfies</p>
<ol type="1">
<li><span class="math inline">\(\mathsf{Gen}\)</span> chooses a uniform key.</li>
<li><span class="math inline">\(\mathsf{Enc}\)</span> is deterministic.</li>
</ol>
<p>If so, why do we still need probabilistic <span class="math inline">\(\mathsf{Enc}\)</span> in CPA-secure encryptions? Can’t we just make <span class="math inline">\(\mathsf{Enc}\)</span> deterministic while still being CPA-secure?</p>
<p>The first thing to realize is that chosen-plaintext attacks are geared towards multiple encryptions (with the same secret key <span class="math inline">\(k\)</span>), so when the adversary obtains a pair <span class="math inline">\((m_0, c_0)\)</span> such that <span class="math inline">\(\Pr[C=c_0\,|\,M=m_0] = 1\)</span>, <em>the key is already leaked</em>. (Recall that the adversary knows the <em>deterministic</em> algorithm <span class="math inline">\(\mathsf{Enc}_k\)</span>, thus reversing <span class="math inline">\(k\)</span> from known <span class="math inline">\(m_0\)</span> and <span class="math inline">\(c_0\)</span> can be quite feasible; e.g., in a one-time pad, <span class="math inline">\(k = m_0 \oplus c_0\)</span>.) The only way to get around this is make <span class="math inline">\(\mathsf{Enc}_k\)</span> <em>probabilistic</em> (constructed from a <em>pseudorandom function</em>), such that an adversary cannot reverse the key efficiently within polynomial time.</p>
<p>Note that perfect secrecy is not possible under CPA, since there is a small possibility that the adversary will reverse the key (by, for example, traversing an exponentially large lookup table of all random bits) and succeed in the further indistinguishability experiment with a slightly higher (but negligible) probability.</p>
</section>
<section id="historical-exploits-of-many-time-pad" class="level2">
<h2>Historical exploits of many-time pad</h2>
<p>One-time pad is one of the most (provably) secure encryption schemes, and its secrecy does not rely on any computational hardness assumptions. However, it requires that <span class="math inline">\(|\mathcal{K}| \geq |\mathcal{M}|\)</span> (which in fact is a necessary condition for any perfectly secret scheme), thus its real-world use is limited.</p>
<p>The one-time key <span class="math inline">\(k\)</span> (uniformly chosen from the key space <span class="math inline">\(\mathcal{K}\)</span>) may <em>not</em> be simply reused in multiple encryptions. Assume that <span class="math inline">\(|\mathcal{K}| = |\mathcal{M}|\)</span>, for encryptions of <span class="math inline">\(n\)</span> messages, the message space is expanded to size <span class="math inline">\(|\mathcal{M}|^n\)</span>, while the key space remains <span class="math inline">\(\mathcal{K}\)</span>, thus we have <span class="math inline">\(|\mathcal{K}| < |\mathcal{M}|^n\)</span>. Such a degraded scheme (many-time pad) is theoretically insecure and vulnerable to several practical cryptanalyses.</p>
<p>A historical exploit of the vulnerability of many-time pad occurred in the VENONA project, where the U.S. Army’s Signal Intelligence Service (later the NSA) aimed at decrypting messages sent by the USSR intelligence agencies (KGB) over a span of 4 decades. As the KGB mistakenly reused some portions of their one-time key codebook, the SIS was able to break a good amount of the messages.<a href="#fn1" class="footnoteRef" id="fnref1"><sup>1</sup></a></p>
</section>
<section id="references-and-further-reading" class="level2">
<h2>References and further reading</h2>
<p><strong>Books:</strong></p>
<p>J. Katz and Y. Lindell, <em>Introduction to Modern Cryptography</em>, 2nd ed.</p>
<p><strong>Papers:</strong></p>
<div id="refs" class="references">
<div id="ref-shannon1949communication">
<p>[1] C. E. Shannon, “Communication theory of secrecy systems,” <em>Bell system technical journal</em>, vol. 28, no. 4, pp. 656–715, 1949. </p>
</div>
</div>
</section>
<section class="footnotes">
<hr />
<ol>
<li id="fn1"><p>R. L. Benson, “The Venona story.” <a href="https://www.nsa.gov/about/cryptologic-heritage/historical-figures-publications/publications/coldwar/assets/files/venona_story.pdf" class="uri">https://www.nsa.gov/about/cryptologic-heritage/historical-figures-publications/publications/coldwar/assets/files/venona_story.pdf</a><a href="#fnref1" class="footnoteBack">↩</a></p></li>
</ol>
</section>
</div>
<!-- (www.soimort.org) last updated: 2016-05-07 -->
<aside id="soimort-toolbar">
<a href="/"><i class="fa fa-home" aria-hidden="true"></i></a>
</aside>
</article>
</body>
</html>