Cryptography-Digest Digest #41, Volume #9 Fri, 5 Feb 99 17:13:04 EST
Contents:
Re: *** Where Does The Randomness Come From ?!? *** (R. Knauer)
Re: Threat Models: When You Can't Use a One-Time Pad (R. Knauer)
Re: cryptology in physics (R. Knauer)
Re: Metaphysics Of Randomness ("Tony T. Warnock")
Re: Metaphysics Of Randomness (R. Knauer)
Re: [question/challenge/HELP ME! IEE!] Another unheard of punk who thinks hes come
up with something new... (Vektor)
Re: [question/challenge/HELP ME! IEE!] Another unheard of punk who (Vektor)
Re: XOR encryption... (Jim Gillogly)
Re: Rational points on a curve ([EMAIL PROTECTED])
Re: Engima (John Savard)
Re: Some more technical info on Pentium III serial number ("Roger Schlafly")
Fwd: cryptology in physics (Kevin C Gotze)
Re: Foiling 56-bit export limitations: example with 70-bit DES ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To: sci.skeptic,sci.philosophy.meta
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Fri, 05 Feb 1999 20:15:01 GMT
Reply-To: [EMAIL PROTECTED]
On 5 Feb 1999 17:18:53 GMT, [EMAIL PROTECTED] (Seisei Yamaguchi) wrote:
>>>Randomness and unforeseeableness are not identical.
>>Why not?
>Randomness:
> No way to processing.
> And, cannot create the way, forever.
>Unforeseeableness:
> From not enough knowledge ---and/or speed--- to processing it.
> AD0019th_century's and AD0020th_century's are not same.
Then by the term "unforeseeable" you mean that something is not known
now but might later. I thought you meant unpredictable, which means
that something is not known now, and will never be known by a formal
procedure.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Threat Models: When You Can't Use a One-Time Pad
Date: Fri, 05 Feb 1999 20:30:15 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 05 Feb 1999 13:54:48 GMT, [EMAIL PROTECTED] wrote:
>I would not normally
>anwser more stuff about OTP's since the subject is a never ending
>tale.
Yes it is - and for good reason.The concept of crypto-grade randomness
is especially difficult for those who insist that it is a property of
numbers themselves.
And even the simplest specification for a TRNG can be misinterpreted
by mathematical and computer formalists. Pretty soon it all depends on
what the meaning of 'is' is. :-)
This is not a trivial subject.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: cryptology in physics
Date: Fri, 05 Feb 1999 20:32:11 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 05 Feb 1999 18:19:24 -0800, David Leuenberger
<[EMAIL PROTECTED]> wrote:
>Cryptology is a discipline taking place in an abstract number place
>(it's a mathematical discipline)
>I wonder if there are analogous mechanism to the Alice-Bob-Eve-pattern,
>to one-way-functions and to zero-knowledge-protocols in general physics,
The concept of crypto-grade randomness suitable for the proveably
secure OTP cryptosystem has close ties to Quantum Mechanics, in that
both are based in indeterminism.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Fri, 05 Feb 1999 14:00:05 -0700
Reply-To: [EMAIL PROTECTED]
R. Knauer wrote:
> On Fri, 05 Feb 1999 08:12:26 -0700, "Tony T. Warnock"
> <[EMAIL PROTECTED]> wrote:
>
> >My example of Champernowne's number shows that a
> >computation that provable generates all k-bit sequences with the proper
> >frequency (1/2^k) cannot be random because some million bit subsequences
> >cannot be generated in the first million bits.
>
> Champernowne's number is not normal in base 2, only in base 10.
The Champernowne construction works in all bases. In fact all my postings
have been in base 2.
11011100101110111...
Tony
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Fri, 05 Feb 1999 21:17:56 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 05 Feb 1999 14:00:05 -0700, "Tony T. Warnock"
<[EMAIL PROTECTED]> wrote:
>> Champernowne's number is not normal in base 2, only in base 10.
>The Champernowne construction works in all bases. In fact all my postings
>have been in base 2.
>11011100101110111...
>From Greg Chaitin's paper entitled: "Randomness in Arithmetic and the
Decline & Fall of Reductionism in Pure Mathematics" at:
http://www.umcs.maine.edu/~chaitin/unm.html
and also reprinted in his 1998 book "The Limits Of Mathematics"
http://www.umcs.maine.edu/~chaitin/lm.html
"This is called Champernowne's number and Champernowne showed that
it's normal in base ten, only in base ten. Nobody knows if it's normal
in other bases, I think it's still open."
Maybe you need to tell Greg Chaitin something he doesn't know.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: Vektor <"vektor_"@hotmail.com(orsoyouthink!)>
Subject: Re: [question/challenge/HELP ME! IEE!] Another unheard of punk who thinks hes
come up with something new...
Date: Fri, 05 Feb 1999 16:27:24 -0500
[EMAIL PROTECTED] wrote:
>
> > > You have just reinvented the stream cipher.
>
> > > Of course, if your PRNG is strong, then your algorithm is strong. RC4 has
> > > yet to be broken and is still used for SSL. (However there are things you
> > > must keep in mind. F'rinstance, since the stream is identical every time,
> > > you can never encrypt using the same key twice. IV's can help prevent
> > > this.)
> > >
> > > Nate
> >
>
> > (btw, if your going to reply to a post, its usually courteous to read
> > the ENTIRE strand, rather than reading the last message and throwing in
> > your 2 cents. my method is NOT RC4.)
> >
>
> I read the whole thread. I'm no crypto-head. We're probably on the same
> level, but I must feel that having read Bruce Schneier's book Applied
> Crytography vests me with some sort of authority to reply.
>
> assertions: 1) the math that good cryptographers understand and have at
> their disposal is beyond anything mere mortals can comprehend 2) this math
> can possibly be used to generate functions which recreate your pseudo-random
> sequence with much less effort than you believe required 3) take assertion
> 2 and combine it with the fact that a lot of computers can do the work of
> 8.9 years in 4 weeks and you see the effort is mostly automated (see
> crypto.sci.Factorization of RSA-140 with the Number Field Sieve) 4) while
> I've got assertion 4 up, let me throw in that to me the NFS (number field
> sieve) looms ominously at the forefront of my mind whenever I decide to try
> and come up with a crypto-system. I don't know what the heck it is, but if
> it can factor 42-digit (base 10) numbers in 4 weeks ....
>
> advice (not answers or protocol evaluation) begins: I'm not knocking your
> system - hell, I can barely cryptoanalyze Wheel-of-Fortune puzzles (with
> R,S,T,L,N and E =o) - but I wouldn't count on the security of your system.
> It seems strong enough to deter casual eavesdroppers (like me), but I
> wouldn't run out and spend any money on patents. This next part I do know
> though. Your PRNS and the keys are the ONLY security of your system. The
> reason is this. Good practice is to assume that your algorithm is known, and
> this practice isn't very far from the truth of the matter. You've already
> told me what compiler you've used (VB5), so now I can find a VB5 decompiler
> and take a look at an equivalent of your source code, or failing that, (if I
> were good at ASM,) I always have the option of disassembling your code to see
> how your encryption and decryption tables are constructed. And if in the
> reverse engineering of your program, I find that your PRNS is not based on
> any external random events (user input, mouse clicks, drive seek time which
> is affected by air friction, or other such events), then I myself could
> reconstruct your PRNS, even if it were based on system time (theoretically,
> anyways.... I probably couldn't do it easily, but I can think of people who
> can .... like the students at Berkeley who were able to hack Netscape's
> security because they figured out what clock time the Netscape systems used
> to generate their PRNS). Even people who know what they're doing (Ron Rivest,
> the-'R'-in-RSA-guy, for example) have come up with algorithms that have been
> cryptoanalyzed.
>
> Side note 1: I'm working on a crypto-scheme myself, so I've gone through
> some of your frustration. I've consigned myself to avoid developing
> crypto-systems until I understand, at least, the math that is currently used
> to break them: number theory, linear cryptanalysis, diffential crytanalysis,
> quadratic sieve, and number field sieve, etc. I'll probably just use RSA
> since I think I actually understand the math to it (and I like to understand
> my programs) and that it's patent will expire by the time I'm ready to
> market anything (Sept 7, 2000, I think).
>
> Side note 2: the author of the previous post may have been suggesting you use
> RC4, since it's patent's expired. Just don't call it "RC4," which is
> trademarked, or something ....
>
> Side note 3: Your tables are forms of S-Boxes. :-) Now you know what they
> are.
>
> Why conform?
>
> ...by the way, where are we going? And why am I in this handbasket?
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
heh...i'm a programmer by profession, if anyone knows how easily
programs are broken, its me :). Yes, I'm already going under the
assumption that anyone who wants to break the algo, already has the
exact details of how it was created. My attempt at this algo was
something that you couldn't just break, knowing how the cipher was
created, that you (hopefully) had to know both of the keys.
i explained it poorly, thus all the silly confusion thats resulted. I've
posted a better explanation in another thread :).
-Alex
------------------------------
From: Vektor <"vektor_"@hotmail.com(orsoyouthink!)>
Subject: Re: [question/challenge/HELP ME! IEE!] Another unheard of punk who
Date: Fri, 05 Feb 1999 16:20:28 -0500
> I did. And I did not claim your method == RC4. I merely pointed out RC4
> as an example of an encryption algo that is essentially a PRNG. Yours is
> also essentially a PRNG unless I completely misunderstand you, which I do
> not think would be entirely my fault ;). Virtually all stream ciphers are
> basically PRNGs. The underlying mechanism for the stream may be completely
> different, but the concept is identical--you have a state array initialized
> according to the seed/key, from which you extract a stream and XOR against
> the plaintext (like RC4). (as opposed to a fundamentally different concept,
> say a Feistel network (like RC5/6 or Twofish or DES), or prime factoring
> (like RSA), or the logarithms (DH))
well...i humbly apologize for anything that i may have thought (or
written ;)) ... looking back on it, my explanation WAS fairly ambigious.
i'm going to start another thread, and HOPEFULLY (hope, prays) I can try
and explain it a little (alot) better.
-Alex
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: XOR encryption...
Date: Fri, 05 Feb 1999 13:36:45 -0800
Reply-To: [EMAIL PROTECTED]
Binder Edgar wrote:
> Jim Gillogly wrote:
> > In any case, since you say "password", it could be subject to a
> > dictionary attack. For any data that's worth anything, the
> > cryptanalyst will have a way to test whether the resulting
> > plaintext is meaningful, so trying lots of possible passwords
> > and decompressing the result should result in something testable. ...
>
> The only thing that compresses efficiently the BWT output is a fast
> adaptive entropy coder. AFAIK, adaptive entropy coders don't leave anything to
> test.
If the correct password is guessed, then the decompresser will produce
the plaintext. If the plaintext is valuable to the cryptanalyst, it
can be tested by whatever she would use to determine its value. Normally
it's easier: the plaintext would be a text file, a program, a formatted
transaction, coordinates, or something else recognizable. That's what
I meant by testing the result of a dictionary attack. For this approach
I was not suggesting testing the ciphertext.
> > individual ARJ files. Still, something messier than a straight XOR
> > with your password will give you better security.
>
> What exactly do you mean by something messier than XOR ?
I mean something more secure, like a modern fast encryption algorithm.
> What is RC4 ?
A modern fast encryption algorithm. See http://ciphersaber.gurus.com
for some pointers.
> > taking the time to compress it, you're not all that worried about
> > nibbling every microsecond off the processing time.
>
> Well, actually I am pretty worried about the encryptor, because the
> archiver will compress 2-3 Mb/Sec on a P200.
A good fast encryption algorithm should cost much less on a P200.
Check out some of the AES candidates, for example. There's a cross-table
at http://home.cyber.ee/helger/aes/table.html (I don't vouch for its
timeliness). Some of these algorithms are unencumbered (i.e. no
intellectual property restrictions).
> Sorry about my bad english...
Viel besser als mein schlechtes Deutsch!
--
Jim Gillogly
Trewesday, 15 Solmath S.R. 1999, 21:24
12.19.5.16.10, 4 Oc 3 Pax, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Rational points on a curve
Date: Fri, 05 Feb 1999 21:27:11 GMT
In article <79fdjf$59t$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jayant Shukla) wrote:
> Hi,
> Is there an easy way to find integer points on
> the curve y^2 = a x^2 + b x + c? i.e. both x and y
> are integers. The constants a, b, and c are integers
> as well.
Yes. It is trivial.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Engima
Date: Fri, 05 Feb 1999 21:40:20 GMT
"Ashley England" <[EMAIL PROTECTED]> wrote, in
part:
>Does anyone know where i can get plans of the enigma?
The way the Enigma works is explained, with diagrams, at my site and
in other sites.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,comp.sys.intel
Subject: Re: Some more technical info on Pentium III serial number
Date: Fri, 5 Feb 1999 13:11:33 -0800
bill davidsen wrote in message
<79ffup$198c$[EMAIL PROTECTED]>...
>Speculation that the CPU will send things unasked (ie. without software
>help) over the net, or "automaticaly detect a network connection" as one
>poster put it, is just amazing. Any one who has tried to make a system
>see find a network connection without significant help from the o/s will
>realize that even assuming Win2001 running, this is not going to happen,
>since it's cheaper to put the logic in the o/s.
The Intel plan had 2 parts:
(1) put a serial number on the CPU;
(2) distribute software which sends identifying information over the
net unasked.
It is the combination that people are objecting to.
>Somehow I can't see anyone selling a browser which makes use of this,
>because there are so many people who wouldn't want it.
You probably also thought that no one would sell a browser that
uses cookies. These things happen unless people object, and
you are watching the objections.
------------------------------
From: Kevin C Gotze <[EMAIL PROTECTED]>
Subject: Fwd: cryptology in physics
Date: Fri, 5 Feb 1999 16:49:21 -0500
On Fri, 05 Feb 1999 18:19:24 -0800, David Leuenberger
<[EMAIL PROTECTED]> wrote:
>Cryptology is a discipline taking place in an abstract number place
>(it's a mathematical discipline)
>I wonder if there are analogous mechanism to the Alice-Bob-Eve-pattern,
>to one-way-functions and to zero-knowledge-protocols in general physics,
I didn't do very good in quantum but,
there was talk of using partical decay as a way of key exchange. a
certain particle decays to 2 smaller ones... one of spin up and one of
spin down(it always happens this way due to conservation of spin). bob
gets one particle and alice gets the other. they measure the spin of
their particle and one of them says in public " you keep all yours,
I'll flip all mine". they each now have the same spin either both up or
both down. they've just secretly agreed upon a bit. this is supposed to
be secure because any attempt to passively measure the spin on a
particle will violate hisenberg uncertanty and thus is impossible.
interception and retransmission of a similar particle is confounded by
this being a random process happening at relativistic speeds.
thus it is considered "physically" secure.
Kevin Gotze
sophmore
ECE/physics CMU
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Foiling 56-bit export limitations: example with 70-bit DES
Date: Fri, 05 Feb 1999 16:55:42 GMT
In article <79dtqr$vu1$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
[snip]
> |The reasons why adding a previous encryption to the plaintext is less
> |effective than adding post encryption to the ciphertext are, mainly:
I believe we are close to understanding one another. I agree that adding a
previous encryption to the plaintext is less effective than adding post
encryption to the ciphertext. What I haven't seen you address is doing BOTH
(i.e., adding a previous encryption to the plaintext, AND ALSO adding THE SAME
post encryption to the ciphertext).
[snip]
> First, let me discuss your assumption. You suppose that repeating the DES key
> for the same message would make the post-encryption in M-DES less secure. I
> affirm that this is not the case, not even for the same repeated M-bit
> unknown-key. Can you please tell me how you derived your assumption? Maybe I
> can more easily spot the difficulty if you tell me the steps you took -- of
> course, using the protocol given in http://www.mcg.org.br/unicity.htm
Ciphertext sent to alice, C1 --> DES(M) XOR unknown_key1
Send same message again, with same DES key, C2 --> DES(M) XOR unknown_key2
If Mike knows that you sent the same message again, with the same DES key,
then Mike can derive: unkown_key1 XOR unknown_key2 == C1 XOR C2. If
unkown_key1 and unknown_key2 are entries in a publically known table, Mike's
search time may have just been drastically reduced, since he knows you used
two of the entries that, when XORED together, are equal to C1 XOR C2.
This weakness disappears if you a) use a block cipher for the post-encryption,
and/or b) do BOTH pre-encryption AND post-encryption.
[snip]
> This is not the issue here -- and, as everyone that has tried (did you?)
> knows, each case is different. Indeed, the US export law seems to be quite
> different for Netscape with 40-bit encryption for export and PGP that exports
> strong encryption -- both, US companies and US-made software.
Each case is different, but if you propose to export a cryptosystem that does
DES encryption with a 56-bit key, and then post-encrypts with an M-bit key
(with M not equal to zero), you WILL NOT get mass-market approval. It's
called "multiple encryption."
PGP doesn't export strong encryption software, they skirt the law by
"publishing a book" about strong encryption software. If you are willing to
go that route, you don't need any tricky schemes to implement 70-bit DES
while claiming to the government that it's really only 56-bit DES.
> However, you must not ignore that the US-sponsored change in the Wassenaar
> Arrangement was exactly targeted to harmonize different criteria, inland and
> abroad. Some have applauded the intiative as "loosening up the US export
> restrictions" ... others have decried the initiative as "depriving the world
> of its privacy". However, as I commented in the thread "On leaving the 56-bit
> export limitation" -- both sides are mislead. The number of bits in a
> secret-key is NOT a good metric for the security of the corresponding cipher.
> Which was the motivation for this thread -- to show that, yes, keep only
> 56-bits secret ... we can still bootstrap that to 70-bit or even more to
> 120-bit ... or even more as I will post here in the next days.
Multiple encryption regulations can be circumvented, but only if you can make
the case that you don't and can't know that multiple encryption is taking
place. For example, you could get export approval for software that encrypts
a file with 56-bit DES, places it in an accessible location on the web, and
securely transmits the DES key to Alice. Now, if Alice retrieves the file
during an SSL session, the multiple encryption is not the fault of any of the
software packages used, so the fact that this can happen does not, by itself,
make any of them un-exportable.
[snip]
> And, this cannot be stopped by any regulation because it does not really
> depend on the cipher (eg, DES) or the export-free software that implements
> it, but how it is used -- which is as diverse as there are users and
> applications. Since, here, the brute-force strength derives not from the
> secret-key strength (but, from "open ignorance"), there is nothing that the
> export-free software would need to do differently -- since the export-free
> software deals only with the secret-key part, which can be 56-bit without
> compromising security.
But how will you integrate the DES and the M-DES? How do you make software
package X, which uses DES, use M-DES, instead?
> This is the point here -- secret-key bit-length is not the deciding factor to
> grade the security of cipher systems. And, what is -- cannot be controlled by
> controlling cryptography.
Regulations can't stop guys like us from writing and distributing such
schemes, but they are very effective at stopping mainstream companies from
doing so.
[snip]
> "BZZT!" was not meant to be hostile ;-) However, it was IMO a just complaint
> in a good-natured graphical way -- an alarm. Apparently, you had lost your
> line of argument in the same e-mail. First, you said that M-DES was "too
> strong" for US-export laws ... then you said it had 56-bits...and I called
> out the contradiction plus an empty statement.
M-DES is too strong for U.S. export, as far as I can see. Maybe you could
describe for me an example of a cryptosystem that uses M-DES, and the software
packages that you would try to submit for export approval?
Furthermore, I think that the scheme I proposed is an improvement on M-DES --
if you are willing to slow Alice down by an additional factor of four, you
can slow Mike down by an additional factor of four times the number of blocks
in the message (both are still slowed in decrypting the first block by adding
M bits to the effective keysize).
[snip]
> > I can name a weakness. The post-encryption is much easier to break if
> > the same message is sent twice with the same DES key.
>
> Why? Please prove that sending the same message twice with the same DES key
> makes **the post-encryption** easier to break -- where I accept that you
> focus only on the M-DES post-encryption mechanism with the XOR choice (even
> though XOR is just one example, from all possible choices such as RC4, RC5,
> RPK, Twofish, etc).
>
> Please, consider also the two possible cases: equal unknown-key and different
> unknown-keys in each transmission -- if you think that changes anything.
> Please, read also what the paper says about it.
See above.
[snip]
> Thanks for the questions! Sorry for the l o n g answer but I though that
> less would not touch all the points.
I'm glad to know you're not as annoyed with my questions as I thought you
were.
--
Peter
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
