added unreleased README
[oweals/thc-archive.git] / Papers / ffp.html
1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
2         "http://www.w3.org/TR/html4/loose.dtd">
3 <html>
4 <meta name="GENERATOR" content="TtH 3.44">
5  <style type="text/css"> div.p { margin-top: 7pt;}</style>
6  <style type="text/css"><!--
7  td div.comp { margin-top: -0.6ex; margin-bottom: -1ex;}
8  td div.comb { margin-top: -0.6ex; margin-bottom: -.6ex;}
9  td div.hrcomp { line-height: 0.9; margin-top: -0.8ex; margin-bottom: -1ex;}
10  td div.norm {line-height:normal;}
11  span.roman {font-family: serif; font-style: normal; font-weight: normal;} 
12  span.overacc2 {position: relative;  left: .8em; top: -1.2ex;}
13  span.overacc1 {position: relative;  left: .6em; top: -1.2ex;} --></style>
14
15     
16    <title>
17        Fuzzy Fingerprints -
18        Attacking Vulnerabilities in the Human Brain
19    </title>
20    <body bgcolor="white">
21    <table width="640" align="center">
22    <tr><td> 
23    <br><br>
24
25
26 <title> 
27    Fuzzy Fingerprints\
28    Attacking Vulnerabilities in the Human Brain</title>
29     
30 <h1 align="center">
31    Fuzzy Fingerprints<br />
32    Attacking Vulnerabilities in the Human Brain </h1>
33
34 <h3 align="center">Plasmoid (plasmoid@thc.org) <br />
35         On behalf of The Hacker's Choice - <a href="http://www.thc.org">http://www.thc.org</a> </h3>
36
37    <p align="center">
38    This document is also available in the Portable Document Format
39    [PDF]: <a href="ffp.pdf">ffp.pdf</a>
40    </p> 
41 <br><br>
42
43 <div class="p"><!----></div>
44
45 <h1>Contents </h1><a href="#tth_sEc1"
46 >1&nbsp; Introduction</a><br />
47 <a href="#tth_sEc2"
48 >2&nbsp; Theoretical background</a><br />
49 &nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc2.1"
50 >2.1&nbsp; Key exchange using public-key cryptography</a><br />
51 &nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc2.2"
52 >2.2&nbsp; Cryptographic fingerprints for key verification</a><br />
53 &nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc2.3"
54 >2.3&nbsp; Fuzzy fingerprint quality</a><br />
55 &nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc2.4"
56 >2.4&nbsp; Finding fuzzy fingerprints</a><br />
57 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc2.4.1"
58 >2.4.1&nbsp; Tweaking RSA key generation</a><br />
59 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc2.4.2"
60 >2.4.2&nbsp; Tweaking DSA key generation</a><br />
61 <a href="#tth_sEc3"
62 >3&nbsp; Implementation details</a><br />
63 &nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc3.1"
64 >3.1&nbsp; Installation of <tt>ffp</tt></a><br />
65 &nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc3.2"
66 >3.2&nbsp; Usage of <tt>ffp</tt></a><br />
67 &nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc3.3"
68 >3.3&nbsp; Sample session using <tt>ffp</tt> and SSHarp</a><br />
69 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc3.3.1"
70 >3.3.1&nbsp; Investigating the victim host</a><br />
71 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc3.3.2"
72 >3.3.2&nbsp; Generating a key pair with a good fuzzy fingerprint</a><br />
73 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="#tth_sEc3.3.3"
74 >3.3.3&nbsp; Launching <tt>ssharp</tt> with the generated keys</a><br />
75 <a href="#tth_sEc4"
76 >4&nbsp; Thanks and greetings</a><br />
77
78   
79
80 <div class="p"><!----></div>
81    <h2><a name="tth_sEc1">
82 1</a>&nbsp;&nbsp;Introduction</h2>
83
84 <div class="p"><!----></div>
85 Welcome to the world of <em>Fuzzy Fingerprinting</em>, a new technique to
86 attack cryptographic key authentication protocols that rely on human
87 verification of key fingerprints. It is important to note that while fuzzy
88 fingerprinting is an attack against a protocol, it is <em>not</em> a
89 cryptographic attack and thus does not attack any cryptographic algorithm.
90
91 <div class="p"><!----></div>
92 This document covers the theoretical background and the generation of fuzzy
93 fingerprints and also details on the  implementation <tt>
94 ffp</tt> [<a href="#ffp" name="CITEffp">FFP</a>] and its usage. For people who don't want to waste their time
95 reading pseudo-academic Blabla it is essential to skip to the more pratical
96 part of this document <a href="#ri">3</a>, the details on the  implementation
97 and the provided sample session using SSHarp [<a href="#sfp" name="CITEsfp">SFP</a>].
98
99 <div class="p"><!----></div>
100  <h2><a name="tth_sEc2">
101 2</a>&nbsp;&nbsp;Theoretical background</h2>
102
103 <div class="p"><!----></div>
104      <h3><a name="tth_sEc2.1">
105 2.1</a>&nbsp;&nbsp;Key exchange using public-key cryptography</h3>
106
107 <div class="p"><!----></div>
108 Asymmetric cryptography has revolutionized the classic cryptography and
109 created new cryptographic techniques such as hybrid cryptosystems or digital
110 signatures. In order to cover the background of fuzzy fingerprinting, this
111 document focuses on the hybrid cryptosystems and their key exchange
112 protocols. Fuzzy fingerprinting may also have an impact on digital
113 signatures or integrity verification systems, for now we simply ignore these
114 aspects.
115
116 <div class="p"><!----></div>
117 Let's introduce the classical problem of communicating using a symmetric
118 cypher. Two parties that want to encrypt a communication using a fast
119 symmetric cipher need to exchange a secret session key before starting to
120 communicate. This problem is not easy to solve, meeting in real life or
121 exchanging the session key via telephone are solutions, but often 
122 impossible to realize.
123
124 <div class="p"><!----></div>
125 Using public-key cryptography both parties can elegantly and securely
126 exchange the session key: Both parties first exchange their public keys,
127 then one chooses a session key and transmits it to the other encrypting it
128 with its public key. Both continue communicating using the session key. An
129 outside attacker is not able to able to read the secret session key if he
130 just passively eavesdrops the communication of both.
131
132 <div class="p"><!----></div>
133 While public-key cryptography looks like a really good solution to the
134 problem, it introduces a new problem into the scenario. An active attacker
135 might intercept the communication between both parties and replaces the
136 transmitted public keys with his own public key. Both parties would exchange
137 keys, but in fact each would receive the public key of the attacker. Any
138 communication first goes to the attacker who decrypts the messages using his
139 private key and then re-encrypts them using the target's public key.  He's
140 now able to read the session key in cleartext and can also read the
141 following secure communication that uses this session key. This attack is
142 known as <em>man-in-the-middle attack</em>.
143
144 <div class="p"><!----></div>
145      <h3><a name="tth_sEc2.2">
146 2.2</a>&nbsp;&nbsp;Cryptographic fingerprints for key verification</h3>
147
148 <div class="p"><!----></div>
149 Several protocols have been proposed to prevent man-in-the-middle attacks
150 when using public-key cryptography, e.g. the interlock protocol [<a href="#ilp" name="CITEilp">ILP</a>].
151 Other protocols rely on digital signatures or trusted key distribution
152 centers to verify the integrity of the public keys. Unfortunately in most
153 situation such methods are not available and the initially exchanged public
154 keys are verificated using so called <em>cryptographic fingerprints</em>.
155
156 <div class="p"><!----></div>
157 Cryptographic fingerprints (also called messages digests) are short blocks
158 generated by cryptographic one-way hash functions (also called
159 collision-free hash functions). These cryptographic fingerprints act similar
160 to real fingerprints, if two fingerprints match it is <em>very</em> likely that
161 they have been made by the same person. In order to verify the integrity of
162 a public key the sender and receiver both generate a cryptographic
163 fingerprint from the key and compare these fingerprints, e.g. by phone.
164
165 <div class="p"><!----></div>
166 The longer a fingerprint is, the better is its security against collisions
167 but the harder it is for a common human subject to compare the fingerprint
168 against another fingerprint. It has been observed that most people tend to
169 compare only a sequence at the start and at the end of the fingerprint
170 instead of checking every single digit. Some more sophisticated human
171 subjects also compare a sequence in the middle - but only very few have been
172 spotted that compare all digits. This observation led to the idea of 
173 fuzzy fingerprints.
174
175 <div class="p"><!----></div>
176      <h3><a name="tth_sEc2.3">
177 2.3</a>&nbsp;&nbsp;Fuzzy fingerprint quality</h3>
178
179 <div class="p"><!----></div>
180 The intention of fuzzy fingerprinting is no to collide against a target
181 fingerprint, but to find a fuzzy fingerprint that would pass lazy human
182 comparison. This attack has been proposed by Plasmoid and Skyper in 
183 a private discussion at HAL2001.
184
185 <div class="p"><!----></div>
186 There are some methods for the generation of fuzzy fingerprints. The most
187 basic is the <em>fuzzy map weighting</em> that was introduced by Plasmoid.
188
189 <div class="p"><!----></div>
190 Each digit of a cryptographic fingerprint is weighted according to a map of
191 importance. The weights range from 0 to 1 and represent the importance for a
192 comparison, so that first and last digits have a higher importance than
193 middle ones. If a digit of the fuzzy fingerprint and the target
194 fingerprint match the weight is added to the quality of the fuzzy
195 fingerprint. The sum of the weighted digits is the quality of the fuzzy
196 fingerprint and equal fingerprints have a quality of 1 or 100
197 <div class="p"><!----></div>
198 In order to imitate the natural laziness an inverse gaussian distribution
199 could be used to generate the fuzzy map. The following example shows an
200 inverse gaussian distribution for a small 2 byte fingerprint.
201
202 <div class="p"><!----></div>
203
204 <table>
205 <tr><td align="right">Target Fingerprint </td><td align="center">= </td><td align="center">9   </td><td align="center">F   </td><td align="center">:</td><td align="center">2   </td><td align="center">3  </td></tr>
206 <tr><td align="right">Fuzzy Map </td><td align="center">= </td><td align="center">25% </td><td align="center">10% </td><td align="center">:</td><td align="center">5% </td><td align="center">20% </td></tr>
207 <tr><td align="right"></td></tr>
208 <tr><td align="right">Fuzzy Fingerprint </td><td align="center">= </td><td align="center">9   </td><td align="center">3   </td><td align="center">:</td><td align="center">1   </td><td align="center">3  </td><td align="center"></td></tr>
209 <tr><td align="right">Quality </td><td align="center">= </td><td align="center">25% </td><td align="center">+ 10% </td><td align="center"></td><td align="center">+ 5% </td><td align="center">+ 20% </td><td align="center">= 45%  </td></tr></table>
210
211
212 <div class="p"><!----></div>
213 Eventhough only 2 digits of 6 are equal the calculated quality is near 50because the important digits at the start and at the end do match. At the
214 first glance a gaussian distribution might be an overkill for such a simple
215 map, but it allows the generation of variable-length maps that can be
216 generated for several one-way hash functions, e.g. MD5 [<a href="#md5" name="CITEmd5">MD5</a>] with 16
217 bytes fingerprints or SHA1 [<a href="#dss" name="CITEdss">DSS</a>] with 20 bytes fingerpints. 
218
219 <div class="p"><!----></div>
220 Instead of the gaussian distribution a cosine function might be used with 3
221 maxima. This can be achieved if the map is generated within the interval 
222 from <font face="symbol">-</font
223 >2<font face="symbol">p</font
224 > to 2<font face="symbol">p</font
225 >. Important parts of the fingerprint therefore
226 become the start, the end <em>and</em> the middle sequence.
227
228 <div class="p"><!----></div>
229 An extension for finding fuzzy fingerprints has been proposed by Heinrich
230 Langos eventhough he probably can't remember that. In addition to the fuzzy
231 map, a map of common key confusions is added to the quality calculation.
232 Digits like 6 and 9 or 1 and 7 are often mixed up depending on the format of
233 the digits, e.g. down written or graphic fonts. A <em>confusion key map</em>
234 contains the confusion and a quality representing the probability of the
235 confusion. The following example shows just a few confusions.
236
237 <div class="p"><!----></div>
238
239 <table>
240 <tr><td align="center">Target Key  </td><td align="center"></td><td align="center">Fuzzy Key  </td><td align="center">Quality </td></tr>
241 <tr><td align="center">6   </td><td align="center"><font face="symbol">®</font
242 > </td><td align="center">9     </td><td align="center">12%  </td></tr>
243 <tr><td align="center">9   </td><td align="center"><font face="symbol">®</font
244 > </td><td align="center">6     </td><td align="center">12%  </td></tr>
245 <tr><td align="center">1   </td><td align="center"><font face="symbol">®</font
246 > </td><td align="center">7     </td><td align="center">8%  </td></tr>
247 <tr><td align="center">7   </td><td align="center"><font face="symbol">®</font
248 > </td><td align="center">1     </td><td align="center">4%  </td></tr></table>
249
250
251 <div class="p"><!----></div>
252 A confusion map adds more granularity to the quality function of fuzzy maps,
253 fuzzy fingerprints generated with confusions maps not only contain similar
254 start and end-sequences in comparison to the target fingerprint, but also
255 feature digits that might easily be confused with digits from the target
256 fingerprint.
257
258 <div class="p"><!----></div>
259 It is important to note that such a key mapping is not necessary symmetric
260 and also that such a confusion key map has not been implemented in this
261 release but may be added later.
262
263 <div class="p"><!----></div>
264      <h3><a name="tth_sEc2.4">
265 2.4</a>&nbsp;&nbsp;Finding fuzzy fingerprints</h3>
266
267 <div class="p"><!----></div>
268 With the fuzzy quality as an instrument to order fuzzy fingerprints, an
269 attacker is able to search for fingerprints with the best fuzzy quality.
270 This search involves two major calculation components, the one-way hash
271 function and the key generation, because the attacker has to bruteforce for
272 keys that have a good fuzzy fingerprint generated using a hash function.
273
274 <div class="p"><!----></div>
275 Cryptographic one-way hash functions are collision-resistant (or try to be),
276 therefore changing just one bit of the input data should result in a
277 complete different fingerprint (50issues into account, it should be very hard to predict the output of a hash
278 function so that there would be any other way than bruteforcing to receive
279 good fuzzy fingerprints. Any performance optimisations need to be done 
280 in the key generation component. 
281
282 <div class="p"><!----></div>
283 For this document the RSA [<a href="#rsa" name="CITErsa">RSA</a>] and the DSA [<a href="#dss" name="CITEdss">DSS</a>] key generation
284 have been reviewed. The intention was to improve the performance of the key
285 generation under the new aspect that the resulting keys not necessary have
286 to be cryptographic secure but still need to work.
287
288 <div class="p"><!----></div>
289       <h4><a name="tth_sEc2.4.1">
290 2.4.1</a>&nbsp;&nbsp;Tweaking RSA key generation</h4>
291
292 <div class="p"><!----></div>
293 The RSA algorithm uses the following interesting variables
294
295 <ul>
296 <li> p, q and n = pq, two strong prime numbers<br /><br /></li>
297
298 <li> <font face="symbol">f</font
299 >(n)=(p<font face="symbol">-</font
300 >1)(q<font face="symbol">-</font
301 >1)<br /><br /></li>
302
303 <li> e with gcd(e,<font face="symbol">f</font
304 >(n))=1, the public key<br /><br /></li>
305 </ul>
306
307
308 <div class="p"><!----></div>
309 There are two possible approaches to the generation of an RSA key pair 
310
311 <div class="p"><!----></div>
312
313 <ul>
314 <li> The first step is to randomly choose the public key e and continue to
315 search for two prime numbers p and q so that p and q meet
316 gcd(e,<font face="symbol">f</font
317 >(n))=1 or in other words e and <font face="symbol">f</font
318 >(n) are relative prime.
319 This approach has been implemented by the OpenSSL Project [<a href="#ssl" name="CITEssl">SSL</a>].<br /><br /></li>
320
321 <li> The other approach is to first calculate the two prime numbers p and
322 q and then search for an e so that e meets gcd(e,<font face="symbol">f</font
323 >(n))=1. This 
324 approach is integrated in the <tt>ffp</tt> implementation [<a href="#ffp" name="CITEffp">FFP</a>].<br /><br /></li>
325 </ul>
326
327
328 <div class="p"><!----></div>
329 While both approaches create the same result the second one better fits into
330 the needs of bruteforcing, because the expensive prime number generations
331 are only performed once. An attacker could calculate the two primes p
332 and q at the start of the bruteforce process and then search successivly
333 for public keys e.
334
335 <div class="p"><!----></div>
336 In order to improve the performance even the check for e being relative
337 prime can be skipped, this is called <em>sloppy</em> key generation. While this
338 step dramatically increases the performance, it is not guaranteed that the 
339 generated keys still work. Test allow the assumption that only very few 
340 keys are broken and if an attacker stores a list of best keys, e.g. 10 there
341 is more than a fair chance that more than one key is working.
342
343 <div class="p"><!----></div>
344       <h4><a name="tth_sEc2.4.2">
345 2.4.2</a>&nbsp;&nbsp;Tweaking DSA key generation</h4> 
346
347 <div class="p"><!----></div>
348 The algorithm uses the following interesting variables
349
350 <ul>
351 <li> p, a prime number of variable length<br /><br /></li>
352
353 <li> q, a 160-bit prime factor of p<font face="symbol">-</font
354 >1<br /><br /></li>
355
356 <li> x with x  &lt;  q, the private key<br /><br /></li>
357
358 <li> g, something different [Do we need to discuss any detail?]<br /><br /></li>
359
360 <li> y = g<sup>x</sup> mod p, the public key<br /><br /></li>
361 </ul>
362
363
364 <div class="p"><!----></div>
365 <a name="slow-dsa">
366 </a>Increasing the performance of the DSA key generation is a diffcult problem. 
367 At the first step one would start the key generation process similar to 
368 the improvements done to the sloppy RSA key generation by first 
369 calculating the two prime numbers p and q. Note that p and q in
370 case of DSA old more constraints than in the RSA algorithm.
371
372 <div class="p"><!----></div>
373 After two primes have been found, it is possible to bruteforce over the
374 private key x that only needs to meed x  &lt;  q which is a simple and fast
375 comparison. Unfortunatley it is necessary for each x to calculate the
376 appropriate public key y which involves calculating a modulus and an
377 exponentiation with very big numbers and thus is very time consuming.
378
379 <div class="p"><!----></div>
380 Tests with the <tt>ffp</tt> implementation show that DSA is about 1000 times
381 slower than RSA key generation and therefore will only be available to the
382 bruteforce process for fuzzy fingerprinting in the next centuries.
383
384 <div class="p"><!----></div>
385  <h2><a name="tth_sEc3">
386 3</a>&nbsp;&nbsp;Implementation details</h2>
387 <a name="ri">
388 </a>
389
390 <div class="p"><!----></div>
391 Now you have read through a rather strange description of the background and
392 honestly I know that some points have been discussed far from complete,
393 nevertheless I also like to present an implementation of the discussed ideas
394 that is callesd <tt>ffp</tt> and available at The Hacker's Choice website. This
395 implementation uses the fuzzy fingerprinting technique in order to attack
396 the key verification protocol used in the client of SSH protocol version 2.
397 As a good victim the implementation OpenSSH [<a href="#ssh" name="CITEssh">SSH</a>] has been chosen,
398 because it is free and really good software that can mess with all
399 commercial implementations (Humble me says so!). 
400
401 <div class="p"><!----></div>
402 OpenSSH makes use of the routines from the free crypto and SSL 
403 libraries provided by the OpenSSL Project [<a href="#ssl" name="CITEssl">SSL</a>]. Therefore several
404 implementation issues have been looked up in the OpenSSL source code 
405 and some parts have even been taken from the actual implementations of 
406 the RSA and DSA key generation.
407
408 <div class="p"><!----></div>
409 OpenSSH uses a hybrid cryptosystem: public-key cryptography is used to
410 exchange a session key between the client and the server and the following
411 client-server-communication is encrypted with a symmetric cipher, but
412 OpenSSH, strictly implementing the SSH protocol, fully relies on the user
413 verificating of an initially received public key by asking for confirmation
414 if the generated cryptographic fingerprint is known and matches.
415
416 <div class="p"><!----></div>
417                                          
418 <pre>
419 $ ssh foo@fluffy
420 The authenticity of host 'fluffy (10.0.0.2)' can't be established.
421 RSA key fingerprint is 54:3a:12:db:d4:35:71:45:3d:61:51:c1:df:47:bc:bc.
422 Are you sure you want to continue connecting (yes/no)? 
423 </pre>
424
425      
426 <br clear="all" /><table border="0" width="100%"><tr><td>
427 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
428 </td></tr></table>
429 </td></tr></table>
430
431
432
433 <div class="p"><!----></div>
434 Once the fingerprint and the key have been approved the key is stored in a
435 file called <tt>known_hosts</tt> or <tt>known_hosts2</tt> and upon further
436 connections the retrieved public key is compared to the stored key an no
437 user interaction is necessary. It has also been shown that there exists
438 tricks to force the SSH client to ask again for the confirmation of a key
439 eventhough a correct version has already been retrieved [<a href="#sfp" name="CITEsfp">SFP</a>]. Using
440 these techniques, a man-in-the-middle tool and <tt>ffp</tt> form a quite
441 mailicous attack that can be launched against any SSH connection using the
442 SSH protocol version 2.
443
444 <div class="p"><!----></div>
445 Therefore <tt>ffp</tt> acts an extension to common man-in-the-middle tools such
446 as dsniff [<a href="#ds" name="CITEds">DS</a>] or ettercap [<a href="#ec" name="CITEec">EC</a>]. If the attacker sends a public
447 key to the victim that has a fuzzy fingerprint that nearly looks like the
448 target fingerprint, the victim might easier be fooled to accept the public
449 key and continue the eavesdropped connection. Because all those theory is 
450 gray, we are quickly installing our implementation and then start to 
451 actively generate a fuzzy fingerprint to be used with Sebastian Krahmer's
452 tool SSHarp.
453
454 <div class="p"><!----></div>
455      <h3><a name="tth_sEc3.1">
456 3.1</a>&nbsp;&nbsp;Installation of <tt>ffp</tt></h3>
457
458 <div class="p"><!----></div>
459 In order to install this release, you need a Unix environment or at
460 least something very similar such as Cygwin or QNX. You will also need
461 a mathematical library which is present in most Unix system and the
462 OpenSSL libraries available at <tt>http://www.openssl.org</tt>.
463
464 <div class="p"><!----></div>
465 If everything is place, follow the boring GNU autoconf/automake installation
466 process:
467
468 <div class="p"><!----></div>
469                                          
470 <pre>
471 $ ./configure
472 $ make
473 $ su -c "make install"
474 </pre>
475
476      
477 <br clear="all" /><table border="0" width="100%"><tr><td>
478 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
479 </td></tr></table>
480 </td></tr></table>
481
482
483
484 <div class="p"><!----></div>
485 If you want to you can use the <tt>-prefix</tt> option to install this
486 software to a specific direction. The default location is <tt>/usr/local</tt>.
487 If you need to you can use the <tt>-with-ssl-dir</tt> option to specify the
488 directory of your OpenSSL installation.
489
490 <div class="p"><!----></div>
491 If during the compilation or installation process errors occur ask yourself
492 at first, if you have done anything wrong, wait for a time, say 2 minutes,
493 and ask yourself again if you have been honest to yourself. If it turns out
494 that there is really something wrong with the code of <tt>ffp</tt> drop a mail
495 to Plasmoid <tt>plasmoid@thc.org</tt> and describe your problems. Please
496 understand that you are on your own if you try to fiddle with any Windows
497 release and Cygwin.
498
499 <div class="p"><!----></div>
500      <h3><a name="tth_sEc3.2">
501 3.2</a>&nbsp;&nbsp;Usage of <tt>ffp</tt></h3>
502
503 <div class="p"><!----></div>
504 The current release of Fuzzy Fingerprint is a command line tool called <tt>
505 ffp</tt> that has the following command line option
506
507 <div class="p"><!----></div>
508                                          
509 <pre>
510 Usage: ffp [Options]
511 Options:
512   -f type       Specify type of fingerprint to use [Default: md5]
513                 Available: md5, sha1, ripemd
514   -t hash       Target fingerprint in byte blocks. 
515                 Colon-separated: 01:23:45:67... or as string 01234567...
516   -k type       Specify type of key to calculate [Default: rsa]
517                 Available: rsa, dsa
518   -b bits       Number of bits in the keys to calculate [Default: 1024]
519   -K mode       Specify key calulation mode [Default: sloppy]
520                 Available: sloppy, accurate
521   -m type       Specify type of fuzzy map to use [Default: gauss]
522                 Available: gauss, cosine
523   -v variation  Variation to use for fuzzy map generation [Default: 4.3]
524   -y mean       Mean value to use for fuzzy map generation [Default: 0.08]
525   -l size       Size of list that contains best fingerprints [Default: 10]
526   -s filename   Filename of the state file [Default: /var/tmp/ffp.state]
527   -e            Extract SSH host key pairs from state file
528   -d directory  Directory to store generated ssh keys to [Default: /tmp]
529   -p period     Period to save state file and display state [Default: 60]
530   -V            Display version information
531 </pre>
532
533      
534 <br clear="all" /><table border="0" width="100%"><tr><td>
535 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
536 </td></tr></table>
537 </td></tr></table>
538
539
540
541 <div class="p"><!----></div>
542 If you have read the theoretical background covered in this paper you should
543 already have an idea how some of these options work and which parameters
544 they influence. Due to the fact that <tt>ffp</tt> is not a kernel module, you
545 run through the classical try and error phase and find the rest out
546 yourself. Instead of discussing each detail of the implementation, this
547 document demonstrates a sample session of <tt>ffp</tt> and SSHarp.
548
549 <div class="p"><!----></div>
550      <h3><a name="tth_sEc3.3">
551 3.3</a>&nbsp;&nbsp;Sample session using <tt>ffp</tt> and SSHarp</h3>
552
553 <div class="p"><!----></div>
554 This part of the documentation demonstrates how to use <tt>ffp</tt> in
555 conjunction with a man-in-the-middle tool and describes a sample session
556 that finally demonstrates the transmission and display of a fuzzy
557 fingerprint. Other nasty techniques, such as ARP spoofing, that are
558 necessary for the successful interception and manipulation of SSH
559 connections, have been wisely left out because the author doesn't have any
560 idea how these things actually work, but hopes to know some bad guys who do.
561
562 <div class="p"><!----></div>
563       <h4><a name="tth_sEc3.3.1">
564 3.3.1</a>&nbsp;&nbsp;Investigating the victim host</h4>
565
566 <div class="p"><!----></div>
567 The first step could be to investigate the victim SSH server in order to
568 find out which version of SSH is used and which public key algorithms are
569 available. The OpenSSH package [<a href="#ssh" name="CITEssh">SSH</a>] provides all tools we need for
570 gathering information from a remote SSH server. Our victim will be the
571 server <tt>skena.foo.roqe.org</tt> which luckily is not available outside the
572 sample network.
573
574 <div class="p"><!----></div>
575                                          
576 <pre>
577 foo@fluffy:doc&#62; ssh-keyscan -t rsa skena.foo.roqe.org &#62; /tmp/skena-sshd 
578 # skena.foo.roqe.org SSH-1.99-OpenSSH_3.4
579 foo@fluffy:doc&#62; cat /tmp/skena-sshd 
580 skena.foo.roqe.org ssh-rsa
581 AAAAB3NzaC1yc2EAAAABIwAAAIEAtE/CTgGl2HSUZUiCiSqhJafup [...]
582 </pre>
583
584      
585 <br clear="all" /><table border="0" width="100%"><tr><td>
586 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
587 </td></tr></table>
588 </td></tr></table>
589
590
591
592 <div class="p"><!----></div>
593 It turns out that <tt>skena.foo.roqe.org</tt> is using an OpenSSH v3.4 server
594 able to run the SSH v2 protocol and also has an RSA public host key 
595 available. This is good news for us, because <tt>ffp</tt> only support SSH v2
596 keys and RSA key generation is faster than DSA <a href="#slow-dsa">2.4.2</a>. The SSH 
597 server version is important to play banner tricks on the server as they 
598 have been covered in Sebastian's paper. 
599
600 <div class="p"><!----></div>
601 Now let's take a closer look at the bits used in the RSA algorithm and 
602 of course at the MD5 fingerprint of the host key we retrieved from 
603 <tt>skena.foo.roqe.org</tt>.
604
605 <div class="p"><!----></div>
606                                          
607 <pre>
608 foo@fluffy:doc&#62; ssh-keygen -f /tmp/skena-sshd -l
609 1024 d6:b7:df:31:aa:55:d2:56:9b:32:71:61:24:08:44:87 skena.foo.roqe.org
610 </pre>
611
612      
613 <br clear="all" /><table border="0" width="100%"><tr><td>
614 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
615 </td></tr></table>
616 </td></tr></table>
617
618
619
620 <div class="p"><!----></div>
621 Again excellent news, good old <tt>skena.foo.roqe.org</tt> is only using a 1024
622 bit RSA key and we also note the cryptographic fingerprint <tt>
623 d6:b7:df:31:aa:55:d2:56:9b:32:71:61:24:08:44:87</tt>. So using a 2048 or even
624 4096 host key is not only a good necessary protection against cryptographic
625 attacks but also a protection against cheap attacks such as fuzzy
626 fingerprinting.
627
628 <div class="p"><!----></div>
629       <h4><a name="tth_sEc3.3.2">
630 3.3.2</a>&nbsp;&nbsp;Generating a key pair with a good fuzzy fingerprint</h4>
631
632 <div class="p"><!----></div>
633 The next step is to generate a public key and a private key for an OpenSSH
634 server so that the public key has a fuzzy fingerprint that nearly matches 
635 the target fingerprint. In order to do so we launch <tt>ffp</tt> with the 
636 appropriate options. <tt>ffp</tt> will output a lot of information and then 
637 start to crunch. This process can take several days, the longer you wait
638 the better the fuzzy fingerprint can get. Please note that the process is
639 not linear at all or in any way predictable, therefore you'll need a lot of
640 time or a lot of luck, best is both.
641
642 <div class="p"><!----></div>
643                                          
644 <pre>
645 foo@fluffy:doc&#62;./ffp -f md5 -k rsa -b 1024 \ 
646                      -t d6:b7:df:31:aa:55:d2:56:9b:32:71:61:24:08:44:87
647 </pre>
648
649      
650 <br clear="all" /><table border="0" width="100%"><tr><td>
651 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
652 </td></tr></table>
653 </td></tr></table>
654
655
656
657 <div class="p"><!----></div>
658 Periodically <tt>ffp</tt> will send some status information to the screen and
659 also show the best fuzzy fingerprint that was generated so far. Internally
660 <tt>ffp</tt> keeps a list of best fuzzy fingerprints, so that you are later
661 able to choose the best yourself. The output of <tt>ffp</tt> during the 
662 crunching process looks like this:
663
664 <div class="p"><!----></div>
665                                          
666 <pre>
667 ---[Current State]--------------------------------------------------------
668  Running:   0d 00h 02m 00s | Total:   2216k hashs | Speed:  18469 hashs/s
669 --------------------------------------------------------------------------
670  Best Fuzzy Fingerprint from State File /var/tmp/ffp.state
671     Hash Algorithm: Message Digest 5 (MD5)
672        Digest Size: 16 Bytes / 128 Bits
673     Message Digest: d1:bc:df:32:a2:45:2e:e0:96:d6:a1:7c:f5:b8:70:8f
674      Target Digest: d6:b7:df:31:aa:55:d2:56:9b:32:71:61:24:08:44:87
675      Fuzzy Quality: 47.570274%
676 </pre>
677
678      
679 <br clear="all" /><table border="0" width="100%"><tr><td>
680 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
681 </td></tr></table>
682 </td></tr></table>
683
684
685
686 <div class="p"><!----></div>
687 The program displays the time it is running the number of hashs it has 
688 been tested in "kilohashs" and the speed. An 1.2 GHz PC has a fair 
689 speed of 130000 hashs per second, where my poor UltraSparc machine only
690 calculates 20000 hashs per second.
691
692 <div class="p"><!----></div>
693 You can interrupt a running session, by pressing the keys <tt>CTRL-C</tt>, <tt>
694 ffp</tt> will abort and store the current environment in a so called state file
695 that is usually stored in <tt>/var/tmp/ffp.state</tt>. Issuing again simple
696 command <tt>ffp</tt> without any options continues the crunching process from
697 the saved state file.
698
699 <div class="p"><!----></div>
700 Please note that while writing this documentation, the author did not find
701 the time to search for a good fuzzy fingerprint and therefore used a
702 fingerprint that was achieved after only a few minutes of intensive
703 crunching on an Ultra 10. Extraction of the fingerprints is done using the
704 following command.
705
706 <div class="p"><!----></div>
707                                          
708 <pre>
709 foo@fluffy:src&#62; ./ffp -e -d /tmp    
710 ---[Restoring]------------------------------------------------------------
711 Reading FFP State File: Done
712     Restoring environment: Done
713  Initializing Crunch Hash: Done
714 --------------------------------------------------------------------------
715 Saving SSH host key pairs: [00] [01] [02] [03] [04] [05] [06] [07]
716 </pre>
717
718      
719 <br clear="all" /><table border="0" width="100%"><tr><td>
720 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
721 </td></tr></table>
722 </td></tr></table>
723
724
725
726 <div class="p"><!----></div>
727 The generated public and private SSH host keys in the <tt>/tmp</tt> directory
728 can be investigated using the following command. The attacker should use 
729 the key that looks best in a human sense. Eventhough fuzzy map weighting is
730 a nice measure for the quality of fuzzy fingerprints the human eye may
731 best choose which fingerprint has the greatest chance to be confused with
732 the original target fingerprint. 
733
734 <div class="p"><!----></div>
735                                          
736 <pre>
737 foo@fluffy:doc&#62; for i in /tmp/ssh-rsa??.pub ; do ssh-keygen -f $i -l ; done
738 1024 d6:b7:8f:a6:fa:21:0c:0d:7d:0a:fb:9d:30:90:4a:87 /tmp/ssh-rsa00.pub
739 1024 d6:b5:d0:34:aa:03:ca:9b:7f:66:b4:79:0a:86:74:a7 /tmp/ssh-rsa01.pub
740 1024 d6:87:6f:71:9d:2c:5d:fb:57:54:03:a2:2d:09:51:87 /tmp/ssh-rsa02.pub
741 1024 d6:b2:3f:ac:13:ce:ca:59:3f:b1:4b:c2:f0:03:44:97 /tmp/ssh-rsa03.pub
742 1024 d6:b9:0f:31:85:b3:34:1e:19:f5:d9:60:79:be:f4:85 /tmp/ssh-rsa04.pub
743 1024 96:57:df:31:8d:11:f2:b1:28:a4:fd:6d:34:5f:b2:87 /tmp/ssh-rsa05.pub
744 1024 d0:b0:df:0e:7c:f6:54:94:46:12:72:94:3a:07:a4:87 /tmp/ssh-rsa06.pub
745 1024 d6:b7:dd:be:f3:52:d9:8f:7e:53:30:49:f1:a8:94:5a /tmp/ssh-rsa07.pub
746 </pre>
747
748      
749 <br clear="all" /><table border="0" width="100%"><tr><td>
750 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
751 </td></tr></table>
752 </td></tr></table>
753
754
755
756 <div class="p"><!----></div>
757 In this sample session the private key <tt>/tmp/ssh-rsa00</tt> and the public
758 key <tt>/tmp/ssh-rsa00.pub</tt> have been chosen for the attack against the
759 host <tt>skena.foo.roqe.org</tt>. But also note that only after a few minutes
760 of crunching there are already several fingerprints that contain a good
761 start and end sequence and two fingerprints that share the correct first two
762 bytes.
763
764 <div class="p"><!----></div>
765       <h4><a name="tth_sEc3.3.3">
766 3.3.3</a>&nbsp;&nbsp;Launching <tt>ssharp</tt> with the generated keys</h4>
767
768 <div class="p"><!----></div>
769 The special thing about the SSHarp implementation is the fact that this
770 tool is build upon the OpenSSH server and therefore the configuration is 
771 very similar to the OpenSSH server configuration. We are now going to start
772 a simple man-in-the-middle session. We launch the <tt>ssharpd</tt> server
773 on the host <tt>fluffy.foo.roqe.org</tt> on port 10000. 
774
775 <div class="p"><!----></div>
776                                          
777 <pre>
778 foo@fluffy:ssharp&#62; ./ssharpd -f /etc/ssh/sshd_config -d \
779                              -h /tmp/ssh-rsa00 -4 -p 10000
780
781 Dude, Stealth speaking here. This is 7350ssharp, a smart
782 SSH1 &amp; SSH2 MiM attack implementation. It's for demonstration
783 and educational purposes ONLY! Think before you type ... (&lt;ENTER&#62; or
784 &lt;Ctrl-C&#62;)
785
786 debug1: Seeding random number generator
787 debug1: sshd version OpenSSH_2.9p1
788 debug1: read PEM private key done: type RSA
789 debug1: private host key: #0 type 1 RSA
790 Disabling protocol version 1. Could not load host key
791 debug1: Bind to port 10000 on 0.0.0.0.
792 Server listening on 0.0.0.0 port 10000.
793
794 </pre>
795
796      
797 <br clear="all" /><table border="0" width="100%"><tr><td>
798 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
799 </td></tr></table>
800 </td></tr></table>
801
802
803
804 <div class="p"><!----></div>
805 While this example looks very simple it might be necessary to study the
806 details of the SSHarp implementation by reading the file <tt>README.sharp</tt>
807 in order to setup a working environment. It has already been noted in the
808 beginning that this session doesn't demonstrate all necessary steps to setup
809 a man-in-the-middle attack and only focuses on the parts that are relevant
810 to see <tt>ffp</tt> in active process.
811
812 <div class="p"><!----></div>
813 We can now connect to our host <tt>fluffy.foo.roqe.org</tt> at port 10000
814 and see our faked public key and its fuzzy fingerprint in action using
815 the normal SSH client
816
817 <div class="p"><!----></div>
818                                          
819 <pre>
820 foo@fluffy:ssharp&#62; ssharp -l foo fluffy.foo.roqe.org -2 -p 10000
821 The authenticity of host '10.0.0.2 (10.0.0.2)' can't be established.
822 RSA key fingerprint is d6:b7:8f:a6:fa:21:0c:0d:7d:0a:fb:9d:30:90:4a:87.
823 Are you sure you want to continue connecting (yes/no)?
824 </pre>
825
826      
827 <br clear="all" /><table border="0" width="100%"><tr><td>
828 <table align="center" cellspacing="0"  cellpadding="2"><tr><td nowrap="nowrap" align="center">
829 </td></tr></table>
830 </td></tr></table>
831
832
833
834 <div class="p"><!----></div>
835 What we are seeing is in fact our fuzzy fingerprint and our client is 
836 asking for confirmation. If the user has got a headache, trouble with
837 his/ger girl/boyfriend or is not that concentrated, pressing <em>yes</em> at 
838 this situation might allow an attacker to eavesdrop <em>all</em> following
839 communications with the host <tt>skena.foo.roqe.org</tt>.
840
841 <div class="p"><!----></div>
842 In order to complete your man-in-the-middle setup, you need to redirect
843 the traffic to <tt>skena.foo.roqe.org</tt> to our fake server at 
844 <tt>fluffy.foo.roqe.org</tt>, e.g. by using ARP spoofing. You also need to
845 use port forwarding on <tt>fluffy</tt> to redirect port 10000 to 22, so 
846 that normal SSH connection will be accepted. That's it. 
847
848 <div class="p"><!----></div>
849  <h2><a name="tth_sEc4">
850 4</a>&nbsp;&nbsp;Thanks and greetings</h2>
851
852
853 <div class="p"><!----></div>
854 2
855
856 <ul>
857 <li> Skyper <br />
858          Who invented the idea with me and is still working on a
859          different approach to very fast RSA key generation.<br /><br /></li>
860
861 <li> Wilkins and Arrow <br />
862          For the classical old-fashioned booze-ups and the 
863          obligatoric action.<br /><br /></li>
864
865 <li> Hannes and Heinrich <br />
866          Who really believe this is serious, academic
867          work and code. Indeed, it is!<br /><br /></li>
868
869 <li> TTEHSCO Fusion <br />
870          This is the first unofficial release for TTEHSCO. Cheers
871          to all fellows and rockers at The Hacker's Choice and 
872          Team TESO.<br /><br /></li>
873
874 <li> All that jazz around <br /><br /><br /></li>
875 </ul>
876
877
878
879 <div class="p"><!----></div>
880
881 <h2>References</h2>
882
883 <dl compact="compact">
884  <dt><a href="#CITEffp" name="ffp">[FFP]</a></dt><dd>
885         <b> Implementation of Fuzzy Fingerprinting for 
886          RSA, DSA, MD5 and SHA1</b>
887
888 <div class="p"><!----></div>
889         Plasmoid
890
891 <div class="p"><!----></div>
892         <a href="http://www.thc.org/releases.php">http://www.thc.org/releases.php</a>
893
894 <div class="p"><!----></div>
895 </dd>
896  <dt><a href="#CITErsa" name="rsa">[RSA]</a></dt><dd>
897         <b>A Method for Obtaining Digital Signatures and Public-Key
898                 Cryptosystems</b>
899
900 <div class="p"><!----></div>
901         Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. 
902         Communications of the ACM 21,2 (Feb. 1978), 120-126.
903
904 <div class="p"><!----></div>
905         <a href="http://theory.lcs.mit.edu/~rivest/rsapaper.pdf">http://theory.lcs.mit.edu/&nbsp;rivest/rsapaper.pdf</a>
906
907 <div class="p"><!----></div>
908 </dd>
909  <dt><a href="#CITEilp" name="ilp">[ILP]</a></dt><dd>
910         <b>How to Expose an Eavesdropper</b>
911
912 <div class="p"><!----></div>
913         R. L. Rivest, Adi Shamir, Communications of the ACM, v. 27, n. 4,
914         February 1978, pp. 120-126.
915
916 <div class="p"><!----></div>
917 </dd>
918  <dt><a href="#CITEmd5" name="md5">[MD5]</a></dt><dd>
919         <b>The MD5 Message Digest Algorithm</b>
920
921 <div class="p"><!----></div>
922         R. L. Rivest, RFC 1321. April 1992
923
924 <div class="p"><!----></div>
925         <a href="http://theory.lcs.mit.edu/~rivest/Rivest-MD5.txt">http://theory.lcs.mit.edu/&nbsp;rivest/Rivest-MD5.txt</a>
926
927 <div class="p"><!----></div>
928 </dd>
929  <dt><a href="#CITEdss" name="dss">[DSS]</a></dt><dd>
930         <b>Digital Signature Standard (DSS)</b>
931
932 <div class="p"><!----></div>
933         National Institute of Standards and Technology, NIST FIPS PUB 186,
934         U.S. Department of Commerce, May 1994.
935
936 <div class="p"><!----></div>
937         <a href="http://csrc.nist.gov/publications/fips/fips186-2/fips186-2.pdf">http://csrc.nist.gov/publications/fips/fips186-2/fips186-2.pdf</a>
938
939 <div class="p"><!----></div>
940 </dd>
941  <dt><a href="#CITEsfp" name="sfp">[SFP]</a></dt><dd>
942         <b>SSH for Fun and Profit</b>
943
944 <div class="p"><!----></div>
945         Sebastian Krahmer, July 2002
946
947 <div class="p"><!----></div>
948         <a href="http://stealth.7350.org/ssharp.pdf">http://stealth.7350.org/ssharp.pdf</a>
949
950 <div class="p"><!----></div>
951 </dd>
952  <dt><a href="#CITEssh" name="ssh">[SSH]</a></dt><dd>
953         <b>OpenSSH Suite</b>
954
955 <div class="p"><!----></div>
956         Free version of the SSH protocol suite of network connectivity
957         tools.
958
959 <div class="p"><!----></div>
960         <a href="http://www.openssh.org">http://www.openssh.org</a>
961
962 <div class="p"><!----></div>
963 </dd>
964  <dt><a href="#CITEssl" name="ssl">[SSL]</a></dt><dd>
965         <b>OpenSSL Project</b>
966
967 <div class="p"><!----></div>
968         Open Source toolkit implementing the Secure Sockets Layer (SSL
969         v2/v3) and Transport Layer Security (TLS v1) protocols.
970
971 <div class="p"><!----></div>
972         <a href="http://www.openssl.org">http://www.openssl.org</a>
973
974 <div class="p"><!----></div>
975 </dd>
976  <dt><a href="#CITEds" name="ds">[DS]</a></dt><dd> 
977         <b>DSniff - Tools for network auditing and penetration
978         testing</b>
979
980 <div class="p"><!----></div>
981         Dug Song
982
983 <div class="p"><!----></div>
984         <a href="http://www.monkey.org/~dugsong/dsniff">http://www.monkey.org/&nbsp;dugsong/dsniff</a>
985
986 <div class="p"><!----></div>
987 </dd>
988  <dt><a href="#CITEec" name="ec">[EC]</a></dt><dd>
989         <b>Ettercap Multiprupose Sniffer/Interceptor/Logger</b>
990
991 <div class="p"><!----></div>
992         A. Ornaghi, M. Valleri 
993
994 <div class="p"><!----></div>
995         <a href="http://ettercap.sourceforge.net">http://ettercap.sourceforge.net</a></dd>
996 </dl>
997
998 <div class="p"><!----></div>
999  
1000    </td></tr>
1001    </table>
1002    </body>
1003
1004
1005 <div class="p"><!----></div>
1006
1007 <br /><br /><hr /><small>File translated from
1008 T<sub><font size="-1">E</font></sub>X
1009 by <a href="http://hutchinson.belmont.ma.us/tth/">
1010 T<sub><font size="-1">T</font></sub>H</a>,
1011 version 3.44.<br />On 25 Oct 2003, 16:39.</small>
1012 </html>