[117596] in Cypherpunks
Re: Build a better OTP?
daemon@ATHENA.MIT.EDU (Sean Roach)
Mon Sep 6 20:19:30 1999
Message-Id: <3.0.6.32.19990906184415.007f07b0@mail.intplsrv.net>
Date: Mon, 06 Sep 1999 18:44:15 -0500
To: cypherpunks@algebra.com
From: Sean Roach <roach_s@mail.intplsrv.net>
In-Reply-To: <19990906212005.14091.qmail@nym.alias.net>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Reply-To: Sean Roach <roach_s@mail.intplsrv.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
At 09:20 PM 9/6/99 -0000, lcs Mixmaster Remailer wrote:
>
>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.
Yes, which is why I figured on satellites. My TV reception off my
mini-dish is pretty clear, being in essence, a broadcast collection
of MPEG encoded streams. Granted, the number of satellites is
finite, but you need a much smaller number of receivers to get the
raw data from any one of them while preserving the ability to access
all of them.
If you were to focus on the sun as a standard, you have limited your
choices down to a much smaller number which can be determined by the
equipment you have set up outside. The same goes for stars. Since a
person who might have the resources to set this up once, perhaps with
dual-use equipment, like a satellite dish that he also uses to get
ESPN, might not have the resources to do it twice, I figured that the
whole of the Clarke belt which both parties can reliably see, would
be a better source for a key.
>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:
I'll have to read up on it next time I connect for an extended time.
I only have access to one phone line and its use is limited during
the day.
>"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.
>
This looks like it might be good for file transfers, but that negates
some of the use toward real time communication, as it means that only
1 in 1,000,000 attempts to transmit the data works, and thus looks
very slow.
Granted real-time communication only really beats the equivalent of
e-mail and phone-tag because it gives the people participating the
opportunity to immediately respond with feedback, while otherwise
using far less of the total bandwidth than it is allotted.
I'm a little rusty on the numbers, but they look good.
I was really considering something more akin to the current use of
PGP and SSL. Where a secure, but slow, public key system is used to
provide the initial safety in which to figure out a more secure
channel which can be handled faster by the hardware. In this case,
instead of being, as it was posted here a few hours ago, a "symmetric
cypher", or in addition to that, information on where, and when, to
look to the skies.
My idea was not to deny the ability to crack the code. But rather to
deny the ability to crack the code long enough that a key portion no
longer existed to use. Basing my idea on the assumption that no-one
would even try to record every transmission from every man-made
object in orbit or anywhere else for that matter, indefinately, on
the off-chance that it might someday become useful.
In my scenario, it becomes not an issue of who gets the best
reception, rather it assumes that everyone can get enough signal on
the first pass to generate the same key. It becomes a matter of who
can archive all of that data for future analysis.
And yes, if two people are at sufficient distances from one another,
the choices of satellites are actually thinned to the point where it
does become feasable to record all of the output.
I guess the main point is this. I can see the NSA maintaining acres
of computers with which to attack the codes of the enemies of the
state as it currently stands, but I fail to see them doing the same
thing, to any workable degree, with every broadcast transmission
which hits a little less than half the planet. The reason I fail to
make this leap is that, although the computers hacking at the code
will eventually finish and be assigned to other tasks, thus
validating their expense, the same can't be said for stored data.
Any given bit of text may never be useful. The threat I see to my
scheme is the further development and adoption of data on demand. If
you have to ask for it, all of the anonymity of getting it is
potentially lost. Which is also why I suggested pirate TV and radio
broadcasts as a means toward dissemenating information to the masses.
With no request for data, who's to know who listened?
Sean Roach
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.1 for non-commercial use <http://www.pgp.com>
iQA/AwUBN9RRzpHDoiHtqFDZEQJl9wCg3lmXIaCQvhtEgKgtXXHfZOFjXWEAn0gW
m1kkQB2xl/xD+MbLhBxLX7qg
=S9SO
-----END PGP SIGNATURE-----
