Cryptography-Digest Digest #330, Volume #13 Thu, 14 Dec 00 17:13:01 EST
Contents:
Re: Protocol for computer go (David Wagner)
Re: Sr. Cryptographer/mathematician ("Douglas A. Gwyn")
Re: Crypto Program for HP48GX Calculator ("Douglas A. Gwyn")
Re: security by obscurity ... ("Douglas A. Gwyn")
Homebrew Block Cipher: Moonshine (Simon Best)
Re: Protocol for computer go (David Eppstein)
book announcement--Brands ([EMAIL PROTECTED])
Re: Visual Basic Source Code (Tom St Denis)
Re: Visual Basic Source Code ("Jason Bock")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Protocol for computer go
Date: 14 Dec 2000 21:13:34 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
David Eppstein wrote:
>The problem is that, in many actual game playing programs, there isn't any
>explicit use of random number generators; the nondeterminism comes from
>much harder-to-control factors (like, exactly how many positions did the
>program have time to consider while waiting for the opponent to move).
Yes, I agree. (However, the example you gave is a bad one. There's a
trivial solution to that one: Use the cycle counter, not wall clock time.
All side inputs should be a deterministic function of the current execution
trace. Wall clock time does not satisfy this principle, but the cycle
counter does.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Sr. Cryptographer/mathematician
Date: Thu, 14 Dec 2000 20:14:28 GMT
Simon Johnson wrote:
> This is non-sensical. Simply because he doesn't know what name
> something is called doesn't mean he cannot do math; it just means,
> quite obviously, he doesn't known the name.
What Tom did was ridicule somebody else's use of *standard*
names for well-known branches of mathematics, which Tom
strongly implied demonstrated that they didn't know what
they were talking about. It's much like criticizing a
physician for not knowing that the liver and the spleen
are the same organ. Whose ignorance is actually shown?
------------------------------
Crossposted-To: comp.sys.hp48
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Crypto Program for HP48GX Calculator
Date: Thu, 14 Dec 2000 20:29:33 GMT
Tom St Denis wrote:
> [EMAIL PROTECTED] wrote:
> > I am looking for some crypto programs for the HP48GX. ...
> Why can't anyone do something for THEMSELVES! Try writting your own
> code and if you get stumped ask for help.
Why do you assume that brice98 isn't already stumped?
> For christ sake is everyone in this newsgroup incapable of their own
> work?
Some people might not be capable of some kinds of programming.
Others might prefer standing on the shoulders of others to
tripping over their own feet.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: security by obscurity ...
Date: Thu, 14 Dec 2000 20:25:01 GMT
Peter Thorsteinson wrote:
> It is often said that security by obscurity is not a valid approach.
> However, I cannot see a fundamental difference between using an algorithm
> that is difficult to guess, and a key that is difficult to guess (due to
> large name space and uniform probability distribution). I agree that
> parameterizing a general algorithm with a key is much more convenient that
> establishing a new algorithm for each session, but I suspect that these two
> approaches are not really different
What is meant is actually Kerchhoff's principle, namely that
one must not assume that the enemy is ignorant about the
methodology you are using, but rather is ignorant only about
the specific "key" information that is applied to particular
uses of that methodology. If your "general system" includes
selection of algorithms, etc. then the "key" would include
the parameters used to select the algorithms in a specific
case (session or whatever).
The practical basis for this principle is that both
encipherer and intended decipherer must share advance
knowledge of the system, and have the devices built and
operators trained in their use, etc. It is much easier to
keep secret just a small package of randomly-punched cards
etc. delivered periodically by secure courier than to keep
secret the details of how the equipment is constructed.
It is also often the case that the *structural* properties
of the system can be determined purely through analysis of
enciphered traffic, short of recovering the key.
------------------------------
From: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Homebrew Block Cipher: Moonshine
Date: Thu, 14 Dec 2000 21:28:34 +0000
Hello!
I've been lurking awhile, and thought I'd post my homebrew block cipher,
named Moonshine.
I'll state up front: I'm an amateur, I have little or no experience
(more the latter than the former) of cryptanalysis, I'm in no position
to claim that this homebrew cipher is in any way secure.
Anyway, as for 'sales blurb', let me say:
* It's heavily inspired by Rijndael
(http://csrc.nist.gov/encryption/aes/rijndael).
* It's heavily inspired by hypercubes.
* It's slightly inspired by Rubic's cube.
* Variable block and key sizes (at least, at the moment).
* Potential for lots of implementation optimisations.
* Doesn't use a Feistel structure.
So as to keep this post from being excessively lengthy (if it isn't
already), I won't say everything I could (like stuff about ways to
optimise implementations).
If anyone's interested in this enough to want demonstrative source code
(in C), I'm happy to post it here.
Again, I'm an amateur, and this is a homebrew cipher.
Simon
MOONSHINE
=========
ENCIPHERMENT
To summarise encipherment:
Nb: block size in bytes
Nk: cipher key size in bytes
Nr: number of rounds
Ns: number of subrounds per round
Nd: number of diffusion rounds per subround
Encipher:
{
Do key schedule (if not done in advance)
Add first subround key
Repeat Nr rounds of:
{
Shuffle block
Repeat Ns subrounds of:
{
Do byte substitutions
Repeat Nd diffusion rounds of:
{
Reorder bytes
Mix byte pairs
}
Add next subround key
}
}
}
ROUNDS, SUBROUNDS, DIFFUSION ROUNDS
Each diffusion round is there to do a bit of diffusion (unsurprisingly).
Each subround is there to do some diffusion (in the diffusion rounds),
provide nonlinearity (in the byte substitutions), and provide cipher key
dependency (by adding a subround key).
Each round is there to do the minimum diffusing required to each byte to
have a chance of being mixed with all other bytes, and to rearrange the
bytes a bit each time.
For example, with a 128 bit block size, there need to be four diffusion
rounds for each byte to have a chance of mixing with all other bytes in
the block. This could be done with four diffusion rounds per subround,
and just one subround per round, or four subrounds of one diffusion
round each, or two subrounds of two diffusion rounds.
KEY SCHEDULE
The cipher key is expanded into an expanded key, from which subround
keys can be directly taken, using the following method:
Nsrk = Nr*Ns + 1 (Nsrk = Number of subround keys)
Nexpand = Round_up( Nsrk * Nb/Nk )
Ndiff = Round_up( log[2]( Nb ) ) (log[b](a) = Logarithm base b of a)
Key expansion:
{
Counter byte = 0
Repeat Nexpand times:
{
Take a copy of the cipher key
Get the expansion constant for the counter value
XOR the expansion constant onto each byte
of the cipher key copy
Append the copy of the cipher key
to the end of the expanded key
Increment counter
}
For each successive subround key in the expanded key:
{
Repeat Ndiff diffusion rounds on the subround key of:
{
Reorder bytes
Mix byte pairs
}
}
}
The expansion constant is just the result of applying Rijndael's S-box
to the counter value. A diffusion round is the same as in encipherment.
The first subround key is the first Nb bytes of the expanded key, the
next subround key the next Nb bytes, and so on.
For decipherment, the same key schedule is used with the same cipher
key, except that the subround keys are used in reverse order.
SUBROUND KEY ADDITION
This is just a bitwise XOR of the block and the subround key. It is its
own inverse.
BLOCK SHUFFLING
Block shuffling is based on slice arrays. A slice array is a kind of
subarray of an array, where the subarray starts at some 'offset' in the
array, and successive subarray elements are separated in the array by
some 'stride'. (Slice arrays also have a size, which is just the number
of array elements in the slice array. For this cipher, the size is
always the maximum that would fit in the array being sliced.)
For example, if the array is '0123456789ABCDEF', a slice array of
offset=5 and stride=3 would be '58BE':
0123456789ABCDEF
* * * *
A slice array can then be treated as an array in itself, though really a
slice is just a way of indexing more general kinds of subarrays in an
array. Alter a slice array, and the array itself is altered.
Now that I can define block shuffling in terms of slice arrays:
Shuffle block:
{
offset = 0
stride = 1
while offset + stride < block size, do:
{
cycle the slice array (specified by offset and stride)
one place left
offset = offset + 1
stride = stride * 2
}
}
Cycling the slice array is just shifting the bytes of the slice array
one place to the left, and putting the byte that falls of the left hand
end back in the right most position. For example: '58BE' becomes
'8BE5'.
Illustrating the block shuffling with an eight byte block:
01234567
******** offset=0 stride=1
12345670
* * * * offset=1 stride=2
14365072
* * offset=2 stride=4
14765032
(It's not a very good shuffling scheme at all, but it does do a bit of
rearrangement of the bytes at the start of each round. This is the
Rubic's cube bit.)
The inverse of this shuffling is to just select the same slice arrays
but in the reverse order, and cycle them one byte to the right.
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).
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.)
The inverse is the inverse of byte pair mixing, followed by the inverse
of byte reordering.
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.
For example:
a0 a1 a2 a3 a4 a5 a6 a7
becomes:
a0 a2 a4 a6 a1 a3 a5 a7
The inverse is quite easy to work out from this. Starting with the
first byte of the old block and taking successive bytes, first fill up
the even indexed bytes of the new block, then fill up the odd indexed
bytes of the new block.
BYTE PAIR MIXING
For byte pair mixing, the block is split into two subblocks. If there
is an even number of bytes in the block, the two subblocks are of equal
length, otherwise the second is one byte longer. Pairs of corresponding
bytes in the two blocks are then mixed (except the last byte of the
block, if the block has an odd number of bytes).
For example:
a0 a1 a2 a3 a4 a5 a6
gets treated as:
a0 a1 a2
a3 a4 a5 a6
Byte pair mixing is similar to column mixing in Rijndael, except that
there are only two bytes, and byte mixing is done modulo x^2+1. Using
[0] and [1] indexes to signify 'top subblock byte' and 'bottom subblock
byte' respectively, byte pair mixing can be expressed as:
b[1]x + b[0] = ( c[1]x + c[0] )( a[1]x + a[0] ) mod x^2 + 1
where:
a: original byte pair
b: result byte pair
c: constant byte pair, where c[1]='02' and c[0]='01'
It boils down nicely to:
b[1] = a[1] + xtime( a[0] )
b[0] = a[0] + xtime( a[1] )
where 'xtime' is Rijndael's xtime function (and '+' is bitwise XOR, of
course).
The inverse of this can be done by first dividing each byte by '05'
(multiplying by the multiplicative inverse of '05'), and then applying
byte pair mixing to those bytes. The result is a pair of unmixed bytes.
DECIPHERMENT
Decipherment, in summary, is:
Decipher:
{
Expand cipher key (if not done already)
Reverse subround key order (if not done already)
Repeat Nr rounds of:
{
Repeat Ns subrounds of:
{
Add next subround key
Repeat Nd undiffusion rounds of:
{
Unmix byte pairs
Unreorder bytes
}
Unsubstitute bytes
}
Unshuffle bytes
}
Add last subround key
}
THE END
--
_______________________________________________________________________________
Personal: [EMAIL PROTECTED]
Yellow Skies: [EMAIL PROTECTED] http://www.yellowskies.com
Everyone does their own signature to be different. How does that work?
------------------------------
From: David Eppstein <[EMAIL PROTECTED]>
Subject: Re: Protocol for computer go
Date: Thu, 14 Dec 2000 13:38:32 -0800
In article <91bd5u$8tu$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (David
Wagner) wrote:
> David Eppstein wrote:
> >The problem is that, in many actual game playing programs, there isn't any
> >explicit use of random number generators; the nondeterminism comes from
> >much harder-to-control factors (like, exactly how many positions did the
> >program have time to consider while waiting for the opponent to move).
>
> Yes, I agree. (However, the example you gave is a bad one. There's a
> trivial solution to that one: Use the cycle counter, not wall clock time.
> All side inputs should be a deterministic function of the current execution
> trace. Wall clock time does not satisfy this principle, but the cycle
> counter does.)
It does? Even on a modern superscalar machine, under an operating system
with preemptive multitasking?
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
Date: Thu, 14 Dec 2000 16:41:28 -0500
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: book announcement--Brands
I thought readers of this list might be interested in this book. For
more information please visit
http://mitpress.mit.edu/promotions/books/BRAUHF00.
Rethinking Public Key Infrastructures and Digital Certificates
Building in Privacy
Stefan A. Brands
As paper-based communication and transaction mechanisms are replaced by
automated ones, traditional forms of security such as photographs and
handwritten signatures are becoming outdated. Most security experts
believe that digital certificates offer the best technology for
safeguarding electronic communications. They are already widely used for
authenticating and encrypting email and software, and eventually will be
built into any device or piece of software that must be able to
communicate securely. There is a serious problem, however, with this
unavoidable trend: unless drastic measures are taken, everyone will be
forced to communicate via what will be the most pervasive electronic
surveillance tool ever built. There will also be abundant opportunity
for misuse of digital certificates by hackers, unscrupulous employees,
government agencies, financial institutions, insurance companies, and so
on.
In this book Stefan Brands proposes cryptographic building blocks for
the design of digital certificates that preserve privacy without
sacrificing security. Such certificates function in much the same way as
cinema tickets or subway tokens: anyone can establish their validity and
the data they specify, but no more than that. Furthermore, different
actions by the same person cannot be linked. Certificate holders have
control over what information is disclosed, and to whom. Subsets of the
proposed cryptographic building blocks can be used in combination,
allowing a cookbook approach to the design of public key
infrastructures. Potential applications include electronic cash,
electronic postage, digital rights management, pseudonyms for online
chat rooms, health care information storage, electronic voting, and even
electronic gambling.
Stefan A. Brands is Distinguished Scientist at Zero-Knowledge Systems,
Inc., Montreal, Canada.
6 x 9, 305 pp., cloth ISBN 0-262-02491-8
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Source Code
Date: Thu, 14 Dec 2000 21:48:05 GMT
In article <91batb$cne$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> In article <91b151$404$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > 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!
> >
> > Tom
> >
> > Sent via Deja.com
> > http://www.deja.com/
> >
> I would say because its faster to code in than C..... However, this is
> debatable with cryptographic algorithms since most of the functions
> required to make an algorithm are not supported by the language.
I like C because it's primitives are those that a processor typically
works with. (i.e ints/char, shifts, xor, etc...). VB is more of an
abstract high level lang where you are working with primitives that are
less ideal for a processor.
Generally I see no need for Visual Basic. If you want to make GUI apps
program in C and use a resource editor...
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Jason Bock" <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Source Code
Date: Thu, 14 Dec 2000 16:03:50 -0600
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.
Jason
------------------------------
** 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
******************************