Cryptography-Digest Digest #940, Volume #8 Thu, 21 Jan 99 01:13:03 EST
Contents:
Re: Metaphysics Of Randomness (Darren New)
Re: Metaphysics Of Randomness (Darren New)
Re: Word List Utilities (Myself)
Re: 3DES cracked in 22 hours ??? (Was: Re: (fwd) DES Challenge III (William Hugh
Murray)
Re: Metaphysics Of Randomness (Darren New)
Re: Pentium III... ("Trevor Jackson, III")
Re: Metaphysics Of Randomness (Darren New)
Re: Random numbers for C: The END?
Re: Pentium III...
----------------------------------------------------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Thu, 21 Jan 1999 04:09:10 GMT
> >(Of course, I'm of the opinion that the mathematics of finite stuff is
> >"computer science",
>
> You obviously don't work with Windows.
>
> >which is anything but boring... :-)
>
> On the other hand, maybe you do work with Windows.
You're making the mistake of thinking that someone building Windows
actually understands computer science. ;-)
> Yeah, it depends on our appreciation of the fact that a proposition,
> like the Godel statement, cannot be expected to be proved.
That elegantly summarizes what I meant to say.
> Chaitin shows that one cannot prove the randomness of a number of
> complexity N with a formal system that is less complex than N.
Cool. Again, I need to read his book, I guess.
> Then it would seem that determinism is not a significant property of
> this kind of randomness.
That's correct.
> Chaitin defines what he means by random in clear unequivocal terms. He
> even gives a calculation to show whether a number is random in his
> theory, and how many of them you can expect for a given complexity
> cutoff.
That's what I would expect from a mathematician, yes. :-)
> I believe you joined us after that preliminary definition had been
> laid down in another thread, before this thread was begun.
Quite likely.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Thu, 21 Jan 1999 04:13:39 GMT
Patrick Juola wrote:
> I should certainly hope you've seen no such proof, as it isn't
> true. If you restrict your problem to a finite domain, then the
> halting problem can be solved by a table lookup.
I'm unsure whether the halting problem is actually impossible to resolve
if you restrict yourself to turing machines whose initial state can be
specified by a bounded number of bits but whose execution can use an
unbounded number of cells on the tape. (This is different from saying
the turing machines are in a finite domain, I think.) For example, can
you write a program that will tell you, for each turing machine with
fewer than 1000 states and which all start with an all-blank but
infinite capacity tape, whether each of those machines will halt? I'm
not sure, and it's too late today to try to figure it out. But it's not
obvious to me that a human could determine that, so it's unclear how
you'd write the program.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: [EMAIL PROTECTED] (Myself)
Crossposted-To: alt.2600,alt.hacking,comp.security.misc,comp.security
Subject: Re: Word List Utilities
Date: Thu, 21 Jan 1999 03:35:46 GMT
I've changed the groups this was crossposted to, I think they're more
appropriate. The original thread was about sorting dictionaries for
crack, but in this reply I raise what I think is an interesting point
about the vulnerabilities of assigned "random" passwords.
On Wed, 13 Jan 1999 02:36:08 -0000, "donoli" <[EMAIL PROTECTED]>
wrote:
>I have a program called dict.zip It won't do anything w/ your files but
>you can make any size word file you want. Just watch how big you make the
>file. It took me three days to realize why I had only 2% of a 3 gig HD
Err, well that's not going to do you much good. Sure it'll make a big
list of random characters but any program can do that. The reason we
use dictionaries instead of just randomly or systematically checking
every combination, is that people are more likely to use words as
passwords (hence the term passWORDs) and there are a lot fewer words
than there are random combinations.
I've heard of programs that'll parse all the text on your hard drive
(or the drive of a system you've "acquired") and build a dictionary
containing all the words it finds. (The beginning of many a search
engine, no doubt!) This strikes me as very useful, especially if the
user's personal works (saved email, work files, perhaps even web
cache) are on the drive, as it'll contain words that they specifically
are interested in, which might not appear in other dictionaries.
What would be REALLY effective, is a list of the passwords that people
have FOUND in passwd files, or in other password repositories
(unencrypted files perhaps.. insecure non-unix systems are great for
this, or through BO password dumping).. Has anyone ever compiled a
list like this? It'd be particularly useful on a college campus,
something like this....
Let's say that the university systems are fairly secure.. Shadowed,
the root users are never drunk, etc.. And just to make things
interesting, let's say the university has an assigned-password policy
that generates a random-gibberish password and assigns it.
Plain-english passwords are not allowed. So even if someone DID get a
list from this place, cracking it would be hell. (Actually if I'm
right, this might be their biggest mistake. Read on.)
First vulnerability, common to all systems:
Now let's say that elsewhere in this college town is a web cafe. The
connections are useless because every dorm room has a 10baseT jack in
it, except for one group of students: The ones that don't have
computers in their rooms. (Read: the computer-stupid ones). These
students, while they're sucking down caffeine, are likely to create
their web cafe IDs with the same login names and passwords that they
use on the secure system. Here's your hole. Break the cafe. It's not
hard, lots of them use a "security system" which is basically an MS
Access database with a front end that only lets you start certain
programs and keeps track of your time used/remaining.
I don't want to give a recipe for this, but let's just say with a
little creative exploration of the cafe's net mounted drives, you
might find said database, plaintext. Get that critter and put it
somewhere you can retrieve it later. (A floppy in your pocket works to
a point, but it's damning evidence if you get caught.) Sending it to a
pseudonymous shell somewhere is much better.
When you get home, open that file and dump the interesting fields as
ASCII into another file, and load THAT into your cracker. Try it on
some of the passwd files you've found from the university. I betcha
dollars to double-lattes, that a handful of morons recycled their
passwords. And I bet the cafe user "doenut" has the same password as
the university acount "jdoe".. so even if you don't have a passwd file
to crack, a little optical parsing and some sophisticated wetware
algorithms will lend a couple of user/pass matches between the
systems.
So here's a security tip! Don't use the same password on more than one
system. If one's compromised, your accounts on the others are too.
Second vulnerability, only applies to assigned-password systems:
For the code-heads out there.. Does anyone know anything about the
PRNG's (Pseudo-Random Number Generators, for the uninitiated
(unseeded?) among us) that the gibberish-password generators use? My
logic is this:
If the server which assigns you a password is using its
seconds-since-boot timer as a seed for the PRNG, and if most passwords
are generated at the beginning of the schoolyear right after the
system's been screwed with by the admins, then it's probably undergone
a few reboots in the last couple weeks and the timer value is likely
to be relatively low, at least in the first few million seconds. Valid
so far? And if the code isn't done too well, then it re-seeds the PRNG
every time the password maker is invoked, instead of saving its state
for next time.
So get ahold of the code they use to make random numbers into
passwords, and run it in a loop.. Generate one entry in your
dictionary file for each possible value of timer since startup.. Let
it run for about 2 weeks' worth of seconds. Then sic your cracker on
the passwd armed with the dictionary and let 'er rip.
Is it just me, or is this too simple?
-Myself-
.nosig
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Subject: Re: 3DES cracked in 22 hours ??? (Was: Re: (fwd) DES Challenge III
Date: Wed, 20 Jan 1999 21:36:24 -0500
This is a multi-part message in MIME format.
==============5D0D735D0057F7E2A0B1A810
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Yes. 2^55 x 22 hours. You should live so long.
"Gary Cowell (QI'HoS)" wrote:
>
> Said Mok-Kong Shen <[EMAIL PROTECTED]>
>
> >RSA Code-Breaking Contest Again Won by Distributed.Net and
> >Electronic Frontier Foundation (EFF)
> >
> > DES Challenge III Broken in Record 22 Hours
>
> When I first heard the news about this, someone said Des three has
> been cracked in 22 hours.....
>
> I took this to mean 3DES or tripple des had been cracked in 22 hours
> which is patently not the case.
>
> Needless to say I was somewhat sceptical of the initial report :-)
>
> Any extrapolations on how long it would take to crack 3DES at the same
> key rate as was used during DES challenge III ?
==============5D0D735D0057F7E2A0B1A810
Content-Type: text/x-vcard; charset=us-ascii;
name="whmurray.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for William Hugh Murray
Content-Disposition: attachment;
filename="whmurray.vcf"
begin:vcard
n:Murray;William Hugh
tel;fax:800-690-7952
tel;home:203-966-4769
tel;work:203-761-3088
x-mozilla-html:FALSE
org:Deloitte Touche
adr:;;24 East Avenue, Suite 1362;New Canaan;Connecticut;06840;
version:2.1
email;internet:[EMAIL PROTECTED]
title:Executive Consultant, Information Security
x-mozilla-cpt:;-1
fn:William Hugh Murray
end:vcard
==============5D0D735D0057F7E2A0B1A810==
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Thu, 21 Jan 1999 04:48:56 GMT
R. Knauer wrote:
> >No. Even if you don't run it. Either it'll halt were you to run it long
> >enough, or it wouldn't halt were you to run it no matter how long you
> >let it run. There's no need to run it to classify it as a program that
> >halts or not in order to know that. That's the point I've been trying to
> >make. You only need to run it to find out whether it halts or not,
> >assuming it halts and you run it long enough.
>
> That does not seem to agree with what is contained in Turing's halting
> problem.
You're mistaken. That is what's in the halting problem. Every machine
will either halt, or it won't. It can't do both, and it can't do
neither. This isn't QM with overlapped non-collapsed state vectors.
> >It *is* deterministic. It's merely uncalculable. But it's value doesn't
> >change from moment to moment.
>
> It does not have a value. Each bit is indeterminate.
Indeterminate is not the same as nondeterministic. Especially when
talking about Turing machines. If Chaitin is going to redefine 'turing
machine' to be something else, then this discussion is as pointless as
if he's talking in Martian. :-)
>
> >Just like whether that nucleus popped five minutes ago is deterministic:
> >yes or no, 100% or 0%. It's only unclear if you start talking about the
> >future.
>
> I think you are using the term "deterministic" in a much different
> sense than what Chaitin means by it. He means (and I have followed his
> convention) that something is algoritmically indeterminant. In that
> sense, you cannot calculate the individual bits of Omega, or calculate
> the time of the individual decays of a radioisotope.
Well, he shouldn't redefine "deterministic" when talking about turing
machines to mean something other than what Turing meant.
Here, I'll define a Turing Machine as something that always halts. ;-)
> You are using the term in the sense of state machine determinism, that
> each state follows from a prior deterministic state. But that is also
> true of formal axiomatic systems, and yet there are propositions in
> those systems which cannot be decided formally - that is, they are
> indeterminate in the sense Chaitin means by the term.
Yes! Right! Guess what a turing machine is? It's a state machine! :-)
Indeterminate is not the same as nondeterministic.
> Please explain your take on the halting problem in unequivocal terms
> so we can have a point of departure for subsequent discussions. Can it
> be determined algorithmically whether any general program halts or
> not?
No. For some programs, yes, but for others no.
> Can it be determined experimentally whether any general program
> halts or not?
No. You can only reliably determine it experimentally for machines that
get stuck in a finite-sized loop, or which halt.
> >Right. And that only happens because TMs are infinite. It isn't because
> >TMs are nondeterministic. It's because they're infinite in size.
>
> Again you seem to be using the term "deterministic" in a different way
> from what Chaitin means and what I always thought was meant. To me,
> determinism means exactly what it says - that something can be
> determined unambiguously.
Yes. And in Turing Machines, you can unambiguously determine that in a
certain state, what state the machine will move to next. 100% all the
time. In exactly the same way that you can say "Given a string in a
formal system and an application of a transformation rule, give me the
new string." That's what formal systems are for.
What you cannot determine is whether any particular state will ever be
reached from the start state, or whether any given theorem can ever be
generated from a base set of axioms.
> Just because each state of a TM is deterministic does not mean that
> the halting or non-halting of any program is deterministic,
Yes, it does, assuming you mean the same thing by "deterministic" as
Turing does. (I'll grant Chaitin defining "random", but I don't think
he's wise in *re*defining "deterministic".) That the halting value of a
TM is deterministic follows from the definition of the state machine.
The fact that you can't figure it out doesn't mean there's no answer.
This isn't QM here. This is math. What I'm saying is similar to saying
"the fact that we cannot produce the full decimal expantion of sqrt(2)
doesn't mean there's no such number, or that the number somehow doesn't
exist in some fundamental way." There *is* exactly one value that is
sqrt(2), even if you can prove that nobody can write down what that
value is. If you want to define "deterministic" such that sqrt(2) is
nondeterministic, then this is a pointless dicussion to continue,
because you're (or Chaitin is) redefining broadly accepted words with a
very definite meaning in the field he's talking about. A TM does the
exact same thing every time you run it. If it halts, it will always
halt. If it doesn't halt, it will never halt no matter how often you run
it. That's what deterministic means when you talk about TMs. Which means
that each bit of Omega has exactly one value, never changing.
If the halting value of the TM was really nondeterministic, then there
wouldn't be *one* value for Omega. Omega can be deterministic yet
impossible to calculate. Nondeterminism is just one reason for something
being impossible to calculate; the two words don't mean the same thing
in any branch of computer science or Turing Machine theories. If
Chaitin uses these terms interchangably, he's going to wind up with
papers as incomprehensible as if someone started talking about "wave
functions" and use the term interchangably with "wavelength" in physics,
or if he redefined "irrational number" to be one that's less than 100.
> any more
> than the fact that a formal axiomatic system is deterministic yet
> there are propositions which are indeterminate.
If you switch back and forth between "indeterminate" and
"nondeterministic", then you're redefining "nondeterministic", which
would normally be OK as long as you're not talking about turing
machines.
Note: There *is* a definition for "nondeterministic turing machine".
It's one that if you run it many times, sometimes it'll halt, and
sometimes it won't. (Amongst other properties, of course.) It does this
because its instructions are ambiguous, and sometimes it choses one set
to follow, and sometimes it choses another set to follow. Hence, saying
something calculated by a deterministic TM is nondeterministic is ...
well, just plain incorrect. A nondeterministic TM has the same
relationship to a deterministic one as an unmeasured event has to one
which you measured but which has a 50/50 probability of having happened.
Think of nondeterminism like an unobserved event, not like an event
which we can't predict in advance but we can measure; the two cause
fundamentally different results. (Maybe I'm stretching the QM here ...
I don't know much QM. I'm sure it shows. :-)
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
Date: Wed, 20 Jan 1999 22:46:41 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Pentium III...
Read the fine print. The purpose is to *identify* the user, not assist him.
Brad Aisa wrote:
> fungus wrote:
> >
> > Intel has announced that the Pentium III will have a built in hardware
> > random number generator, and individual serial number on each chip.
>
> I don't quite understand how a unique serial number in the chip is
> supposed to be helpful for anything cryptographic.
>
> ...and if the chip dies?
>
> ...and if you switch between computers?
>
> __
> Brad Aisa
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Thu, 21 Jan 1999 05:12:23 GMT
> Hmm... now we *are* getting metaphysical.
No, I'm just separating formalisms from reality. Formalisms can describe
our perception of reality, but they're not reality.
> I consider Quantity to be a fundamental attribute of the real physical
> world, not just a convenience of analysis.
Hmmm. OK. One gallon of liquid plus one gallon of liquid is two gallons
of liquid, right? It has to be, because 1+1=2. Bzzzt. You probably
even know for what liquids this isn't true. (Isopropanol and water, if
I remember right, because of the way the molecules fit together?)
> And if you buy into the
> Physics Of Information, then Quantity is a most fundamental attribute
> which causes the quantum world to exist, and the classical world to be
> what it is. Without Quantity as a fundamental, there could be no
> physical world that we are part of.
Perhaps 1 electron + 1 electron is always 2 electrons, but I suspect
that isn't true at the quantum level either? Clearly it's untrue for any
of the particles that decay.
As for
> Without Quantity as a fundamental, there could be no
> physical world that we are part of.
I would argue that perhaps there would be no "we" to be a part of a
physical world, even if such a physical world existed. That is, without
quantity, there would be no "we" to observe that there was no quantity,
even if the physical world was still there. *Now* lets get down to some
heavy metaphysics. ;-)
1+1=2 because we define it to be that way. But the real world doesn't
pay any attention to our definitions. When our theories are wrong, the
world doesn't change to accomodate us, regardless of what the
politicians might like to believe.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: [EMAIL PROTECTED] ()
Crossposted-To: sci.math.num-analysis
Subject: Re: Random numbers for C: The END?
Date: 21 Jan 99 05:09:33 GMT
George Marsaglia ([EMAIL PROTECTED]) wrote:
: My offer of RNG's for C was an invitation to dance;
: I did not expect the Tarantella.
I saw your original post; I wasn't aware that there was quite a thread
after it. If I wanted to nitpick about language issues, I'd note that as a
FORTRAN programmer, I am liable to use variables with names like "x" and
"y", and thus I would probably modify your preprocessor functions
accordingly.
I am honored to see a post by one of the co-inventors of the famed
MacLaren-Marsaglia random number generator. Although, due partly to a
Cryptologia article, that generator has generally been dismissed as a
component of a cryptosecure stream cipher, I've tended to feel:
1) the article was flawed, since one would never, in practice, use more
than a few of the most significant bits of generated random numbers for
stream cipher purposes, and
2) more elaborate variations on the principle, using the basic
MacLaren-Marsaglia generator as a building block, are possible.
On the other hand, it may be just as well that there is a dichotomy in the
methods used for stream ciphers and those used for random number
generation in the numerical solution of scientific problems, as this has
no doubt contributed to the fact that random number generators are not
affected by export control problems.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Pentium III...
Date: 21 Jan 99 04:59:39 GMT
fungus ([EMAIL PROTECTED]) wrote:
: Intel has announced that the Pentium III will have a built in hardware
: random number generator, and individual serial number on each chip.
: http://www.techweb.com/wire/story/TWB19990120S0017
Hmm. The serial number on the chip is to assist in copy-protection
schemes, creating a market for cryptographic techniques...
and a hardware random number generator on the chip will be useful to
cryptography programs.
So useful, I'm surprised they included such a feature (yes, I know dice
aren't export controlled) since they probably have enough headaches
getting approval to export their latest and greatest microprocessors.
John Savard
------------------------------
** 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
******************************
