Cryptography-Digest Digest #122, Volume #9 Mon, 22 Feb 99 18:13:04 EST
Contents:
Re: Testing Algorithms (Coen Visser)
Re: Snake Oil (from the Feb 99 Crypto-Gram) (Shai Halevi)
Re: Testing Algorithms (Coen Visser)
Re: Crypt for FTP Protocol (Thomas Wu)
Re: Randomness of coin flips (R. Knauer)
Re: Randomness of coin flips (Darren New)
Anyone know of any good stream chipers? ("Rats")
Re: Randomness of coin flips (Darren New)
Re: Testing Algorithms (Thomas Pornin)
Re: rfc1319 algorithm != reference impl. ???? (Paul Rubin)
Re: Scramdisk File (Jim Dunnett)
Re: Testing Algorithms (Coen Visser)
Re: Randomness of coin flips (R. Knauer)
Re: Testing Algorithms (Withheld)
Re: Public key algorithms (Mr. Tines)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Coen Visser)
Subject: Re: Testing Algorithms
Date: 22 Feb 1999 17:52:16 GMT
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
>Coen Visser wrote:
>
>>fungus <[EMAIL PROTECTED]> writes:
>>>So you think a 256 bit key will eventually be brute forced?
>> Why not? Who can look 50 years into the future or 100 years or 200 years?
>You may be underestimating the steepness of exponentials. 2^256 is a fearsome
>number. Rather than envisioning a machine (or machines) doing trial
>decryptions, try envisioning simply counting up to 2^256.
A working QC [ the successor of the PC ;-) ] could reduce the search space
to 2^128. Still a large number but significantly smaller...
If you are talking about *eventually* brute forcing a key of 256 bits you
don't talk about doing it with technology that doesn't have the potential
of doing it (i.e. current technology). Who knows what technology is capable of
500 years from now. Maybe we've blown ourself to pieces, maybe we've build
machines with computing power beyond your (and mine) imagination.
Regards,
Coen Visser
------------------------------
From: Shai Halevi <[EMAIL PROTECTED]>
Subject: Re: Snake Oil (from the Feb 99 Crypto-Gram)
Date: Mon, 22 Feb 1999 12:18:29 -0500
You're right. I should have been more careful here: Formal, rigorous
treatment of chosen ciphertext security has been around for about 10
years. Specific attacks on "bad implementations" were known pretty much
since day one.
Thanks,
-- Shai Halevi
JPeschel wrote:
>
> >Shai Halevi <[EMAIL PROTECTED]>writes:
>
> >This is irrelevant here, but the notion of chosen ciphertex attacks
> >against public-key encryption has been around for less than 10 years
> >(Naor-Yung'90, Rackoff-Simon'91, Dolev-Dword-Naor'91).
>
> But see: "A chosen text attack on the RSA cryptosystem and some discrete
> logarithm schemes,"
> Y. Desmedt and A. M. Odlyzko, pp. 516-522 in Advances in Cryptology - CRYPTO
> '85.
>
> http://www.research.att.com/~amo/doc/arch/rsa.attack.pdf
>
> The papers references, I think, indicate attacks even earlier
>
> J
> __________________________________________
>
> Joe Peschel
> D.O.E. SysWorks
> http://members.aol.com/jpeschel/index.htm
> __________________________________________
------------------------------
From: [EMAIL PROTECTED] (Coen Visser)
Subject: Re: Testing Algorithms
Date: 22 Feb 1999 19:41:50 GMT
[EMAIL PROTECTED] writes:
> [EMAIL PROTECTED] (Coen Visser) wrote:
>> fungus <[EMAIL PROTECTED]> writes:
>>>So you think a 256 bit key will eventually be brute forced?
>> Why not? Who can look 50 years into the future or 100 years or 200 years?
>
>Anyone with more than 2 brain cells working.
Bad day?
>This gets tiresome. Doesn't anyone know how to do arithmetic anymore???
>
>(1) There are physical limits to how fast we can make computers. We haven't
>reached them yet, but we will.
Yes, but we don't know what those limits are. Only for architectures that
are studied today.
>(2) There are physical limits to how small we can make computers. We haven't
>reached them yet, but we will.
Yes, but we don't know what those limits are. Only for architectures that
are studied today.
>Yes, we can change to faster semi-conductors (e.g. Gallium Arsenide). Yes, we
Computer != semi-conductor.
[...]
>I suggest you do the arithmetic. Assume we have computers that are 10^10
[...]
I suggest you look at what was stated: "So you think a 256 bit key will
eventually be brute forced?"
^^^^^^^^^^
How can you claim that your (engineering) knowledge is still valid 50
or 500 years from now? I think eventually is a pretty long time.
>What is it that drives people to make these wild claims and speculations
>without doing the arithmetic? Computers can not continue to get faster
>indefinitely.
Agreed, but the limits are not known.
Regards,
Coen Visser
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: Crypt for FTP Protocol
Date: 22 Feb 1999 11:53:29 -0800
[EMAIL PROTECTED] writes:
> My users have repeatedly asked if I could add crypt/cipher to my FTPD so I've
> finally got around to looking at it ;) So basically I've trying to find if
> there is some easy to use crypt library that would do something usable in this
> case.
It's been done. Take a look at SRP ftp/ftpd (http://srp.stanford.edu/srp/),
which addresses most, if not all of your issues. It encrypts both data
and control connections, supports strong 128-bit ciphers, retains the
standard FTP user interface, and is backwards-compatible with standard FTP.
It's based on the publicly-available FTP Security Extensions RFC.
There is no restrictive license agreement to deal with; it's completely
Open Source.
> I've looked at "ssh" ofcourse, and if you wanted to just crypt the
> control-session it would be fairly straight-forward to tunnel it, but since
> it is required to crypt the data-sessions as well it makes it more
> complicated. (Far beyond your average user I suspect?) Although ssh2 comes
> with what looks like a library of sorts, ssh2's licence makes it pretty much
> useless in that sense. The "sftp" that comes with it breaks FTP-Protocols
> too much to be really used (still basic ssh challange before it drops down
> into FTP-style protocols).
>
> The problem is, I'm rather a newbie to ciphers. I got the impression that
> "ssh" uses RSA public-key to send across a session-key which is then used for
> IDEA for the remainer of the session. Would this be sufficient? Are there
> better options? PGP? (or is that just RSA again, showing my ignorance :) )
>
> The idea is to add something "not too complex" - to make merging with existing
> FTPD and FTP client code fairly straight forward.
It's slightly more complicated than that - just remember that the best
solutions perform some form of secure authenticated key exchange and use
the exchanged key to encrypt the session. Also keep in mind that SRP is
supported in third-party clients and servers, so that should help with
compatibility issues.
> Well, basically, any information to aid me and further my knowledge will be
> appreciated :)
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "The pen may be mightier than the sword, but my
Phone: (650) 723-1565 mouse can crash Windows with one click."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Randomness of coin flips
Date: Mon, 22 Feb 1999 20:25:03 GMT
Reply-To: [EMAIL PROTECTED]
On 22 Feb 1999 13:04:22 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>>The probem with probability theory, as I see it, is that it is based
>>on the ideal, and the real world is not ideal by any measure. The law
>>of large numbers only tells you the probability of the expectation
>>value (arrived at with an infinite measure), but that does not mean
>>that it must happen with great certainty. Great certainty is obtained
>>by other means than statistics, namely inference/induction.
>No, it doesn't. It tells you the probabilility of the expected value --
>but also the probability of various degrees of divergence from the
>expected value.
+++++
"In everyday language we call random those phenomena where we cannot
find a regularity allowing us to predict precisely their results.
Generally speaking, there is no ground to believe that random
phenomena should possess any definite probability. Therefore we should
distinguish between randomness proper (as absence of any regularity)
and stochastic randomness (which is the subject of probability
theory). There emerges the rpoblem of finding reasons for the
applicability of the mathematical theory of probability to the real
world". --A. N. Kolmogorov (quoted in Li & Vitanyi, p. 52, op. cit.)
"The frequency concept based on the limiting frequency as the number
of trials increases to infinity does not contribute anything to
substantiate the application of the results of probability theory to
real practical problems where we always have to deal with a finite
number of trial." --A. N. Kolmogorov (quoted in Li & Vitanyi, p. 55,
op. cit.)
+++++
>>If you are observing a herd of horses and you spot one unicorn among
>>them, you cannot conclude that unicorns do not exist just because the
>>expectation value for the population of unicorns goes to zero as the
>>number of horses you observe increases without bound.
>
>No. But if I observe an unbounded herd of everything and don't see a single
>unicorn, I can conclude that the probability of unicorns existing is as
>low as I like, depending on how much time I want to sit and watch.
+++++
"... for each eps > 0, the probability that the number S_n of outcomes
1 in the first n trials of a single sequence of trials satisfies n(p -
eps) < S_n < n(p + eps). This is J. Bernoulli's [...] so-called Weak
Law of Large Numbers. This law shows that with great confidence in a
series of n trials the proportion of successful outcomes will
approximate p as n grows larger. [...] Thus, contrary to common
belief, the time average of S_n (1 <= n <= m) over an individual game
of length m has nothing to do with the so-called "ensemble" average of
the different S_n's associated with all possible games (the ensemble
consisting of 2^n games) at a given moment n, which is the subject of
the weak law". --Li & Vitanyi, p. 63, op. cit.
+++++
BTW, no one has commented on whether a (crypto-grade) TRNG can be a
uniform Bernoulli process (p = 1/2). It would seem to be, yet some
people claimed otherwise a year ago when we were discussing random
number generation for the OTP cryptosystem.
Bob Knauer
"If experience teaches us anything at all, it teaches us this: That a good
politician, under democracy, is quite as unthinkable as an honest burglar."
--H.L. Mencken
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Mon, 22 Feb 1999 20:37:53 GMT
> The bits of Chaitin's Halting Probability, Omega, arise from a uniform
> Bernouilli process (p=1/2), namely from inspecting his exponential
> diaphantine equation, or equivalently, inspecting the halting behavior
> of universal Turing machines.
Wouldn't this mean that exactly half of all programs halt? Besides, one
can't compute the bits of Omega, so what does it mean to talk about
their distribution? If Omega's bits are based on the halting problem,
it's not that they're unknown, it's that they're unknowable.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"Be.... the email."
------------------------------
From: "Rats" <[EMAIL PROTECTED]>
Subject: Anyone know of any good stream chipers?
Date: Tue, 23 Feb 1999 10:24:46 +1300
Hi
Just wondering if someone could point me in the direction of good Stream
Chipers. I am interested in the algorithms rather than source code or
executables.
Thanks in advance.
Ratnesh
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Mon, 22 Feb 1999 21:41:46 GMT
> Omega is defined as SUM (p halts) (2^{-|p|}. People have actually
> determined lower and an upper bounds for Omega:
All right.
> One cannot compute the bits with effective (recursive) functions, but
> one can determine experimentally if certain Turing machines do halt or
> not.
Yes, certain machines. But not all. I.e., I can prove some turing
programs halt. I can prove others loop forever. But there are some
programs for which I cannot prove or disprove they halt. Hence, the
value of Omega itself is not well-defined, in some sense, as the value
of "p halts" over which you are summing is uncalculable.
> >If Omega's bits are based on the halting problem,
> >it's not that they're unknown, it's that they're unknowable.
>
> They are unknowable computationally. One can always examine a given
> Turing Machine and see how it behaves. Kinda tedious, but if you are
> being paid out of taxpayer's money, who cares, eh.
No. You've missed the point. You *cannot* examine an arbitrary turing
machine to see if it halts. If you can't tell algorithmically, how do
you know if you're correct when you tell me it does or doesn't halt?
Again, there are three types:
Machines that halt.
Machines that repeat a state. (and hence are provably not going to halt)
Machines that never halt and never repeat a state.
That third set of machines are the ones you cannot compute whether they
halt. Any formula based on whether they halt is questionable at best,
since there's no way to even say that a machine is in that third group,
rather than the first or second. All we know for sure is that at least
one machine is.
Here's the machine: tell me if it halts:
main() {
if (halt(me)) {while (true) do nothing;}
if (!halt(me)) exit(0);
}
(Roughly Cish, but you get the idea.)
Now, examine that simple little machine and tell me if it halts.
The problem with the Haltability of turing machines (again) is not that
there is no algorithm to do it, but that there are machines which you
can build which are contradictory. Reducto ad absurdum. Hence, Omega is
telling you the probablility that a program will do something that
cannot be calculated.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"Be.... the email."
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: Testing Algorithms
Date: 22 Feb 1999 18:06:34 GMT
According to Patrick Juola <[EMAIL PROTECTED]>:
> The fact that doomsayers have been predicting physical limits to
> the maximum speed of computers for 20 years now, and the successive
> violation of these physical "limits" has become routine.
Actually this is not the point. What is important is to realize that,
when science achieves the building of computers that can brute-force
256 bit keys, it will also allow the cheap construction of brain wave
analyzors that will make this whole key-search thing a utterly useless
game. Therefore there is no point in trying to get protection against
such an attack.
--Thomas Pornin
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: rfc1319 algorithm != reference impl. ????
Date: Mon, 22 Feb 1999 22:00:55 GMT
In article <7arnd9$9t$[EMAIL PROTECTED]>,
Adam Worrall <[EMAIL PROTECTED]> wrote:
>In section 3.2 of rfc1319 ('The MD2 Message Digest Algorithm'),
>some pseudo-code for generating an initial checksum is given.
>(Note that this checksum is appended to the data before the
> main message digest algorithm is brought to bear.)
I noticed the same thing a few months ago and emailed Burt Kaliski
(author of the RFC). He replied that the reference implementation was
correct and that a couple of other people had asked him about it in
the previous few months, after several years of no inquiries at all.
Contrary to what I may have said a few months ago, I think an SHA-1
implementation is likely to be faster than MD2 in any reasonable
language at all including 8-bit assembly language and Javascript.
------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: Scramdisk File
Date: Mon, 22 Feb 1999 21:49:13 GMT
Reply-To: Jim Dunnett
On Sun, 21 Feb 1999 16:49:51 -0800, Gregg Berkholtz <[EMAIL PROTECTED]>
wrote:
>Typos for me? Unheard of! :-)
>The strange thing was that I was able to mount and dismount the file multiple
>times before I had this problem.
OK. Then perhaps you aren't using the right pass-phrase, or
at least the pass-phrase that the file was saved with?
Sure you're trying to open the correct file. Correct directory.
As I recall if you have to be careful about what backslashes you
put in the directory name when you tell ScramDisc what to mount.
If your file is, say, C:\scd\scramble.svl, then in the filename
you have to put scd\scramble.svl. If you put \scd\scramble.svl
the mount will fail.
Just a thought. Simple things like that are sent to try us!
>Now, what did you mean by giving the scramdisk more breathing room -- I don't
>believe that scramdisk creates a swap file or any other file outside of what I
>intended it to create (the .SVL file).
Don't know. Just an idea. Perhaps the author of the program can
answer that.
--
Regards, Jim. | An atheist is a man who has
olympus%jimdee.prestel.co.uk | no invisible means of support.
dynastic%cwcom.net |
nordland%aol.com | - John Buchan 1875 - 1940.
marula%zdnetmail.com |
Pgp key: pgpkeys.mit.edu:11371
------------------------------
From: [EMAIL PROTECTED] (Coen Visser)
Subject: Re: Testing Algorithms
Date: 22 Feb 1999 22:19:38 GMT
[EMAIL PROTECTED] (Thomas Pornin) writes:
>According to Patrick Juola <[EMAIL PROTECTED]>:
>> The fact that doomsayers have been predicting physical limits to
>> the maximum speed of computers for 20 years now, and the successive
>> violation of these physical "limits" has become routine.
>Actually this is not the point. What is important is to realize that,
>when science achieves the building of computers that can brute-force
>256 bit keys, it will also allow the cheap construction of brain wave
>analyzors that will make this whole key-search thing a utterly useless
>game. Therefore there is no point in trying to get protection against
>such an attack.
Of course there is. The same company (or its competition) that produces
the brain wave analyzer would undoubtedly sell a high security brain
wave jammer. And so the game goes on and on and on ...
Regards,
Coen Visser
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Randomness of coin flips
Date: Mon, 22 Feb 1999 22:32:00 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 22 Feb 1999 21:41:46 GMT, Darren New <[EMAIL PROTECTED]>
wrote:
>Yes, certain machines. But not all. I.e., I can prove some turing
>programs halt. I can prove others loop forever. But there are some
>programs for which I cannot prove or disprove they halt. Hence, the
>value of Omega itself is not well-defined, in some sense, as the value
>of "p halts" over which you are summing is uncalculable.
I imagine that is why Omega is not better defined.
>No. You've missed the point. You *cannot* examine an arbitrary turing
>machine to see if it halts.
You missed my point - you can examine *some* simple TMs, like the ones
used to set the bounds on Omega.
>If you can't tell algorithmically, how do
>you know if you're correct when you tell me it does or doesn't halt?
I agree, for those TMs. That's why Omega is not known any better than
it is. The same is true of the exponential diophantine equation that
Chaitin mapped the halting problem onto.
You must have thought I claimed that Omega could be determined
exactly, which I did not mean to imply. Perhaps I misinterpreted
statement of yours. Whatever, I never meant to imply that ALL bits of
Omega could be determined by any means. Omega is inherently unknowable
(which is the title of Chaitin's latest book "The Unknowable").
>Hence, Omega is
>telling you the probablility that a program will do something that
>cannot be calculated.
That is the whole idea behing Omega. It is algorithmically
irreducible.
Now I found the paragraph that led to the confusion of what I said:
+++++
The bits of Chaitin's Halting Probability, Omega, arise from a uniform
Bernouilli process (p=1/2), namely from inspecting his exponential
diaphantine equation, or equivalently, inspecting the halting behavior
of universal Turing machines.
+++++
I did not mean to imply that one could actually inspect each and every
entity, be it TM or EDE, and determine all the bits of Omega. I meant
to say that the bits of Omega were dependent on the TMs and the EDEs
in the sense that they arise from whether TMs halt or whether EDEs
have a finite or infinite number of solutions. The term "inspect" is
at fault, since it implied an effective construction - which is not
possible for all bits of Omega with certainty.
Bob Knauer
"If experience teaches us anything at all, it teaches us this: That a good
politician, under democracy, is quite as unthinkable as an honest burglar."
--H.L. Mencken
------------------------------
From: Withheld <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Date: Mon, 22 Feb 1999 22:43:27 +0000
Reply-To: Withheld <[EMAIL PROTECTED]>
In article <7as5gg$dtq$[EMAIL PROTECTED]>, Coen Visser
<[EMAIL PROTECTED]> writes
[cut]
>
>A working QC [ the successor of the PC ;-) ] could reduce the search space
>to 2^128. Still a large number but significantly smaller...
>
>If you are talking about *eventually* brute forcing a key of 256 bits you
>don't talk about doing it with technology that doesn't have the potential
>of doing it (i.e. current technology). Who knows what technology is capable of
>500 years from now. Maybe we've blown ourself to pieces, maybe we've build
>machines with computing power beyond your (and mine) imagination.
>
Given some of the original mumblings about biological computers based
around DNA it's entirely possible to exceed the current understanding of
where machines are going.
--
Withheld
------------------------------
From: Mr. Tines <[EMAIL PROTECTED]>
Subject: Re: Public key algorithms
Date: 22 Feb 1999 22:23 +0000
###
On Sun, 21 Feb 1999 19:09:13 -0000, in
<[EMAIL PROTECTED]>
"Alan Kelly" <[EMAIL PROTECTED]> wrote.....
> Does anyone know where I can get some source code for a public key
> encryption algorithm, or at least some good information so that I can
> implement my own?
http://www.windsong.demon.co.uk/ctclib2_1.zip
has RSA, in rsa.c and Elliptic curves on GF(2^255) in ec_crypt.c
(these call into other source files).
-- PGPfingerprint: BC01 5527 B493 7C9B 3C54 D1B7 248C 08BC --
_______ {pegwit v8 public key =581cbf05be9899262ab4bb6a08470}
/_ __(_)__ ___ ___ {69c10bcfbca894a5bf8d208d001b829d4d0}
/ / / / _ \/ -_|_-< www.geocities.com/SiliconValley/1394
/_/ /_/_//_/\[EMAIL PROTECTED] PGP key on page
### end pegwit v8 signed text
2255ebad80db7bf263d4287a461b8116eb1da578699efa65d4747bc4715e
85981d69fc76dffcc521613fdb7332485f3b7f4951d841b901f7b147fc1d
------------------------------
** 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
******************************
