Public-key Based Streamed Encryption? 116
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. "
This is the Blum-Blum-Shub (BBS) generator (Score:2)
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.
This is a subject... (Score:2)
...phil
Stream ciphers vs. Block ciphers (Score:2)
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
Actually there are related schemes... (Score:3)
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?
--
Granularity is the killer question (Score:2)
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, [hex.net] 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."
My Suspicion: Not Practical (Score:3)
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.
Possible misunderstanding of stream ciphers... (Score:3)
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...
Here is a good Windows client solution for ssh! (Score:1)
F-secure is garbage. I tried it for 30 days and decided not to give it a second look; it doesn't handle color properly, nor resizing. ssh + rxvt handles resizing properly, so I can be typing in vi on the remote machine, change the size of the local window and the remote editor is notified. Plus the color support is there so I can edit code on a remote machine using vim with all the syntax coloring crap working properly.
To boot, rxvt copy and paste behaves in the standrad way: highlighting automatically copies, middle button pastes!
SecureCRT looks a lot better than F-secure (color, resizing works), but it's the same old 30 day crippleware story. (Plus it integrates everything into one program, which is stupid. Why not have a separate terminal emulator and ssh client instead of making a monolithic thing that does the terminal emulation?)
Re:Why a byte at a time? -- hints (Score:3)
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.
Re:Why a byte at a time? (Score:2)
Suggestions (Score:1)
Re:the first question to ask is why (Score:1)
I work for a crypto company too and I concur with the above statement. While there are asymmetric stream algorithms (RPK is the main one, I believe) most of the existing knowledge is of using asymmetric algorithms to share session keys for stream ciphers. It is always good idea to go with the most used algorithms unless there are known deficiencies in them. See any of Bruce Schneier's Cryptogram newsletters for reasons (http://www.counterpane.com).
Two points:
1) It is better to use a real stream cipher (such as RC4/Arcfour or one of the LFSR based ones) since they all emit a single byte at a time and are very fast. Key entropy is not necessarily a problem with the LFSR based ones since you will be generating the session keys automatically (must be from a good PRNG). CBS-mode block algorithms are fine too but the performance will usually leave something to be desired.
2) ALWAYS generate a new session key for each encryption session and preserve state for the duration of the session. NEVER start a new stream with the same key or reset the state to the initial value in mid-stream (e.g. for resynchronisation). If you get this wrong you might as well send it all in clear (since the XOR attacks are basically trivial).
NO - Re:Yes! (Score:1)
Bits vs Packets (Score:2)
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...
Goldwasser & Micali, Prob. Encryption, April 1984 (Score:1)
--
Kyle R. Rose, MIT LCS
Re:SSH (Score:1)
Re:Streaming is still batches of data (Score:1)
Just my observation.
Re:the first question to ask is why (Score:1)
2048 byte? Don't you mean 2048 bit?
Many stream encryptions that I know of, need 64-128 bits ok keyspace, and that's quite enough. And RSA would naturally give between 500 and 2000 bits of data per "run" of the algorithm. So for 2000 bytes, you'd need to run RSA 8 times in a row, giving MUCH more bits than you really need.
Roger.
Re:Difficult (Score:1)
Don't think I'm picking on you. You're just the so-many-eth that makes this mistake, and I think I should set this straight.
If you need a stream cypher, you can just take the past data, and shove it into the encryption routine. The random bytes you then get, you just feed in an XOR with the data. As much as you need. And once you exhaust one your "blob" of encryption, you use the encrypted data, or the plaintext as the source for another encryption round.
People get a "bad feeling" with XOR, as it feels unsafe (probably because if you just xor with the password, it actually IS unsafe....). But that's not true. If the "key" I XOR with has "random" ones and zeros, all bits have had a 50/50 chance of having been flipped, So wether there is a 0 or a 1, you really can't say wether it was flipped or not and wether the original might have been a 0 or a 1.
So, an algorithm like RSA spewing 1000 to 2000 bits at you at a time, doesn't really matter. What matters is that RSA or other public key crypto is orders of magnitude slower than a symmetric. (as everybody else is saying...)
Roger.
Yes! (Score:1)
You can encrypt/decrypt byte by byte with DES, and if I'm not mistaken any of the "fish" protocols also support various feedback modes to do streaming as well. Just be sure you feed it a prime number as the key, or your entropy goes down more than "alittle".
--
Re:Yes! (Score:1)
--
Re:NO - Re:Yes! (Score:1)
--
Re:Bits vs Packets (Score:1)
Briefly, taking your comments by paragraph:
(1) First, message integrity is exactly what MACs provide. You can layer them over or under the encryption algorithm, or both, depending on what you need. Your statement that "single-bit encryption cannot be done securely" is both erroneous and unrelated to the issue of integrity.
(2) You're talking about block ciphers in ECB mode here, and not about stream ciphers at all. If you're going to participate in a discussion, learn the technology.
(3) Yes, you can get redundancy through any number of means. Again, this is not exactly relevant. Sure it sounds like virtual circuits and TCP/IP. Whatever.
(4) It sounds like you are (poorly) describing a one-time pad with a unit size of one or more bits. Maybe, if there are feedback buffers involved, you could be talking about a stream cipher. I can't tell. XOR is not an algorithm--at least I hope nobody considers it one--but it's one of the many mathematical operations that form the building blocks of modern block and stream ciphers.
(5) This I agree with.
I wouldn't even care about your apparent ignorance, were it not for your user profile which lists you as a "security software professional". That scares me.
spawn_of_yog_sothoth
Re:Public Key is the Fake Rock (Score:1)
That is, of course, not true. If it were true you could decipher any data stream that uses a public key-based key exchange by breaking that initial key exchange.
Generally, good public key cryptography with a certain key length is not as strong as good symmetric key cryptography with the same key length; that's why you need a 1024 bit RSA key to be safe for a while, and not more than 128 bits for an algorithm like blowfish.
(Unless, of course, somebody finds a way to break either algorithm in a way that's faster than brute force, for example by mathemetical breakthrough)
EjB
Surely you could assemble one? (Score:1)
Take a block cypher, use it in a mode which gives stream cypher behaviour (OFB or CFB?) and encrypt the session key under the recipient's public key. Pass the encrypted session key as part of the stream setup protocol, and there you have it...
(Suggested reference for those who don't understand but want to: "Applied Cryptography" by Bruce Schneier.)
Re:Boy the moderators are having fun today... (Score:1)
Let me get this straight; one programmer from a company makes one internet post about a subject, and you misunderstand the meaning of one word because his sentence was unclear to your quick reading, and that indicts the entire company's entire product line?
Jeezus, boy, you just talked yourself out of doing business with every single company that ever existed. Get a grip.
If some guy writing POS apps for Burger King accidentally types "freis" when he's in a hurry some time, are you going to quit eating there?
The sad part is, what the guy said wasn't even wrong; he was exaggerating for effect. You're the one that made the mistake, and you're claiming people should blow off HIS company over it?
Hell, where do you work; maybe we should boycott your company too while we're at it.
BTW, you misspelled "algorithm". Perhaps the Public Relations folks at your company should be fired over your horrible mistake.
Use a hybrid system... (Score:5)
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
Re:Use a hybrid system... (Score:1)
This is actually not the case. SSL supports Diffie-Hellman key exchange as an alternative to RSA. Unfortunately, none of the major browsers implement DH, making this not very useful for web servers. OpenSSL [openssl.org] does, however, support DH out of the box.
Stream Encryption (Score:1)
I've worked with systems that use convolutional encoding to protect data streams against noise. The encoding and decoding algorithms are very different. The problem is that the encoding algorithm is much simpler than the decoding algorithm. The generator polynomial could be viewed as a private key.
Re:Bits vs Packets (Score:1)
I would disagree. Each cipher text bit can be computed as the exclusive-or of the plain text bit and a complex function of the preceding N bits (plain or cipher or key).
Re:"general reader" interesting in the techincal s (Score:1)
There may not be any packets to encrypt. The data may already be encrypted or may not have any structure. For example, delta modulation converts an audio signal to a stream of bits, not bytes or packets.
A stream encryption device allows you to encrypt an arbitrary bit stream at high speed and minimum delay. This is ideal for link encryption, such as point-to-point data lines.
Re:I am not a professional cryptographer... (Score:1)
Boy the moderators are having fun today... (Score:2)
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
Re:PGPfone? (Score:1)
Difficult (Score:4)
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.
Re:Here's a stream based encryption scheme ... (Score:1)
Transmission 1 (T1) = A XOR M.
Transmission 2 (T2) = A XOR M XOR B
Transmission 2 (T3) = A XOR M XOR B XOR A = M XOR B
T1 XOR T2 XOR T3 = (A XOR M) XOR (A XOR M XOR B) XOR (M XOR B) = (A XOR A) XOR (B XOR B) XOR (M XOR M) XOR M = M
Why, yes, I am bored today.
RPK is stream based (Score:1)
Note, however, that because you are not able to transpose bit positions or make them interdependent in any way, you _will_ lose strength in your cipher.
Re:Here is a good Windows client solution for ssh! (Score:1)
SSH (Score:1)
SSH2 also supports x11 forwarding and port forwarding so you can stream other things (such as IRC and Web browsing) all through a compressed and encrypted channel, using 3des, blowfish, twofish, rc4, etc...
There are Windows Clients (SecureCRT, F-secure) as well as the Unix clients, ssh, ssh2, OpenSSH, etc.
Speed is a major factor... (Score:3)
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!
Some thoughts (Score:1)
I'm also going to ignore
Now for your first question: can you encrypt a bit-at-a-time using public key methods? Yes. The best way to do this would probably be to pad each 1 bit message out to whatever the size that the PKE algorithm takes with a truly-random bitstream, and on the decryption end, you can just throw away the other random bits.
Is this "viable"? Well, yes, but it seems an awful waste of both bandwidth and computing power; PKE computations are expensive! Nevertheless, this would provide the desired "public-key based stream encryption algorithm" with "consistent security throughout the entire bit string".
--
Re:SSH (Score:1)
The public key (RSA) stuff is used for authentication and exchanging the actual keys which are used to encrypt the stream (with DES, blowfish, IDEA, whatever).
Why a byte at a time? (Score:2)
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
Streaming is still batches of data (Score:2)
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.
----------------------------------------------
No special stuff needed (Score:2)
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 is the Fake Rock (Score:2)
- 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.
Re:Use a hybrid system... (Score:2)
Currently, it seems that SSL and RSA are tied together--you can't talk SSL unless you talk RSA. I would take SSL, gut out the algorithms (gut out RSA, and see if the symmetric algorithm is copyrighted), and replace the algorithms.
You can get a pseudo-free implementation of SSL out of an Australian team (the RSA patent is void there). They are called SSLeay [ssleay.org]. If you can't find one, you can find the SSL spec and write to it.
Then, go to GnuPG [gnupg.org], a GPL'd version of PGP that only uses Diffie-Hellman to avoid the RSA patent. Snag the crypto algorithms out of GnuPG, glue them into the SSL server/client, and you have your own free variant SSL. You won't be able to talk to regular SSL (expecting RSA), but you can make your own free standard.
Public Key Stream Ciphers DO exist (Score:2)
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!
There shouldn't be a theoretical problem (Score:1)
Sure, but... (Score:1)
At least I was thinking of encrypting things like videostreams. Given that you already have a public key block encryption algorithm, you can use that to answer the posed question with: yes, you can encrypt these things.
(So I don't need to use the fact that there exist stream ciphers.)
Re:I am not a professional cryptographer... (Score:1)
If you've got a real interest, I'd suggest the ICSA Guide to Cryptography and Schneier's _Applied Cryptography 2nd Edition_.
Also, check out the PGP owner's manual. It has a good introduction to crypto.
Re:One was announced last year (Score:1)
There are also some real questions about security. Remember, the crypto community barely trusts DES, and DES has survived 20+ years of intense cryptanalysis. There are some places that won't use Blowfish because it's too new and untested.
An algorithm which came out only a year or so ago may be interesting, but at this stage it's also irrelevant except to the academic community. If it survives three years, I'll be moderately impressed.
99% of all algorithm designs are crap. (This is not to say they're worthless; FEAL is an example of a very crap algorithm, but it's very useful as a way to test out new cryptanalytic attacks.) Cayley-Purser is no different; statistically, it has a 99% chance of being demonstrated to be crap. And even if it's not demonstrated to be crap, that's not the same as saying it's not crap.
For right now, it's interesting to the academic community and irrelevant to the practical world.
I am not a professional cryptographer... (Score:5)
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.
Some more thoughts (Score:2)
First thought, but not a true stream cipher:
One possible suggestion would be a winnowing and chaffing [slashdot.org] 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
Anyone know what they're talking about here? (Score:2)
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.
Re:Generic Solution (Score:1)
> checked(&corrected?) encrpytion, or encrpyted error checking.
This is a little off-topic, but why not...
You want to apply error correction to the encrypted stream, not the reverse.
A single bit error in the encrypted data will result in multiple bit errors to the decrypted data. And if you're uing a good encryption algorithm, chances are that a single bit error to the encrypted block will cause all the bits of the decrypted block to be unpredictible. If you originally had to deal with single bit errors, you now have to deal with burst errors as long as a single cipher block for every single bit error you had to handle before. And that's only in ECB mode. If you use a mode in which errors propagate, the situation is even worse.
Furthermore, the codewords of an ECC have more structure than the original data, and although this is a bit of a guess, that may help the cryptanalyst a bit.
Re:I am not a professional cryptographer... (Score:2)
Ok. The simplest to understand is RSA - it relies on the fact that for a very carefully chosen pair of numbers (x and p) you can do the following:
- Take your original message as a number
- raise it to a power (say, 512)
- divide it by p, and take the remainder (this is called modulo arithmatic, but is the same as division-with-remainder you may have done when learning division)
- the remainder is your ENCRYPTED MESSAGE that you send
- the recipient gets your remainder, and raises it to the power (x/512)
- HE then takes the remainder when divided by p
- the remainder he gets is your original message!
for obvious reasons, the value "p" is the PUBLIC half of the code - you have to know it. the value "x" is the secret half - without it, you can encode, but not decode.that do?
--
Not feasible (Score:2)
Re:Bits vs Packets (Score:1)
The whole idea of a stream cipher is built on that concept:
You take a bit of the message you want to encrypt.
You XOR it with a bit from a stream of "random" bits
voila!: the bit is encrypted.
Anyone who doesn't know with which random bit the original bit was encrypted, has no way to "crack" the encryption.
The drawbacks:
The recipient needs to know which "random bits" to XOR with the encrypted bit.
The alignment should be perfect, so the loss of 1 bit in transmission causes the rest of the message to be intellegible. There are numerous error correction codes for this.
By reading a lot of these comments, there aren't that many readers that know what exactly a "stream cipher" is... It's not encryption on a stream of data (like SSH and stuff)... Bram
Okay... I'll do the stupid things first, then you shy people follow.
Re:the first question to ask is why (Score:1)
give me a break, moderators. since when do people get moderated up for missing the point by so much. what is your point, 'um', that 2048 bytes is a bit long for a symmetric cipher? maybe attacking his company is a little extreme? (and it's the one time i don't have points!)
sh_
Re:Use a hybrid system... (Score:1)
Hmm, wonder if some team outside the US could implement a SSL/TLS via DH and merge it into Mozilla [mozilla.org]...
Bite this, Microsoft -- "Sorry, you can't visit this secure site unless you use the lizard." Hehehehe...
Sorry if this isn't up to my usual standards, but I'm very pissed off at IE right now. :-)
Compressibility (Score:1)
One good reason data should be encrypted first, then compressed later (no-one seems to be mentioning it) is that compressed data generally has some sort of header that could be used to speed up the cracking process.
Re:Yes! (Score:1)
Offtopic...!
The question was whether you could do public-key stream encryption. DES is not a public-key (asymmetric) cipher.
oopsie...
Re:the first question to ask is why (Score:1)
yes.
>Glad to know that there's one source I won't be obtaining crypto software...
The above sentence is grammatically incorrect.
>Wouldn't it be more appropriate to use 2048-BIT RSA to exchange your 3DES or 128-bit IDEA key? I mean, who's heard of a 2048-byte triple DES key?
You are deliberately misinterpreting me?
I didn't say a 2048 byte 3DES key, I said your favorite symmetric algorithm, IDEA, DES, whatever. And yes, 2048 bytes is an absurd key size. I was merely pointing out that you could choose one that large if you wanted to, i.e. it could be as secure as you wanted it to be, and you only need one initial public key exchange.
the first question to ask is why (Score:5)
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.
Re:SSH (Score:1)
Stream ciphers have a considerable speed (10x or more) advantage over typical block ciphers such as DES, Blowfish, Triple-DES, CAST, and IDEA. They are primarly used where high transfer rates are required (such as video or real-time audio).
Forget trying to use public-key algorithms for stream ciphers for the following reasons:
a) Pathetically slow (i.e 10-100x times SLOWER than block encryption and 1000's X SLOWER than good stream implementations.
b) Block size must be greater than or equal to the size of your keys. Making the encrypted block size (say 1 byte) would be subject to many attacks. That is why blocks are often padded to the minimal recommended block size with random characters when a small block is introduced.
Unless you have a very fast hardware implementation of a PK system (say it's contained within a Star Trek like Warp field), then I'd take the key exchange approach as recommended in my and the other posts that preceed mine.
Re:SSH (Score:1)
Most cipher implementations in software are based on a byte as the fundamental unit for encryption. A byte, is eight bits. So, yes, it is a block. But, a byte (or multiple of) is used because the processor can effectively manipulate it. Most processors aren't designed with the primary purpose of working on single bits.
The primary difference between a stream and block cipher is how it is designed and its intended application with Stream ciphers designed primarly for speed.
Software implementations of the typical block encryption algorithms are extremely inefficient for applications requiring stream encryption. One would not consider using Blowfish, IDEA, or even DES in a stream cipher application unless the encryption engine was hardware based. It's simply not practical.
I, personally, have not done a thorough analysis of RC5 (I will leave that as an exercise for the reader). The security of the likes of RC5 is based primarily on the entropy introduced by a large key. But, the overall complexity of the algorithm is sufficiently low that it can be readily implemented in software without significant bandwidth degradation. Hence, it is widely used in applications requiring video and audio encryption.
Would I trust my personal finances to it? Sorry, (and not offense to Ron Rivest), not in this lifetime. I would more likely trust them to the likes of Triple-DES, Blowfish, probably TwoFish, and eventually, AEC.
One must remember that RC5 was a proprietary algorithm right up until the momement when it was illegally published. Security by obscurity is no security at all.
Re:SSH (Score:1)
But, if someone is connecting for the first time, ssh appears to let you do so. It will generate a one time session key. All you achieve in this situation is an encrypted link.
Validation to known hosts can be compromised by spoofing an IP. If there was an exchange of trusted X.509 certificates and a protocol used to exchange a session key with a "trusted" host in ssh1 as their is, I believe, in ssh2, then authentication is actually being performed to determine the indentify of the remote user.
If I am wrong, please correct me. I don't claim to be infallible. I'll just go back to making radios from coconuts and sea-shells.
The Professor
Re:Here is a good Windows client solution for ssh! (Score:1)
As long as you want Windows solutions, I've found Tera Term [vector.co.jp] to be a most excellent terminal emulator for Windows. When combined with TTSSH [zip.com.au] it makes an excellent free, secure client for Windows.
Resizing needs some help (every time you resize it, it clears the screen), but other that that, it's worlds above any other terminal emulator for Windows. Of course, I still haven't tried rxvt for Windows.
streaming + encryption + compression (Score:1)
I used ssh to connect to our LAN from my SOHO. When ssh was running with encryption + compression, it was getting rather slow. It looks as if ssh first compresses and then encrypts every packet (perhaps it encrypts first and then compresses?!?).
This is not very efficient. Is there an algorithm, that compresses and encrypts in one step?
Bye egghat.
Re:Streaming is still batches of data (Score:1)
PGPfone? (Score:1)
--
Richi Jennings
OpenMail Technical Product Manager http://www.hp.com/go/openmail
Hewlett-Packard Company
"Practice random acts of kindness and senseless beauty"
Re:Here's a stream based encryption scheme ... (Score:1)
public key algorithms fundamentaly packet-based (Score:1)
In other-words, to encrypt one bit at a time is impossible unless you use _extremely_ small keys, or your willing to expand your data _a lot_.
Of course you can send out your encrypted packets one bit at a time, but that's not a true streaming cipher, and you won't be able to reconstruct any part of such a packet until you have the entire packet. And, as everyone has pointed out already, you can use public encryption to securely exchange cipher keys.
Three Easy Answers (Score:2)
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 [counterpane.com].
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.
umm (Score:1)
Re:My Suspicion: Not Practical (Score:1)
some remarks:
So I think you are right in saying public key systems do not fit the need. Your analysis of the problem reducing it to key length is definately wrong.
Re:Public Key is the Fake Rock (Score:1)
Well, not all of them... Also you can make them strong by increasing Key Length.
"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."
That doesnt say that there is an authentication in it. You definately need some shared secrets for that (I know about zero knowledge etc. but actually they rely at some state on a possibility to prove the own identity to someone else, and you need shared secrets for that - the shared secret for the pizzy guy is the order).
Re:It's possible (Score:1)
Re:I am not a professional cryptographer... (Score:1)
Did you mean 'hacker' or 'cracker'?
Do you know the diffrence? I don't think you do.
Use a C=64 (Score:1)
Here's a stream based encryption scheme ... (Score:1)
Alice wants to send a message to Bob (heard this one before? ;)
Alice has a key of here own, let's make it 8 bit long: 11010011
Bob also has a key of his own: 01011100
Alice uses her key to encrypt a message (for simplicity, that's also 8 bit) to Bob: 11010011 XOR 01010101 = 10000110
Bob receives the message, encrypts it with his key and sends the result back to Alice: 01011100 XOR 10000110 = 11011010
Alice receives this message, encrypts it again with her own key (thereby actually removing her encryption) and sends the result to Bob once again: 11010011 XOR 11011010 = 00001001
Now, finally, Bob encrypts the message with his key, effectively removing the last encryption to get the plaintext: 01011100 XOR 00001001 = 01010101
Wow!!! We got the plaintext! And not a single time did we send anything else but encrypted plaintexts, impossible for Eve to extract anything from! And Alice and Bob didn't even have to exchange keys!
Or?
Well ... the above is easily hacked. Moderate up the first person to answer with the crack ;)
Generic Solution (Score:2)
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.
The best way to log in remotely (Score:1)
If you set up a web page on that machine which runs the Java applet, you will always be able to securely login to your box from any machine with a compatible browser. And you can download the applet and use it locally to login to wherever.
public key too expensive... (Score:1)
Using this method you could use any stream cipher available, and just use public key to move the stream cipher keys around.
Re:NO - Re:Yes! (Score:1)
The Ellis doc, etc. (Score:1)
Yes, I am a professional (Score:2)
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 [looneys.net]