CryptoLib 1.0 now available

[Note! This is posted for Jack Lacy; please direct responses to him
at cryptolib@research.att.com.  -matt]

Announcing CryptoLib - Release 1.0		12/13/95
   Jack Lacy, AT&T Bell Labs

CryptoLib is a portable and efficient library of primitives
for building cryptographic applications.  It runs under most versions
of Unix as well as DOS, Windows and Windows-NT (and 95).

We are pleased to make CryptoLib source code available without charge
to researchers and developers in the US and Canada.  (Because of export
restrictions on cryptographic software, we are only able to make the
software available within the US and Canada to US and Canadian citizens
and US permanent residents.)

CryptoLib is intended for research and experimental use, and is
distributed without warranty or support.  In particular, please
note the following license conditions:

 *              Copyright (c) 1995 by AT&T.
 * Permission to use, copy, and modify this software without fee
 * is hereby granted, provided that this entire notice is included in
 * all copies of any software which is or includes a copy or
 * modification of this software and in all copies of the supporting
 * documentation for such software.
 *
 * This software may be subject to export controls.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.

The attached describes the library and some timing results.

To obtain source code send electronic mail to:

	cryptolib@research.att.com

with a statement of the following form:

	"I am a U.S. or Canadian citizen or a legal permanent resident of the
	U.S. and am aware that some parts of CryptoLib may be restricted under
	United States export regulations.  I have read and understand the
	CryptoLib license."

	Name:
	Location:
	E-mail:
	Are you licensed to use the RSA patent?
	   If yes, give name of licensed organization:
		
===============================================================================

CryptoLib includes the following:

	arbitrary length bignums.

	bigmath package:
		bigAdd, bigSubtract, bigMultiply, bgiDivide,
		bigLeftShift, bigRightShift,
		bigAnd, bigOr, bigXor, bigCopy,
		Euclid's extended GCD,
		modular reduction and exponentiation

	crypto primitives
		DES and 3DES + modes
		Diffie-Hellman
		DSA (Signing and verification roughly equally efficient)
		El Gamal
		Rabin's scheme
		Random Number generation (PSEUDO and TRUE)
		MD[2,4,5]
		Prime generation
		RSA (provided only if you convince me that you have a license)
		SHA
		truerand (For Unix, NT and 95)
		quantization (Defense against Kocher's timing attack)
		quantized RSA, DSA and El Gamal private key operations.
		
	support functions
		asn1.c
		ioutils.c
		netIface.c

Some timing information:

All times assume 32X32 bit assembly of multiplication primitives.

bigPow times (a^b mod c with a,b,c the same length)

		512 bits	1024 bits
		--------	---------
bigPow		0.12s		0.72s		Sparc II Brickell bigpow
		0.43s		3.0s		Sparc II with asm (gcc)
		0.12s		0.78s		Sparc 10 with asm
		0.03s		0.17s		Sparc 10 with asm (Brickell)
		0.084s		0.45s		SGI Indigo (150MHz)
		0.109s		0.75s		100 MHz Pentium (gcc under DOS)

Strong Prime Generation -- ProbTestAttempts = 5
100 primes generated in each test.  Times below are:
(total test time)/100 = avg. time per prime generated.
Using Gordon's strong prime algorithm.

    256		512	1024	Machine
    ---		---	----	-------
    2.8s	24.0s	5.11m	Sparc II 
    .45s	2.7s	77s	100 MHz pentium
	


	RSA Times (64 bit public exponent, message encrypted is full length)
	---------

		512	768	1024 bits	machine
		---	---	---------	-------
encrypt		30ms	50ms	80ms		sparc II
decrypt		160ms	480ms	930ms

encrypt		15ms	33ms	56ms		100 MHz Pentium (Under NT)
decrypt		38ms	104ms	214ms


	DSA Times
	---------

		512	768	1024 bits	machine
		---	---	---------	-------
sign		99ms	166ms	216ms		sparc II (Brickell speedup)
verify		156ms	316ms	416ms

sign		21ms	38ms	49ms		100 MHz Pentium (Under NT)
verify		27ms	43ms	71ms

> CryptoLib includes the following:
[...]
> 		quantization (Defense against Kocher's timing attack)
> 		quantized RSA, DSA and El Gamal private key operations.


Maybe this is an incorrect conclusion, but here seems to be a _second_ group
who knew about Kocher's timing attack before Kocher did. What on earth
would ECash or ATT have to gain by keeping such knowledge a secret? 

                                   -- Will

>
>> CryptoLib includes the following:
>[...]
>> 		quantization (Defense against Kocher's timing attack)
>> 		quantized RSA, DSA and El Gamal private key operations.
>
>
>Maybe this is an incorrect conclusion, but here seems to be a _second_ group
>who knew about Kocher's timing attack before Kocher did. What on earth
>would ECash or ATT have to gain by keeping such knowledge a secret? 
>
>                                   -- Will
>
>

Although it's very tempting to come up with an elaborate confession to
being part of the big conspiracy of the powers-that-be to suppress our
most brilliant cryptologic discoveries, I must admit that in fact you have
reached an incorrect conclusion.  I added the quantization stuff to
CryptoLib over the weekend right after I read Kocher's paper.  I posted the
routines to cypherpunks and sci.crypt yesterday.  You must have missed it.

Also, it should be pointed out that the idea that timing information
can leak information (like bit density) about keys has been well-known
for a long time.  I understand that NSA cryptosystems have long required
fixed response time for some (but not all...) cryptographic primitives in
comsec equipment.  But understanding that timing information might be
a threat in principle is not the same as understanding how to exploit it
in practice.

Kocher's observations are very, very surprising.

-matt