Cryptography-Digest Digest #94, Volume #12 Fri, 23 Jun 00 13:13:00 EDT
Contents:
Re: Variability of chaining modes of block ciphers (Tim Tyler)
Re: does 3des use only keys? (Runu Knips)
Re: TEA-wmlscript question (Mark Wooding)
Re: Variability of chaining modes of block ciphers (Guy Macon)
Re: how to compare the securtity between ECC and RSA (DJohn37050)
Re: MD5 Expansion ("Scott Fluhrer")
Re: MD5 Expansion ("Scott Fluhrer")
Re: Variability of chaining modes of block ciphers (Mark Wooding)
Re: How encryption works (Simon Johnson)
Re: Try it. (John)
Re: how to compare the securtity between ECC and RSA (Roger Schlafly)
Re: breaking encryption - help! (James Felling)
Re: MD5 Expansion (Mark Wooding)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Reply-To: [EMAIL PROTECTED]
Date: Fri, 23 Jun 2000 15:10:23 GMT
Guy Macon <[EMAIL PROTECTED]> wrote:
: michael wrote:
:>I like the idea that you nassume that your attacker knows
:>everything except the plaintext and the key, and has more
:>resources and cleverness than you do. Limiting yourself to
:>improvements that still improve your security under this
:>standard seemms wiser than adding improvements that require
:>secrets algorithms, chaining methods, etc (unless the algorithm,
:>etc is selected by a part of the key not used elsewhere).
: Wow. Exactly what I wrote 2 days ago, right down to the typo!
: I guess great minds work alike...
You nassume that there was only one typo to copy - but there seemms to be
at least three - all of which have been faithfully reproduced! ;-)
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
Date: Fri, 23 Jun 2000 18:12:06 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: does 3des use only keys?
dexMilano wrote:
> I've found an implementation of 3DES using 2 times the 1st key and one
> time the second.
3DES is not really strictly defined. Some use it this, others that way.
And yes, one could use 3 different keys, but that useless because at
the moment 112 bits is as unbreakable as 168 bits.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: TEA-wmlscript question
Date: 23 Jun 2000 16:18:30 GMT
dexMilano <[EMAIL PROTECTED]> wrote:
> I've tried to implement TEA in wmlscript but I've found some problem to
> assign the Golden number delta (= 0x9e3779b9).
> In the wmlscript we have (signed) int a 32 bit so the range arrive to
> 7fffffff.
>
> The question is: Is there a way to create a golden number minor than
> 7fffffff?
Try -0x61c88647.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Variability of chaining modes of block ciphers
Date: 23 Jun 2000 12:25:30 EDT
Mok-Kong Shen wrote:
>Perhaps I may say my 'personal' opinion in using a cipher. I certainly
>attempt to select the BEST cipher available under all the constraints
>(economical etc.). Since I can't be entirely sure (may be due to my
>specific psychological weakness) of the strength of it (because on
>the one hand I don't have 100% trust on the crypto gurus and on
>the other hand my own crypto knowledge is meager), I'll look out
>for any practically available (and economically affordable)
>supplementary measures to enhance its strength, no matter how
>small these are. It may well be the case that my fear is unjustified,
>because the cipher I use is indeed absolutely strong, but adding
>these supplementary measures do help me to fall to sleep at
>night easier (placebo effect?). So they are at least worth that
>for me.
An excellent explanation of the psychology of many here (including me).
Clearly you are not saying that everyone should use supplementary measures
to enhance crypto strength, and just as clearly it's nobodies business if
you or I choose to do so, as long as we aren't pushing it as a universal
remedy to a real problem.
Here is the rub; for those of us with the described philosophy, the
possibility that one of our attempts to enhance security may actually
decrease it is poison to the whole concept. The chances of our tweaks
actually increasing security are really, really, small and are easily
wiped out by even a slight chance that what we do is counterproductive.
Thus the argument of picking a strong cipher and doing nothing else
has considerable merit.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: how to compare the securtity between ECC and RSA
Date: 23 Jun 2000 16:31:56 GMT
My understanding is that in complexity theory SPACE is less of a constraint
than TIME. That is, P-SPACE can solve more problems than P-TIME, etc. My
point is simply a symmetric algorithm is broken by TIME and does not need much
space. This maps quite well into methods that attack asymmetric algorithms
that are based on TIME, such as Pollard rho variants, that also do not need
much space.
The mapping to asymmetric attack methods that currently need SPACE is more
problematic. One valid choice is to ignore the SPACE requirements and just use
TIME of the attack. This is a conservative choice. It allows the space
requirements to become very small due to algorithm improvements and the
analysis will still hold up. It also allows a straightforward mapping.
Another choice is to try to factor SPACE into the mapping. This is more
problematic and is subject to more assumptions.
Don Johnson
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: MD5 Expansion
Date: Fri, 23 Jun 2000 09:20:58 -0700
Simon Johnson <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
> >
> >Simon Johnson <[EMAIL PROTECTED]> wrote
> in message
> >news:[EMAIL PROTECTED]...
> >> Good point.......
> >> I'll revise my suggestion:
> >>
> >> Divide the message into two parts,a,b. do this by taking the
> >> first character and appending it to a, the second character
> and
> >> appending it to b, the third character and append this to a,
> the
> >> forth character and append it to b. And so on and so
> fourth.....
> >>
> >> Then:
> >>
> >> Output = h(a) & h(b)
> >>
> >> This should now be secure enough, with a 128-bit birthday
> attack.
> >Not particularly. Suppose you know M != M' such that h(M) == h
> (M'). If h
> >has a 128 bit output, this takes no more than O(2**64) work
> >
> >Then, consider the function f(X) that takes a message X, and
> replaces each
> >character with two of that same character. For example,
> > f( "I am a message" ) = "II aamm aa mmeessssaaggee".
> >It is clear that f(M) != f(M')
> >
> >Then, if you apply your hashing mechanism to f(M), f(M'), then
> you'll find
> >the a=b=M, a'=b'=M', and so Output==Output', giving you a
> collison.
> >more than O(2**64) work.
>
> >For more fun, you can consider f's which interleave M and M',
> which gives
> >you more colisions.
>
> I can't see how this is correct.....
> Lets see where i'm wrong,
>
> 1.) treat A & B as two seperate messages...
I think I see your problem. You think the problem is: given a known message
M, find a message M' with the same hash. I was attacking the slightly
different (and easier) problem: find two messages M, M' that have the same
hash.
However, your problem can be attacked as well...
>
> 2.) We want to find A' such that H(A')=H(A)
Ok (and A'!=A). BTW: make the length of A' match the length of A
>
> 3.) We also want to find B' such that H(B') = H(B)
Unless we set B=B', which takes only O(1) effort.
Then, the hash of the original message is:
Output = h(A) & h(B)
And the hash of the new message is:
Output' = h(A') & h(B')
h(A)=h(A'), because we found A' with that property.
h(B)=h(B') because B=B'
And so the two hashes are identical, with you having to break MD5 only once.
BTW: I was under the impression that the strength of MD5 against this sort
of attack, finding a second message that had the same hash as a given one,
was believed to be O(2^128), as the birthday paradox does not apply.
However, your strategy of double hashing does not make it any stronger.
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: MD5 Expansion
Date: Fri, 23 Jun 2000 09:27:03 -0700
Mark Wooding <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> David Hopwood <[EMAIL PROTECTED]> wrote:
>
> >
> > Simon Johnson wrote:
> > >
> > > A much better way is to divide the message in two. Then hash
> > > each part individually and contatenate each hash.
> > >
> > > a = 1/2 of M
> > > b = other 1/2 of M
> > > Hash output = H(a) & H(B)
> >
> > No, this is a disastrous idea, because one half of the message can be
> > held constant in a collision attack. That means it is only as collision-
> > resistant as H.
> >
> > The modification with bytes of the message interleaved also doesn't
work,
> > because odd or even-numbered bytes can still be held constant.
>
> Indeed. Some more complicated mixing needs to be done. Let H be a hash
> function, and let K be a cipher. Let M = (a, b) be a message split into
> two halves (it doesn't really matter how). Compute:
>
> a' = E_{H(b)}(a)
> b' = E_{H(a)}(b)
>
> Then let the extended hash be
>
> H'(M) = H(a', b') || H(b', a')
>
> Any analysis? (Yes, it's much slower than just hashing the data twice.)
Find two messages x, y such that:
E_{H(x)}(x) = E_{H(y)}(y)
The birthday paradox should apply here. Then,
H'(x,x) = H'(y,y)
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Variability of chaining modes of block ciphers
Date: 23 Jun 2000 16:51:16 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Let me reiterate my points:
If you like. I'd like to see an answer to mine at some point, though.
I've snipped and reformatted your text here.
> 1. I showed that there are more than one chanining modes [...]
True and accepted.
> But if someone claims that CBC is the only best mode, then I do
> like to hear his supporting arguments.
Just to point out, my suggestion has been to keep life simple by just
choosing a single chaining mode in your protocol (or choosing it at the
same time as your cipher, if your protocol does that), rather than
fiddling about with loads of different modes.
I've mentioned my preference for CBC with stealing, which is based
primarily on the observation that it's `good enough' to avoid block
substitution attacks, and that the security should rest in the cipher
rather than the chaining mode. I'm much more interested that
implementators should just choose one mode they're happy with than
fiddle with all sorts of extra modes.
> 3. I argued that, even though exploitation of the variability in
> question amounts only to a couple of bits of increase of key
> space, it does have a good sense to do that in many situations,
> because
> switching to an algorithm that has greater key size, [...] may not
> be a viable option in certain environments, due to e.g.
> unavailability of the larger algorithms
Why would other algorithms be unavailable? It's not difficult to find
implementations of ciphers with `sufficiently large' key spaces. If the
environment is already that constrained, why are you likely to have
freedom to implement funny modes? And why can't you do something like
triple-encryption with the cipher you've already got?
> an improvement of a time factor of 2 or 3 may not be trivial in
> respect of the chance of opponent's success, either because his
> resource is already at the limit or because the usefulness of the
> information is time-limited.
I'd be extremely worried about making such fine estimates of my
adversary's capabilities.
> BTW, I don't understand why one belittles chances of getting small
> benefits.
For crypto, it's because (a) they're not very useful, and (b) we can
often get large benefits at pretty much the same cost.
> In other contexts, I know, for example, plenty of people who care
> much about the price differences among the supermarkets.
Indeed. That's because they don't have possibility (b) above: they
can't buy things lots cheaper, so they settle for buying things a little
cheaper. And possiblity (a) doesn't apply as much: the benefit is
measurable -- you save 5p per widget, say. In cryptography, the success
metric is binary: your message is secure, or someone read it, and for
increasing the difficulty for my adversary by a small amount to make a
difference to my expectation of success means that I've decided
extremely precisely what resources my adversary has to bring to bear on
the problem. And this doesn't happen very often.
-- [mdw]
------------------------------
Subject: Re: How encryption works
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Fri, 23 Jun 2000 09:59:25 -0700
Errrrr, Now i'm worried..........
Why?
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Try it.
From: John <[EMAIL PROTECTED]>
Date: Fri, 23 Jun 2000 10:03:08 -0700
[EMAIL PROTECTED] (Mark Wooding) wrote:
>John <[EMAIL PROTECTED]> wrote:
>
>> 1. Public availability, as you say, I think, won't guarantee
>> security,
>
>Indeed not. But if you have lots of people looking at your
system, it's
>more likely that one of them will notice and tell you (and,
possibly the
>rest of the world, but hey, you can't have everything).
Whereas if you
>keep the system a secret, you'll keep the `white hat' people
away, while
>the `black hat' people will be quite happy to reverse-engineer
your
>work, find holes in it, and exploit them rather than letting
you know.
>
>But I'm not sure I was talking about security itself. I think
I was
>talking about *trust* in security. I, as a potential consumer
of your
>security system, want to as sure as I can be that it will meet
my needs.
>If I know, for example, that it uses established cryptographic
>algorithms and protocols, and I can see a strong security
architecture,
>then this increases the level of trust I'm willing to give the
system.
>If it uses new, but public, cryptography protocols and other
components
>then at least I can analyse them, and get other people to
analyse them,
>and I might be willing to grant a limited amount of trust. But
if it's
>a secret black box, I can't trust it at all.
>
>> A better way to be sure if an algorithm/source code is
good/secure,
>> would be some courses in computer programming.
>
>Erm, no, not really. It's an absolute prerequisite that you
know what
>you're doing. But even the experts make mistakes. That's why
review is
>so important.
>
Yes, I agree. Any good computer scientist would not object to
review. It is common to have teams of programmers nowadays. Some
computer people still have the "cowboy mentality." They think
they can go it alone. Maybe 15-20 years ago, but things have
changed.
>> 2. I am confused, what part of the source would one get an
NDA
>> for? If you can't "protext" your encryption, the rest hardly
>> seems worth protecting.
>
>I don't know whether your `encryption' is symmetric or public-
key. It
>doesn't really matter: there are many established and
respectable free
>algorithms for both. There are symmetric ciphers such as
triple-DES,
>CAST, Blowfish and the AES algorithms such as Serpent, Rijndael
and
>Twofish. We have asymmetric algorithms such as ElGamal, DSA,
and (come
>September, or outside the USA) RSA, together with some elliptic
curve
>variants of these. I honestly don't think that, for general-
purpose
>use, you have much scope for improving on these significantly.
(You
>might be able to make more headway with a new public-key
scheme, but
>you're best off making that public so that it can be used in
protocols
>such as TLS.)
>
>-- [mdw]
>
>
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: how to compare the securtity between ECC and RSA
Date: Fri, 23 Jun 2000 10:06:32 -0700
DJohn37050 wrote:
> Roger says he would use a 410 bit DSA/DH key. ANSI X9 requires use of a 1024
> bit DSA/DH key. Roger is at one extreme, he picks that smallest size key that
> has not yet been broken.
I just don't happen to have any valuable secrets. Even if it were
possible to break 410 bit DSA/DH using 1000s of MIPS-years, it
wouldn't bother me if my secrets were not valuable enough for
anyone to expend the effort.
OTOH, for a bank moving around millions of dollars, 1024 bit
DSA/DH is a conservative choice.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: breaking encryption - help!
Date: Fri, 23 Jun 2000 12:02:38 -0500
First off, I believe that this is an XOR related cypher. Why? because the hex
for 'a' XOR 'w' = 39 hex XOR 2F.
The first character is always XORed with the hex value 58, and I will also
note that given the plaintext is identical up to a point the first character
after that divergence also has that property. This implies that the value
being this is of the form
F(previoustext) XOR present character. I haven't broken it, but I have not
really messed with it. play with it a bit -- try analyzing what the difference
between abaaaaa and aaaaaaa is that kind of thing.
Tim Tyler wrote:
> Steve Basford <[EMAIL PROTECTED]> wrote:
> : Andrew Carol <[EMAIL PROTECTED]> wrote:
>
> :>Yet notice the leading "www." DO match. Perhaps they are employing a
> :>carry from left to right between characters? Or some other feedback
> :>system between characters.
> :>
> :>Another thing to try to is use a web address such as "aaaaaaaaaa.com",
> :>"bbbbbbbbbb.com", and "cccccccccc.com" to see if there is a common
> :>change which would suggest a simple carry.
>
> : Okay, here you go...
>
> : 0E
> : 39 57 09 7D 19 0E F8 D4 AB 40 76 DE 33 B3 := aaaaaaaaaa.com
>
> : 0E
> : 3B F8 FF 99 91-B2 46 29 6A 65 6D E6 3D EA := bbbbbbbbbb.com
>
> : 0E
> : 3A 7D 7A C3 08 90 51 14 5B 16 44 A0 31 3B := cccccccccc.com
>
> Something obvious: the first characters in the cyphertext increase
> here as the plaintext characters are incremented.
>
> Presumably this will not work for all characters - since "w" was
> always mapped to 0x2F.
>
> It /looks/ like the first character can be extracted by compiling a table.
>
> This is what should probably be done first, and the table examined for
> any pattern.
>
> Then, hold the first character fixed (somewhere, anywhere), and do the
> same with the second character.
>
> Repeating this process may help to produce some illumination.
>
> Something else to try - try modifying single characters slightly and
> observing any regularities in the effect on the resulting (probably
> subsequent) cyphertext.
> --
> __________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
> |im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: MD5 Expansion
Date: 23 Jun 2000 17:09:25 GMT
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> Find two messages x, y such that:
>
> E_{H(x)}(x) = E_{H(y)}(y)
>
> The birthday paradox should apply here. Then,
Hmm. If x and y are very short then this probably isn't very
difficult. Good attack.
Let's fix this up hurriedly:
M = (a' || b')
K_a = H(00 || a)
K_b = H(01 || b)
a' = E_{K_b}(K_a || K_b || a)
b' = E_{K_a}(K_b || K_a || b)
H'(M) = H(00 || a' || b') || H(01 || b' || a')
The insertion of the constants into the hash preimages destroys the
symmetry Scott took advantage of. Putting the hashes into the
plaintexts for the encryptions makes them long enough that finding
collisions that way is probably not sensible.
-- [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
******************************
