Cryptography-Digest Digest #21, Volume #12 Tue, 13 Jun 00 18:13:00 EDT
Contents:
Re: Random sboxes... real info (Rex Stewart)
Re: Random sboxes... real info (tomstd)
A new conversion (encoding) scheme (Mok-Kong Shen)
Re: A new conversion (encoding) scheme (Mok-Kong Shen)
Re: Finding prime numbers (Bob Silverman)
Re: Digits of pi in Twofish (Anton Stiglic)
Re: Cryptographic voting (zapzing)
Re: Observer 4/6/2000: "Your privacy ends here" (Paul Shirley)
Re: Finding prime numbers (Anton Stiglic)
Re: Onefish (Twofishes sibbling) (Simon Johnson)
Re: Onefish (Twofishes sibbling) (tomstd)
Re: DPmax of Feistel Construction (zapzing)
Re: Multiple encryptions ("Douglas A. Gwyn")
Re: DPmax of Feistel Construction (tomstd)
Would you recon HushPOP to be any good ? ("Martin Hamann")
Re: Would you recon HushPOP to be any good ? ("Joseph Ashwood")
Re: Cipher design a fading field? ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: Random sboxes... real info
Date: Tue, 13 Jun 2000 18:52:30 GMT
I agree with your assesment that there is a differance between
an s-box being good and being ideal. For random (key dependant)
s-boxes, good may be good enough - if, as Terry Ritter has
pointed out, you use several of them.
The only cipher I have ever studied to use key dependant s-boxes
is Diamond/Diamond Lite by Mike Johnson. In these ciphers any
one bit change will affect (on average) 53 s-boxes. Of course
these ciphers are not fast - and are excruciatingly slow to key.
I think however saying NSA was "wrong" about their s-boxes might
be harsh - howabout they were half right :-) For the purposes
they wanted them for they did pretty well. And, even today,
the s-boxes aren't considered the weakest point in the cypher.
Constrained as they might be, I wonder how many of these "ideal"
s-boxes there might be (in theory). The only percentage I have
heard so far was something like one out of 10,000 - probably too
few and far between to make random searching effective.
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> [EMAIL PROTECTED] wrote:
> : tomstd <[EMAIL PROTECTED]> wrote:
>
> :> I.e is my point comming through? Random sboxes are hardly ideal.
>
> : Ok Tom -- new assignment. Random S-boxes are bad. [...]
>
> Lots of folk like random s-boxes. To quote from BS's AC (p. 351):
> ``my personal feeling is that S-boxes should be as large as possible,
> random and key-dependent.''
>
> I don't usually number myself among lovers of large s-boxes - but
large
> random s-boxes aren't exactly bad. In fact they're usually very
good -
> and the bigger they are the better they are, in terms of strength.
>
> Tom was closer to the mark - random s-boxes are rarely *ideal*.
>
> But what is an ideal s-box? The designers of DES had one idea - we
now
> know they were wrong.
>
> The "desirable" attributes of s-boxes are contradictory and pull in
> different directions. The resulting boxes are always compromises -
> emphasising one aspect at the expense of something else. The very
act of
> constraining s-boxes means the analyst has less potential candidate
> s-boxes to consider if he attempts to consider all possibilities for
that
> component.
>
> At least large random s-boxes are unlikely to be systematically weak.
>
> It's pretty hard to claim this about any constrained subset of s-
boxes,
> in the light of the possibility of unknown cryptanalytic attacks from
> future analysts, or simply ones who do not publish their results.
> --
> __________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
> |im |yler The Mandala Centre http://mandala.co.uk/ UART what
UEAT.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Random sboxes... real info
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 13 Jun 2000 12:09:31 -0700
In article <8i5vt7$bl7$[EMAIL PROTECTED]>, Rex Stewart
<[EMAIL PROTECTED]> wrote:
>I agree with your assesment that there is a differance between
>an s-box being good and being ideal. For random (key dependant)
>s-boxes, good may be good enough - if, as Terry Ritter has
>pointed out, you use several of them.
An sbox is good when it can effectively hinder cryptanalysis in
a cipher. An sbox is ideal when it satisfies numerous
conditions. For example the sboxes in SAFER are not ideal but
are good enough.
>The only cipher I have ever studied to use key dependant s-boxes
>is Diamond/Diamond Lite by Mike Johnson. In these ciphers any
>one bit change will affect (on average) 53 s-boxes. Of course
>these ciphers are not fast - and are excruciatingly slow to key.
Twofish uses key-dependent sboxes and is fairly quick.
>I think however saying NSA was "wrong" about their s-boxes might
>be harsh - howabout they were half right :-) For the purposes
>they wanted them for they did pretty well. And, even today,
>the s-boxes aren't considered the weakest point in the cypher.
Actually their sboxes are the point of attack, but even the best
found sboxes so far only push the attacks up, but not out.
>Constrained as they might be, I wonder how many of these "ideal"
>s-boxes there might be (in theory). The only percentage I have
>heard so far was something like one out of 10,000 - probably too
>few and far between to make random searching effective.
Have you checked out my preliminary results? Partially ideal
8x8 sboxes are about 1 in a million, and I have yet to find
fully idea 8x8 sboxes.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: A new conversion (encoding) scheme
Date: Tue, 13 Jun 2000 21:35:34 +0200
Base conversions have been propagated by wtshaw in our group
since some time and recently treated in certain detail in
another thread. In my opinion, the idea underlying that
scheme is somewhat analogous to coordinate transformations
where an object has different descriptions in different
coordinate systems so that simple operations in one system
may under circumstances correspond to more or less weird
operations in the other. Thus base conversions could be
of some utility when appropriately employed as a processing
step in encryption schemes. On this general view point,
I have recently suggested to use modular rests to effect a
conversion different from but in principle akin to the base
conversions. In the following yet another such conversion
(encoding) scheme will be presented. Being presumably not
treated before in the literature, it may well have
disadvantages that I haven't yet seen myself (excepting
eventually the efficiency issue). On the other hand, I
suppose it could certainly serve the purpose of demonstrating
the wide diversity of viable representations of informations
which could be exploited to help rendering the task of the
opponent hard.
We shall assume that the information to be converted is
in form of a sequence of octal digits (i.e. 4 bit values).
We determine first the runs of digits in the sequence, i.e.
sets of contiguous digits that are either ascending or
descending. Each run can be coded by one bit which indicates
up-run or down-run, followed by 8 bits indicating whether
the values 0-7 are present in the run or not. If we adopt the
(arbitrary) convention that 0 denotes up-run and 1 denotes
down-run and the 8 bits that follow are such that from right
to left they indicate the presence (1) or absence (0) of
the octal digits 0, 1, 2, ... 7, then each run corresponds
to 9 bits in total. If a run consists of a single element,
then the bit indicating the type of the run can be arbitrary
chosen.
Let's consider the octal sequence 420152202467. This has
five runs, as can be seen in the form (420)(15)(2)(20)(2467),
where we have used parentheses to separate the runs from one
another. The first run is then coded as the bit sequence
100010101, the second as 000100010, the third as 000000100,
the fourth as 100000101 and the fifth as 011010100. Obviously
the number of bits of the conversion result will in general
be different from the original sequence, i.e. can be smaller
or larger. In our example, the original sequence has 12*4=48
bits, while the conversion result has 5*9=45 bits. (For
storage into bytes, one can arbitrary fill to byte boundary
with any bits, since on back-conversion only full groups of
9 bits will get processed.)
M. K. Shen
===========================
http://home.t-online.de/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A new conversion (encoding) scheme
Date: Tue, 13 Jun 2000 22:02:02 +0200
Mok-Kong Shen wrote:
Very sorry, some essential corrections:
> We shall assume that the information to be converted is
> in form of a sequence of octal digits (i.e. 4 bit values).
Read:
We shall assume that the information to be converted is
in form of a sequence of octal digits (i.e. 3 bit values).
> or larger. In our example, the original sequence has 12*4=48
> bits, while the conversion result has 5*9=45 bits. (For
Read:
or larger. In our example, the original sequence has 12*3=36
bits, while the conversion result has 5*9=45 bits. (For
M. K. Shen
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Finding prime numbers
Date: Tue, 13 Jun 2000 19:52:09 GMT
In article <8i5vn8$bib$[EMAIL PROTECTED]>,
AllanW <[EMAIL PROTECTED]> wrote:
>
> I suppose that's true. But it's unlikely on it's face. Finding
> prime factors without knowing the primes would seem to be like
> guessing how to spell a word without knowing the alphabet.
Do us a favor. Go read about the subject before making any
further "guesses". Read Knuth Vol 2.
Modern factoring algorithms do not do trial division.
Further, even if one *did* do it that way, it is not necessary
to compute *any* primes. Instead, one would construct a (say)
8-spoke or 48 spoke (or larger) wheel and divide by all integers on the
wheel.
For example: the numbers less than 30 and co-prime to it are:
1,7,11,13,17,19,23,29. One uses this to construct a sequence of
integers co-prime to 2,3 and 5 and uses *this* sequence as candidates
for trial division. One trial divides with some composites, but so
what? Try to trial divide only by primes is SLOWER than allowing some
composites in the sequence. You can extend the wheel to include the
primes 7,11,13 etc. The pre-computation is small. The only constraint
is storage.
But trying to break an RSA key by trial division is worse than hopeless.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Digits of pi in Twofish
Date: Tue, 13 Jun 2000 16:15:40 -0400
In fact, this technique has been used in the generation of
strong primes as well, it is sometimes called kosherization.
This was used in IKE (rfc2409), where they suggest a strong
prime whose middle digits are a multiple of Pi.
It can be used for S-boxes or key expansion algos as a sort
of proof that there is no back door (as mentioned in the
previous post), for kosherazation.
P.S. By the way, I if anybody knows where the work Kosherization
was used for the first time, I'd really be interested in knowing.
Anton
Jim Gillogly wrote:
>
> tomstd wrote:
> >
> > it's blowfish not twofish that uses pi, and there is absolutely
> > no cryptographic reason to the best of my limited knowledge
>
> 'Transparency' is a good cryptographic reason. "See, we're using
> a pile of bits in here, but there's no back door -- honest. You
> can verify for yourself that it's the most obvious pile of bits in
> all of mathematics."
>
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Tue, 13 Jun 2000 20:10:56 GMT
In article <8i4i9u$bit$[EMAIL PROTECTED]>,
Greg <[EMAIL PROTECTED]> wrote:
>
> > > Tyranny is kept at bay by guns and will. Our government
> > > knows we have the guns, but they don't know if we have
> > > the will. Nor do we.
> > > The only lawful gun law on the books- the second amendment.
> >
> > Personally I think cryptography works better than
> > guns. for a gun to work you first must know
> > *who* to shoot. Then you have to be there with
> > your gun, get him before he gets you ...
> > All very messy.
>
> But the tyrant with a gun can stop you from using your PC.
If any government tries to stop people
from using PCs they will only accomplish
the economic collapse of their country.
After that, the country will be invaded
by hopefully more reasonable people.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Paul Shirley <[EMAIL PROTECTED]>
Reply-To: Paul Shirley <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,alt.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: Tue, 13 Jun 2000 21:20:22 +0100
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> writes
>The scheme is for use with arbitrary texts from books, e.g. religious
>ones, and newspapers and such stuffs and doesn't carry any secret
>messages. Its purpose is only to waste and hopefully exhaust the
>resources of the interceptors. I originally had that idea in a thread
>of sci.crypt discussing better ways (than incorporating sentitive
>words into e-mails) of jamming Echelon and similar machineries.
Then you've missed the point of monkey wrenching RIP. It does not matter
what the message is, only that its been encrypted. If it has been
encrypted the options for 'wasting time' are severely limited. Either
you hand the key over or go to prison.
If there's no encryption then prison is no longer an option for the
authorities, yet they still have to do the work. You are then in a much
stronger position to 'help' them waste their time.
Hopefully none of this will become necessary, its not quite too late to
stop this madness before it becomes law.
--
Paul Shirley: reply address may change at short notice.
cc'ed news posts *unwelcome*
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Finding prime numbers
Date: Tue, 13 Jun 2000 16:49:54 -0400
You could speed up a simple stupid brute force algorithm.
Instead of checking n integers in time O(n), you would take
time O(n/lg(n-1)).
But of course, the best known algorithm is not brute force,
but the Number Field Sieve. You can ask Mr. Silverman if
this helps anything in NFS, if you are kind, he might answer
you.
Anton
AllanW wrote:
>
> Suppose I had an algorithm so that, given a prime number P(n),
> I could find the next prime number P(n+1) extremely quickly.
> Let's say it was as quick as four or five integer additions.
> (I don't actually have such an algorithm, but let's say I did.)
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Onefish (Twofishes sibbling)
Date: Tue, 13 Jun 2000 20:38:15 GMT
A question about Pseudo Handarmard Transformations (PHT):
I believe one is:
y=(a+b) mod 2^32
When a & b are both 32-bit words.
Now if a & b are 8-bit words:
is y=(a+b) mod 2^8 a PHT?
If not, why not?
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Onefish (Twofishes sibbling)
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 13 Jun 2000 13:53:04 -0700
The PHT is given by
PHT(x, y)
x' = 2x + y
y' = x + y
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: DPmax of Feistel Construction
Date: Tue, 13 Jun 2000 20:56:34 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> I am trying to make a 16x16 sbox by using two 8x8 sboxes (and
> earlier I was using a single 8x8 sbox with similar results) and
> always seem to get a DPmax of about 16/65536 ... essentially I
> have
>
> A = A xor SBOX[B xor 1]
>
> B = B xor SBOX[A xor 2]
>
> .. 2 more times
>
> The sbox is the inverse in GF(2^8) so it itself has a DPmax of
> 4.
>
Dunno, but I would like to know what the
best DPmax of *any* 16x16 sbox is.
Maybe this is a pretty good figure
compared to the other 16x16 sboxes.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Multiple encryptions
Date: Tue, 13 Jun 2000 21:03:43 GMT
AllanW wrote:
> I think that the general consensus is that E o D is OFTEN
> more secure than either E or D, other than degenerate cases.
For a counterexample, see the most recent issue of Cryptologia.
------------------------------
Subject: Re: DPmax of Feistel Construction
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 13 Jun 2000 14:38:21 -0700
The DPmax of any n-bit function is at most 2^-n+1
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Martin Hamann" <[EMAIL PROTECTED]>
Subject: Would you recon HushPOP to be any good ?
Date: Tue, 13 Jun 2000 23:42:58 +0200
Reply-To: "Martin Hamann" <[EMAIL PROTECTED]>
HushMail is now available as a POP utility.
http://www.zdnet.com/eweek/stories/general/0,11011,2586300,00.html
I believe I've earlier heard Mr. Schneier say that the security in HushMail
was a joke. Does anyone know if HushPOP is just another snake oil product ?
Regards,
Martin Hamann, Student,
Technical University of Denmark.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Would you recon HushPOP to be any good ?
Date: Tue, 13 Jun 2000 15:07:31 -0700
Well, regardless of whether HushMail itself offers security that's a joke,
ANYTHING that goes over a POP3 connection (including your username/password)
goes in plaintext, unless they use extensions that are extremely rare and to
my knowledge not supported on any big name mail client. So the security of
the HushPOP is a joke, unless they are using an additional plugin to your
mail reader similar to what PGP has become to most people. But this will do
nothing to stop them from grabbing your username/password(passphrase) from
the login stage. It can be done securely, but it's doubtful that they have
made the quite significant effort to do such.
Joe
"Martin Hamann" <[EMAIL PROTECTED]> wrote in message
news:8i69t2$plu$[EMAIL PROTECTED]...
> HushMail is now available as a POP utility.
>
> http://www.zdnet.com/eweek/stories/general/0,11011,2586300,00.html
>
> I believe I've earlier heard Mr. Schneier say that the security in
HushMail
> was a joke. Does anyone know if HushPOP is just another snake oil product
?
>
> Regards,
> Martin Hamann, Student,
> Technical University of Denmark.
>
>
>
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Tue, 13 Jun 2000 21:21:52 GMT
Tim Tyler wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> : Actually the programs involved don't have to be very large.
> : Chaitin has a rather small one for his specialized version of LISP.
> They *have* to be potentially unboundedly large for the halting problem to
> exist.
Nope.
> If the size of the program is constrained, a halting determination program
> could be written which enumerates all programs of that size or shorter and
> lists whether they halt or not.
It "lists" them how?
> I cannot myself envisage a proof of security for a cypher system.
> This personal incredulity is by no means conclusive evidence - but
> I am pretty certain that no such proof currently exists for any cypher
> system, at least without making use of un-physical assumptions.
That is an argument from ignorance (no insult intended), which doesn't
prove anything. It may be that such proofs exist in places you haven't
looked. (In fact there are even some *published* papers on systems with
guaranteed security, although I haven't studied them enough to have an
opinion on theor validity. But they *do* exist.)
> The basic problem is that it is not possible to realistically place bounds
> on the capabilities of our opponents.
Sure it is. It is fairly safe to assume that they are constrained by
the laws of physics, by the principles of information theory, etc.
> We can be pretty sure that they can't violate the laws of physics -
> but we are also pretty certain that we do not know what the laws of
> physics actually are ...
That is the argument from skepticism, which is worthless. In fact we
know a *lot* about the physical principles involved with the way the
world operates, even if there is not a single unifying theory that
satisfactorily interrelates everything we know.
> Assuming that your opponents have a particular weakness is unlikely to
> convince the sceptic.
Skepticism is inherently a philosophical dead end.
------------------------------
** 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
******************************
