Cryptography-Digest Digest #612, Volume #14 Thu, 14 Jun 01 17:13:01 EDT
Contents:
Re: Algorithm take 3 - LONG (was : Re: RSA's new Factoring Challenges: $200,000
prize. (my be repeat)) ("Joseph Ashwood")
Re: Alice and Bob Speak MooJoo (Al)
Re: Publication violation notice ("AY")
Re: survey (Sam Yorko)
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY (wtshaw)
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY (wtshaw)
Re: Brute-forcing RC4 (Ian Goldberg)
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and (Mok-Kong
Shen)
Re: FIPS 140-1 test (Tim Tyler)
Re: Substitution Humor! ("Robert J. Kolker")
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY (Mok-Kong Shen)
Re: FIPS 140-1 test (Tim Tyler)
Re: Substitution Humor! (Mok-Kong Shen)
sbox design intuition? ("Tom St Denis")
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Algorithm take 3 - LONG (was : Re: RSA's new Factoring Challenges:
$200,000 prize. (my be repeat))
Date: Thu, 14 Jun 2001 12:26:28 -0700
Crossposted-To: sci.math
that has to be one of the longest NNTP delays I've seen, 5 days.
It's getting much better, but it's still a program. You still use dword,
instead of the rather more useful integer. Use forcibly compress 4 entities
together into a byte when that is an implementation detail (you should
consider the detail when computing the RAM but not when explaining the
algorithm). And your arbitrary addition of variables (without types) is
still around. I would like to see a move away from a pseudo programming
language to something more expressive, but as long as it's complete and
understandable it will work. So would it be possible to move to a higher
level? I know last time I asked you to move to a lower level, it's hard to
find the right balance sometimes.
I'm just going to skip straight to the algorithm
the presentation of something that appears to be highly structured is very
beneficial, the knowledge that you come from a Pascal background is actually
at least as useful because it reveals some hidden assumptions. My comments
are inline
> <START OF ALGORITHM>
>
I will assume that there is some portion of algorithm here that will do
things like define the BoxStack, and StackLen.
Just for accounting I'll list the variables that are not properly defined up
here
BoxStack
StackLen
Boxes
> NextBox : dword;
Just make this an integer.
> OldVal : byte;
> DestPart : byte;
> DestMask : byte;
I'd suggest defining a type Box that has 4 subvariables, labelled A,B,O and
C. Each of these variables takes a value from the set {0,1,unknown,
invalid}. You implementation will likely do it as you wrote for optimization
but for algorithm expression it is unecessary. It won't match what most
people call math, but it will be useful. To do this you might consider
splitting things to a less monolithic structure. For example find a
reasonable name for a portion of the algorithm, something like
StackInitialize(...), then give an semi-English explanation of what it does
(something like what I've called gibberish would be suitable), then later
give a more rigorous definition.
>
> while StackLen > 0 do
> begin
> NextBox := BoxStack[StackLen - 1];
> dec(StackLen);
I assume dec(...) is decrement
> redim(BoxStack, StackLen);
I assume redim(A,B) changes the dimensions of A to correspond with B
> OldVal := Boxes[NextBox].Values;
> Boxes[NextBox].Values := Lookup[Boxes[NextBox].Values];
>
> // Has the link connected to input A changed?
> if ((Boxes[NextBox].Values xor OldVal) and $03) > 0 then
I assume "xor" is the bitwise logical eXclusive-OR, and "and" is the
bitewise logical And.
> begin
> // Make the mask for the destination box
> DestPart := Boxes[NextBox].BoxPart and $03;
> DestMask := not ($03 shl DestPart);
> // Set the destination box values:
> // The original value OR'd with
> // the state of the link shifted to the correct place
> Boxes[Boxes[NextBox].ABox].Values :=
> (Boxes[Boxes[NextBox].ABox].Values and DestMask) or
> ((Boxes[NextBox].Values shl DestPart) and (not DestMask));
> inc(StackLen);
I assume inc(...) increments, and "not" is the bitwise logical inverse. I
don't know what shl is?
> redim(BoxStack, StackLen);
> BoxStack[StackLen - 1] := Boxes[NextBox].ABox;
> end;
>
> // Has the link connected to input B changed?
> if ((Boxes[NextBox].Values xor OldVal) and $0C) > 0 then
> begin
> // Make the mask for the destination box
> DestPart := (Boxes[NextBox].BoxPart shr 2) and $03;
> DestMask := not ($03 shl DestPart);
> // Set the destination box values:
> // The original value OR'd with
> // the state of the link shifted to the correct place
> Boxes[Boxes[NextBox].BBox].Values :=
> (Boxes[Boxes[NextBox].BBox].Values and DestMask) or
> (((Boxes[NextBox].Values shr 2) shl DestPart) and (not
DestMask));
> inc(StackLen);
> redim(BoxStack, StackLen);
> BoxStack[StackLen - 1] := Boxes[NextBox].BBox;
> end;
>
> // Has the link connected to the output changed?
> if ((Boxes[NextBox].Values xor OldVal) and $30) > 0 then
> begin
> // Make the mask for the destination box
> DestPart := (Boxes[NextBox].BoxPart shr 4) and $03;
> DestMask := not ($03 shl DestPart);
> // Set the destination box values:
> // The original value OR'd with
> // the state of the link shifted to the correct place
> Boxes[Boxes[NextBox].OBox].Values :=
> (Boxes[Boxes[NextBox].OBox].Values and DestMask) or
> (((Boxes[NextBox].Values shr 4) shl DestPart) and (not
DestMask));
> inc(StackLen);
> redim(BoxStack, StackLen);
> BoxStack[StackLen - 1] := Boxes[NextBox].BBox;
> end;
>
> // Has the link connected to the carry changed?
> if ((Boxes[NextBox].Values xor OldVal) and $C0) > 0 then
> begin
> // Make the mask for the destination box
> DestPart := (Boxes[NextBox].BoxPart shr 6) and $03;
> DestMask := not ($03 shl DestPart);
> // Set the destination box values:
> // The original value OR'd with
> // the state of the link shifted to the correct place
> Boxes[Boxes[NextBox].CBox].Values :=
> (Boxes[Boxes[NextBox].CBox].Values and DestMask) or
> (((Boxes[NextBox].Values shr 6) shl DestPart) and (not
DestMask));
> inc(StackLen);
> redim(BoxStack, StackLen);
> BoxStack[StackLen - 1] := Boxes[NextBox].BBox;
> end;
> end;
>
> <END OF ALGORITHM>
>
> Basically it goes like this:
> 1) Get the next box to process
> 2) Find out the new value of the box
> 3) If input A has changed, update the other box and push the index onto
the
> stack.
> 4) If input B has changed, update the other box and push the index onto
the
> stack.
> 5) If the output has changed, update the other box and push the index onto
the
> stack.
> 6) If the carry has changed, update the other box and push the index onto
the
> stack.
> 7) Go back to 1 if there are more boxes still to process.
>
> Before I try and do the more complex part to specify exactly, I'd like to
know
> whether I'm on the right track.
You are very much on the right track, it's still a little too computer bound
int some parts, and a little too loose in others, but it's definitely
starting to look better.
>
> On a slightly different note, this is not really why I originally posted,
which
> was to try to get people to think about the concept (which many have).
However,
> since a lot of people on this NG won't even look at an concept unless is
is
> presented in algorithmic form (at which point it isn't really an concept
any
> more) it obviously needs to be translated into this form in order for
people to
> look at it. Unfortunately, as of tomorrow, I will no longer have much time
to do
> this, so I would ask that you try to look at the concept and figure out
what's
> going on rather than to ignore it until I finally can present a complete
> algorithm (which quite probably will be in at least 6 months' time, more
likely
> further). I will be able to answer questions on the method (or whatever
state
> you wish to call it) as it stand, though. I make take a couple of days,
and
> since my news server seems to drop things after they are a couple of days
old
> it's probably safer to send these questions through email:
> emboss1(AT)i4free.co.nz
There's a reason we generally don't take things seriously until they are
presented in a clear form. There have been numerous claims about factoring
in polynomial time, and at least one that I vaguely remember that claimed
sub-linear time. All of these have been found to have serious flaws once
they are formalized. One of the most publisized examples was just a few
months ago. All the individual managed to prove was that if you could
perform a discrete log under the modulus you could factor, this was already
known, and it was also already known that discrete log in general is at
least as hard as factoring, so all his work and publicity was for nothing.
There are other, less well publicized variations of the same story. In many
ways I hope this one ends differently, I'd like to see one of the few
functional hard problems actually fall, it'll be good for a lot of things
(bad for e-commerce immediately, but good for security in the long run).
Joe
------------------------------
From: [EMAIL PROTECTED] (Al)
Subject: Re: Alice and Bob Speak MooJoo
Date: 14 Jun 2001 12:36:21 -0700
Hi Bob
You are right, all government agencies during war and peace time have
said finding the resources to speak their enemies languages has caused
significant delays in decoding (ie key strenghening).
WWII: US said cracking purple was considerably complicated by having
to learn Japanese.
UK & US agencies have found criminals have their own language (just
like un original cockney).
By the by; not using encryption has been argued to be better than
using.
As secret messages infered by innocuous emails/letters can't be
filtered as easily and are legally innocuos . ie U have security just
by being another face in the crowd.
And all those people using safeweb.com and other anonymizers don't
realise that they are actually drawing attention to themselves just by
using it.
------------------------------
From: "AY" <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy
Subject: Re: Publication violation notice
Date: Thu, 14 Jun 2001 20:51:13 +0100
which reminds me of this...
http://www.nctimes.com/news/071700/dd.html
"... One of the freed observers, British army Maj. Andrew Harrison, said he
was informed of the rescue mission a day in advance when he was sent a
cryptic message by satellite phone disguised as a chess move..."
------------------------------
From: Sam Yorko <[EMAIL PROTECTED]>
Subject: Re: survey
Date: Thu, 14 Jun 2001 12:47:01 -0800
"Douglas A. Gwyn" wrote:
>
> Joseph Ashwood wrote:
> > ... Explore the boundaries, we know that the middle of the sandbox
> > offers some good secure areas, but it's crowded, find something that can
> > distinguish your designs from the designs of others. ...
>
> Joseph made some good points. One class of cryptosystem that has
> not been thoroughly explored in the open literature is stream
> ciphers that are *not* of the key-generator class. Some solid
> theoretical results there would be publishable, and a good system
> along those lines would have many uses. Not all communications
> are block-oriented!
I (and everybody in the WLAN 802.11 community) would be >very<
interested in something like this. With the amazing number of attacks
against RC4 being published, we would welcome a better solution for
encryption of the data stream.
Sam
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Date: Thu, 14 Jun 2001 13:23:50 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> Isn't it that the existence of the so-called trust centers
> is because of the need of proving whether a public key
> actually belongs to me? If you consider that the
> trustworthiness of a trust center in fact needs itself a
> proof, you get what I meant.
>
> M. K. Shen
An well known bank robber was asked why he robbed banks. His answer was,
"Because that's where the money is."
It seems that to penetrate trust, you would make a bee-line to a trust
center and try to corrupt it for your own purposes.
--
In trying to get meaning from the TmV-OK saga, remember that
those who do not learn from history are apt to repeat it.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Date: Thu, 14 Jun 2001 13:18:58 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
> >
> > Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> >
> > > The problem is whether one has a 'common' measure of
> > > security that could be applied to all sorts of encryptions.
> >
> > Note that some ciphers are outside of both of these categories. The
> > strength of them ranges from stupidly simple to GOK.
> >
> > There is no and can't be one common measure of security. Without
> > repeating them, I had to create that which some saidcould not be, a way to
> > variously describe comparitive security of different ciphers in several
> > ways. I can't ignore Shannon, even as he did not cover all the relative
> > factors and did not know and therefore could not include new aspects of
> > recent ciphers in his thinking.
>
> I suppose that discussions long ago in the group have
> already established that there is no scientifically
> rigorous and practically applicable measure of 'strengh'
> of ciphers.
Carefully read what I said above that there can be no SINGLE universally
useful measure of security. I say that there can be MANY that have
different uses as different aspects of strength are directly available.
Those that want to escape a solution of the strength problem because it is
complex miss the utility of such an effort.
--
In trying to get meaning from the TmV-OK saga, remember that
those who do not learn from history are apt to repeat it.
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: Brute-forcing RC4
Date: Thu, 14 Jun 2001 19:55:59 +0000 (UTC)
In article <[EMAIL PROTECTED]>, S Degen <[EMAIL PROTECTED]> wrote:
>
>
>David Wagner wrote:
>>
>> If you want to break WEP encryption, there are many ways to do so
>> without recovering the RC4 key. (You can see the paper to be presented
>> at MOBICOM 2001 for some discussion, for instance.)
>
>I know, i am doing research about WLAN security, but i simply want to
>decrypt the key :) Where can i find this paper?
There's a draft copy at
http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html
- Ian
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and
Date: Thu, 14 Jun 2001 22:44:02 +0200
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > > > "Douglas A. Gwyn" wrote:
> > > > > Sure we can. In this particular case, we now know that
> > > > > the program could not be completed, not even in principle.
> > > > So please suggest such a goal for the future scientists.
> > > ? Why would I want to suggest an impossible goal?
> > To support your emphatic claim 'Sure we can'. ...
>
> Please do not remove the context then misrepresent what I was
> saying. What was it to which I said "sure we can"? It matters!
You yourself had snipped that context in a previous post.
Here it is:
S: One could say that Whitehead and Russell had persued the
'wrong' goal and failed. But then which goal was/is
instead 'the' 'right' one? Could anyone say that? I am
not sure that one can.
G: Sure we can. In this particular case, we now know that
the program could not be completed, not even in principle.
Note that I asked whether one could give a 'right' goal
(instead of the 'wrong' goal of Whitehead and Russell)
and you answered with an emphatic 'sure'.
>
> > If it was consistent, it was not wrong.
>
> The programme required completeness. Therefore it was wrong.
You wrote in a previous post about 'wrong model', not
'wrong programme' (I understand you mean by 'programme'
'goal'.) As I said, a logical model is wrong, if it is
not consistent. The stuff did by the two authors is not
wrong in the mathematical sense (e.g. 2+3=6 would be
wrong mathematically). Every proof in the book must be
correct (even though I haven't touch that book), since
it apparently is a recognized literature. It just didn't
attain the big goal that they wanted to achieve.
>
> > knowledge. But the theorem is really significant in my
> > humble view, for antinomies have been sort of thorns in
> > the eyes of logicians. If I were you in the present context,
> > I would have taken the trouble to go to the library and
> > locate the stuff that I had read about the theorem and
> > posted something useful for the readers of this thread
>
> Sorry, I don't have the time, and as I said it's rather
> obvious once you know it. (The basic idea is you can
> iterate the system and it has to converge to a unique
> fixed point due to convexity.)
I certainly could not but accept your having difficulties
with your time. If I am allowed nonetheless to say a word
about my inner feeling, I would say that a little bit more
guidance from you to search for that theorem (and a
complete proof) would have been of great value to me.
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: FIPS 140-1 test
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Jun 2001 20:13:41 GMT
Dobs <[EMAIL PROTECTED]> wrote:
: Thanks a lot for this links, however I am looking for source code of FIPS
: 140-1 statistical test in C (but working one)
: or any other tests but please in C :))))
DiehardC? http://www.helsbreth.org/random/diehard.html
NIST test suite? http://csrc.nist.gov/rng/
Plab do a C++ test suite - but you have to mail them to get it...
http://random.mat.sbg.ac.at/
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: "Robert J. Kolker" <[EMAIL PROTECTED]>
Subject: Re: Substitution Humor!
Date: Thu, 14 Jun 2001 16:52:11 -0400
[EMAIL PROTECTED] wrote:
> After zis fifz yer, ve vil hav a reli sensibl riten styl. Zer vil be no
> mor trubl or difikultis and evrivun vil find it ezi to understand ech
> ozer. Ze drem vil finali kum tru! And zen ve vil tak over ze
> world!
Und you vil enchoy it!
Bob Kolker
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Date: Thu, 14 Jun 2001 22:50:22 +0200
wtshaw wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> > wtshaw wrote:
> > >
> > > Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> > >
> > > > The problem is whether one has a 'common' measure of
> > > > security that could be applied to all sorts of encryptions.
> > >
> > > Note that some ciphers are outside of both of these categories. The
> > > strength of them ranges from stupidly simple to GOK.
> > >
> > > There is no and can't be one common measure of security. Without
> > > repeating them, I had to create that which some saidcould not be, a way to
> > > variously describe comparitive security of different ciphers in several
> > > ways. I can't ignore Shannon, even as he did not cover all the relative
> > > factors and did not know and therefore could not include new aspects of
> > > recent ciphers in his thinking.
> >
> > I suppose that discussions long ago in the group have
> > already established that there is no scientifically
> > rigorous and practically applicable measure of 'strengh'
> > of ciphers.
>
> Carefully read what I said above that there can be no SINGLE universally
> useful measure of security. I say that there can be MANY that have
> different uses as different aspects of strength are directly available.
> Those that want to escape a solution of the strength problem because it is
> complex miss the utility of such an effort.
The problem with having many different measures is
the situation when these measures seem to have no
inherent relation to one another (let alone to be
convertible like inch and centimeter). Given a particular
cipher, which measure should one use? If there is no
clear-cut answer, then the co-existence of different
measures is confusing in my humble view.
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: FIPS 140-1 test
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Jun 2001 20:23:06 GMT
Dobs <[EMAIL PROTECTED]> wrote:
: I am looking for source code of FIPS
: 140-1 statistical test in C (but working one)
: or any other tests but please in C :))))
One test is at:
http://www.home.aone.net.au/qualcomm/fips140.c
``fips140.c is freely usable C source code implementing the statistical
test for correct operation of a random generator specified by FIPS
140. A "-v" flag reports the gathered statistics of the input file. A
single #define allows selection of either version 1 or (default, draft
at time of writing) version 2. FIPS 140-2 significantly tightens the
tests over the previous version.''
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Substitution Humor!
Date: Thu, 14 Jun 2001 23:04:31 +0200
[EMAIL PROTECTED] wrote:
>
> Substitution Humor!
>
> The European Commission has just announced an agreement
> whereby English will be the official language of the EU rather
> than German which was the other possibility. As part of the
> negotiations, Her Majesty's Government conceded that English
> spelling had some room for improvement and has accepted a 5
> year phase-in plan that would be known as "Euro-English".
>
> In the first year, "s" will replace the soft "c". Sertainly, this will
> make the sivil servants jump with joy. The hard "c" will be
> dropped in favour of the"k". This should klear up konfusion and
> keyboards kan have 1 less letter.
[snip]
It may be of interest to note that in Germany there is
yet controversial issue 'Schreibreform' which leads to
analogous seemingly ridiculous cases of new word forms.
M. K. Shen
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: sbox design intuition?
Date: Thu, 14 Jun 2001 21:08:30 GMT
I am sieving for 8x1's right now that have a LPmax of 16/256 and are SAC
compliant.
My question is, if I pick eight 8x1s which together satisfy BIC to the
seventh order [i.e any linear combo of the eight output bits is nonlinear]
shouldn't the 8x8 have a low LPmax and DPmax overall?
My guess [sorry I haven't plumbed through all the Nyberg, Seberry et al
papers yet, although I ahve read a few] is that if the 8x1s are nonlinear
(NL) then the 8x8 will be NL and that if the sboxes follow SAC and the 8x8
follows BIC then the 8x8 will haev a low DPmax.
So far I have found over 3,200 8x1 functions that have a LPmax (i.e the
highest absolute FWT output is the numerator of ) 16/256 and have a zero SAC
bias.
I am using the FWT code from Terry Ritters site [which I transcribed to C].
Any hints or guesses to if this is right?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
** 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
******************************
