Cryptography-Digest Digest #549, Volume #9 Fri, 14 May 99 02:13:03 EDT
Contents:
Toy Function (post didn't work) ([EMAIL PROTECTED])
Re: TwoDeck solution (but it ain't pretty) (David A Molnar)
Re: On Contextual Strength (John Savard)
Re: Thought question: why do public ciphers use only simple ops like shift and
XOR? (John Savard)
Re: Thought question: why do public ciphers use only simple ops like (Bryan Olson)
Re: Lemming and Lemur ([EMAIL PROTECTED])
Re: Lemming and Lemur: New Block and Stream Cipher ("Craig Clapp")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Toy Function (post didn't work)
Date: Fri, 14 May 1999 04:12:23 GMT
Obviously my first post didn't work..
Hmm I have a round function where
a, b 32 bits
+ addition (mod 2^32)
^ addition (mod 2)
S[1024] Array S-Box
R[32] Array of round keys
for r = 0 to rounds
A = A + (((B ^ R[2r]) * S[B >> 22]) ^ R[2r + 1])
(B,A) = (A,B)
next r
Where there are two permutations using round keys, and diffusion using
an sbox. The multiplication is to ensure a higher rate of diffusion
(while maintaining simplicity), and the shift is to use the more active
bits as indexes.
The diffusion is delayed by one round, but after about 16 rounds I
dunno if it matters. The average hamming distance is 31.93 bits after
16 rounds (comparing plaintext from decrypt cipher text with 'random'
keys). I used a blowfish style key schedule, which is heavily
dependant on the round function. I also used a R[32] and R[33] for
post white...
Anyways, this cipher may (and is most likely) weak, the point I am
trying to get to is....
Where would I start to analyze this? What could I poke at to exploit?
I just want pointers on how to start. I have allready implemented
this. And some empiracle testing (hamming distance),.
Any pointers?
Thanks,
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: TwoDeck solution (but it ain't pretty)
Date: 14 May 1999 04:09:18 GMT
[EMAIL PROTECTED] wrote:
>> This is not a question which an aspiring cryptographer should ask
>> after posting his phone number...
> Why not? They have to know where to send the money :)
combine digital cash with alt.anonymous.messages and a remailer network, and
we can get around that tiny little problem.
> Just kidding!!!!
-David
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: On Contextual Strength
Date: Fri, 14 May 1999 04:35:26 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote, in part:
>I want to reject ciphers if there exists a tractable break,
>without regard to whether an adversary may know or discover that
>break.
>No. I mean what I wrote.
I'd want to reject such ciphers too. However, I am helpless to reject
a cipher for which I do not know the break, or of the break - and my
adversaries are smarter than I am.
>If a cipher is strong under the idea I proposed, then _no_
>adversary can break it since a break does not exist.
So you do mean this.
And you are correct - that's a good definition of "strong".
But we don't know if tractable breaks exist that we don't know about.
We don't _even_ know if tractable breaks exist that we don't know
about, but our adversaries know about. We only know about the breaks
we know.
Terry Ritter asks us to consider the possibility our adversaries know
something we don't.
You are now saying that you believe in following an even higher
standard. I don't think he opposes this higher standard. What he
opposes is the *lower* standard of assuming a cipher is strong if we,
ourselves, don't know the break.
And that lower standard at least _appears_ to be the one followed in
practice by the conventional academic cryptographic community. Plus a
fudge factor - I tend to think this is unavoidable, even if it could
be made a little larger - but Mr. Ritter appears to be seeking to
reject that practice completely. Well, I think that even his
multi-cipher proposal is just a way of getting a bigger fudge factor -
but a _much_ bigger fudge factor without a correspondingly large
sacrifice of processing time.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Thought question: why do public ciphers use only simple ops like
shift and XOR?
Date: Fri, 14 May 1999 04:23:02 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote, in part:
>We *can't* build in "safety factors" if we don't know that anything is
>strong. We don't. You assume something which is not known. That is
>unlikely to be a good path toward a correct result.
Multiple encryption, and your method of using many different ciphers
at once, are ways of building in a safety factor, too.
Of course, if we don't know how weak conventional designs really are,
then if we make them bigger/more complicated, we don't know if the
result is really strong enough, as you are saying.
Since we need a "conventional" design to get the ball rolling even in
this kind of system (i.e., for initial key exchange, agreement on the
choice of ciphers, communicating which ciphers are currently to be
used) if it is _hopeless_ to rely on the security of a single-cipher
system, even if that single cipher is too slow and complicated for
regular use, it seems that the "why bother" argument comes back in
force. Ultimately, even with your multiple cipher scheme used in pure
form - say, for a fixed link, where the choice of ciphers etc. is all
arranged in advance by courier - we still have to cross our fingers
and assume *some* degree of strength for the ciphers being used; but
that does not mean that your scheme can't succeed in making that
assumption - even if still not _provable_ - a lot more plausible.
I certainly do think, too, that it is unfair to fault you for not
spelling out all the little details needed to make this general kind
of scheme workable: naturally, you want to be in a position to take
the credit for - and perhaps even patent and sell commercially - the
resulting system.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Thought question: why do public ciphers use only simple ops like
Date: Thu, 13 May 1999 22:17:55 -0700
Terry Ritter wrote:
> <[EMAIL PROTECTED]> wrote:
>
> >Terry Ritter wrote:
> >>
> >> Bryan Olson
> >> >[...]
> >> >Try to follow what people are saying. Without authentication,
> >> >adversary can influence the choice and _make_ the easiest
> >> >ciphers appear reasonably often.
> >>
> >> Since it is my proposal, *you* try to follow what *I* am saying:
> >
> >You jumped in after my reply to John Savard, and your comment
> >misunderstood the particular issue. Just because it started
> >with your suggestion doesn't mean you get to direct the
> >discussion.
>
> Alas, we all get to post whatever we want, not just what you imagine
> your particular discussion to be. Savard has only heard this second
> hand, just like you. So when you try to snow Savard and heap ridicule
> and abuse on what is essentially a fine proposal, you might expect the
> originator to jump in. I guess that may be inconvenient to your
> goals.
I was just pointing out that what you though was a correction was
not in fact so, since we were discussing a different issue.
> In particular, you are going into odd detail for a broad-stroke
> proposal, well beyond the issues, presumably in some desperate attempt
> to find faults not yet presented. My proposal addressed issues; this
> particular issue is the concept of changing ciphers, with the
> sub-issue of cipher-change negotiation, and your implication was that
> the whole concept was dead because you couldn't see how it could be
> secure.
Huh??? I wrote that the authentication on the cipher choice is
more important than its privacy. Where did I write that the
authentication couldn't be made secure?
> Will you now argue for the strength of a single cipher used in the
> normal way, as opposed to the strength of multi-ciphering and changing
> the cipher frequently? It will be satisfying to enshrine your words
> for posterity.
My words are on the record of already. From the beginning I stated
that there's a case to be made for (and against) multiple encryption.
I presented an argument against what I view as the a naive aspect of
your proposal - the per-message cipher choice from a very large pool.
> >> Authentication is an ordinary expected part of any cipher system.
> >> Secret key delivery is key authentication. Public key certification
> >> is key authentication. Plaintext hashing and message sequence
> >> numbers, both hidden under cipher, could be message authentication; or
> >> we could do something else. But none of this has much to do with
> >> cipher choice selection.
> >
> >Yes, once the difficulties are pointed out, you can describe
> >the needed authentication steps. You had claimed that for years
> >you've been calling for these cipher independent-protocols, but
> >when you tried to describe it, you seemed to speaking off the top
> >of your head and omitted not merely details, but essential security
> >points. Strange, since so much work is already done on such
> >protocols.
>
> There is a problem in discussing things with you, Bryan, because you
> don't seem to know the field and you don't know what is normal for
> cryptosystems. So you think any little problem you find is new meat,
> because nobody explicitly told you what we expect from a competent
> cryptosystem designer.
I don't think using block cipher encryption when one needs
authentication is competent cryptosystem design. For some time I've
been pointing out that block ciphers provide shoddy authentication.
The importance of this authentication is now a well known issue,
though it's perhaps best known as one of the mistakes in the design
of SSL, as Michael Weiner showed.
And again, I merely pointed out in a response to John Savard that
the authentication on the cipher selection is more important than its
privacy. Maybe you had already covered the authentication of the
choice in a post I had not seen, though the citation you offer
below doesn't.
> And then, instead of seeing your own
> ignorance, you seem to imply that I am dishonest.
Good strategy. Maybe people won't expose the faults in your
design if you heap enough derision on them when they do.
> Worse, you seem to be under some delusion that the purpose of finding
> problems in a design is to win some sort of "face" contest with the
> designer. That must be convenient for you, since I have yet to see a
> design which *you* have put out for others to kick around.
You've certainly seen me post designs to solve problems people
actually proposed. A few weeks ago someone asked about ciphers
where decryption is the same as encryption. I found a general
construction for which relative security is provable given a block
cipher.
I bring up this example because the technique is based on the one
I proposed in a response to you, when you wrote that generating
random single-cycle permutations is an interesting problem, and
one you had not seen addressed. At that time (10/9/97) I posted
a conjecture which I thought could be turned into a theorem (now
done, to appear). I guess you decided not to kick it around, but
_you_know_ that I post on-topic solutions that you can kick around
if you want.
I've never seen to point to most of the design contests here. Each
person can point out that the other can't prove security, and that
no one has broken his design (his current one anyway).
> Unless of
> course we count your supposed "break" of my Fenced DES cipher, which
> you wanted me and everyone else to accept as a mere claim, but which
> in fact did not work.
Hey you're the one who turns things into face contests. Before I
jumped in you were insinuating that respected cryptologists are
dishonest. Well that aint the way it is. And since you brought it
up, with your choice of cipher being part of the key, that means a
distinguisher recovers those key bits. So my Fenced DES attack,
which is at least a distinguisher for the cipher, is now a short-
cut solution when the cipher is used with the dynamic choice as
in the paper you cite below. If you don't want a face contest cut
out the e-tantrums.
> The proper role of cryptanalysis is to find design problems *so they
> can be fixed*. But you -- and many of your ilk on sci.crypt -- seem
> to think that fixing a design is dirty pool, an unfair contest for the
> poor cryptanalyst who then has no way to "win." For some of us the
> point of all this is to create real systems which are actually used.
AES is a real system that is destined to actually be used. How
many of these 1000 cipher systems have your customers installed?
Is that just because of all those dishonest cryptologists
deceiving people into not using your superior technology?
I seem to recall a couple years ago you wrote that it remained to
be seen whether your strategy of inventing and patenting ciphers
would be successful. Any clues yet?
> The proper role of cryptanalysis is to find design problems *so they
> can be fixed*. But you -- and many of your ilk on sci.crypt -- seem
> to think that fixing a design is dirty pool, an unfair contest for the
> poor cryptanalyst who then has no way to "win." For some of us the
> point of all this is to create real systems which are actually used.
> Cryptanalysis does not do that. And to the extent that cryptanalysis
> becomes fault-finding and gloating, it is part of the problem, not
> part of the solution. You are a prime example.
Temper temper. I came in with a very specific focused criticism,
which I believe is a sufficient basis on which to reject the
dynamic cipher choice. A couple other issues came up, but you
seemed to think I and others were arguing all sorts of other things
that we never said.
--Bryan
> Those who would like to see the origin of the current proposal can
> find that at:
>
> http://www.io.com/~ritter/NEWS4/LIMCRYPT.HTM
>
> Some of my comments from 1996 and earlier are at:
>
> http://www.io.com/~ritter/CRYPTWAR.HTM
>
> which also links to my early 1996 comments on negotiated cipher
> selection:
>
> http://www.imc.org/workshop/mail-archive/0233.html
>
> ---
> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Lemming and Lemur
Date: Fri, 14 May 1999 04:32:16 GMT
In article <7hfhkg$fmi$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> Dan Bernstein has pointed out in private email that there is an easy
> slide attack [1] on Lemming needing 2^64 known texts.
> Dan Bernstein has pointed out in private email that there is an
> easy slide attack [1] on Lemming needing 2^64 known texts.
It looks more like 2^68 to me, since (P,C) can't be part of a
useful slid pair unless P[0]=C[0]. In any case, Lemming is
clearly broken. I don't see how to extend this attack to Lemur,
which is interesting, since I had thought Lemur was less secure
than Lemming.
> (Dan Bernstein
> has apparently done some early, unpublished work on slide attacks,
> under the name of ``teleportation attacks.'') To defend against this,
> you need some round dependence in the round function: perhaps round
> counters (like in Skipjack), or round subkeys.
That clearly would stop this particular attack. I guess round
counters sound more appealing than subkeys, but this deserves more
thought.
> I'd like to make a second observation: I don't think Lemming has
enough
> rounds. There are truncated diff's of prob. 1 for each half of the
> cipher, which suggests that boomerang attacks (see esp. Section 7 of
[2])
> and miss-in-the-middle attacks (see [3]) might be a concern. I haven't
> done any detailed analysis, but someone should before using this
cipher.
I agree. I'll look at that.
> [1] Alex Biryukov and David Wagner, ``Slide attacks'', FSE'99.
> ~http://www.cs.berkeley.edu/~daw/papers/slide-fse99.ps
> <http://www.cs.berkeley.edu/daw/papers/slide-fse99.ps>
> [2] David Wagner, ``The boomerang attack'', FSE'99.
> ~http://www.cs.berkeley.edu/~daw/papers/boomerang-fse99.ps
> <http://www.cs.berkeley.edu/daw/papers/boomerang-fse99.ps>
> [3] Eli Biham, Alex Biryukov, and Adi Shamir, ``Miss in the
> middle attacks on IDEA, Khufu, and Khafre'', FSE'99.
Thanks, that's very helpful.
LCB
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: "Craig Clapp" <[EMAIL PROTECTED]>
Subject: Re: Lemming and Lemur: New Block and Stream Cipher
Date: Fri, 14 May 1999 01:31:47 -0400
[EMAIL PROTECTED] wrote in message <7hel5j$7fk$[EMAIL PROTECTED]>...
<snip>
>
>TO LEMMING ENCRYPT A BLOCK:
> for (i=0; i<32; i++)
> block = rotate(block ^ key[block[0]]);
>
For the form of key specified, the expression
block = rotate(block ^ key[block[0]])
is equivalent to the expression
block = shift(block) ^ rotate(key[block[0]]).
where shift() does the same as rotate() but without
the end-around action.
In this case the rotation can become part of the the key
schedule, or more conveniently you just build the key
with key[i][15] = perm[i]. Then the round function
needs only a shift rather than a rotate. On many
architectures the shift is more efficient than a rotate.
This form of S-Box was first proposed by David Wheeler
at the first Fast Software Encryption Workshop (1993) as
a component of WAKE's mixing function, albeit applied to
32-bit words rather than 128-bit blocks as you propose.
It was also adopted (with acknowledgement to Wheeler) by
W. G. Chambers in the paper 'Two Stream Ciphers' from the
same workshop.
>TO DECRYPT A BLOCK ENCRYPTED WITH LEMMING:
> for (i=0; i<32; i++) {
> block = backwardsRotate(block)
> block = block ^ inverseKey[block[0]]);
> }
>
>TO GENERATE A NEW KEY AND ITS INVERSE:
> perm[0..255] = random permutation of the bytes 0 to 255
> key[i][0] = i XOR perm[i]
> key[i][1..15] = 15 random bytes
> inversePerm[0...255] = the inverse of perm[0...255],
> inverseKey[i][0] = i XOR inversePerm[i]
> inverseKey[perm[i]][1...15] = key[i][1...15]
>
>In a previous post, the last line above had a typo.
>It had "i" instead of "perm[i]".
>
>In the pseudocode, rotate(block) rotates the block by
>8 bits so block[0] moves to block[1], and
>backwardsRotate(block) does the reverse. block[0] is
>the first byte of the 16-byte block. key[0...255][0...15]
>is the 4KB key, which would presumably be generated from
>a shorter key or passphrase.
>
>There's been a lot of discussion about the permutations.
>The key can be simplified by just using the identity
>permutation, which gives key[i][0]=0 for all i. That
>simplifies key generation. It might weaken the cipher,
>but I don't see any way to exploit that weakness right now.
>
>
>LCB
>[EMAIL PROTECTED]
>
------------------------------
** 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
******************************
