Cryptography-Digest Digest #365, Volume #11 Sun, 19 Mar 00 15:13:01 EST
Contents:
Re: Card shuffling (Mok-Kong Shen)
Re: Card shuffling (Mok-Kong Shen)
Re: Card shuffling (Mok-Kong Shen)
Re: Card shuffling (Mok-Kong Shen)
Re: Crypto books ([EMAIL PROTECTED])
Re: On jamming interception networks (David A. Wagner)
Re: Special One way function ([EMAIL PROTECTED])
Re: NIST, AES at RSA conference (Tim Tyler)
Re: Looking for a special one way function ([EMAIL PROTECTED])
Re: Looking for a special one way function ([EMAIL PROTECTED])
ASCII to binary with 5% savings (wtshaw)
New Cryptanalysis of MARS and Serpent (Bruce Schneier)
New Performance Comparison of the AES Finalists (Bruce Schneier)
Re: On jamming interception networks (jungle)
Re: Attacks on AES candidates (Bruce Schneier)
Re: new Echelon article (John Savard)
Re: new Echelon article (John Savard)
Re: new Echelon article (John Savard)
Re: SHA-1 as a stream cipher (Ichinin)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Sun, 19 Mar 2000 18:39:37 +0100
Amical wrote:
>
> Have you considered a Kendall test between the initial permutation
> and the permutation after suffling ?
I suppose one should preferably first clarify some fundamental
aspects as those discussed in my most recent replies to Tim Tyler
and Jim Reeds before considering application of any specific tests.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Sun, 19 Mar 2000 18:39:26 +0100
Jim Reeds wrote:
>
> <[EMAIL PROTECTED]> writes:
> |> ... However, if one person on a specific session of the game
> |> shuffles a deck, could we say how well (effective) that deck
> |> has been shuffled?
>
> You might as well ask how to tell if one particular page
> of a one-time-pad is effective. Or even, how effective
> the first line of digits on the page are. Or even, how
> random the first digit is? You are asking, in effect,
> if one can tell if the digit '6' is as random as the digit
> '7'. (Some people would say 'no'.) In the binary case, you
> are asking, can one tell if the bit '0' (when used as
> an XOR key) is as effective as the bit '1'? Sci.crypt is
> the right forum to answer this question, as it comes up about
> twice a week here.
>
> I think the sensible question is: does the method of production
> of these objects (bits, digits, one time pads, permutations)
> come close to producing uniformly distributed items?
> And to make 'come close' precise, one should consider how
> much of a sample size would be needed to distinguish between
> the actual distribution and the desired uniform distribution.
You are apparently considering certain 'statistics' of the game
concerned. For a statistician that's a respectable research. However,
I am interested in a certain specific mondane problem which I believe
does have a non-trivial real-world meaning. In card games, the
shuffling is normally done by the players themselves. Suppose we
vary the convention some bit and assign an independent person to
do the shuffling and have another independent person to examine
the result of shuffling before giving the deck to the players to
start the game. (Incidentally there is a project to generate some
standard software to do shuffling for card games. As said, I like
to consider the case where humans do shuffling.) Now how can this
last person evaluate the task that has been done by the shuffler?
Note that he has only one single instance of the permutation to
judge and that, even if he had some past performance data of the
shuffler such as the frequency distribution curve you mentioned,
the shuffler could have cheated in that particular instance of
shuffling work or else simply could have had a bad day physically
or psychologically so that his past performance no longer counts.
As is also argued in a parallel follow-up (answer to Tim Tyler),
in the ideal case of employing a truly random device to shuffle,
each possible permutation has equal chance of occuring. So even
the identity permutation couldn't be rejected as being the result
of poor quality shuffling. I should very much appreciate further
discussions on the issue. Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Sun, 19 Mar 2000 18:39:16 +0100
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : My reading of Knuth's book is certainly not deep. But I am fairly
> : sure that he doesn't give a (practical) 'measure' of 'randomness'.
> : There are a number of tests described. But there is no single
> : numerical value that can be computed and taken as the (standard)
> : measure of 'randomness' comparable to the measures obtained
> : in physics.
>
> You /could/ define a quantity representing the shortest program in a
> specified language that produced the sequence - and call the ration
> of the length of this program to the length of the sequence a measure
> of the randomness, with respect to that language.
>
> The problem with such a metric is that it's *totally* impractical to
> compute - due to a combination of vast resources required and the halting
> problem.
>
> Knuth's tests *are* practical - in that you can actually perform them.
>
> If you want a single figure that detects every type of deviation from
> randomness, you *still* have to work with respect to some descriptive
> language - since what is random from one POV may be ordered from another
> one - and calculation of your metric /very/ rapidly becomes intractable.
So, if I understand you correctly, you do agree that obtaining a single
figure to measure 'randomness' is impractical.
>
> : If I use a very poor PRNG to obtain a permutation according to the
> : method of Durstenfeld, is that permutation 'random' or not? [...]
>
> Not.
Fine. Now consider the situation: A human X is asked to shuffle
a deck starting from some canonical order and give the result to
Y to examine whether the shuffling quality is o.k. Suppose it
is found that the shuffled deck is also in canonical order. Is
that shuffling o.k. or not? Most people would say no. Note however
that, if we had a truly random device to generate random permutations,
the probability of obtaining the identity is non-zero, though very
small. So is the rejection of the deck justified? I conjecture
that you would continue to argue for no. How about a deck such that
only the top two cards get swapped, or a deck where only the top
three cards get permuted, etc. etc.? Since a truly random device
will generate each possible permutation with the same probability,
the identity permutation is just like any other permutation in
having the (exactly) same chance of occuring. So we shouldn't
after all actually reject the identity deck from this consideration.
What is logically flawed in the above? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Sun, 19 Mar 2000 18:42:26 +0100
DMc wrote:
>
> Seriously, I think you might see card deck randomness as one true
> path only. I suggest it is the overwhelming multitude of possible
> paths. What you might fruitfully do is figure out ways to riffle
> and cut a card deck which produce non-random results.
I should appreciate your comments on my follow-up answering the
one posted by Jim Reeds.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Crypto books
Date: Sun, 19 Mar 2000 09:43:35 -0800
I would highly recommend "Cryptography and Network Security" by William
Stallings. Covers classic enryption and current encryption in a text book
format. It uses exercises that are great for learning. It also uses "simple
DES" to teach. It's great.
K
version_x wrote:
> i'm trying to get started in cryptography and have am looking for books
> which would suit a beginner,
>
> i have already bought Applied Cryptography by bruce s. but have found it
> pretty hard going, understading wise.
>
> is anyone aware of any books which are more beginner oriented or should i
> try and stick with applied cryptography.
>
> rees.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: On jamming interception networks
Date: 19 Mar 2000 09:10:14 -0800
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> jungle wrote:
> > > ... Hayden's speech to the Kennedy Political Union.
> > how to get grip of this speech ? on internet, please ...
> It should be on the NSA Web site.
http://www.nsa.gov/releases/dir021700.html
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Special One way function
Date: Sun, 19 Mar 2000 17:43:43 GMT
In article <[EMAIL PROTECTED]>,
James Felling <[EMAIL PROTECTED]> wrote:
>
> let f(Ai) = Ai ^ e mod M where e is an intreger >= 2, and M is the
product of
> two large primes. This is 1-way if M has not been factored and , and
An=
> A1^(e*n) mod M.
>
Thanks. But I am not quite sure about your result.
An=A1^(e*n) or An=A1^(e^n) ?
Which one is correct?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Reply-To: [EMAIL PROTECTED]
Date: Sun, 19 Mar 2000 17:46:23 GMT
D. J. Bernstein <[EMAIL PROTECTED]> wrote:
: Terry Ritter <[EMAIL PROTECTED]> wrote:
:> If you get to decide that a cipher is no good unless it has
:> mathematically proven security, you should apply that criteria to the
:> other side as well, in which case there is no good cipher.
: On the contrary. The Mauborgne cipher provably protects against
: eavesdropping, given one key bit per message bit. Wegman-Carter MACs
: provably protect against forgery, given just 128 key bits per message.
: Why, then, does anyone bother with secret-key systems that aren't
: provably secure? Because key bits are expensive---so expensive that we
: are willing to abandon provable security for the sake of a shorter key.
: Apparently that isn't a concern for you. You've made clear that you
: don't care about cost. So you can have mathematically proven security.
I don't remember him saying cost in terms of keyspace was irrelevant.
Also, if you're not aware what Ritter thinks of such "proven" security,
perhaps you should visit "Ritter's Comments on The One Time Pad" at:
http://www.io.com/~ritter/NEWS2/OTPCMTS.HTM
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
That's just peanuts to space.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Looking for a special one way function
Date: Sun, 19 Mar 2000 17:49:43 GMT
Thanks. But I am still not so clear about your idea:
1. What are i0,i1... . ? Are they just any sequence of number?
2. How do you define f2, f3, ....
Thanks,
In article <8aquhh$ft9$[EMAIL PROTECTED]>,
"Reuben Sumner" <[EMAIL PROTECTED]> wrote:
> Sorta.
>
> Suppose for fixed k bit n you want to generate x_0 .. x_{n-1}.
> Let f0 and f1 be two one way functions. Let i = i0,i1,i2,...,i{n-1}.
> Then let x_i=f_i{n-1}(f_i{n-2}(...(f_i0(x))))
>
> I don't recall where this is described.
>
> Reuben
>
> [EMAIL PROTECTED] wrote in message
<8aocs6$ql1$[EMAIL PROTECTED]>...
> >I am looking for a special one way function that has the following
> >properties:
> >Assume f is the one way function, the computation cost of f is C.
> >Xi+1 = f(Xi)
> >Generally, compute Xn from X1 needs computation cost (n-1)C, which is
in
> >the order of O(n). Here is my question: Is there any one way function
> >that can computer Xn from X1 at a cost of O(1) or O(lgn)?
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Looking for a special one way function
Date: Sun, 19 Mar 2000 18:12:16 GMT
I don't think I need the trapdoor. Could you give more detail about
"squaring mod n"? Sorry I am a newbie in crypto.
In article <8b2nbo$qc1$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> In article <8aocs6$ql1$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]>
wrote:
> > Assume f is the one way function, the computation cost of f is C.
> > Xi+1 = f(Xi)
> > Generally, compute Xn from X1 needs computation cost (n-1)C, which
is in
> > the order of O(n). Here is my question: Is there any one way
function
> > that can computer Xn from X1 at a cost of O(1) or O(lgn)?
>
> Maybe, but if so, it's not collision-free.
> See http://www.cs.berkeley.edu/~daw/my-posts/iterable-hash
>
> If you'll accept a one-way function with a trapdoor, so that
> anyone who knows the trapdoor can compute f^n() quickly (but
> can also invert f()), yet without the trapdoor you can only
> compute f() efficiently, consider squaring mod n, where n is
> a RSA modulus.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: ASCII to binary with 5% savings
Date: Sun, 19 Mar 2000 11:15:50 -0600
Aside from the special allowances I made for my particular purposes in one
implementation of the Rosebud Cipher, if you must, even with a plaintext
from the lower ascii set, the numbers don't lie:
1) Consider a minimum block of three ascii text characters, for a total of
21 bits. (Remember that base 97 allows some wiggle room as to what
formatting can be used.)
2) With the raw output of the block in base 31, 4 characters in base 32 is
20 bits. (You also have wiggle room here with an unassigned 32th
character.)
3) Expressing 21 bits as 20 is about 5% savings, which can be used in an
ascii data stream, storage, or, with optional cryptographic keys, a layer
of compatible encryption to interface common binary methods.
The mathematical relationship in this example of single stage base
translation is:
((Pt base)^(char/group))<((Ct base)^(char/group)
(97^3)<(31^4)
(88,529,281)<(90,224,199) at about 98.8% efficiency
Save space? More stuff down the pipeline at the same baud rate? Sure.
Now, just do it!
--
To see the results of GW Bush's shaddow, visit the Valley;
notice the miserable conditions he allows to fester.
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: New Cryptanalysis of MARS and Serpent
Date: Sun, 19 Mar 2000 14:43:36 GMT
These two papers will be presented at AES in New York in April:
http://www.counterpane.com/serpent-aes.html
http://www.counterpane.com/mars-attacks.html
Bruce
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: New Performance Comparison of the AES Finalists
Date: Sun, 19 Mar 2000 14:44:17 GMT
This paper will also be presented at AES3.
http://www.counterpane.com/aes-comparison.html
Bruce
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: On jamming interception networks
Date: Sun, 19 Mar 2000 18:51:00 GMT
thanks ...
"David A. Wagner" wrote:
>
> In article <[EMAIL PROTECTED]>,
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > jungle wrote:
> > > > ... Hayden's speech to the Kennedy Political Union.
> > > how to get grip of this speech ? on internet, please ...
> > It should be on the NSA Web site.
>
> http://www.nsa.gov/releases/dir021700.html
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Attacks on AES candidates
Date: Sun, 19 Mar 2000 14:48:53 GMT
On Fri, 17 Mar 2000 15:41:25 -0800, lordcow77
<[EMAIL PROTECTED]> wrote:
>Evidently, Schneier and the other cryptographers working with
>him have discovered new attacks on the AES candidates. In "A
>Performance Comparison of the AES Candidates," Schneier
>discusses two new attacks on MARS reduced to 11 rounds in the
>cryptographic core and another comprised of the round components
>symmetrically reduced to 3 rounds each. Rijndael and Serpent
>have distinguishing attacks against 8 and 9 rounds respectively.
>I wonder if there are other currently unpublished attacks on the
>AES candidates.
I've posted the Serpent results, and some of the Mars results. I will
post the rest of the Mars results and the Rijndael results just as
soon as we finish polishing up the two papers.
Bruce
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: alt.politics.org.cia,alt.politics.org.nsa,talk.politics.crypto
Subject: Re: new Echelon article
Date: Sun, 19 Mar 2000 19:01:22 GMT
On Sat, 18 Mar 2000 09:33:08 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote, in part:
>Jos Horikx wrote:
>> Another interesting echelon-article on:
>> http://cryptome.org/echelon-cia2.htm
>Thanks; that was a refreshing change from Duncan-Campbellism.
I always thought, though, that since in many Third World countries,
there is a great amount of corruption in the government, it is corrupt
officials there that initiate bribery, by essentially forcing people
to pay bribes if they want to sell anything to the government.
Thus, given that world situation, which the developed world is not
going to change by charging into any country where such corruption is
allowed to exist, invading it and replacing its government, that many
countries recognize their exporters must contend with the world as it
is, I don't find it surprising that they would indeed recognize paying
bribes as a legitimate, tax-deductible business expense.
(This, however, does assume that the article presents an unfair
picture, and the corruption is being initiated on the side of the
Third World country, not the European exporter. But that is a
reasonable assumption, given that a country that does not want its
officials to be corrupt can deter foreigners from attempting to bribe
them with severe penalties.)
Now, for the developed world to instead form a common front against
bribery in developing nations, and to practise solidarity in not
allowing their businesses to pay bribes, that might be a good idea.
However, as the signs about using seat belts tell us, there is a
difference between "a good idea" and "the law". Unless there is a
claim that somewhere in the clauses of the WTO treaty, to which these
European nations are signatories, bans paying bribes to third
countries as a form of unfair export competition, once again the
criticism appears to be valid that the United States is attempting to
make decisions for other nations that concern matters within their own
competency as sovereign states.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To:
alt.politics.org.cia,alt.politics.org.nsa,talk.politics.crypto,alt.journalism.print,alt.journalism.newspapers
Subject: Re: new Echelon article
Date: Sun, 19 Mar 2000 19:09:17 GMT
On 19 Mar 2000 06:31:13 -0800, [EMAIL PROTECTED]
(David A. Wagner) wrote, in part:
>It's a shame, given this mission, that the NSA has been such
>a force for _in_security in, e.g., the design of the US cellular
>telephony infrastructure.
And, of course, cell phones are one of the very few areas in which one
might be able to support the idea that something like the Clipper chip
had a legitimate role. One has, at least, the precedent of laws that
forbid all forms of encryption over the radio without special
licensing, and the fact that a cell phone is itself a piece of
(somewhat) expensive hardware, not, say, an existing net-connected PC
that can encrypt quite well, thank you, without buying a special chip
to do the job.
And the Clipper chip, for its flaws, would be considerably more secure
than what we have now, even in digital cell phones.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To:
alt.politics.org.cia,alt.politics.org.nsa,talk.politics.crypto,alt.journalism.print,alt.journalism.newspapers
Subject: Re: new Echelon article
Date: Sun, 19 Mar 2000 19:05:35 GMT
On Sat, 18 Mar 2000 15:54:27 -0600, "Andy Culp" <[EMAIL PROTECTED]>
wrote, in part:
>I think that makes perfect sense, why would the government have them if they
>weren't worth their money? The NSA obviously has to do something useful or
>all of the billions of dollars in funding would be put somewhere else.
They have to do something useful, but it also has to be honest work.
Spying on terrorists, tyrants, and aggressors, however ignoble it may
seem to be snooping at all, is honest and necessary work.
Spying on honest businessmen in our allied democratic neighbors for
the purpose of stealing from them is neither honest nor advisable, and
hence I tend to believe the NSA's denials, because I think they and
the U.S. government would be crazy to get involved in this sort of
thing.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: SHA-1 as a stream cipher
Date: Fri, 17 Mar 2000 04:25:44 +0100
Personally i've been playing around with SHA-1 as a tool for self
modifying S-Boxes:
Password + Key -> SHA-1 = in values.
- In values sets 8 x 16bit (4x4) S-Boxes
- In values sets 8 x 8 bit counters.
Main(){
For x ... until EOF{
foo = counters + previous hashed value (160+64 bits)
Modify S-Boxes with foo's values
Rotate SHA-1 hash 64* x bits
}
}
(* guessing 64)
even if someone know the previous SHA-1 value, the states of the 64*
bits
counter values have to be guessed too.
(* change to your desired size)
Regards,
Glenn
______________
Crypto Novice
------------------------------
** 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
******************************
