"Random flood" crypto
mike3
I read this, it looks pretty old given the date though, but I was
curious about the idea as it seemed kind of weird:
http://www.developer.com/tech/article.php/742151/An-Unbreakable-Code.htm
which suggests a type of "cryptography" that involves transmitting a
huge "flood" of random data, such that only a tiny part is relevant to
ciphering the message. It says that "RSA is unbreakable if no one has
a big enough computer to break it. This new system is unbreakable if
no one has a big enough tape recorder." But would it offer any
advantage to more conventional forms of cryptography? For example it
requires an initial key distribution step, if you compromise that then
you don't need the huge tape deck any more, same as goes with a
conventional symmetric cipher. So what's the advantage? More
importantly: what is the advantage over the one-time pad? A simple one
time pad system -- which this looks to be a modification of -- would
provide the same level of security, and is much simpler to implement.
If the initial agreed-upon pad is so big that it will never run out
for the entire working lifetime of the device given the length of
messages that are sent, then there needs to be only one agreement
step, and this could be perfectly feasible for, e.g. a pair of text
transmission terminals, given the small size of text messages. If the
pads are stolen then that compromises all future messages but not past
ones, same as if the key for the flood machine is stolen.
Joseph Ashwood
news:05999ff6-b033-49e3...@x15g2000vbr.googlegroups.com...
> Hi.
>
> I read this, it looks pretty old given the date though, but I was
> curious about the idea as it seemed kind of weird:
>
> http://www.developer.com/tech/article.php/742151/An-Unbreakable-Code.htm
It's a variation of Rivest's Wheat and Chaff, there have been many
resuggestions of it as "unbreakable"
>
> which suggests a type of "cryptography" that involves transmitting a
> huge "flood" of random data, such that only a tiny part is relevant to
> ciphering the message. It says that "RSA is unbreakable if no one has
> a big enough computer to break it. This new system is unbreakable if
> no one has a big enough tape recorder."
That's a very weak proof. In fact it isn't a proof at all. Let me choose
limits for the attacker and I'll prove anything secure. I choose my attacker
to be completely incompetent and doesn't even know how to turn on a
computer, ROT-13 is perfectly secure, even ASCII offers superior security.
> But would it offer any
> advantage to more conventional forms of cryptography?
Depends. Do you have infinite download resources? If your download resources
are finite then the attacker can simply parse it to what you can download
and *poof* its breakable.
> For example it
> requires an initial key distribution step, if you compromise that then
> you don't need the huge tape deck any more, same as goes with a
> conventional symmetric cipher. So what's the advantage?
There's a reason it isn't actually used, that reason is that it doesn't have
any real advantage.
There have been many, many variations of this, some using multiple sources,
some using this kind of flood, some that miraculously assume you have
infinite comptue resources but the attacker doesn't, etc. None of them are
in use because none of them are actually useful.
Joe
Mok-Kong Shen
> "mike3" wrote:
>> http://www.developer.com/tech/article.php/742151/An-Unbreakable-Code.htm
>
> It's a variation of Rivest's Wheat and Chaff, there have been many
> resuggestions of it as "unbreakable"
What's the latest concensus of experts on the security and (above all)
practicability of such schemes? Could somebody kindly give references?
Thanks.
M. K. Shen
Joseph Ashwood
"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:heg9de$p4q$02$1...@news.t-online.com...
Do you ever read what you are replying to?
You quoted a fairly reasonable summary answering one of your questions, and
trimmed the answer to the other.
Security: People keep claiming they are unbreakable, people keep being
wrong.
Practicality: "Do you have infinite download resources? If your download
resources are finite then the attacker can simply parse it to what you can
download and *poof* its breakable."
From an analytic standpoint all this does is blind the suggestor to the fact
that it is just a stream cipher, and how you choose the bits to use is more
important than the bits chosen. They always miraculously assume that the
numbers are selected purely randomly (a perfect CSPRNG is used for
selection), as such the "proof" is that encrypting random bits is at least
as secure as the underlying encryption function, it is trivial to do better
based on unicity distance. The correct proof was supplied by Rivest, proving
that this is effectively an inflating stream cipher and is exactly as secure
as the underlying number generator. You probably wouldn't understand the
proof, but Chaffing and Winnowing: Confidentiality without Encryption
by Ronald L. Rivest. CryptoBytes (RSA Laboratories), volume 4, number 1
(summer 1998), 12--17. Rivest has some more recent statements dating to
2000.
So did you understand the answers this time? Probably not.
Joe
Mok-Kong Shen
>
> So did you understand the answers this time? Probably not.
I asked my question because I remember years ago, when the scheme
of Rivest became known, there were quite some discussions in the
group, and, if my memory is right, not everybody's opinion was
in favour of it. So I wanted to know whether this state of affairs
has changed during the relatively long period I didn't subscribe
to sci.crypt.
M. K. Shen
mike3
> "Mok-Kong Shen" <mok-kong.s...@t-online.de> wrote in message
<snip>
> From an analytic standpoint all this does is blind the suggestor to the fact
> that it is just a stream cipher, and how you choose the bits to use is more
> important than the bits chosen. They always miraculously assume that the
> numbers are selected purely randomly (a perfect CSPRNG is used for
> selection), as such the "proof" is that encrypting random bits is at least
> as secure as the underlying encryption function, it is trivial to do better
> based on unicity distance. The correct proof was supplied by Rivest, proving
> that this is effectively an inflating stream cipher and is exactly as secure
> as the underlying number generator.
I'm curious about this here. Wouldn't one use a true random number
generator (TRNG) for the bit generation instead of an algorithmic one?
Also, what about the key distribution -- isn't this thing only as good
as
the initial key distribution and so no better than a symmetric cipher
or
the plain OTP? If so, why focus only on the random generator?
David Eather
in encrypted data only when required. It is TLA's "onion router"
Joseph Ashwood
news:me6dneIi6aOgA5HW...@supernews.com...
> Joseph Ashwood wrote:
>> "mike3" <mike...@yahoo.com> wrote in message
>> news:05999ff6-b033-49e3...@x15g2000vbr.googlegroups.com...
>>> http://www.developer.com/tech/article.php/742151/An-Unbreakable-Code.htm
>> There's a reason it isn't actually used, that reason is that it doesn't
>> have any real advantage.
>>
> Um, actually most embassies transmit random data continuously and slip in
> encrypted data only when required. It is TLA's "onion router"
Two problems.
First, that is a very different structure than the subject. It is winnowing
and chaffing, but is not the random flood.
Second, embassies don't do that. Embassies use scheduled bursts, they have
specific times they send a set size. Exceptions can be made for extreme
priority or low security. The frequency of the bursts depends on the
embassy, US-China has higher frequency than say Eritrea-Russia, direction
doesn't matter much the frequency will be close in both directions. This can
be proven security equivalent but costs less and is more dependable.
Joe
Mok-Kong Shen
> ......... Embassies use scheduled bursts, they
> have specific times they send a set size. Exceptions can be made for
> extreme priority or low security. The frequency of the bursts depends on
> the embassy, US-China has higher frequency than say Eritrea-Russia,
> direction doesn't matter much the frequency will be close in both
> directions. This can be proven security equivalent but costs less and is
> more dependable.
I understand that 'scheduled' and 'specific' above imply that the time
of transmission is certain fixed times of the day. If so, wouldn't it
be better to tell in a message the time the next transmission is going
to be and perhaps also the frequency (if that could be chosen and not
fixed)? One could of course at any arbitrarily time (and frequency)
send any random stuff (without requiring the partner to pay attention
to that) in order to confuse the opponent.
M. K. Shen
David Bernier
I think this might be related to the "tor" discussed at EFF:
<
http://www.eff.org/deeplinks/2009/06/help-protesters-iran-run-tor-relays-bridges
>
and here:
< http://www.torproject.org/index.html.en >
David Bernier
Mok-Kong Shen
> I think this might be related to the "tor" discussed at EFF:
>
> http://www.eff.org/deeplinks/2009/06/help-protesters-iran-run-tor-relays-bridges
>
> and here:
> < http://www.torproject.org/index.html.en >
Interesting. On the other hand, I am afriad it's always a very hard
competition between those support/desire freedom and privacy and those
anti- or pseudo-democratic regimes that suppress freedom and privacy
(either publically or secretly) of people, and nothing would go under
a situation comparable to the time, say, under Stalin in the Soviet
Union in the recent history.
M. K. Shen
David Bernier
There's a web site "Chilling Effects":
< http://www.chillingeffects.org/ >
They're in part sponsored by the Electronic Frontier Foundation,
which is a strong advocate of privacy over the Internet.
Recently, there was a story there:
"German Murderer Threatens to Censor Wikipedia"
< http://www.chillingeffects.org/weather.cgi?WeatherID=620 >
W. W., a convicted murderer in Germany who was recently paroled,
hired the law firm Stopp and Stopp.
The la firm sent a letter to the Wikimedia Foundation threatening legal
action if Wikipedia continued to mention W. W. in the article
on the deceased actor Walter Sedlmayr ( d. 1990) .
W. W. was convicted of murdering Sedlmayr.
While Sedlmayr is a public figure, it's argued that
mentioning W.W. in the wikipedia article on
Sedlmayr won't help the rehabilitation of W.W.,
etc .
----------
Another case is a semi-retired investigative journalist who
investigated his late mother for hiding a family secret.
The mother had a sister who was institutionalized. There
was a family secret about the life of the journalist's aunt,
Annie.
The book is called "Annie's Ghosts: A Journey Into a Family Secret"
by Steve Luxenberg. Privacy laws on the census records didn't help
his investigation.
David Bernier
Mok-Kong Shen
> There's a web site "Chilling Effects":
>
> < http://www.chillingeffects.org/ >
>
> They're in part sponsored by the Electronic Frontier Foundation,
> which is a strong advocate of privacy over the Internet.
EFF's steadfast efforts for freedom of privacy are to be highly valued
and admired. Nonetheless, when one reads news about censorships by
certain countries on internet access by civilians (or on the other
hand the competing preparations by some mighty nations on eventual
cyber wars), one couldn't help but feel oneself 'chilled'.
M. K. Shen
David Eather
Ok. (and thanks for the correction)
Mok-Kong Shen
> ....... Embassies use scheduled bursts, they
> have specific times they send a set size.
BTW, besides embassies there are also the numbers stations:
http://en.wikipedia.org/wiki/Numbers_station
An acquaintance of mine who has an amateur radio station told me
that there exist indeed many such numbers stations today.
M. K. Shen
Joseph Ashwood
There are still various broadcast points that no one publicly admits the
purpose. If I was to guess (as I don't know the real truth), I'd guess that
they are relics, maintained because it is cheap and just in case it is
needed. I say this because there's no current need for the locations I know
of. As an example, I know of a few in the US where the broadcast location is
apparently US-owned, there should be no purpose for them, but they exist.
Setting up a number station is relatively cheap, a computer can easily
repeat random data, a few thousand dollars will create a deliverable, and
with modern satellite dishes a single marine can easily deliver one almost
anywhere to broadcast randomly for years with no purpose. Compare a few
thousand dollars to the cost of random flyovers by any airplane over the
same time and the station is a superior strategic weapon to force your
opposition to spend money on sig int. This makes the number station a
valuable tool. The just in case, a number station system makes a good worst
case scenario, if there have been years of random broadcasts in a region
then a spy actually using a number station is relatively safe, add your own
security implementations. So it exists for the same reason that militaries
still train in using a knife, if it has to be used, you've already lost, but
it as worst cases go it isn't th worst.
Joe
Mok-Kong Shen
> There are still various broadcast points that no one publicly admits the
> purpose. If I was to guess (as I don't know the real truth), I'd guess
> that they are relics, maintained because it is cheap and just in case it
> is needed. I say this because there's no current need for the locations
> I know of. As an example, I know of a few in the US where the broadcast
> location is apparently US-owned, there should be no purpose for them,
> but they exist. Setting up a number station is relatively cheap, a
> computer can easily repeat random data, a few thousand dollars will
> create a deliverable, and with modern satellite dishes a single marine
> can easily deliver one almost anywhere to broadcast randomly for years
> with no purpose. Compare a few thousand dollars to the cost of random
> flyovers by any airplane over the same time and the station is a
> superior strategic weapon to force your opposition to spend money on sig
> int. This makes the number station a valuable tool. The just in case, a
> number station system makes a good worst case scenario, if there have
> been years of random broadcasts in a region then a spy actually using a
> number station is relatively safe, add your own security
> implementations. So it exists for the same reason that militaries still
> train in using a knife, if it has to be used, you've already lost, but
> it as worst cases go it isn't th worst.
Excellent insight, I believe.
BTW, years ago I had the idea that, if most users of the internet
would regularly add at the end of each of their e-mails, usenet
postings, web publications, etc. a few lines of random (dummy)
characters, then the supercomputers of certain agencies would be
bogged down due to overload. Thus freedom of privacy could be
practically achieved through a little bit of concerted collective work.
M. K. Shen