Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
109 lines (82 sloc) 6.2 KB
---
layout: post
date: 2013-03-08 00:00:00 UTC
title: WPA2 Key Generation Vulnerability: TP-Link
---

These days I have been playing with my new WLAN router, a TP-Link TD-W8970, and I have found a particularly interesting issue that affects other TP-Link routers as well. These routers can be recognized by the ESSID key TP-LINK_XXXXXX. Their default key for WPA/WPA2 and WEP is 10 and 13 characters in length respectively, apparently in range [0-9A-Z] and randomly generated by the EasySetupAssistant.

Based on this, the corresponding handshake of such a WPA/WPA2 key, bruteforced with typical GPU speeds of 20000 keys / second, would require 36^10 / 20000 seconds = 182807922003.1488 seconds = 5796.8011 years to be cracked. However, by disassembling the setup assistant, I realized this key is generated from a 32-bit seed by following a linear congruential generator reducing our key set from 36^10 keys to 2^32 keys. The reversed generator is:

chars = "2345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ"
def gen(seed, length): #length=10 in WPA/WPA2, length=13 in WEP 
    key = ""
    for i in range(length):
        seed = (seed * 0x343FD) + 0x269EC3
        key += chars[((seed >> 0x10) & 0x7FFF) % 0x28]
    return key

Furthermore, note how the for any length and 32-bit integer seed k following condition holds: gen(k, length) == gen(k + 0x80000000, length). This reduces the keys to check to 2^31. At the previously mentioned computing speed, this implies finding such a key in 231 / 20000 seconds = 1.24 days.

There is an additional issue affecting the seed generation that can help reducing the password dictionaries even more. These 32-bit seeds are not the result of a cryptographically secure PRNG. Instead they just represent a time difference, growing linearly at a rate of 1 every second as the system time passes. In Windows, the system time is obtained via GetSystemTimeAsFileTime from Kernel32.dll. The corresponding code to generate a seed at a given moment is:

import datetime
 
def genSeed(currentTime):
    dt = currentTime - datetime.datetime(1601, 1, 1, 0, 0, 0)
    t = dt.days*864000000000 + dt.seconds*10000000 + dt.microseconds*10
 
    tA = (t / 2**32 + 0xFE624E21)
    tB = (t % 2**32 + 0x2AC18000) % (1 << 32)
 
    if tA >= (1 << 32):
        tA += 1
        tA %= (1 << 32)
 
    r = (tA % 0x989680) * (2**32)
    r = ((r + tB) / 0x989680) % (2**32)
    return r
 
print genSeed(datetime.datetime.utcnow())

If we can estimate the time interval in which the router was installed, we can reduce the total seeds from 2^31 to the seeds that could be generated in that specific time interval. For instance, if we are confident that such a router was installed during 2012, we would only have to check the keys corresponding to seeds between 0x4EFFA3AD y 0x50E22700:

genSeed(datetime.datetime(2012, 1, 1, 0, 0, 0))  # 0x4EFFA3AD
genSeed(datetime.datetime(2013, 1, 1, 0, 0, 0))  # 0x50E22700

At the previously mentioned speed, we could potentially crack the password in a worst-case time of (0x50E22700 - 0x4EFFA3AD) / 20000 seconds = 26.35 minutes.

Since guessing the time in which the setup assistant configured the router can help us reduce the time required to find the key, we could improve our dictionary in the following ways:

  • Detecting the WLAN router series and model, if possible, and compare it with a database of release dates in order to discard any seed corresponding to dates in which the router was not on the market.
  • Discard any seeds corresponding to strange hours. For instance, it is pretty unlikely someone sets up their router at 2 AM and 6 AM.

Affected routers

I have verified all setup assistants distributed with TP-Link routers and all TL-WA, TL-WR, TL-WDR series and TD-WXXXX, TD-VGXXXX models are affected. In about 10% of these routers I wasn't able to download the EasySetupAssistant through the link TP-Link provided, but I am confident enough that the results of same routers of the series can be extrapolated to them.

The complete list of affected routers is:

  • TL-W8151N (V1, V3)
  • TL-WA730RE (V1, V2*)
  • TL-WA830RE (V1, V2*)
  • TL-WDR3500
  • TL-WDR3600
  • TL-WDR4300
  • TL-WR720N
  • TL-WR740N (V1, V2, V3, V4)
  • TL-WR741ND (V1, V2, V3*, V4)
  • TL-WR841N (V1*, V5, V7, V8)
  • TL-WR841ND (V3, V5, V7, V8*)
  • TL-WR842ND
  • TL-WR940N (V1, V2)
  • TL-WR941ND (V2, V3, V4, V5)
  • TL-WR1043N
  • TL-WR1043ND
  • TD-VG3511 (V1*)
  • TD-VG3631
  • TD-W8901N
  • TD-W8950ND
  • TD-W8951NB (V3*, V4, V5)
  • TD-W8951ND (V1, V3, V4, V5)
  • TD-W8960N (V1, V3, V4)
  • TD-W8961NB (V1, V2, V3*)
  • TD-W8961ND
  • TD-W8968
  • TD-W8970

Resources

Solutions

  • Do not use seeds at all. Feed the results of a cryptographically secure PRNG such as /dev/random or /dev/urandom in Unix-like sytems as indices of the character array modulo its length. This is for instance what the Linksys E4200 WLAN routers do, the indices of the key character array are provided by CryptGenRandom in Advapi32.dll.
  • If for some reason you want to use seeds for generating keys:
    • Make them bigger than 32-bit. Just 2^32 keys are easy to check.
    • Obtain them from a cryptographically secure PRNG.
    • If you still want to obtain them from the system time, use low granularity time intervals (e.g. elapsed time in nanoseconds rather than seconds) to minimize the number of bits an attacker can guess.