[117585] in Cypherpunks
Re: Build a better OTP?
daemon@ATHENA.MIT.EDU (lcs Mixmaster Remailer)
Mon Sep 6 17:36:23 1999
Date: 6 Sep 1999 21:20:05 -0000
Message-ID: <19990906212005.14091.qmail@nym.alias.net>
To: cypherpunks@cyberpass.net
From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
Reply-To: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
> Here is a purely hypothetical scenario. Party A decides to send a
> communication to Party B which, even years later, could haunt them.
> To overcome the possibility of later analysis even years later, party
> A uses a public key encryption, not to directly encrypt the channel,
> but instead to instruct party B to tune in to a certain channel on a
> satellite. This being after party A spent a few seconds ensureing
> that the channel truly did have enough entropy to use as a key. With
> both XORing thier communication channel with the raw output of the
> satellite signal, and with an additional layer of conventional
> encryption just in case, they proceed to speak freely, unconcerned
> with the fact that thier communication is being recorded by some
> organization aligned counter to themselves.
>
> Now, 2 weeks later, that organization, party C, has finally broken
> through the encryption. To his dismay, the only truly readable
> portion says, in some protocol, to "tune in to channel 23 of
> satellite number 81 and XOR the data with that and then encrypt with
> this." Because he didn't have the forsight to record EVERY SINGLE
> BIT that was broadcast by the multitude of satellites in the sky, he
> can't reconstruct the data. Hence, it is secure until someone learns
> to reach back into the past for a single radio signal.
This is a good idea, although there is always the danger that C
actually will have the resources to record EVERY SINGLE BIT broadcast
by the satellites. In practice there may not be that many satellites
that are suitable. On the other hand it doesn't actually have to be
a satellite, it could be some natural phenomenon like a star or some
other natural source of radiation. Note that there is a limit in that
the communicators both need line of sight to a common source.
If you're going to do this, consider the enhancement described by Ueli
Maurer, "Protocols for Secret Key Agreement by Public Discussion Based
on Common Information", from Crypto 92. A slightly different version
is avaiable from http://www.inf.ethz.ch/personal/maurer/publications.html:
"Abstract: Consider the following scenario: Alice and Bob, two parties who
share no secret key initially but whose goal it is to generate a (large
amount of) information-theoretically secure (or unconditionally secure)
shared secret key, are connected only by an insecure public channel to
which an eavesdropper Eve has perfect (read) access. Moreover, there
exists a satellite broadcasting random bits at a very low signal power.
Alice and Bob can receive these bits with certain bit error probabilities
e_A and e_B, respectively (e.g. e_A = e_B = 30%) while Eve is assumed
to receive the same bits much more reliably with bit error probability
e_E << e_A, e_B (e.g. e_E = 1%). The errors on the three channels are
assumed to occur at least partially independently. Practical protocols
are discused by which Alice and Bob can generate a secret key despite
the facts that Eve possesses more information than both of them and is
assumed to have unlimited computational resources as well as complete
knowledge of the protocols."
Here the main assumption is that there is some natural noise in the
signals, and although the eavesdropper may have superior technology,
they still are subject to some level of noise.
The basic idea of the protocol can be described as follows. Alice
receives satellite bits, as do Bob and Eve. If we use the figures above,
30% of Alice's bits will be wrong, a (possibly) different 30% of Bob's
will be wrong, but only 1% of Eve's will be wrong.
Alice groups her bits into sets of N, and sends either all N bits or
the complements of all N bits. Bob compares this group of N with his
own data, and tries to determine whether it has been complemented or not.
The safest strategy for Bob is to require that either all N bits match
his, or the complement of all N bits match his. This won't happen that
often but when it happens he has good reliability that he has determined
the "complementation bit, 0 vs 1". If Bob can't tell, he discards the
bits. Bob tells Alice which bits he was able to accept.
Meanwhile, Eve is sitting there and doing the same thing. Because
Eve's data is more reliable, she has a good chance of learning the
complementation bit. But if you make N large enough, both Bob and Eve
have a low probability of learning the value of the bit for any given
packet. If you then accept just those packets where Bob got lucky and
recognized the bit, Eve's probability of being lucky on those packets
is as low as ever, hence she probably doesn't know that bit.
It's basic probability theory. Suppose Bob has one chance in a million
of getting lucky on each packet, but Eve has one chance in a thousand.
If you do a million packets then Bob gets lucky on one of them. But
Eve's chances on that packet are still one in a thousand.
Actually Maurer recommends doing this in multiple stages, using something
like N=3 at each time. This does not reduce Eve's information much at
any stage, but over multiple stages it is just as good as a large N,
with less data being discarded. This way you can get a practical amount
of data out of the system for Alice and Bob to share.
