Cryptography-Digest Digest #810, Volume #13 Mon, 5 Mar 01 18:13:00 EST
Contents:
Re: Monty Hall problem (was Re: philosophical question?) (Fred Galvin)
Re: Again on key expansion. (Benjamin Goldberg)
Re: The Foolish Dozen or so in This News Group (Stephen Mercer)
Re: passphrase question (Tom McCune)
Re: passphrase question (Sundial Services)
Re: passphrase question ("Paul Pires")
Re: => FBI easily cracks encryption ...? (Fogbottom)
Re: Q: Crypto security of pseudo-random sequences (Benjamin Goldberg)
Re: Monty Hall problem (was Re: philosophical question?) (Joe H. Acker)
Re: Monty Hall problem (was Re: philosophical question?) (Ken Cox)
Re: Monty Hall problem (was Re: philosophical question?) (Ken Cox)
Re: Monty Hall problem (was Re: philosophical question?) (Ken Cox)
Re: passphrase question (Tom McCune)
Re: Q: Crypto security of pseudo-random sequences (Benjamin Goldberg)
----------------------------------------------------------------------------
From: Fred Galvin <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: Monty Hall problem (was Re: philosophical question?)
Date: Mon, 5 Mar 2001 16:18:26 -0600
On Mon, 5 Mar 2001, Mxsmanic wrote:
> "Fred Galvin" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
>
> > Suppose Monty's strategy is that, whichever door
> > I pick, he will open the highest numbered remaining
> > door that conceals a goat. In that case, if I pick
> > door #1 and Monty shows me a goat behind door #2, I
> > can be 100% sure that the car is behind door #3;
> > however, if I pick door #1 and Monty shows me a
> > goat behind door #3, then I have only a 50% chance
> > of getting a car, regardless of whether I stick with
> > door #1 or switch to door #2.
>
> That's not Monty's strategy, though, by definition.
Probably not (only Monty would know), who said it was? I was replying
to your assertion (which you snipped):
On Mon, 5 Mar 2001, Mxsmanic wrote:
> Correct. That's why the truth table that I provided does not take
> Monty's choice into account. The only thing that matters is that he
> always eliminates a door that conceals a goat.
Specifically, I was pointing out error in stating "The only thing that
matters is that he always eliminates a door that conceals a goat." It
does matter that, if I pick the car door, Monty chooses randomly
between the two goat doors.
As for your truth table, note that a line of your table does not
completely specify an outcome: there should be another column
indicating which door Monty opened.
In order to draw your conclusions about probabilities, you must be
assuming that the lines of your table are equally likely outcomes. In
particular, then, you are assuming that the player is equally likely
to pick any of the three doors. There is no justification for such an
assumption; it's not part of the problem, and was probably false in
the actual tv game.
--
People who don't have a sense of humor shouldn't try to be funny.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Again on key expansion.
Date: Mon, 05 Mar 2001 22:31:39 GMT
Cristiano wrote:
>
> > [...]
> > Thus, if you're using the same implementation on the same hardware,
> > it can't take 1.26 seconds in one instance and 76 microseconds in
> > another.
>
> You are right! I had misunderstood.
>
> > [...]
> > Two methods that both take a second offer the same strength.
>
> This point is not clear (for me). I'd like better understand what you
> tell me:
> to add 13 bits of entropy to my key my method takes 0.079 s, SALEK's
> method takes 1.26 s (on *my* computer with *my* program).
> Why the two methods offer the same strength?
> In the same time my method add more entropy to the key.
> I don't want to blame SALEK's method, I want only understand and
> learn!
The disparity is due to your miscounting the number of rounds.
To multiply a point by a 512 bit integer is 512 doublings, and 256 adds.
To perform sha512 once, is 64 internal rounds.
(Note, I forgot the adds in my earlier estimate).
Your method, looping 16 times adds log2(16*(512+256+64)) bits of work.
SALEK's method, looping 2^13 times adds log2(2^13*64) bits of work.
So your method takes .079s to add 13.7 bits of work.
SALEK's method takes 1.26s to add 19 bits of work.
The expected work difference is 5.3 bits, or a time factor of 39.
The actual time difference is a factor of 16, or 4 bits of work.
Thus, by attempting to measure rounds more accuratly, we end up with a
more accurate measurement of how much the two methods should differ.
I'm still off by 1.3 bits, but that is because it takes about 2.4 times
longer to double a point or add two points than it takes to perform one
of sha512's internal rounds. Now considering that adding two points (or
doubling one point) is actually a number of operations, we could
recalculate the number of rounds to be even more accurate. Also, adds
and doublings don't take the same amount of time, I don't think.
Anyway, if you measure rounds ACCURATLY, and if you use the same number
of rounds in both methods (not number of times your loop goes, but the
number of rounds, as I've been measuring), then both methods should take
the about same amount of time.
To get 13 bits of entropy, using sha512 and SALEK's method, something
like the following:
for i in 1 to 2^7
x = sha512(x)
And I think you will discover that it takes about the same amount of
time as your method done as:
for i in 1 to 2^4
p = sha512( p.x, p.y ) * (Base point)
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
From: [EMAIL PROTECTED] (Stephen Mercer)
Crossposted-To: alt.hacker
Subject: Re: The Foolish Dozen or so in This News Group
Date: 5 Mar 2001 22:32:57 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>,
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
>The Foolish Dozen or so in This News Group
>
>Read below. It'll be just like being forced to look into a mirror.
>You'll see who you all really are. Read it an weep.
Ya know, when a dozen people are bothered enough by my statements to
actually go out of there way and persistently correct me, I tend to want
to stop and ask myself, "Self, am I _really sure_ I know what I'm talkin'
about here?". But that's just me.
Mr. Szopa, the basis for your algorithm is wrong. The C lib/OS/disk caching
descriptions you have been repeatedly given are correct, and explain why
you cannot reliably expect that the physical writes to disk are done when
you check the return code of either fclose() or close(). All evidence here
indicates that you are quite willing to ignore me (as well as repost your
diatribes), but I'm pretty sure my ego could take that. This just lends
more evidence to the record that you were, indeed, told the difference.
--
Stephen Mercer <[EMAIL PROTECTED]>, Optical Design (613) 765-3214
------------------------------
Crossposted-To: alt.security.pgp
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: passphrase question
Date: Mon, 05 Mar 2001 22:34:21 GMT
In article <kUTo6.39010$[EMAIL PROTECTED]>, "Paul Pires"
<[EMAIL PROTECTED]> wrote:
>> I can't buy that. There is no way for my opponent to know whether or not I
>> repeat characters, or have numbers, or have letters, etc., in my passphrase.
>
>Ehr... I think you just told everybody.
I didn't say anything about how I do or do not construct passphrases.
>This is the problem with password selection schemes and passwords
>in general. If it is any good, a hacker will just add it to their dictionary
>search routine reducing the needed "find" to the unique aspects.
>If you tell, you can't use. I have a much easier and much better way.
And I think that is what the original poster was asking, that is whether
such an approach is routinely considered in passphrase attacks.
I do agree with you that it is best not to let others know how you go about
it - I won't discuss my approach either.
Tom McCune
My PGP Page & FAQ: http://www.McCune.cc
------------------------------
Date: Mon, 05 Mar 2001 15:41:04 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: passphrase question
An intruder will -always- seek out and attack the weakest link, and this
is almost certainly "the user himself."
Even the most famous attack on a cryptosystem, the Enigma break, was
centered around the human nature of the users of the system, and the
habits of the organization using it, both of which lead to an
opportunity for a plaintext attack. All of that sophisticated
technology, at least for Enigma, was simply an automated brute-force(?)
attack on that weak link.
Had the users merely pressed a few garbage characters on the keyboard
before starting the real text ... how different the outcome might have
been.
>JPeschel wrote:
>
> "Mxsmanic" [EMAIL PROTECTED] writes:
>
> >The passphrase is no more secure than a six-character password, and is
> >thus vastly less secure than a well-chosen passphrase. The fact that
> >you repeat each of the characters has no effect, since your opponent
> >knows this.
>
> A passphrase chosen using "Nobody's" formulation isn't secure,
> but it will survive an opponent's attack for a longer time than would
> a six-character password.
>
> Joe
> __________________________________________
>
> Joe Peschel
> D.O.E. SysWorks
> http://members.aol.com/jpeschel/index.htm
> __________________________________________
--
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: passphrase question
Date: Mon, 5 Mar 2001 14:45:01 -0800
Tom McCune <[EMAIL PROTECTED]> wrote in message
news:NvUo6.188143$[EMAIL PROTECTED]...
> In article <kUTo6.39010$[EMAIL PROTECTED]>, "Paul Pires"
><[EMAIL PROTECTED]> wrote:
>
> >> I can't buy that. There is no way for my opponent to know whether or not I
> >> repeat characters, or have numbers, or have letters, etc., in my passphrase.
> >
> >Ehr... I think you just told everybody.
>
> I didn't say anything about how I do or do not construct passphrases.
That was careless of me. I responded to you as if you started the thread.
Sorry.
>
> >This is the problem with password selection schemes and passwords
> >in general. If it is any good, a hacker will just add it to their dictionary
> >search routine reducing the needed "find" to the unique aspects.
> >If you tell, you can't use. I have a much easier and much better way.
>
> And I think that is what the original poster was asking, that is whether
> such an approach is routinely considered in passphrase attacks.
Maybe routinely considered, Maybe not. It seems to miss the point. If you
want better security, use more "Surprise" don't try to hide a lack of
it.
>
> I do agree with you that it is best not to let others know how you go about
> it - I won't discuss my approach either.
I kinda liked Simon Johnson's suggestion. General without being deterministic.
Paul
>
> Tom McCune
> My PGP Page & FAQ: http://www.McCune.cc
------------------------------
Date: 5 Mar 2001 22:46:40 -0000
From: [EMAIL PROTECTED] (Fogbottom)
Subject: Re: => FBI easily cracks encryption ...?
Crossposted-To: alt.security.pgp,talk.politics.crypto
In article <[EMAIL PROTECTED]>
[EMAIL PROTECTED] (Free-man) wrote:
> >> There is a better way to prevent terrorism. There is an
> >alternative
> >> to the police-state.
> >
> >History indicates otherwise.
> >You'll have to wait for the "Second Coming" or whatever your
> >particular creation myth promises.
> Remember alcohol prohibition when the US government decided
> to treat millions of honest, decent people as criminals in
order to
> "protect the children" What was the
> result of all thatt government violence? That violent and
criminal
> intervention into the free market produced an equally violent
black
> market. Sending police goons to attack people produced more
violence.
> Look at drug prohibition today. Millions of good people have
been
> assaulted, robbed, and arrested. This state-sponsored
terrorism has
> produced armies of thugs, spies, and informers, a violent
underground
> market, many prisons, and the widespread abuse of humans.
I agree with you. Most Americans apparently don't.
> All this violence is produced by governments with too much
power. The
> solution is not to give more power to government. The
solution is
> more freedom for individuals which means less power for
government.
Ain't a-gonna happen, though, is it?
Far too many people think just like "kroesjnov"
<[EMAIL PROTECTED]>
And so long as they do, the powers that be can make themsleves
look good by stomping on the "Freemen" of Montana and the
Timothy McVeighs.
But comments like "In my country (US), there are more government
goons kicking
down doors and invading homes than there were in Nazi Germany."
simply marginalize you.
Nazi Germany had *lots* of goons.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Q: Crypto security of pseudo-random sequences
Date: Mon, 05 Mar 2001 22:53:23 GMT
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
From: [EMAIL PROTECTED] (Joe H. Acker)
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: Monty Hall problem (was Re: philosophical question?)
Date: Mon, 5 Mar 2001 23:53:48 +0100
Ken Cox <[EMAIL PROTECTED]> wrote:
> "Joe H. Acker" wrote:
> > If Monty knows where the car is, and never opens the door with the car
> > behind (as has been assumed), then the probability to win has to be 1/2.
> > From the beginning, my chances to win were 1/2, because Monty always
> > opens a door that doesn't contain the car.
>
> Are you saying above that from the beginning, when you
> initially chose among three doors, your chance of picking
> the right door was always 1/2?
Yes, that's what I think. A reason I've given in another followup is
that Monty follows a deterministic algorithm when he *always* picks the
door with a goat after you have chosen a door. The truthtable Mxsmanic
gave is the correct truthtable for three doors, but the correct
truthtable to solve this problem is the rather trivial truthtable for
only 2 doors---the door you've initially chosen and the door left over
after Monty has picked out the goat door.
Consider the 2 subsequent choices:
1st Choice: Regardless which door you chose, you cannot chose the door
Monty will pick out as the goat door, because he never picks out *your*
door as the goat door and has not yet picked out the goat door at all.
Or to put it in other terms, Monty will always pick out another door
than you initially choose.
2nd Choice: The doors left you can chose from are the door you've chosen
first, and the door left over. You are not allowed to chose the goat
door that already has been opened by Monty.
In none of the two choices you have even the slightest chance of picking
out the goat door Monty opens. Monty's deterministic algorithm prevents
from that. Therefore, your chances two win are 1/2 from the beginning,
provided that Monty actually follows his algorithm, as is being assumed
by the puzzle.
Interestingly, this can be tested empirically. All you need is a good
TRNG based on radioactive-decay and a function that takes input from the
TRNG to produce an unbiased random number in an integer range. Then you
write a program that randomly assigns the car to an element of an array
[1..3], makes a random choice c for one element of the array and
implement Monty's algorithm: take the two remaining elements, if one of
them is the car, mark the other as "opened", otherwise you're free to
randomly mark any of the remaining two elements as "opened". Then, make
two iterated test runs, one time always staying with the first element
c, another run always changing to the remaining element that is not the
first c and not marked as "opened".
If I'm wrong, the first iterated run should create a 33% and the second
run a 66% winning rate. If I'm right, both runs should return the same
result of 50%.
Any volunters? (I don't have a TRNG...)
Regards,
Erich
------------------------------
From: Ken Cox <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: Monty Hall problem (was Re: philosophical question?)
Date: Mon, 05 Mar 2001 16:53:58 -0600
Fred Galvin wrote:
> Hmm. Suppose Monty's strategy is that, whichever door I pick, he will
> open the highest numbered remaining door that conceals a goat.
Then you've changed the conditions for the puzzle, and the
answer will change correspondingly.
--
Ken Cox [EMAIL PROTECTED]
------------------------------
From: Ken Cox <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: Monty Hall problem (was Re: philosophical question?)
Date: Mon, 05 Mar 2001 16:55:47 -0600
Fred Galvin wrote:
> On Mon, 5 Mar 2001, Mxsmanic wrote:
> > That's not Monty's strategy, though, by definition.
>
> Probably not (only Monty would know), who said it was?
I think I see the confusion here. You are talking about
the show, where Monty's strategy was unknown (and might
even have varied with each contestant); most of the rest
of us are talking about the Monty Hall problem, in which
Monty's strategy is given.
--
Ken Cox [EMAIL PROTECTED]
------------------------------
From: Ken Cox <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: Monty Hall problem (was Re: philosophical question?)
Date: Mon, 05 Mar 2001 16:52:26 -0600
Fred Galvin wrote:
> On Mon, 5 Mar 2001, Ken Cox wrote:
> > Fred Galvin wrote:
> > > [...] I may as well assume that there's a goat
> > > behind door #3. Now, how does the decision I make, on the assumption
> > > that there's a goat behind door #3, differ from the decision I'd make
> > > if Monty opened door #3 and showed me a goat?
> > Your assumption may be wrong. There may not be a goat
> > behind door #3.
> Of *course* the assumption may be wrong. That's what I *said* in the
> part you snipped:
>
> : I don't know what's behind door #3, could be the car, could be a
> : goat.
> Let me repeat the question very slowly. The car may be behind door
> #3.
In the standard Monty Hall problem, the car is *never* behind
the door that Monty opens. That is one of the conditions that
is stated. Another condition that is stated is that the reason
that the car is never behind the door that Monty opens is that
Monty knows where the car is, and does not reveal it. A third
condition is that Monty always offers the switch, no matter
what door (and prize) the contestant has chosen. All three of
these conditions are important to working out the Monty puzzle,
and you get different answers if you vary any of them.
You need to be equally specific when describing your variation
of the Monty puzzle, in which Monty does not open a door but
just offers the contestant a choice of another door. If, for
example, Monty always offers the next door in line (modulo 3),
even if the car is behind it, then there are the following
cases (by symmetry, assume the contestant always picks 1 so
Monty always offers "switch to 2"):
Stay Switch
Car behind 1: win lose
Car behind 2: lose win
Car behind 3: lose lose
The contestant in this game thus has a 1/3 chance of winning
whether they stay with 1 or switch to 2. The contestant
definitely doesn't have a 50% chance of winning no matter
what they do, with this Monty strategy.
> If the car is behind door #3, it doesn't matter which door I pick,
> I get a goat either way. Therefore, in deciding between door #1 and
> door #2, it makes sense to disregard the possibility that I am
> choosing between two goats, and assume that I am choosing between a
> goat and a car.
What you are describing here is yet another problem. You are
not answering the question "What is the probability that the
contestant wins", but the question "What is the conditionaly
probability that the contestant wins given that the car is
behind door one or door two". The different question means
a different answer; your 50% is correct in this case. However,
50% is definitely *not* the answer to the question "What is
the probability that the contestant wins".
--
Ken Cox [EMAIL PROTECTED]
------------------------------
Crossposted-To: alt.security.pgp
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: passphrase question
Date: Mon, 05 Mar 2001 23:00:05 GMT
In article <ZGUo6.39600$[EMAIL PROTECTED]>, "Paul Pires"
<[EMAIL PROTECTED]> wrote:
>That was careless of me. I responded to you as if you started the thread.
>Sorry.
<snip>
No problem - I've been known (recently, too) to make the same kind of
mistake.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Q: Crypto security of pseudo-random sequences
Date: Mon, 05 Mar 2001 23:04:31 GMT
Mok-Kong Shen wrote:
>
> If one has a statistically good pseudo-random sequence, e.g.
> one from the Mersenne Twister, and post-process it through
> the following methods:
>
> (1) Encryption with AES.
This is secure. Take 128 bits chunks of MT output, and encrypt them
with AES, and you've got something secure. However, if you are doing
this, there's no reason not to simply use AES in counter mode. AES/CTR
is faster, and not measurably less secure.
> (2) Hashing with SHA-1.
This is also secure, but the same argument as with AES applies.
To produce a CSPRNG with sha, take a random key k, and do the following:
x(i) = SHA1( k || i || k )
And it will be just as secure as hashing MT output.
> (3) Using groups of n bits (e.g. n=24) to index the binary
> digits of Pi.
I don't know. Maybe it's secure, maybe not.
> (4) Further processing any of the above by taking the parity
> of groups of m bits.
Almost anything which cuts down on the output rate (lossily compresses)
may be able to make MT secure. However, security comes from analysis;
"may be" is not "is." Self-shrinking might be good, or it might not.
> which of these can qualify (or not qualify) as crypto-secure
> pseudo-random sequences? Why?
(1) and (2) are secure because AES and SHA are secure. MT alone is
insecure because if you have a decent amount of its output, you can
learn the state, and it's not difficult to run MT forwards and
backwards.
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
