Thoughts on 15 day CJ crypto

As most of you know, the SPA/NSA deal for auto-approved export
requires 512 bit RSA and 40 bit RC4.

Everyone knows that 40 bit RC4 is weak cryptographically, but no one
particularly thought that 512 bits RSA was -- weakening, maybe, but
not down in the real-time crack range.

I had an insight yesterday as to that particular requirement.
Consider the standard kind of way that one uses a hybrid crypto
system.  The secret session key is encrypted with the public key.
There are now two ciphers that can be broken.  And you only need to
break one of them.

So the NSA breaks 40-bit RC4 by brute force.  The keyspace is small.
What is left unsaid about the search is that candidate decryption keys
need to be selected.  You can't do a ciphertext only attack if the
plaintext is random bits.

The 512 bit RSA can be used to verify candidate keys.  Doing 2^40
modexp's is probably not how it's done (but it might be), but if you
can eliminate the bulk of candidate RC4 keys in some other way (by
looking at trial decryptions) then you've got a way of verifying the
rest of them.  If trial decryption can eliminate, say, one of every
hundred or thousand keys then the RSA verification could be done in
real time.

So it's possible the RSA requirement is in there to provide an
assurance that the right key was selected.

Eric

It is an interesting idea that the RSA actually helps with the RC4
decryption by letting them check a key guess.

This would suggest, though, that RC4 alone would not be allowed, only RC4
plus RSA.  If they allowed RC4 alone then unlimited-length RSA would not
seem any worse since with RC4 alone you don't get the key-checking
feature.

Also, are there restrictions on the encryption exponent?  A 1024 bit RSA
with a small encryption exponent would be faster to check than a 512 bit
RSA with an arbitrary 512 bit encryption exponent.  So if this were the
reason you might think they would put some restrictions on that.

Hal

From: Hal <hfinney@shell.portal.com>

   This would suggest, though, that RC4 alone would not be allowed, only RC4
   plus RSA.

Or perhaps RC4 at 32 bits.  All these restrictions are key length
dependent.  If you have a smaller search space, you can spend more
time examinining candidates.

   Also, are there restrictions on the encryption exponent?  A 1024 bit RSA
   with a small encryption exponent would be faster to check than a 512 bit
   RSA with an arbitrary 512 bit encryption exponent.  

These are public key operations, remember.  The public exponents are
usually only a few bits long anyway, no matter what the modulus.  

Eric

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

eric@remailer.net (Eric Hughes) writes:

>   From: Hal <hfinney@shell.portal.com>

>   Also, are there restrictions on the encryption exponent?  A 1024 bit RSA
>   with a small encryption exponent would be faster to check than a 512 bit
>   RSA with an arbitrary 512 bit encryption exponent.  

>These are public key operations, remember.  The public exponents are
>usually only a few bits long anyway, no matter what the modulus.  

That's what I mean.  "Usually" they are, but that helps a snooper to
check his guess.  Maybe it would be wise when using limited-length
session keys to use larger encryption exponents just to confound an
exhaustive search of the session key space.  I think it is surprising
if there is no limitation on encryption exponent size for these
exportable key systems, assuming that is the strategy the government is
using.

Hal

-----BEGIN PGP SIGNATURE-----
Version: 2.6

iQBVAwUBLvNQxRnMLJtOy9MBAQHXdAIAmvtcjZUXJF97vROjOFQK1DJ2jx44GhZq
CkmETSb8nmkzJhRVDYyQ7aZgWKSOril2MQsTRkJ59DyLKGZY7qQ6oQ==
=e06A
-----END PGP SIGNATURE-----

From: Hal <hfinney@shell.portal.com>

   Maybe it would be wise when using limited-length
   session keys to use larger encryption exponents just to confound an
   exhaustive search of the session key space.  

It would, but remember that you're generally going to be generating
those keys with the application that will be using them eventually.
One could write a spoofer, perhaps, to generate you're own keys, but
most people won't be using it.

   I think it is surprising
   if there is no limitation on encryption exponent size for these
   exportable key systems, assuming that is the strategy the government is
   using.

Consider the position from the viewpoint of the NSA.  Suppose that the
hypothesis is correct, and session keys encrypted with short exponents
are used to verify candidates.  You haven't told anybody this is the
reason for the particulars of the restrictions.

So, do you, the NSA, write the restriction into the regulation?  Or do
you rely on the fact that the developer will optimize public keys for
speed?

The first strategy reveals tactics.  The second carries some risk.

Eric