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
participants (2)
-
eric＠remailer.net -
Hal