Cryptography-Digest Digest #768, Volume #11 Sun, 14 May 00 00:13:00 EDT
Contents:
S-BOX Construction Tutorial? ("Simon Johnson")
Re: On higher level Feistel schemes (Tom St Denis)
Re: Living in my car in Miami ... 5/10/2000 - cryptography and other ("Douglas A.
Gwyn")
Re: How does one test an encryption algorithm? ("Douglas A. Gwyn")
Re: Help!? Accidental 'crypt' needs to be undone ("Douglas A. Gwyn")
Re: Two basic questions ("Douglas A. Gwyn")
Re: factor large composite ("Douglas A. Gwyn")
Re: On higher level Feistel schemes (zapzing)
Re: UK issue; How to determine if a file contains encrypted data? (zapzing)
Re: Scary Possibility: Ticklish Chips (zapzing)
Re: S-BOX Construction Tutorial? (Tom St Denis)
Re: Cipher contest analysis [several] (Boris Kazak)
----------------------------------------------------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: S-BOX Construction Tutorial?
Date: Sat, 13 May 2000 14:49:10 -0700
Does any one have a PDF or HTML S-BOX construction tutorial?
If So please, leave a post with the URL as a reply to this message thanxs.
Simon Johnson
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: On higher level Feistel schemes
Date: Sun, 14 May 2000 01:22:39 GMT
In article <8fksf9$un8$[EMAIL PROTECTED]>,
zapzing <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > Previously I suggested several possibilities of
> > variations of a given block cipher, including using
> > varaible keys, permuting the subkeys and permuting the
> > S-boxes for different rounds. In all these variations
> > the block size remains unchanged. In the following
> > a simple, in fact trivial, possibility of doubling
> > the block size of a given cipher is indicated.
> >
> > We note that a Feistel scheme is customarily applied
> > inside a block cipher, e.g. DES. However, given any
> > block cipher of size n bits, denoted by the function
> > E in the following, one can easily build a cipher of
> > block size 2n bits though defining a typical Feistel
> > round as follows:
> >
> > L_(i+1) = R_i
> >
> > R_(i+1) = L_i xor E(K_i, R_i)
> >
> > where L_i and R_i each have n bits and the subkeys
> > K_i are to be obtained through some appropriate
> > key scheduling.
> >
> > An apparent disadvantage of this lies of course in
> > speed. However, the scheme appears otherwise to be
> > o.k. At least theoretically, one could recursively
> > apply the Feistel scheme to obtain ciphers of
> > increasingly larger block size.
> >
> > Thanks for your critiques and comments in advance.
> >
> I was just thinking of something similar, but
> I decided that I wanted to quadruple a block
> of DES. I think that in order to do that, recursive
> Feistel networks would be too time consuming,
> But I think that Wrapped Cypher Block Chaining
> mode would just about do the trick.
>
> If one has four blocks, A thru D.
> then WCBC mode can be described as:
>
> Procedure 1:
> X=B+E(A)
> Y=C+E(X)
> Z=D+E(Y)
> W=A+E(Z)
>
> Where + indicates xor and E indicates
> encryption. If the underlying algorithm
> is secure then I believe (if I am not mistaken)
> this should be secure. Am I correct in this?
In the encryption direction only. Maybe. But the diffusion between
blocks would not be 100% ideal. (See the CAST-256 design), note a
change in 'D' will only change W, and the rest with prob 0.
So you would have to have afew rounds of the four FULL encryptions.
This is a terribly bad idea in terms of efficiency.
If you must be wierd try this.
A = A xor (Ek1(C) + Ek2(D))
B = B xor (Ek2(C) + Ek1(D))
(swap (a, b) <-> (c, d))
And repeat with new k1/k2 values for a round or two more, where E is an
encryption algorithm (say DES in this case...). Each round uses two
independant keys. This algorithm is terribly slow (slower then just
encrypting four blocks in CBC mode) but would be a 'block cipher' with
ideal avalanche, etc..
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Living in my car in Miami ... 5/10/2000 - cryptography and other
Date: Sun, 14 May 2000 01:33:29 GMT
"Markku J. Saarelainen" wrote:
> When I woke up in this morning, it was around 5:50 A.M. and I saw a
> shopping mall.
Remind me: Why do we care?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How does one test an encryption algorithm?
Date: Sun, 14 May 2000 01:36:50 GMT
[EMAIL PROTECTED] wrote:
> All I want to know is that if my algorithm is tough to crack.
Unless it is particularly easy to crack, you'll probably never
be able to find out how tough it really is.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Help!? Accidental 'crypt' needs to be undone
Date: Sun, 14 May 2000 01:46:46 GMT
stanislav shalunov wrote:
> Look for a program called "Crypt Breaker's Workbench" (CBW).
You also need a VT100 terminal emulator, as I recall, since
CBW assumed that and is somewhat hard to modify for other
display types.
If you know for sure the first yay many plaintext characters
of the file, it will really help!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Two basic questions
Date: Sun, 14 May 2000 01:54:45 GMT
Ricardo wrote:
[DAGwyn wrote:]
> >That still has a lot of the statistical characteristics of English.
> Dat exxampul didd but iff wun iz klevva inuff wun kan surtunli
> rimmuuv most ov da kommon letarz - ivvun widdowt badd spelin in da
> kas ov Jorjj Perikk huu roat da bookk "La Disparition".
That is still so far from uniform-random that it doesn't pose
much problem for the cryptanalyst. The basic problem is that
in order to be understood by a native-language speaker, it is
still highly constrained by the need to remain "close enough"
to the structure of the natural language (which has a *large*
amount of structure). For example, if I fit a C-V model to
your text using SVD or HMM methods, I'll get nearly the same
topology as for genuine English.
> >A big problem is that the more you corrupt the natural language,
> >the greater the chance that the intended recipient will misread it.
> Kan you ridd wot I amm rytin ryt now widdowt tuu manyy probblimmz?
If you were trying to communicate some technical information,
for example whether to attack Georgia or George W., I might
easily misunderstand your intent.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: Sun, 14 May 2000 01:58:32 GMT
Tim Tyler wrote:
> Not even God's algorithm is O(1).
No, it's order 0.
However, it is unimplementable, so who cares?
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: On higher level Feistel schemes
Date: Sun, 14 May 2000 02:13:58 GMT
In article <8fkv4l$18m$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <8fksf9$un8$[EMAIL PROTECTED]>,
> zapzing <[EMAIL PROTECTED]> wrote:
> > In article <[EMAIL PROTECTED]>,
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > > Previously I suggested several possibilities of
> > > variations of a given block cipher, including using
> > > varaible keys, permuting the subkeys and permuting the
> > > S-boxes for different rounds. In all these variations
> > > the block size remains unchanged. In the following
> > > a simple, in fact trivial, possibility of doubling
> > > the block size of a given cipher is indicated.
> > >
> > > We note that a Feistel scheme is customarily applied
> > > inside a block cipher, e.g. DES. However, given any
> > > block cipher of size n bits, denoted by the function
> > > E in the following, one can easily build a cipher of
> > > block size 2n bits though defining a typical Feistel
> > > round as follows:
> > >
> > > L_(i+1) = R_i
> > >
> > > R_(i+1) = L_i xor E(K_i, R_i)
> > >
> > > where L_i and R_i each have n bits and the subkeys
> > > K_i are to be obtained through some appropriate
> > > key scheduling.
> > >
> > > An apparent disadvantage of this lies of course in
> > > speed. However, the scheme appears otherwise to be
> > > o.k. At least theoretically, one could recursively
> > > apply the Feistel scheme to obtain ciphers of
> > > increasingly larger block size.
> > >
> > > Thanks for your critiques and comments in advance.
> > >
> > I was just thinking of something similar, but
> > I decided that I wanted to quadruple a block
> > of DES. I think that in order to do that, recursive
> > Feistel networks would be too time consuming,
> > But I think that Wrapped Cypher Block Chaining
> > mode would just about do the trick.
> >
> > If one has four blocks, A thru D.
> > then WCBC mode can be described as:
> >
> > Procedure 1:
> > X=B+E(A)
> > Y=C+E(X)
> > Z=D+E(Y)
> > W=A+E(Z)
> >
> > Where + indicates xor and E indicates
> > encryption. If the underlying algorithm
> > is secure then I believe (if I am not mistaken)
> > this should be secure. Am I correct in this?
>
> In the encryption direction only. Maybe. But the diffusion between
> blocks would not be 100% ideal. (See the CAST-256 design), note a
> change in 'D' will only change W, and the rest with prob 0.
>
Good point, since bit diffusion *is* the whole point
here.
> So you would have to have afew rounds of the four FULL encryptions.
> This is a terribly bad idea in terms of efficiency.
>
In terms of hardware requirements maybe, but
if you have several superblocks to encrypt,
then the stages can be arranged so that,
if you have N superrounds, you have N
chips working on each stage. It's
like a bucket brigade.
This means that there would be more of
a time delay for setup, but the average
time to encrypt a superblock will be
about equal to the time to encrypt
one superblock, if the message is
long enough.
> If you must be wierd try this.
>
> A = A xor (Ek1(C) + Ek2(D))
> B = B xor (Ek2(C) + Ek1(D))
> (swap (a, b) <-> (c, d))
> And repeat with new k1/k2 values for a round or two more, where E is
an
> encryption algorithm (say DES in this case...). Each round uses two
> independant keys. This algorithm is terribly slow (slower then just
> encrypting four blocks in CBC mode) but would be a 'block cipher' with
> ideal avalanche, etc..
>
actually, I have also been discussing the possibility
of a hardware backdoor in a chip, and it has just
occured to me that if we introduce the
concept of rekeying into this, then it may
perhaps be possible to defeat a backdoor.
So we would be doing something like this:
C=C+E(K1+A,K2+B)
D=D+E(K1+B,K2+A)
A=A+E(K1+C,K2+D)
B=B+E(K1+D,K2+C)
where E(K,P) indicates the encryption of P with key K.
You could then do some other rounds with different keys.
What is your opinion on that?
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: UK issue; How to determine if a file contains encrypted data?
Date: Sun, 14 May 2000 02:26:24 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> On Fri, 12 May 2000 13:31:16 +0200, Runu Knips
> <[EMAIL PROTECTED]> wrote:
>
> >[EMAIL PROTECTED] wrote:
> >> This thread seems to neglect the fact that while being too random
may
> >> be cause for suspicion on the part the police, it is not proof that
> >> the apparently random bits are in fact ciphertext.
> >
> >Correct, this has been stated by multiple people in this thread,
> >including my little existence.
> >
> >> In the absence of access to keys which will prove that it is
ciphertext,
> >> by deciphering it, they cannot prove anything. It is more likely
that
> >> they will rely on circumstantial evidence, such as the number of
such
> >> files, the presence of encryption software on the machine, and
traffic
> >> analysis. All this doesn't necessarily amount to proof however.
> >
> >But the policemen don't need to search for further proofs.
>
> Why dont they?
>
> <Begin quote from Foundation for Information Policy Research
> (www.fipr.org) News Release, Thurs 10th Feb 2000>
>
> (Clause 49): to prove non-compliance with notice to decrypt, the
> prosecution must prove person "has or has had" possession of the key.
>
> <End quote>
>
> So if they cannot prove the apparently random file is cipher text to
> which a key exists, they cannot prove that the person has or has had a
> key.
>
> >The
> >only proof you can have that a random sequence is ciphertext is
> >if you know the cipher and the cipher key, which lead into some
> >valid plaintext.
>
> Indeed so the police (or prosecution) cannot prove that the persone
> has or has had a key to what they dont know is cipher text.
>
> >In fact, you can give them any key and any cipher, stating that
> >the data you've enciphered was random data. But I fear nobody
> >would believe you.
> >
> >> My guess is that it is a classic example of a law, like alcohol
> >> prohibition, that will simply force the prohibited activity
> >> underground, so that the ordinary punter has less access, while the
> >> seriously bad guys simply invest in more sophisticated set ups that
> >> will maintain their access and be pretty much unpoliceable.
> >
> >Which means Steganography might become quite popular in Britain. Or
> >the thankful crypto filesystem of Linux where you can always hide
> >additional data without letting people know.
>
> I suspect that since a file of pure ciphertext is indistinguishable
> from random numbers, police and prosecutors in the UK will not be able
> to rely on the discovery files of apparently random numbers if they
> want to have any hope of making their case.
>
> There are other fallacious posts in this thread - eg the suggestions
> about sending the Home Secretary encrypted files. As I understand it,
> the intended effect of clause 49, as summarised above, is that
> possesssion of what appears to be an encrypted file is not sufficient.
>
> Cl 49 was introduced specifically to address the objection to the case
> where a person may never have had possession of the key ("encrypted
> e-mail out of the blue").
>
> What will cause people trouble under the UK law is if they have, for
> example, PGP, and the key ring shows there are keys associated with
> their email id and they decline to make those keys available to the
> police.
>
> The critical challenge to the UK law will not be using stenography to
> hide the cipher text, but rather devising encryption apps that give no
> appearance of being an encryption app.
>
> So who is going to be the first person to devise an encryption app
> that is itself completely hidden and undetectable?
>
>
But you could have a perfectly good reason
for having that encryption app around
Perhaps you actually do use encryption to
send email to friends. Some files might just
use a different key that you deny the
existence of, that's all.
You would give the police the key to your
emails that you send to your "cover" friends.
the other files, you say 'Gosh, I don't
really know what that is".
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Scary Possibility: Ticklish Chips
Date: Sun, 14 May 2000 02:44:57 GMT
In article <8f8g1l$2cn$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Paul Rubin) wrote:
> In article <8f802p$rdc$[EMAIL PROTECTED]>, zapzing
<[EMAIL PROTECTED]> wrote:
> >Here's something to keep you awake at night: What if some of the
> >chips for doing DES etc. have been made "ticklish" , that is what if
> >some sort of irritant, such as a dose of radiation or an electrical
> >input that is out of band would prompt the chip to divulge its key.
> >This could be bad if bad guys manage to steal your (otherwise tamper
> >proof) encryption device. Any ideas on how to prevent this, (other
> >than by just trying to make your packaging impervious to all possible
> >tickles, which seems to me to be pretty hopeless) ?
>
> That's called differential fault analysis and it's a serious problem
> for smart card manufacturers. Several papers have been written about
it.
>
> For modules with more complicated packaging than smart cards, it's
easier
> to protect against, though I don't think any type of hardware tamper
> resistance can stop a really determined and rich attacker.
>
Of course not, a really determined attacher
could hunt me down and torture me or bribe
me, hopefully the latter.
But the essence of my post wasn't really differential
fault analysis, it was the possibility of a chip that
was actually designed to leak information under
certain circumstances, which is similar but not quite
the same thing.
I have another idea about it though.
what if rekeying was used in a sort of
an enlarged block cipher, for example like
this:
C=C+E(K1+A,K2+B)
D=D+E(K1+B,K2+A)
A=A+E(K1+C,K2+D)
B=B+E(K1+D,K2+C)
Where + indicates xor, and E(K,P) indicates
the encryption of P with key K.
Do several rounds of this, with several keys
and it would make it difficult for even a
malicious chip to leak any information that
an attacher could use (at least that is my
conjecture).
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: S-BOX Construction Tutorial?
Date: Sun, 14 May 2000 03:21:00 GMT
In article <8fjm8v$nqr$[EMAIL PROTECTED]>,
"Simon Johnson" <[EMAIL PROTECTED]> wrote:
> Does any one have a PDF or HTML S-BOX construction tutorial?
> If So please, leave a post with the URL as a reply to this message
thanxs.
>
> Simon Johnson
>
>
Terry Ritter has some good sources on it.
I also have my sbox generator C program if you care to look at it...
http://www.tomstdenis.com/sboxgen.c
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cipher contest analysis [several]
Date: Sun, 14 May 2000 03:54:01 GMT
"David A. Wagner" wrote:
>
> I looked at MMBOOZE, a variation on MMB but with some interesting
> new ideas, as proposed for the sci.crypt cipher contest. However,
> I think there is a differential attack against it.
*******************
> Each right pair suggests some subkey material, and this can probably be
> fashioned into a key-recovery attack with the standard techniques of
> differential cryptanalysis. This would need to be verified, of course,
> but I think it should probably all work out.
>
> There also seem to be other truncated differentials which have similar
> probability but allow for more use of structures. I did not search very
> hard for better truncated differentials, so it may be possible to greatly
> improve the attack.
>
> In any case, this does not look very good for the MMBOOZE cipher....
> What do you think?
============================
Dear Mr. Wagner:
Coming at last to the procedure of launching the proposed
differential attack on MMBOOZE, I want first to assure
myself that I understand all your assumptions and terms
correctly.
Thus, when you speak about a pair of ciphertexts with
difference 00000000ab000000, I understand it as:
1) there are 2 ciphertetxs XXXXXXXXXXXXXXXX and
YYYYYYYYYYYYYYYY, both 128 bits long, and
XOR operation between them yields 00000000ab000000.
Each letter stands here for 1 byte, the PLAIN
constant in the program is #defined so that the
block size is equal to 128 bits (16 bytes).
It could be any other number, the reasoning will
not change.
2) these 2 ciphertexts can be rewritten as
XXXXXXXXABXXXXXX and
XXXXXXXXCDXXXXXX, in this case AB^CD = ab
and diff = 00000000ab000000
Now your statement is that when it comes to decryption
with the multiplier chosen as Mult[A^B] and Mult[C^D],
there is some significant probability to obtain after
the decryption a pair of texts with the difference
0000000000cdef00
Let us trace the decryption process closely and see
what really will we obtain. To do this we need to trace
2 steps. We will exclude for now the case a==b when 2
different multipliers will converge into a single one.
First step is when XXXX, immediately adjacent to AB or
CD on the right, will be multiplied with 2 different
multipliers. Despite the fact that XXXX in both
ciphertexts are identical by definition, in this case
there is a probability 1 guarantee that the resulting
products will be different.
Unfortunately, the _XOR_ difference between the multiplier
indexes in the table provides absolutely no information
about the _XOR_ difference between the multiplication
products. The only things we know about this difference
are 1) it is nonzero and 2) it does not hold constant
over the possible range of XXXX, rather it behaves as a
random number within 2^32 range of values.
Come the second step.
The 2 bytes for the multiplier index will be taken
immediately adjacent to AB or CD on the left. Now the 2
multipliers selected will be identical, since they will
be selected based on XOR(XX), which is by definition
equal for both ciphertexts. However, in this case the
multiplicands will be different (by definition, due to
the fact that AB and CD are now parts of the 2
multiplicands).
Unfortunately, the _XOR_ difference between the
multiplicands provides absolutely no information
about the _XOR_ difference between the multiplication
products. The only things we know about this difference
are 1) it is nonzero and 2) it does not hold constant
over the possible range of multiplicands, rather it
behaves as a random number within 2^32 range of values.
In this case you are absolutely correct in stating that
there is a 1/2^16 probability for this difference to be
of the form 00cd, with the 2 higher bytes = 0. The
resulting difference in the 2 partially decrypted
ciphertexts will be of the form
0000000000cdef00
with exactly this probability, and cdef can in this case
amount to anything in 2^32 range.
Now taking the more special case of a==b, the multiplier
chosen for the first step will be equal for both ciphertexts.
In this case your assumption about the difference
0000000000cd0000
holding with probability 1/2^16 is also correct.
Thus, starting with the ciphertext pairs having the
_XOR_ difference
00ab000000000000 (a==b)
in 1-st step you can achieve the ciphertext pair with
_XOR_ difference
0000cd0000000000 (cd = anything)
with probability 1/2^16,
in 2-nd step you can achieve the ciphertext pair with
_XOR_ difference
000000efgh000000 (efgh = anything)
with probability 1/2^32, and in the last step
get the "plaintext pair" with the difference
YYYYYYYYYYYY0000
with the same probability. What is important here,
is a chain of trailing 0-s in the difference.
The bigger the block size, the easier it is to launch
this attack.
Unfortunately, I fail to see how this fact can help recover
any of the key material. The cd and efgh differences after
successive rounds of decryption are not any definite values,
and there is no easy way to link these to any particular
multiplier or to any particular position in the table.
On the positive side, this attack provides a definite way
of "distinguishing" - if the chosen ciphertext pairs can show
this kind of statistical bias, then there is a great
probability that the cipher used was the MMBOOZE. To stop this
attack, it would be necessary to double the number of rounds -
ta make it 6 instead of 3. In this case the 5 inner rounds
would lower the probability down to 1/2^80.
I also fail to understand the reasoning behind your statement
about the 2^25 chosen ciphertexts. Will you please elaborate
a little on the "technique of structure" which allows you
to multiply ciphertext pairs as rabbits - 2^15 pairs from
2^8 ciphertexts, and where does the additional 2^17 come from.
If you mean that you provide 2^17 sets of 2^8 chosen
ciphertexts each, this will give you (even with your technique
of structure) only 2^32 ciphertext pairs (1 hit). To be
statistically sure you will need at least 2^8 times more than
that, and this only for determining the type of the cipher...
I agree that this approach provides some interesting information
about MMBOOZE, but personally I would be confident trusting my
secret communications to this 3-round baby. I would even supply
each encrypted file with the "MMBOOZE" tag, so that there would
be no doubt about the algorithm.
Congratulations and best wishes BNK
------------------------------
** 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
******************************
