tags:

views:

153

answers:

2

So, I've been beating my head against the wall of this issue for several months now, partly because it's a side interest and partly because I suck at programming. I've searched and researched all across the web, but have not had any luck (except one small bit of success; see below), so I thought I might try asking the experts.

What I am trying to do is, as the title suggests, generate a 40/64 bit WEP key from a passphrase, according to the "de facto" standard. (A site such as http://www.powerdog.com/wepkey.cgi produces the expected outputs.) I have already written portions of the script that take inputs and write them to a file; one of the inputs would be the passphrase, sanitized to lower case.

For the longest time I had no idea what the defacto standard was, much less how to even go about implementing it. I finally stumbled across a paper (http://www.lava.net/~newsham/wlan/WEP_password_cracker.pdf) that sheds as much light as I've had yet on the issue (page 18 has the relevant bits). Apparently, the passphrase is "mapped to a 32-bit value with XOR," the result of which is then used as the seed for a "linear congruential PRNG (which one of the several PRNGs Python has would fit this description, I don't know), and then from that result several bits of the result are taken. I have no idea how to go about implementing this, since the description is rather vague.

What I need is help in writing the generator in Python, and also in understanding how exactly the key is generated. In other words, I need code to turn "jackson" into "09F38AF593". (And please don't tell me jackson = 09F38AF593; print (jackson))

I'm not much of a programmer, so explanations are appreciated as well.

(Yes, I know that WEP isn't secure.)

+1  A: 

I'm not sure what "de facto standard" that website is talking about, but I'm fairly sure router manufacturers all implement their own methods. It doesn't matter how you do it, as long as the same input always results in the same output; it's a convenience so WEP users can remember a passphrase instead of the actual hex key. Even the method in the PDF you posted is largely ambiguous; it uses an undefined PRNG (and every type of PRNG is going to give a different result), and takes "one byte" from each result without specifying which. If you're trying to reverse engineer a particular router's method, mention that in the post and we might be able to find out how that one works, but there isn't a standard method

Michael Mrozek
This website (http://www.netpoint.com/wep.htm) generates the expected result as well, and the JavaScript is exposed to view. I just don't know enough JS to understand it very well.An old post to a Linux mailing list has some C code that will generate what is necessary as well. (http://lists.linux-wlan.com/pipermail/linux-wlan-devel/2001-September/000597.html) Same problem with not knowing enough about code period to understand it.There does appear to be some sort of standard - Linksys, Netgear, Belkin, and DLink all use the same algorithms, to the best of my research's knowledge.
Aktariel
+2  A: 

That C code you linked to would have been awfully helpful to include in the question ;-) Anyway, I went ahead and translated it into Python. Before you read it, let me say that I highly encourage you to try it yourself and only use my transcription as a guide. Translating algorithms from one programming language to another is generally great practice when you want to boost your skills in one or both languages. Even if you don't know C, as long as you're familiar enough with Python to write programs in it, you should be able to get the gist of the C code, since there are many similarities.

Anyway, on to the code.

import itertools, operator

First, the pseudorandom number generator, which was identified in the presentation as a linear congruential generator. This type of PRNG is a general algorithm which can be "customized" by choosing specific values of a, c, and m (the variables mentioned in the Wikipedia article). Here is an implementation of a generic linear congruential generator:

def prng(x, a, c, m):
    while True:
        x = (a * x + c) % m
        yield x

(hopefully you could have come up with that on your own)

Now for the actual function:

def pass_to_key(passphrase):

The first step in the process is to hash (or "map") the passphrase provided to a 32-bit number. The WEP algorithm does this by creating a set of 4 bytes (thus 4*8=32 bits) which are initialized to zero.

    bits = [0,0,0,0]

It goes through the string and XORs each character with one of the bytes; specifically, character i is XOR'd into byte i % 4.

    for i, c in enumerate(passphrase):
        bits[i & 3] ^= ord(c)

These four bytes are then concatenated together, in order, to form a single 32-bit value. (Alternatively, I could have written the code to store them as a 32-bit number from the beginning)

    val = reduce(operator.__or__, (b << 8*i for (i,b) in enumerate(bits)))

This 32-bit value is used as the seed for a linear congruential generator with certain specific values which you can see in the code. How the original developer figured out these numbers, I have no idea.

    keys = []

The linear congruential generator can produce up to 32 bits of output at a time. (In C this is a limitation of the data type; in Python I had to artificially enforce it.) I need 20 bytes to generate 4 40-bit (5-byte) WEP keys, so I'll iterate the PRNG 20 times,

    for i, b in enumerate(itertools.islice(prng(val, 0x343fd, 0x269ec3, 1<<32), 20)):

and from each number, take only the 3rd byte from the right (bits 16-23):

        keys.append((b >> 16) & 0xff)

Why the third? Well, the bits at the high end (4th from the right) tend not to change much, and those at the low end can be predictable for many values of the PRNG constants.

Afterwards, all that's left is to print out the generated bytes in groups of 5.

    print ('%02x:%02x:%02x:%02x:%02x\n'*4) % tuple(keys)
David Zaslavsky
Thank you for showing me just how far I have to go in learning programming. (And thank you for the code and the explanations as well). One quick question, how would you go about mapping the new key values to a variable and then returning that, rather than just printing out the output?
Aktariel
@Aktariel: consider that an exercise for the reader ;-) Depending on how you want to do it, you might consider using the [`struct`](http://docs.python.org/library/struct.html) module.
David Zaslavsky