Portable crypto code

One thing that frustrates me is the difficulty of easily providing
implementations of cryptographic algorithms that would be useful on a
wide range of machines.  A lot of these algorithms are really simple,
almost trivial.  Yet to write programs to implement them takes pages and
pages of code, and making them portable so that people on PC's, Mac's, and
Unix machines can use them is almost impossible.

Take the simple Chaum cash we have discussed here a few times.  The
user picks a random x and a random r, calculates r^3*f(x) where f is some
one-way function, and sends it to the bank.  The bank takes the cube root
and sends it back, then the user divides by r.  That's pretty simple.  Yet
to actually implement software to perform these steps raises a host of
complications.

First, we want to choose a "random" x and r in the range 0..m-1, where
m is the bank's public key modulus.  But we want these to be strong,
unguessable random numbers.  We need an unpredictable RNG,
and we need to seed it.  There are various URNG's that are provably as
strong as breaking factoring, discrete logarithms, and such, so these
would have to be implemented (as before, most are conceptually trivial).
Or you could run DES or IDEA in a feedback mode and take bits from there,
for a little less security but more speed.

For seeding the RNG you could do like PGP does and retain random numbers
from earlier runs, mixing in new randomness when feasible; you could do
like RIPEM and scan disk partitions hoping for randomness (I think RIPEM
has a lot of other ways of looking for entropy); you could use hardware
features like /dev/audio or the free-running, high-speed timers some PC's
have; you can get the user to click the mouse or type keys at random.

OK, we've got our random numbers.  Now we want a one-way function.  Again,
there are several choices: MD4 and MD5 from RSA; the Secure Hash Standard
NIST is pushing; Ralph Merkle's (I forget the name); others based on
conventional ciphers like DES or IDEA.  Implementations of these are
probably available, but portability is a question mark.

Now we need a multi-precision math package.  We may have needed one for
the URNG, too.  There are a lot of libraries available in source code
for these, but not many of them will work with 16-bit ints, and are
tested on DOS and Mac's as well as Unix.

Finally, to send the data around, we may want to convert to and from ASCII,
and once again there are a lot of choices, but perhaps not too many
portable libraries.  I suppose RFC1113 and MIME, which are similar but
not quite identical, would be the encodings of choice.

The point I'm getting to is that it would be nice if all this were done
ONCE, and a library made and tested which would work on a wide range
of machines.  Entry points for one-way functions, multi-precision
arithmetic, unpredictable random numbers, conventional encryption, and
ascii conversions could all be provided.  Multiple alternatives would be
supported as much as possible and it should not be difficult to add more
as time goes on.

Once you had such a library, it would be possible to add a user interface
to allow interactive use of the routines.  It could be as simple as the
Unix "bc" program where you can say "x = y*z" to do arithmetic, or perhaps
"x = md5(y)" to call a one-way function.  Or the library could perhaps be
linked into perl or some other high-level program (does mathematica have
hooks for compiled user code?).  The nice thing is that since most of the
compute time is spent doing the MP arithmetic in these algorithms, an
interpreted system which calls compiled libraries can be as efficient as
a purely compiled program.

I know that others here have made similar proposals in the past, but
I have not heard of many results.  I'd like to hear more about whether
these efforts have produced anything that could be incorporated.  It
would also be good to hear suggestions for specific existing packages that
would meet the portability requirements.  I've looked at a couple of MP
packages from ripem.msu.edu but so far I haven't had much luck running them
under DOS.

Perhaps a project like this could allow progress to be made more easily
toward cypherpunk goals.  By providing a toolkit to programers newly
interested in cryptography people will be able to try out ideas more
easily without having to re-invent the wheel each time.

Let me know if you would be interested in participating in this effort.
Hopefully a lot of the pieces already exist and it will just be a matter
of pulling them together.

Hal Finney
hfinney@shell.portal.com

> From: hfinney@shell.portal.com (Hal Finney)
> 
> One thing that frustrates me is the difficulty of easily providing
> implementations of cryptographic algorithms that would be useful on a
> wide range of machines.  [...]
> 
> The point I'm getting to is that it would be nice if all this were done
> ONCE, and a library made and tested which would work on a wide range
> of machines. 

Well, I do know of someone who is working on a cryptolib package that will
attempt to include a ton of crypto methods into a single library that
anyone can link to.  From email exchanged with this person it seems that he
is looking to get a unix version up and then let people port it around.
The math lib stuff is the most recent sticking point he was having: there
arenot many fast multi-precision math packages out there that are free (and
gmp does not cut it, he wants to be able to let anyone use the code however
they want...)  So far he has checked fgmp and bignum, but if anyone knows
of a fast package that has a berkelyish copyright let me know and I will
pass it on...

> Let me know if you would be interested in participating in this effort.
> Hopefully a lot of the pieces already exist and it will just be a matter
> of pulling them together.

Maybe I can set up a list for this if people are interested.  The existence
of such a beast, even in a rudimentary form, would be useful to quite a few
people I would bet.  I will push him a bit to see if he will dump what he
has now into a package so that others can help out.

jim

# One thing that frustrates me is the difficulty of easily providing
# implementations of cryptographic algorithms that would be useful on a
# wide range of machines.  A lot of these algorithms are really simple,
# almost trivial.  Yet to write programs to implement them takes pages and
# pages of code, and making them portable so that people on PC's, Mac's, and
# Unix machines can use them is almost impossible.

My experience has been much better.  I do have a TCL-based crytpo
tookit running, currently on SunOS, although some of the work (RSAREF
wrappers) I did on macintosh.  I think most of the pieces in this
list port to MAC or DOS, using ANSI_C+POSIX emulation:

	tcl7.0 (John Ousterhout's "Tool Control Language") sprite.berkeley.edu /pub/tcl
	gmp (gnu miltiple precision) prep.ai.mit.edu /pub/gnu
	gdbm (gnu database manager) /pub/gnu
	alo-des (by Antti Louko (alo@kampi.hut.fi)) kampi.hut.fi
	md2, 4, 5 (reference implementation) ftp.uu.net /inet/rfc/rfc{1319,1320,1321}
	tclRawTCP (TCP socket, listen, connect for TCL) harbor.ecn.purdue.edu
	RSAREF 1.1 (beta?) <rsaref-administrator@rsa.com>, 
			includes limited license to practice RSA & DH

Along with the tcl7.0 for MAC (for THINK6.*, altho in about 2 hrs
I got it running under THINK5.* as well) comes ANSI and enough-of-POSIX
libraries, sufficient to do most of what you need.

I assume ANSI and enough-of-POSIX are available for PC as well?
(I've never done programming on PC, so I can't speak from experience.)

And I assume assume we can find TCP (Berkeley Sockets functions) for MAC and PC.


This toolkit is sufficient to do most anything we've talked about.  I
want to supplement this with more stuff -- IDEA, UDP, cme's trans,
tripleDES, etc. -- but it already contains at least one implementation
of what you need to prototype almost anything we've talked about.

TCL is the trick.  Using this toolkit, I implemented Knapsack in about
2 hours (because it was my first one), El Gamel in half an hour, and a
DH-exchanged- DES-encrypted TCL-shell session over TCP in 2 hours.
Most anything becomes a one-evening job, except DC-nets, because it has
so many componenets....

I'm trying to shape this into a release.  This will have to be a
strictly-US-citizen-in-the-USA highly-controlled release, like
RSAREF and RIPEM are.  Sorry...


					strick

					"stricks write code"


p.s. perhaps someone could mail me the ftp path to the ITAR again...  thx