Slashdot Mirror
Public-key Based Streamed Encryption?
Scott_F asks this thought provoking question: "Doing research on my thesis, I have come across many different encryption algorithms. The one thing I have not found is a public-key based stream encryption algorithm. Does one exist? If so, is it publicly available? If one does not exist, without going too far into the theory for the general readers' sake, is it viable? It should be from what I've found, but there may be circumstances that I've overlooked. Since it is stream encryption, there is no "look-ahead" so encryption can only be done a bit at a time. The algorithm could depend on the values of previous bits, but that would possibly leave those previous values with a weaker encryption. What would be desired would be a consistent security throughout the entire bit string. "
While the posters here are correct in saying that what you want is an ordinary stream cipher like Panama using keys generated by a public-key algorithm like Diffie-Hellman (remember to autenticate the peer, kids!), there *is* a stream cipher that can be used directly as a public-key algorithm. It's not sensible for bulk use, but it has some nice properties as a public key system.
Look up "probabilistic encryption" in Applied Cryptography. This system uses a neat property of the Blum-Blum-Shub CPRNG: you can run the generator *backwards* from the final state to the inital state *if and only if* you know the primes P and Q used to set up the generator. To run the generator forwards, of course, you need only their product N = P * Q. So to use this scheme, initialise the generator in a random state, encrypt a short message (must be short: BBS is not fast!) by XORring the message with random bits from the generator, then append the final state of the generator. Only the intended recipient, who knows P and Q, can then figure out the initial state and decrypt the message.
OK, it's not what you wanted, but it's neat, isn't it?
--
Xenu loves you!
Add to the above the consideration that the bignum ciphers tend to be less secure than their "block-oriented" brethren, so that whilst (for instance) IDEA is considered pretty secure with 128 bits of key, RSA requires 1024 bits (or more) to provide similar secureness. This "bloating" of key sizes magnifies the differences in relative efficiency further, thus making it even less sensible to use RSA (or DH, or the "Lucas" variant, or ...) as alternatives to the private key ciphers.
But on top of all that, which is a mouthful, you're not talking about block ciphers, but rather stream ciphers, which are a different class still, as they encrypt byte-by-byte, that doubtless magnify the inefficiencies of the public key encryption bignum math further.
If you're not part of the solution, you're part of the precipitate.
Remember stream ciphers != block ciphers.
RC4 and SEAL are notable stream ciphers; the usual distinction between a stream cipher and a block cipher is that block ciphers work with "blocks" (or "packets") of material, whereas stream ciphers work with far smaller "blocks," commonly a single word or byte. The pathological example of a stream cipher should encrypt bit-by-bit; on computers with word sizes of 32 bits, it would make considerable sense to treat a 32 bit word as the "atomic unit" being encrypted.
Whether the "atom" is a bit, byte, or word, the critical issue is that the unit of encryption is liable to be a whole lot smaller than the 56 bytes one might have in an Ethernet packet...
If you're not part of the solution, you're part of the precipitate.
One reason may be latency. If your data link rate is R bits per second and you gather N bits for encryption, you are introducing N * R seconds of latency. If you can clock out individual bits as they come in, you reduce the latency.
Another reason may be the saving of space. Think of remote login connections. The user types one character at a time. But most block ciphers operate on at least eight bytes at a time. It would be wasteful to send eight bytes for one keystroke (assuming we ignore the sad fact that over TCP, each keystroke already turns to 41 bytes; Nagle helps with this, but only if you type faster than the network delay. Some programs, notably SSH disable Nagle). In any case, by using a stream cipher, or a block cipher operated as a stream cipher (for example, using CFB mode) you can shift out one byte for each keystroke down to the transport layer or datalink or what have you.
Public key encryption is very slow (for all operations) so it is never used for bulk encryption. Instead, what you need to do is use a very fast secret key stream encryption algorithm (such as RC4) to do your actual data transfer and use the public key system to transfer the keys. It works like this with client A and server B:
:)
A: generate a random, unguessable secret session key.
A: obtain B's public key
A: encrypt your secret key with B's public key
A: send the encrypted key to B
A: initialize the stream cipher with the session key
B: decrypt the encrypted key with my private key
B: initialize the cipher with the decrypted session key
A and B: begin data transfer.
Now, as far as feasability of using a public key system for stream transfer.. it's certainly possible but only in output feedback mode with a rather large block size. Also, it will be slow as to be useless. Your only other option is to invent a very fast public key cryptosystem... I wish you luck
By the way, the protocol I described above is very similar to what SSL and PGP use. The technical documents on those protocols would be good reading along with "Applied Cryptography" by Bruce Schnier
If I understand this correctly, you want to use public key cryptography to encrypt a stream of data, instead of the more traditional method of using public key cryptography for secure transmission of a session key.
In order to use public key cryptography for a stream of data, you have to worry about two things.
First, public key cryptography is slow. If you want a secure bit length, you'll need a fairly slow stream or very fast hardware.
Second, public key cryptography works with relatively large blocks of data at a time. You either have to encrypt on a packet-basis (I suspect your packet size will need to be a multiple of the key bit-length, though independent of the network packet size), or you have to pad out the data.
You can't do something funny with using previous data and still have the encrypted steam the same size as the input stream. The problem with that is the encrypted output for a block is based on the entire block--to reconstruct a single bit of the plaintext, you need the entire cyphertext. You can't pick a few bits of the cypertext, even if you know most of the bits of the plaintext.
One reason that people use stream ciphers is often a speed factor-- it's much faster to simply XOR the data stream with the keystream from a stream cipher than it is to actually involve the plaintext in the permutation. This is especially true if you implement the stream cipher on, say, a separate chip.
Given the fact that public-key ciphers are generally slower than symmetric ciphers, the main reason to use a stream cipher is pretty much defeated. Why not just use a pulic-key cryptosystem to send the key, then send the rest of the message encrypted with a conventional stream cipher?
Also, cryptologists prefer to work on things that have practical qualities (well, *most* do). Perhaps a public-key stream cipher hasn't been designed because there is very little practical advantage to doing so. Or maybe some of the major cryptologists out there haven't even considered the implications.
As part of your thesis, perhaps you could give some reasons and legitimate uses for a stream cipher. Are there any protocols where this would be useful? Are there applications that would be greatly helped by this? Could the design of a public-key stream cipher give new insights into the mathematical workings of other public-key ciphers such as ElGamal and RSA? Can you show that there is a legitimate reason to use a PKSC instead of key exchange, followed by a conventional stream cipher?
I think it'd be interesting to see a paper on this subject. If you do include a section on this topic as part of your thesis, I think people would be *very* interested in seeing it. Go for it!
Best of luck!
... in fact, I don't even play one on TV.
:)
The problem with streaming asymmetric encryption comes from the way asymmetric encryption works. Namely, you've got all these different numbers that all coalesce and interact to give the cipher security. The two numbers that cause the most problems with streaming are referred to as p and k. p is a prime number that's very, very large, and k is a number which is relatively prime to (p-1).
The value of p is a constant for all the bytes you want to encrypt. The value of k will change for each byte -- or at least it should change, if you're as rabidly paranoid about security as you should be.
If p is a few hundred digits long, then it is a nontrivial task to find k relatively prime to p-1. Right there is a huge bottleneck. You also have to do a lot of multiplication on extremely large numbers; this, too, causes a bottleneck. And since you'd have to do these tasks for each and every byte, it would become a huge tax on the processor in no time flat.
Then there's the problems of decrypting. At some point in the decryption process, the extended Euclidean algorithm (or one of its derivatives) must be used. This is another nontrivial algorithm, and it must be executed for every byte received.
So in short -- yes, it is possible to do streamed asymmetric algorithms. But it's such an enormous performance hit that it's almost universally a bad idea. Far better to use an asymmetric method to negotiate a random session key (Diffie-Hellmann key exchange is specifically designed just for this), and then use a very fast symmetric algorithm to encrypt the stream.
If I recall correctly, algorithms like Blowfish are something like three orders of magnitude faster than asymmetric algorithms like RSA or Diffie-Hellmann. It's significant.
I may be off somewhat on some of my statements; I don't have my usual crypto references handy. So take this with a grain of salt.
WHY do want public key based stream encryption? If, during the initiation of your stream, you use public key encryption to exchange a shared secret (let's call this a "stream key") which is generated from random noise, then you can use shared secret stream encryption from that point forward. All the trust advantages of public key encryption, with all the speed advantages of shared secret encryption.
So, for example, during a TCP handshake you use RSA to exchange a 2048 byte key. Then use your favorite symmetric cypher (3DES, IDEA, whatever) with this shared key to encrypt the stream!
I write stream encryption software for www.v-one.com. The method I've just described is roughly what we do, and what all of our competitors do. While public key stream encryption is certainly feasible, if you understood the preceding paragraph you'll understand why it hasn't been written.
More details available upon request,
-mwalker.
--
What happens when you outlaw guns