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. "
The sender generates a random x[0], and lets x[1] = x[0]^2 (mod n). Further x values are computed recursively x[n] = x[n-1]^2 (mod n). The low-order bits of x[1..n] form a key stream. Note that x[0] is *not* part of the stream. Also, the number of low-order bits you can take from each x[i] is actually about log2(n).
After you have used as much key stream as you like, send x[n+1] along with the encrypted data. The recipient, knowing p and q, can compute square roots mod n in a fairly straightforward manner. It is provably impossible to find such a square root without the factorization. (To be precise, it is provable that an efficient algorithm for finding square roots modulo a composite leads directly to an efficient algorithm for factoring tat composite.)
Having said that, please look at hybrid schemes. They tend to have much better security in practice.
...that can take up several chapters of a good textbook. So, rather than spend it all typing in here, I recommend (as I'm sure lots of other people will) that you go and get a copy of Applied Cryptography by Bruce Schnier. It's got everything you ever wanted to know.
...phil
...phil
"For a list of the ways which technology has failed to improve our quality of life, press 3."
Secondly, once you share the key, you can either use a stream cipher, or you can use a block cipher. Using a stream cipher would be fairly easy in a streaming environment. If you wish to instead use a well-proven block cipher such as 3DES or Blowfish/Twofish, what you will want to do is packetize your input data, prepend it with a length byte (to tell how many bytes are in the encrypted block -- fill out the remaining empty bytes in a block with random noise to confuse attackers), and then send the result. This is similar to the way the network code itself packetizes data, by prepending data packets with a header that, amongst other things, tells how long the attached data block is.
A streaming public key encryption algorithm is possible, but of little use. The above is a fast, elegant way to handle situations that at casual glance would require streaming public key encryption, and those techniques are used by every product I'm aware of that appears to do "streaming public key encryption".
-E
Send mail here if you want to reach me.
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!
The question is not simply of whether the "delay is acceptable;" it is of whether any delay is acceptable.
Consider the situation of running a Telnet session. You press a key, and expect the system to respond to you, updating the screen every time you press a key.
That is a case where there is a need for something rather like streaming; in effect, the communications stream needs to be able to respond to each key press, and transmit them immediately. Not only is your "two minute" delay unacceptable, I would (and sometimes do ) find a 0.5s delay to be unacceptable. If I'm running Emacs or vi across an encrypted Telnet session, I am absolutely NOT going to find it acceptable for the system to collect up two minutes worth of updates, and handle 'em all at once. (If I was running TECO, where updates are queued 'til I hit ESC, or a mainframe editor where updates are queued until I press [ENTER], that may be a different story...)
That being said, it is fairly usual for network-based transmissions to mandate block-oriented schemes, as the transmission medium is not a "stream," but rather a set of "packets" that map nicely onto "blocks."
If you're not part of the solution, you're part of the precipitate.
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.
Becouse block size isn't known about before hand. It's not a fixed width field that's being encrypted. The packet may only BE a byte. It may be 200. You don't know..
-- I'm the root of all that's evil, but you can call me cookie..
The fact is, single-bit encryption Cannot be done securly. If you are Not sure, for example, in a streaming situation, that All previous bits have been recieved, then you cannot base current bit values on all previous ones without making your system so weak as to be useless. Even if you increase the minimum data size to a 8-bit byte, you still run into problems - did the previous byte come through? what about the one before that?
The only way to have secure and usable streaming encryption would be to use a large packet size, and encrypt each packet... now by large, i dont mean several kb or anything - we could be talking about 256 bits per packet, for example. Each packet gets its own encryption applied, and is not only secure, but does not rely upon future or past data for the encryption.
Redundancy could be built into the schema also - spreading data through several packets to ensure it gets through even if one is lost. Mind you, this does Not produce a true stream, but a series of packets that can be decrypted and reassembled into a stream... Sounds like virtual circuits and tcp/ip, doesnt it?
If you can get around the problem of being sure all data previously sent Was sent, then a XOR based algorythm could be used on a per-bit or per-byte basis as the data flowed through, with the encryptor keeping track of where in the key it is pointing, and systamaticly applying the encryption to individual pieces of data as they flow through...
the problem is, however, that XORs are not that hard to break...
man is machine
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
Fine. I get your point. Please don't take this as a personal attack of any sort, because it's not. It's just the way I happen to see things. Okay?
My question is this: Would you use or purchase cryptography software from somewhere that is even the slightest bit sloppy as to the phrasing of what their product does?
One of the entire points of the crypto is being a stickler for detail. Like making sure that the algorythm takes the same amount of time to run regardless of the inputs and outputs. Like making sure that the random number generator actually generates random numbers, rather than just numbers that appear to the eye to be random.
With so many places available to get VPN software, why would one wish to use a product which was developed by people that can't even describe the process correctly. It's not that hard, you know...
Extending that, whose advice would you want to take on such subjects? Not mine. But I'm not offering any, either... I'm just pointing out a fault I saw.
That's all...
Moderators, bring it on... I've got the karma to burn
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!
IANAG : I am not a guru, But ...
I admit a certain naiviety on this subject, but why does it HAVE to be a bit or byte at a time? Are you tansmiting network packets that size? Seems an awful waste. Why don't you encrypt blocks of the size you are pumping out in you packets, while it is not technicaly a stream, neither is the way in which we handle network communications, and it shouldn't really matter (except for real time systems, and people rarely combine real time applications with encryption, because encryption is so slow.)
-Crutcher
-- Crutcher --
#include <disclaimer.h>
Encryption of a stream basicly comes down to the encryption of batches (or packets) of data. The size of these batches is variable of course. It depends on the delay that is still acceptable.
E.g. if you think a 2 minute delay is acceptable, you can opt co collect 2 minutes of data, encrypt it and send it. The client then decrypts it and views it. Thus, in the client, while viewing these 2 minutes of data, the next two minutes are processed.
With public channels, this is not really an option, for you don't know when someone attaches to this stream. They have to be more continuous. With public/private keystreams this is a viable option. The request request can be authenticated with the public key, and acted upon immediately, serving only that connection.
An even better scheme would be to let each batch, or number of batches be encoded with a new 'public transmission key', generated by the client and sent to the server. Thus even if, at a later time, the original keys were broken or discovered, all the transmission keys would still secure the data sent.
The problems in all this don't lie in the encryption. That's hardly a problem. The problems lie in speed.
1. It still takes quite some time to encode data, and decode it on the client. Weaker keys will have to be used to decrease needed computing power.
2. Encrypted data is cannot be compressed (if it could, recurring structures could be identified, and thus encryption can be (partly) broken). Therefor transmission speeds would drop dramatically.
This has become quite a rant. Hope it helps.
----------------------------------------------
the pun is mightier than the sword
Use a conventional PK algorithm to transfer the keys, then a conventional stream cypher to send the data.
That's similar to PGP, where RSA is used to transfer a random session key, and IDEA is used to encode the message with the random key.
As it turns out, most PK systems are fairly slow for general purpose encoding, and they're primarily used to mearly send session keys.
- Public key algorithms are very computationally intensive
- Public key algorithms aren't cryptographically strong.
If you use a public key algorithm, such as RSA, to encrypt a message it would be a lot slower and you would be giving eavesdroppers tons and tons of cyphertext to crank through their cryptanalytic tools.The "big idea" of public key algorithms is not that they're more secure but rather that they allow secure communications between parties without shared secrets. In other words, you don't need to clandestinely meet with your contact in a small shop in Switzerland to agree on a secret password or to swap one-time pads.
Each public-key pair is (warning, this is another loose analogy) like a phone number. I can call you from anywhere and only you will hear it ring. (I told you it was loose...) And once I've called you, I can be pretty sure that it's you on the other end instead of your neighbor.
That's why the pizza place asks for your phone number. If they call it, and you confirm your order you've just "signed" it.
See Douglas Stinson's Book "Cryptography: Theory and Practice" Chapter 12. Look for the Goldwasser-Micali public key cryptosystem and the Blum-Goldwasser pubic key cryptosystem.
.).
Both of them generate a psuedo random string (based on the difficulty of factoring) and then encrypt the plaintext one bit at the time. (Stream Cipher).
No one uses this for two reasons: the Goldwasser-Micali encrypts one bit by sending log(n) bits (where n=pq, and it is the modular base of all the operations) so that means 1 bit -> 512 or more bits if you want security. Additionally both of these schemes are MUCH slower (as noted by previous posters) than symmetric key ciphers (DES, blowfish, serpent. .
The usual trick is the trick mentioned by everyone here: use public key to share a secret key, then use secret key. This is used by all software that I am aware of.
Hope this helps!
jabber: johnynek@jabber.org
... 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.
Since you are working on your thesis, I suppose you are already quite familiar with cryptography. The other slashdotters recommending Schneier's book is falling short of your question.
:-)
First thought, but not a true stream cipher:
One possible suggestion would be a winnowing and chaffing system. The drawback is that you need a huge channel to pass the w/c information. The w/c channel would need to be magnitudes larger than the original stream.
Second thought, also not a true stream cipher
There is a suggestion for a hybrid w/c system using pre-calculated hashes with an incrementing serial number, and sending the correct hash for that bit.
The hashes can be quite short, it depends on the length of the key and the serial number, and the entropy of your algorithm. Both sides can pre-calculate the hashes for many bits ahead, so the actual latency can be quite short.
This keeps your bandwidth low, but processing power is enormous.
Third thought, look to new hybrids
There has been other work done in creating streaming ciphers with a self-shrinking generator coupled with a large starting key. The starting key would use standard PKI, and a secure channel to exchange the keys. The certificate would not be time-based, but bit-based. The keys would have to be re-negotiated before the permutation engine has the chance to roll over. This keeps the entropy of your encrypted stream low to foil cryptanalysis.
I like this idea best, because the whole PKI/IKE/DH system is becoming well known, and only minor changes to the certificate data would be needed to move from time limits to data limits. Now somebody has to cobble together a working system using OSS code, and we're set
Good luck with your thesis. I think you've thrown this question right over the heads of most slashdotters, but you might find a good lead or two here.
the AntiCypher
Hemos is like...sci-fi fans;he thinks technology is cool, but he hasn't bothered to understand the science it's based on
This guy is writing his thesis so -hopefully- he should know what he's asking. PGP, SSL, ssh, etc. etc. only use public key encryption to exchange session keys. And the Public Key encryption used ISN'T Streaming. DES, Blowfish, etc., aren't public key.
Sure public key is "expensive" computationally, but that's not what the guy's asking. If he doesn't know, all's lost anyway.
So keeping in line with the other post: ;-)
Use either Linux or the GPL to provide you with encryption
Sorry btw that I'm jumping on this post, my criticism applies to almost the entire discussion.
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
Answer number two: As other posters have indicated, known public key algorithms are too slow to be of much use in encrypting large amounts of data. If you look at existing implementations, nobody does bulk encryption with a public key algorithm. Generate a random session key, send it to the other end encrypted with your public key algorithm, then use a stream cipher of your choice to do the bulk of the work.
This means, as hinted at above, that you don't just need an algorithm you need a protocol. Your protocol must address questions about how you generate your keys, how once side informs the other, who gets to generate them, how often (or if) they change, etc. It is possible to keep your protocol quite simple, but you need to at least think about such things.
Answer number three: In a word "modes". There are various ways to apply block encryption algorithms such that you can use them as stream algorithms. Because the public key algorithms are slow, this application will be slow, but it does work and is generally considered an OK cryptographic practice to apply the various modes where appropriate. So, what are the modes? What are their pros and cons? See chapter 9 of Bruce Schneier's Applied Cryptography.
If you are interested in this stuff, then you should really get a copy of Schneier's book and check it out. It's chok full O' cryptographic goodness. If your local bookstore doesn't have it, then fatbrain.com or your favorite online bookseller will.
One final thought. Messing around with crypto is a lot of fun, but it is harder than it might seem. There are a lot of implementation pitfalls that can render your crypto worthless or nearly so. When you are doing something really important, stick to existing algorithms and implementations.
However, it seems to me that as stated, your problem has two immediate solutions. First is buffering bits until you have enough to properly encrypt. While you couldn't use full PGP in this (since digesting won't work), doesn't RSA operate on single chunks of the plaintext, so you could buffer to the appropriate length and use RSA. This might make your crypto vulnerable to frequency attacks, if they're appropriate to the plaintext.
It occurs to me that some sort of random delay on the buffered packets, together with ordering information within the encryption, would destroy this attack potential, though.
The other solution approached the shortcoming of the first that it infringes on the real-time-ness of the stream. For mission critical streaming, it might be sufficient to use a pad at the beginning of the message, determined by a challenge-response or some such. (Honestly, I have an even vaguer feeling for challenge-response crypto and security, so this might not be as helpful.) Anyhow, if a garbage string of sufficient length could be added to the beginning of messages, you could accomplish bit by bit encryption without loss of security in early communication.
Of the two, I definitely favor the first, if for nothing other than error checking. It also seems to be the more secure of the two, and a trade off in security to simultaneity can be made in the length of packets, in extreme cases, or for extreme control methods (or on noisy lines) and in the maximum shuffling that can occur. This results in fairly predictable delays, since the length of packets times the maximum hold order (how many packets late it'll be) gives the minimum buffer length required, and thus the minimum delay.
Again, you might use the second in cases where the demand for synchronization is so high that it defeats the first system. However, I'm still uncertain how to arrange for the padding. Perhaps more conventional PGP or something could be used to establish the transmission?
Finally, I'm honestly curious as to what other /.rs believe would be better: error checked(&corrected?) encrpytion, or encrpyted error checking. Again, maybe it doesn't matter if you aren't doing mission critical data, or data that can take errors okay, like voice or images, but in any other case, it should be required.
IP is just rude.
Is there any torture so subl
The way we pro's do it, is use a key exchange protocol such as Diffie Hellman which uses asymmetric ciphers (public key stuff) just to generate a shared secret on both sides of the communication . This shared secret is usually used to generate a key for a symmetric cipher such as DES.
When both parties have the same secret key for the symmetric cipher on both sides, the streaming then begins. As for your question regarding why the earlier blocks are as well encrypted given the behavior of feedback ciphers, it's because the first block is transformed using something called an initialization vector, which is a block of noise. yes, it has to be the same noise on both ends or it all goes to hell.
in other words, yes it's public key based but the actual work of it is old fashioned symmetric. this is due to the fact that asymmetric stuff is very slow compared to symmetric.
You should definitely read anything by Bruce Schneier, starting out with Applied Cryptography
-nutsaq
Looney's.net