Marked unused slots in the trustdb.
[gnupg.git] / doc / gph / c2.sgml
1 <chapter id="concepts" xreflabel="2">
2 <docinfo>
3 <date>
4 $Id$
5 </date>
6 </docinfo>
7 <title>
8 Concepts
9 </title>
10
11 <para>
12 &Gnupg; makes uses of several cryptographic concepts including 
13 <firstterm>symmetric ciphers</firstterm>, 
14 <firstterm>public-key ciphers</firstterm>, and 
15 <firstterm>one-way hashing</firstterm>.
16 You can make basic use &gnupg; without fully understanding these concepts,
17 but in order to use it wisely some understanding of them is necessary.
18 </para>
19
20 <para>
21 This chapter introduces the basic cryptographic concepts used in GnuPG.
22 Other books cover these topics in much more detail.
23 A good book with which to pursue further study is 
24 <ulink url="http://www.counterpane.com/schneier.html">Bruce 
25 Schneier</ulink>'s
26 <ulink url="http://www.counterpane.com/applied.html">"Applied 
27 Cryptography"</ulink>.
28 </para>
29
30 <sect1>
31 <title>
32 Symmetric ciphers
33 </title>
34
35 <para>
36 A symmetric cipher is a cipher that uses the same key for both encryption
37 and decryption.
38 Two parties communicating using a symmetric cipher must agree on the
39 key beforehand.
40 Once they agree, the sender encrypts a message using the key, sends it
41 to the receiver, and the receiver decrypts the message using the key.
42 As an example, the German Enigma is a symmetric cipher, and daily keys
43 were distributed as code books.
44 Each day, a sending or receiving radio operator would consult his copy
45 of the code book to find the day's key.
46 Radio traffic for that day was then encrypted and decrypted using the
47 day's key.
48 Modern examples of symmetric ciphers include 3DES, Blowfish, and IDEA.
49 </para>
50
51 <para>
52 A good cipher puts all the security in the key and none in the algorithm.
53 In other words, it should be no help to an attacker if he knows which
54 cipher is being used.
55 Only if he obtains the key would knowledge of the algorithm be needed.
56 The ciphers used in &gnupg; have this property.
57 </para>
58
59 <para>
60 Since all the security is in the key, then it is important that it be
61 very difficult to guess the key.
62 In other words, the set of possible keys, &ie;, the <emphasis>key
63 space</emphasis>, needs
64 to be large.
65 While at Los Alamos, Richard Feynman was famous for his ability to
66 crack safes.
67 To encourage the mystique he even carried around a set of tools
68 including an old stethoscope.
69 In reality, he used a variety of tricks to reduce the number of
70 combinations he had to try to a small number and then simply guessed
71 until he found the right combination.
72 In other words, he reduced the size of the key space.
73 </para>
74
75 <para>
76 Britain used machines to guess keys during World War 2.
77 The German Enigma had a very large key space, but the British built
78 speciailzed computing engines, the Bombes, to mechanically try 
79 keys until the day's key was found.
80 This meant that sometimes they found the day's key within hours of
81 the new key's use, but it also meant that on some days they never
82 did find the right key.
83 The Bombes were not general-purpose computers but were precursors
84 to modern-day computers.
85 </para>
86
87 <para>
88 Today, computers can guess keys very quickly, and this is why key
89 size is important in modern cryptosystems.
90 The cipher DES uses a 56-bit key, which means that there are
91 <!-- inlineequation -->
92 2<superscript>56</superscript> possible keys.
93 <!-- inlineequation -->
94 2<superscript>56</superscript> is 72,057,594,037,927,936 keys.
95 This is a lot of keys, but a general-purpose computer can check the
96 entire key space in a matter of days.
97 A specialized computer can check it in hours.
98 On the other hand, more recently designed ciphers such as 3DES, 
99 Blowfish, and IDEA
100 <!-- inlineequation -->
101 all use 128-bit keys, which means there are 2<superscript>128</superscript> 
102 possible keys.
103 This is many, many more keys, and even if all the computers on the
104 planet cooperated, it could still take more time than the age of
105 the universe to find the key.
106 </para>
107 </sect1>
108
109 <sect1>
110 <title>
111 Public-key ciphers
112 </title>
113
114 <para>
115 The primary problem with symmetric ciphers is not their security but
116 with key exchange.
117 Once the sender and receiver have exchanged keys, that key can be
118 used to securely communicate, but what secure communication channel
119 was used to communicate the key itself?
120 In particular, it would probably be much easier for an attacker to work
121 to intercept the key than it is to try all the keys in the key space.
122 Another problem is the number of keys needed.
123 <!-- inlineequation -->
124 If there are <emphasis>n</emphasis> people who need to communicate, then 
125 <!-- inlineequation -->
126 <emphasis>n(n-1)/2</emphasis> keys
127 are needed for each pair of people to communicate privately.
128 This may be ok for a small number of people but quickly becomes unwieldly
129 for large groups of people.
130 </para>
131
132 <para>
133 Public-key ciphers were invented to avoid the key-exchange problem
134 entirely.
135 A public-key cipher uses a pair of keys for sending messages.
136 The two keys belong to the person receiving the message.
137 One key is a <emphasis>public key</emphasis> and may be given to anybody.
138 The other key is a <emphasis>private key</emphasis> and is kept 
139 secret by the owner.
140 A sender encrypts a message using the public key and once encrypted,
141 only the private key may be used to decrypt it.
142 </para>
143
144 <para>
145 This protocol solves the key-exchange problem inherent with symmetric
146 ciphers.
147 There is no need for the sender and receiver to agree
148 upon a key.
149 All that is required is that some time before secret communication the
150 sender gets a copy of the receiver's public key.
151 Furthermore, the one public key can be used by anybody wishing to
152 communicate with the receiver.
153 <!-- inlineequation -->
154 So only <emphasis>n</emphasis> keypairs are needed for <emphasis>n</emphasis> 
155 people to communicate secretly
156 with one another,
157 </para>
158
159 <para>
160 Public-key ciphers are based on one-way trapdoor functions.
161 A one-way function is a function that is easy to compute,
162 but the inverse is hard to compute.
163 For example, it is easy to multiply two prime numbers together to get
164 a composite, but it is difficult to factor a composite into its prime
165 components.a
166 A one-way trapdoor function is similar, but it has a trapdoor.
167 That is, if some piece of information is known, it becomes easy
168 to compute the inverse.
169 For example, if you have a number made of two prime factors, then knowing
170 one of the factors makes it easy to compute the second.
171 Given a public-key cipher based on prime factorization, the public
172 key contains a composite number made from two large prime factors, and
173 the encryption algorithm uses that composite to encrypt the
174 message.
175 The algorithm to decrypt the message requires knowing the prime factors,
176 so decryption is easy if you have the private key containing one of the
177 factors but extremely difficult if you do not have it.
178 </para>
179
180 <para>
181 As with good symmetric ciphers, with a good public-key cipher all of the
182 security rests with the key.
183 Therefore, key size is a measure of the system's security, but
184 one cannot compare the size of a symmetric cipher key and a public-key
185 cipher key as a measure of their relative security.
186 In a brute-force attack on a symmetric cipher with a key size of 80 bits,
187 <!-- inlineequation -->
188 the attacker must enumerate up to 2<superscript>81</superscript>-1 keys to 
189 find the right key.
190 In a brute-force attack on a public-key cipher with a key size of 512 bits,
191 the attacker must factor a composite number encoded in 512 bits (up to
192 155 decimal digits).
193 The workload for the attacker is fundamentally different depending on
194 the cipher he is attacking.
195 While 128 bits is sufficient for symmetric ciphers, given today's factoring
196 technology public keys with 1024 bits are recommended for most purposes.
197 </para>
198 </sect1>
199
200 <sect1>
201 <title>
202 Hybrid ciphers
203 </title>
204
205 <para>
206 Public-key ciphers are no panacea.
207 Many symmetric ciphers are stronger from a security standpoint,
208 and public-key encryption and decryption are more expensive than the
209 corresponding operations in symmetric systems.
210 Public-key ciphers are nevertheless an effective tool for distributing
211 symmetric cipher keys, and that is how they are used in hybrid cipher
212 systems.
213 </para>
214
215 <para>
216 A hybrid cipher uses both a symmetric cipher and a public-key cipher.
217 It works by using a public-key cipher to share a key for the symmetric
218 cipher.
219 The actual message being sent is then encrypted using the key and sent
220 to the recipient.
221 Since symmetric key sharing is secure, the symmetric key used is different
222 for each message sent.
223 Hence it is sometimes called a session key.
224 </para>
225
226 <para>
227 Both PGP and &gnupg; use hybrid ciphers.
228 The session key, encrypted using the public-key cipher, and the message
229 being sent, encrypted with the symmetric cipher, are automatically
230 combined in one package.
231 The recipient uses his private-key to decrypt the session key and the
232 session key is then used to decrypt the message.
233 </para>
234
235 <para>
236 A hybrid cipher is no stronger than the public-key cipher or symmetric
237 cipher it uses, whichever is weaker.
238 In PGP and &gnupg;, the public-key cipher is probably the weaker of
239 the pair.
240 Fortunately, however, if an attacker could decrypt a session key it
241 would only be useful for reading the one message encrypted with that
242 session key.
243 The attacker would have to start over and decrypt another session
244 key in order to read any other message.
245 </para>
246 </sect1>
247
248 <sect1>
249 <title>
250 Digital signatures
251 </title>
252
253 <para>
254 A hash function is a many-to-one function that maps its input to a
255 value in a finite set.
256 Typically this set is a range of natural numbers.
257 <!-- inlineequation -->
258 A simple ehash function is <emphasis>f</emphasis>(<emphasis>x</emphasis>) = 0 
259 for all integers <emphasis>x</emphasis>.
260 A more interesting hash function is 
261 <emphasis>f</emphasis>(<emphasis>x</emphasis>) = <emphasis>x</emphasis> 
262 <emphasis>mod</emphasis> 37, which
263 maps <emphasis>x</emphasis> to the remainder of dividing <emphasis>x</emphasis> by 37.
264 </para>
265
266 <para>
267 A document's digital signature is the result of applying a hash
268 function to the document.
269 To be useful, however, the hash function needs to satisfy two
270 important properties.
271 First, it should be hard to find two documents that hash to the
272 same value.
273 Second, given a hash value it should be hard to recover the document
274 that produced that value.
275 </para>
276
277 <para>
278 Some public-key ciphers<footnote><para>
279 The cipher must have the property that the actual public key or private
280 key could be used by the encryption algorithm as the public key.
281 RSA is an example of such an algorithm while ElGamal is not an example.
282 </para>
283 </footnote> could be used to sign documents.
284 The signer encrypts the document with his <emphasis>private</emphasis> key.
285 Anybody wishing to check the signature and see the document simply
286 uses the signer's public key to decrypt the document.
287 This algorithm does satisfy the two properties needed from a good hash
288 function, but in practice, this algorithm is too slow to be useful.
289 </para>
290
291 <para>
292 An alternative is to use hash functions designed to satisfy these
293 two important properties.
294 SHA and MD5 are examples of such algorithms.
295 Using such an algorithm, a document is signed by hashing it, and
296 the hash value is the signature.
297 Another person can check the signature by also hashing their copy of the
298 document and comparing the hash value they get with the hash value of
299 the original document.
300 If they match, it is almost certain that the documents are identical.
301 </para>
302
303 <para>
304 Of course, the problem now is using a hash function for digital
305 signatures without permitting an attacker to interfere with signature
306 checking.
307 If the document and signature are sent unencrypted, an attacker could
308 modify the document and generate a corresponding signature without the
309 recipient's knowledge.
310 If only the document is encrypted, an attacker could tamper with the
311 signature and cause a signature check to fail.
312 A third option is to use a hybrid public-key encryption to encrypt both
313 the signature and document.
314 The signer uses his private key, and anybody can use his public key
315 to check the signature and document.
316 This sounds good but is actually nonsense.
317 If this algorithm truly secured the document it would also
318 secure it from tampering and there would be no need for the signature.
319 The more serious problem, however, is that this does not protect either
320 the signature or document from tampering.
321 With this algorithm, only the session key for the symmetric cipher
322 is encrypted using the signer's private key.
323 Anybody can use the public key to recover the session key.
324 Therefore, it is straightforward for an attacker to recover the session
325 key and use it to encrypt substitute documents and signatures to send
326 to others in the sender's name.
327 </para>
328
329 <para>
330 An algorithm that does work is to use a public key algorithm to
331 encrypt only the signature.
332 In particular, the hash value is encrypted using the signer's private
333 key, and anbody can check the signature using the public key.
334 The signed document can be sent using any other encryption algorithm
335 including none if it is a public document.
336 If the document is modified the signature check will fail, but this
337 is precisely what the signature check is supposed to catch.
338 The Digital Signature Standard (DSA) is a public key signature 
339 algorithm that works as just described.
340 DSA is the primary signing algorithm used in &Gnupg;.
341 </para>
342
343 </sect1>
344 </chapter>
345