WPA attack: details

Based on the topic of a hacked WPA .
Nevertheless, let’s try to figure out what happened and how this may threaten us. Since cryptographic attacks are a thing that requires a lot of specific knowledge to understand, the article can be considered somewhat familiar with the security in Wi-Fi networks.

Well, first you’ll have to go over the theory of Wi-Fi encryption protocols. Although impatient and those who are not interested in all this pseudo-scientific casuistry, it is not forbidden to immediately proceed to conclusion.

WEP


The WEP protocol is currently considered obsolete, not recommended for use at all in favor of WPA and WPA2. Still would! Its vulnerabilities are so serious that they allow to crack a key and connect to a secure network in minutes. How many of these very minutes will be needed depends on the intensity of traffic on the network; the average loaded network breaks down in one or two minutes (I am interested in this issue and refer to the article on the home page of the main hacker tool for wi-fi aircrack-ng ). WPA / WPA2 itself is, to some extent, an add-on to WEP, in the sense that the main packet format and encryption algorithm (for WPA) have not changed, i.e. there was no need to change the equipment, in most cases it was enough to update the firmware (it’s more correct to talk not about WPA / WPA2, but about the IEEE 802.11i standard; WPA is part of it, including the key management and encryption protocol TKIP, WPA2 fully implements the standard, including CCMP with AES encryption).

Since the packet formats for all protocols have much in common, we start with the WEP packet as the simplest:
We are most interested in the transmitted data (Network Data) in this packet

Here IV is the Initialization Vector, the salt needed to create the per-packet key. Data is actually the transmitted data generated by the upstream protocols in the OSI stack (for example, data can be an IP packet). IC (hereinafter we will call this field ICV - Integrity Check Value) is a CRC32 check-sum from Data, which serves to verify data integrity. Data + ICV are encrypted with the RC4 algorithm with the IV + WEP_key key, i.e. obtained by simple concatenation of IV and WEP password. Size IV - 24 bits, RC4 cipher uses keys of 64 or 128 bit length. This explains why WEP passwords are 5 or 13 characters long (i.e. 40 or 104 bits).

RC4 — это потоковый шифр. Инициализируется ключом, после чего выдает последовательность псевдослучайных битов с равномерным распределением, называемую keystream. Эта последовательность может быть использована для шифрования данных (традиционно называемых plaintext) путем операции XOR, получающаяся последовательность обычно называется ciphertext.

The main vulnerabilities of WEP are associated with a short IV length, a primitive algorithm for obtaining a per-packet key, vulnerabilities of the RC4 algorithm itself and its stream nature.


WPA



So, in this picture, what I previously called Network Data comes after the MAC Header (the FCS check sum is not shown here, as in the figure for WEP; we are not interested in it, because its processing is carried out at the lower level of the OSI model ) IV is the same 24-bit WEP Initialization Vector, only its meaning is somewhat different, the data structure of the package is much more complicated. To understand what the presented fields mean, we will consider briefly (but there is no time and energy completely, and I'm afraid to get bored :-)) the TKIP protocol, which I already mentioned:


TKIP (Temporal Key Integrity Protocol) реализует три подхода к улучшению безопасности радио-протоколов семейства IEEE 802.11. Во-первых, это функция смешения ключей, которая комбинирует секретный основной ключ PTK (см. ниже) с вектором инициализации перед тем, как передать его в качестве ключа алгоритму RC4. Во-вторых, это последовательный счетчик (TSC — TKIP Sequence Counter) 48-битной длины, значение которого растет с каждым переданным пакетом. Пакеты, полученные в неверном порядке, будут отвергнуты (а именно, будут отвергнуты пакеты с более ранним TSC), что позволяет защищаться от так называемых replay-атак. Наконец, это 64-битный код защиты сообщения MIC (Message Integrity Code).
TKIP реализует также механизм rekeying'а — смены сессионных ключей и гарантирует, что каждый пакет будет передан с уникальным RC4 ключом.

The basic session key PTK (Pairwise Transient Key) is a set of 4 128-bit keys used by TKIP to encrypt individual packets between key changes. Note that PTK is not a WEP password, and neither it nor the mechanism for generating it are part of TKIP.
There are 4 keys in PTK: one for encrypting data in TKIP (let's call it TK), one for computing MIC (and its MTK) and two more so-called EAPOL keys, which I will not touch. The keys are generated using the WPA password (finally, the password has appeared!), Known to both parties, during the four-step “handshake” ( picture , there is a rather detailed article in English about WPA).

Returning to the previous figure with the structure of the WPA package, we see that all that between the MAC Header and Data is essentially a TSC counter plus some service fields that protect against weak keys and indicate that Extended IV is being used. TSC is set to zero at the beginning of the session and monotonically increases with each packet transmitted by this device, a capacity of 48 bits is enough for ~ 250 trillion packets, which can be considered sufficient given the periodic reinitialization of session keys (as opposed to 24-bit IV in WEP). The unique key for encrypting the packet is calculated from TK, TA (Transmittor Address - MAC address of the transmitter) and TSC by means of a specific two-phase hashing mechanism, which gives the output a 104-bit string, to which WEP IV is added (yes, тот самый 24-битовый IV) для получения 128-битового ключа (на самом деле рисунок про формирование ключа наглядный, но неточный, дотошные могут взглянуть на this one ).

Uff ... what do we have left there? Oh yes, MIC.
It was created primarily to combat forgery packages. The code is calculated from the data of the entire message (plus the addresses of the transmitter and receiver) even before fragmentation and a possible change in the order of packets using an algorithm called MICHAEL, generating a signature of 64 bits in length. Along with data, the algorithm uses a key, namely, the aforementioned MTK. Importantly, the algorithm is in a sense reversible, i.e. knowing the data and MIC signature, you can calculate the MTK key.
The fight against forgery on the part of Access Point occurs, in fact, as follows: if a packet with an incorrect MIC arrives (while it is valid according to other indications, i.e., it has a valid TSC value and ICV, the amount has passed verification), then a notification is sent to the sender and, if there is a possibility, this event is recorded in the log as an attempt to hack. If within 60 seconds another packet arrives with the wrong MIC, the access point initiates rekeying with the given sender. T.O. fake packets with impunity (relatively) can be sent no more than once a minute.


Chop-chop attack


From the impressive list of attacks that WEP is vulnerable to, consider the so-called Chop-Chop attack (from the English chop, the free translation is “cut a slice”). This attack allows you to find out plaintext messages (i.e. message data before encryption), and therefore RC4 keystream packet (plaintext + keystream = ciphertext => keystream = ciphertext + plaintext). The attack takes advantage of the fact that the CRC32 check sum does not at all pass the cryptographic hash function according to the requirements.

Напомню, что идеологически CRC есть остаток от деления исходной строки S, представленной в виде многочлена (от X) с коэффициентами, равными соответствующим разрядам в ее двоичной записи, на предопределенный многочлен P CRC (X), причем арифметические операции выполняются в поле GF(2) (подробнee, например, в википедии ). Однако, в такой форме CRC нечувствителен к нулям в начале и в конце исходной строки, поэтому на практике в начало и конец дописываются специальные строки (длины, равной количеству разрядов CRC), которые обозначим как L i (начало) и L f (конец). Обычно обе они состоят из 32-х двоичных единиц. Таким образом, для CRC32:
CRC = (X 32 * S + L i * X n+32 + L f ) mod P CRC (1)
где n — длина S в битах.
Примечательно, что если к исходной строке S приписать справа ее CRC, то CRC от полученной строки будет постоянна и равна CRC пустой строки, которую обозначим за P zero (доказывается очень просто, достаточно помнить, что в GF(2) сложение и вычитание суть одна и та же операция — XOR), или в виде формулы
(X 32 * (X 32 * S + CRC) + L i * X n+64 + L f ) mod P CRC = P zero (2)


In the WEP packet, the last bytes of data (Network Data) are the encrypted ICV, i.e. CRC from the message. Let's forget about encryption for a while and consider what happens if we remove the last byte, which we denote as R, from the packet. Let Q be a packet without the last byte, then Q is unlikely to have the desired remainder (i.e., CRC). But it turns out that a certain polynomial M can be added to Q so as to correct the CRC. Substituting S O = Q * X 8 + R and then S 1 = Q + M in (2) , it is easy to find that
M = (X 32 ) -1 * (1 + (X 8 ) -1 ) * (P zero + L f ) + (X 8 ) -1 * R

Возвести многочлен P в -1ю степень означает найти такой многочлен P', что P * P' = 1 mod P CRC , что всегда возможно, т.к. P CRC неприводим и многочлены с операциями по модулю P CRC образуют поле. Кстати, степень М не превышает 32, т.к. M достаточно взять по модулю P CRC .

If we sort through all the R bytes from 0 to 255 and send them to the access point to the network, we will eventually come across the correct one. To understand that we hit the byte in reality is also easy: packets with the wrong ICV quietly drop as transmitted with an error; if the CRC is correct, we are entitled to expect a response packet, for example, in the case of WPA, it will usually be a packet informing of an invalid MIC. But more on that later.

But what about encryption? It turns out that the fact that the packet is encrypted does not matter, because RC4 encryption with the algorithm comes down to XOR-data with keystream, but adding M is the same XOR, and since the XOR operation is commutative and associative, it doesn’t matter if you add M to the original data and then encrypt it, or to already encrypted ones.

The described process can be repeated further, "biting off" a byte from the message, and theoretically it is possible to decrypt a WEP packet of arbitrary length.


WPA attack


Let us finally pass to the topic of the article.
So, what happens if you try to apply a Chop-Chop attack to a network with WPA protection?

TKIP has basically 2 means to protect against such attacks:
  • Packets with an invalid ICV, as I mentioned, are discarded. If the ICV is guessed, but the MIC code is incorrect, the attacker must withstand a minute so as not to provoke a key change
  • If a packet is received, the TSC counter for this channel (TSC counters exist separately for each channel to which this device can send packets; about channels a little later) is increased by 1. Packets with a smaller or equal TSC from this moment are discarded (again not quite precisely: in fact, there is a small window of TSC values, inside which packets are received, but not the point)

The first point is partially in the hand of the attacker, because allows you to understand when he guessed the next byte. The second is more complicated: indeed, even though we caught an ARP packet sent by one of the devices on the network, Access Point also caught it, sending the packet to it again is pointless, because the TSC is already incremented, plus the first device may have sent more packets, increasing the counter even more. The authors of this attack found a way out in the IEEE 802.11e specification, which defines improvements in QoS for Wi-Fi networks. The bottom line here is: Wi-Fi devices support several queues of packets (I named them channels above; what exactly do they relate to real radio channels, I can’t say), according to one of the authors, Eric Tuce, it was supposed to use 4 channels , in the standard there are 8, in reality, the authors found up to 16. Channels are typically not used simultaneously, saving bandwidth for important packets. In an unloaded network, often all traffic goes to one channel, i.e. we will most likely catch the packet on a channel with a high TSC counter value, but you can resend it by switching to a less loaded channel. It is important that, again referring to the authors, when sending a message about an incorrect MIC, the channel counter does not increase, i.e. further channels can not be switched.
If the network does not support QoS extensions, the attack, in principle, is also feasible if it is possible to prevent the packet selected for decryption from getting to the AP and disconnect the device that sent it from the network.

It is clear that trying to decrypt any long packets by byte per minute is pretty hopeless - the standard Wi-Fi packet is ~ 2300 bytes in size, i.e. it will take about a day and a half, and during this time, either the TSC counter will increase, or the keys will change, or the access point will be scrapped, or you will be “inflamed”. Moreover, having one device, you can break only one package.


Well, the sniffer will not work, let's see what decryption of short packets, for example, ARP, which can be easily identified by their length (14 bytes), can give us. Actually, the attacker knows most of the contents of the APR packet, namely, headers and MAC addresses. If you can also make some assumptions about the IP structure of the hacked network (in a network created from under Windows, for example, you can expect that IP addresses will be in the form 192.168.0.x), then nothing will be left to guess. That is, guessing 12 bytes of ICV + MIC, the rest can simply be selected using the ICV amount. Hence, the figure of 12 minutes for breaking mentioned in the press.

What next? Having decrypted one packet, the attacker recognizes the RC4-keystream packet (it is true, you can only use it until the TSC has changed) and, more importantly, the session MTK - I mentioned that MIC is reversible, and you can set the key from the data and signature. The latter means that before the next key change, there is no need to guess the MIC anymore, and, for example, it takes 4-5 minutes to crack the next ARP packet (with the same assumptions about the network structure). You can use decrypted data to send forged packets, depending on the number of QoS channels, from 7 to 15 times (less if traffic goes through more than one channel), then you will have to “chop-chop” another packet.


Conclusion: degree of threat and protective measures


If you recall the press reports before Tewes’s report, for example:

Erik Tews will show how he was able to crack WPA encryption… in a relatively short amount of time: 12 to 15 minutes… in order to read data being sent from a router to a laptop computer.
To pull off their trick, the researchers first discovered a way to trick a WPA router into sending them large amounts of data. This makes cracking the key easier, but this technique is also combined with a «mathematical breakthrough», that lets them crack WPA much more quickly than any previous attempt, Ruiu said.
www.pcworld.com

it is obvious that the paint "slightly" exaggerated - read traffic from the AP to the client in reality is impossible, and once it is unclear what kind of «mathematical breakthrough» a committed authors, for chop-chop attack is known already since 2004 ...
Despite the fact that there were statements about breaking the encryption, WPA passwords themselves and even temporary session keys (not counting the MIC key) are completely safe. Attack allows you to decrypt individual short packets with which work is carried out, spending at best 4-5 minutes per packet, and using the results of decryption, inject a very limited number of equally short packets back into the network. Yes, this is, apparently, the first serious attack that demonstrated the vulnerability of the TKIP protocol, but the majority cannot worry about this. According to Tuce: "if you used encryption only to protect your Internet channel from being used by random people, you are completely safe." An attack cannot be used to connect to a home or corporate network, or to monitor traffic in them.
However, minor dirty tricks theoretically You can do something like: “poison” the ARP (maybe DNS) cache, read some amount of private traffic, Tewse also points out the possibility of tricking some firewalls.

What methods can be used to deal with this type of attack?
Well, firstly, of course, you can just upgrade to WPA2 with AES encryption. The authors also advise reducing the key regeneration time by the access point (up to 2-3 minutes, which will make the procedures described above impossible in principle) and disabling the automatic sending of messages about the wrong MIC in the received packet. Unfortunately, it is unclear whether modern access points provide such subtle settings (personally, I don’t have a clue if someone had met, it would be interesting to know).

Well, you can hardly say that WPA is hacked. Moreover, I think that so far there is nothing to worry about. However, quoting one source, “now that the two (Beck and Hughes) have opened the door, the WPA is likely to attract the close attention of thousands of researchers: white, gray and black.”


Materials and links
Battered, but not broken (popular and accessible article about the attack)
Beck and Tuz
article WPA
article
Presentation (I used a couple of pictures in the article)
aircrack-ng A
good article about CRC and its hacking theory
An article about WEP hacking methods and FMS attack on Wikimedia
Disclaimer
Please do not judge strictly, I am not an expert on information security and wireless protocols, nor even an amateur, most of those interested :-) And I apologize in advance if I overloaded the article with theory and details.