Cryptography-Digest Digest #776, Volume #9 Fri, 25 Jun 99 17:13:03 EDT
Contents:
Re: Kryptos article (Jim Gillogly)
Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length? (DJohn37050)
Re: one time pad (AllanW)
Re: Bytes of "truly random" data for PRNG seed. (Terry Ritter)
Re: RC4 Susectability ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
sha-1 C/C++ source code ([EMAIL PROTECTED])
Re: one time pad (AllanW)
Re: Tough crypt question: how to break AT&T's monopoly??? ([EMAIL PROTECTED])
How does 3DES work? ([EMAIL PROTECTED])
Re: Converting arbitrary bit sequences into plain English texts (wtshaw)
Re: Kryptos article (Jim Gillogly)
Re: Bytes of "truly random" data for PRNG seed. (David A Molnar)
Re: "Breaking" a cipher ([EMAIL PROTECTED])
Re: one time pad (John Myre)
Re: Converting arbitrary bit sequences into plain English texts (wtshaw)
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: Converting arbitrary bit sequences into plain English texts (wtshaw)
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Fri, 25 Jun 1999 12:16:32 -0700
Lincoln Yeoh wrote:
> http://www.odci.gov/cia/information/tour/krypt.html
>
> Is that a hole on the lower right? And is that where we're supposed to dig
> or look inside?
It's a pool of water. I suspect if you stand a bit closer it would
reflect the Vigenere table that's cut through the copper panels on
the right; we're seeing them reversed, so presumably the pool will
straighten them out for us.
Is there another pool on the concave side of the cipher panels?
--
Jim Gillogly
2 Afterlithe S.R. 1999, 19:14
12.19.6.5.10, 1 Oc 18 Zotz, Second Lord of Night
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length?
Date: 25 Jun 1999 19:05:12 GMT
Here is an advantage of ECC over other methods, the domain parameters are
public, so one can use a Koblitz curve with a random curve as a backup. Note
that this may entail NO change to the key generation code, if it allows
selection of domain parameters. So one can get the benefits of Koblitz today,
and if someone somehow finds out they are weaker than now thought, can switch
to a random curve.
Don Johnson
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 18:35:43 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote:
> Were it possible to tell whether sequence s + '0' was more
> random than s + '1', we could produce the one sequence which
> was most random. But everybody would know that sequence so
> it would be useless for cryptography.
Heh heh, I like that. It's kind of like, "Give me a list of
all well-known patterns, and then find the one that is least
well-known!" The answer depends on the quality of the first
list.
> The whole point of crypto random is the hope that it is
> not possible to know what the sequence will be.
Right.
Common RNG tests wouldn't be of any use, if they didn't
check for known problems that make the next character in
a sequence too easy to guess.
For instance, we use frequency graphs to prove that each
possible output byte is generated approximately the
correct number of times. If we found that the byte value
'0' was output only half as often as the odds predict it
should be, we would call that a weakness because an
attacker would rarely guess 0.
--
[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.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Bytes of "truly random" data for PRNG seed.
Date: Fri, 25 Jun 1999 18:38:20 GMT
On Fri, 25 Jun 1999 12:49:24 GMT, in <[EMAIL PROTECTED]>, in
sci.crypt "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>fungus wrote:
>> The Blum Blum Shub I mentioned earlier is supposed to be "provably
>> good" but I have to confess I don't know much about the algorithm
>> or how the proof works.
>
>It's just iterated squaring (starting with a random seed) modulo a
>product of two large primes (each of which is congruent to 3 mod 4).
>The claim that BBS is "cryptographically strong" is based on the
>difficulty of factoring, which of course is a field that has seen
>rapid progress..
Actually, there is more to a real BB&S system. See:
20. Blum, L., M. Blum and M. Shub. 1983. Comparison of Two
Pseudo-Random Number Generators. Advances in Cryptology: CRYPTO '82
Proceedings. Plenum Press: New York. 61-78.
21. Blum, L., M. Blum and M. Shub. 1986. A Simple Unpredictable
Pseudo-Random Number Generator. SIAM Journal on Computing. 15:
364-383.
One issue is that BB&S primes are "special." Another issue is that
the original seed must be on a long cycle.
>From section 4.4 of my 1991 Cryptologia RNG article:
"N is to be the product of two large distinct primes, P and Q. Both P
and Q are to be congruent to 3 mod 4, and must also be special
(p.378). Prime P is special if P = 2P1 + 1 and P1 = 2P2 + 1 where P1
and P2 are odd primes. The paper gives 2879, 1439, 719, 359, 179, and
89 as examples of special primes (but 179 and 89 appear to not be
special, while 167, 47 and 23 should be). As yet another condition,
only one of P1, Q1 may have 2 as a quadratic residue (P1, Q1 are the
intermediate values computed during the "special" certification). If
we mark such particular special primes with an asterisk ("*"), we get,
for example: 23, 47*, 167, 359, 719*, 1439*, 2039, 2879*, 4079*,
4127*, etc. Accordingly, N = 719 * 47 fails the additional condition,
because both special primes are particular. Presumably, these detailed
conditions guarantee the existence of long cycles, but they do not
banish short ones."
We can force the seed to be on a long cycle by picking a random x then
actually checking to see if x is on a cycle of the expected length.
The BB&S article describes this, but the article is extremely complex,
somewhat disorganized, and the second half is often overlooked.
Again, from my article:
"Because an x^2 mod N generator generally defines multiple cycles with
various numbers of states, the initial value x[0] must be specially
selected to be sure that it is not on a short cycle (p. 377). The
paper says to select x[0] such that the "order" of x mod N (that is,
the length of that cycle) is a particular value, specifically
Lambda(N)/2, where Lambda is "Carmichael's Lambda-function." The
function Lambda(M) can be computed using the least common multiple
(lcm) of the factors of M."
I am aware by private communication of work investigating the
probability of short cycles. This is also very complex, and I am
unaware of formal publication. The implication is that we can avoid
cycle length checks at low risk, but I think that is almost a step
beyond what I would call "proven" strength: Admittedly, any cipher
can be solved by guessing the key, which implies that we accept a tiny
probability of weakness in ciphers. But it seems a little different
if we, by our own choice, have selected a short cycle for our
opponents to exploit, while still maintaining the delusion that our
generator is "proven" secure.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RC4 Susectability
Date: Fri, 25 Jun 1999 19:53:45 GMT
In article <7l0egd$a8k$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> > Sorry about that (bad water or something :) ). I will try to post
> when
> > I am sure about what I am saying...
>
> Is that just for this thread, or a new policy in
> general?
hey I spark conversation ok. Gimme a break I haven't had any formal
training so most of my knowledge is self-taught.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES-NULL attack
Date: Fri, 25 Jun 1999 19:51:44 GMT
In article <7l0ir0$c7b$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Oh! You are on duty today.
> You should get a more salary.
> The case is out of your confidence
Ok what's this about?
Your argument is not substantiated. Just because you pass a zero block
thru does not mean you will find out the key faster then any other
method. In the standard attacks they use differences between pairs no
single inputs.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: sha-1 C/C++ source code
Date: Fri, 25 Jun 1999 19:46:41 GMT
Hi All!!
Is there a site to get sha-1 C/C++ source code?
Thanks in advance,
Vasav
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 19:18:19 GMT
[EMAIL PROTECTED] (S.T.L.) wrote:
> This thread is disgusting. Most involving OTPs get ugly, but
> *so* many kooks posting here have the wrong ideas.
Gosh, S.T.L., it's a good thing you're here to help us
distinguish the kooks from, say, the insufferable
egotistical asshole bastards.
> I'll just state it plainly:
>
> If you have a perfect random number generator
Is there such a thing? If so, how do you know?
> that is operating correctly, then ALL you need to do is
> take its output, send it to the recipient securely, and
How?
Doesn't the existance of a secure channel imply that no
encryption is needed?
> then XOR said output with the plaintext, and send that
> over on an unsecure channel. No munging / filtering /
> adulterating of the true RNG's output is required. In
> fact, any filtering / adulterating / munging of the
> output will WEAKEN the complete strength of the OTP to
> something worse.
Gosh, you're the only one to point that out. Thank god
for you.
> Let me repeat that a little differently.
Oh, would you?!? Please?!?
> It doesn't matter if you talk about "all zeros" or
> "patterns" in the true-RNG's output. Possible stream
> ciphers have nothing to do with it. Munging the
> true-RNG's output will weaken security, period.
> If you don't realize that what I'm saying is true,
> you don't understand cryptography.
Imagine the arrogance of someone who doesn't understand
cryptography, posting a question to sci.crypt! S.T.L.,
would such a person qualify as an insufferable egotistical
asshole bastard?!?
> Now, IF you suspect that your true-RNG is going flaky on
> you (operating incorrectly), take it out of service, have
> it output a quadrillion bits
Different countries have different names for names of numbers
larger than 1 million. For instance, in England the words
Billion, Trillion and Quadrillion represent much larger values
than they do in the United States.
U.S. England
Thousand 10^3 10^3
Million 10^6 10^6
Billion 10^9 10^12
Trillion 10^12 10^24
Quadrillion 10^15 10^48
For instance, in the United States, the number 100,000,000,000
would be called "One Hundred Billion" but in England it would
be called "One Hundred Thousand Million".
Giving you the benefit of the doubt, I'll assume that by
"One Quadrillion Bits" you meant 10^15 bits, or 10^12
8-bit bytes. Can your "true-RNG" really create that much
data in a reasonable amount of time?
> and run *statistical tests* on those bits.
Can your *statistical tests* examine 10^12 8-bit bytes in
a reasonable amount of time?!?
> If it turns out to be flaky, then you can safely discard it
> knowing that the chances of it actually being good are lower
> than your chances of being hit by a meteorite while being
> struck by lightning.
That happened to me three times. It was embarrasing, but it
really hurt a lot too. Worst of all, after the first time,
the newspapers refused to print the story because they said
it was old news. And after the second time the insurance
company cancelled my policy. Now that was *Really*
embarrasing!
> If it turns out to pass those statistical tests, you can
> safely use it knowing that the chances of it actually
> being flaky are lower than your chances of being hit by
> a meteorite while being struck by lightning.
You must have a lot of confidence in your statistical tests.
Have you really checked for *EVERYTHING* that can be checked
for? And you have the mathematical basis to prove that there
are no other possible tests? If so, I stand in awe, and I beg
you to do the entire Internet community a service by making
the source code for these tests available online. Please. I
really could use some tests of this quality, and it's obvious
to me that many other people could use them too.
> Moo moo kabubu.
Cowabunga, yourself. Here's some hay.
> If I've forgotten an assumption here, or said something
> wrong (gasp!) feel free to point it out.
How could you, when you know all (gasp!) of the answers?
> I can tell kooks from the intelligent people,
Easy, just look for the string "@kooks.org" in the E-mail
address.
...One possible weakness with this plan is that it would
ignore intelligent kooks. Or is there such a thing? If
you say that there isn't any such thing, I will bow to
your superior knowledge. You seem to have an insight
into both kooks and intelligent people.
> and I'll only bother replying if an intelligent person
What about people who are neither kooks nor intelligent?
> notes a true mistake/omission I've made.
No mistakes, just an omission. Look up "polite" in any
good dictionary. See also "civil" and "manners."
> ---
...
> I believe the courtesy of providing a correct E-mail
...
Ah! You've heard of courtesy, so "polite" shouldn't be a
difficult concept for you. Not with such an intelligent
and un-kooky mind as yours!
--
[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.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Tough crypt question: how to break AT&T's monopoly???
Date: Fri, 25 Jun 1999 19:59:57 GMT
<snip>
If you want to do a bit of coding you could make a simple RC4 stream
gen. Then make a program to accept the stdin as input and stdout as
output which will xor the stream with the input. You could use it like
this
RC4 "pass word" < input > output
or in unix
cat input | RC4 "pass word" > output
(what is the inverse cat?)
Or you could simply make a 8-bit sbox and sub if you don't care for
security.
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: How does 3DES work?
Date: Fri, 25 Jun 1999 20:03:24 GMT
Does 3DES work because not all outputs are possible? Because the key
is smaller then the input it's not a perfect permutation (it's
complete ... but ?).
For example 2^64 possible inputs but only 2^56 possible outputs for
that one input.
If this argument is true then ciphers with larger keys will most likely
not work because there would be a shortcut (i.e mitm).
Any help?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Fri, 25 Jun 1999 14:51:44 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> 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.
>
There are examples where randomness can be used to produce music, based on
a predetermined set of available and compatible notes, measures, etc. To
export something like source code, a rather long list of musical creations
could be broadcast or otherwise distributed.
In addition to initial enjoyment of the music, and subsequent boredom of
that, the product could be decryted into an intelligent series of numbers
by a recipient through automatic recognition of the various parameters in
these songs.
I do take pleasure in suggesting that NSA spend more time listening to the
classics so that they could pick out the forbidden tunes if anyone
actually were to do this. It could make for persecution of someone who
was just hooked on lots of themes and variations.
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Fri, 25 Jun 1999 12:45:39 -0700
Jim Gillogly wrote:
>
> Lincoln Yeoh wrote:
> > http://www.odci.gov/cia/information/tour/krypt.html
> >
> > Is that a hole on the lower right? And is that where we're supposed to dig
> > or look inside?
>
> It's a pool of water. I suspect if you stand a bit closer it would
> reflect the Vigenere table that's cut through the copper panels on
> the right; we're seeing them reversed, so presumably the pool will
> straighten them out for us.
Reflecting on this, I realized it's utter garbage. The pool would
swap up and down, not right and left. Never mind.
--
Jim Gillogly
2 Afterlithe S.R. 1999, 19:44
12.19.6.5.10, 1 Oc 18 Zotz, Second Lord of Night
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Bytes of "truly random" data for PRNG seed.
Date: 25 Jun 1999 20:28:24 GMT
[EMAIL PROTECTED] wrote:
> Does anyone have a link to the BBS paper online?
I am photocopying it right after finishing this post.
Will I be sued if I scan and post the photocopy ?
Thanks,
-David Molnar
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: "Breaking" a cipher
Date: Fri, 25 Jun 1999 19:56:47 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (JPeschel) wrote:
> I agree with you that Matsui's attack on DES is a break. Still I
must
> contend that when we know we can exhaustively search the entire
keyspace
> of cipher, in this instance, DES, in less than a couple days this a
break.
>
> Knudsen seems to agree when he writes: "More recently the Electronic
> Frontier Foundation (EFF) built a machine to exhaustively break the
DES."
oooooooh I get it. It's a break against the security of the
algorithm!!! (Wow am I silly). The algorithm itself is not broken
(well in the case of brute force) just using it as it was designed has
been... Now I get it. Hmm didn't have to beat my head into wall that
much :) Sorry about the fuss.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 14:05:27 -0600
AllanW wrote:
>
> [EMAIL PROTECTED] (S.T.L.) wrote:
<snip>
> > Now, IF you suspect that your true-RNG is going flaky on
> > you (operating incorrectly), take it out of service, have
> > it output a quadrillion bits
>
> Different countries have different names for names of numbers
> larger than 1 million. For instance, in England the words
> Billion, Trillion and Quadrillion represent much larger values
> than they do in the United States.
<snip>
I think he made a mistake, and meant "bazillion".
J.M.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Fri, 25 Jun 1999 14:42:26 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> There's a boundary hidden somewhere here. As we move from compilable
> source code to translated source code to encoded source code we come
> close to steganography. Is there really a difference between hiding
> source code in the party of words and the LSBs of pixels? I suspect the
> government will find this distinction less than convincing.
Is the government going to put itself in the position of using anything
that it does not understand to try to prove that it contains information
that is forbidden. This seems to be begging for trouble. You need only
submit some the pronouncements of government back to themselves to
demonstrate lack of clarity. Perhaps sourcecode should be done with
steganography using legal terms, since much of that stuff appears
unreadable already; clue: pick a set of jargon that will be unknown to the
person evaluating it, chemical, mathematical, particle physics, the wisdom
of snoop dogy dogy in lyrics, etc.
>
> 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.
You are right, it is silliness....until the government starts picking
people it wants to crucify as examples.
>
.....
>
> When we focus on these distinctions we may find that the export
> regulations are void for vagueness. They do not adequately describe the
> difference in a way that reasonable person can know what is legal and
> what is not.
>
Courts have ruled that people have a right to know, in advance, and, in
detail. Putting it in the hands of bureaucrats with arbitrary power seems
counter to the rulings of the court already. But, since all have the
right of petitioning the government, do so in court. Game, set, match?
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES-NULL attack
Date: Fri, 25 Jun 1999 20:56:15 GMT
In article <7l0psu$f7u$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hello Tom,
>
> I'm very sorry. You must ask for training in math.
> You is doing your job not good enough.
> But, I love you.
What *are* you talking about?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Fri, 25 Jun 1999 15:01:10 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> 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
.....
>
> 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.
>
You have your most common words, and less common ones, and most rare ones.
I'm not sure that using most common words is best. Consider a list of
1024 words, 10 bits, with several alternates for each.
Come to think of it, this is a dandy way to handle a permuted key as well,
consider that x special words were used in an essay. The order of them
would determine the key.
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
** 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
******************************