Cryptography-Digest Digest #767, Volume #9 Fri, 25 Jun 99 07:13:04 EDT
Contents:
Re: one time pad (Greg Ofiesh)
Re: one time pad ([EMAIL PROTECTED])
Re: one time pad ([EMAIL PROTECTED])
Re: one time pad ([EMAIL PROTECTED])
Re: TeraPi (fungus)
Re: On an old topic of internet publication of strong crypto (Mok-Kong Shen)
Re: one time pad (Benjamin Goldberg)
Re: Converting arbitrary bit sequences into plain English texts (Mok-Kong Shen)
Re: Converting arbitrary bit sequences into plain English texts (Mok-Kong Shen)
Re: Converting arbitrary bit sequences into plain English texts (Mok-Kong Shen)
Re: Encryptor that fits on a disk? (Robert G. Durnal)
Re: Converting arbitrary bit sequences into plain English texts (Mok-Kong Shen)
Re: Converting arbitrary bit sequences into plain English texts (Mok-Kong Shen)
Re: Converting arbitrary bit sequences into plain English texts (Mok-Kong Shen)
Re: xtea (Nikos Mavroyanopoulos)
generated pad for OTP? (Benjamin Goldberg)
----------------------------------------------------------------------------
From: Greg Ofiesh <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 05:50:54 GMT
> Terry, I tend to agree with you about the fallaciousness of assigning
> relative strengths to ciphers, but this usage of the term proof is
> probably not a good one. It implies a mathematical level of proof.
> Note that we have no equivalent proof that the earth is not flat...
This will likely be my last post on this thread. I really can't say
thank you all for your patience with me as you pointed some thing out
to me I have not considered. I think the examples helped the best.
Let me just clarify what I ment by mathematically provable. A cipher
like PGP, RSA, DES, etc., all have a single conclusion, a single
correct answer. If you ever get it, you know you have it. There is
only one candidate and when you find it you win.
These ciphers have no guarantee of security because no one knows if the
NSA, for example, can crack any of them. People believe this thing,
people believe that thing, but in the end no one knows for certain and
therefore there exists no proof - no proof of security.
The OTP on the other hand guarantees two things: 1. the candidates can
be anything (without exception) and 2. that is where the work of the
cryptanalyst ends. No one candidate can be proven correct.
This difference is what I ment by proof of security, and I think you
can write it out mathematically as a simple proof. It is really an
issue of numbers - the number of candidates has to be brought to 1 to
defeat the guarantee of security.
Now I say all this with all the new information I have gleaned. For
example, the scenarios painted by Terry would have to be avoided to
maintain the OTP guarantee.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Thu, 24 Jun 1999 16:04:50 -0400
From: [EMAIL PROTECTED]
Subject: Re: one time pad
AllanW wrote:
>
> [EMAIL PROTECTED] (Terry Ritter) wrote:
> > One approach to a solution might be to build a physically-random
> > device which cannot be incorrectly built, cannot fail to perform,
> > cannot be damaged in an undetectable way, and will meet every
> > possible test for randomness, even if we have not yet defined
> > those tests. Then we could say that our device was "provably
> > random," which would imply a security proof for an OTP using
> > such a device as a keystream generator. In my opinion, any
> > attempt to build such a device would be a foolish quest.
>
> Would it?
>
> Consider a CPU which has no fixed clock speed. That is, instead
> of (say) 450MHz, we allow the clock speed to "drift" very
> slowly -- sometimes as low as 400MHz, other times as high as
> 450MHz, in a cycle that repeats 100 times per second.
>
> To this we attach a single-bit counter attached to it's own
> clock source, independant of the CPU and much faster. Give
> the counter a known duty cycle; ideally, 50% of the time it
> contains "0" and the other 50% of the time it contains a
> "1". (Other duty cycles can be adjusted algorithmically.)
> Like the CPU's clock, we will allow the counter's clock to
> "drift", sometimes as low as 3GHz, other times as high as
> 4GHz, in a cycle that repeats 500 times per second.
>
> Note that the CPU's clock drift is not connected to the
> counter's clock drift in any way.
This is an unreasonable assumption. It would require a massive effort
to demonstrate a complete decoupling, and skeptics would still be able
to question the rigor of the demonstration (proof).
>
> Even when the CPU is at it's fastest (450MHz) and the counter
> is at it's slowest (3GHz), the counter will change states
> many times during one CPU clock. So the value retrieved by
> the CPU during any one poll depends on the exact timing of
> the polling pulse. By giving the two clocks different speeds
> and having each of them drift, the timing will vary each time
> that the CPU polls the counter. If the result of one such
> poll is truely random and has a 50% duty cycle, then the
> results of N polls should be enough to create a truely-
> random N-bit integer.
>
> > On the other hand, I am willing to believe that a well-designed,
> > well-constructed, and well-tested physically-random RNG could be very
> > secure indeed. The difference is that we have no absolute *proof*.
> > And that places the OTP firmly into the body of ciphers we know.
>
> I don't claim to have proven that my device is truely random.
> But it does seem to me that it should be possible to
> mathematically prove (or disprove) it.
No. It is possible to prove that the device is not random by finding
some correlation that supports some degree of predictability, but it is
not possible to prove that there are no correlations.
>
> --
> [EMAIL PROTECTED] is a "Spam Magnet," never read.
> Please reply in newsgroups only, sorry.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
------------------------------
Date: Thu, 24 Jun 1999 16:11:14 -0400
From: [EMAIL PROTECTED]
Subject: Re: one time pad
Douglas A. Gwyn wrote:
>
> It is common in cryptanalytic work to see patterns which aren't
> "causal", i.e., which are produced by pure coincidence and are not
> indicative of the true encryption process. Even in the Kryptos
> work, Jim and I noted some fairly long plaintext sequences that
> were apparent in the ciphertext (under certain arrangements), but
> we had enough experience to realize that they were spurious.
> History contains many examples of people finding spurious patterns
> in Shakespeare's plays, the Bible, the Torah, etc.
This is called numerology. Gardner addressed this issue several times
in his Scientific American column in the 1970's.
------------------------------
Date: Wed, 23 Jun 1999 23:13:58 -0400
From: [EMAIL PROTECTED]
Subject: Re: one time pad
Jerry Coffin wrote:
> Randomness is qualitative, not quantitative. IOW, either your stream
> is random, or it's not. There's no "strength" or "percentage"
> involved. If there's any ability to find patterns or correlations in
> the stream, then the key is not random. It may model randomness in
> some fashion to some degree, but it's still not random.
I don't want to start another randomness flame war, but this is a pretty
extreme statement. If entropy density can be used as a metric for
"randomness" then it is possible to quantize the "amount of
randomness". Also, a medium-sized nit is that a "truly" random stream
includes the possibility of sequences with apparent order. Order is a
subset of "chaos" (for want of a better synnonyn).
For most
> practical purposes, a well written LFSR (for one example) models
> randomness well enough that breaking such encryption is relatively
> rare, but it IS still (at least theoretically) possible. To truly
> guarantee against any possibility of the cipher being broken, the key
> stream must be really and truly random.
I believe this is correct if "most practical purposes" excludes crypto.
But since the context is crypto, the statement is false.
Do you have some definition of "well written LFSR" that prevents
cracking the generator?
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: TeraPi
Date: Fri, 25 Jun 1999 09:19:16 +0200
Greg Ofiesh wrote:
>
> What say all of you?
>
It seems very vulnerable to a know plaintext attack. If somebody
knows what message you encoded then they can easily figure out
what your key is, then read all the other messages you've sent
with the key.
A good cipher should hide this relationship between key and
message.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On an old topic of internet publication of strong crypto
Date: Fri, 25 Jun 1999 11:21:44 +0200
Paul Koning wrote:
>
> You seem to be assuming that there are problems with publishing
> papers about crypto. In the US anyway I don't think that is true.
> It was tried, but that attempt was defeated.
You misunderstood me. I (implicitly) pointed out that exporting
published strong crypto materials on paper is allowed, but on magnetic
media (diskettes) or electronically (web page) is not. Prof. Bernstein
got difficulty because he wanted to publish his lecture notes on the
internet. On the other hand crypto textbooks, some with program codes
of strong crypto, don't have ANY export problems. The source code of
PGP was entirely legally exported that way. You might like to reflect
why the bureaucrats act irrationally and illogically. I am pretty
sure it could be worthy of your time.
>
> > Would that be o.k., since the author is not exporting but only
> > redistributing something that he has imported from a foreign
> > country?
>
> Not necessarily. If you were talking about software rather than
> something like a scientific paper, it doesn't matter to the US
> that it came from elsewhere: once you bring it in you can't send
> it back out.
Your point is new to me. But why should a scientific paper possibly
be subject to higher degree of restriction than software (which
implements the idea in the paper), rather than the other way round?
M. K. Shen
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 05:39:00 -0400
On Thu, 24 Jun 1999, Greg Ofiesh wrote:
:
: > 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.
:
: Given the message and the cipher stream, one can derive the pad segment
: between them. Examining the pad segment, one would immediately realize
: that the odds of 20 0's are astronomical. The plain text as well is an
: equally astronomical candidate (all candidates have same astronomical
: odds of being correct). But when you have one astronomical event
: coincide with another, that cannot be coincidence. Thus patterns to
: the naked eye must be avoided in the pad.
:
: What say you?
:
:
: Sent via Deja.com http://www.deja.com/
: Share what you know. Learn what you don't.
:
:
In other words, you are saying the "not a coincidence" of 20 0's is not a
result of randomness, but due to a broken generator. The solution isn't
to filter out recognizable patterns, but rather to make sure that your
generator isn't generating these patterns due to some flaw... Never
forget that it IS possible for a truly random sequence to contain a
pattern, but there is no way of predicting how far that pattern holds. If
I toss a penny 50 times, and get heads 50 times, either there's something
really wrong with my penny, or I've had a phenomenal streak of luck -- If
I get a sequence like this, the solution isn't to remove it [the
sequence], but rather to double-check that my penny [or my random number
generator] is not flawed, and if it is, replace it [replace the
penny/generator, and start from scratch... not just replace that outcome
sequence]; If it isn't flawed, then it just means that I've been lucky,
and I should leave the bit-sequence as-is.
Ben Goldberg
--
The fountain code has been tightened slightly so you can no longer dip objects
into a fountain or drink from one while you are floating in mid-air due to
levitation.
Teleporting to hell via a teleportation trap will no longer occur if the
character does not have fire resistance.
- README file from the NetHack game
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Fri, 25 Jun 1999 11:54:05 +0200
Mike Keith wrote:
>
> Y'all might find
>
> http://users.aol.com/s6sj7gt/cadenza.htm
>
> interesting.
>
> This is a 4000-word short story (quite grammatical)
> in which each word encodes a decimal digit
> (usually - sometimes two).
> The series of digits encoded is statistically
> quite random, being the successive digits of the number pi.
I suspect there is some misunderstanding of my post. The intention
of my approach is to openly and expressly export something, which
the bureaucrats don't like, in front of their eyes, not to secretly
do that in the sense of encryption/steganography, and to achieve
that goal as simply as possible (in particular in respect of
programming effort). Thus an author who publishes his strong crypto
(texts/codes/binaries) will first state the title of the book used,
the base point of the chosen 256 sentences for coding and then let
that be followed by the bunch of sentences that do the encoding.
Thus any person can recover the original information with an almost
trivial computer program. Of course there are hugely excessive
repetitions of the same sentences in the text file thus obtained. But
it is not meant for a human to read that, it's only an input to the
computer program for obtaining what the author sends. Note that there
is a simpler variant of the approach, see the post of S.T.L. in this
thread.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Fri, 25 Jun 1999 12:04:25 +0200
fungus wrote:
>
> You could modify one of those "poetry generators" to give it
> an artistic feel...maybe even encode more than one bit per
> word....
I suppose one disadvantage is that the specification of the generator
has to be published and be such as to be amenable to easy programming
by everybody so as to achieve the goal of export (to the world). See
also my answer to Mike Keith.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Fri, 25 Jun 1999 11:58:52 +0200
[EMAIL PROTECTED] wrote:
>
> Rather than find clever ways of hiding the source code we should push on
> the basic silliness of banning source code. Optimally, we like
> something just far enough from compilable to be exportable. There is
> really is no need to _hide_ the material, only a need to distinguish it
> from machine-usable source code. After all we're citizens to be
> protected not crimminals to be persecuted.
I suppose that my answer to Mike Keith answers your post and that
of wtshaw as well.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Robert G. Durnal)
Subject: Re: Encryptor that fits on a disk?
Date: 24 Jun 1999 13:58:00 GMT
In <7krh1i$i25$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
: Hello,
: I am looking for an encryptor that could be used from a single floppy
: disk. I wish I could use PGP but unfortunatly its just to big.. plus
: the system I am working on gives me limited admin.. no installs
: basicaly. I remember seeing once a program that did a number of
: algorithms and had high bit keys.. but I forgot the name.. If you know
: of one.. that fits my bill.. please let me know.. Thanks
You have not specified whether you want public key or symmetric key
encryption. If symmetric is useable, check out TinyIdea at ftp.garbo.uwawa.fi
/pub/crypt/idea3a.zip. This combines a CFB block chaining shell, Tandem Davies-
Meyer hashing of the passphrase, and the IDEA encryption algotithm which has
not yet been cracked??? all in 507 bytes. And I understand that Mark Andreas
has further reduced it to 366 bytes; see www.sky.net/~voyageur.
==============
My home page URL=http://members.tripod.com/~afn21533/ Robert G. Durnal
Hosting HIDE4PGP, HIDESEEK v5.0, PGE, TinyIdea (link) [EMAIL PROTECTED]
and BLOWFISH in both Windows and mini-DOS versions. [EMAIL PROTECTED]
EAR may apply, so look for instructions.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Fri, 25 Jun 1999 12:08:19 +0200
Boris Kazak wrote:
>
> 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.
A very good suggestion. Readability is no problem, since the stuff
is to be processed by computer.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Fri, 25 Jun 1999 12:12:28 +0200
Matthew Montchalin wrote:
>
> Why settle for adverbs like yes or no? Let's do 4 bits at a time, and
> encode them as a mix of adverbs or prepositions:
>
> 0000 - no
> 0001 - yes
> 0010 - here
> 0011 - there
> 0100 - down
> 0101 - up
> 0110 - left
> 0111 - right
> 1000 - off
> 1001 - on
> 1010 - under
> 1011 - over
> 1100 - around
> 1101 - true
> 1110 - false
> 1111 - maybe
The problem is that the encoded text has to be a collection of
meaningful sentences in order to pass the criterion of being
a natural language text. Simply a bunch of words wouldn't do,
I am afraid.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Fri, 25 Jun 1999 12:34:24 +0200
Mok-Kong Shen wrote:
>
> Matthew Montchalin wrote:
> >
>
> > Why settle for adverbs like yes or no? Let's do 4 bits at a time, and
> > encode them as a mix of adverbs or prepositions:
> >
> > 0000 - no
> > 0001 - yes
> > 0010 - here
> > 0011 - there
> > 0100 - down
> > 0101 - up
> > 0110 - left
> > 0111 - right
> > 1000 - off
> > 1001 - on
> > 1010 - under
> > 1011 - over
> > 1100 - around
> > 1101 - true
> > 1110 - false
> > 1111 - maybe
>
> The problem is that the encoded text has to be a collection of
> meaningful sentences in order to pass the criterion of being
> a natural language text. Simply a bunch of words wouldn't do,
> I am afraid.
Apology. I believe I have misunderstood you. But I don't know whether
'around' and 'under' could be a sentence by itself.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Nikos Mavroyanopoulos)
Subject: Re: xtea
Date: 25 Jun 1999 10:31:33 GMT
In article <7kt942$4n7$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>The correct line is:
>a += ((z << 4) ^ (z >> 5)) + (z ^ sum) + k[sum & 3]
>Read the paper. The idea is to mix all ^ and + operations. Your above
>line will do that so it is most likely equally as strong.
Actually in C this line
y += (z << 4 ^ z >> 5) + z ^ sum + k[sum & 3];
is equal to:
y += ( (z << 4 ^ z >> 5) + z ) ^ ( sum + k[sum&3]);
in the paper there is no description of the algorithm except the C code.
>Tom
--
Nikos Mavroyanopoulos
mailto:[EMAIL PROTECTED]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: generated pad for OTP?
Date: Fri, 25 Jun 1999 06:47:41 -0400
If I have some secret sequence of bytes [as in a session key] and use this
sequence as a seed for a psuedo random number generator, and use the
output of this PRNG as my pad, how easy/hard is it to decrypt data that
has been XORed with this generated pad? While I assume that it depends on
the PRNG, are there generators that are "crytpographically strong?"
Java offers the class 'java.secuity.SecureRandom' which it *claims* is
"crytpographically strong," but I don't know enough about cryptography to
figure out how accurate that claim of strength is.
The "SecureRandom" generator produces 20 psuedo-random bytes at a time, by
incrementing a 64-bit counter, and using a SHA-1 digest on that counter
and a seed. While I know you can't reconstruct a message directly from a
digest, we have, for many values of the counter, the digest of a known
value followed by an unknown value... could one concievably trace the path
of the bits of the counter through to the digest, and compute the next
digest in the sequence? The counter of course starts at 0, and is
incremented every time 20 bytes of psuedo-random data has been used.
Ben Goldberg
--
The fountain code has been tightened slightly so you can no longer dip objects
into a fountain or drink from one while you are floating in mid-air due to
levitation.
Teleporting to hell via a teleportation trap will no longer occur if the
character does not have fire resistance.
- README file from the NetHack game
------------------------------
** 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
******************************
