Re: Layman's explanation for limits on escrowed encryption ...

From:	IN%"unicorn@schloss.li"  "Black Unicorn" 24-MAY-1996 15:07:57.78
>On Wed, 22 May 1996, Ernest Hua wrote:

>> Could someone with some knowledge of NSA/DoS/FBI intentions please
>> explain why key length limitations are necessary for escrowed
>> encryption?

>To deal with the possibility that someone might slip through the cracks of
>the escrow process.

>Insurance.

	Hmm.... what were the normal key-length recommendations again? This
appears to imply that the NSA can break at least 64-bit, and probably 80-bit,
encryption. How does this translate into public key lengths? E.g., how many
normal bits is a 1024-bit PGP key equivalent to?
	-Allen

--Boundary..3941.1071713581.multipart/signed
Content-Type: text/plain
Content-Transfer-Encoding: 7bit

On Fri, 24 May 1996, E. ALLEN SMITH wrote:

> 	Hmm.... what were the normal key-length recommendations again? This
> appears to imply that the NSA can break at least 64-bit, and probably 80-bit,
> encryption. How does this translate into public key lengths? E.g., how many
> normal bits is a 1024-bit PGP key equivalent to?
> 	-Allen

The normal key-length recommendation was 96 bits.  64 bits and 80 bits are
equivalent to 512 bits and 768 bits respectively.  I would guess that a
1024-bit key is about as strong as an 96-bit key.  The first two numbers are
from _Applied Cryptography_; my estimate is an extrapolation from the data in
AC.

-- Mark

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
markm@voicenet.com              | finger -l for PGP key 0xe3bf2169
http://www.voicenet.com/~markm/ | d61734f2800486ae6f79bfeb70f95348
((2b) || !(2b))                 | Old key now used only for signatures
"The concept of normalcy is just a conspiracy of the majority" -me



--Boundary..3941.1071713581.multipart/signed
Content-Type: application/octet-stream; name="pgp00005.pgp"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="pgp00005.pgp"
Content-Description: "PGP signature"

LS0tLS1CRUdJTiBQR1AgTUVTU0FHRS0tLS0tClZlcnNpb246IDIuNi4zCgpp
UUNWQXdVQk1hcEwrTFpjK3N2NXNpdWxBUUdicHdRQW9QN1gwR0N2WmVHMUY1
MHV2NHhRa0dYYjBTSC9nRDZQCkxIUVBiK0RmZGF6RHNIaTdSdTdtYllSM3lV
Tytocm5SOHRqUWlBb01OLzhFZnUwSVNzSWNhR1Jla0Q0QnAwNHUKSkVQRlpv
Nkx6blV5RmoyM1hsSjdWaENqUW5STmxDYUFzbE1GSHg1RWVJL0dXZXZZQUJm
NHpEaHdDSmVONExwNQp2VDZMOU4yMTRHMD0KPXprUzgKLS0tLS1FTkQgUEdQ
IE1FU1NBR0UtLS0tLQo=
--Boundary..3941.1071713581.multipart/signed--

Mark M. <markm@voicenet.com> writes:
>  The normal key-length recommendation was 96 bits.  64 bits
>  and 80 bits are equivalent to 512 bits and 768 bits respectively.
>  I would guess that a 1024-bit key is about as strong as an
>  96-bit key.  The first two numbers are from _Applied
>  Cryptography_; my estimate is an extrapolation from the data
>  = in AC.

These number should be qualified with the date on which the estimate was  
determined.  New factoring techniques increase the number of RSA key bits  
required to make factoring work equivalent to a given brute-force search.

Also, I would think that the NFS makes 512 bit RSA key factoring easier than  
brute-forcing 64-bits of key space...


andrew

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

On Tue, 28 May 1996, Andrew Loewenstern wrote:

> Mark M. <markm@voicenet.com> writes:
> >  The normal key-length recommendation was 96 bits.  64 bits
> >  and 80 bits are equivalent to 512 bits and 768 bits respectively.
> >  I would guess that a 1024-bit key is about as strong as an
> >  96-bit key.  The first two numbers are from _Applied
> >  Cryptography_; my estimate is an extrapolation from the data
> >  = in AC.
> 
> These number should be qualified with the date on which the estimate was  
> determined.  New factoring techniques increase the number of RSA key bits  
> required to make factoring work equivalent to a given brute-force search.
> 
> Also, I would think that the NFS makes 512 bit RSA key factoring easier than  
> brute-forcing 64-bits of key space...

Quite true.  These estimates were made in 1995 so they are probably still
pretty accurate.  The rate at which factoring time decreases is greater than
the rate at which brute-force time decreases.  As to your claim that factoring
a 512 bit number is easier than bruting a 64-bit key space, it is not feasible
for anyone except maybe the NSA to do either of these.  I have heard that an
effort similar to that of factoring RSA 127 will be launched against a 512-
bit modulus.  I think that the difficulty is about equal to that of brute-
forcing a 64-bit key.

- -- Mark

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
markm@voicenet.com              | finger -l for PGP key 0xe3bf2169
http://www.voicenet.com/~markm/ | d61734f2800486ae6f79bfeb70f95348
((2b) || !(2b))                 | Old key now used only for signatures
"The concept of normalcy is just a conspiracy of the majority" -me


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQCVAwUBMatd7bZc+sv5siulAQHZZAP/eyguOKHDmfYtVEr7JVH0jxuTRVWdWDxJ
ICEuHrhKnF0xG3kaBirOMtvZjnga90cFRk++pEv/zbAS0qyEoizA1YxnKUQrqHn5
emuYf+lbm83fzBBOcKwdspoSg8W25TTtJIH2BX7JpNiyVzfco7DcHJOPxlDxspGZ
LgUf7G9L4vI=
=uO8h
-----END PGP SIGNATURE-----