NSA, Random Number Generation, Soviet Codes, Prohibition of Crypto

[Black Unicorn <unicorn@access.digex.net>]

-----BEGIN PGP SIGNED MESSAGE-----

** How a conservative learned to like NPR -


Listening to Public Radio this morning I caught a story about the 
NSA's recent release, or pending release of some 2000 - 2200 
documents bearing decoded Soviet communications.  These were the 
result of a long running communications and signals intelligence 
program conducted by the U.S., and thus, by the NSA and it's 
predecessors.  Some of the documents to be released include 
communications quite damaging to the Rosenbergs, who were executed 
for espionage and selling U.S. atomic "secrets" to the Soviets.  
This is, in fact, the key attraction in the documents.

More interesting than all this was the discussion with the deputy 
director of the NSA in which he described the communications 
collections program which continued from the 1950's all the way 
into the 1980's.  What interested me most, aside the fact that the 
NSA was speaking so candidly, and in my opinion foolishly so, 
about the program (even given their new public relations 
awareness) was a brief discussion of what methods were used in 
cracking the Soviet code.

While it was not defined specifically, it was suggested that the 
majority of the messages were communications between the embassies 
and Moscow.  As a result, the procedural and cryptologic algorithm 
was likely very entrenched as a method, and lacked variation 
because of the massive coordination required to switch methods in 
embassy to home country secure communications.  While I do not 
know how much was puffing, I suspect that it is safe to say that 
the basic method the Soviets were using looked something like 
this.

Plaintext -> Codebook number substitution pass -> One time pad 
pass.

The most difficult, and in the words of the deputy director, 
"remarkable" task was, of course, attacking the last layer in the 
encryption, and the first layer in the decryption process, the 
random series on the one time pad, which, in the words of the 
public spook, "was not so random after all."  The fixed codebook 
substitution perhaps had a high overhead in the initial 
computation, but once analyzed the first time the entire cipher is 
a wash until a new codebook or random number generation method is 
used.

** "Captain, the energy is structured in a pattern I have never 
     before encountered." -

So what does this little disclosure tell us about NSA 
capabilities?

Most obviously that they have extremely sophisticated "random" 
number analysis abilities.  1950-1980 is a long time to practice, 
and develop specialized hardware for this purpose.  The discussion 
of the value of specialized hardware gains having been applied on 
this list to RC4 analysis, its value is still somewhat of a 
mystery to me with reference to random number analysis.

In any event, it is safe to assume that the NSA has a very large 
section dedicated to this entire pursuit, and moreover, that the 
Soviets probably were not "petty" random number generators.  
Perhaps laziness got the best of them, but I am inclined to think 
they conducted this program, at least at first, like any other 
massive communist "for the glory of the state" program--  i.e., 
with crippling dedication.

To me this prompts the questions: How random is random, and how 
random is "cryptographically random?"

I don't know much about the mechanics of cryptographically strong 
random number generation, but considering the enormous effort the 
NSA has put into the analysis of same, I suspect it is in 
everyone's best interest to know more.

Consider:  Now that the NSA has gone public with the program one 
must believe this prima facie evidence that the program is no 
longer of use against the Soviets.  I suspect that a lot of 
dedicated hardware, already paid for, is probably sitting about 
looking for a use.  "Hey Louie Freeh, any idea what we can do with 
all this idle equipment?"

So for the cypherpunks, my first suggestion is a long look at 
exactly how strong the "cryptographically strong" random numbers 
might be.  Certainly we are not random number ignorant, but how 
random number savvy are we?

Perhaps someone with the equipment and the computer time might 
conduct a bit of an experiment.  Maybe lifting the random number 
generators from common cryptographic applications like CryptDisk 
Curve Encrypt, PGP, Secure Device, and taking a massive sample to 
identify trends in the "random" data might be a good idea.

Even those processes that employ some physical component might 
have some trends that could fall into patterns.  Even with hard 
hashes of random seeds, could seed patterns create patterns in the 
actual random data?  I must suspect so.

Perhaps a piece of code which could be distributed far and wide to 
'punks and others which might generate random data on different 
machines with different hardware and different users and generate 
an export file to be submitted to a Web Page or something.  We've 
seen the tremendous value Web Pages have in bringing users 
together to contribute processor time for the RC4 project, what 
about random number generation time?

One of the first attacks on short-wave radio "number stations" 
(for the uninitiated, most are based in South America and read off 
long sets of code numbers, usually in Spanish) was with the 
assumption that a one time pad had been used.  The result?  An 
analyst determined that the "random" numbers for several stations 
were one time padded with "random" poundings on an old typewriter.  
Even if not broken, this immediately identified several stations 
as related by the use of the same one time pad generation method 
(which is sensitive enough that unrelated stations are quite 
unlikely to have been privy to the method) and thus provided 
tremendous traffic analysis information.  What does our random 
data tell the world about us?

Could not the bits in PGP keystroke timing subroutines fall into a 
subtle pattern?  Enough of one to make someone's job a lot easier?  

When you whirl that mouse around the screen to generate random 
numbers for CryptDisk, do you start with a counter clockwise 
circle?  If you're right handed you're likely to.

In the scheme of things, these might be pretty good clues to 
someone who does nothing but random analysis all day long in a 
cubical with a frighteningly quick piece of specialized hardware 
in the next room.

** "He's in a tough position.  If he announces he's running,
     everything becomes a political move, if he announces he
     isn't, his administration becomes a lame duck effort.
     Perhaps he should say nothing" -

My estimation of the NSA's new public image, which amazed me at 
first, prompted me to suggest that the bulk of the hyper-sensitive 
work done there has already been moved to another outfit.  To go 
from "No Such Agency" to a politicized and highly public 
organization with a public relations department and press releases 
in just under 30 years is a dramatic change for a secret agency.

In many ways it is not a poor move.  The agency has grown quite 
large, and it has become impossible to hide.  In addition, the 
public is much more likely to be receptive to an agency which 
appears-- in public-- to have some worth.  Cryptography is a 
complex concept, enigmatic at best for the general public.  The 
public relates much better to the capture of spies and the foiling 
of the Soviet Union than to an agency which is too secret to 
acknowledge.

Public opinion tilting to the NSA might be a bad thing for 
Cypherpunks.  When the NSA says key forfeiture is required, the 
public is much more likely to swallow the pill from an agency that 
uncovers traitors, protects our national interest, and has a cool 
museum that you can visit to boot.

Mr. Young rightly pointed out on this list that part of the coin 
the intelligence community sells, the demand for which moves 
novels by the millions, is the feeling of inclusion in a select 
group, a shared secret.  How elegant the way the National 
Cryptological museum was opened.  No fanfare, no publicity, no 
invitations, just there to be discovered at first, like a little 
secret.  Stuck in an old motel, barely visible from Route 32, 
dwarfed by the massive NSA complex.  Talk about public relations 
coup.  Classic intelligence, release what is worthless or nearly 
worthless, create the impression it is rare, make cursory efforts 
to obscure it- efforts you know will eventually fail, and you have 
created something coveted.  Wait a while, and then when it has 
been discovered, uncovered, publicized, put out a brown and white 
sign:  "National Cryptologic Museum."  What does DeBeers do any 
differently?

So the NSA has become a political tool.  A mouthpiece, and in a 
subtle way, a propaganda machine.  (Just keep the lead counsel out 
of the public eye guys.  He keeps screwing things up.  Do a 
Stephenopolis or Hillary Clinton on him.  Time for him to go 
behind the scenes).

We've long been predicting the clash between crypto and 
government, I doubt government sees it much differently, though 
perhaps through the foggy lenses of a entity used to getting its 
way through coercion.  I suspect they are likely to do themselves 
major damage with simple hubris.

Still, the signs are out there.  They are more and more public 
every day.  I think cryptography scares the administration.  It 
certainly scares the FBI.

So I ask some of the same questions I asked here a few months ago.

Where are the stealth PGP hacks?
Where are the more subtle stego programs?
Why aren't there totally transparent strong crypto programs which
   don't advertise the recipient right in the header?
Why isn't crypto prepared to weather the storm of a outright ban?

Sure, fight on the side of keeping crypto legal, but prepare for 
the worst.

The fact that everyone and their mother drank didn't keep 
prohibition from being initially passed.  How is it people think 
it will be the sure fire crypto ban deterrent?

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBMAOxEi1onm9OaF05AQEi6Qf/ZW3qZln5SwPonJnf00OZM7DiPrjg/0+R
qzsgolAAnZIr/xFnNP99kzfLf393B5i/8CYO3V0m43VWI4T51b+sBs90Jkiin5hi
dals2aa/hCnMKvGfX1RjBo6OmiPmBhiwtvIOkn+tTda37YSWjYuBJ5DOZhXiuW6S
CUBxoDoE7yQmNy2BVZU9AKibpF3+Mv2k0yR9PlO0Yc0g8Z+juKR5xxUuMgqpy4HJ
qERDYZ6Cd+ADBt/YZGpoESBdishkKfZJeA+J9XApKbR8GiFgeT487ax1/P+Ph+eo
3kMcDEW4O87QbuXa3zewnNrxO306TO04jOeQp6GdJ00IQkRKeru0uw==
=6iZQ
-----END PGP SIGNATURE-----



00B9289C28DC0E55 nemo repente fuit turpissimus - potestas scientiae in usu est
E16D5378B81E1C96 quaere verum ad infinitum, loquitur sub rosa    -    wichtig!
*New Key Information*    -    Finger for key revocation and latest key update.