Cryptography-Digest Digest #502, Volume #12 Tue, 22 Aug 00 03:13:01 EDT
Contents:
Re: New algorithm for the cipher contest ([EMAIL PROTECTED])
Memory usage ([EMAIL PROTECTED])
Re: Provable (or probable) primes ("Ed Suominen")
Very Fast Decorrelated Cipher ([EMAIL PROTECTED])
Re: Kryptos and Gillogly (Jim Gillogly)
Re: Very Fast Decorrelated Cipher ([EMAIL PROTECTED])
Re: OTP using BBS generator? (Bryan Olson)
Re: SHA-1 program (cool!) ("Ed Suominen")
Re: Memory usage (Mack)
Re: CRC? (Peter "Shaggy" Haywood)
Re: 215 Hz five-qubit quantum processor (Torkel Franzen)
Re: Very Fast Decorrelated Cipher ([EMAIL PROTECTED])
The future direction ... ([EMAIL PROTECTED])
Re: Bytes, octets, chars, and characters (Paul Schlyter)
Re: Bytes, octets, chars, and characters (Paul Schlyter)
Re: SHA-1 program (cool!) (S. T. L.)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New algorithm for the cipher contest
Date: Tue, 22 Aug 2000 02:56:23 GMT
In article <8nsopc$1iq$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <8ns93e$fr3$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> >
> > It looks like you are doing multiplications modulo 2^64, may I
suggest
> > this neato thing called differential cryptanalysis? Since your
> > multiplication doesn't create a group structure you don't get the
nice
> > decorrelation you would have otherwise. Also there are many weak
keys
> > per round (i.e even keys). Consider any key with the lower 'n' bits
> > set to zero ... there are sum from i=1 to 63 (2^64) over 2^i, weak
> > keys... or just over 2^63... Well this is per round. If your cipher
> > only uses 8 32-bit words as the key, then it's slightly more
> >
> > I suggest you could make neat differentials such as toggleing the
> > middle bit which would affect the upper 32 bits in the first round,
> > then only the lower 32 bits in the next round (with some
probability)
> > etc... this could be made into a four round differential.
> >
> > I can't think of a specific attack for it yet, but I bet others
> could :)
> >
> > Back to the drawing board :)
>
> The K argument passed to the CipherBlock function is a subkey derived
> from the primary key S (called "secret numbers" in the documentation).
>
> S is a vector with a variable number of 64-bit integers. Usually, S
> contains 2 or 3 integers (128 or 192 bits). Is the key that the user
> should keep and provides the algorithm strength against brute-force
> attack.
>
> K is a fixed length vector (8 integers = 512 bits).
>
> The "MakeKey" function is used to create K from S. In this function I
> try to construct K as random integer sequence based on S.
> Examining "MakeKey" you will notice that is hard to find S that gives
> an specific K. Note the similarity between "MakeKey" and a stream
> cipher with S the key, K the stream and "FCipher" function the RNG.
>
> Statistical tests of MakeKey produced K's as random bit sequences, for
> all S values I could test.
>
> Also, at the end of "MakeKey" the multiplicative elements K[0]..K[3]
> are forced to be odd.
Still multiplication in Z is not a good idea since it's not a group
operation.
> Weak K values are very improbable but not impossible. So, based on
your
> observations, I will improve MakeKey to test and discard non-random K
> values. I think discarding is not a problem, since K keyspace is
> usually much larger then S keyspace.
Weak K values will come from having low hamming weights.
> About differential cryptanalysis, I think the combination of
> multiplication (even mod 2^64) with bit-reversal is a good defense. I
> will study this deeply and post my results.
You may be surprised :)
I will admit it does seem difficult but I have only looked at it
briefly. Here's a trick.
Consider flipping the lsb of the input, then if the K[0] has a zero lsb
then the msb of the output of the first round may be flipped with some
probability not 1/2 :). Then as you reverse the string you get the
biased msb in the lsb position.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Memory usage
Date: Tue, 22 Aug 2000 02:59:51 GMT
Is taking 128kb for precomputed-tables for a cipher taboo in the
desktop world? I want to make a 128-bit cipher using a pair-wise
decorrelation module as the F function, this requires multiplication in
GF(2^64) which can be a pain in the but.
So I decided todo eight 8x64 sboxes that emulate a GF multiplication
for each round. I am thinking of eight rounds for the cipher so it
will need 8x8x8x64x256=131072. The cipher will be very fast (only
eight look ups/xor per round) but require ram.
So is 128kb too much in a desktop world? My guess is no, but I would
like some opinions...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Ed Suominen" <[EMAIL PROTECTED]>
Subject: Re: Provable (or probable) primes
Date: Mon, 21 Aug 2000 20:15:25 -0700
Thanks for the "prime time," folks!
Ed Suominen
Registered Patent Agent
Web Site: http://eepatents.com
PGP Public Key: http://eepatents.com/key
------------------------------
From: [EMAIL PROTECTED]
Subject: Very Fast Decorrelated Cipher
Date: Tue, 22 Aug 2000 03:22:26 GMT
To go with my point of precomputed tables I present (source only, paper
to follow) a pair-wise Decorrelated 64-bit cipher that encrypts at 12
cycles per byte on my K6-2 with the reference C code.
Please check it out at
http://www.geocities.com/tomstdenis/files/tc6a.c
The source is relatively easy to follow.
I will write a paper soon so please comment.
Thanks,
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Kryptos and Gillogly
Date: Tue, 22 Aug 2000 04:35:42 +0000
Achilles Outlaw wrote:
> Jim-- you made mention that part three of the code is a reference to
> Howard Carter's discovery of King Tutankhamun's tomb; and it (the
> plaintext) ends in the question "Can you see anything?" I should point
> out that the plaintext is not a very accurate reproduction of his diary
> entry (is there a reason for this?). But in a post you stated that the
I assume the modifications are to get the right number of letters for
the kind of transposition he wanted to use for this part of the cipher.
That doesn't explain the misspelling -- the diary had it right, I think.
The whole passage suggests to me the same process one sees in
cryptanalysis -- heavy spade-work followed by the first crack, which
is relatively easily enlarged to expose all the secrets. I suspect
Sanborn saw it more generally as a metaphor for all the work of the CIA.
> answer Carter gave was, "Yes, wonderful things." That's actually not
> true-- what he said was, "I replied to him, Yes it is wonderful."
> (http://www.ashmol.ox.ac.uk/gri/4sea1not.html, see November 26). I
Thanks for the correction.
> only mention this in pursuit of a better crib. That response reminded
> --
> Achilles Outlaw
> 26 Wedmath 1993
> 12.19.7.8.13.8.16 Lord O' Night 2 ----> give or take a millenium
A heretic! 26 Wedmath?? That puts the solstices all out of joint!
--
Jim Gillogly
Hevensday, 30 Wedmath S.R. 2000, 04:30
12.19.7.8.14, 9 Ix 17 Yaxkin, Third Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Very Fast Decorrelated Cipher
Date: Tue, 22 Aug 2000 04:28:33 GMT
In article <8nsrl3$4ol$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> To go with my point of precomputed tables I present (source only,
paper
> to follow) a pair-wise Decorrelated 64-bit cipher that encrypts at 12
> cycles per byte on my K6-2 with the reference C code.
>
> Please check it out at
>
> http://www.geocities.com/tomstdenis/files/tc6a.c
>
> The source is relatively easy to follow.
>
> I will write a paper soon so please comment.
>
> Thanks,
> Tom
I just read the twofish-impossiblediff paper and found out about the
attack on DEAL. So I will change the cipher to use eight rounds. It
works at 16.92 cycles per byte with eight rounds which is still pretty
fast...
I will post updated source and a paper later on this week.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Tue, 22 Aug 2000 04:40:23 GMT
Mok-Kong Shen wrote:
> Bryan Olson wrote:
> > Mok-Kong Shen wrote:
> > > First of all the 'zero' is understood in the sense of
> > > probability theory not in the sense of number theory.
> > > At the time the spy makes up a list for casting a die,
> > > he has free choice out of a practically unlimited topics
> > > to be mapped to the die. The die may also be cast a
> > > multiple times (thus having a larger event space) to
> > > render the probability you mentioned arbitrarily small.
> > > Once the topic is selected, he has yet a free choice
> > > of messages (content). So before the timepoint where
> > > his huge neuronal network starts to compose the message,
> > > even the spy himself doesn't know what that message is.
> > > So I think that justifies to ascribe a probability 0.
> >
> > That justifies "small" or even "negligible".
> > Zero is wrong.
>
> Then kindly give me an example of yours that can
> serve to illustrate a probability of measure zero
> so that we could have a compararison.
Uh, O.K: Let m be any message space, and s the sum
of the probabilities of all messages in m. Consider
the probability that s does not equal one.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Ed Suominen" <[EMAIL PROTECTED]>
Subject: Re: SHA-1 program (cool!)
Date: Mon, 21 Aug 2000 22:04:18 -0700
Thanks for contributing a very nice little program that addresses a
particular need of mine. At the moment, I have only one suggestion: arrange
the hex digits of the hash output in groups of four, as is conventional with
both PGP and the GNU Privacy Guard software. In the current version, they
are clumped together in big groups that are not easily committed to
short-term memory for comparison with a reference hash value (e.g., of a
public key fingerprint).
P.S. - I tested your program on a 2 MB ZIP file (high entropy), and its
output was exactly the same (except for the digit-clumping problem discussed
above) as the SHA1 hash generated with GPG using the following command line:
"gpg --print-md sha1 <file>". Not an exhaustive test, to be sure, but a good
sign that the software is working.
Ed Suominen
Registered Patent Agent
Web Site: http://eepatents.com
PGP Public Key: http://eepatents.com/key
"S. T. L." <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I've programmed a little thing that calculates the SHA-1 hash of a given
file;
> it's the first real thing I've done in C, so the source code is probably
ugly,
> but it's there. It's available at
http://members.aol.com/stl137/download.html
> . Both the binary (29KB) and the C source code (13KB) are provided, and
are
> distributed under the GNU GPL. I never did find a quick utility to
calculate
> an SHA-1 hash, so I made my own. :-P Most of the code is crufty; the one
> thing I'm sort of proud of is the part that pads the message on the fly
(no
> temp files!). Perhaps someone on sci.crypt will find it useful or
hilarious,
> though I'd prefer the former to the latter. Heh.
>
> Enjoy!
>
> -*---*-------
> S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
> My upgraded Book Reviews Page: * http://sciencebook.cjb.net *
> Optimized pngcrush executable now on my Download page!
> Long live pngcrush! :->
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 22 Aug 2000 05:14:08 GMT
Subject: Re: Memory usage
>Is taking 128kb for precomputed-tables for a cipher taboo in the
>desktop world? I want to make a 128-bit cipher using a pair-wise
>decorrelation module as the F function, this requires multiplication in
>GF(2^64) which can be a pain in the but.
>
>So I decided todo eight 8x64 sboxes that emulate a GF multiplication
>for each round. I am thinking of eight rounds for the cipher so it
>will need 8x8x8x64x256=131072. The cipher will be very fast (only
>eight look ups/xor per round) but require ram.
>
>So is 128kb too much in a desktop world? My guess is no, but I would
>like some opinions...
Using anything over 8k will kick it our of L1 cache on low grade systems.
(old pentiums and 486's). Can't tell you what the limits are for
all of the newer hardware but 128k is pushing it.
Now on the flip side, if the system has a large L2 cache running at
1/2 CPU then you only need four cycles per fetch (mileage may vary).
On a high end cpu, it will only take two cycles per fetch (mileage may
vary). So if the market is low end then no 128k is too much but if it
is high end then s-box away.
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
>
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Peter "Shaggy" Haywood)
Crossposted-To: alt.msdos.programmer,comp.lang.c,comp.lang.c++,comp.os.msdos.programmer
Subject: Re: CRC?
Date: Tue, 22 Aug 2000 05:35:58 GMT
Reply-To: [EMAIL PROTECTED]
THIS MESSAGE WILL BE DELIVERED WHENEVER (IF) THE NEWS SERVER IS UP
AGAIN. PLEASE DIRECT ANY COMPLAINTS REGARDING THIS DELAY TO
mailto:[EMAIL PROTECTED]
Groovy hepcat Mario Tonni was jivin' on Mon, 21 Aug 2000 03:13:10
+0200 in comp.lang.c.
CRC?'s a cool scene! Dig it!
>Often I hear the term "CRC", which I know that means
>"cyclic redundancy check".
>
>What I wonder instead is if CRC's are error-recovering
>methods, or simply a more reliable way to calculate a
>checksum?
This is off topic in comp.lang.c, comp.lang.c++, sci.crypt, and
arguably alt.msdos.programmer and comp.os.msdos.programmer too.
(Although, those last two will accept just about anithing. You could
post a poem about your cat and most people would not object. Some
might even correct your grammar and spelling... if they have the
slightest clue about those things themselves. I've never seen a
newsgroup more accepting of off topic posters.)
But, of course, you did not post this to one single place where this
just might be on topic, such as comp.programming.
--
===== Dig the EVEN NEWER, MORE IMPROVED news sig!! =====
============== Shaggy was here! ===============
http://aardvark.apana.org.au/~phaywood/
============= Ain't I'm a dawg!! ==============
------------------------------
From: Torkel Franzen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: 22 Aug 2000 07:34:53 +0200
[EMAIL PROTECTED] (Maynard Handley) writes:
> I think it's a great example because it gets to the root of why this is
> interesting. I mean, let's face it, who apart from five logicians in the
> world gives a damn about the sort of self-referential statements that
> Godel used to prove the theorem?
The self-referential statements are just a technicality. The Godel
sentence for T ("this sentence is not provable in T") is equivalent
in T to "T is consistent".
Setting aside the misleading topic of self-reference, the
incompleteness theorem can today be formulated, for effectively
axiomatizable theories, as the statement that there are, in any
such theory T, infinitely many undecided statements of the form
"the Diophantine equation P=0 has no solution". Whether there are
any mathematically interesting examples is another matter. In recent
years, much work has been done on producing sentences undecidable
in T that have independent mathematical interest.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Very Fast Decorrelated Cipher
Date: Tue, 22 Aug 2000 05:34:10 GMT
Can someone help I think this is how the attack on five rounds goes..
For any input diff (0,a) you use pairs of inputs such as (L,Ri) where
Ri varies and L remains the same. Then the output is something like
(b,a).
With 2^32 possible inputs of the form (L,Ri) you can get about 2^31
right pairs which would remove 2^31 keys right?
Then you need todo this 2^32 more times before the key becomes apparent?
That means you need 2^63 chosen texts?
I'm lost...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: The future direction ...
Date: Tue, 22 Aug 2000 06:01:36 GMT
Dear all :
Sorry , I am a fresh in this area, can I ask a question ?
Until now , I know that cryptography is based on "compute secure"
. But if quantum computer appears , is this method still useful or
we have another direction to make a security system?
The second question is about the distributed cryptography .
Is there anyone can tell me how to start in this area ?
For example, Where I can get the research progress or the related
papers?
Thanks for reading this.
Sincerely..
fish
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Crossposted-To: comp.lang.c
Subject: Re: Bytes, octets, chars, and characters
Date: 22 Aug 2000 07:48:56 +0200
In article <8nrhsi$te5$[EMAIL PROTECTED]>,
John Winters <[EMAIL PROTECTED]> wrote:
> In article <8nrds8$jsv$[EMAIL PROTECTED]>, Dan Pop <[EMAIL PROTECTED]> wrote:
>>In <8nqjkq$fq5$[EMAIL PROTECTED]> [EMAIL PROTECTED] (John Winters) writes:
>>
>>>Definitely not - a word is the natural size of number for manipulation
>>>of the machine - sometimes a little hard to pin down. The misconception
>>>that a word is two bytes comes from the every-computer-is-a-PC-running-DOS
>>>brigade.
>>
>>It's even older than that. It was first introduced by the PDP-11.
>>The VAX, a 32-bit machine that predates the PC, had 16-bit words
>>"inherited" from its predecessor, the PDP-11.
>
> Ah, I know 16 bit words are older than that - it was the misconception
> that I was talking about.
You mean the idea "a word is always 16 bit" was a misconception in the
PC world, but not in the PDP/VAX world?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Crossposted-To: comp.lang.c
Subject: Re: Bytes, octets, chars, and characters
Date: 22 Aug 2000 07:49:18 +0200
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Paul Schlyter wrote:
>
>> Yep -- a word is X bits on an X-bit machine, that's the rule.
>
> That is a tautology. The real question is, what is meant
> by "X" in calling a computer an "X-bit machine"? I have
> encountered real cases where no matter what you use for X,
> it could be disputed.
X = the width, in bits, of the data bus.
Yes, I know there are cases where the external and the internal
data buses differ in width... :-(
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Date: 22 Aug 2000 06:44:01 GMT
Subject: Re: SHA-1 program (cool!)
<<Thanks for contributing a very nice little program that addresses a
particular need of mine.>>
:-D Cool!
<<At the moment, I have only one suggestion: arrange the hex digits of the hash
output in groups of four, as is conventional with both PGP and the GNU Privacy
Guard software. In the current version, they
are clumped together in big groups that are not easily committed to
short-term memory for comparison with a reference hash value>>
Yes, I am aware of the PGP style of fingerprints. However, the SHA-1
specification, which has been my constant companion since I first tried to
implement the algorithm (in BASIC, actually... shudder), always gives the
hashes in 8-hexit groups, and it naturally fits the thinking of a "word" that
I've learned (32-bit value; again, from the SHA-1 spec). However, it is true
that people do prefer other modes of display and yours is a good suggestion. I
will include it after I figure out how to do it.
<<P.S. - I tested your program on a 2 MB ZIP file (high entropy), and its
output was exactly the same (except for the digit-clumping problem discussed
above) as the SHA1 hash generated with GPG using the following command line:
"gpg --print-md sha1 <file>". Not an exhaustive test, to be sure, but a good
sign that the software is working.>>
I haven't used GNU Privacy Guard, but the GNU name tells me it's good. I've
gone over the algorithm as it's implemented a few times in my head, and I would
have thought that I could confidently say that after twenty revisions to
version 0.01 (the first "finished" version that gave a hash, albeit a very
corrupted one), the implementation is logically perfect and should cope with
all possible inputs under 4GB. Sadly, I just found that one exists, although I
have NO idea where it's coming from as it hasn't shown up either in the 1M-"a"
vector or your 2MB file. I took the largest darn file I had on my hard drive,
a hulking behemoth called "pak0.pak" in the \valve\ directory of the game
Half-Life (weighing in at a crushing 302,907,835 bytes), and the reference I
use (HASHcipher demonstration by Bokler.com) output a different hash than my
SHA-1 program. Something is afoot, and I'm not sure exactly what it could be.
On the upside, SHA1.EXE only took thrice the time of the Bokler software to
output its hash, which is cool; even better is that my program didn't crash.
Of course, now I have a new bug to contend with....
Thanks again for replying about my program; I'll implement a switch for display
style soon. :-D Any other sci.crypt regulars want to diagnose the problem in
my code?
-*---*-------
S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
My upgraded Book Reviews Page: * http://sciencebook.cjb.net *
Optimized pngcrush executable now on my Download page!
Long live pngcrush! :->
------------------------------
** 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
******************************
