fashizzlepop wrote:You haven't given us enough of a description to know what you are talking about. At least give us some more info from the book.

Sorry for the epicly late reply, life got in the way. Anywho, here's all the info:

"0x764. Password Probability Matrix

There is a trade-off between computational power and storage space that exists everywhere. This can be 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 such as 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 principle 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 reasonable amount of time, using a reasonable amount of space. Unfortunately, the dilemma of salts will still present itself, since this method still requires some form of storage. However, there are only 4,096 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 4,096 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, compared to a full hash lookup table (with a fixed salt), and the keyspace that must be brute-forced through is reduced by about 1,018 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 speedup when compared to the two hours needed for an exhaustive bruteforce 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 9,025, bits long (about 1,129 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 2 through 4, 4 through 6, 6 though 8, and 8 though 10, 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 leave only those bits turned on that correspond to the plaintext pairs 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. Since 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. Since each vector has 9,025 entries, there should be about (954 · 2) / 9025 columns. This works out to be about 18,000 columns. Since 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.

Since there are four vectors that 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 also done for the last two characters, providing about 2802, or 78,400, possible plaintext values. Under the assumption of 10,000 cracks per second, this reduced keyspace would take under 8 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 it. 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.

- Code: Select all
`/*********************************************************\`

* Password Probability Matrix * File: ppm_gen.c *

***********************************************************

* *

* Author: Jon Erickson <matrix@phiral.com> *

* 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 *

* be used to quickly crack passwords found within this *

* keyspace with the corresponding ppm_crack.c program. *

* *

\*********************************************************/

#define _XOPEN_SOURCE

#include <unistd.h>

#include <stdio.h>

#include <stdlib.h>

#define HEIGHT 16384

#define WIDTH 1129

#define DEPTH 8

#define SIZE HEIGHT * WIDTH * DEPTH

/* Map a single hash byte to an enumerated value. */

int enum_hashbyte(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;

}

/* Map 3 hash bytes to an enumerated value. */

int enum_hashtriplet(char a, char b, char c) {

return (((enum_hashbyte(c)%4)*4096)+(enum_hashbyte(a)*64)+enum_hashbyte(b));

}

/* Barf a message and exit. */

void barf(char *message, char *extra) {

printf(message, extra);

exit(1);

}

/* Generate a 4-char.ppm file with all possible 4-char passwords (salted w/ je). */

int main() {

char plain[5];

char *code, *data;

int i, j, k, l;

unsigned int charval, val;

FILE *handle;

if (!(handle = fopen("4char.ppm", "w")))

barf("Error: Couldn't open file '4char.ppm' for writing.\n", NULL);

data = (char *) malloc(SIZE);

if (!(data))

barf("Error: Couldn't allocate memory.\n", NULL);

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; // Build every

plain[1] = (char)j; // possible 4-byte

plain[2] = (char)k; // password.

plain[3] = (char)l;

plain[4] = '\0';

code = crypt((const char *)plain, (const char *)"je"); // Hash it.

/* Lossfully store statistical info about the pairings. */

val = enum_hashtriplet(code[2], code[3], code[4]); // Store info about

bytes 2-4.

charval = (i-32)*95 + (j-32); // First 2 plaintext bytes

data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val += (HEIGHT * 4);

charval = (k-32)*95 + (l-32); // Last 2 plaintext bytes

data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val = HEIGHT + enum_hashtriplet(code[4], code[5], code[6]); // bytes 4-6

charval = (i-32)*95 + (j-32); // First 2 plaintext bytes

data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val += (HEIGHT * 4);

charval = (k-32)*95 + (l-32); // Last 2 plaintext bytes

data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val = (2 * HEIGHT) + enum_hashtriplet(code[6], code[7], code[8]); //

bytes 6-8

charval = (i-32)*95 + (j-32); // First 2 plaintext bytes

data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val += (HEIGHT * 4);

charval = (k-32)*95 + (l-32); // Last 2 plaintext bytes

data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val = (3 * HEIGHT) + enum_hashtriplet(code[8], code[9], code[10]);

// bytes 8-10

charval = (i-32)*95 + (j-32); // First 2 plaintext chars

data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

val += (HEIGHT * 4);

charval = (k-32)*95 + (l-32); // Last 2 plaintext bytes

data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));

}

}

}

}

printf("finished.. saving..\n");

fwrite(data, SIZE, 1, handle);

free(data);

fclose(handle);

}

The first piece of code, ppm_gen.c, can be used to generate a fourcharacter password probability matrix, as shown in the output below. The -O3 option passed to GCC tells it to optimize the code for speed when it compiles.

- Code: Select all
`reader@hacking:~/booksrc $ gcc -O3 -o ppm_gen ppm_gen.c -lcrypt`

reader@hacking:~/booksrc $ ./ppm_gen

Adding ** to 4char.ppm..

Adding !** to 4char.ppm..

Adding "** to 4char.ppm..

.:[ output trimmed ]:.

Adding ~|** to 4char.ppm..

Adding ~}** to 4char.ppm..

Adding ~~** to 4char.ppm..

finished.. saving..

@hacking:~ $ ls -lh 4char.ppm

-rw-r--r-- 1 142M 2007-09-30 13:56 4char.ppm

reader@hacking:~/booksrc $

The 142MB 4char.ppm file contains loose associations between the plaintext and hash data for every possible four-character password. This data can then be used by this next program to quickly crack four-character passwords that would foil a dictionary attack.

- Code: Select all
`7.6.5.2. ppm_crack.c`

Code View:

/*********************************************************\

* Password Probability Matrix * File: ppm_crack.c *

***********************************************************

* *

* Author: Jon Erickson <matrix@phiral.com> *

* 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 <unistd.h>

#include <stdio.h>

#include <stdlib.h>

#define HEIGHT 16384

#define WIDTH 1129

#define DEPTH 8

#define SIZE HEIGHT * WIDTH * DEPTH

#define DCM HEIGHT * WIDTH

/* Map a single hash byte to an enumerated value. */

int enum_hashbyte(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;

}

/* Map 3 hash bytes to an enumerated value. */

int enum_hashtriplet(char a, char b, char c) {

return (((enum_hashbyte(c)%4)*4096)+(enum_hashbyte(a)*64)+enum_hashbyte(b));

}

/* Merge two vectors. */

void merge(char *vector1, char *vector2) {

int i;

for(i=0; i < WIDTH; i++)

vector1[i] &= vector2[i];

}

/* Returns the bit in the vector at the passed index position */

int get_vector_bit(char *vector, int index) {

return ((vector[(index/8)]&(1<<(index%8)))>>(index%8));

}

/* Counts the number of plaintext pairs in the passed vector */

int count_vector_bits(char *vector) {

int i, count=0;

for(i=0; i < 9025; i++)

count += get_vector_bit(vector, i);

return count;

}

/* Print the plaintext pairs that each ON bit in the vector enumerates. */

void print_vector(char *vector) {

int i, a, b, val;

for(i=0; i < 9025; i++) {

if(get_vector_bit(vector, i) == 1) { // If bit is on,

a = i / 95; // calculate the

b = i - (a * 95); // plaintext pair

printf("%c%c ",a+32, b+32); // and print it.

}

}

printf("\n");

}

/* Barf a message and exit. */

void barf(char *message, char *extra) {

printf(message, extra);

exit(1);

}

/* Crack a 4-character password using generated 4char.ppm file. */

int main(int argc, char *argv[]) {

char *pass, plain[5];

unsigned char bin_vector1[WIDTH], bin_vector2[WIDTH], 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(argc < 1)

barf("Usage: %s <password hash> (will use the file 4char.ppm)\n", argv[0]);

if(!(fd = fopen("4char.ppm", "r")))

barf("Fatal: Couldn't open PPM file for reading.\n", NULL);

pass = argv[1]; // First argument is password hash

printf("Filtering possible plaintext bytes for the first two characters:\n");

fseek(fd,(DCM*0)+enum_hashtriplet(pass[2], pass[3], pass[4])*WIDTH, SEEK_SET);

fread(bin_vector1, WIDTH, 1, fd); // Read the vector associating bytes 2-4 of hash.

len = count_vector_bits(bin_vector1);

printf("only 1 vector of 4:\t%d plaintext pairs, with %0.2f%% saturation\n", len,

len*100.0/

9025.0);

fseek(fd,(DCM*1)+enum_hashtriplet(pass[4], pass[5], pass[6])*WIDTH, SEEK_SET);

fread(temp_vector, WIDTH, 1, fd); // Read the vector associating bytes 4-6 of hash.

merge(bin_vector1, temp_vector); // Merge it with the first vector.

len = count_vector_bits(bin_vector1);

printf("vectors 1 AND 2 merged:\t%d plaintext pairs, with %0.2f%% saturation\n", len,

len*100.0/9025.0);

fseek(fd,(DCM*2)+enum_hashtriplet(pass[6], pass[7], pass[8])*WIDTH, SEEK_SET);

fread(temp_vector, WIDTH, 1, fd); // Read the vector associating bytes 6-8 of hash.

merge(bin_vector1, temp_vector); // Merge it with the first two vectors.

len = count_vector_bits(bin_vector1);

printf("first 3 vectors merged:\t%d plaintext pairs, with %0.2f%% saturation\n", len,

len*100.0/9025.0);

fseek(fd,(DCM*3)+enum_hashtriplet(pass[8], pass[9],pass[10])*WIDTH, SEEK_SET);

fread(temp_vector, WIDTH, 1, fd); // Read the vector associatind bytes 8-10 of hash.

merge(bin_vector1, temp_vector); // Merge it with the othes vectors.

len = count_vector_bits(bin_vector1);

printf("all 4 vectors merged:\t%d plaintext pairs, with %0.2f%% saturation\n", len,

len*100.0/9025.0);

printf("Possible plaintext pairs for the first two bytes:\n");

print_vector(bin_vector1);

printf("\nFiltering possible plaintext bytes for the last two characters:\n");

fseek(fd,(DCM*4)+enum_hashtriplet(pass[2], pass[3], pass[4])*WIDTH, SEEK_SET);

fread(bin_vector2, WIDTH, 1, fd); // Read the vector associating bytes 2-4 of hash.

len = count_vector_bits(bin_vector2);

printf("only 1 vector of 4:\t%d plaintext pairs, with %0.2f%% saturation\n", len,

len*100.0/

9025.0);

fseek(fd,(DCM*5)+enum_hashtriplet(pass[4], pass[5], pass[6])*WIDTH, SEEK_SET);

fread(temp_vector, WIDTH, 1, fd); // Read the vector associating bytes 4-6 of hash.

merge(bin_vector2, temp_vector); // Merge it with the first vector.

len = count_vector_bits(bin_vector2);

printf("vectors 1 AND 2 merged:\t%d plaintext pairs, with %0.2f%% saturation\n", len,

len*100.0/9025.0);

fseek(fd,(DCM*6)+enum_hashtriplet(pass[6], pass[7], pass[8])*WIDTH, SEEK_SET);

fread(temp_vector, WIDTH, 1, fd); // Read the vector associating bytes 6-8 of hash.

merge(bin_vector2, temp_vector); // Merge it with the first two vectors.

len = count_vector_bits(bin_vector2);

printf("first 3 vectors merged:\t%d plaintext pairs, with %0.2f%% saturation\n", len,

len*100.0/9025.0);

fseek(fd,(DCM*7)+enum_hashtriplet(pass[8], pass[9],pass[10])*WIDTH, SEEK_SET);

fread(temp_vector, WIDTH, 1, fd); // Read the vector associatind bytes 8-10 of hash.

merge(bin_vector2, temp_vector); // Merge it with the othes vectors.

len = count_vector_bits(bin_vector2);

printf("all 4 vectors merged:\t%d plaintext pairs, with %0.2f%% saturation\n", len,

len*100.0/9025.0);

printf("Possible plaintext pairs for the last two bytes:\n");

print_vector(bin_vector2);

printf("Building probability vectors...\n");

for(i=0; i < 9025; i++) { // Find possible first two plaintext bytes.

if(get_vector_bit(bin_vector1, i)==1) {;

prob_vector1[0][pv1_len] = i / 95;

prob_vector1[1][pv1_len] = i - (prob_vector1[0][pv1_len] * 95);

pv1_len++;

}

}

for(i=0; i < 9025; i++) { // Find possible last two plaintext bytes.

if(get_vector_bit(bin_vector2, i)) {

prob_vector2[0][pv2_len] = i / 95;

prob_vector2[1][pv2_len] = i - (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 second piece of code, ppm_crack.c, can be used to crack the troublesome password of h4R% in a matter of seconds:

- Code: Select all
`reader@hacking:~/booksrc $ ./crypt_test h4R% je`

password "h4R%" with salt "je" hashes to ==> jeMqqfIfPNNTE

reader@hacking:~/booksrc $ gcc -O3 -o ppm_crack ppm_crack.c -lcrypt

reader@hacking:~/booksrc $ ./ppm_crack jeMqqfIfPNNTE

Filtering possible plaintext bytes for the first two characters:

only 1 vector of 4: 3801 plaintext pairs, with 42.12% saturation

vectors 1 AND 2 merged: 1666 plaintext pairs, with 18.46% saturation

first 3 vectors merged: 695 plaintext pairs, with 7.70% saturation

all 4 vectors merged: 287 plaintext pairs, with 3.18% saturation

Possible plaintext pairs for the first two bytes:

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 <! <8 =! =3 =H =L =N =Y >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

Filtering possible plaintext bytes for the last two characters:

only 1 vector of 4: 3821 plaintext pairs, with 42.34% saturation

vectors 1 AND 2 merged: 1677 plaintext pairs, with 18.58% saturation

first 3 vectors merged: 713 plaintext pairs, with 7.90% saturation

all 4 vectors merged: 297 plaintext pairs, with 3.29% saturation

Possible plaintext pairs for the last two bytes:

! & != !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 <L <m <r <u =, =4 =v >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%

reader@hacking:~/booksrc $

These programs are proof-of-concept hacks, which take advantage of the bit diffusion provided by hash functions. There are other time-space trade-off attacks, and some have become quite popular. RainbowCrack is a popular tool, which has support for multiple algorithms. If you want to learn more, consult the Internet.

Well, I consulted the Internet, and haven't learned more. So, I turn to you. If you can't give me some more info on this, a helpful push in the right direction would be glorious.

Thanks

~C