2

This might well be a silly question, but at the moment I've not thought of a reason it doesn't work.

As I think is generally known, you should never re-use a one-time pad. But compression allows you to transmit something larger than the number of bytes used in transmission...

I'm not intending to / have no reason to do this but thought it was an interesting idle thought wondering why you can't:

  • establish initial one-time pads securely with someone.
  • communicate using the pads, and when it gets near the end, transmit a knew (compressed) one-time pad, which you both subsequently use.

(I realise the ratio of data vs pads in your throughput might be pretty terrible).

I'm assuming someone strong on maths might be able to explain that if the algorithm is known it might be possible to break it because in a way data is being 'reused', though in an encrypted, compressed form the first time, as the key the second.

If the security does degrade, at what point/how much? (Assuming neither ends have the conversation have been compromised).

edit: thanks for looking guys, I forgot that random data is hard to compress; question answered.

pacifist
  • 794
  • 3
  • 8
  • Why do you think OTP is secure/insecure depending on the content of the message Alice wants to send to BoB? – dfc Mar 28 '14 at 00:01
  • ... I'm not sure I follow? I'm aware that repeated pads will throw the entropy off, so I'm open to the concept that transmitting pads (even compressed) might do the same. Is that what you mean? – pacifist Mar 28 '14 at 00:05
  • 2
    Since the OTP is supposed to be crytographically secure random data, it should not be compressible at all. – Johnny Mar 28 '14 at 00:08
  • Are we assuming the OTP is securely implemented, transferred and used? – dfc Mar 28 '14 at 00:09
  • It is also worth pointing out that "compression allows you to transmit something larger than the number of bytes used in transmission" is not true for random data. Try `dd if=/dev/urandom of=rand bs=1024 count=10000 ; xz -k rand ; du -b rand rand.xz` – dfc Mar 28 '14 at 00:14
  • you guys are absolutely correct; not sure whether to delete the question, but it all seems to hinge around (my up-for-debate assertion) whether you can compress random data. I'd assume with fancy enough compression (each end keeping a big dictionary etc) you might be able to, but perhaps not: http://www.drdobbs.com/architecture-and-design/the-enduring-challenge-of-compressing-ra/240049914 – pacifist Mar 28 '14 at 00:26
  • @pacifist - There is no question about whether or not you can compress random data. Compression works by looking for patterns and redundancies in the data and optimizing them out, and by definition, random data has no patterns or redundancies except what might occur by chance. A dictionary large enough to compress random data would be as large as the random data itself. Well compressed data looks a lot like random data (but it's not), so if it were possible to compress random data, you could keep compressing a compressed file over and over again until it was down to a single byte (or bit). – Johnny Mar 28 '14 at 02:00

1 Answers1

6

This isn't possible/feasible, for two reasons.

  1. Compression doesn't "work" on random data - it won't actually significantly reduce the size of your data, and in fact, may increase the size.

  2. A one time pad must be greater than or equal in length to the data being encrypted.

    • So if you're using the "remaining," unused part near the end of your one time pad to transmit a new one time pad, you're going to end up with a very small "new" one time pad... and the same problem that you're almost near the end of it.
HopelessN00b
  • 3,385
  • 19
  • 27