View Single Post
Old 11th February 2014
IdOp's Avatar
IdOp IdOp is offline
Too dumb for a smartphone
 
Join Date: May 2008
Location: twisting on the daemon's fork(2)
Posts: 1,027
Default

I'd like to subject the WPA passphrase part of my script to some needed criticism , as I realized it has a certain weakness, that I think is worth explaining.

The basic idea is that each input byte from /dev/[u]random, thought of as an integer in the domain {0, 1, ..., 255} is scaled into the desired output set { ASCII 32, ..., ASCII 126 }, which is a set of 95 values. (Actually, there is one less because I weed out the double quote " but let's ignore that, it just complicates the discussion.) The scaling idea was appealing to me, but since we're working with discrete sets, not real numbers, there can be problems.

So basically there's a map from 256 values into 95 values. If you think of such maps generally, many of them would be very bad. E.g., if the map was a constant, it would always give the same output, which wouldn't be random at all! The scaling map I used isn't nearly that bad; it does map onto the whole desired output range, in a many-to-one way. The problem is that the "many" is not the same for each output value though.

For example the map starts off like this:

Code:
input output
byte  ASCII
 0    32
 1    32
 2    32
 3    33
 4    33
 5    33
 6    34
 7    34
 8    34
 9    35
10    35
11    36
12    36
13    36
  ...
You can see output 35 has only two pre-images (inputs 9 and 10), while the others shown have three. If you look at the whole map, you find:

1 output has a single pre-image,
27 outputs have two pre-images,
67 outputs have three pre-images.

Note: 1 + 27 + 67 = 95 and 1*1 + 27*2 + 67*3 = 256.

What this means is that even if the inputs from /dev/[u]random are uniformly probable, the outputs are not. E.g., an output of ASCII 32 is 1.5 times as likely to occur as ASCII 35.

I don't think there is a way around this kind of problem if you want to keep all the inputs, because 95 just doesn't divide evenly into 256. You could get around it by throwing out some of the inputs so that the range is uniformly covered, say 2-to-1 everywhere. But this would have the cost of reading more bytes from /dev/[u]random, and in principle the process might never finish!

An alternative would be to restrict the size of the output set so it divides evenly into 256 (say, 64), and choose a map that covers it uniformly. But a smaller output set is a drawback too.

So, all in all, I think there are several reasons to prefer the WPA pre-shared key (PSK) method, which as far as I can see is done very cleanly by my script (criticisms also welcome!). They are:

1) Passphrase has the above problem (in my script). (Though perhaps I'm making a mountain out of a molehill?)

2) Passphrase is at most 63 characters anyway, which doesn't seem to contain as much randomness as a 64-byte PSK chosen with each byte totally random. The passphrase, if used, is mixed with the ESSID to create a PSK, but this probably doesn't help since the ESSID is public knowledge.

3) A good passphrase should be long, contain characters from a large set, and be very random. This means you won't be able to remember it! If you can't remember the passphrase, you might as well use a random PSK (which you can't remember either), since it's better. Either way you'll have to cut-and-paste it into your wireless setups.

Comments etc. also very welcome.

Last edited by IdOp; 11th February 2014 at 11:51 PM. Reason: spelling, and molehill
Reply With Quote