Cryptography-Digest Digest #333, Volume #13 Fri, 15 Dec 00 01:13:00 EST
Contents:
Re: Protocol for computer go (David Schwartz)
Re: Crypto Program for HP48GX Calculator (Richard Hutchinson)
Re: Visual Basic Source Code ("Jason Bock")
Re: Protocol for computer go (David Eppstein)
Re: Visual Basic Source Code ("Jason Bock")
Re: Visual Basic Source Code ("Jason Bock")
Re: discrete math textbook (Dido Sevilla)
Re: Protocol for computer go (Paul Rubin)
Re: Protocol for computer go (David Wagner)
Re: Protocol for computer go (David Wagner)
Re: discrete math textbook (Paul Rubin)
Re: discrete math textbook ("John A. Malley")
Re: Protocol for computer go (David Eppstein)
Re: Homebrew Block Cipher: Moonshine (Simon Best)
Re: Protocol for computer go (Paul Rubin)
----------------------------------------------------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Protocol for computer go
Date: Thu, 14 Dec 2000 20:08:14 -0800
Benjamin Goldberg wrote:
> Those things effect how much real time memory operations take, but they
> don't effect *how many* operations the program takes, which is what the
> cycle counter should be counting.
Actually, the cycle counter (surprisingly enough) counts cycles. The
number of cycles it takes to perform an operation depends upon all kinds
of factors, including what happens to be in the cache.
> If, instead of counting cycles of
> program operation as you should be doing, you strangely decide to count
> cycles of program operation PLUS cycles taken by operating system stuff
> (putting stuff in cache from main memory, puttting stuff in main memory
> from disk), then of course you are going to have a non deterministic
> counter.
The operating system doesn't put stuff in the cache, the hardware does.
And it takes it cycles to do that.
DS
------------------------------
From: Richard Hutchinson <[EMAIL PROTECTED]>
Crossposted-To: comp.sys.hp48
Subject: Re: Crypto Program for HP48GX Calculator
Date: Fri, 15 Dec 2000 04:14:30 GMT
And who twisted your arm to answer. If you don't want to help someone
just ignore it. I don't believe it was personally addressed to you.
Like mom use to say if you don't have something nice to say then just
say nothing.
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Richard Hutchinson <[EMAIL PROTECTED]> wrote:
> > A real friendly fella.
>
> Do you know how many people post "I am doing a shareware program can
> someone do all the programming for me and submit it to my email".
>
> Seriously folks do yer'own work once in a while. Plus if you used this
> new fangled-thingy-jobler called a "SEARCH ENGINE" you may perchance
> find something.
>
> Eegad...
> Tom
>
> Sent via Deja.com
> http://www.deja.com/
--
Richard Hutchinson
[EMAIL PROTECTED]
------------------------------
From: "Jason Bock" <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Source Code
Date: Thu, 14 Dec 2000 22:50:33 -0600
Paul Schlyter <[EMAIL PROTECTED]> wrote in message
news:91bsmi$g7d$[EMAIL PROTECTED]...
> In article <3a39439f$0$17729$[EMAIL PROTECTED]>,
> Jason Bock <[EMAIL PROTECTED]> wrote:
>
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > news:91b151$404$[EMAIL PROTECTED]...
> >> In article <91b0mp$3gl$[EMAIL PROTECTED]>,
> >> [EMAIL PROTECTED] wrote:
> >>> Does anyone know where i can get GOOD source code for MD4, MD5, SHA1,
> >>> DES, IDEA, and CAST in VB??
> >>
> >> Why is everyone interested in VB? Arrg!
> >
> > Why not? Any good reasons why millions of VB programmers should give up
> > their tool of choice?
> >
> > Just curious.
>
> You're right! 50 billion flies can't be wrong -- eat shit!!! <g>
My statement wasn't advocating or criticizing VB. And just because millions
of people use <insert tool/language/OS here> doesn't mean it's the best for
all circumstances.
I'm not advocating VB - I'm interesting in why someone dismisses VB
outright. I personally wouldn't use it to create high-speed cipher
implementations; I personally don't find it useless, though.
Jason
------------------------------
From: David Eppstein <[EMAIL PROTECTED]>
Subject: Re: Protocol for computer go
Date: Thu, 14 Dec 2000 20:41:40 -0800
In article <91btir$c3h$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (David
Wagner) wrote:
> Yes, you're right. Probably what you want to count is number
> of instructions computed, not how many clock cycles they've taken
Ok, that avoids the nondeterminism problem, sort of -- you're specifying
additional information that describes the nondeterministic input to the
game search algorithm.
Now, how do you put that into a protocol that prevents the remote computer
operator from cheating?
Here's a strawman protocol:
after each move, the game program reports how many instructions it used (or
whatever other information is necessary). To verify that the program was
not cheating, you run it for that many instructions and test that it
produces the same answer.
Problem: the report of how many instructions were used provides a channel
for communicating from the game-time run of the program to the
verification-time run, allowing it to reproduce any cheating behavior from
game-time.
Not to mention that instructions computed is still not good enough to
handle the nondeterminism from shared-memory multiprocessors (these really
are used in several modern chess programs, don't know about go yet).
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
From: "Jason Bock" <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Source Code
Date: Thu, 14 Dec 2000 22:55:13 -0600
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:91blvi$m1s$[EMAIL PROTECTED]...
> VB is the programming language for the lame programmer. Now I am far
> from being a math/compsci wiz but at least I don't fear some real
> programming. VB also makes very inefficient applications. Hello world
> should not take more then 4kb for a win app...
OK. <Insert tool/language/OS here> is lame. What does that mean?
If you're going to argue efficiency, use assembly. Hell, that makes C lame.
People have done some amazing things in VB to break beyond its' boundaries
(i.e. they don't fear "real programming"). And for certain tasks it makes
the job very easy.
Jason
------------------------------
From: "Jason Bock" <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Source Code
Date: Thu, 14 Dec 2000 22:57:27 -0600
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:91bq5p$pec$[EMAIL PROTECTED]...
> In article <3a39439f$0$17729$[EMAIL PROTECTED]>,
> "Jason Bock" <[EMAIL PROTECTED]> wrote:
> > Why not? Any good reasons why millions of VB programmers should give
> up
> > their tool of choice?
> >
> > Just curious.
>
> Because most visual tools make unusually unrequired large programs out
> of nothing? They are inefficient? They are expensive... hmm list
> continues.
If you're going to argue that, I would then say use PowerBASIC. One of the
fastest if not the fastest compiler for Windows (which is what I primarily
use (Windows I mean) and all VB developers would use). It can make visual
or non-visual programs pretty easily, and it's easy for the VB developer to
pick up. Plus, its' executable size is very small, even if you add in
windows and controls. And although it's not free, it's not expensive
either - $100. And it comes on two floppies. For what you get out of the
tool that's pretty impressive.
I personally have used VB for many projects. For the requirements at hand,
it fit the bill. It doesn't fit the bill in all cases, but that to me is
not a reason to dismiss it outright.
Jason
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: discrete math textbook
Date: Fri, 15 Dec 2000 12:51:01 +0800
[EMAIL PROTECTED] wrote:
>
> Can anybody recommend a decent textbook on discrete math? I have
> college-level math background (mainly calculus) and want to self-study
> some discrete math. It will be good if CS-oriented, but not necessary.
>
I recommend Richard Johnsonbaugh's "Discrete Mathematics" (ISBN
971-656-054-0). It's CS-oriented, alright, but unfortunately it doesn't
discuss some important discrete structures important to cryptography
(particularly finite fields). My favorite book in abstract algebra
however is John B. Fraleigh's "A First Course in Abstract Algebra" (ISBN
0-201-59291-6), but it's more oriented to students of pure mathematics
than those of computer science.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Protocol for computer go
Date: 14 Dec 2000 21:02:37 -0800
David Eppstein <[EMAIL PROTECTED]> writes:
> Here's a strawman protocol:
> after each move, the game program reports how many instructions it used (or
> whatever other information is necessary). To verify that the program was
> not cheating, you run it for that many instructions and test that it
> produces the same answer.
How can the program tell how many instructions it's used? That's
intended as a practical question about real hardware that's used
for chess programs today, not an abstract question.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Protocol for computer go
Date: 15 Dec 2000 05:08:44 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Paul Rubin wrote:
>[EMAIL PROTECTED] (David Wagner) writes:
>> Yes, you're right. Probably what you want to count is number
>> of instructions computed, not how many clock cycles they've taken.
>
>I don't see how to do that on any current processor without orders of
>magnitude worth of performance loss.
Ok.
Let's see. How about the following alternative?
The underlying `operating system' (which must be trusted) exports
a query-clock-cycles operation which returns the number of clock cycles,
plus or minus a random number. This random number can be generated
in a secret yet verifiable way with techniques described in an earlier
post of mine, so others can still verify that the transcript proceeded
correctly -- yet the go-playing program cannot guess the exact number
of clock cycles due to the randomization. Thus, the non-determinism
inherent in the number of clock cycles it takes to execute the
algorithm cannot be exploited to alter the behavior of the program.
Can this sort of idea be made to work? I'm not too sure myself,
and would welcome comments on it.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Protocol for computer go
Date: 15 Dec 2000 05:13:04 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
David Eppstein wrote:
>Here's a strawman protocol:
>after each move, the game program reports how many instructions it used (or
>whatever other information is necessary). To verify that the program was
>not cheating, you run it for that many instructions and test that it
>produces the same answer.
>
>Problem: the report of how many instructions were used provides a channel
>for communicating from the game-time run of the program to the
>verification-time run, allowing it to reproduce any cheating behavior from
>game-time.
What do you mean by "reproduce any cheating behavior"? I thought the idea
was to ensure that the results played truly came from the program, and not
from some human. Thus, you don't want it to be the case that a kibitzing
human can give the algorithm "hints" about the best moves; this would
be cheating, because the algorithm would not be purely computer-driven.
This type of cheating is prevented by the protocol. But if it is not
this type of cheating you had in mind, what did you have in mind?
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: discrete math textbook
Date: 14 Dec 2000 21:13:37 -0800
[EMAIL PROTECTED] writes:
> Can anybody recommend a decent textbook on discrete math? I have
> college-level math background (mainly calculus) and want to self-study
> some discrete math. It will be good if CS-oriented, but not necessary.
Concrete Mathematics, by Knuth, Graham, and Patashnik. It's supposed
to give their recommend math background for CS, actually a mixture of
CONtinuous and disCRETE (hence "concrete") mathematics.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: discrete math textbook
Date: Thu, 14 Dec 2000 21:15:50 -0800
[EMAIL PROTECTED] wrote:
>
> Can anybody recommend a decent textbook on discrete math? I have
> college-level math background (mainly calculus) and want to self-study
> some discrete math. It will be good if CS-oriented, but not necessary.
There are already some good suggestions in this thread. May I add
another one?
"Discrete Mathematics" by Norman L. Biggs, Oxford Science Publications,
ISBN 0-19-853427-2. It's an introduction to discrete mathematics written
with CS undergraduates in mind.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: David Eppstein <[EMAIL PROTECTED]>
Subject: Re: Protocol for computer go
Date: Thu, 14 Dec 2000 21:20:05 -0800
In article <91c990$duh$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (David
Wagner) wrote:
> What do you mean by "reproduce any cheating behavior"? I thought the idea
> was to ensure that the results played truly came from the program, and not
> from some human. Thus, you don't want it to be the case that a kibitzing
> human can give the algorithm "hints" about the best moves; this would
> be cheating, because the algorithm would not be purely computer-driven.
> This type of cheating is prevented by the protocol.
How is it prevented? The program in cheating-game-play mode has a variable
that cycles through the possible moves, and when it sees a hint it waits
until the variable comes round to the right move then outputs the move
given by that variable. The program in replay mode will then reproduce the
same move when run for the same number of instructions.
> But if it is not
> this type of cheating you had in mind, what did you have in mind?
Another commonly used method of cheating is for a human operator to watch
the computer's display of what move it is currently planning to make, and
use the "move now" command when you like the move you see. This is largely
prevented by not having human operators (making everything automatic) but
if the computer is remote how can you tell?
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
From: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Homebrew Block Cipher: Moonshine
Date: Fri, 15 Dec 2000 05:26:25 +0000
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
[...]
> > * It's heavily inspired by Rijndael
> > (http://csrc.nist.gov/encryption/aes/rijndael).
>
> Why? Rijndael is very efficient but not among the most fuzzy-warm
> secure ciphers. It has known diffusion problems and is too highly
> structured.
The efficiency was certainly something that appealed to me. Also, the
way diffusion was done with that column mixing stuff struck me as an
interesting alternative to Feistel structures. (I hadn't known enough
about finite fields before reading through the Rijndael specification to
know of any alternative to Feistel networks.)
As for the regularity, I suspect that my cipher's far too regular at
present.
> > * It's heavily inspired by hypercubes.
> >
> > * It's slightly inspired by Rubic's cube.
>
> Right... well inspiration can come from anywhere I suppose :-)
And I'm hoping that the Rubic's cube bit (shuffling) might help reduce
regularity, a little bit.
> > * Variable block and key sizes (at least, at the moment).
>
> This is a good feature, however, it's best to either focus on a
> specific size for the momement or do cryptanalysis in general.
You're right. I may come back to looking at variable block and key
sizes some time in the future. It was something I wanted to design in
from the start, though, so as to leave that avenue easily open for
future exploration. I'll stick with a few nonnegative integer powers of
two for now.
> > * Potential for lots of implementation optimisations.
>
> Always a plus.
>
> > * Doesn't use a Feistel structure.
>
> Why not? Why do you feel that a Feistel is bad?
No, not at all! I just fancied something different.
[...]
> > If anyone's interested in this enough to want demonstrative source
> code
> > (in C), I'm happy to post it here.
>
> How about a formal description of it (i.e in PDF/PS format)?
Okay, I'll get to work on it, once I've finished making alterations to
the cipher. (At the very least, it'll give me some practice at formal
specification writing.)
> > Again, I'm an amateur, and this is a homebrew cipher.
>
> All good, I'm an amateur too :-)
I thought you were a professional here!?
> > BLOCK SHUFFLING
> >
> > Block shuffling is based on slice arrays.
[...]
>
> Are the "offset/stride" pairs key dependant? If so I smell WEAKKEYS...
No, it's not key dependent, I don't think I described it very well.
It does several slice array cyclings for each shuffle, but each shuffle
is identical. There's just one shuffle per round.
For example:
a0 a1 a2 a3 a4 a5 a6 a7
always ends up as:
a1 a4 a7 a6 a5 a0 a3 a2
in a single shuffle (done by cycling a few slice arrays).
I should probably replace this so called shuffling with something less
regular, and have a different shuffling in each round (but, of course,
with no key dependency).
> > BYTE SUBSTITUTION
> >
> > I'm stealing this straight from Rijndael. It's Rijndael's S-box,
> > applied to each and every byte in the block. The inverse of this is
> the
> > inverse of Rijndael's S-box (unsurprisingly).
>
> Well why not trying to invent your own sbox? You may learn something.
Laziness. Or, rather, more interested in other bits of the cipher, so I
was just lazy with this bit. I will come up with one of my own, though,
and (hopefully) learn from it (as you suggest).
> > DIFFUSION
> >
> > A diffusion step is done with two steps. Bytes are first reordered in
> > the block, and then pairs of bytes are mixed together. Rounds of
> these
> > two steps are intended to produce rapid diffusion of bytes throughout
> > the block. (This is the hypercube inspired bit, but the effective
> > structure is only hypercubic for certain block sizes.)
>
> Permutations are not forms of diffusion. They are catalysts for it
> however. A permutation is nothing more then a sparse linear system.
True. My description was ambiguous, specifically where I said "pairs of
bytes are mixed together". What I meant was that the block was then
treated as a set of pairs of bytes, where each pair is taken in turn,
and the two bytes in a pair are mixed with each other.
[...]
> > BYTE REORDERING
> >
> > Indexing the bytes in a block from 0 to Nb-1, all the bytes indexed
> with
> > an even number end up at the front (low indexes) of the block, and all
> > the bytes indexed with an odd number end up at the back of the block.
[...]
>
> Again this seems fairly regular. There could be unsettling patterns in
> the diffusion. You should analyze the movement of a difference for
> potential weaknesses.
It was that regularity that prompted me to add the shuffling step to
each round. I think I could do more, though...
> > BYTE PAIR MIXING
> >
[...]
>
> Of course this becomes a MDS matrix so at least diffusion is optimal
> here :-)
Hooray! (I really will have to properly learn what an MDS matrix is...)
> I really haven't looked at it deeply. But it seems neat from an
> offset. What were your goals? More secure? Faster?
>
> Tom
My goals were:
1. Jump in at the deep end.
2. Learn some (but certainly only some) stuff from doing it.
3. Block and key size scalability (as in order of magnitude).
4. Implementational flexibility (hardware, software...).
5. Optimisational opportunities (limited memory, speediness...).
6. Block and key size variability (as in linear).
7. Toothbrush.
Thank you for your helpful, critical perusal!
Simon
--
_______________________________________________________________________________
Personal: [EMAIL PROTECTED]
Yellow Skies: [EMAIL PROTECTED] http://www.yellowskies.com
Everyone does their own signature to be different. How does that work?
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Crossposted-To: rec.games.chess.computer
Subject: Re: Protocol for computer go
Date: 14 Dec 2000 21:28:45 -0800
[EMAIL PROTECTED] (David Wagner) writes:
> The underlying `operating system' (which must be trusted) exports
> a query-clock-cycles operation which returns the number of clock cycles,
> plus or minus a random number. This random number can be generated
> in a secret yet verifiable way with techniques described in an earlier
> post of mine, so others can still verify that the transcript proceeded
> correctly -- yet the go-playing program cannot guess the exact number
> of clock cycles due to the randomization. Thus, the non-determinism
> inherent in the number of clock cycles it takes to execute the
> algorithm cannot be exploited to alter the behavior of the program.
>
> Can this sort of idea be made to work? I'm not too sure myself,
> and would welcome comments on it.
I have to say I've lost track of the proposal but I think the basic
problem is this: Go-master Greg loses a game against the computer. He
shouts "Damn cheating hunk of tin! No computer could *ever* have come
up with that capture. You must have Anatoly Karpov (or his Go-playing
counterpart) sending moves to it by wireless modem! I demand to see
the instruction trace!" (This basically is what happened at the
Kasparov-DB2 chess match). But what collected data can you give him
that shows that the machine actually found that move?
Since the clock cycle count is at best somewhat correlated with the
instruction count, i.e. it's the instruction count plus some random
variable, can you find a sequence of values for the random variable
that leads to the machine picking that move?
I don't think there's an answer that's not inextricably entwined with
the specifics of the hardware and software involved. DB2, for example,
was a massive parallel supercomputer with around 1000 chess-specific
ASICs each doing its own tree search and all interacting with a shared
cache to spot nodes that had already been searched by another processor.
Crossposted to rec.games.chess.computer since this stuff gets discussed
there sometimes.
------------------------------
** 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
******************************
