Cryptography-Digest Digest #777, Volume #12 Tue, 26 Sep 00 07:13:00 EDT
Contents:
Re: Encryption Project (Bryan Olson)
Re: Tying Up Loose Ends - Correction (Tim Tyler)
Re: Tying Up Loose Ends - Correction (Tim Tyler)
Re: On block encrpytion processing with intermediate permutations (Mok-Kong Shen)
Re: On block encrpytion processing with intermediate permutations (Mok-Kong Shen)
Re: On block encrpytion processing with intermediate permutations (Mok-Kong Shen)
Re: Test for weak keys in 3DES (Tom St Denis)
Re: continuous functions and differential cryptanalysis (Tom St Denis)
Re: What make a cipher resistent to Differential Cryptanalysis? (Mok-Kong Shen)
Re: What make a cipher resistent to Differential Cryptanalysis? (Mok-Kong Shen)
Re: continuous functions and differential cryptanalysis (Mok-Kong Shen)
Re: On block encrpytion processing with intermediate permutations (Tom St Denis)
Re: "Secrets and Lies" at 50% off (Arturo)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Encryption Project
Date: Tue, 26 Sep 2000 08:44:22 GMT
Robert Hulme wrote:
> to be really sure the system is safe even if the NT box got
> cracked I want to encrypt the records in the database...
[...]
> In particular I wonder if people could help me with if this:
>
> a) makes any sense :0)
> b) has any glaring security holes
> c) what encryption I should use ?
If there are just a couple, mostly static fields to
protect it might be reasonable. If you want to let
users look up their recent transactions and such, then
you'll run into problems. For example, the database
isn't going be able to join a vendor record and a
customer transaction record if the vendor ID in the
transaction record is encrypted with the customer's
key.
Though the damage from a cracked system would be reduced,
it doesn't really go away. The cracker could cause the
system to collect passwords as users provide them. Also,
keeping the database current seems to imply keeping the
passwords around, unless you go to an even more
complicated public-key system.
You are not the first to have this problem, and I wish
I could offer a good solution. We certainly need better
security built into the foundation of our systems. I
think adding a custom encryption layer on top would set
you up for a maintenance nightmare.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Reply-To: [EMAIL PROTECTED]
Date: Tue, 26 Sep 2000 08:56:54 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Bryan Olson wrote:
:> : Yes, you can work on reducing that constant. The mistake is
:> : pretending it does something to the keyspace.
:>
:> It doesn't do anything to the keyspace. This was the point
:> of my attempts to distinguish the "effective keyspace"
:> from the actual keyspace.
:>
:> The "effective keyspace" contains the keys that can't be dismissed out
:> of hand on a priori grounds - and may need further consideration.
: The only attack you considered was exhaustive search. [...]
I was discussing rejecting keys. This is rarely useful if the only
attack available is brute force, due to the size of the keyspace. You
need something more than this for rejecting keys to be useful.
: Not one single key can be dismissed a priori. [...]
That may - or may not - be true, depending on how much known plaintext
is involved.
:> I've said if this is likely to rub people up the wrong
:> way then they are invited to present an alternative
:> concise way of saying operation X "reduces the effective
:> keyspace by five bits".
: The problem is the meaning, not the wording. I'd suggest
: "Makes testing each key faster most of the time."
Good - but still not very quantitive. It would have to be
"makes testing 31/32 keys faster, most of the time", in order to
play the same role as my sentence is intended for.
We /seem/ to be agreed on the meaning, the only question to my eyes is
that of the wording.
: [...]
:> : If I give you a thousand bits of Blowfish (448-bit key)
:> ciphertext and corresponding plaintext, what's the
:> "effective keyspace"?
:>
:> Probably very small, to the point of being practically non-existent.
:> The work required to reject each key is about as small as it can
:> ever be expected to be, and - in all liklihood - enough information is
:> supplied to be able to reject all but the correct key.
: So try your search. If you cannot search a "practically
: non-existent" "effective keyspace", then we have a good
: indication that your effective keyspace concept is
: misguided.
I don't see why a failed search would lead to such a conclusion.
"Effective" and "not-as-effective" are intended as relative terms. The
"ineffective keyspace" contains keys that are ineffective relative to
other keys. That doesn't necessarily imply that they're totally useless.
The difference beteen the keys /might/ be quite small, as in the examples
you're bringing up. However, it might also be gigantic. It's quite
possible that it takes hundreds of times more work to reject an
"effective" key than it does to reject an "ineffective" one. Under such
circumstances, the terminology would be more appropriate.
The issue of considering the keys en mass is a bit like pointing to a
strong crowd, and a weak crowd. Even if every individual in the strong
crowd is stronger than the strongest in the weak crowd, it doesn't mean
that the weak crowd can't apply significant force if everyone pushes at
once.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Florist: Petal pusher
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Reply-To: [EMAIL PROTECTED]
Date: Tue, 26 Sep 2000 09:08:48 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
:> : Tim Tyler wrote:
:> I was still wanting to talk about adding "arbitrary" lemngths of padding
:> - with the idea being to hide the location of the message, and to conceal
:> the length of the message as far as is possible.
[...]
:> : I don't think there is sufficient amount there for predicting the
:> : pseudo-random source of the padding [...]
:>
:> Ah, I was hypothesizing a genuinely random source, and asking what the
:> be way of using information from this as padding was, while retaining the
:> ability to distinguish the message from the padding.
: I am confused. Do you mean you append to some bit sequence
: certain number of genuinely random bits [...]
Yes.
: and ask whether the opponent can exactly identify these additional bits?
Not really.
I am trying to locate a method of adding the random bits in such a manner
that:
1) the recipient can unambiguously strip off the random padding;
2) the attacker is given the minimum opportunity to reject keys.
As an example of a scheme that fails the second criterion, imagine
the message as a prefixed size 64-bit field prepended to it, which
describes the length of the plaintext (anything after that is padding).
An attacker can reject huge numbers of keys by checking to see that the
MSB of the length field is 0000000 (and that the length field is shorter
than the entire message).
This method is dreadful. It adds lots of known plaintext to each
message.
I'm interested in a scheme that has a similar aim, but has the fewest
possible security-related side effects.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Hat: Baldness cure
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 12:20:17 +0200
Mok-Kong Shen wrote:
>
> What would interest me is the question whether employing
> permutation could in general be better than block chaining
> or not. If not, then the scheme would have no value.
In fact, however, word permutation is 'orthogonal' to block
chaining. So, if one doesn't mind the higher computing cost
and some more code, one can use both techniques. That is,
one applies a cycle of the block encryption algorithm to
the whole message with block chaining (of any type one
prefers, including non-linear ones), then permute the
words of the whole message, before starting the next cycle
of the block encryption algorithm and so on.
As said in the original post, the combination can also be
done at the level of interfaces of algorithms in case of
multiple encryption. For 3DES, for example, one can apply
the first DES module with block chaining to all blocks of
the message, then permute the words of the message, before
applying the next DES module in a similar way and so on.
One has then something like the inner chaining mode of
3DES, excepting that there are intermediate permutation
of words of the entire message.
It may be noted that, since we are processing the whole
message in a number of passes, we can, as a variation,
change the directions of the passes, i.e. some passes
are in the normal direction from begin to the end of the
message, while others are in the backward direction,
thus rendering through the block chaining different
results.
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 12:20:05 +0200
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > I don't think so. If the message is large, the number
> > of the parts a, b, etc. become large. In that case
> > the chance of a pair remain sticking together at the
> > same location should be lower. If a block consists of
> > 4 words instead of 2 words, there would be a similar
> > favourable effect.
>
> No, My point was that not all halves would affect each other DIRECTLY.
> That is optimum diffusion.
Certainly, since there are only m cycles but commonly
lots more halves (and words) in a message, it is
impossible that all halves (and words) of the message
have the chance to interact with all others through the
permutation operation during the time of the encryption
process. But there 'are' some interactions and these
are difficult for the opponent to exactly trace out.
That's the intended effect.
> >
> > What would interest me is the question whether employing
> > permutation could in general be better than block chaining
> > or not. If not, then the scheme would have no value.
> Ok Consider a 128-bit block cipher where I permute the 16 bytes then
> pass the clumps through a 16x16 sbox...
>
> There will be alot of weak permutes where the diffusion is not terribly
> high amongst all words.
You are considering the scaled-down case. That might be
indeed poor, if the original block algorithm is well
designed. But for the proper scheme (not the scaled-down
one) and considering, say, DES, in each cycle of the
common DES, one half-block is used to transform another,
and vice versa. If the effect of these transformations
are very good, it seems to be intuitively clear that it
shouldn't matter much if the 'transformer' of a particular
half-block comes from elsewhere in the message rather
than from the partner of the block as it happens to be
in the original sequence of the plaintext. Any weakening
due to change of partners are more than compensated
by the complexity introduced by the permutation, I
suppose. Techniques like differential analysis would be
confounded in their proceedings, I believe. (The
locations of the halves are constantly changing in ways
unknown to the opponent.) If the block is large, say,
of 4 words, and you fear that tearing apart the 2 words
making up one operational entity (i.e. one half) of the
Feistel cipher could be disadvantageous (presumably
because the design has been tuned to that), then you
could also permute, instead of words as I described,
group of 2 words to maintain the integrity of the halves.
> Also the PRNG must be reseed'ed for each block otherwise you have a
> stream cipher, not a block cipher.... not terribly usefull since
> seeking is a benefit of block ciphers.
There is no reseeding of the PRNG during the processing
of a message/session. If you like, you could call it a
combination of stream and block processing. I would
rather prefer the term 'huge' block processing. One can
consider the whole message as a virtual 'block'. There
are operations at that level and there are operations at
another level, namely the proper block operations,
during each cycle. (PRNG need not cause in mind
'association' with stream encryptions. You could think
that there is a key (the seed) that generates a set of
key-dependent permutations that are subsequently used.
Compare key-dependent S-boxes.) Does the appearance
of a novel (it isn't novel, I used such combinations of
processing techniques in my humble designs) form of
encryption as such trouble you? Why? I don't understand
your last phrase. In particular I can't figure out the
meaning of the word 'seeking' in the present context.
Could you explain a bit? Thanks.
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 12:20:12 +0200
Bryan Olson wrote:
>
> Tom is right; the diffusion is obviously terrible.
> Here's a first-cut at an attack strategy:
>
> In a typical Fiestel cipher one might have 16 rounds
> or 8 round-pairs. Let's use chosen messages of about a
> thousand blocks. We introduce differential pairs in
> which only one block input differs. There probably
> exists a left half-block for which any input
> differential survives to become an output differential.
> That happens if at each of the seven between-round
> permutations the differential goes into a left block
> and the right blocks are still constant.
>
> We can easilly detect the case when it happens; the
> differential put into the left half of input block
> 'i', appears as the differential comming out of the
> left half of ouput block 'j'. Now we can put
> differntial pairs into the right half of i, holding
> everything else constant, and the differential that
> comes out in the left half of j is exactly the
> differential from the right half of i going through
> the f function in the first round. For most Feistel
> ciphers that will expose the first round-key, and
> allow us to push to the next round.
>
> There are other opportunities to extract information
> based on the poor diffusion. As a rule of thumb,
> letting information out from intermediate rounds is
> extremely dangerous.
Suppose each half is a word (e.g. DES), the permutation
is rendering each one of them to go to a different
location that is unknown to the opponent. I don't yet
see how he can 'follow' the individual halves as they
get processed in the different cycles in order to be
able to exploit differentials etc. He has a moving
target, so to say, and the motion is invisible.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Test for weak keys in 3DES
Date: Tue, 26 Sep 2000 10:19:47 GMT
In article <8qpfgl$los$[EMAIL PROTECTED]>,
"kihdip" <[EMAIL PROTECTED]> wrote:
> In RFC2409 it is stated that you should test your key before use in a
DES
> CBC encryption, and be sure it is not a weak or semi-weak key.
>
> This is not mentioned for 3DES CBC encryption. Does it matter whether
you
> use weak keys in 3DES ??
I suggest you read sci.crypt posts, before posting yourself. This is
asked at least once a week.
You don't have to check because the probability of picking one is
about the same as spontaneously combusting while winning the lottery
and having aliens visit your neighbours.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: continuous functions and differential cryptanalysis
Date: Tue, 26 Sep 2000 10:18:19 GMT
In article <[EMAIL PROTECTED]>,
Paul Rubin <[EMAIL PROTECTED]> wrote:
> Tom St Denis <[EMAIL PROTECTED]> writes:
>
> > Woohoo I used calc for something.
> >
> > Theorem. No continuous [finite] function can ever have a minimum
> > Probability associated with a differential (over all possible
> > differentials).
> >
> > Lemma. Examine the derivative of function 1/x in GF(2)^n, given
as -
>
> Um, what's wrong with this sentence? Hint: do you know what a
> derivative is?
Um? Derivative is the slope of the tangent of a function at a given
point. I.e F(x) = 1/x, F'(x) = -1/x^2.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Tue, 26 Sep 2000 12:44:14 +0200
Tom St Denis wrote:
>
> Ah, but something can be pratically random. Take the output of say RC4
> that is hashed (gather 30 bytes then hash it via SHA-1, etc...) I would
> bet 10 bucks that without knowing the RC4 seed you couldn't guess the
> output better then 1/2.
>
> Make the RC4 seed 256 bits long ... and voila.
>
> Of course how do you make a random RC4 seed? recursive problem...
I am really confused. Aren't we discussing the 'ideal'
OTP that requires (theoretical) perfect randomness
all the time? Why here 'practical' randomness at all??
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Tue, 26 Sep 2000 12:50:29 +0200
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > Tom St Denis wrote:
> > > Then why reorder them?
> >
> > With reordered S-boxes, the algorithm is not identical
> > to the one with the standard ordering. So the opponent
> > does not 'exactly' know which algorithm he is dealing
> > with.
>
> True, but in DES you would have to use round independent swappings to
> make it worth while and it would slow it down considerably.
Certainly you have a trade-off. You have to consider
whether the trade-off is justified in the given security
environment. To get something useful, you always have
to pay something. (I only once in my life happened to
get a free beer. That's all.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: continuous functions and differential cryptanalysis
Date: Tue, 26 Sep 2000 12:54:03 +0200
Tom St Denis wrote:
>
> Paul Rubin <[EMAIL PROTECTED]> wrote:
> > Um, what's wrong with this sentence? Hint: do you know what a
> > derivative is?
>
> Um? Derivative is the slope of the tangent of a function at a given
> point. I.e F(x) = 1/x, F'(x) = -1/x^2.
I think he meant you are in a discrete field, not in R.
Do you actually have a reference for a definition
of derivative in GF? I am not quite sure.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 10:54:04 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > > I don't think so. If the message is large, the number
> > > of the parts a, b, etc. become large. In that case
> > > the chance of a pair remain sticking together at the
> > > same location should be lower. If a block consists of
> > > 4 words instead of 2 words, there would be a similar
> > > favourable effect.
> >
> > No, My point was that not all halves would affect each other
DIRECTLY.
> > That is optimum diffusion.
>
> Certainly, since there are only m cycles but commonly
> lots more halves (and words) in a message, it is
> impossible that all halves (and words) of the message
> have the chance to interact with all others through the
> permutation operation during the time of the encryption
> process. But there 'are' some interactions and these
> are difficult for the opponent to exactly trace out.
> That's the intended effect.
>
> > >
> > > What would interest me is the question whether employing
> > > permutation could in general be better than block chaining
> > > or not. If not, then the scheme would have no value.
>
> > Ok Consider a 128-bit block cipher where I permute the 16 bytes then
> > pass the clumps through a 16x16 sbox...
> >
> > There will be alot of weak permutes where the diffusion is not
terribly
> > high amongst all words.
>
> You are considering the scaled-down case. That might be
> indeed poor, if the original block algorithm is well
> designed. But for the proper scheme (not the scaled-down
> one) and considering, say, DES, in each cycle of the
> common DES, one half-block is used to transform another,
> and vice versa. If the effect of these transformations
> are very good, it seems to be intuitively clear that it
> shouldn't matter much if the 'transformer' of a particular
> half-block comes from elsewhere in the message rather
> than from the partner of the block as it happens to be
> in the original sequence of the plaintext. Any weakening
> due to change of partners are more than compensated
> by the complexity introduced by the permutation, I
> suppose. Techniques like differential analysis would be
> confounded in their proceedings, I believe. (The
> locations of the halves are constantly changing in ways
> unknown to the opponent.) If the block is large, say,
> of 4 words, and you fear that tearing apart the 2 words
> making up one operational entity (i.e. one half) of the
> Feistel cipher could be disadvantageous (presumably
> because the design has been tuned to that), then you
> could also permute, instead of words as I described,
> group of 2 words to maintain the integrity of the halves.
What's the diff between my 16-bit sbox example and your 64-bit sbox
(DES) example?
> > Also the PRNG must be reseed'ed for each block otherwise you have a
> > stream cipher, not a block cipher.... not terribly usefull since
> > seeking is a benefit of block ciphers.
>
> There is no reseeding of the PRNG during the processing
> of a message/session. If you like, you could call it a
> combination of stream and block processing. I would
> rather prefer the term 'huge' block processing. One can
> consider the whole message as a virtual 'block'. There
> are operations at that level and there are operations at
> another level, namely the proper block operations,
> during each cycle. (PRNG need not cause in mind
> 'association' with stream encryptions. You could think
> that there is a key (the seed) that generates a set of
> key-dependent permutations that are subsequently used.
> Compare key-dependent S-boxes.) Does the appearance
> of a novel (it isn't novel, I used such combinations of
> processing techniques in my humble designs) form of
> encryption as such trouble you? Why? I don't understand
> your last phrase. In particular I can't figure out the
> meaning of the word 'seeking' in the present context.
> Could you explain a bit? Thanks.
By seeking I mean if I want to read say an encrypted mp3 and seek to a
minute into it... I can't do that. This protocal is only good if the
entire file/msg is available at once to load and provided it's not too
big.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Crossposted-To: comp.security,comp.security.misc
Subject: Re: "Secrets and Lies" at 50% off
Date: Mon, 25 Sep 2000 08:20:17 GMT
On Sat, 16 Sep 2000 17:32:53 GMT, [EMAIL PROTECTED] (Menial Roky) wrote:
>Andrew Carol <[EMAIL PROTECTED]> wrote:
>
>>He does not have a history of simply popping in to shill books but
>>contributes enourmous amounts of useful information to this group.
>
>A good example is the frequent questions that we see here about the proper
>implementation of Blowfish and Twofish. Bruce Schneier is able to offer
>such helpful advice on these issues that you'd almost think he invented
>those algorithms himself!
Well, just in case you didn�t know by now, he DID invent them.
------------------------------
** 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
******************************
