chroma
2nd November, 2009, 11:48 AM
This is essentialy a response to a thread in Gen PC Chat (http://www.digital-kaos.co.uk/forums/f94/wireless-hack-63634/)
I explained that cracking a wifi connection with WPA - PSK would be both technical, lengthy and fairly difficult.
This didnt seem to disuade people from wanting to know more so here goes:
WPA PSK now with added C++ fiber for all your dietary needs
WPA - PSK Wireless Protected Access - Pre-Shared Key mode (sometimes pre is substituted for personal or private)
WEP (Wired Equivalent Protection) was discovered early on to be pants, in that unlike Ronseal, it didnt do what it said on the tin.
Boffins got into a panic and devised WPA as a stopgap measure to protect things until the arrival of WPA2 with its fancy AES (Advanced Encryption Standard: ie. a whole nother ballgame) encryption methods.
Its essentialy a method of encrypting packets of data with a key to prevent snooping, the weakness of this system is that once you know the key you can in fact snoop, bringing the entire concept down on its knees like a cheap hooker.
The important part of all this is understanding the encryption, which is where this little primer will come in and cause you to go "squeg eyed" and has known side effects like migranes, dizziness and nausiating confusion hopefully it will all make some sort of sense in the end though.
PSK basics
A PSK is a 256bit value or "key" thats known to every device connected on the WLAN (Wireless Local Area Network) its made using an encryption algorithm that works essentialy by using the SSID (Service Set Identifier) as whats known as a "salt" (more on this later) this is then combinded with a passphrase of between 8 and 63 characters from the ASCII table and then randomised through 4096 cycles or "itterations."
Headache yet? its in the post trust me.
you have mail
salt? algorithms? ascii? itterations? wtf?
You set up your router, it asks you for your wifi passphrase.
you type in "whatever_i_can_easily_remember" the router then takes this "whatever_i_can_easily_remember" and applies the "Password-Based Key Deriviation Function" or that algorithym called PBKDF2 by combining the SALT (by garbling the ssid with the hmac-sha1 algorithm) with the Passphrase to randomise it, then it repeats this over again and again to create the 256bit PSK.
The thing is computers dont "do" random, they cant, random is a mathmaticaly heavy problem so computers do "kind of random" or more accurately PSEUDORANDOM.
This is good because with a little bit of intensive math you can figure out the original numbers.
To further obscure this process computers use whats known as "salt"
Salt is useful in that a password can be bruteforced with relative ease with a few dictionaries (that is to say a few databases with common words) by applying a salt these common words mutate into abstract strings so instead of "cabbage" you wind up with (8t"2!d$) which shouldnt be on any ordianry crackers dictionary.
This means that in order to brute force a salted password you would need to calculate every password sequentialy between !!!!!!! and ~~~~~~~ (printable ascii has 95 chars that start at ! and go all the way through every number both cases of letters and symbols till it reaches ~) so for this 7 digit password you would need to compute and attempt 69,833,729,609,375 passwords in order to guarantee you got the right one. if you did 60 per second it would take you 323304303.74ish hours or 36906.88 years.
Bear in mind that this is just a stupid 7 digit password PSK's are bigger... a lot bigger 256bit (32 random (full) ascii characters) so to brute force it you would need longer than the universe has been in existance, whats a couple of billion years between friends?
Reverse engineering is the only sane option, it would take far less time to do so than to randomly input digits.
screw it, heres the code in c++ using basic libraries, so its painfuly slow but abundantly clear about what it does, ill talk you through it.
//part 1 "setup"
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
unsigned long Rol(unsigned long x, int y);
unsigned long Ror(unsigned long x, int y);
unsigned long f(unsigned long B,unsigned long C,unsigned long D, int t);
unsigned long H[5];
unsigned long T[512]={0};
void HMAC(string text, string key);
void SHA1(string s);
void PBKDF2(string P,string S, int c, int dkLen);
//part 2 "The main"
int main()
{
char P[8192];
char S[8192];
int dkLen,c;
c = 4096;
dkLen = 32;
cout << "Password Based Key-Derivation function 2 (PBKDF2) with" << endl << "SHA-1 Hashing Algorithm. \n \n";
cout << "Enter Password: ";
cin.getline(P, 8192, '\n');
cout << "Enter Salt: ";
cin.getline(S, 8192, '\n');;
cout << "Enter Number of Iterations c: ";
cin >> c;
cout << "Enter intended length in bytes of the derived key: ";
cin >> dkLen;
cout << "Derived Key: " << endl;
PBKDF2(P,S,c,dkLen);
for(int i=0; i<(dkLen/4); i++)
{
cout << hex << T;
}
cout << endl;
return 0;
}
//Part 3 "PBKDF2 function"
void PBKDF2(string P, string S,int c,int dkLen)
{
string U;
unsigned long L[5]={0,0,0,0,0};
int hlen,l,r;
char t;
hlen = 20;
//Needs a replacement for ceiling function: l = ceil(dkLen/hlen)+1;
l = (dkLen/hlen)+1;
r = dkLen -(l-1)*hlen;
for(int i=1; i<=l; i++)
{
t = 0;
U = S + t + t + t;
t = i;
U = U + t;
L[0] = L[1] = L[2] = L[3] = L[4] = 0;
for(int j=1; j<=c; j++)
{
HMAC(U,P);
L[0] = L[0]^H[0];
L[1] = L[1]^H[1];
L[2] = L[2]^H[2];
L[3] = L[3]^H[3];
L[4] = L[4]^H[4];
U = "";
for(int x=0; x<5; x++)
{
for(int y=0; y<4; y++)
{
t = ((H[x] >> 8*(3-y)) % 256);
U = U + t;
}
}
}
T[5*(i-1)] = L[0];
T[5*(i-1)+1] = L[1];
T[5*(i-1)+2] = L[2];
T[5*(i-1)+3] = L[3];
T[5*(i-1)+4] = L[4];
}
}
// Part 4 "HMAC function"
void HMAC(string text, string key)
{
char c;
string s;
unsigned long Key[16] = {0};
unsigned long X[16] = {0};
unsigned long Y[16] = {0};
unsigned long ipad = 0x36363636;
unsigned long opad = 0x5c5c5c5c;
int k;
s = "";
//Process string key into sub-key
//Hash key in case it is less than 64 bytes
if (key.length() > 64)
{
SHA1(key);
Key[0] = H[0];
Key[1] = H[1];
Key[2] = H[2];
Key[3] = H[3];
Key[4] = H[4];
}
else
{
for(int i=0; i<16; i++)
{
for(int j=0; j<4; j++)
{
if (4*i+j <= key.length())
{
k = key[4*i+j];
}
else
{
k = 0;
}
if (k<0)
{
k = k + 256;
}
Key[i]= Key[i] + k*pow(256,(double)3-j);
}
}
}
for(int i=0; i<16; i++)
{
X[i] = Key[i]^ipad;
Y[i] = Key[i]^opad;
}
//Turn X-Array into a String
for(int i=0; i<16; i++)
{
for(int j=0; j<4; j++)
{
c = ((X[i] >> 8*(3-j)) % 256);
s = s + c;
}
}
//Append text to string
s = s + text;
//Hash X-Array
SHA1(s);
s = "";
//Turn Y-Array into a String
for(int i=0; i<16; i++)
{
for(int j=0; j<4; j++)
{
c = ((Y[i] >> 8*(3-j)) % 256);
s = s + c;
}
}
//Append Hashed X-Array to Y-Array in string
for(int i=0; i<5; i++)
{
for(int j=0; j<4; j++)
{
c = ((H[i] >> 8*(3-j)) % 256);
s = s + c;
}
}
//Hash final concatenated string
SHA1(s);
}
//Part 5 "SHA-1 Algorithm"
void SHA1(string s)
{
unsigned long K[80];
unsigned long A,B,C,D,E,TEMP;
int r,k,ln;
H[0]=0x67452301;
H[1]=0xefcdab89;
H[2]=0x98badcfe;
H[3]=0x10325476;
H[4]=0xc3d2e1f0;
ln=s.length();
r = int((ln+1)/64);
if (((ln+1) % 64) > 56)
{
r=r+1;
}
// initialize Constants
for(int t=0; t<80; t++)
{
if (t<20)
{
K[t] = 0x5a827999;
}
if ((t>19)&(t<40))
{
K[t] = 0x6ED9EBA1;
}
if ((t>39)&(t<60))
{
K[t] = 0x8F1BBCDC;
}
if (t>59)
{
K[t] = 0xca62c1d6;
}
}
for(int l=0; l <= r; l++)
{
unsigned long W[80]={0};
//Initialize Text
for (int i=0; i<16; i++)
{
for(int j=0; j<4; j++)
{
if (4*i+j <= ln)
{
k = s[64*l+4*i+j];
}
else
{
k = 0;
}
if (k<0)
{
k = k +256;
}
if (4*i+j == ln)
{
k = 0x80;
}
W[i]= W[i] + k*pow(256,(double)3-j);
}
}
if ((W[14]==0)&(W[15]==0))
{
W[15]=8*s.length();
}
// Hash Cycle
for (int t = 16; t <80; t++)
{
W[t] = Rol(W[t-3]^W[t-8]^W[t-14]^W[t-16],1);
}
A = H[0];
B = H[1];
C = H[2];
D = H[3];
E = H[4];
for(int t = 0; t < 80; t++)
{
TEMP = Rol(A,5) + f(B,C,D,t) + E + W[t] + K[t];
E = D;
D = C;
C = Rol(B,30);
B = A;
A = TEMP;
}
H[0] = H[0] + A;
H[1] = H[1] + B;
H[2] = H[2] + C;
H[3] = H[3] + D;
H[4] = H[4] + E;
ln = ln - 64;
}
}
//Part 6 "Returning values"
unsigned long f(unsigned long B,unsigned long C,unsigned long D, int t)
{
if (t < 20)
{
return ((B & C)^((~B) & D));
}
if ((t > 19) & (t < 40))
{
return (B ^ C ^ D);
}
if ((t > 39) & (t < 60))
{
return ((B & C)^(B & D)^(C & D));
}
if (t > 59)
{
return (B ^ C ^ D);
}
}
unsigned long Rol(unsigned long x, int y)
{
if (y % 32 == 0) {return x;}
else {return ((x << y)^(x >> -y));}
}
unsigned long Ror(unsigned long x, int y)
{
if (y % 32 == 0) {return x;}
else {return ((x >> y)^(x << -y));}
}
Now your either sitting at this point white as a sheet wondering wtf that moonspeak is, or else you've just got yourself a new toy to play with and are busy firing up vi to add optimisations... or your rolling on the floor buckled over at the sheer horror of the code, getting ready to post that "doing it X or Y ways would be more efficient" for the former squad i'll guide you through with the bare essentials.
preamble:
C++ is a lovely language in that it can do just about anything with relative speed, it doesnt need much in the way past basic setup to "go like shit off a shovel" the main trick with it is to make it do what you want, like wrestling a bear really, you make a single error somewhere and results are "vague" at best and all that speed has just proppeled you into a brick wall. with that said:
All programs adhere to some fairly basic rules, you start by adding libraries and defining anything complicated and global for the rest of the code to use.
Then you move on to your MAIN function, this does your main task and with any program outside the realm of "herro za wurdooo" or printing penis infinately across a screen it will use other functions to help pass it stuff to use.
Finaly ending with your returns that return values to the operating system and or rest of your code.
Part 1 (// is just for commenting anything following on the same line after // is ignored by the compiler and is there merely for reader reference)
This part is just typical program setup, #include <iostream> for instance just tells the compiler to look up the library called iostream for the meanings of command in the rest of the program.
iostream controls streams to input and output like cout is "console out" meaning print to the damned screen. cin is console in meaning read whatever is typed on the screen and store it someplace. string is a library for handling strings, cmath is a library to handle complex math and so forth.
using namespace std;
this tells the compiler to use standard namespacing, you can split code into seperate namespaces, this essentialy means you can use variables of the same name to do different things without the compiler shitting a brick, so long as its in a different namespace they wont interfere with each other.
unsigned long Rol(unsigned long x, int y);
This is a "function prototype" a fancy way of saying ive told the compiler that later on there will be a function called Rol and that Rol will need the variables x and y from elsewhere in the code to do its job properly.
unsigned long
c/c++ are strongly "typed" languages (that doesnt mean pounding hard on the keys with hamfistedness) it means that variables are assigned types, there are several to choose from, int being the basic (integer) or whole numbers.
float being the basic decimal 3.14 is a floating point, double's are "double precision floating point numbers" meaning you can have more numbers after the point. 3.14159 for instance.
you can also have longs (an int with more room essentialy), bools (true false), chars(a,B,c), wchar_t's(unicode) shorts(bigger than char but smaller than int) and so forth (if ive used anything wierd i'll explain as i go)
UNSIGNED, this is important, theres no difference between 1 and -1 to a computer except the -sign so in order to represent negative numbers c/c++ by default signs every variable, this uses up a lot of space by splitting the maximum value a variable can hold in half, half negatives and half regular old positive values, by unsigning you can store twice as much in a variable so long as its not going to wind up a negative number and cause "brick wall at speed."
void HMAC(string text, string key);
Same as abve but lacking a type, meaning its not going to return anything meaningful back to the operating system, these functions usualy just post things to other functions.
Part2 "The Main"
Your first function.
Functions are surrounded by braces {} fail to use braces and you hit the wall, fail to include a semi-colon ; at the end of the right lines and you also hit the wall. (this is where setting up your editor to colour coordinate and apply language formatting is a godsend, it helps you navigate all the god damned walls)
They start with a variable type (in this case int) to return to the operating system when they complete, the most common being return 0; this just means your telling the os that nothing caught fire. wanna know more? read a book, otherwise i'll be here for eons.
The purpose of your main is to set up all your variables, which is what all that char P[8192]; stuff is, this means make me a char called P and allow it to hold 8192 digits (if you see anything in brackets [] then its more often than not denoting an "array" which is just a way of saying a list.
int dkLen,c; this means make me an integer called dkLen then make another one called c by seperating with a comma , you can set up reams of variables of the same type without having to resort to:
int something;
int somewhere;
int somehow;
int something, somewhere, somehow; does exactly the same only faster and faster is good when you could be sitting for days at a time. you can call variables whatever you want to be honest, something meaningful helps you remember wtf eveything is, in this case dkLen = desired key length, c is cycles or itterations (but i gets used frequently on the fly hence the reason its not just i) P for password S for salt... making any sense? i could have named them a, b x and y but if theres a bug its easier to trace with easily understood variables, you'll have to take my word for that at this point but its good advice.
its also customary to give your variables default values just incase theyre used before expected and if that happens with no value in em then more often than not you will brick wall. this is what the = operator does, c=4096 just makes sure that 4096 gets stored in c (you can and will overwrite variables later but defaults help prevent bad things)
cout << "Password Based Key-Derivation function 2 (PBKDF2) with" << endl << "SHA-1 Hashing Algorithm. \n \n";
this tell the program to print to the screen, << (left shift opperator) means stream whatever is after it to what before it. ENDL means end line or go to the next line, \n does the same thing but its faster to type, i covered faster is better already, in other cout statements youll see variable names after the <<'s that just prints the contents of that variable to the screen capish?
cin.getline(P, 8192, '\n');
cin is console in, meaning read whats been typed and then store it in a variable, getline just means read the entire string (strings are just arrays of characters, the mean more than one letter or symbol, they will be the bane of your life, theres no "default" way to deal with strings in c/c++ and serve as the inspiration of many a flamewar) all this line does is store everything you spew at the keyboard into the character array P then terminate with a newline.
cin >> c;
far easier than strings, it just states to put the number written into variable c.
note in the effort of simplicity i never did any actual error handling so if you type "penis" here instead of a whole number then you will brick wall.
PBKDF2(P,S,c,dkLen);
this is yet another function thing. this just tells the compiler to use the values given in this function into that particular function for use later. its essentialy the glue of the code, these statements allow you to swap data around and do usefull stuff.
[i]for(int i=0; i<(dkLen/4); i++)
{
cout << hex << T[I];
}LOOPS'n'STUFF for is a loop command, note that it doesnt have a semicolon; that would be easy right? it would also be _you guessed it_ brick wall. simple rule if it uses braces it wont have use for a semicolon.
This just states to do everything proceeding it in the braces {} till the conditions in the parentheses () are met.
int i=0; this is just initialising a variable on the fly to use immediately.
i<(dkLen/4) this just makes the loop chec to see if i is less than dkLen divided by 4, it it is then it should do whatever is in the for loop and then:
i++ this is the "increment operator" that just means increase the value of i by 1 each time its run. -- also works but it decrements instead.
The actual loop just prints in HEX notation (values between 0 and F) the values contained in the T[] array.
The interesting part is the this means on the first time round it will print T[0] (arrays start at 0 by the way not 1, this leads to headaches at times) then it will check the loop again to see if i is still less than (dkLen/4) and if so will increase the value of i to 1 meaning it will then print T[1] then T[2] etc.
Loops are the only sane way to deal with getting data into and out of arrays and strings. you will rapidly either learn to love loops or learn to loathe strings and arrays.
[I]return 0; this means the program finishes without causing any harm and you can go about your day.
synopsis this function essenialy promps the user for information and stores that in variables, then it calls another function and passes it the values you just gave, it then prints the values contained in the string T[] to the screen (T[]'s values will be formed in another function) then gives the return type 0 to the OS telling it it finished in good order.
Thats programming in a nutshell, so you can forgive me for missing out a lot of the rest of the code and only highlighting specific details from now on (otherwise we really will be here for weeks)
Part 3 "PBKDF2 function"
Now down to the fun stuff, the actual workings.
This time we'll be dealing with the PBKDF2 algorithm.
As you know void means no usable return type to worry about and the stuff in parentheses just means actual values to manipulate for the rest of the function and program.
unsigned long L[5]={0,0,0,0,0}; The rest of the code surrounding this gemstone should be readily familiar at this point, this one here is just setting up an array on "the fly" you saw previously that you can spew stuff out of an array using a for loop, you can also put data in with a for loop too.
however you can also manualy input every value yourself by using parenthises and commas. all this means is set up an array called L with 5 values each one being 0.
l = (dkLen/hlen)+1;
Its all math from here on out, and some of it heavy at that, hopefully you'll be able to grasp whats going on at this point and things shouldnt look nearly as daunting.
all that does is assigns l the value of dkLen devided by 20 (then adds a 1 as a workaround to arrays starting at 0.
The previous comment is more for my benefit than anyone elses, ive not set up a "ceiling" meaning that values could overun their sizes if im not careful this causes variables to overrun and causes "brick wall" at worst, completely meaningless results at best.
for(int i=1; i<=l; i++)
{
t = 0;
U = S + t + t + t;
t = i;
U = U + t;
L[0] = L[1] = L[2] = L[3] = L[4] = 0;
for(int j=1; j<=c; j++)
{
HMAC(U,P);
L[0] = L[0]^H[0];
L[1] = L[1]^H[1];
L[2] = L[2]^H[2];
L[3] = L[3]^H[3];
L[4] = L[4]^H[4];
U = "";
for(int x=0; x<5; x++)
{
for(int y=0; y<4; y++)
{
t = ((H[x] >> 8*(3-y)) % 256);
U = U + t;
}
}
}
T[5*(i-1)] = L[0];
T[5*(i-1)+1] = L[1];
T[5*(i-1)+2] = L[2];
T[5*(i-1)+3] = L[3];
T[5*(i-1)+4] = L[4];
}
Nesting, we aint coverd that yet! nesting is placing a loop within a loop, the last loop has priority in that for(int y=0; >> 8*(3-y)) % 256); will need to complte its runs before the loop that initiated that can continue its next cycle. in this case y will do 5 runs (0,1,2,3,4) to every 1 cycle x completes, and x will complete 6 cycles to ever 1 j completes which will have to run its lot before i can loop again. all in all y will do its job a whole lot, numbering in several thousands here.
Every time the i loop runs it will reset the values of all those variables then assigns values to the T[]array with the values in the L[]array...
T[5*(i-10] = L[0] means place the value thats in L[0] into the position in the T[]array in this case its whaever i in the for loop is - 1 then times by 5 so on the first run it will wind up as T[0] second time around it will be T[5] then T[10] etc, with me so far?
back to arrays those numbers in the brackets[]? theyre not actual values, think of them more as positions. like i said an array is just a digital list, so think of a grocery list.
L[0] could be "peas" and below that is L[1] which is "cabbage" and so forth, the numbers just mark off the position on the list, they dont denote the actual values.
Now that the easy stuff is ironed out your probbably wondering wtf is the value in L[0] then? well thats worked out in the next loop L[0] = L[0]^H[0];
that is to say that L[0] has the value of L[0]^H[0] (H[0] refers to a position in memory thats specified later "H[0]=0x67452301;" to be exact)
^ denotes a "bitwise xor" that means that it compares the values stored in H[0]'s memory location and then XOR's that against the value already stored in L[0] and compares the binary results...
simply put an XOR means that it can be either a 1 in L and 0 in H or vice versa but if it winds up as a 1 in both or a 0 in both it will default to whichever value it was initialy.
You should by now be bleeding out your nose, or at least have lost partial vision. but thats ok. its juat moonspeak for swapping values around in a set sequence, like i said, it wasnt going to be easy to understand or translate to laymans terms.
Persevering on. the next loop further complicates things by placing a value in U = (U + t) where t is determined from the value of the remainder between H which is "bitshifted" to the right by 8 times the value of (3- however many loops y has done) so on the first loop it will be 8*(3-0) or 24places.
So for the first loop t = H[0] >> 24 % 256
% is the "modulus" operator... that gives the remainder of a devisor... yeah i know right?
Simply put 10 devided by 3 is 3 with a remainder of 1 yeah?
so the modulus or 10 % 3 is 1
This might appear to be fairly useless and pointless but its extremely usefull when transforming between numerical bases (binary is base 2, hex is 16 decimal is 10 etc)
By now you should be able to figure out that the function essentialy does a bunch of math governed by a set of rules on to the T[] array using otther stuff from other functions. you should also begin to grasp math operators used and be able to work out values if a gun barrel was placed next to your head.
That about wraps things up on the code front, reading through the rest theres not much else thats not already been explained, so things should become apparent just by reading whats going on. i figure at this point if there are any questions you can post away and i'll answer them.
So wtf use is that?
Back to reality... or as close an approximation as i can at this point
Well this is exactly what your router does with your passphrase albeit in a far more optimised form, ive tried my best to keep it simple, embeded deveopers dont have that luxury and need things to be fast and small and lightweight, this means that the code rapidly becomes a nightmare of obscure calls and features that would be impossable to fully wade through.
By now you should see the math thats involved in each step of the conversion process and this gives you a valuable insight into less than straightforward its going to be to reverse a PSK into a passphrase.
To be continued... cause its stupid oclock and my face hurts.
More coverage to follow, including tools, more on how the wpa psk standard works between devices and so forth.
I explained that cracking a wifi connection with WPA - PSK would be both technical, lengthy and fairly difficult.
This didnt seem to disuade people from wanting to know more so here goes:
WPA PSK now with added C++ fiber for all your dietary needs
WPA - PSK Wireless Protected Access - Pre-Shared Key mode (sometimes pre is substituted for personal or private)
WEP (Wired Equivalent Protection) was discovered early on to be pants, in that unlike Ronseal, it didnt do what it said on the tin.
Boffins got into a panic and devised WPA as a stopgap measure to protect things until the arrival of WPA2 with its fancy AES (Advanced Encryption Standard: ie. a whole nother ballgame) encryption methods.
Its essentialy a method of encrypting packets of data with a key to prevent snooping, the weakness of this system is that once you know the key you can in fact snoop, bringing the entire concept down on its knees like a cheap hooker.
The important part of all this is understanding the encryption, which is where this little primer will come in and cause you to go "squeg eyed" and has known side effects like migranes, dizziness and nausiating confusion hopefully it will all make some sort of sense in the end though.
PSK basics
A PSK is a 256bit value or "key" thats known to every device connected on the WLAN (Wireless Local Area Network) its made using an encryption algorithm that works essentialy by using the SSID (Service Set Identifier) as whats known as a "salt" (more on this later) this is then combinded with a passphrase of between 8 and 63 characters from the ASCII table and then randomised through 4096 cycles or "itterations."
Headache yet? its in the post trust me.
you have mail
salt? algorithms? ascii? itterations? wtf?
You set up your router, it asks you for your wifi passphrase.
you type in "whatever_i_can_easily_remember" the router then takes this "whatever_i_can_easily_remember" and applies the "Password-Based Key Deriviation Function" or that algorithym called PBKDF2 by combining the SALT (by garbling the ssid with the hmac-sha1 algorithm) with the Passphrase to randomise it, then it repeats this over again and again to create the 256bit PSK.
The thing is computers dont "do" random, they cant, random is a mathmaticaly heavy problem so computers do "kind of random" or more accurately PSEUDORANDOM.
This is good because with a little bit of intensive math you can figure out the original numbers.
To further obscure this process computers use whats known as "salt"
Salt is useful in that a password can be bruteforced with relative ease with a few dictionaries (that is to say a few databases with common words) by applying a salt these common words mutate into abstract strings so instead of "cabbage" you wind up with (8t"2!d$) which shouldnt be on any ordianry crackers dictionary.
This means that in order to brute force a salted password you would need to calculate every password sequentialy between !!!!!!! and ~~~~~~~ (printable ascii has 95 chars that start at ! and go all the way through every number both cases of letters and symbols till it reaches ~) so for this 7 digit password you would need to compute and attempt 69,833,729,609,375 passwords in order to guarantee you got the right one. if you did 60 per second it would take you 323304303.74ish hours or 36906.88 years.
Bear in mind that this is just a stupid 7 digit password PSK's are bigger... a lot bigger 256bit (32 random (full) ascii characters) so to brute force it you would need longer than the universe has been in existance, whats a couple of billion years between friends?
Reverse engineering is the only sane option, it would take far less time to do so than to randomly input digits.
screw it, heres the code in c++ using basic libraries, so its painfuly slow but abundantly clear about what it does, ill talk you through it.
//part 1 "setup"
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
unsigned long Rol(unsigned long x, int y);
unsigned long Ror(unsigned long x, int y);
unsigned long f(unsigned long B,unsigned long C,unsigned long D, int t);
unsigned long H[5];
unsigned long T[512]={0};
void HMAC(string text, string key);
void SHA1(string s);
void PBKDF2(string P,string S, int c, int dkLen);
//part 2 "The main"
int main()
{
char P[8192];
char S[8192];
int dkLen,c;
c = 4096;
dkLen = 32;
cout << "Password Based Key-Derivation function 2 (PBKDF2) with" << endl << "SHA-1 Hashing Algorithm. \n \n";
cout << "Enter Password: ";
cin.getline(P, 8192, '\n');
cout << "Enter Salt: ";
cin.getline(S, 8192, '\n');;
cout << "Enter Number of Iterations c: ";
cin >> c;
cout << "Enter intended length in bytes of the derived key: ";
cin >> dkLen;
cout << "Derived Key: " << endl;
PBKDF2(P,S,c,dkLen);
for(int i=0; i<(dkLen/4); i++)
{
cout << hex << T;
}
cout << endl;
return 0;
}
//Part 3 "PBKDF2 function"
void PBKDF2(string P, string S,int c,int dkLen)
{
string U;
unsigned long L[5]={0,0,0,0,0};
int hlen,l,r;
char t;
hlen = 20;
//Needs a replacement for ceiling function: l = ceil(dkLen/hlen)+1;
l = (dkLen/hlen)+1;
r = dkLen -(l-1)*hlen;
for(int i=1; i<=l; i++)
{
t = 0;
U = S + t + t + t;
t = i;
U = U + t;
L[0] = L[1] = L[2] = L[3] = L[4] = 0;
for(int j=1; j<=c; j++)
{
HMAC(U,P);
L[0] = L[0]^H[0];
L[1] = L[1]^H[1];
L[2] = L[2]^H[2];
L[3] = L[3]^H[3];
L[4] = L[4]^H[4];
U = "";
for(int x=0; x<5; x++)
{
for(int y=0; y<4; y++)
{
t = ((H[x] >> 8*(3-y)) % 256);
U = U + t;
}
}
}
T[5*(i-1)] = L[0];
T[5*(i-1)+1] = L[1];
T[5*(i-1)+2] = L[2];
T[5*(i-1)+3] = L[3];
T[5*(i-1)+4] = L[4];
}
}
// Part 4 "HMAC function"
void HMAC(string text, string key)
{
char c;
string s;
unsigned long Key[16] = {0};
unsigned long X[16] = {0};
unsigned long Y[16] = {0};
unsigned long ipad = 0x36363636;
unsigned long opad = 0x5c5c5c5c;
int k;
s = "";
//Process string key into sub-key
//Hash key in case it is less than 64 bytes
if (key.length() > 64)
{
SHA1(key);
Key[0] = H[0];
Key[1] = H[1];
Key[2] = H[2];
Key[3] = H[3];
Key[4] = H[4];
}
else
{
for(int i=0; i<16; i++)
{
for(int j=0; j<4; j++)
{
if (4*i+j <= key.length())
{
k = key[4*i+j];
}
else
{
k = 0;
}
if (k<0)
{
k = k + 256;
}
Key[i]= Key[i] + k*pow(256,(double)3-j);
}
}
}
for(int i=0; i<16; i++)
{
X[i] = Key[i]^ipad;
Y[i] = Key[i]^opad;
}
//Turn X-Array into a String
for(int i=0; i<16; i++)
{
for(int j=0; j<4; j++)
{
c = ((X[i] >> 8*(3-j)) % 256);
s = s + c;
}
}
//Append text to string
s = s + text;
//Hash X-Array
SHA1(s);
s = "";
//Turn Y-Array into a String
for(int i=0; i<16; i++)
{
for(int j=0; j<4; j++)
{
c = ((Y[i] >> 8*(3-j)) % 256);
s = s + c;
}
}
//Append Hashed X-Array to Y-Array in string
for(int i=0; i<5; i++)
{
for(int j=0; j<4; j++)
{
c = ((H[i] >> 8*(3-j)) % 256);
s = s + c;
}
}
//Hash final concatenated string
SHA1(s);
}
//Part 5 "SHA-1 Algorithm"
void SHA1(string s)
{
unsigned long K[80];
unsigned long A,B,C,D,E,TEMP;
int r,k,ln;
H[0]=0x67452301;
H[1]=0xefcdab89;
H[2]=0x98badcfe;
H[3]=0x10325476;
H[4]=0xc3d2e1f0;
ln=s.length();
r = int((ln+1)/64);
if (((ln+1) % 64) > 56)
{
r=r+1;
}
// initialize Constants
for(int t=0; t<80; t++)
{
if (t<20)
{
K[t] = 0x5a827999;
}
if ((t>19)&(t<40))
{
K[t] = 0x6ED9EBA1;
}
if ((t>39)&(t<60))
{
K[t] = 0x8F1BBCDC;
}
if (t>59)
{
K[t] = 0xca62c1d6;
}
}
for(int l=0; l <= r; l++)
{
unsigned long W[80]={0};
//Initialize Text
for (int i=0; i<16; i++)
{
for(int j=0; j<4; j++)
{
if (4*i+j <= ln)
{
k = s[64*l+4*i+j];
}
else
{
k = 0;
}
if (k<0)
{
k = k +256;
}
if (4*i+j == ln)
{
k = 0x80;
}
W[i]= W[i] + k*pow(256,(double)3-j);
}
}
if ((W[14]==0)&(W[15]==0))
{
W[15]=8*s.length();
}
// Hash Cycle
for (int t = 16; t <80; t++)
{
W[t] = Rol(W[t-3]^W[t-8]^W[t-14]^W[t-16],1);
}
A = H[0];
B = H[1];
C = H[2];
D = H[3];
E = H[4];
for(int t = 0; t < 80; t++)
{
TEMP = Rol(A,5) + f(B,C,D,t) + E + W[t] + K[t];
E = D;
D = C;
C = Rol(B,30);
B = A;
A = TEMP;
}
H[0] = H[0] + A;
H[1] = H[1] + B;
H[2] = H[2] + C;
H[3] = H[3] + D;
H[4] = H[4] + E;
ln = ln - 64;
}
}
//Part 6 "Returning values"
unsigned long f(unsigned long B,unsigned long C,unsigned long D, int t)
{
if (t < 20)
{
return ((B & C)^((~B) & D));
}
if ((t > 19) & (t < 40))
{
return (B ^ C ^ D);
}
if ((t > 39) & (t < 60))
{
return ((B & C)^(B & D)^(C & D));
}
if (t > 59)
{
return (B ^ C ^ D);
}
}
unsigned long Rol(unsigned long x, int y)
{
if (y % 32 == 0) {return x;}
else {return ((x << y)^(x >> -y));}
}
unsigned long Ror(unsigned long x, int y)
{
if (y % 32 == 0) {return x;}
else {return ((x >> y)^(x << -y));}
}
Now your either sitting at this point white as a sheet wondering wtf that moonspeak is, or else you've just got yourself a new toy to play with and are busy firing up vi to add optimisations... or your rolling on the floor buckled over at the sheer horror of the code, getting ready to post that "doing it X or Y ways would be more efficient" for the former squad i'll guide you through with the bare essentials.
preamble:
C++ is a lovely language in that it can do just about anything with relative speed, it doesnt need much in the way past basic setup to "go like shit off a shovel" the main trick with it is to make it do what you want, like wrestling a bear really, you make a single error somewhere and results are "vague" at best and all that speed has just proppeled you into a brick wall. with that said:
All programs adhere to some fairly basic rules, you start by adding libraries and defining anything complicated and global for the rest of the code to use.
Then you move on to your MAIN function, this does your main task and with any program outside the realm of "herro za wurdooo" or printing penis infinately across a screen it will use other functions to help pass it stuff to use.
Finaly ending with your returns that return values to the operating system and or rest of your code.
Part 1 (// is just for commenting anything following on the same line after // is ignored by the compiler and is there merely for reader reference)
This part is just typical program setup, #include <iostream> for instance just tells the compiler to look up the library called iostream for the meanings of command in the rest of the program.
iostream controls streams to input and output like cout is "console out" meaning print to the damned screen. cin is console in meaning read whatever is typed on the screen and store it someplace. string is a library for handling strings, cmath is a library to handle complex math and so forth.
using namespace std;
this tells the compiler to use standard namespacing, you can split code into seperate namespaces, this essentialy means you can use variables of the same name to do different things without the compiler shitting a brick, so long as its in a different namespace they wont interfere with each other.
unsigned long Rol(unsigned long x, int y);
This is a "function prototype" a fancy way of saying ive told the compiler that later on there will be a function called Rol and that Rol will need the variables x and y from elsewhere in the code to do its job properly.
unsigned long
c/c++ are strongly "typed" languages (that doesnt mean pounding hard on the keys with hamfistedness) it means that variables are assigned types, there are several to choose from, int being the basic (integer) or whole numbers.
float being the basic decimal 3.14 is a floating point, double's are "double precision floating point numbers" meaning you can have more numbers after the point. 3.14159 for instance.
you can also have longs (an int with more room essentialy), bools (true false), chars(a,B,c), wchar_t's(unicode) shorts(bigger than char but smaller than int) and so forth (if ive used anything wierd i'll explain as i go)
UNSIGNED, this is important, theres no difference between 1 and -1 to a computer except the -sign so in order to represent negative numbers c/c++ by default signs every variable, this uses up a lot of space by splitting the maximum value a variable can hold in half, half negatives and half regular old positive values, by unsigning you can store twice as much in a variable so long as its not going to wind up a negative number and cause "brick wall at speed."
void HMAC(string text, string key);
Same as abve but lacking a type, meaning its not going to return anything meaningful back to the operating system, these functions usualy just post things to other functions.
Part2 "The Main"
Your first function.
Functions are surrounded by braces {} fail to use braces and you hit the wall, fail to include a semi-colon ; at the end of the right lines and you also hit the wall. (this is where setting up your editor to colour coordinate and apply language formatting is a godsend, it helps you navigate all the god damned walls)
They start with a variable type (in this case int) to return to the operating system when they complete, the most common being return 0; this just means your telling the os that nothing caught fire. wanna know more? read a book, otherwise i'll be here for eons.
The purpose of your main is to set up all your variables, which is what all that char P[8192]; stuff is, this means make me a char called P and allow it to hold 8192 digits (if you see anything in brackets [] then its more often than not denoting an "array" which is just a way of saying a list.
int dkLen,c; this means make me an integer called dkLen then make another one called c by seperating with a comma , you can set up reams of variables of the same type without having to resort to:
int something;
int somewhere;
int somehow;
int something, somewhere, somehow; does exactly the same only faster and faster is good when you could be sitting for days at a time. you can call variables whatever you want to be honest, something meaningful helps you remember wtf eveything is, in this case dkLen = desired key length, c is cycles or itterations (but i gets used frequently on the fly hence the reason its not just i) P for password S for salt... making any sense? i could have named them a, b x and y but if theres a bug its easier to trace with easily understood variables, you'll have to take my word for that at this point but its good advice.
its also customary to give your variables default values just incase theyre used before expected and if that happens with no value in em then more often than not you will brick wall. this is what the = operator does, c=4096 just makes sure that 4096 gets stored in c (you can and will overwrite variables later but defaults help prevent bad things)
cout << "Password Based Key-Derivation function 2 (PBKDF2) with" << endl << "SHA-1 Hashing Algorithm. \n \n";
this tell the program to print to the screen, << (left shift opperator) means stream whatever is after it to what before it. ENDL means end line or go to the next line, \n does the same thing but its faster to type, i covered faster is better already, in other cout statements youll see variable names after the <<'s that just prints the contents of that variable to the screen capish?
cin.getline(P, 8192, '\n');
cin is console in, meaning read whats been typed and then store it in a variable, getline just means read the entire string (strings are just arrays of characters, the mean more than one letter or symbol, they will be the bane of your life, theres no "default" way to deal with strings in c/c++ and serve as the inspiration of many a flamewar) all this line does is store everything you spew at the keyboard into the character array P then terminate with a newline.
cin >> c;
far easier than strings, it just states to put the number written into variable c.
note in the effort of simplicity i never did any actual error handling so if you type "penis" here instead of a whole number then you will brick wall.
PBKDF2(P,S,c,dkLen);
this is yet another function thing. this just tells the compiler to use the values given in this function into that particular function for use later. its essentialy the glue of the code, these statements allow you to swap data around and do usefull stuff.
[i]for(int i=0; i<(dkLen/4); i++)
{
cout << hex << T[I];
}LOOPS'n'STUFF for is a loop command, note that it doesnt have a semicolon; that would be easy right? it would also be _you guessed it_ brick wall. simple rule if it uses braces it wont have use for a semicolon.
This just states to do everything proceeding it in the braces {} till the conditions in the parentheses () are met.
int i=0; this is just initialising a variable on the fly to use immediately.
i<(dkLen/4) this just makes the loop chec to see if i is less than dkLen divided by 4, it it is then it should do whatever is in the for loop and then:
i++ this is the "increment operator" that just means increase the value of i by 1 each time its run. -- also works but it decrements instead.
The actual loop just prints in HEX notation (values between 0 and F) the values contained in the T[] array.
The interesting part is the this means on the first time round it will print T[0] (arrays start at 0 by the way not 1, this leads to headaches at times) then it will check the loop again to see if i is still less than (dkLen/4) and if so will increase the value of i to 1 meaning it will then print T[1] then T[2] etc.
Loops are the only sane way to deal with getting data into and out of arrays and strings. you will rapidly either learn to love loops or learn to loathe strings and arrays.
[I]return 0; this means the program finishes without causing any harm and you can go about your day.
synopsis this function essenialy promps the user for information and stores that in variables, then it calls another function and passes it the values you just gave, it then prints the values contained in the string T[] to the screen (T[]'s values will be formed in another function) then gives the return type 0 to the OS telling it it finished in good order.
Thats programming in a nutshell, so you can forgive me for missing out a lot of the rest of the code and only highlighting specific details from now on (otherwise we really will be here for weeks)
Part 3 "PBKDF2 function"
Now down to the fun stuff, the actual workings.
This time we'll be dealing with the PBKDF2 algorithm.
As you know void means no usable return type to worry about and the stuff in parentheses just means actual values to manipulate for the rest of the function and program.
unsigned long L[5]={0,0,0,0,0}; The rest of the code surrounding this gemstone should be readily familiar at this point, this one here is just setting up an array on "the fly" you saw previously that you can spew stuff out of an array using a for loop, you can also put data in with a for loop too.
however you can also manualy input every value yourself by using parenthises and commas. all this means is set up an array called L with 5 values each one being 0.
l = (dkLen/hlen)+1;
Its all math from here on out, and some of it heavy at that, hopefully you'll be able to grasp whats going on at this point and things shouldnt look nearly as daunting.
all that does is assigns l the value of dkLen devided by 20 (then adds a 1 as a workaround to arrays starting at 0.
The previous comment is more for my benefit than anyone elses, ive not set up a "ceiling" meaning that values could overun their sizes if im not careful this causes variables to overrun and causes "brick wall" at worst, completely meaningless results at best.
for(int i=1; i<=l; i++)
{
t = 0;
U = S + t + t + t;
t = i;
U = U + t;
L[0] = L[1] = L[2] = L[3] = L[4] = 0;
for(int j=1; j<=c; j++)
{
HMAC(U,P);
L[0] = L[0]^H[0];
L[1] = L[1]^H[1];
L[2] = L[2]^H[2];
L[3] = L[3]^H[3];
L[4] = L[4]^H[4];
U = "";
for(int x=0; x<5; x++)
{
for(int y=0; y<4; y++)
{
t = ((H[x] >> 8*(3-y)) % 256);
U = U + t;
}
}
}
T[5*(i-1)] = L[0];
T[5*(i-1)+1] = L[1];
T[5*(i-1)+2] = L[2];
T[5*(i-1)+3] = L[3];
T[5*(i-1)+4] = L[4];
}
Nesting, we aint coverd that yet! nesting is placing a loop within a loop, the last loop has priority in that for(int y=0; >> 8*(3-y)) % 256); will need to complte its runs before the loop that initiated that can continue its next cycle. in this case y will do 5 runs (0,1,2,3,4) to every 1 cycle x completes, and x will complete 6 cycles to ever 1 j completes which will have to run its lot before i can loop again. all in all y will do its job a whole lot, numbering in several thousands here.
Every time the i loop runs it will reset the values of all those variables then assigns values to the T[]array with the values in the L[]array...
T[5*(i-10] = L[0] means place the value thats in L[0] into the position in the T[]array in this case its whaever i in the for loop is - 1 then times by 5 so on the first run it will wind up as T[0] second time around it will be T[5] then T[10] etc, with me so far?
back to arrays those numbers in the brackets[]? theyre not actual values, think of them more as positions. like i said an array is just a digital list, so think of a grocery list.
L[0] could be "peas" and below that is L[1] which is "cabbage" and so forth, the numbers just mark off the position on the list, they dont denote the actual values.
Now that the easy stuff is ironed out your probbably wondering wtf is the value in L[0] then? well thats worked out in the next loop L[0] = L[0]^H[0];
that is to say that L[0] has the value of L[0]^H[0] (H[0] refers to a position in memory thats specified later "H[0]=0x67452301;" to be exact)
^ denotes a "bitwise xor" that means that it compares the values stored in H[0]'s memory location and then XOR's that against the value already stored in L[0] and compares the binary results...
simply put an XOR means that it can be either a 1 in L and 0 in H or vice versa but if it winds up as a 1 in both or a 0 in both it will default to whichever value it was initialy.
You should by now be bleeding out your nose, or at least have lost partial vision. but thats ok. its juat moonspeak for swapping values around in a set sequence, like i said, it wasnt going to be easy to understand or translate to laymans terms.
Persevering on. the next loop further complicates things by placing a value in U = (U + t) where t is determined from the value of the remainder between H which is "bitshifted" to the right by 8 times the value of (3- however many loops y has done) so on the first loop it will be 8*(3-0) or 24places.
So for the first loop t = H[0] >> 24 % 256
% is the "modulus" operator... that gives the remainder of a devisor... yeah i know right?
Simply put 10 devided by 3 is 3 with a remainder of 1 yeah?
so the modulus or 10 % 3 is 1
This might appear to be fairly useless and pointless but its extremely usefull when transforming between numerical bases (binary is base 2, hex is 16 decimal is 10 etc)
By now you should be able to figure out that the function essentialy does a bunch of math governed by a set of rules on to the T[] array using otther stuff from other functions. you should also begin to grasp math operators used and be able to work out values if a gun barrel was placed next to your head.
That about wraps things up on the code front, reading through the rest theres not much else thats not already been explained, so things should become apparent just by reading whats going on. i figure at this point if there are any questions you can post away and i'll answer them.
So wtf use is that?
Back to reality... or as close an approximation as i can at this point
Well this is exactly what your router does with your passphrase albeit in a far more optimised form, ive tried my best to keep it simple, embeded deveopers dont have that luxury and need things to be fast and small and lightweight, this means that the code rapidly becomes a nightmare of obscure calls and features that would be impossable to fully wade through.
By now you should see the math thats involved in each step of the conversion process and this gives you a valuable insight into less than straightforward its going to be to reverse a PSK into a passphrase.
To be continued... cause its stupid oclock and my face hurts.
More coverage to follow, including tools, more on how the wpa psk standard works between devices and so forth.