1993-09-17 - How to use cipher programs without trusting them.

Header Data

From: norm@netcom.com (Norman Hardy)
To: cypherpunks@toad.com
Message Hash: 6f64a672e22d95ce3f267b85678b7fa1be0b1463e422d750d0c5955e0d282323
Message ID: <9309170117.AA13564@netcom2.netcom.com>
Reply To: N/A
UTC Datetime: 1993-09-17 01:19:24 UTC
Raw Date: Thu, 16 Sep 93 18:19:24 PDT

Raw message

From: norm@netcom.com (Norman Hardy)
Date: Thu, 16 Sep 93 18:19:24 PDT
To: cypherpunks@toad.com
Subject: How to use cipher programs without trusting them.
Message-ID: <9309170117.AA13564@netcom2.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


The shortest summary of all this is that cipher program should be
deterministic and written to a public spec so that they may be checked
short of the hazardous task of reading code.
 
This may be quixotic but that has never stopped me. I propose here a way
to choose secret random numbers and random primes without having
to trust a single program exclusively. Suppose that you want to choose a
random n bit number. You type text while trying to make it random in some
subjective sense. The text accepts only space and letters and ignores all
else. The text is interpreted as a base 53 number and reduced modulo 2^n.
Note that 53 and 2^n are relatively prime. Experiments have shown that
this type of "typewriter random" produces about one or two bits of
information per character depending on the typist. This assumes an unspecified
form of information compression which I do not recall. It did, however,
look for patterns that were specific to people trying to type random
characters at a keyboard. One caution: if choosing random numbers this way
becomes routine one falls into habits that makes the numbers no longer
independent.
 
Different programs can easily be written according to such a standard and
their results compared. The skeptic runs two or three programs and
compares the output. After a few trials it may be reasonable to trust
one of the programs. A natural adjunct of such a program is a prime tester
that seeks primes in some arithmetic sequence. The sequence is chosen
according to published rules from keyboard selected random numbers.
 
I hear that PGP pads messages with random information in order to thwart
known plaintext attacks. This is wise but the paranoid wonders how
the random information is selected. The padding prevents output from two
programs from being compared for compliance.
 
Some will argue that if the cipher program were malicious it could stash
your secrets somewhere on your disk that was destined for export for
reasons unrelated to ciphering. The SoftPC story below indicates that
there are problems even when the cipher program is programmed to spec.
I know of operating systems where cipher programs may be installed so as
not to have the authority to stash your secrets away. I don't know
whether such operating systems will ever see commercial use.
 
There are several problems with keyboard timing. The first that I saw
mentioned arises when running such a program on SoftPC which is a clever
program to execute programs designed for IBM PCs on the Macintosh. The clock
appears not to run (I think the story is) and while the random numbers
look impressive they depend only on the number of keystrokes and nothing else!
There is much more technology such as SoftPC coming down the pike.





Thread