Cryptography-Digest Digest #758, Volume #9 Thu, 24 Jun 99 04:13:03 EDT
Contents:
Re: Secure broadcast ("Gene Sokolov")
Re: one time pad (Jerry Coffin)
Re: Kryptos article ("Douglas A. Gwyn")
Re: one time pad ("Douglas A. Gwyn")
Re: Sexual Contact Privacy :) ([EMAIL PROTECTED])
Re: "Breaking" a cipher (Jerry Coffin)
Re: one time pad ("Douglas A. Gwyn")
Re: one time pad ("Douglas A. Gwyn")
Re: one time pad (Greg Ofiesh)
Re: Encryption Algorithm Functional? ("Douglas A. Gwyn")
Re: Arbitrary Huffman tree and weights distribution (was: huffman code length) (Alex
Vinokur)
Re: Converting arbitrary bit sequences into plain English texts (Boris Kazak)
Re: one time pad (Jerry Coffin)
----------------------------------------------------------------------------
From: "Gene Sokolov" <[EMAIL PROTECTED]>
Subject: Re: Secure broadcast
Date: Thu, 24 Jun 1999 10:11:31 +0400
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > Yes, it is too expensive. That's why in I.1 I wrote how much data is
worth
> > ($500/month). I guess "too expensive" starts at about $10K.
>
> You may be underestimating the value of a cracked password. The threat
> model you presented includes only potential customers using your data
> without paying for it. What about competitors? A competitor could
> spend $500,000, twice what a 56-bit cracker cost a while ago, and recoup
> the investment in one year with only a hundred
> customers.
That's really not an issue. The competition can pay $500/month and then
rebroadcast the data. No need to spend half a million. Or, even easier, then
can buy this data from us over the Internet - it's cheaper. But, we know our
competition. If they start reselling our data, we can always sue them.
Individuals are seen as the primary threat.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 00:18:24 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> If you assume that a plausibly valid message is all ASCII, you have about
> 100^100 messages to eyeball. Assume that there are spaces on the average
> every five letters, and you have about 80^100 potential messages.
>
> So far, your computer has rejected a huge number of messages, so huge that
> it cann't be done.
The problem isn't with the number of messages involved. The problem
is that if you supply all possible keys, you'll get EVERY message you
consider plausible. I.e. the original message will have no effect on
what you get -- only the preconceptions YOU bring into it will. If
you decide that messages that contain only characters from 32 to 127
(I.e. printable ASCII characters) are plausible, you'll get EVERY
possible sequence of characters in that range.
> >And then you look through the list only to discover one plain text
> >candidate actually has 100 0xa7's and the message looks valid to you.
>
> How many aeons did you say you had to look through this list?
It's irrelevant. The point is that as long as 100 0xa7's in a row is
exactly as likely as any other sequence of 100 characters, the
attacker has no better idea that this particular decryption is valid
compared to all the others that his criteria says are plausible.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Thu, 24 Jun 1999 06:50:25 GMT
Jerry Coffin wrote:
> I think in this case, their cracking it long before the rest of us
> mostly had to do with their having easy access to it before the rest
> of us did. I'm not sure when Jim started working on the problem, but
> from what he's said, it sounds like once he started working on it, he
> cracked it in less time than they did...
Since I posted an accurate transcript of the Kryptos ciphertext
several years ago, there has been plenty of time to work on it.
(ACA's The Cryptogram published a slightly incomplete and slightly
inaccurate version in the MA92 issue, which was the start of my
quest for the complete, accurate text.)
Jim took about 9 days, I think, not counting a preliminary
glance at it earlier and his previous investment in constructing
general cryptanalytic tools (computer and otherwise). Also not
counting the time previously invested in learning and practicing
cryptanalysis. (Practice is more important than you might think.)
I think there are several other people who *could* have cracked
Kryptos to the same degree, but didn't have the motivation or time.
It would be nice if somebody would get that last piece of Kryptos
deciphered.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 06:21:35 GMT
Greg Ofiesh wrote:
> Let me begin by saying this is the first time here, and I am quite
> surprised at how some people participate here. I wish my
> correspondences to remain at the highest technical level possible.
How ironic...
> First, in my first post, I used the term "statistical" randomness.
> It is a term I received when reading about PI, which is supposively
> the most statistically random sequence of digits known to man.
Supposed by whom?
> Also, a OTP's strength is entirely found in the fact that given a
> cipher stream only, any plain text stream is an equal candidate to
> be the true plain text.
No, that is patently false. "Oryx blfp mophh" is less likely to be
the plaintext than is "Need more funds".
> does it make sense that randomness is a requirement, that patterns
> must be avoided, in building a one time pad?
No, suppressing "patterns" *reduces* the randomness of the keystream.
There is one caveat: The pad generator may break down, so it is
useful to monitor the keystream being produced in order to detect
such an occurrence and thereby avoid using the output of a process
that has become insufficiently random for the intended purpose.
There are plenty of elementary treatises on probability and
statistics that cover the topic of "randomness" well enough to
address the kinds of questions you raise. It would be more
efficient to find one and read it than to try to obtain
reliable, thorough instruction through a net news group.
------------------------------
Date: Wed, 23 Jun 1999 04:39:35 -0400
From: [EMAIL PROTECTED]
Subject: Re: Sexual Contact Privacy :)
There may also be those interested in supervising the sexual practices
of the population who use the database for such purposes. A recent
paper in teh Journal of the ACM, "Private Information Retrieval", Vol
45, #6, inspect the problem of hiding the nature of queries against a
database. The basic threat model is one where an adversary can infer
the subject of the querant's search by inspecting the results returned
byt the database.
If the results of a database query are a list of possible/suspected
sexual contacts a snooper could make much trouble with the act of
submitting a query.
Karel Wouters wrote:
>
> On 20 Jun 1999, Doug Goncz wrote:
>
> > It is for the good of the public that the government or a health agency might
> > wish to keep records of sexual contacts between people. On the other hand, the
> > individuals involved usually wish to retain this information as private. There
> > is the possibility that an agency could misuse the information.
>
> You'll have to define sexual contacts ...
> and as showed in the past year, Americans may have some problems with that
> :-))))
> ("I did _not_ have any sexual relationship with Ms. XXXXXXXX")
>
> This sounds like flame bait ...
>
> [snip]
>
> Karel w
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: "Breaking" a cipher
Date: Thu, 24 Jun 1999 00:18:26 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> It's wonderful -- the decryptor can choose any message with equal
> justification, so long as it's the right length. So if you're the police,
> just pick the one that's the most incriminating.
If you're trying to do this, you simply start with the message you
want as output, do a bit of math, and you can find what the key would
had to have been to produce that ciphertext from the plaintext you've
chosen.
Likewise, if the person involved is smart, he can figure out a
complete innocent plaintext message and corresponding key to display
to the police to prove their accusation wrong.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 06:30:20 GMT
Greg Ofiesh wrote:
> You cannot say this with OTP. OTP, even if rough, as long as it
> lacks any obvious conclusions, does not let an attacker have a clue
> as to which candidate is correct. In this lies the guarantee (it
> would seem to me) that OTP cannot be broken, even in rough
> implementation.
However, several one-time pad systems have in fact been broken by
cryptanalysis. One that has achieved some measure of fame can be
found under "VENONA" on the NSA Web site.
The point is, in actual application, one-time pad systems have
several weaknesses that the theoretical OTP systems don't. The
two obvious ones are generation of truly random key and
distribution of the large volume of key material needed for such
a system.
Isn't all this in the sci.crypt FAQ?
> ... If a pure and perfect (okay, theoretical) random generator
> can produce any sequence of bits, and no bit is dependent on any
> other, then you could theoretically produce streams of obvious
> patterns.
Not only could, but do.
> And this should produce weaknesses in the pad.
No, it doesn't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 06:36:02 GMT
Terry Ritter wrote:
> Nope. Finding "patterns" in known random data is not the problem.
> The problem is any ability to *predict* specific patterns.
More relevantly, for every correct good plaintext produced using a
regular pattern as trial key, there are vastly more incorrect good
plaintexts produced by using other regular patterns as keys against
other OTP ciphertexts. So what clue does the cryptanalyst have that
*this* good plaintext is any more correct than it was those zillions
of other times (in his Methuselah-like lifetime) when he obtained
good plaintexts that turned out to be incorrect decryptions?
------------------------------
From: Greg Ofiesh <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 06:45:15 GMT
> Not always. Some techniques can have sufficient keyspace to produce
> every possible encryption for messages of some maximum length.
I have never heard of anyone using such a technique to find a single
private key. What ever do you mean? How, may I ask, could you find a
private key with such a technique?
> In any case, we believe that finding the correct key can be very, very
> difficult. It does not seem to matter much that only one possibility
> will fit the mold if we cannot find that one possibility.
Difficulty is not an issue. The number of candidates to choose from is
the issue. This is mathematical proof of OTP's security guarantee.
Since you can NEVER determine which is correct, you can NEVER crack the
cipher stream.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Encryption Algorithm Functional?
Date: Thu, 24 Jun 1999 06:53:11 GMT
"Nathan A. Baker" wrote:
> Is there a similar formulation for cryptographic problems?
Not anything particularly helpful, although there are of course
many other useful mathematical models and methods.
------------------------------
From: Alex Vinokur <[EMAIL PROTECTED]>
Crossposted-To: comp.compression,alt.comp.compression,sci.math
Subject: Re: Arbitrary Huffman tree and weights distribution (was: huffman code length)
Date: Thu, 24 Jun 1999 06:56:12 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Alex Vinokur wrote:
> >
>
> > ----------------------------
> >
> > Stage#2 : 49 (51)
> > L R
> >
> > 100
> > /\
> > / \
> > 49 51
> > /\
> > / \
> > 3 48
> > /\
> > / \
> > 1 2
> >
>
> At each level the nodes are sorted. But the terminal nodes are
> not sorted.
The terminal nodes are sorted on stage#0 of Huffman algorithm. As far as the
terminal nodes are concerned It is enough. See example in my message :
http://x21.deja.com/getdoc.xp?AN=492905747&CONTEXT=930200759.400228377&hitnum
=3 http://www.deja.com/getdoc.xp?AN=492905747&fmt=text
> Would this matter for you in proceeding further to obtain
> the range of variation of the frequency distributions of (terminal)
> nodes where the frequncies are sorted (the problem I originally
> asked)?
>
A-conditions and B-conditions require that the (internal an terminal) nodes
be sorted at each level. See my original message :
http://x29.deja.com/getdoc.xp?AN=489813355&CONTEXT=930200784.2102591510&hitnu
m=15 http://www.deja.com/getdoc.xp?AN=489813355&fmt=text A-conditions and
B-conditions require no other sorting. So (I think) we can obtain the range
of variation of the frequency distributions of terminal nodes (the very
interesting problem you originally asked). But (I sure) this problem requires
additional research.
> M. K. Shen
>
Regards,
Alex
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Wed, 23 Jun 1999 23:53:05 -0400
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen wrote:
>
> S.T.L. wrote:
> >
> > Is this a sentence:
> > "Yes!"
> > And is this a sentence:
> > "No!"
> > Both are. Therefore, encode 10010110 as:
> > Yes! No! No! Yes! No! Yes! Yes! No!
> > It's English, even though it's a long string of interjections.
>
> I think that this should work. Any thought of what arguments the
> bureaucrats could possibly have against the sort of conversions we
> discuss in this thread? I should appreciate further contributions.
>
> M. K. Shen
====================
A practical suggestion - use lowercase letters for 0, uppercase for 1.
This way my name can be written as "BorIS kAZak" and will represent
binary 1001101100. Other arrangements are also possible. In any respect
it will be a legitimate readable text.
Best wishes BNK
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 00:18:21 -0600
In article <7krli9$jqr$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> First, in my first post, I used the term "statistical" randomness. It
> is a term I received when reading about PI, which is supposively the
> most statistically random sequence of digits known to man. By this, it
> is ment that the digits are generally well distributed, and that they
> occur approximately as often as each other- that 1' occur as
> frequently, as 2's which occur as frequently as..., you get the idea.
Right -- I'm not sure it's statistically any more (or less) random
than lots of other transcendental numbers though -- I've never tried
to do a direct comparison, but I'd be a bit surprised if you could
find much in the way of long-term patterns in something like the
square root of 2 or 10. More or less by definition, any
transcendental number is going to lack any real pattern...
> Also, a OTP's strength is entirely found in the fact that given a
> cipher stream only, any plain text stream is an equal candidate to be
> the true plain text.
Quite true.
> Now to the point. If we say that a OTP has truly random values and
> that the pad's contents are totally independent of each other, then
> there is the extremely low possibility for a series of bits to display
> a pattern, though the pattern may never occur again. For example,
> there could occur a series of BYTE values 0xa7 (or any value) that
> repeats, say, 100 times.
Yup, it can (at least appear to) contain a pattern. I won't try to
get into the (more or less meaningless) discussion of whether it
constitutes a pattern if it happened by accident or not.
> I proposed this ment nothing, until someone disagreed with me and
> advocated I turn to this forum for advise and insight. So I ask you,
> does it make sense that randomness is a requirement, that patterns must
> be avoided, in building a one time pad?
NO -- if you avoid any particular set of possibilities, and the
attacker can find the possibilities you've avoided, then he's found at
least some limit on the possibilities for the plaintext. This isn't
likely to be a useful attack in most cases, but if you pick out enough
things as looking like patterns, and refuse to use them, you could (at
least theoretically) eliminate enough for the attacker to decrypt a
few small bits of what you've encrypted.
> It appeared to me that this individual is correct. For example, if you
> take a long sentence of 100 characters and you apply the segment of the
> pad to it and someone guesses that the segment is in fact all 0xa7,
> then one would have to conclude that the proposed candidate is indeed
> the plain text because the odds against it appear astronimcal.
The problem is that the attacker has no more reason to believe that
you've used a segment containing a repeating character than another
set of characters of the same length. He can guess that it's all 0xa7
and it might decrypt to something reasonable. However, by using other
keys, he can decrypt the same ciphertext to every other plaintext he
considers reasonable.
> so I wonder now just how much relationship must occur in build a pad.
> It seems that weak statistical randomness must be employed if nothing
> else but to prevent this scenario.
I disagree. If, for example, 0x00 appears 20 times in a row, then the
plaintext for those 20 characters will show up in the ciphertext. The
problem is that the attacker has NO way of guessing that this is
really the correct plaintext. Without knowing up-front that there's a
20-byte run of zeros in the key, he has no more reason to guess the
plaintext is showing through unchanged than any other run of 20
characters.
Another poster (at least I don't think it was you) recently asked
about using this to feed misinformation to the enemy. If you had a
truly secure channel, you could do this pretty easily. Start with a
(presumably false) message you want to send to your enemy. You can
then pick out a key that will decrypt this to a different message of
the same length. You can then transmit the false message as
plaintext, and (with a little luck) your enemy may assume it was sent
un-encrypted entirely by accident. The intended receiver, however,
knows to decrypt it with the secretly transmitted key, and gets the
correct message.
If you make only a few judicious changes between the two messages,
with most bytes identical between the two messages, then the key that
has to be transmitted secretly will contain mostly zero bytes. Even
if you use something as simple as run-length encoding on the key, it
will then be considerably smaller than the entire message, so it can
then be transmitted by a secure channel of much lower bandwidth.
Ultimately, the real key might consist of nothing more than the
position in the openly transmitted message at which "not" will be
inserted. In this case, the key might be transmitted by an
_extremely_ low-bandwidth medium, which might render the entire scheme
quite practical.
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
