null program

15 Jul 2008

A One-Time Pad Mistake

In a previous post I discussed one-time pads. Note: this is about a cryptosystem, not some kind of menstruation disaster. The information for this post comes from a little gem I saw on the xkcd forums. I generally don't lurk around there because it suffers from the same disease most non-self-moderating forums suffer from: anal retentive, power-abusing, whiny moderators. I lucked out this time.

The user Berengal posed the question,

One thing I've been wondering about is if you can use a single one-time-pad to encrypt other one-time-pads to send around.

My first though was, "Hey, why didn't I think of this?". Then, after a moment, I realized that it was the sort of thing that is too good to be true. This is along the lines of ideas that break the laws of thermodynamics. We are looking at a perpetual motion machine here. Just as you cannot create or destroy energy, neither can you use a one-time pad to distribute more than one other equal length one-time pad. Let's make it formal,

In any closed one-time pad cryptosystem, the total number of one-time pad bits in the system remains the same.

Also, if something like this could work, people would be using it already everywhere. Before I got a chance to think too much about it, user AJR spoiled it with an excellent proof on why it won't work.

Note below that I use ^ to indicate exclusive or (XOR).

Suppose you have a master pad, K, that you use to distribute two message pads, k₁ and k₂. You have two messages, m₁ and m₂. We then have four transmitted texts: two encrypted message pads e₁ and e₂, and two ciphertexts c₁ and c₂. We define these as,

e₁ = K ^ k₁
e₂ = K ^ k₂

c₁ = k₁ ^ m₁
c₂ = k₂ ^ m₂

Suppose an adversary is able to record all four transmitted texts. He can apply them like so,

e₁ ^ c₁ = K ^ k₁ ^ k₁ ^ m₁ = K ^ m₁

e₂ ^ c₂ = K ^ k₂ ^ k₂ ^ m₂ = K ^ m₂

This cancels the original message keys and effectively leaves you encrypting two messages with the same pad, which is exactly the wrong thing to do when using one-time pads. Once that is done, the adversary can do tricks like,

e₁ ^ e₂ ^ c₁ ^ c₂ = m₁ ^ m₂

What is left is the two messages XORed together with no keys/pads involved, which, depending on the messages, might reveal something. Don't make this mistake.

[] permanent link

Don't stop here! This isn't everything. Check out the archives (on the left) for more posts. Or just have a look at the index.