Joshua Oreman: 802.11 wireless development

Meeting notes from last Saturday:

• alloc_iob() should align to the smallest power of two greater than the allocation size, instead of the current constant of 2kb, to make sure allocations don't cross a page boundary for finicky cards. 802.11 packets can be larger than 2kb, so this is the first time it's come up.
• Discussed implementing a proper cryptographic RNG, possibly using the low-order bits of the TSC on timer interrupts; for now I've just stubbed the relevant function to use random().
• I'm going to try to get WPA1 with TKIP working by the middle of the week; hopefully WPA2 with CCMP by the end.
• I leave Sunday for the IPhO, so I want to get as much done as I can before that
• My loadable module idea was vastly overcomplicated; one can get the same effect just by chainloading another gPXE.
• It may be a good idea to either turn gPXE into a bzImage (it's currently a low-loaded zImage) or decrease the amount of heap/stack we give to zImages, as my test machine serves as an example of one whose EBDA goes all the way down to 0x98c00 and prevents loading zImage kernels using gPXE.

Commits:

• [802.11] Make wpa.h global, remove eapol_key.h
• [crypto] Add a placeholder for a proper random number generator
• [sha1] Parameter type cleanup
• [802.11] Extensions of core code to make WPA more readily supportable
• [802.11] Clarify some RSN definitions
• [eap] Try eap-identity setting before username
• [eapol] Properly free packet we now own, if callback fails
• [802.11] Implement WPA 4-Way Handshake and Group Key Handshake

The last one is the biggie; it represents about 3/4 of the work necessary to get WPA done. The rest is just in the routine to encrypt or decrypt an individual packet. (I also have to write the encryption and decryption functions for the key data in the 4-Way Handshake frames.) I'm going to try to get TKIP encryption coded tomorrow, so I can have Wednesday to test it. If all goes well, CCMP later in the week.

• [crypto] Add parentheses around len argument in blocksize assert
• [crypto] Add arc4_skip() to perform ARC4 skipping some keystream bytes
• [802.11] Make IE processing more robust
• [802.11] Pass initial RSC to sec80211_install()
• [wpa] Add replay detection, miscellaneous other fixes
• [wpa] Add PSK frontend and TKIP cryptosystem support

Theoretically, WPA support [for TKIP and PSK, which are the most common cipher and AKM used] is now complete! In practice it's probably got some serious bugs, but that's what testing tomorrow is for.

• [crypto] Properly provide last block of SHA1 PRF data
• [rtl818x] Keep device pointer for later cleanup
• [eapol] Record protocol field in network byte order
• [802.11] WPA bugfix potpourri

It works!

I was able to use gPXE's new WPA support to connect to an access point configured to use either WPA or WPA2-format packets, with TKIP as the cryptosystem. WPA2 also supports a more secure and complex cryptosystem called CCMP, based on AES; hopefully I'll be able to implement it by the end of the week.

WPA is quite a complex system, and I'm very glad I was able to get it to work. If you want to get an idea of the stuff it's managing, you can compile with DEBUG=net80211:3,sec80211:3,wpa:3,wpa_tkip:3,wpa_psk; since I used DBGC(), the result is rather psychedelic

No code today; I needed to get caught up with my physics preparation, and had some other issues to take care of. I did have an impromptu meeting with the mentors this morning, which Marty suggested upon Michael's statement that he couldn't make our usual Saturday time.

• Since I've completed (as of tomorrow) all the core wireless features I originally proposed, we discussed future plans.
• Drivers:
  • I'll write a driver for ath5k (Atheros non-802.11n cards); they're quite widespread and are one of the few chipsets in common use that don't require custom firmware, so ath5k gPXE could feasibly be burned to a (larger than normal) EEPROM.
  • JH suggested support for the various Intel wireless drivers, as they're used for the built-in wireless on Centrino laptops. These do require firmware, though.
  • A USB wireless driver would be handy, but a USB stack is a little out-of-scope for the time I've got left in the summer
• Since we're certainly going to wind up with some wireless drivers requiring firmware files, how do we handle the firmware?
  • It seems most straightforward to treat them like all the other binary blobs we deal with, as images. That way they can be embedded.
  • One could either use an embedded image for firmware, or supply it to a .lkrn-prefix gPXE as an initrd (using an eventual patch to support that). There would need to be some way of identifying it, and these files almost never have magic numbers. If we treat firmwares as embedded images always, we could add a field to the embedded image structure to override detected type, and have firmware-type never be autodetected. Another detection possibility is using file extensions; almost every firmware I've ever seen has an extension of .fw, .bin, or .ucode, with .fw being the most common. We could also wrap firmwares with a gPXE-specific header, but that's cumbersome.
  • If we go the embedded-image route, which seems likely, we can do things reasonably elegantly:
    • Extend the embedded image support to use a linker table, so multiple files can contain embedded images.
    • Have the gPXE build system treat everything in firmware/ with a non-.c extension as a vendor-supplied firmware, and make a .c file out of it in the same way as embedded.c is made using user-supplied embedded images.
    • Have each such autogenerated file also define a special symbol, along the lines of obj_XXX; maybe firmware_XXX where XXX is some identifier-ized version of the firmware filename.
    • Provide a function, get_firmware(), that can be called by a driver needing a firmware blob. If the blob exists (matching on filename) as a loaded image, it is unregistered from the image table, its image structure is freed keeping its data, and the userptr_t to the data is returned to the requesting driver. If the blob is not found, an error is returned.
    • Provide a macro, REQUIRE_FIRMWARE(), that works like REQUIRE_OBJECT() to pull the specified firmware file into the link by introducing a dependency on the firmware_XXX symbol. If the required firmware is not available, the link will fail. This would be used for drivers with freely distributable firmwares included with gPXE.
    • Provide a macro, USE_FIRMWARE(), to note a dependency on a certain firmware file without forcing it to be present for the link to succeed. There may be a way to use the linker for this, or it could define a symbol visible with nm and a script could add dependencies on those firmware_XXX symbols both requested and available. This would be used for drivers for which obtaining firmware requires jumping through some hoops (e.g. b43).
      • Update 7/3: After trawling linker documentation, I've found that the desired behavior can be effected using REQUIRE_FIRMWARE() plus a linker script that does PROVIDE(firmware_XXX = 0); for each firmware symbol that should not cause a link error if it is not present, but should still pull the firmware into the link if it is available. The easiest way to manage this is probably to require that each driver requiring non-included firmware place a linker script in fw/ with the PROVIDE() commands in it, and include all of those scripts in the link.
• Main wireless stack things:
  • WPA-Enterprise support might be useful.
• Not-quite-wireless things:
  • We need a proper cryptographic RNG. I could look into using the Yarrow algorithm or a similar one, with as much real entropy as we can get from low-order bits of the TSC during timer interrupts.

WPA2 is working!

• [crypto] Make AES context size and algorithm structure externally available
• [crypto] Add AES key-wrap mode (RFC 3394)
• [wpa] Remove KIE encrypt function, and allow decrypt to return an error
• [tkip] Make private functions static
• [wpa] Avoid recomputing Snonce during handshake + some minor tightening
• [wpa] Add support for CCMP encryption (AES-based, WPA2 default)

I was able to connect to a network that uses CCMP for unicast packets and TKIP for broadcast packets, and do DHCP (which uses broadcast) and chainload tomsrtbt (unicast) without any crypto errors. (The unicast/broadcast cipher split is fairly common, because the broadcast cipher has to be supported by every node, while a unicast cipher can be negotiated with each node separately.)

Before that, I discovered that writing a memory-processing loop like this:

for ( i = nblk; i >= 1; i++ ) {
        /* ... */
}

is a surefire road to a hair-pulling two-hour debugging session. Learn from my mistake, and don't write descending loops as ascending loops.

CCMP uses AES in two ways: in key-wrap mode (RFC 3394) to protect the group key in the 4-Way Handshake frames, and in counter mode with CBC-MAC (CCM; RFC 3610) to handle normal data packets. I implemented AES-wrap as a generic crypto function, since it is reasonably simple and does not have many tunable parameters; it doesn't have a crypto_algorithm structure, but that's just a matter of it being almost uniformly used for bite-sized chunks of data that are generally operated on in one piece. For CCM, I made the implementation private to WPA2 because that allowed me to make WPA2-specific size-saving assumptions about how it would be used. I kept the encryption and MACing code separate from the packet marshalling code, though, so if another use for CCM arises it should be fairly easily genericizable.

This will be my last coding work until July 20. In the meantime I will be preparing for and competing in the 2009 International Physics Olympiad in Merida, Mexico. Wish me luck!

After I get back: drivers drivers drivers…