asymmetric encryption options

[snacktime]

Without going into too much detail, I've run into a roadblock using
rsa. I need to encrypt data that is larger than the key size. Right
now I am generating a random key, encrypting the data with it using
AES, then encrypting the key with rsa. Works, but I'd rather keep it
simpler if there is another asymmetric cipher I could use in place of
rsa. At most the data to be encrypted would be 10 times the key size.

Any ideas?

Chris

 

[Jan Svitok]

Without going into too much detail, I've run into a roadblock using
rsa. I need to encrypt data that is larger than the key size. Right
now I am generating a random key, encrypting the data with it using
AES, then encrypting the key with rsa. Works, but I'd rather keep it
simpler if there is another asymmetric cipher I could use in place of
rsa. At most the data to be encrypted would be 10 times the key size.

Any ideas?

Chris

1. You can try larger key, though I don't think it's a good idea.
Exponetiation algorithms are O(n**2) at best, possibly O(n**3). That
means, in the ideal case, that when you have 10x larger key, you'd
need 100x more multiplications.

2. You can split the longer key into blocks, and encrypt them alone.
If it is fast enough for you, then you're done.

3. If it is too slow, use the above mentioned combination of RSA&AES.
The tradeoff is slow RSA speed vs time of AES initialisation. In case
of relatively small number of blocks, AES might be slower.

4. For RSA+AES, I'd have a look at PKCS#1, either at the original
padding or OAEP. The original padding is really simple to implement,
and it'll save you some wheel reinventing. The newer one, OAEP, is
more complicated, but has some nice additional properties. You can use
standard pkcs tools to generate/test your data in this case as an
additional benefit.

5. For RSA only, I'd use some padding scheme as well, possibly based on PKCS.
I'd include block number somewhere to prevent reordering. You need to
make sure that the block doesn't produces a number larger than modulo
(in PKCS this is achived by adding 00 00 or 01 00 bytes in front of
the data).

6. You can try ElGamal [1] that allows you to precompute most of the
things berforehand, so it might be possible to use large keys. Even if
you choose the "random" parameters small enough, you might be able to
trade some security for some speed.

[1] http://en.wikipedia.org/wiki/ElGamal_encryption

HTH.

J.

 

[Dido Sevilla]

Without going into too much detail, I've run into a roadblock using
rsa. I need to encrypt data that is larger than the key size. Right
now I am generating a random key, encrypting the data with it using
AES, then encrypting the key with rsa. Works, but I'd rather keep it
simpler if there is another asymmetric cipher I could use in place of
rsa. At most the data to be encrypted would be 10 times the key size.

Well, ElGamal (basically a variation on Diffie-Hellman key agreement),
but then again having implemented both ElG and RSA on various
platforms myself I don't see ElG as being significantly simpler than
RSA (both still require modular exponentiation of large numbers).
What's the big problem with RSA?

 

[snacktime]

Well, ElGamal (basically a variation on Diffie-Hellman key agreement),
but then again having implemented both ElG and RSA on various
platforms myself I don't see ElG as being significantly simpler than
RSA (both still require modular exponentiation of large numbers).
What's the big problem with RSA?

The openssl implementation won't encrypt a block larger then the size
of the key. I think I will just stick with my current approach
though, as it seems to be the path of least resistance, and the
performance is acceptable.

 

[Francis Cianfrocca]

The openssl implementation won't encrypt a block larger then the size
of the key. I think I will just stick with my current approach
though, as it seems to be the path of least resistance, and the
performance is acceptable.

What you're doing is definitely the standard approach. Most people
would also throw in a digital signature of a digest of the message and
the key material.

 

[Dido Sevilla]

The openssl implementation won't encrypt a block larger then the size
of the key. I think I will just stick with my current approach
though, as it seems to be the path of least resistance, and the
performance is acceptable.

Well, a common problem with asymmetric ciphers is that they tend to be
problematic when encrypting large amounts of data. They often cause
data expansion and are extremely slow; I imagine that using an
asymmetric cipher to encrypt everything would result in your data
being at least twice the size of what you put in (whether you used RSA
or ElGamal), and I think that it would probably be even slower than
what you're doing now as well. It would probably also be prudent, as
Francis suggests, to add a digital signature to your data; I've found
that authentication of data is quite often more important than keeping
the data confidential.

 

[snacktime]

Well, a common problem with asymmetric ciphers is that they tend to be

problematic when encrypting large amounts of data. They often cause
data expansion and are extremely slow; I imagine that using an
asymmetric cipher to encrypt everything would result in your data
being at least twice the size of what you put in (whether you used RSA
or ElGamal), and I think that it would probably be even slower than
what you're doing now as well. It would probably also be prudent, as
Francis suggests, to add a digital signature to your data; I've found
that authentication of data is quite often more important than keeping
the data confidential.

What would be a good envelope to put all that in? I'm not sure what
ruby openssl supports, and my experience with this is somewhat
limited. In the past I've always used PKCS7. Performance is also an
issue, plus I have two types of data to store. One is short term with
a life of maybe a week at most, the other would be stored much longer
for auditing purposes. Plus the keys have to change every 90 days.

 

[Francis Cianfrocca]

What would be a good envelope to put all that in? I'm not sure what
ruby openssl supports, and my experience with this is somewhat
limited. In the past I've always used PKCS7. Performance is also an
issue, plus I have two types of data to store. One is short term with
a life of maybe a week at most, the other would be stored much longer
for auditing purposes. Plus the keys have to change every 90 days.

To decide on the storage container you have to ask how transportable
and how interoperable your encrypts need to be. If they're only going
to be consumed by your own applications or stored in your own
archives, then you can roll your own formats. If not, then you face a
documentation and support challenge whether you use a "standard" like
PKCS7 or not.

As far as performance is concerned, I think you've already taken the
most important step by using asymmetric crypto only for key material
and digests. I also strongly recommend you not use asymmetric keys
longer than 1024 bits, especially given that you will be re-keying
everything every 90 days. 2048-bit keys sound really attractive until
you see them running 10 to 100 times slower in software, or several
times more expensive in crypto-hardware!

Another critical performance factor, perhaps the dominant one if you
have to protect a lot of documents, is the quality of your
symmetric-key material. It's very time consuming on most ordinary
servers to generate high-quality randomness (although there are ways
to speed it up), and you really don't want to use pseudo-randomness.

A final consideration is the usage profile. I've generally found that
what you're proposing to do is most worth doing with documents of
medium-sensitivity that have medium-sized user communities. (A
canonical example I've often used is engineering documents for large
manufacturers, that have to be seen by perhaps 10,000 people.) With
smaller communities, the job is far easier. With highly-sensitive
data, it shouldn't be stored in computers in the first place ;-).

 

[snacktime]

To decide on the storage container you have to ask how transportable

and how interoperable your encrypts need to be. If they're only going
to be consumed by your own applications or stored in your own
archives, then you can roll your own formats. If not, then you face a
documentation and support challenge whether you use a "standard" like
PKCS7 or not.

The encrypted data is for our own applications only. We have used a
variety of methods but now that I'm tackling it again I'd like to
decide this once and for all. I doubt that I could brew up a
container any more efficient then just using PKCS7 via openssl, and
experience tells me that it's probably better to use a well known
standard. I'm not going to be the one maintaining the code in the
long run.