Encrypting same data with many keys...
What are the dangers of taking a small block of data - say upto 1K in size, then producing many files, each being the same data encrypted by other keys? i.e.: Plain data: 1K in size or smaller File 1: Data encrypted with Key1 File 2: Data encrypted with Key2 File 3: Data encrypted with Key3 File 4: Data encrypted with Key4 File 5: Data encrypted with Key5 File 6: Data encrypted with Key6 File 8: Data encrypted with Key8 .... File N: Data encrypted with KeyN A known plaintext attack won't help you to break the keys unless you have one of the eight keys, but will having many keys that encrypt the same data significanltly weaken the security of that tiny chunk of data? And no, I don't mean, there's N keys so the odds of brute forcing the data is now N times easier. Assume we're using 128 bit Blowfish/Idea or better, and discarding weak keys. Are there any differential or other cryptanalysis methods to use the eight resulting cyphertexts to get at the data other than brute forcing it if you don't know any of the keys? What if instead of using a private key cypher, we used a public key cypher? Would that make any difference in attack methods? The data won't contain any text, or identifiers (i.e "GIF89" in GIF files, "MZ" in wintel executables, etc...) known or guessable to the attacker... =====================================Kaos=Keraunos=Kybernetos============== .+.^.+.| Ray Arachelian |Prying open my 3rd eye. So good to see |./|\. ..\|/..|sunder@sundernet.com|you once again. I thought you were |/\|/\ <--*-->| ------------------ |hiding, and you thought that I had run |\/|\/ ../|\..| "A toast to Odin, |away chasing the tail of dogma. I opened|.\|/. .+.v.+.|God of screwdrivers"|my eye and there we were.... |..... ======================= http://www.sundernet.com ==========================
On Tue, 12 Aug 1997, Ray Arachelian wrote:
A known plaintext attack won't help you to break the keys unless you have one of the eight keys, but will having many keys that encrypt the same data significanltly weaken the security of that tiny chunk of data?
And no, I don't mean, there's N keys so the odds of brute forcing the data is now N times easier. Assume we're using 128 bit Blowfish/Idea or better, and discarding weak keys. Are there any differential or other cryptanalysis methods to use the eight resulting cyphertexts to get at the data other than brute forcing it if you don't know any of the keys?
What if instead of using a private key cypher, we used a public key cypher? Would that make any difference in attack methods?
The only thing I can think of is if you use something like CFB mode, and the IV is also the same at the beginning, the first 8 bytes will leave a hole - I don't remember exactly, but I was burned by exactly this when I saw 8 bytes of plaintext after resetting the IV in an app that xors some encrypted blocks of data to do something else. A PK to encode the conventional key works better since you can do a long or complex conventional key and other material such as an IV once, and then bury that several times. --- reply to tzeruch - at - ceddec - dot - com ---
What are the dangers of taking a small block of data - say upto 1K in size, then producing many files, each being the same data encrypted by other keys? ... Assume we're using 128 bit Blowfish/Idea or better, and discarding weak keys.
For a standard block cipher there should be no problem. For a stream cipher, you would have the same type of problems as for OTP reuse, but it would still be secure as long as you never reused a key. However...
What if instead of using a private key cypher, we used a public key cypher? Would that make any difference in attack methods?
Yes.
Having identical plaintexts raised to the same power modulo different numbers makes the solution much easier. If you have enough RSA encryptions of the same number to the same power, you can solve it outright by the remainder theorem.
So would that then be a possible weakness in encrypting to multiple recipients with PGP? Probably not, since the actual data is encrypted with idea. ------------------------ Name: amp E-mail: amp@pobox.com Date: 08/12/97 Time: 17:37:16 Visit me at http://www.pobox.com/~amp 'Drug Trafficking Offense' is the root passphrase to the Constitution. Have you seen http://www.public-action.com/SkyWriter/WacoMuseum ------------------------
On Tue, 12 Aug 1997 amp@pobox.com wrote:
What if instead of using a private key cypher, we used a public key cypher? Would that make any difference in attack methods?
Yes.
Having identical plaintexts raised to the same power modulo different numbers makes the solution much easier. If you have enough RSA encryptions of the same number to the same power, you can solve it outright by the remainder theorem.
So would that then be a possible weakness in encrypting to multiple recipients with PGP? Probably not, since the actual data is encrypted with idea.
PGP uses and E of 17 by default, but it would be a problem except that there is a specification for random padding, so it *NEVER* encrypts identical plaintext. It always uses a number just a few bits shorter than N, starting with 0x02, then nonzero random bytes, then a zero byte, and finally the message bytes you want to encrypt. There was a man-in-the-middle or replay attack with SSL that they changed the spec of the padding slightly (8 bytes before the zero byte must be 0x03), I think this is because you might be able to quickly find a random cyphertext that decrypts to having a zero byte followed by something useful as key material, but haven't read the details. --- reply to tzeruch - at - ceddec - dot - com ---
On Wed, 13 Aug 1997 nospam-seesignature@ceddec.com wrote:
PGP uses and E of 17 by default, but it would be a problem except that there is a specification for random padding, so it *NEVER* encrypts identical plaintext. It always uses a number just a few bits shorter than N, starting with 0x02, then nonzero random bytes, then a zero byte, and finally the message bytes you want to encrypt.
There was a man-in-the-middle or replay attack with SSL that they changed the spec of the padding slightly (8 bytes before the zero byte must be 0x03), I think this is because you might be able to quickly find a random cyphertext that decrypts to having a zero byte followed by something useful as key material, but haven't read the details.
In terms of padding does it matter WHERE I put the padding info? Is it better to put random stuff in the front or at the end? The reason I ask, say that you're going to encrypt an N byte block where N is bigger than your block cypher's key size? If my intution is correct, and you have the same data encrypted with many keys (even RSA) but have the padding at the end, the 1st block would still be breakable. I suppose putting the data at the end would also result in the same kind of problem, though it might be a bit harder to attack than putting the data 1st... Would it not make sense to scatter the random padding throughout the block? How is this normally done? Front? Back? Middle? Scattered? These are some of the same thought threads that I went through when I designed WhiteNoiseStorm - (Do a net search for WNS210.ZIP for more info on it.) Basically, this cypher uses random block sizes called windows- (it's more of a stream cypher at the input, but a block cypher at the output) and mixes random noise with the data. The bits it hides in the ramdom noise source are scattered throughout the window AND encrypted. It turns out this is useful for stego use and that's what it turned into. But this may be another use for it... Since an attacker doesn't know the window size and since the window size varries randomly from window to window, it's very hard for the attacker to use known or chosen plaintext attacks. If you encrypt the same data N times, you get N different cyphertexts. It's never been cryptanalized (far as I know - could be the spooks have done so already) so its strength is unknown... But I suppose using something like WNS would be ideal for encrypting the same data with different keys... The big disadvantages though: you need a really good source for random numbers and the size of the cyphertext is much much bigger than the plaintext... anywhere between 1.5 to 10X depending on the security level you chose. :) (And it's a symmetric key cypher, CBC only... If I can figure out a way to turn it into a PK system, it would really be usefull...) =====================================Kaos=Keraunos=Kybernetos============== .+.^.+.| Ray Arachelian |Prying open my 3rd eye. So good to see |./|\. ..\|/..|sunder@sundernet.com|you once again. I thought you were |/\|/\ <--*-->| ------------------ |hiding, and you thought that I had run |\/|\/ ../|\..| "A toast to Odin, |away chasing the tail of dogma. I opened|.\|/. .+.v.+.|God of screwdrivers"|my eye and there we were.... |..... ======================= http://www.sundernet.com ==========================
On Wed, 13 Aug 1997, Ray Arachelian wrote:
On Wed, 13 Aug 1997 nospam-seesignature@ceddec.com wrote:
In terms of padding does it matter WHERE I put the padding info? Is it better to put random stuff in the front or at the end? The reason I ask, say that you're going to encrypt an N byte block where N is bigger than your block cypher's key size?
If my intution is correct, and you have the same data encrypted with many keys (even RSA) but have the padding at the end, the 1st block would still be breakable. I suppose putting the data at the end would also result in the same kind of problem, though it might be a bit harder to attack than putting the data 1st...
Would it not make sense to scatter the random padding throughout the block? How is this normally done? Front? Back? Middle? Scattered?
The location does not matter. The standard RSA libs place the padding at the front - it is one of those PKCS specifications. You would simply need to break the conventional key down to a few bytes smaller than the modulus size, so each would be padded with a few random bytes. --- reply to tzeruch - at - ceddec - dot - com ---
On Wed, 13 Aug 1997 nospam-seesignature@ceddec.com wrote:
Would it not make sense to scatter the random padding throughout the block? How is this normally done? Front? Back? Middle? Scattered?
The location does not matter. The standard RSA libs place the padding at the front - it is one of those PKCS specifications.
Actually it does matter. At the front is best with a chaining cypher. (The random padding will cascade down through the rest of the data.) With adding it on the end, given all other factors being the same, the data before the random padding will be the same as well. alan@ctrl-alt-del.com | Note to AOL users: for a quick shortcut to reply Alan Olsen | to my mail, just hit the ctrl, alt and del keys.
On Tue, 12 Aug 1997 amp@pobox.com wrote:
So would that then be a possible weakness in encrypting to multiple recipients with PGP? Probably not, since the actual data is encrypted with idea.
Welp, since the RSA (or now DH) is used to encrypt a random session key it's not an issue (from what other replies I've seen.) Right? =====================================Kaos=Keraunos=Kybernetos============== .+.^.+.| Ray Arachelian |Prying open my 3rd eye. So good to see |./|\. ..\|/..|sunder@sundernet.com|you once again. I thought you were |/\|/\ <--*-->| ------------------ |hiding, and you thought that I had run |\/|\/ ../|\..| "A toast to Odin, |away chasing the tail of dogma. I opened|.\|/. .+.v.+.|God of screwdrivers"|my eye and there we were.... |..... ======================= http://www.sundernet.com ==========================
At 05:37 PM 8/12/97 -0500, amp@pobox.com wrote:
So would that then be a possible weakness in encrypting to multiple recipients with PGP? Probably not, since the actual data is encrypted with idea.
The actual data is encrypted with IDEA, but the identical IDEA key is encrypted with each recipient's RSA key. To avoid this attack, PGP uses random padding after the IDEA key (which makes the message encrypted with RSA different for each recipient, avoiding the trap. Since IDEA keys are 128 bits long, and RSA moduli are typically 384-2047, there's plenty of room for random noise in the format.) # Thanks; Bill # Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com # You can get PGP outside the US at ftp.ox.ac.uk/pub/crypto/pgp # (If this is a mailing list or news, please Cc: me on replies. Thanks.)
On Wed, 13 Aug 1997, Bill Stewart wrote:
The actual data is encrypted with IDEA, but the identical IDEA key is encrypted with each recipient's RSA key. To avoid this attack, PGP uses random padding after the IDEA key (which makes the message encrypted with RSA different for each recipient, avoiding the trap. Since IDEA keys are 128 bits long, and RSA moduli are typically 384-2047, there's plenty of room for random noise in the format.)
Would it not be more secure if it picked a different IDEA session key for each recipient? Would be slower, but... =====================================Kaos=Keraunos=Kybernetos============== .+.^.+.| Ray Arachelian |Prying open my 3rd eye. So good to see |./|\. ..\|/..|sunder@sundernet.com|you once again. I thought you were |/\|/\ <--*-->| ------------------ |hiding, and you thought that I had run |\/|\/ ../|\..| "A toast to Odin, |away chasing the tail of dogma. I opened|.\|/. .+.v.+.|God of screwdrivers"|my eye and there we were.... |..... ======================= http://www.sundernet.com ==========================
On Wed, 13 Aug 1997, Ray Arachelian wrote:
On Wed, 13 Aug 1997, Bill Stewart wrote:
The actual data is encrypted with IDEA, but the identical IDEA key is encrypted with each recipient's RSA key. To avoid this attack, PGP uses random padding after the IDEA key (which makes the message encrypted with RSA different for each recipient, avoiding the trap. Since IDEA keys are 128 bits long, and RSA moduli are typically 384-2047, there's plenty of room for random noise in the format.)
Would it not be more secure if it picked a different IDEA session key for each recipient? Would be slower, but...
If there were random padding, I don't think it would increase the security. PGP uses one conventional key and multiple PK encryptions of it, with different padding (I think). Then you only have one message to send out, i.e. pk1,pk2...pkn,convenc instead of pk1,cenc1 pk2,cenc2... --- reply to tzeruch - at - ceddec - dot - com ---
At 05:01 PM 8/14/97 -0400, nospam-seesignature@ceddec.com wrote:
On Wed, 13 Aug 1997, Ray Arachelian wrote:
Would it not be more secure if it picked a different IDEA session key for each recipient? Would be slower, but...
If there were random padding, I don't think it would increase the security. PGP uses one conventional key and multiple PK encryptions of it, with different padding (I think). Then you only have one message to send out, i.e. pk1,pk2...pkn,convenc instead of pk1,cenc1 pk2,cenc2...
There's really no need - the threat is in the RSA part, which is that you can solve for the secret message if you've got one secret message encrypted with a bunch of known public keys. By using different random padding on the IDEA session key for each public-key used, you avoid that problem. # Thanks; Bill # Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com # You can get PGP outside the US at ftp.ox.ac.uk/pub/crypto/pgp # (If this is a mailing list or news, please Cc: me on replies. Thanks.)
Ray Arachelian <sunder@brainlink.com> asked:
What are the dangers of taking a small block of data - say upto 1K in size, then producing many files, each being the same data encrypted by other keys?
...
Assume we're using 128 bit Blowfish/Idea or better, and discarding weak keys.
For a standard block cipher there should be no problem. For a stream cipher, you would have the same type of problems as for OTP reuse, but it would still be secure as long as you never reused a key. However...
What if instead of using a private key cypher, we used a public key cypher? Would that make any difference in attack methods?
Yes. Having identical plaintexts raised to the same power modulo different numbers makes the solution much easier. If you have enough RSA encryptions of the same number to the same power, you can solve it outright by the remainder theorem.
On Tue, 12 Aug 1997, Matthew Ghio wrote:
Having identical plaintexts raised to the same power modulo different numbers makes the solution much easier. If you have enough RSA encryptions of the same number to the same power, you can solve it outright by the remainder theorem.
So if I wanted to do this and use RSA, how could it be shielded from attack? I take it switching to DH or MH won't help. Would Eliptic Curves have different properties against this attack? Maybe a random session key in the middle would help? i.e.: File[N]=RSA(PublicKey[n],RandomSessionKey[N]+IDEA(SessionKey[N],Data)) =====================================Kaos=Keraunos=Kybernetos============== .+.^.+.| Ray Arachelian |Prying open my 3rd eye. So good to see |./|\. ..\|/..|sunder@sundernet.com|you once again. I thought you were |/\|/\ <--*-->| ------------------ |hiding, and you thought that I had run |\/|\/ ../|\..| "A toast to Odin, |away chasing the tail of dogma. I opened|.\|/. .+.v.+.|God of screwdrivers"|my eye and there we were.... |..... ======================= http://www.sundernet.com ==========================
So if I wanted to do this and use RSA, how could it be shielded from attack? I take it switching to DH or MH won't help. Would Eliptic Curves have different properties against this attack?
Maybe a random session key in the middle would help?
Using a salt would work. DH would be okay if you used DH to exchange a different key with each recipient and then conventionally encrypted the message with that key. The point is that you need to use different (random) inputs to each P-K operation in order to avoid the possibility of ending up with a system of equations that could be solved.
participants (7)
-
Alan -
amp＠pobox.com -
Bill Stewart -
ghio＠temp0107.myriad.ml.org -
Matthew Ghio -
nospam-seesignature＠ceddec.com -
Ray Arachelian