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 ---

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.

> > 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.)