nullprogram.com/blog/2008/07/15/
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, k1
and k2
. You have two
messages, m1
and m2
. We then have four transmitted texts:
two encrypted message pads e1
and e2
, and two
ciphertexts c1
and c2
. We define these as,
e1
= K
^ k1
e2
= K
^ k2
c1
= k1
^ m1
c2
= k2
^ m2
Suppose an adversary is able to record all four transmitted texts. He
can apply them like so,
e1
^ c1
= K
^ k1
^ k1
^ m1
= K
^ m1
e2
^ c2
= K
^ k2
^ k2
^ m2
= K
^ m2
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,
e1
^ e2
^ c1
^ c2
= m1
^ m2
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.
Update: My friend Gavin thought he discovered a way to make
one-time pads useful, but I was able to show him that it simply
reduces to the same situation
here. His
website (dead link now) details the algorithm and the crack
that breaks it.