Joshua Oreman: 802.11 wireless development

Had a very long meeting with the mentors this morning. Things discussed:

• Encryption thoughts: use netX/key for the encryption key setting, to avoid interfering with the iSCSI password option set using NVO or DHCP. Use gPXE's existing AES implementation, and write the core RC4 code as a gPXE crypto-subsystem cipher instead of keeping it wireless-specific. Use end-user-understandable names (WEP, WPA, WPA2, as opposed to RC4, RC4/TKIP, AES/CCMP) for configuration options.
• Michael and I spent about two hours hashing out the correct behavior as related to my TCP fix. My patch did one thing wrong (ignored TCP sequence number wraparound) and one thing right by accident (returned early for duplicate ACKs, thus not stopping the retransmission timer and causing tcp_xmit() to do nothing). Michael corrected it and made its mode of operation clearer, and verified using artificially-duplicated frames on rtl8139 that it fixed the problem. He also pointed me to a Wikipedia article describing almost the exact issue: Sorcerer's Apprentice Syndrome. Because TCP does not automatically reply to ACKs, the problem on gPXE could only be caused by receiving two ACKs in a row for the same packet. In any event, it's fixed now, and should be in mainline soon.
• ROM size issues: rtl8185.rom is about 500 bytes shy of the effective 64k limit. It may be possible to use a bit more than 64k, with a 128k EEPROM, but total option ROM size is limited to 128k and we don't want to starve other devices that need ROM space (e.g. RAID cards). [Most wireless cards don't have Option ROMs, but it's possible to use the ROM socket on another card, such as a r8169 (64k space) or e1000 (128k space?).]
• Some interesting preliminary discussion about the possibility of loading part of gPXE as a module. If I do any work on this it'll be after encryption, and won't impact gPXE's current uses.

I did not get any coding done today to speak of; I worked rather fervently to get wireless done by the end of last week, and I needed some time to recharge. Encryption support will commence tomorrow.

WEP support is done and some of my supporting changes from early last week have been merged in. Current state-of-the-branches, in logical order of application:

• Merged in gPXE mainline:
  • [nvs] Add init function for Atmel 93C66 EEPROM (was 18e6470...)
  • [netdevice] Add netdev argument to link-layer push and pull handlers (was d429b31...)
  • [image] Modify imgfree command to accept an argument (was a9a0567...)
• Merged with significant modifications:
  • [tcp] Improve robustness in the presence of duplicated received packets and following commits
  • [netdevice] Add mechanism for reporting detailed link status codes (was 4602299...) [6/24]
• More merged: [6/24]
  • [ifmgmt] Move link-up status messages from autoboot() to iflinkwait() (was 30df822...)
  • [dhcp] Await link-up before starting DHCP (was 6d63a4a...)
  • [hci] Expose ifcommon_exec() in a local header so wireless commands can use it (was 22c261e...)
• The three big commits on mainline-review, needing updates against recent modifications by Michael and I: (as of 6/24, updated and ready for review)
  • [802.11] Add support for 802.11 devices with software MAC layer
  • [rtl818x] Add driver for Realtek 8180/8185 wireless cards
  • [iwmgmt] Add user-level 802.11 management commands and common error tables
• Patches to those three, based on discussion with Michael and bug-hunting: (as of 6/24, included in the above three)
  • [802.11] Automatically retry association if it fails
  • [iwmgmt] Remove iwassoc; do not display association error in iwstat
  • [802.11] Add measure of link quality based on received beacons
  • [iwmgmt] Print link quality in iwstat output
  • [802.11] Remove spurious assert()
  • [802.11] Properly handle return code of fetch_setting()

I will update the above list as things change this week. After we've decided what to do with the non-802.11 commits (up to “Make DHCP wait for link-up”), I'll reformat all the mainline-ready 802.11 code into three commits like the three I committed on Saturday, rebased off the then-current gPXE trunk.

• New encryption commits on branch wireless, not ready for mainline review yet:
  • [digest] Add generic CRC32 function
  • [cipher] Add the ARC4 stream cipher
  • [802.11] Add core support for encryption hooks
  • [802.11] Add support for WEP-protected networks
  • [802.11] Add errortab entry for the error returned by unsuccessful decryption
  • [config] Move linker massaging for 802.11 options to new file config_80211.o
  • [config] Add 802.11 encryption options to config/general.h

Encryption is looking like it will be at least reasonably elegant to support. Of course, WEP is the easiest of the three methods in use; WPA may well have me tearing out my hair by this time tomorrow The WEP code has been tested with hostapd and seems to work very well.

Spent all day researching the security protocols used in WPA-based setups. They're over an order of magnitude more complicated than WEP, taking up about 70 pages in the IEEE 802.11-2007 standard, with reference needed to 802.1X-2004 and various RFCs. The bits I will need to implement include:

• Algorithmic:
  • Generation of pairwise master key (PMK) from passphrase salted with SSID
  • Generation of pairwise transient key (PTK) from PMK and nonces
  • The Michael message integrity code for TKIP (WPA) frames
  • TKIP key mixing stages (the encryption is just ARC4)
  • CCMP (CTR [counter mode] with CBC-MAC [cipher-block chaining message authentication code] protocol, used in WPA2) encryption and encapsulation
  • NIST AES key wrap for 4-Way Handshake frames on CCMP networks
  • HMAC-MD5 and HMAC-SHA1, for 4-Way Handshake MIC [I think gPXE already has implementations of these]
• Protocol:
  • EAPOL decapsulation (packets of EtherType 0x888E with defined header format)
  • Processing of 4-Way Handshake contained in EAPOL frames
  • Processing of Group Key Handshake contained in EAPOL frames and rekeyed occasionally

I've got a busy week and a half ahead of me!

Earlier today Michael finished reviewing all the commits on my mainline-review branch except the three 802.11-specific ones; I've updated yesterday's commit list with the current state of things.

WPA is truly a horribly complicated beast. The more I learn about it, the more I realize I need to implement… ah well. I do feel as though I'm getting a handle on things, at least, and spent today working on ancillary code:

• [802.11] Detect secured networks properly, and find errors better
• [digest] Add HMAC-SHA1 based pseudorandom function and PBKDF2
• [eap] Add handlers for EAPOL decapsulation and EAP demultiplexing

Things I still need to do include implementing the 4-Way Handshake, generating the PTK, checking the Michael MIC, and the nuts-and-bolts methods of TKIP key mixing and CCMP encryption.

One thing I discovered today while browsing the Linux wpa_supplicant source code is that the RSN information element and 4-Way Handshake documented in the IEEE standard are not supported by many “WPA” devices that were shipped prior to the time IEEE 802.11i (the WPA amendment) was finalized. Instead, they use an information element under the “vendor-specific” heading with a different format, and a slightly different handshake as well. Judging by wpa_supplicant the old way seems to be simpler, but I haven't been able to find any documentation on it other than the source code. When I run hostapd in WPA1 mode, gPXE thinks it's WEP, so that's another thing I'll need to figure out and fix.

Most of the major bits of WPA have yet to be completed, but I've got enough ancillary stuff written that I think I should be able to dive in and have at least one WPA encryption scheme implemented by mid-next week. Commits:

• [802.11] Revamp RSN IE processing
• [802.11] Miscellaneous structural and API changes for encryption code
• [802.11] Start hashing out how WPA is going to work

The issue I noted in the last paragraph of yesterday's entry was not quite so bad as it seemed; after accounting for different header bytes and different version numbers, for gPXE's purposes the bulk of the WPA and RSN information elements can be parsed identically. Huzzah. The two versions still have some respective idiosyncracies in the handling of the 4-Way Handshake (which is next up on the list of things to write), but the wpa_supplicant code is a good reference for that.

I now offer an interlude of Cool Linker Tricks.

One of the things I did today was move all the helper functions that will only be needed when some encryption method is supported into a separate file, sec80211.c, so they don't bloat the code size in wireless builds that don't use encryption. There's one chink in that: the main wireless probe code needs to be able to differentiate fully between the various types of secured network even if they're not all supported, as WPA looks like WEP to a client that knows nothing about WPA. So net80211_probe_step() has to call sec80211_detect(), but we don't want that call to pull in sec80211.c if nothing else needs it.

Enter a very handy and underused linker feature: weak symbols!

Suppose you have a function, check_snazzy(), that needs to be called from the base.o module only if the module containing it, snazzy.o, is compiled in for another reason. It's a one-off, so using a linker table would be overkill; instead, you can do in snazzy.h

int check_snazzy() __attribute__ (( weak ));

In snazzy.c the function is defined as normal, without the weak attribute; it's only the external declaration that's weak, not the definition. But in base.c you can do

void check_things() {
        /* ... */
        if ( check_snazzy ) {
                int snazziness = check_snazzy();
                /* ... */
        } else {
                DBG ( "snazziness not enabled" );
        }
        /* ... */
}

If snazzy.o would not be pulled into the link by an ordinary (“strong”) symbol reference, a weak reference alone isn't going to be enough to pull it in. Instead, the linker defines snazzy.o's referenced weak symbols to be NULL pointers, and code that wants to conditionally use check_snazzy() just needs to test it against NULL before using it. While this example is obviously contrived, the technique can be very useful.

This is rather messy, of course; the fewer symbols with an implicit “might-be-NULL” attached the better. But for fairly tightly-coupled source files that need to be separated for size reasons, one or two weak functions can provide an excellent interface between the two.

While we're in the Cool Linker Tricks department, there's also something called a “weak alias”, which serves a completely different purpose: providing one implementation of an API function while allowing it to be superseded without complaint by another object file. I haven't seen anything in gPXE that really needs this, but to give an example of how it could be used, gPXE core defines a simple memcpy() function that doesn't know about any architecture-specific optimizations, but only declares its prototype if the preprocessor macro __HAVE_ARCH_MEMCPY hasn't been defined by architecture-specific includes; that allows architecture-specific string functions to be used instead, using either #define or an inline implementation, but no symbol can be named memcpy because the linker would complain. A way around that would be:

/* in core string code */
void * core_memcpy ( void *dest, const void *src, int len ) {
        /* ... */
}

void * memcpy ( void *dest, const void *src, int len )
        __attribute__ (( weak, alias ( "core_memcpy" ) ));

Then architecture-specific code could just define memcpy directly, no preprocessor tricks needed, and it would supersede the core version. Again, I don't think anything needs this at this point, but it's cool to know - maybe it'll even come in handy someday!