## Monday, July 6, 2015

### P vs. NP Problem

I was reading through an amusing article that I found while browsing my Twitter feed and stumbled upon a simple problem, and that is to programmatically (and efficiently) find two numbers whose product (multiplication) equals 119. The author states that we cannot use 1, or 119, and which means that we are dealing with a non-deterministic polynomial problem ("easy to verify, but hard to solve").

Well, why can't we make the solve part easy too?

Now, the author's explanation of the problem may not have been sufficient, as I know nothing about the P vs. NP problem, but I did instantly recognize something while reading it; it's actually a simply problem to tackle, if you know where to look!

The author then goes on to say "you probably have to go through all possible numbers from 2 to 118". <--- That line was the breaking point for my concentration. I thought that "there's no way you have to go through that many iterations for this application. That's absurd!" I instantly grabbed a pen and some paper and after a few minutes I was already typing out the C source code in a Vim which defies that. The way I did it was to take the tiny sequential steps and drop a lot of them and then make the remaining steps taller (so-to-speak).

## Dyslexia

We read our text here in the the US, from left to right. We read our numbers from right to left! Yeah, that's right, we evaluate the columns starting with the least significant column, (the ones column for integers)! Anyways, the least significant column is the one which holds the most clues about a number, obviously. For instance, numbers that end in 2, 4, 6, 8 are all divisible by two. Well, if the number given in the article was 118, we could have instantly said 2 * 29 and been done with it, since that's neither 1 nor 118. Also, if the least significant column is a 5 or 0, assuming there is a tens column value for the latter, they are both divisible by 5. Well, that leaves us with 1,3,7, and 9. But wait a minute, the author says we cannot use 1. So now we are down to 3, 7, and 9!

Well if the number is not divisible by those, we increment each by 10 (becoming 13, 17, and 19) and try again. We repeat this ONLY until we get halfway up the stair case. Yeah, that's right, I just dropped even more sequential steps (half of them) from the solution the author provided. Why I do this may be obvious. If we look at numbers that are divisible by other numbers, they are never divisible by numbers higher than half of their own value. For instance 1336 is divisible by 2 which equals 668. It has no factor larger than that. Same goes for 10. 10 is divisible by 1,2, and 5, but nothing above five.

## C Programming

So, how does this translate into an algorithm and source code? Well, I did it in C programming, but added a massive amount of comments on the way through the code. I also broke the source code up into functions without any global variables so that I could easily explain what each does here in this weblog.

The first function outside of `main()` is `void checkType(char *ct);` This function simply deduces what kind of mathematics will be used on the entire number. It gathers this information by simply using the least significant value, or value in the ones column. I use the modulo function in C after converting the input as an integer. This gathers the last digit into the integer symbol, `ictm`, named for "integer check type modulo". If `ictm` equals 5 or 0, or 2,4,6, or 8, we process it with the function `void processEasy(int ict,int even);`

This returns the value to the user and exits instantly. That means that we can instantly calculate any integer value whose least significant (ones place) value is 0,2,4,5,6 and 8. No (mathematical) verification needs done at all. That only leaves us with 1,3,7, and 9. So how many values are there that end with these four numbers "from 2 to 118" in the context of the article author's example? Well, 46 to be exact. I know this because I modified the code to output the number when sent into the `void processHard(int ict)` function that I made. This function is for handling odd (least significant) numbers that aren't 1,5, or 0. That's 46 out of 117. That means that I only have to mathematically verify about 39% of the numbers. That's not too shabby.

Well, I begin with three simple calculations, for modulo, `if(ict%3==0)`, `if(ict%7==0)`, and finally `if(ict%9==0)`. Well, guess what? The second calculation got his number, 119! That means I only performed 2 verification calculations for this sum! That's about 1.7% of his "from 2 to 118" method! Bingo? No bingo. No why? Because prime numbers, that's why.

Yeah, those damned things. Well, I compensated for that by letting the application go off into a `while()` loop into the `void processInsane(int ict);` function. This function is pretty cool because it performs a simple stack-oriented (pemdas-like) POSTFIX inline with the modulo function in C. There were 26 prime numbers between 2 and 118. That's only 26 calls to the heavy-lifting `void processInsane(int ict);` subroutine. 26 is 21% of 119. Not too shabby? That's just over one-fifth of the "verification" required for numbers 2-118.

~Douglas

## WEAKERTHAN Linux 6 BETA 2

As promised, WT6 BETA 2 is now available to the public! You can download a copy from my own personal server (80211.ninja) from the Weakerthan Page in this weblog.

 Screenshot of Weakerthan 6 BETA 2
 Weakerthan 6 BETA 1 screenshot

 Weakerthan BETA 1 screenshot
Please, if you test the ISO and have any suggestions, recommendations for features, etc, let me know! Email me, or reply directly to this post! Below are some features and development updates,
• Added VirtualBox Guest installation for drivers (click to drag to change screen  resolution!)
• Went a little top-heavy on the Reverse Engineering/Programmer setup (inspired by the work of ro0ted :) His/Her tutorials are awesome!
• Added Vim themes and customized the Vim Run-time for NASM/Assembly
• Customized my own Fluxbox theme, icons, wbar, and wallpapers
• Removed custom Linux (kernel) for ease of use for newcomers to Linux
• Compiled from source almost all penetration testing tools and debugging software
• Created my own UX/UI applications for Fluxbox
• Created my own Fluxbox menu and set Gnome-Terminal as preferred console - Also added functionality to change wallpaper directly from the Fluxbox menu
• Customized and updated all of my own penetration testing softwares including WARCARRIER, WifiCake-NG, and the pWeb web application penetration testing suite
These are mostly UX/UI customization and work. Also, please keep in mid when suggestion tools to be added, that with open source software a lot of preexisting tools may already do what you are looking for, just from a different perspective (the terminal) :)

I recently just hit 1,000 likes on Facebook! Be sure to click on the Facebook page link on the right sidebar! Thank you all, I love you!!!

## Penetration Testing with Perl

I was recently made aware that David Farrell from Perl Tricks is reading my book Penetration Testing with Perl, and writing the code as he goes along (while refactoring, and probably making it more readable). So, if you cannot afford the publisher's ridiculous prices, you can still download all the code from his GitHUB page! Thank you David!

## Introduction

Before we begin, let's take a look at how the process of WPA2 encryption works. I feel this is a very necessary step for this advanced subject. How could we possibly begin to write an application to crack wpa2 if we have no idea how the protocol/authentication methods work? Also, I would like to note that I do realize that this is incredibly absurd to use the system administration tool Perl to do this, since it is quite slow in comparison to C programming for these heavy lifting tasks (we will see why later), but it is still a good exercise to get familiar with the actual WPA2 cracking process for those already familiar with Perl.

## Requirements

A packet capture file containing a WPA2 4-way handshake, and a single beacon frame from the AP - This is for simply viewing the values using a binary to hex tool for network packets, such as Wireshark while coding your own tool with this article. I will be using Wireshark for a few examples and I also have prepared my own 4-way+1 beacon packet capture file that you can download here. To use the code that I write, you will need a few Perl modules:

## Terms Used

• Symmetric Key Algorithm or SKA - Cryptography method which uses identical keys to encrypt plain text data and decrypt cipher, or encrypted text.
• Pre-Shared Key - The key, or WPA2 password, used for the SKA process.
• EAP, or Extensible authentication Protocol - the actual protocol for transporting WPA2 encrypted data (not to be confused with other protocols, such as 802.11)
• Pairwise Master Key (PMK) - a string derived using the EAP framework which is used in the process of creating the PTK
• Pairwise Transient Key, or PTK -
• Message Integrity Code, or MIC - a checksum that is used to authenticate an encrypted message. It is often used as "MAC" for "Message Authentication Code" but since we already use MAC in computer communications to mean the hardware address of a radio, we use MIC.
• MAC Address - 6 byte, unique, network hardware address, e.g. "01:23:45:67:89:01".
• BSSID or Basic Service Set Identifier, MAC address of the AP radio.
• ESSID or Extended Service Set Identifier, Network name, e.g. "Free WiFi", or "linksys".
• Nonce - random number used for initiating an encrypted communication.
• "Station" - refers to a wireless client on the BSS.
• "AP" Access Point - refers to the actual wireless access point or router.
• Radio - used synonymously with WiFi adapter or Network Interface Card, or NIC for short.
• RFMON or Radio Frequency Monitor Mode - Passive listening to 802.11 traffic with a special driver for the radio.
• Handshake - an authentication process used by parties wishing to communicate using encryption to protect the transmitted data.

## Trolling for APs

If you analyze a packet capture file of 802.11 packets, you may see your client sending out "probe request" packets. These request packets are to stimulate nearby APs into sending out information such as the router/AP capabilities and name. The router's response will be a packet known as a "probe response." This is generally how all devices including our phones and tablets search for nearby WiFi access points. This type of "scanning," or "trolling" in the case of noisy-wardriving phones and tablets, for APs is sometimes referred to as "active scanning." it does not require a client radio to be in "monitor mode" or RFMON mode. If we have a radio whose driver supports RFMON, then we are able to "passively" scan for APs (and any other 802.11 traffic on any of the frequencies (one at a time, except when bleeding or overlapping naturally occurs) supported by the device). The most abundant frame is usually the beacon, which by default can be sent out of the AP around 10 times per second. This frame has all of the APs capability and identity information. Since in "passive" scanning the radio is only listening, not sending, these frames are easily acquired.

## Open System Authentication

When a client station wants to connect to an access point, e.g. when we select it in our supplicant software or tap on the network name on our phone screens to connect, it first goes through the process of authentication which is often open system authentication, or OSA. OSA is a four-way handshake style process that must be completed before we go further. This process has often been compared to simply plugging a device into a wired network, e.g. the actual action of pushing the Ethernet cable into the laptop and the network port or switch.

1. Station --> Authentication Request --> AP
2. AP --> Authentication Response --> Station.

Each one of these is a single unique 802.11 packet. This is where MAC address filtering is used. If the AP is set up to only allow certain MAC addresses of clients, which is a poor method of securing the network and should not be used alone, and the MAC address of the system or station which initiated the process is not in the AP's "white-list" the station is then rejected from the authentication process.

## System Association

To finally "associate" the station system with the network/AP the station initiates an association by sending the AP an "association request." The AP then updates a few tables, allocates resources (similar to starting up a program in a computer, the AP actually makes memory space for things for the station), and synchronizes with the station finishing the association process. This is, of course, if the AP accepts the station as a client. Below are the steps involved.

1. Station --> Association Request --> AP
2. AP --> Association Response --> Station.

## Pairwise Master Key (PMK)

The station already knows the PMK, or Pairwise Master Key value. This is pre-calculated by the station supplicant software using the following algorithm, `PBKDF2(SHA1,4096,SALT_LEN,OUTPUT_LEN)` where the SHA1 means that we are using the SHA1 cryptographic hash function. The number 4096 means that we are running the `PBKDF2()` function 4096 times for "key stretching" which makes the process of offline-brute-force cracking of the WPA2 passphrase that much harder. The SALT_LEN refers to the salt length of the encryption function, which is the length of the network name, since the network name, or ESSID, is used as the salt. The OUTPUT_LEN refers to the how long we want the output string to be in bytes. Here is an example PMK directly from the pages of my book, `9051BA43660CAEC7A909FBBE6B91E4685F1457B5A2E23660D728AFBD2C7ABFBA` Now that the station and the AP know the PMK, we can move on to the next step, the 4-way handshake.

## WPA2 4 Way Handshake

You may have heard of this "4-way handshake" process before, if you have ever used the Aircrack-NG suite of 802.11 penetration testing tools. This process starts with the AP creating a string, called an A-nonce, which stands for "AP Nonce." The animation below shows how to view the A-nonce in Wireshark using the capture packet file I offer in the beginning of this article.

Okay, let's get our hands dirty. This is going to be complicated so maybe we should use a writing pad and take some notes? :) The A-nonce is first sent to the Station by the AP. The Station uses the PMK to calculate the Pairwise Transient Key, or PTK. This is done using a Pseudo-Random Function, or PRF. The PRF loops over a simple integer variable, let's call it `\$i` for the time being (`i` is commonly used in `for()` loop examples), starting at `\$i = 0`, and stopping when `\$i == 3` - so four times total. During each loop, a new string is constructed by concatenating the hexadecimal byte value of the string "Pairwise key expansion \0\0" - which is

"5061697277697365206b657920657870616e73696f6e00"

and sometimes just referred to as PKE in technical documentation, both of the MAC addresses for the station radio and the AP radio, the A-nonce and the S-nonce, a zero "0", and finally

`\$i+``PKE+MAC0+MAC1+ANONCE+SNONCE+0+\$i+PKE+MAC0+MAC1+ANONCE+SNONCE+0+\$i+PKE+MAC0+MAC1+ANONCE+SNONCE+0+\$i+PKE+MAC0+MAC1+ANONCE+SNONCE+0+\$i`

The "Pairwise key expansion \0\0" string is actually part of the IEEE 802.11i-2004. It literally is a string with two null bytes at the end of it. We encoded it into hex by taking the case-sensitive ASCII values of each letter in decimal and calculating their individual hexadecimal values. For example, 80 is the ASCII (decimal) value for the capital "P" and 97 is the ASCII (decimal) value for "a" which are the first two letters of our string. So we first calculate the hexadecimal value for these two numbers, which in base 16 become, 50 and 61 respectively. Notice the first two bytes of the string, "5061697277697365206b657920657870616e73696f6e00", are 50 and 61? We do this for the entire string including the two null bytes at the end, which we simply denote using a single 0 for each.

To make this even more complex, the order in which all of these values are concatenated, matters! In the string above, we actually have to use the MAC address (station or AP) that is lowest in hexadecimal value first, and same goes for the nonce values. The nonce which is lowest in hexadecimal value first in our string as well. Before the string becomes part of the PTK, is is packed using the `pack()` Perl function and sent into the HMAC_SHA1() function along with the PMK string that acts as a "key." The value returned from the `HMAC_SHA()` function is then concatenated to an empty string, let's call it `\$ptkGen`. As `\$i` increments to 1, the process starts over and the final result of the new iteration is then appended to the value in `\$ptkGen` (itself). After all 4 iterations are complete, The PTK is then completely calculated as four concatenated strings into `\$ptkGen` by the station. (Well, not really, I am sure the AP doesn't use Perl. We do for this exercise). Next, the station sends the AP the S-nonce and the Message Integrity Check or MIC value. This MIC value is what we will finally use to crack the PSK. Below is an animation I made to show how to check an MIC in the 4-way handshake by hand using Wireshark.

Aircrack-NG and our Perl code only really needs two of the 4 packets in a four-way handshake. This is because the first two packets have both the A-Nonce and S-Nonce values in them AND the MIC. The second two packets also have the same information, just different values. We cannot, however, crack the key with just packets 2 and 4, or 1 and 3. The MIC is the "key" to our treasure, so to speak. This means that for each word in our dictionary file, we are going to go through this entire process over-and-over calculating a new PMK and PTK, hash the message body of the (captured) transmitted packet and check the MIC value. If the MIC value that we have calculated matches that in the 802.11 packet, then we have used the correct PSK in the process and thus know the secret password to the network. Heavy lifting for Perl! The message body can be obtained from the packet using the following line of Perl,

 `1` `\$msg = unpack("H*",substr(\$pkt,60,121)); `

This is the 60th to the 121st bytes in the packet using the packet's very first byte as an offset. We assign the message body to `\$msg`. The message is what we finally hash using the PTK to calculate the MIC.

First, need to take out the MIC from the message body. By "take out" we need to actually "zero-out" the MIC, and we do so with the Perl substitution operator with the following 2 lines,

```my \$pad = "0"x32; # 16 null bytes for padding
\$msg =~ s/\$mic/\$pad/i; # remove the WPA2 MIC value string
```

This is two lines of code, just so we don't have a single line with 55 "0" characters in length, not including the comment. We will, once again, be using the `HMAC_SHA1()` function from the `Digest::HMAC_SHA1` Perl module to check the MIC with our PTK. We do so by passing it the (packed up) value of the message body, `\$msg` and the first 32 bytes of the (packed up) PTK, `\$ptk` like so:

 `1` `my \$digest = hmac_sha1(pack("H*",\$msg),pack("H*",substr(unpack("H*",\$ptk),0,32))); `

Now, we check the sub-string of bytes 1 through 16 of the digest, `\$digest`, with that of the MIC, `\$mic`, like so: ```if(substr(unpack("H*",\$digest),1,16) eq substr(\$mic,1,16)){  print "PTK: ",unpack("H*",\$ptk),"\n";  print "\n\n\tKEY FOUND: [ ",\$psk," ] \n\n";  exit; # we are done }``` And that is all I did to create a simple brute-force tool, like (but not as efficient as the (oh the beautiful language of C <3 aircrack-ng.="" nbsp="" p="">
Below is the entire PoC that was used in my incredibly boring book, Penetration Testing with Perl. I have added lots of comments, and for those who have read all the way through this text (or simply understand how encrypted communication works), this should not resemble "write-only" code.

## Conclusion

This is a proof of concept. Stimulating and picking apart the 802.11 transactions with Wireshark is recommended and my WEAKERTHAN Linux distribution has all of the necessary tools to do so. By "stimulating," I simply mean, using Aircrack-NG's Aireplay-NG to de-autheticate a client causing it to re-authenticate using the 4-way handshake process described above. We do this because if we do, in fact, crack the PSK, or WPA2 passphrase, we can de-crypt the traffic using Wireshark- if and only if (to my knowledge at least) this 4-way handshake is in the packet trace.