12 March 2009

Embarrassingly parallel

Bruce Schneier, in his 'Crypto-gram' summary this month, has an outlink to a story in The Register on a purported desire of the US NSA to crack Skype's call crypto


But this misses the point -- the needed technology and infra-structure are out there already, fielded, and ready to go, pretty everywhere. Let's take a hypothetical country -- call it 'Glassware' ("US", "China" and "Elbonia" were taken)

The country of Glassware has a population of M * 10 ^ N people

Of those M * 10 ^ N people, the average family size is three, and there are an average of two cell phones and one television (the latest -- digital)

There is a broadcast infrastructure suitable to distributing portions of a problem sample -- say, the header block -- sufficiently long that one can detect when a 'good' private key has been found, which is sufficient to decode something encoded with an asymmetric encoding public key.

That target information is distributed over the airwaves, in the vertical blanking interval or sub-carrier side layer, itself encoded with a private key, readily decodeable with one of several 'factory included 'public keys'

The power supply switches in the television sets do not actually place the sets into a 'No power drawn' mode -- just into a lower power use 'sleep' stand-by mode. When tickled with the right signal, and not otherwise engaged in presenting content to possessors of that unit (who might complain about glitches if the video graphics display processor did not fully paint their screen), it is possible to wake them up to do some ciphering. Good for them -- recycles the electrons, and so forth

The television has a handy feature -- it will accept and display caller ID information from nearby affiliated cellular phones, over BlueTooth -- it can be configured to ONLY display wanted cell phones, but it will receive data and collate data from all ringing near it.

So when Mrs Glassware has her girlfriends over, and the babysitter calls during the home sales party, the TV will pop up an alert for them of the call over the din of the fun.

The TV also sends back, over SMS messages, duly encoded and encrypted, the logfiles to series of central collation points -- Father Glassware can see when the oldest son is over at the home of the girl from the wrong side of the tracks. The benefits are as broad as the imagination can see. Who could be against protecting the children?

Those cell phones as it turns out are really not using very much of all that processing power they have in THEIR 'CUDA chips to draw those dinky screens, and are really off most of the time as well.

Let's not waste their graphics processor chips as well, when they are on the charger. This is great, as it simplifies the math.

Perhaps Glassware have an even better infrastructure -- say a national conversion to High Definition digital media signaling, and a mature broadband or cable modem backbone. All the better for shuttling information around digitally.

A friend who deals with quants, tells me the quants are all hot and bothered to get 4 x quad head graphics cards in Dell Precision units -- 16 GPU's, because each of them can do a 10,000 (10 ^ 4) speedup over the simple general purpose processors in the underlying processors the chassis carry. All for under $10k a unit. They are doing the math and think they can have a huge HPC farm, just in the normal overhead which their traders and developers have to have anyway to do their day jobs.


M is 3 in the US (we'll round to 4 to make the math prettier), and perhaps 10 in China, and N is 8 (a hundred million). Feel free to pick a value for your local Glassware

So properly harnessed, we have at least: M * (10 ^ N) * (10 ^ 4) in compute engines available to us -- we should be able to crank out at least 100,000 samples a second ... 10 ^ 5, In cough numbers -- sufficiently accurate for our 'back of the envelope' purposes here, 10 is equal to 2 ^ 3. 2 is useful, as it is bits of key strength to solve. There are 8.6 * 10 ^ 4 seconds in a day -- call it 2 ^ 16

so: M * 2 ^ (3 + 3 + 3 + N + 4 + 5+ 16)

US: 2 ^ 43 key trials per day;
China: 2 ^ 44 key trials per day.

The old DES cipher had a 2 ^ 56 bit keyspace -- worst case time to solution is 2 ^ 13 days and always getting better as build out scales in, without even beginning to bear pre-processing tricks, One time pad reuse, identifying non-perfect implementations, planting known cribs, and the rest.

And it is Free, free, free -- or better yet, paid for by others. What was that old saw about people living in glass houses?