Cryptography-Digest Digest #536, Volume #9 Wed, 12 May 99 16:13:03 EDT
Contents:
Re: Hello I am paper, please read me. (Thomas Pornin)
Re: public/private key authentication? (Medical Electronics Lab)
Re: Crypto export limits ruled unconstitutional (Mok-Kong Shen)
Re: TOMSTDENIS AND SCOTT ARE THE SAME PERSON-- ([EMAIL PROTECTED])
[Q] Are all encryption algorithms based on primes? ("Jessie")
Re: Crypto export limits ruled unconstitutional (Jim Gillogly)
Re: AES (Terry Ritter)
Re: Fast random number generator ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: Hello I am paper, please read me.
Date: 12 May 1999 18:12:03 GMT
According to SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>:
> Tom the big boys like "*.ps" however I can't read or write *.ps
> files.
Ghostscript is freely available, source code included, and can read
PostScript files. To write them, you can still do it by hand (it is a
programming language, after all) but many people use TeX/LaTeX, which is
also freely available, source code included, for many platforms, among
which are all Microsoft things (msdos, windows, win95/8, NT...).
Plain text is good for... text, but not so good for mathematical
functions (unless you are a god of ascii-art). Html should be avoided
because of the many slightly incompatible flavors, until MathML
stabilizes and becomes widely implemented.
Some people prefer PDF files. PDF can be converted to many things using
free tools (pdftops or Acrobat Reader).
--Thomas Pornin
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: public/private key authentication?
Date: Wed, 12 May 1999 12:17:43 -0500
Dylan Thurston wrote:
> I think we must be talking about different things here. I'm talking
> about the practice of prepending a random number to the message before
> hashing; this random number is transmitted in the clear as well, so
> the other side can use it to verify the hash. This is analogous to
> the 'salts' used in /etc/passwd. I forget exactly why it's done,
> though. To prevent replay attacks, maybe?
That's different than what I had in mind. It's a better solution too,
doesn't violate the "any secrets" portion. Won't help with replay
attacks, but it will verify the hash.
> Also, I was interpreting the question from the point of view of a
> paranoid government: the users have to prove they're not transmitting
> hidden information. From this point of view, there's no reason to
> assume the users haven't shared their private keys; of course, this
> breaks the authentication, but might allow cryptographic
> communication.
Actually it can help authentication. It gives more combinations of
things they can do. Crypto isn't allowed as part of the solution
over the air (as I understand it). Does that mean crypto walkie
talkies are illegal?
> (Incidentelly, you may want to check your user name, Mr. Medical Lab.)
I have many net names. This is just where I connect via lunch.
My local ISP has gone bankrupt, so I had to pick a new one.
My new address is [EMAIL PROTECTED] and web page is at
http://www.terracom.net/~eresrch If anyone has problems getting
it, please let me know.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Crypto export limits ruled unconstitutional
Date: Wed, 12 May 1999 20:26:25 +0200
[EMAIL PROTECTED] wrote:
>
> The inverse translation is actually the more interesting of the two.
> CASE tools are a form of this automation.
Whichever the direction, you have to provide rules of transformation.
That isn't apparent. I was asking about the specific software that
Bravo claimed to have used.
M. K. Shen
------------------------------
Date: Wed, 12 May 1999 14:54:58 -0400
From: [EMAIL PROTECTED]
Subject: Re: TOMSTDENIS AND SCOTT ARE THE SAME PERSON--
Jim Gillogly wrote:
>
>
> Must remember to include this identification mechanism in my
> stylometric analysis program.
>
I presume this is the equivalent of the "fist" of a telegrapher?
When we get to te semantics of style instead of the syntax we'll have
the ability to infer what the writer _thought_ in adition to what he
_wrote_. Any bets on first (public) release?
------------------------------
From: "Jessie" <[EMAIL PROTECTED]>
Subject: [Q] Are all encryption algorithms based on primes?
Date: Wed, 12 May 1999 18:58:16 GMT
Are all encryption algorithms based on the fact that it is difficult to
factor a number which is the product of two LARGE primes? If this is true,
then, when a factoring function (of the type f(x), which yields all the
factors of a number without checking the modulus of every number) is
discovered, there will be ABSOLUTE CHAOS and PANIC!!
There other ways of encrypting data effectively WITHOUT using this prime
technique, like XOR-ing the bits and reversing them, etc., but are these as
effective? Many thanks in advance!
--
Jessie
"With great power comes great responsibility"
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Crypto export limits ruled unconstitutional
Date: Wed, 12 May 1999 12:16:28 -0700
Mok-Kong Shen wrote [regarding translating C to English-like text]:
> Whichever the direction, you have to provide rules of transformation.
> That isn't apparent. I was asking about the specific software that
> Bravo claimed to have used.
Uh, claimed? No need to be offensive.
Try http://personal.sip.fi/~lm/c2txt2c/
Nobody who's read the tortuous (and torturous and potentially tortious)
language used to translate algorithms into Patentese can doubt that
some legal firms have a program to do this. It's for a different
purpose, allowing the Patent Office to pretend to believe that it
describes a machine or process rather than an algorithm (which is
not patentable), but the net effect is the same. A case in point:
13. The compression apparatus of claim 12 in which said transfer
means comprises means for transferring said data character signal
from said character register means to the lower significant positions
of said code register means, and means for zeroing the remaining
high order positions of said code register means.
I'm not making this up.
--
Jim Gillogly
21 Thrimidge S.R. 1999, 18:57
12.19.6.3.6, 9 Cimi 14 Uo, Third Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: AES
Date: Wed, 12 May 1999 19:32:47 GMT
On 11 May 1999 18:28:15 GMT, in <7h9srv$jmu$[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] wrote:
>[EMAIL PROTECTED] (Terry Ritter) writes:
>[...]
>As someone who is more of a physicist than a mathematician i have no problem
>with this language. I can say that general relativity has "proven to be
>correct" while understanding that tomorrow it could very well be proven to
>be incorrect -- in fact I entirely expect that this will happen some day.
Then you fundamentally misunderstand even your own field. The facts
of relativity, as tested, do not change when a new theory is proposed.
Relativity is unlikely to be "proven incorrect." Instead, there will
be certain areas where the theory incorrectly models reality. The
whole point of a new physical theory is to provide at least as good a
model as the old, and cover even more.
There is a fundamental difference between cryptography and physics
with respect to provability: In physics, we can use the model to
predict outcomes and then measure those outcomes in reality; the
extent to which we get a match is the extent to which we have a good
theory. But in cryptography, we cannot model strength. There is no
computation which gives the strength value, and there is no experiment
which allows us to confirm it. The only thing we have are some
attacks which require some amount effort, but they give us no
assurance at all that some very clever but absolutely trivial
successful attack does not exist. The very concept of "proven
security" in cryptography currently has no practical meaning.
>>But as far as I can tell, a logic of
>>cryptanalytic validation goes something like this:
>>
>>1. Assuming academic cryptanalysis is the best possible,
>>2. if cryptanalysis has found no break, then
>>3. no break is possible.
>
>Interesting. Care to show me where Mr. Schneier has suggested that this
>logic is valid? Or are you simply using rhetorical games to try to put
>words in his mouth? (yes that's a rhetorical question)
If you don't like *my* syllogism, perhaps you can provide one which
*does* imply cipher strength. What is your interpretation of this
process? And that is not rhetorical.
In my view, the whole concept is bankrupt, and these continued
attempts to extend what is now clearly an unworkable process can only
damage users and thus the field itself. It is time to have a clear
understanding of what cryptanalysis provides, and that is an upper
bound on strength, with no lower bound. To provide any implication of
security, we must have a lower bound on strength. Currently, that is
zero.
>I've never, ever seen Bruce say anything even remotely suggesting that
>he would accept (3.) in that list as a conclusion. The fact that you're
>suggesting that he'd hold such opinions says a whole lot more about you and
>why you're attacking him than it does about what he's written.
I would say that your perception that I am attacking Schneier --
instead of the false ideas he promotes -- says more about you than me.
My words were "as far as I can tell" and "a logic of validation": it
is you who assign those words to Schneier, not me.
But Schneier does promote the use of cryptanalysis as the way we know
cipher strength -- I think that is a fair quick summary of his
position -- which implies that he *does* have *some* logic which in
his mind *does* provide some logical implication of strength. And
while I have become convinced that any such logic is false, if someone
can come up with workable logic which does produce such a conclusion,
I would have to accept it.
>>No cryptanalyst will ever put this so baldly. But we see in practice
>>the sequence: new cipher designs, subjected to academic cryptanalysis,
>>then generally approved for use, which seems to be an expression of
>>the above logic.
So I clearly *did* show my doubt that Schneier would ever *express*
such a syllogism. The question is, "What syllogism *does* he use?"
In what way *can* cryptanalytic results *ever* be used to imply user
information security?
>It seems to be about the best we can do. Barring a formal proof of
>security in the mathematical sense (the holy grail of cryptography) there
>seems to be no better option than to go with the cipher that has proven
>to be secure through time.
So, basically, since we have no way to find a lower bound on strength,
we will just ignore it. We will ignore the idea that any cipher might
have a trivial break which we do not know. We will encourage users to
believe they have "proven security," while knowing that we have no
such thing. In other fields, making claims which cannot be supported
would be called "deceptive," or perhaps even "fraud."
>[...]
>>It is a
>>*realistic* possibility that DES has been broken in secret from the
>>time it was designed and that we still do not know that.
>
>Yes. However, DES has been around for a very long time, and has more
>extensive public cryptanalysis than probably any other algorithm, and the
>rewards (prestige, furtherance of career) for breaking DES would be
>substantial. This is in some sense just a glorified "crypto contest" which
>we agree is not any indication of security -- however it has been going on
>for 20 years with the highest rewards that the crypto community could offer
>the person that broke it. Against this kind of a challenge DES has proven
>to be secure.
No, DES has *not* proven to be secure. It has simply no break that we
know about. Not knowing about weakness is far different than having
proven security.
The very idea that we could on the one hand admit that DES *might* be
broken, and then call it "secure" -- simply because we do not know for
sure that a break exists -- sounds crazy. Not *knowing* that our
cipher is broken is the *normal* situation for a cipher being broken.
It is all we ever know of the worst possible case when our information
is being harvested and wisely exploited. Our only reasonable choice
is to assume that the cipher *might* be broken. And that can hardly
be called "secure."
>>And while we
>>might wish and hope to call this "improbable," that would be pasting
>>the illusion of scientific analysis on something which cannot (yet) be
>>quantified.
>
>Why on earth does "improbable" imply to you anything about scientific
>analysis or quantification? To me it implies exactly that opposite -- saying
>that something is improbably almost certainly means (to me) that someone is
>making a judgement call and weighing the percieved risks.
But in cryptography we *have* no information on which to perceive
risks. We do not know the "absolute strength" of our ciphers. We do
not know the capabilities of our opponents. We do not know how many
of our designs have been broken by our opponents. There is simply no
information upon which to base a risk analysis or a judgment call.
>[...]
>What I think is part of the problem is professional cryptographers on
>sci.crypt who decide to attack other cryptographers over obviously
>fabricated issues, just so that they can attack them.
If you are referring to me, in this case, your interpretation is
false. I have a substantial history of messages and writings which
directly confront the issue of proof in cryptography, and my position
has not changed to allow me to attack the current guru. Schneier
created the problem; I did not go after him.
On the other hand, to the extent that Schneier has in recent months
actively promoted various ideas which are logically insupportable, we
will find that I oppose those ideas.
>It is the kind of
>behavior that I expect out of Mr. SCOTT19U.ZIP.
I think you need to look to yourself to find why you take a rational
issue in personal terms. Attacking Schneier's misuse of these terms
is not an attack on Schneier, and certainly not an attack on you.
Unless, of course, you think there *is* "proven security" in
cryptography, in which case this reality may be quite distressing to
you.
>I read what Bruce wrote
>and I gave him the very obvious benefit of the doubt about the language
>that was being used.
Then you are giving him far too much benefit. As an "authority,"
Schneier has a responsibility to not mislead those who ask for his
advice. Schneier is a writer to whom words are professional tools,
who is well aware that words can be misinterpreted, and he can take
action to prevent that. In this case he did not.
The idea that there is anything in cryptography like "proven security"
is a widespread misconception which can lead to a fruitless unending
search for the holy grail which is said to exist. This belief is a
serious problem which can undermine the attempt of any student to put
the field into perspective.
Your acceptance of words which can be misinterpreted is the wrong way
to go -- instead we should expect statements which are provably
correct (and not just not proven wrong) which have a clear meaning.
When ambiguity exists, we should expect a discussion to resolve that
in the context of the truth. This *is* that discussion.
>You read Bruce and figured that now was a good time
>to try to make yourself look smart by attacking Bruce on a stupid detail.
It is hardly a stupid detail; it is at the basis of understanding what
cryptography can do.
>I'm getting quite tired of some of the people on this list who should
>know better jumping all over Bruce the second he is percieved as making
>the slightest mis-step. If you're upset about the fact that Bruce is
>more popular, then get off of Usenet and go write your own damn book.
You need to first of all be more tolerant, and second to understand
that a whole range of possible motives can produce pretty much the
same actions. Your interpretation of my motives in those actions is
false, and consequently says more about you than me.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Date: Wed, 12 May 1999 16:07:39 -0400
From: [EMAIL PROTECTED]
Subject: Re: Fast random number generator
Herman Rubin wrote:
>
> In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >Herman Rubin wrote:
>
> >> In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>
> >> >On Wed, 05 May 1999 17:56:55 GMT, in
> >> ><[EMAIL PROTECTED]>, in sci.crypt
> >> >[EMAIL PROTECTED] (John Savard) wrote:
>
> ..............
>
> >> >>>>The classical shuffling algorithm depends on a good random number
> >> >>>generator to produce small random numbers in the range [0, size-1].
>
> >> >>No, it needs more than that.
>
> >> >>It needs one random number in the range {0, 1, 2, ... size-1 }, and
> >> >>then it needs one random number in the range {0, 1, 2, ... size-2 },
> >> >>and then one in the range {0, 1, 2, ... size-3 }.
>
> ................
>
> >> >In particular, an appropriate way to develop a random value of
> >> >arbitrary range is to first mask the random value by the next higher
> >> >power of 2 less one, and then reject any value beyond the desired
> >> >range.
>
> >> This method is quite inefficient, as far as bit usage, especially
> >> as the value of the number m for which a number in the range
> >> 0 - m-1 is needed. Here is an algorithm which will use the
> >> minimum expected number of bits. The algorithm given is optimal
> >> if m = 2^k or m = 2^k - 1, but not otherwise. For m = 5, it
> >> uses an average of 4.8 bits, rather than the 3.39 possible.
> >> For m = 65, it is 13.75, rather than 7.72.
>
> >> A version of the optimal bit algorithm is as follows, assuming
> >> that m > 1. B is a new random bit at each stage. It uses
> >> multiplication by 2, addition, and comparison.
>
> >> i = 1; j = 0;
> >> loop: i = i*2; j = j*2+B;
> >> if(i < m)goto loop;
> >> if(j < m){return j:
> >> exit}
> >> i = i-m; j = j-m;
> >> goto loop;
>
> >> The basis of the proof of correctness is that, on the loop: line,
> >> j is always uniform 0 - i-1, and that this remains true after the
> >> subtraction if that is done. No procedure returning one result
> >> uniform random numbers in the range 0 - m-1, considering no other
> >> results from random processes, can be more efficient.
>
> >I believe that as m grows the bit utilization efficiency of the methods
> >converges, but the parallelism of the word-oriented power-of-two masking
> >technique will dominate the bit-shifting technique (the *2 in the loop:
> >line is a bit shift).
>
> The bit utilization efficiency does not approach one, but
> asymptotically varies between ln(4) ~ 1.3863 and 4/e ~ 1.4715.
> One can speed up the time substantially by setting i to 2^k,
> where this is the smallest power of 2 exceeding m, and j to
> result of k random bits, and starting at the instruction just
> after the loop line, or modifying the loop: line to shift by
> the number of places needed to reach at least m, and bring in
> that number of bits. The latter minimizes the number of times
> random bits are brought in, still keeping bit efficiency.
I agree that making the optimizations you describe will preserve the
correctness of the algorithm and improve the efficiency of the code
snippet above to the point that it matches the power-of-two masking
technique. In fact, setting i to the least power of two greater than or
equal to m is exactly the same as the bit-masking technique Ritter and I
have mentioned.
However, there remains an aspect that I do not understand. If B
delivers the requisite number of bits on each access, they why is the
summation/subtraction worth while? I.e., given that i becomes invariant
ceil(log2(m)), why not get a fresh j each iteration and skip the
summation/subtraction completely? As far as I can tell the
simplification does not decrease the bit utilization efficiency.
For example:
i = ceil( log2( m ) ); // O( log2(m) ) here for integral
versions
loop: j = B( i ); // B(n) returns 0..2^n-1
if ( j >= m ) // j flat over 0..2^n-1, thus ...
goto loop;
return j; // j flat over 0..m-1
>
> I suspect that a major part of the time in both algorithms is
> the bookkeeping to keep track of the location of the random
> bits, and managing buffer fills, etc.
Absolutely. The overhead required to present such a simple algorithm to
the caller is usually much more expensive then the actual algorithm
itself. This is why, given a word-oriented rand() function [ B() ], it
is much more efficient to avoid shifting altogether. Keeping track of
the bit counts overwhelms the simplicity of the technique.
------------------------------
** 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
******************************
