Cryptography-Digest Digest #218, Volume #12 Thu, 13 Jul 00 07:13:01 EDT
Contents:
Re: SC also in inverse ? (=?iso-8859-1?Q?H=E5vard?= Raddum)
Re: DES Analytic Crack (Simon F)
Re: Proposal of some processor instructions for cryptographical (Terje Mathisen)
Re: Random Numbers (Tim Tyler)
Re: key dependent s-boxes (Tim Tyler)
Re: Base Encryption: Strongest Cypher (Simon Johnson)
Re: Q: Hadamard transform (Simon Johnson)
Re: Steganographic encryption system (Andrew McDonald)
Re: Steganographic encryption system (Tim Haynes)
Re: Q: Hadamard transform (Simon F)
Re: Use of EPR "paradox" in cryptography (Tim Tyler)
Re: Q: Hadamard transform (Mok-Kong Shen)
Re: DES Analytic Crack (Mok-Kong Shen)
Re: attack against CBC mode (Runu Knips)
Re: attack against CBC mode (Runu Knips)
Re: Chaining mode discussion (Runu Knips)
Re: Q: Hadamard transform (Mok-Kong Shen)
Re: Q: Hadamard transform (Mok-Kong Shen)
Re: General Question on cryptography (Runu Knips)
Cryptographic Camouflage ("Andrew Wong")
Re: Chaining mode discussion (Mark Wooding)
----------------------------------------------------------------------------
From: =?iso-8859-1?Q?H=E5vard?= Raddum <[EMAIL PROTECTED]>
Subject: Re: SC also in inverse ?
Date: Thu, 13 Jul 2000 10:04:29 +0200
Runu Knips wrote:
> If a sbox is SC (single cycle), the inverse is also
> SC, isn't it ?
>
> So one can drop the test if the inverse is SC in
> Tom's sboxgen. Makes that program a little
> simpler and faster 8-)
Of course. If the Sbox is SC you can make a sequence {a_0, a_1, ...,
a_{n-1}} such that a_{i+1}=S[a_i], 0<= i <=n-2, and a_0=S[a_{n-1}]. If
you want to do the same with the inverse Sbox you get the sequence in
reverse, also a single cycle.
------------------------------
From: Simon F <[EMAIL PROTECTED]>
Subject: Re: DES Analytic Crack
Date: Thu, 13 Jul 2000 08:34:15 GMT
In article <[EMAIL PROTECTED]>,
Volker Hetzer <[EMAIL PROTECTED]> wrote:
> "Douglas A. Gwyn" wrote:
> >
> > Mok-Kong Shen wrote:
> > > Do you know any literature about obtaining and solving the set of
> > > equations for DES? Could you give any reference or are you merely
> > > postulating on a miscalculation? Thanks.
> >
> > As previously reported here, many years ago a colleague constructed
> > the complete, explicit set of DES encipherment equations and printed
> > them on a line printer, resulting in output just a few inches thick.
> > That much data can easily be held in RAM on today's computers.
> The problem is not to hold them in RAM but to solve them.
> Suppose you've got Ciphertext=DES(Key,Messagetext).
> Now, you've got Ciphertext and Messagetext and want to know
> what key was used. You can try to solve the equation for
> the key bits or you could try to find bits that make the equation
true.
> I don't think the first approach is feasible.
> However, in the second case a lot of progress has been made lately.
Did
> anybody try to solve those equations using a BDD approach?
I tried using both BDDs and BEDs on RC5. I generally found that apart
from a few particular key bits, moving a key bit variable from the
bottom to the top of the tree resulted in exponential growth in the size
of the tree. Although the initial tree was quite small, it rather
quickly grew to fill up the 2GB of RAM on the system it was running on
(and slowed down a lot!).
Simon
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Wed, 12 Jul 2000 15:20:49 +0200
"Peter L. Montgomery" wrote:
> For multiple-precision multiplication, the fundamental
> arithmetic operation is
>
> x1*x2 + x3 + x4 -> (double-length register).
>
> where all inputs (x1, x2, x3, x4) are unsigned, single-length.
> The result cannot overflow: if the inputs are bounded by R-1,
> then the output is bounded by R^2 - 1 (where typically R = 2^32 or 2^64).
>
> Of course a four-input, two-output primitive would use considerable
> opcode space. The IA-64 gives us the top and bottom of
> x1*x2 + x3 in one instruction each, which is an excellent start
> since these can overlap.
> However we seem to need three more multiply-add instructions
> to add x4 to the result if the data are in floating point registers
> (even after putting the integer 1 in an FP register).
The missing fourth input is the exact reason why I have been advocating
carry-save arithmetic, by using twice as much storage, you get both
something that works with the existing opcodes, and allows arbitrary
parallelism.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Reply-To: [EMAIL PROTECTED]
Date: Thu, 13 Jul 2000 08:33:03 GMT
Paul Koning <[EMAIL PROTECTED]> wrote:
: John Savard wrote:
:> ...But the simplest rule for producing truly random bits
:> from biased bits is to use this table:
:>
:> 00 : discard
:> 01 : 0
:> 10 : 1
:> 11 : discard
: Shouldn't that be "less biased bits from biased bits"?
: If there is correlation over lengths greater than 2, this
: approach alone is not sufficient.
With one common and orthodox sense of the term "bias", John's statement
was spot on.
If there are other problems besides a bias (such as the correlations you
mention), it may not be sufficient.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ This tagline no verb.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: key dependent s-boxes
Reply-To: [EMAIL PROTECTED]
Date: Thu, 13 Jul 2000 08:25:34 GMT
Vladimir Castro Alves <[EMAIL PROTECTED]> wrote:
: I am looking for references on key dependent s-boxes [...]
IIRC, "Practical S-box Design", S. Mister and C. Adams, contains
some useful ideas and information in this area.
Download it from: http://adonis.ee.queensu.ca:8000/sac/sac96/papers.html
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ UART what UEAT.
------------------------------
Subject: Re: Base Encryption: Strongest Cypher
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 13 Jul 2000 02:09:02 -0700
Would someone be kind enough to restate what this 'Base'
encryption method is?
It seems like u're generating a class of ciphers. In which case
the its like using, RC5 with a 32-bit block 1024-bit key one day
and RC5 with a 64-bit block and 128-bit key the next.
Altough the actual encryption engine is the same, they may have
adverly different cryptographic properties.
Anyway, i can't form an opinion on this cipher until i know
exactly what it is. Until then, i'll keep an open mind :)
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Q: Hadamard transform
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 13 Jul 2000 02:11:17 -0700
Prehaps this is related:
What is a Pseudo Handarmard Transformation and its cryptographic
signifiance?
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Andrew McDonald)
Crossposted-To: comp.os.linux.development.apps,uk.comp.os.linux
Subject: Re: Steganographic encryption system
Date: Thu, 13 Jul 2000 10:23:51 +0100
On Wed, 12 Jul 2000 02:12:52 +0100,
phil hunt <[EMAIL PROTECTED]> wrote:
> On Tue, 11 Jul 2000, Frank Gifford wrote:
> >
> > There are certain pitfalls with ciphers in this context. Assuming you use
> > a block cipher, you have to consider the chaining mode.
>
> What's a chaining mode?
Ah. Methinks you need to read up on using crypto.
If you want paper, Bruce Schneier's 'Applied Cryptography' is fairly
good.
On-line, try Peter Gutmann's tutorial:
<http://www.cs.auckland.ac.nz/~pgut001/tutorial/index.html>
Or maybe Ross Anderson's lecture notes from:
<http://www.cl.cam.ac.uk/Teaching/1998/>
('Introduction to Security' in part IB, 'Security' in part II)
> > Then you have to
> > think about the IV to go with it.
>
> IV? Intra-venous??
Initial/Initialisation vector.
> > A strong cipher should be indistinguishable from random noise.
>
> Agreed.
>
> > But if two
> > streams of data seem to have blocks of repeated data in them, that is an
> > indication that a block cipher was used. This is what I'm thinking about
> > in terms of a cryptography expert for the prosecution. Showing repeated
> > data which are, say, 64 bits in length and multiples of 64 bits apart would
> > be enough to show that it wasn't random data and that the likely explanation
> > is that it is encrypted data.
>
> This is infact what blowfish does (I've just checked it). But I thought
> blowfish was a strong cipher? -- obviously I must be wrong somewhere here.
>
> So how do I get it so it doesn't repeat?
Use a suitable chaining mode.
> > >* strong encryption -- no-one can crack it (what key size do I need for this?)
> >
> > For "uncrackable", 256 bits for a symmetric key system.
>
> Blowfish is a max of 448 bits, right?
Just remember that keyspace on its own is not a measure of security.
Consider how many keys a simple substitution cipher has, but it is
not generally secure.
Andrew
--
Andrew McDonald
[EMAIL PROTECTED]
http://www.mcdonald.org.uk/andrew/
OpenPGP DSA/ElG 1024/2048 3EDE 0FBC 6138 DCA0 FC8E C508 FCBB A9C8 F2DE ED36
------------------------------
From: [EMAIL PROTECTED] (Tim Haynes)
Crossposted-To: comp.os.linux.development.apps,uk.comp.os.linux
Subject: Re: Steganographic encryption system
Date: 13 Jul 2000 10:15:02 +0100
jungle <[EMAIL PROTECTED]> writes:
> phil hunt wrote:
> >
> > On Wed, 12 Jul 2000 00:40:39 -0400, jungle <[EMAIL PROTECTED]> wrote:
> > >current, well working stego have ration of 1 to 2 ...
> > >and all are super safe / super stego ...
> > >you are creating stego that will have ratio of 1 to 30 ...
> > >
> > >what a waste of resources ...
> >
> > I'm not forcing you to use it, you know.
>
> I'm not stopping your from developing un - needed software, to ...
`Need' is determined by the author, not "the market", btw...
~Tim
--
| Geek Code: GCS dpu s-:+ a-- C++++ UBLUAVHSC++++ P+++ L++ E--- W+++(--) N++
| w--- O- M-- V-- PS PGP++ t--- X+(-) b D+ G e++(*) h++(*) r--- y-
| So shine on, harvest moon, | http://piglet.is.dreaming.org/
| Cast your might on the ripening corn | [EMAIL PROTECTED]
------------------------------
From: Simon F <[EMAIL PROTECTED]>
Subject: Re: Q: Hadamard transform
Date: Thu, 13 Jul 2000 09:17:22 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> There exists 2-D Fourier transform. Does anyone have literature
> pointer of an analogous 2-D Hadamard transform? Thanks in advance.
In a texture compressor (for Dreamcast) I used Hadamard transforms to
extract frequency information.
Assuming that you have an n*n matrix of values, M, (where n is a power
of 2), I just used:
Result = 1/n^2 * (Hn * M * "Hn-transpose")
where Hn is the n*n hadamard matrix. (Hn-transpose is actually just
H)
Just to check we aren't talking about different things, H is defined
by...
H1 = [1], and
H2n=[Hn Hn]
[Hn -Hn]
The DC component ends up in the top left corner of matrix. I also wanted
the frequency values sorted so that the frequency data increased from
left to right and top to bottom. To get this, I had to re-order the rows
and columns of H.
Simon
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Crossposted-To: sci.physics
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Use of EPR "paradox" in cryptography
Reply-To: [EMAIL PROTECTED]
Date: Thu, 13 Jul 2000 08:58:19 GMT
In sci.crypt Bill Unruh <[EMAIL PROTECTED]> wrote:
: In <[EMAIL PROTECTED]> Roger Schlafly <[EMAIL PROTECTED]>
:writes:
:>Benjamin Goldberg wrote:
:>> True about interception, but it's easy to detect if this has
:>> occurred. If someone intercepts and re-sends data, then
:>> there is a 25% chance of polarization being changed (per bit
:>> intercepted).
:>Which means that someone can grab a few bits and have a
:>decent chance of not being caught. In some cryptographic
:>application, losing just a few bits is catastrophic.
: [...Eve] may still have gotten a few of them. [...]
: They can now do for example a oneway hash of the bits they have, and
: compare those. If they agree, they they are pretty certain that she
: also did not eavesdrop any substantial percentage of the secret bits.
Somehow, this stage never seems to get mentioned in classical descriptions
of quantum cryptography.
: (If E was lucky and did eavesdrop on a some, the prob of not being
: detected goes something like .75^n where n is the number of bits.)
This figure is some distance from the original 1/2^(no_of_bits_checked)
probability of eavsdropping being detected suggested by most descriptions.
: They can now do a running hash of the bits, (eg, each 128 bits of
: key is run through say MD5 to give 128 bits of new key which depends
: on all of the 128 bits-- since the probability is negligible that E
: listened in on 128 bits and was not detected (.75^128 =10^-16),
: this gives a key which Eve does not know any bits of.
This stage never seems to get mentioned in classical descriptions
of quantum cryptography either :-(
Note that the hash needs to be strong enough that knowing some bits of the
input does not provide any useful information about the output.
*Hopefully* Eve will not know of some method of getting such information
from the hash you are using which you are unaware of.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Hadamard transform
Date: Thu, 13 Jul 2000 11:50:51 +0200
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > One maybe odd question I would like to know is whether one
> > would get something inherently different in quality, if, instead of
> > doing 1-D Hadamard transform of n^2 values, one fills these
> > into a matrix of n*n and process that with a 2-D transform.
>
> What problem are you trying to solve? Why 2 dimensions instead
> of 64?
My thought was that the one approach might be more advantageous
than the other in the context of crypto, i.e. if the transform is
employed
in an algorithm.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: DES Analytic Crack
Date: Thu, 13 Jul 2000 11:50:57 +0200
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > It seems that it could be advantageous to first try the diverse
> > ideas out on a miniature version of DES to gain experiences of
> > which methods are the best.
>
> No, absolutely not -- I am tired of solutions for "toy problems"
> that do not scale. The whole point of the exercise was to develop
> a technique that would be effective against a large class of real-
> world cryptosystems. If one doesn't start out with that goal,
> most likely any simplified approach that didn't have to address the
> tough problems brought on by combinatorial explosion would not
> work when applied to the real problem where such matters pose
> the biggest part of the problem!
>
> The sketch I gave wasn't a set of diverse ideas; it was essentially
> all the steps one would use in that one particular method, except
> for specific techniques to use in tree reduction. The only
> diversity was that two methods were suggested for the final stage
> (iterative reestimation vs. gradient following).
Well, I am not quite sure in that issue, e.g. about the integer
optimization
techniques you mentioned. There is a plethora of methods for that but
none is the best, being dependent to some extent on the problems. One
has to experiment to gain experience. And experimenting on a small
model is cheaper. (At least it narrows down to a couple of candidates
from a bunch for further check with the full-scale work.)
M. K. Shen
------------------------------
Date: Thu, 13 Jul 2000 11:48:46 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: attack against CBC mode
Doug Kuhlman wrote:
> Umm...Bruce Schneier mentions this on pages 196-197. [...]
Damned, I really need that book... (yes I still have to buy it).
> And this should also answer Runu's question about why only 64-bit
> blocks. If you use 128-bit blocks, the chance of collision drops and
> you need about 2^{64} blocks, or about 16 quadrillion blocks, which is
> ... umm... ummm...more bytes than I know the right word for.
>
> Doug
Hmm ? I didn't asked why only 64-bit blocks ? This is a principial
problem which occurs with 128 bit and 256 bit and even with millions
and billions of bits, it is only becomes less probable the larger
the blocksize is.
That is the reason why I want to have a chaining mode where those
attacks are impossible.
------------------------------
Date: Thu, 13 Jul 2000 11:50:18 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: attack against CBC mode
Mok-Kong Shen wrote:
> > [CBC has a principial weakness]
> I recently proposed to use the square of sum of all previous plaintext
> and ciphertext blocks (addition mod 2^n) as chaining value. That's
> non-linear and should be safe against your attack, I suppose.
I think so, too.
------------------------------
Date: Thu, 13 Jul 2000 11:54:51 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Chaining mode discussion
Mark Wooding wrote:
> My main surprise is that this is considered new. I thought we knew that
> using n-bit block ciphers for more than 2^{n/2} blocks was a bad idea
> anyway, precisely because of such collisions.
Well, but the problem is always there, not only after 2**(n/2) blocks.
Its really a bad and principial property, and I think one should use
a different chaining mode to get rid of it.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Hadamard transform
Date: Thu, 13 Jul 2000 12:32:11 +0200
Simon Johnson wrote:
> What is a Pseudo Handarmard Transformation and its cryptographic
> signifiance?
See Schneier's AC, p.340. I don't know why the name is so called.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Hadamard transform
Date: Thu, 13 Jul 2000 12:32:17 +0200
Simon F wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > There exists 2-D Fourier transform. Does anyone have literature
> > pointer of an analogous 2-D Hadamard transform? Thanks in advance.
>
> In a texture compressor (for Dreamcast) I used Hadamard transforms to
> extract frequency information.
>
> Assuming that you have an n*n matrix of values, M, (where n is a power
> of 2), I just used:
>
> Result = 1/n^2 * (Hn * M * "Hn-transpose")
>
> where Hn is the n*n hadamard matrix. (Hn-transpose is actually just
> H)
>
> Just to check we aren't talking about different things, H is defined
> by...
>
> H1 = [1], and
>
> H2n=[Hn Hn]
> [Hn -Hn]
>
> The DC component ends up in the top left corner of matrix. I also wanted
> the frequency values sorted so that the frequency data increased from
> left to right and top to bottom. To get this, I had to re-order the rows
> and columns of H.
Suppose you stretch out your two dimensional data to become a one
dimensional sequence, would you get poorer or better informations
for your purpose? And why? Thanks.
M. K. Shen
------------------------------
Date: Thu, 13 Jul 2000 12:16:03 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: General Question on cryptography
DW wrote:
> one of the things that's always made me curious about cryptography
> is why can't someone develop a combination of algorithms that no
> one would ever think of in attacking encrypted data?
That idea is posted here on a regular basis all one or two months.
> Just to give you an example [...]
Not necessary.
> How would one attack data encrypted by such an algorithm?
No matter how complex you make an algorithm, you still can't be
sure that it is secure. And the trick is to make it both secure
and fast.
> It seems like you need to have an idea of the algorithm used and maybe
> even the order, and I don't see how one would guess this?
You always know the algorithms, and you always have an idea
what the plaintext should be. That is the practice. Anything
based on weaker assumptions is not of interest.
> Can you attack it mathematically to decrypt it without discovering
> each algorithmic operation after many many several messages have
> been sent?
One can get the algorithm by disassembling the binary
excecutable. One can get the plaintexts by forcing the enemies
to send certain messages.
------------------------------
From: "Andrew Wong" <[EMAIL PROTECTED]>
Subject: Cryptographic Camouflage
Date: Thu, 13 Jul 2000 18:24:06 +0800
I recently came upon this product, called WebFort, developed by Arcot
Systems Inc., that uses cryptographic camouflage to secure keys in a
software container.
Pse advise if anyone has experience on this product and what are your
comments.
Regards,
Andrew
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Chaining mode discussion
Date: 13 Jul 2000 11:04:57 GMT
Runu Knips <[EMAIL PROTECTED]> wrote:
> Mark Wooding wrote:
> > My main surprise is that this is considered new. I thought we knew
> > that using n-bit block ciphers for more than 2^{n/2} blocks was a
> > bad idea anyway, precisely because of such collisions.
>
> Well, but the problem is always there, not only after 2**(n/2) blocks.
The attack works by finding collisions in ciphertext blocks. If we have
two ciphertext blocks C_i = C_j, then we know that
E_K(P_i \xor C_{i-1}) = E_K(P_j \xor C_{j-1})
Now because E_K is a permutation, we can decrypt both halves
P_i \xor C_{i-1} = P_j \xor C_{j-1}
and then rearrange to give
P_i \xor P_j = C_{i-1} \xor C_{j-1}
Note that the attack is dependent on finding a collision. Since (we
assume) the cipher itself behaves like a random permutation, we know
that for n-bit blocks we'll have a probability of 1/2 of a collision
after 2^{n/2} blocks.
Yes, we *might* get a collision well before the 2^{n/2} threshold, but
it's not very likely. The attacker *might* just guess the right key on
his third guess. We're only worried when collisions start to become
*probable*. And this problem is well known. See, for example, `A
concrete security treatment of symmetric encryption: Analysis of the DES
modes of operation' by Mihir Bellare, Anand Desai, Eron Jokipii and
Phillip Rogaway, which provides tight security bounds on the security of
CBC mode.
> Its really a bad and principial property, and I think one should use
> a different chaining mode to get rid of it.
I think that your response is due to a misunderstanding about the
significance and novelty of Vaudenay's result.
-- [mdw]
------------------------------
** 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
******************************
