June 25, 2011 at 07:20About WPA-PSK Hacking Algorithm
Good day, dear Habrosociety!
In this topic, I would like to consider some subtle issues related to attacks on Wi-Fi networks in the shared key mode WPA-PSK (more simply - WPA-PSK is a mode without a dedicated authentication server that most Wi-Fi users use, for example , when creating a computer-to-computer network connection).
On the vast expanses of the Internet you can find both a description of the methods of such an attack and download programs for its semi-automatic conduct (a vivid example of aircrack-ng ). But these programs, for the most part, are presented to the user as a kind of black box, which isgood if it works in accordance with the manual for its operation.
A recent article on Habré devoted to one of such programs, mentioning the use of rainbow tables (is this possible?) To accelerate the attack, and prompted me to write this topic. I hope the information turns out to be useful, since I have not seen any analogues on the network either in Russian or in the enemy languages.
The essence of the attack on the network in WPA-PSK mode is as follows: using the vulnerabilities of the user authentication protocol (namely, open data transfer), obtain some authorization data from the network, and then reproduce the authentication algorithm on the side of the attacker ( wiki on the topic, sorry, so long), substituting the intercepted traffic piece and password (the so-called shared key) as source data. The real password is not known to the attacker, therefore, passwords from a pre-prepared dictionary are selected sequentially as it. If “authentication of the user succeeds” when the authentication algorithm is played, then the password selected from the dictionary is true and the attack led to a successful network hacking. More information about the connection establishment algorithm (4-sided handshake) can be found in the original source .
Now let's go a little deeper into the jungle of the wonderful (or?) IEEE 802.11i standard and take a closer look at the 4-way handshake algorithm.
Based on the name of the mode ("... with a shared key") it is logical to assume that in the process of establishing a connection and further communication between the client and the access point, a certain “key” (trouble, trouble with native speech) scheme will be used, namely a set of keys, both temporary and static, used to encrypt traffic, verify message integrity, etc. Moreover, the agreement on the use of keys occurs precisely at the stage of a 4-sided handshake.
To reproduce the user authentication algorithm on the attacker's side, it is necessary to have information not only from the 4-way handshake packets, but also from the broadcast packets of the access point about the network organized by it (Access Point Beacon, the sign of such a packet is the sender's MAC address == MAC- access point address (bssid in the standard notification), the destination MAC address of the broadcast FF: FF: FF: FF: FF: FF). In particular, from such frames it is necessary to obtain the network name (essid in the standard notification).
Messages of 4 third-party handshakes (4 frames of the channel level) contain information fields of the following contents (I indicate only what is needed for the subsequent writing of the code that reproduces the attack algorithm, for details, see the standard):
Now briefly about the connection establishment algorithm - the access point and the client exchange the above data (but not only them), transmitting information in an open (unencrypted) form. At the same time, in order toeliminate the complication of conducting a man-in-the-middle attack, a message integrity check has been introduced (starting from the second frame!) By computing a hash-based message authorship function ( HMAC), according to its contents, using as a key not only a static key, i.e. a password (but actually a hash from it), but also random numbers anonce and snonce generated by the participants of the handshake at the time of establishing the connection (and they are also used hardware addresses). As a result, since both the client and the access point know each other's random numbers, and the password must be the same on them, message integrity keys will coincide on both sides. If during the transmission of 4 handshake frames 3 successful integrity checks are recorded (as well as the devices manage to agree on the supported operating modes), then the access point concludes that a valid client is connected.
As can be seen from the above description, no keys (neither password, nor temporary integrity check keys) are transmitted in clear form over the network.
A fair question arises - how can an attacker get the coveted key?
With a little thought in mind, a simple solution comes to mind - the algorithm is known, the input data, with the exception of the password itself, is also known. So what prevents us from calculating the integrity key of the message by choosing any random (well, maybe not completely random one, they still play their part, setting passwords to godgod, etc.) from the password on the shelf of the dictionary by Vladimir Ivanovich Dahl. Let us make a mistake several thousand (or millions) times, but sooner or later Fortune may smile atus with its Hollywood smile, and the calculated integrity key will coincide with the intercepted one. And this will mean only one thing (it’s true in connection with the avalanche effect of hashing functions) - the password used to create the network has been opened!
So, the last jerk. Whoever reads here will get candy right now.
The theory behind, ahead of practice. What is worth doing first? That's right, compute a set of keys. And it is quite small for WPA-PSK mode:
Let's start with point 1.
Actually 90% of the code is already behind. As you can see, all operations are simple, SHA-1 is used as a hashing algorithm , namely, its implementation, supplied in OpenSSL . The meaning of using not a password as a key, but a hash from it is twofold - on the one hand, this is a way to unify the key length (since the length of the password itself by the standard can vary from 8 to 63 ASCII characters), and on the other hand, introducing a computational complexity in the algorithm for generating the key scheme to avoid lightweight brute force attacks (these are two cycles of 4095 iterations in the code).
We proceed to step 2. Here we calculate the temporary key (the essence of the temporality is that two random numbers snonce and anonce, which are new each time the connection is established), are used in its calculation. The PTK key is used to calculate the integrity keys of the transmitted frames. In addition to the numbers snonce and anonce, the MAC addresses of the access point and the client, the sacramental phrase “Pairwise key expansion” (they come up with the same thing) and of course the highlight of the program are the PMK key. The need to generate a key of all these parameters makes it limited on time on the one hand (no rainbow tables will help now), on the other hand it is tied to specific equipment (a man-in-the-middle attack is complicated), and on the third hand, albeit indirectly but calculable,
The code is again elementary. First, in main, the pke array is formed, containing all the above parameters, and then 4-fold HMAC calculation. Although we will further be interested only in the first 16 bytes.
Actually the formation of a set of keys is completed. All that remains is to calculate using the PTK the integrity key for any of the frames of the 4-sided handshake (having previously zipped the mic field in it) and compare the result with the intercepted key. The function for calculating the integrity key mic is presented in the following piece of code. The various branches of the if statement correspond to the versions of the WPA and WPA2 data protection protocol.
An example of a working draft can be taken from here .
Obviously, to organize a full-fledged attack by brute force, it remains only to repeat the above algorithm for each password from the dictionary.
Analysis of the user authentication algorithm in WPA / WPA2-PSK allows us to draw the following conclusion: rainbow tables become irrelevant with this approach to calculating keys, and the speed of enumerating passwords from the dictionary comes to the fore.
But more about that next time ...
This topic was erupted from the depths of my subconscious only to increase the security of information transfer in wireless Wi-Fi networks. By publicly exposing the hacking methods used by negligent individuals, we help to increase the knowledge level of wide circles of users, and as the saying goes, “Alerted, then armed!”
In this topic, I would like to consider some subtle issues related to attacks on Wi-Fi networks in the shared key mode WPA-PSK (more simply - WPA-PSK is a mode without a dedicated authentication server that most Wi-Fi users use, for example , when creating a computer-to-computer network connection).
Why all this?
On the vast expanses of the Internet you can find both a description of the methods of such an attack and download programs for its semi-automatic conduct (a vivid example of aircrack-ng ). But these programs, for the most part, are presented to the user as a kind of black box, which is
A recent article on Habré devoted to one of such programs, mentioning the use of rainbow tables (is this possible?) To accelerate the attack, and prompted me to write this topic. I hope the information turns out to be useful, since I have not seen any analogues on the network either in Russian or in the enemy languages.
Attack, comrades!
The essence of the attack on the network in WPA-PSK mode is as follows: using the vulnerabilities of the user authentication protocol (namely, open data transfer), obtain some authorization data from the network, and then reproduce the authentication algorithm on the side of the attacker ( wiki on the topic, sorry, so long), substituting the intercepted traffic piece and password (the so-called shared key) as source data. The real password is not known to the attacker, therefore, passwords from a pre-prepared dictionary are selected sequentially as it. If “authentication of the user succeeds” when the authentication algorithm is played, then the password selected from the dictionary is true and the attack led to a successful network hacking. More information about the connection establishment algorithm (4-sided handshake) can be found in the original source .
The farther into the forest, the angrier the wolves
Now let's go a little deeper into the jungle of the wonderful (or?) IEEE 802.11i standard and take a closer look at the 4-way handshake algorithm.
Based on the name of the mode ("... with a shared key") it is logical to assume that in the process of establishing a connection and further communication between the client and the access point, a certain “key” (trouble, trouble with native speech) scheme will be used, namely a set of keys, both temporary and static, used to encrypt traffic, verify message integrity, etc. Moreover, the agreement on the use of keys occurs precisely at the stage of a 4-sided handshake.
To reproduce the user authentication algorithm on the attacker's side, it is necessary to have information not only from the 4-way handshake packets, but also from the broadcast packets of the access point about the network organized by it (Access Point Beacon, the sign of such a packet is the sender's MAC address == MAC- access point address (bssid in the standard notification), the destination MAC address of the broadcast FF: FF: FF: FF: FF: FF). In particular, from such frames it is necessary to obtain the network name (essid in the standard notification).
Messages of 4 third-party handshakes (4 frames of the channel level) contain information fields of the following contents (I indicate only what is needed for the subsequent writing of the code that reproduces the attack algorithm, for details, see the standard):
- Access Point MAC Address
- Client MAC Address
- random 32-byte number generated by the access point when establishing a connection (anonce) - frame I;
- random 32-byte number generated by the client (snonce) - frame II;
- size of the current authentication frame (without a channel header) - frame II or III or IV;
- the contents of the authentication frame (without a channel header) - always the same, the frame that is selected in the previous paragraph;
- message integrity key (mic) - always the same frame as that selected in the previous paragraph;
- version of the data protection protocol (WPA or WPA2) - frame II or III or IV.
Now briefly about the connection establishment algorithm - the access point and the client exchange the above data (but not only them), transmitting information in an open (unencrypted) form. At the same time, in order to
As can be seen from the above description, no keys (neither password, nor temporary integrity check keys) are transmitted in clear form over the network.
A fair question arises - how can an attacker get the coveted key?
Inside the black box
With a little thought in mind, a simple solution comes to mind - the algorithm is known, the input data, with the exception of the password itself, is also known. So what prevents us from calculating the integrity key of the message by choosing any random (well, maybe not completely random one, they still play their part, setting passwords to godgod, etc.) from the password on the shelf of the dictionary by Vladimir Ivanovich Dahl. Let us make a mistake several thousand (or millions) times, but sooner or later Fortune may smile at
Finally code
So, the last jerk. Whoever reads here will get candy right now.
The theory behind, ahead of practice. What is worth doing first? That's right, compute a set of keys. And it is quite small for WPA-PSK mode:
- PMK master key (password hashed multiple times using essid as the network name).
- PTK transfer key (using it, or rather part of it, the message integrity key is calculated).
Let's start with point 1.
void calc_pmk( char *key, char *essid_pre, uchar pmk[40] )
{
int i, j, slen;
uchar buffer[65];
char essid[33+4];
SHA_CTX ctx_ipad;
SHA_CTX ctx_opad;
SHA_CTX sha1_ctx;
memset(essid, 0, sizeof(essid));
memcpy(essid, essid_pre, strlen(essid_pre));
slen = strlen( essid ) + 4;
/* setup the inner and outer contexts */
memset( buffer, 0, sizeof( buffer ) );
strncpy( (char *) buffer, key, sizeof( buffer ) - 1 );
for( i = 0; i < 64; i++ )
buffer[i] ^= 0x36;
//SHA1_Init() initializes a SHA_CTX structure.
SHA1_Init( &ctx_ipad );
//SHA1_Update() can be called repeatedly with chunks of the message to be hashed (len bytes at data).
SHA1_Update( &ctx_ipad, buffer, 64 );
for( i = 0; i < 64; i++ )
buffer[i] ^= 0x6A;
SHA1_Init( &ctx_opad );
SHA1_Update( &ctx_opad, buffer, 64 );
/* iterate HMAC-SHA1 over itself 8192 times */
essid[slen - 1] = '\1';
HMAC(EVP_sha1(), (uchar *)key, strlen(key), (uchar*)essid, slen, pmk, NULL);
memcpy( buffer, pmk, 20 );
for( i = 1; i < 4096; i++ )
{
memcpy( &sha1_ctx, &ctx_ipad, sizeof( sha1_ctx ) );
SHA1_Update( &sha1_ctx, buffer, 20 );
//SHA1_Final() places the message digest in md, which must have space for SHA_DIGEST_LENGTH ==
//20 bytes of output, and erases the SHA_CTX
SHA1_Final( buffer, &sha1_ctx );
memcpy( &sha1_ctx, &ctx_opad, sizeof( sha1_ctx ) );
SHA1_Update( &sha1_ctx, buffer, 20 );
SHA1_Final( buffer, &sha1_ctx );
for( j = 0; j < 20; j++ )
pmk[j] ^= buffer[j];
}
essid[slen - 1] = '\2';
HMAC(EVP_sha1(), (uchar *)key, strlen(key), (uchar*)essid, slen, pmk+20, NULL);
memcpy( buffer, pmk + 20, 20 );
for( i = 1; i < 4096; i++ )
{
memcpy( &sha1_ctx, &ctx_ipad, sizeof( sha1_ctx ) );
SHA1_Update( &sha1_ctx, buffer, 20 );
SHA1_Final( buffer, &sha1_ctx );
memcpy( &sha1_ctx, &ctx_opad, sizeof( sha1_ctx ) );
SHA1_Update( &sha1_ctx, buffer, 20 );
SHA1_Final( buffer, &sha1_ctx );
for( j = 0; j < 20; j++ )
pmk[j + 20] ^= buffer[j];
}
}
Actually 90% of the code is already behind. As you can see, all operations are simple, SHA-1 is used as a hashing algorithm , namely, its implementation, supplied in OpenSSL . The meaning of using not a password as a key, but a hash from it is twofold - on the one hand, this is a way to unify the key length (since the length of the password itself by the standard can vary from 8 to 63 ASCII characters), and on the other hand, introducing a computational complexity in the algorithm for generating the key scheme to avoid lightweight brute force attacks (these are two cycles of 4095 iterations in the code).
We proceed to step 2. Here we calculate the temporary key (the essence of the temporality is that two random numbers snonce and anonce, which are new each time the connection is established), are used in its calculation. The PTK key is used to calculate the integrity keys of the transmitted frames. In addition to the numbers snonce and anonce, the MAC addresses of the access point and the client, the sacramental phrase “Pairwise key expansion” (they come up with the same thing) and of course the highlight of the program are the PMK key. The need to generate a key of all these parameters makes it limited on time on the one hand (no rainbow tables will help now), on the other hand it is tied to specific equipment (a man-in-the-middle attack is complicated), and on the third hand, albeit indirectly but calculable,
void calc_ptk( uchar *pmk, uchar pke[100], uchar *ptk )
{
/* compute the pairwise transient key*/
for (int i = 0; i < 4; i++)
{
pke[99] = i;
HMAC(EVP_sha1(), pmk, 32, pke, 100, ptk + i * 20, NULL);
}
}
void main()
{
uchar pmk[40]; //Используется первых 32 байта
uchar ptk[80];
uchar mic[20]; //Используется первых 16 байт
char *key = "12345678";
char essid_pre[32];
memset(essid_pre, 0, 32);
memcpy(essid_pre, "Harkonen", 8);
uchar bssid[6] = { 0x00, 0x14, 0x6c, 0x7e, 0x40, 0x80 };
uchar stmac[6] = { 0x00, 0x13, 0x46, 0xfe, 0x32, 0x0c };
uchar anonce[32] = { 0x22, 0x58, 0x54, 0xb0, 0x44, 0x4d, 0xe3, 0xaf,
0x06, 0xd1, 0x49, 0x2b, 0x85, 0x29, 0x84, 0xf0,
0x4c, 0xf6, 0x27, 0x4c, 0x0e, 0x32, 0x18, 0xb8,
0x68, 0x17, 0x56, 0x86, 0x4d, 0xb7, 0xa0, 0x55 };
uchar snonce[32] = { 0x59, 0x16, 0x8b, 0xc3, 0xa5, 0xdf, 0x18, 0xd7,
0x1e, 0xfb, 0x64, 0x23, 0xf3, 0x40, 0x08, 0x8d,
0xab, 0x9e, 0x1b, 0xa2, 0xbb, 0xc5, 0x86, 0x59,
0xe0, 0x7b, 0x37, 0x64, 0xb0, 0xde, 0x85, 0x70 };
uchar pke[100];
memset(pke, 0, 100);
memcpy( pke, "Pairwise key expansion", 23 );
if( memcmp( stmac, bssid, 6 ) < 0 ) {
memcpy( pke + 23, stmac, 6 );
memcpy( pke + 29, bssid, 6 );
} else {
memcpy( pke + 23, bssid, 6 );
memcpy( pke + 29, stmac, 6 );
}
if( memcmp( snonce, anonce, 32 ) < 0 ) {
memcpy( pke + 35, snonce, 32 );
memcpy( pke + 67, anonce, 32 );
} else {
memcpy( pke + 35, anonce, 32 );
memcpy( pke + 67, snonce, 32 );
}
calc_pmk( key, essid_pre, pmk );
calc_ptk( pmk, pke, ptk );
}The code is again elementary. First, in main, the pke array is formed, containing all the above parameters, and then 4-fold HMAC calculation. Although we will further be interested only in the first 16 bytes.
Actually the formation of a set of keys is completed. All that remains is to calculate using the PTK the integrity key for any of the frames of the 4-sided handshake (having previously zipped the mic field in it) and compare the result with the intercepted key. The function for calculating the integrity key mic is presented in the following piece of code. The various branches of the if statement correspond to the versions of the WPA and WPA2 data protection protocol.
void calc_mic( int wpaKeyVer, uchar *ptk, uchar *eapol, size_t eapolSize, uchar *mic )
{
if (wpaKeyVer == 1)
HMAC(EVP_md5(), ptk, 16, eapol, eapolSize, mic, NULL);
else
HMAC(EVP_sha1(), ptk, 16, eapol, eapolSize, mic, NULL);
}An example of a working draft can be taken from here .
Obviously, to organize a full-fledged attack by brute force, it remains only to repeat the above algorithm for each password from the dictionary.
Thinking out loud
Analysis of the user authentication algorithm in WPA / WPA2-PSK allows us to draw the following conclusion: rainbow tables become irrelevant with this approach to calculating keys, and the speed of enumerating passwords from the dictionary comes to the fore.
But more about that next time ...
Matches for children is not a toy
This topic was erupted from the depths of my subconscious only to increase the security of information transfer in wireless Wi-Fi networks. By publicly exposing the hacking methods used by negligent individuals, we help to increase the knowledge level of wide circles of users, and as the saying goes, “Alerted, then armed!”