Cryptography-Digest Digest #66, Volume #11 Mon, 7 Feb 00 18:13:01 EST
Contents:
Re: NIST, AES at RSA conference (David Wagner)
Re: Random-Width Transposition Tables? ("r.e.s.")
Latin Squares (was Re: Reversibly combining two bytes?) (Michael Wojcik)
Re: Math contest winner from Ireland... ("Douglas A. Gwyn")
Re: NIST, AES at RSA conference (David Wagner)
Re: NIST, AES at RSA conference (David Wagner)
Re: Maybe a simple question ("Dave VanHorn")
Re: NIST, AES at RSA conference (Helger Lipmaa)
Re: Math contest winner from Ireland... (David Wagner)
Re: NIST, AES at RSA conference (David Wagner)
Here is some of my artwork ... you should always visit art galleries .. you never
know if you find some encryption (Markku J. Saarelainen)
Re: NSA opens up to US News (John Savard)
Re: NIST, AES at RSA conference (David Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NIST, AES at RSA conference
Date: 7 Feb 2000 14:14:56 -0800
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> I have never claimed that multi-ciphering will provide a proof of strength.
Ok.
But your line of reasoning did seem to go like this: (1) our ciphers are
not provably secure, hence (2) we need to triple them.
My claim is that the lack of provable security is largely irrelevant to
the question of whether to triple our ciphers. Our untripled ciphers aren't
provably secure, but then, neither are our tripled ciphers.
So let's go back to the basics. Why should we triple our ciphers again?
The right answer, I believe, is that we are unsatisfied with the security
of our untripled ciphers, *and* that we have reason to believe that adding
rounds (e.g., via tripling) will make them stronger. Agreed?
Now, if you agree with me so far, we're ready to address the last piece
of the puzzle: namely, the implicit claim that the best way to strengthen
our ciphers is to use diversity (multiple types of ciphers), rather than
just adding more rounds. And this implicit claim is not a priori obvious,
and while it may well be true, nonetheless, I haven't seen any reasoned
evidence for it so far.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Random-Width Transposition Tables?
Date: Mon, 7 Feb 2000 14:23:12 -0800
"wtshaw" <[EMAIL PROTECTED]> wrote
: "r.e.s." <[EMAIL PROTECTED]> wrote:
[...]
: > The case of a simple "row-wise fill" seems clear enough, but if more
: > complex transposition is used (e.g. "patterned fills" etc) it's not
: > so obvious to me. But if such cases do benefit from randomizing the
: > number of columns over a range [lo,hi], I still wonder how one might
: > go about determining the most advantageous values for lo & hi. (?)
: >
[...]
: In programong the encryption side, things are equivalent,
: when you are done you are done. However, decryption seems to require
: guessing column lengths, but if you know the key, there is no real
: guessing, so the same program will handle either situation.
[...]
OK, as far as the programming is concerned.
Because of the snipping that's been done, it may not be clear
that I'm trying to get some handle on criteria for selecting
lo & hi while *designing* a columnar transposition cipher
that randomizes the number of columns in the range [lo,hi].
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Michael Wojcik)
Subject: Latin Squares (was Re: Reversibly combining two bytes?)
Date: 7 Feb 2000 21:31:44 GMT
Reply-To: [EMAIL PROTECTED]
[We're talking about ways to generate Latin Squares, and treating
them as combining functions as suggested by Terry Ritter. Standard
disclaimer: I'm not a cryptographer, and am definitely not
recommending this method for anything more than experimentation.]
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> writes:
> In sci.crypt Michael Wojcik <[EMAIL PROTECTED]> wrote:
> : ... the proposed method (generating a square as a random
> : permutation of the rotations of a random permutation, then randomly
> : swapping rows and/or columns) will always generate a valid square.
> This method seems interesting - mainly due to its speed.
It also has advantages in storage requirements (see my earlier post
on the subject). We can keep an order-256 square as two or three
arrays of 256 bytes each (depending on whether we swap rows again
after generating the columns) with only a small lookup penalty,
rather than using the 64K required to maintain the entire square in
memory.
At least for encoding, that is. For decoding, this only works if we
can generate the inverse square in the same form.
More formally:
Generate a permutation P on {0..255} (the "primary permutation"), and
a second permutation R on {0..255} (the "rotation permutation"). Form
the columns of square S as follows: for each column c, 0<=c<=255, c
is rotate(P, R[c]). For c s.t. R[c] is 0, the column will be simply
P; for other columns, the first entry in the column will be P[R[c]],
the second P[R[c]+1 (mod 256)], etc.
The columns of the square will be a permutation on the set of all
distinct rotations of P.
Call a square constructed this way "PR-form". Call the set of all
squares constructed from the same P, but with different R, a "family"
of PR-form squares.
(If anyone prefers different notation, be my guest. I'm just making
this up as I go along. Also, note of course that we can swap "row"
and "column" throughout, since transposing a Latin Square yields a
valid square with similar properties.)
Having constructed a PR-form square, we can permute its rows and/or
columns and still have a valid square. Permuting rows just yields
another member of the same family - probably not a very interesting
result for cryptographic purposes (if any of this is). Permuting
rows, however, generally yields a square that is *not* in PR-form.
That third permutation we'll call T, for "third" or "transform"
(since it yields a square that is no longer in PR-form). Again, we
can represent T as an ordering of the set {0..255}.
Call a square of this soft "PRT-form".
Assuming we're using the squares as generalized combiners, in the
manner suggested by Terry Ritter - as a kind of extended XOR. For
each plaintext byte (since we're working with squares of order 256)
we mix plaintext and a byte of (expanded) key material, using one
to index the row and the other to index the column. For convenience
I'll assume the key byte selects the column.
As I noted in an earlier post, given three arrays P, R, and T, that's
a simple and cheap operation. We can even gain some cache locality
benefits by doing multiple passes over a block of plaintext rather
than indexing all three arrays for one byte of plaintext and then
moving on. (Of course, on modern general-purpose CPUs, it may not be
terribly hard to keep all three arrays in cache anyway.)
That's convenient for encoding. For decoding, though, we either have
to construct an inverse tree (such that indexing cyphertext and key
produces plaintext), or search the column indexed by the current key
byte for the cyphertext byte (then the position in the column is the
plaintext byte).
Searching is clearly suboptimal, since it adds an O(n) linear-
search time factor to the decoding process. It can still be done
with arrays P, R, and T, assuming the encoding square is in PRT-form.
(Or with arrays P and R if the encoding square is just PR-form.)
What we'd really like is to be able to easily generate the inverse
square S^-1, though, in PRT-form. (It won't be in PR-form in the
general case. As trivial pen-and-paper experimentation shows, the
inverse of a PR-form square of even order 4 isn't guaranteed to be
in PR-form itself. That is, its columns won't be rotations of one
another.)
Question: Is the inverse of a PRT-form square always itself a PRT-
form square? More generally, are all Latin Squares in PRT-form?
Is there a simple, low-cost construction procedure to derive the
inverse of a PRT-form square in PRT notation?
Note that if the answer to the second question is yes (all Latin
Squares are in PRT-form), then we can reduce any Latin Square of
order N to three arrays of N entries, which means that the internal
state of a square of order N is bounded by 3N, not by N^2. (Right?)
Ie., this result helps us specify how much information there really
is in a Latin Square, since it gives us a bijective compression
function for squares. (That tends to make me suspect the answer is
no, but a few minutes of head-scratching wasn't enough for me to
prove it one way or another.)
> It may be that the results will be systematically weak in some way,
> though. If I planned to use this, I'd generate some squares and test
> them with a stack of orthodox s-box criteria before doing much else.
Of course. There's also Terry Ritter's Boolean non-linearity
test for Latin Squares, which is very interesting; I plan on giving
that a try one of these days.
PRT-form squares may well be stronger (by these criteria) than simple
PR-form squares, since they don't have the column-rotation attribute,
which looks potentially troublesome.
If some PRT-squares could be identified as weak by a fast procedure,
the square generator could be sensitive to that and reject weak
squares. Assuming the permutations are generated by a PRNG seeded
with key material (the obvious protocol), we could in theory keep
generating new squares until we got a good one. Since the decoder
would be applying the same tests, it would arrive at the same square.
> : Whether that square is "strong" (are all squares equally strong, or
> : are some, say, easier to reconstruct from cyphertext?) is another
> : question.
> Squares are not all equally strong. Squares of the form...
>
> x(i,j) = (i+j) mod n, (i=1->n, j=1->n) would not do at all, for example.
Right. Another idea would be to use multiple rounds and chaining
to offset the possible weakness of one particular square. (Of
course, for an actual working cypher, I'd assume that square-
combining would be only one technique contributing to the encoding
process.)
We should also return to the question of changing squares during
encoding, as Terry Ritter suggested in another post. Generating a
new square is relatively expensive, but perhaps not prohibitive with
this method. If we're using square-combining in a block cypher, we
might advance to a new square on every block. With a stream cypher,
we might generate a new square after every so many bytes (how many
is an interesting question), or we might do so dynamically based on,
say, the key or plaintext (with the decoder examining output plain-
text to decide when to regenerate).
Of course, if there's a way to identify with some decent probablility
where in the cyphertext the square changed (perhaps with a chosen-
plaintext attack), then dynamically deciding when to change squares
based on the key may not be a good idea.
--
Michael Wojcik [EMAIL PROTECTED]
AAI Development, MERANT (block capitals are a company mandate)
Department of English, Miami University
Pseudoscientific Nonsense Quote o' the Day:
From the scientific standpoint, until these energies are directly
sensed by the evolving perceptions of the individual, via the right
brain, inner-conscious, intuitive faculties, scientists will never
grasp the true workings of the universe's ubiquitous computer system.
-- Noel Huntley
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Math contest winner from Ireland...
Date: Mon, 07 Feb 2000 22:23:15 GMT
Jean-Jacques Quisquater wrote:
> See http://www.counterpane.com/crypto-gram-9912.html
which includes the gem: "By breaking her own system, Flannery has
shown even more promise as a cryptographer."
I started to read Flannery's paper, but was stymied by such
things as the claim that the order of GL(2,Zn) cannot be
determined from knowledge of n alone. If somebody were to
translate it into mathematics, I'd take another look.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NIST, AES at RSA conference
Date: 7 Feb 2000 14:22:27 -0800
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> But we have a whole subset of people here for whom proof is
> everything, despite the fact that 50 of mathematical cryptography have
> yet to produce a proof of strength for any cipher in practice.
I'm not sure who was advocating that proof of security is everything.
I wasn't, but if you had intended to include me in that subset, I'd
personally want to respond something like this:
But sir, you yourself claimed that using multiple ciphers *provably*
strengthens them. Do you find it so surprising that I, for one, want
to see that proof (if indeed it exists), now that you've mentioned it?
But maybe you were referring to someone or something else.
> But these same people say things like "since we cannot prove any
> cipher, nothing we can do will provide such proof, so nothing is worth
> doing."
Well, yes, I agree, that would be silly logic.
Fortunately, it is not my logic, so I will let whoever made such silly
claims (if indeed anyone did) squirm in well-deserved discomfort.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NIST, AES at RSA conference
Date: 7 Feb 2000 14:31:53 -0800
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> Right. For provable added strength, the ciphers must not have
> "groupiness." [...]
But now we're getting at exactly my point.
You claimed that multi-ciphering provides *provable* added strength.
I asked for a proof of the claim. You said it should be obviously true.
I demurred, showing a counterexample ("groupiness") where it was false.
Now you seem to modify your original position, agreeing that my
counterexample is correct, and agreeing that the original claim must be
modified to specifically exclude this class of counterexamples -- but you
still give no proof of the claim.
I'm not trying to be hard on you, but I'm getting the impression that you
and I perhaps understand the word "proof" to mean two very different things.
A proof does not mean that you claim something to be true, and the burden
is on the reader to disprove it. A proof means that the burden is on you
to provide a reasoned, compelling, irrefutable argument [*] for your claim.
So far, you have not done so.
Yes, I really am truly interested in hearing proofs that multi-ciphering
increases strength. I think it would be a tremendous scientific advance
if one could prove such a result. I'm looking forward to seeing your proof.
-- David
[*] Ideally proofs should be formal and mathematical, but sometimes, for
ease of discussion, experienced parties to the discussion agree to drop that
requirement, when it introduces no confusion. In this case, where confusion
is apparently rampant, it is most important to be precise and accurate and
formal and rigorous; informal handwaving just won't do, especially when it
is not quite correct.
------------------------------
From: "Dave VanHorn" <[EMAIL PROTECTED]>
Subject: Re: Maybe a simple question
Date: Mon, 07 Feb 2000 22:35:10 GMT
> Here is a classic case, and I know from a participant that it was an
> actual case, where a number scheme was solved. LE frowned on the ability
> which was developed as part of a formal research project at an institution
> of higher learning to discover if the algorithm for generating credit card
> numbers, in that case, was any good...which it wasn't. They were more
> afraid that the fairly hollow scheme would be made available than
> punishing those that had learned more than they should have.
You mean the LUHN check algorithm? That's public (or at least so widely
known it might as well be)
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Tue, 08 Feb 2000 00:38:26 +0200
David Wagner wrote:
> But this line of reasoning still does not provide a satisfactory answer
> to Brian Olson's question: How do you know when to stop? If lack of proof
> were the only reason to triple a cipher, then there would be no end to the
> tripling. After all, tripling doesn't help one whit with the problem
> that we lack proofs -- there is no tripled cipher that we can prove secure,
> nor can we prove that tripling increases security even the slightest bit.
>
> In practice, I expect that the reason why we to triple ciphers is because
> of subjective concerns about the security of our ciphers, not because of
> the lack of proofs. (That's a fine reason, by the way -- but let's be clear
> about our reasons.) The lack of proofs, IMHO, seems to be a red herring.
There ARE proofs that say 'if cipher A is ideally good then the double cipher
AoA is even better'. There AREN'T general proofs saying that 'if cipher A has
strength f(x) against ciphertext-only attacks then AoA has strength f^2(x)'. To
illustrate the first claim, see the publication
[ABDV98] W. Aiello, M. Bellare, G. Di Crescenzo and R. Venkatesan. Security
amplification by composition: The case of doubly-iterated, ideal ciphers.
Extended abstract in
Advances in Cryptology- Crypto 98 Proceedings, Lecture Notes in Computer
Science Vol. 1462,
H. Krawczyk ed, Springer-Verlag, 1998.
[Note that they consider A to be a pseudo-random permutation, and both A's in
composition AoA to have independent keys]
To illustrate the second claim, consider e.g. cipher Akelarre, which has been
shown to be totally insecure independent of the number of the rounds! I.e., you
can even multiply the number of rounds by 100, but against certain types of
attacks the security of this cipher virtually remains the same. Also,
double-OTP with independent keys K1 and K2 is equal to OTP with key K1 XOR K1
(i.e., no increase in strength at all).
I guess David knows more examples than I do :-)
Helger Lipmaa
http://home.cyber.ee/helger
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Math contest winner from Ireland...
Date: 7 Feb 2000 14:37:41 -0800
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> I started to read Flannery's paper, but was stymied by such
> things as the claim that the order of GL(2,Zn) cannot be
> determined from knowledge of n alone. If somebody were to
> translate it into mathematics, I'd take another look.
Yeah, that's a small groaner (although not as bad as talking about
"factoring large prime numbers", I suppose, so at least she's doing better
than Gates and his ghostwriter). I presume what was meant was that the
order of GL(2,Z_n) can't be discovered without factoring n, and I'm pretty
sure that such a modified statement can indeed be rigorously proven.
(Just apply the standard result that finding a multiple of \phi(n)
enables one to factor n via probabilistic polytime reductions, noting
that |GL(2,Z_n)| is a multiple of \phi(n).)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NIST, AES at RSA conference
Date: 7 Feb 2000 14:46:39 -0800
In article <[EMAIL PROTECTED]>,
Helger Lipmaa <[EMAIL PROTECTED]> wrote:
> There ARE proofs that say 'if cipher A is ideally good then the double cipher
> AoA is even better'.
Right. Good point. I knew about that paper (and it is a nice one!), but
it had temporarily slipped my mind. Still, one must be careful when
interpreting their results, because the formal model is a bit
counterintuitive. In particular, their proof only applies to
information-theoretic model of security [*], not the usual model where we
take adversaries to be computationally-bounded and ignore attacks that are
infeasible (require too many computational resources).
> To illustrate the second claim, consider e.g. cipher Akelarre, which has been
> shown to be totally insecure independent of the number of the rounds!
> I.e., you
> can even multiply the number of rounds by 100, but against certain types of
> attacks the security of this cipher virtually remains the same.
A fascinating example! Thanks for bringing that to my attention.
Now does this feature of Akelarre rely on properties of the key schedule,
or would it remain even if one used truly random (independent) round subkeys?
Thanks,
-- David
[*] They use the Shannon model, where your cipher is a *totally* random
codebook -- as you say in one part (but seem to overlook later in your post,
although perhaps it is merely a typo), they don't have any comparable proofs
for the case where the cipher is a pseudorandom permutation, i.e., where the
cipher is merely taken to be indistinguishable from a Shannon cipher to
computationally-bounded attackers.
------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.cia.
Subject: Here is some of my artwork ... you should always visit art galleries .. you
never know if you find some encryption
Date: Mon, 07 Feb 2000 22:43:49 GMT
Here is some of my artwork ... you should always visit art galleries ..
you never know if you find some encryption
http://homestead.virtualjerusalem.com/waeg/files/art.gif
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NSA opens up to US News
Date: Mon, 07 Feb 2000 15:51:23 GMT
[EMAIL PROTECTED] (Dave Hazelwood) wrote, in part:
>http://www.usnews.com/usnews/issue/000214/nsa.htm
Does 000214 really mean that this article is from the February 14,
2000 issue of U.S. News and World Report? The February 7th issue just
arrived on a newsstand near me today.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NIST, AES at RSA conference
Date: 7 Feb 2000 15:02:31 -0800
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> This is the 3rd time I have tried to post this message...
Sorry to hear it. Thanks for retrying until it made it through.
> [EMAIL PROTECTED] (David Wagner) wrote:
> >I'll repeat my request for a proof, then...
>
> I think I have been more than forthcoming.
Well, correct me if I'm wrong, but I *still* haven't seen a proof...
> With respect to known-plaintext and defined-plaintext not being the
> easiest attacks, it is hard to imagine how having *less* information
> about a particular transformation (a keyed cipher) could possibly
> produce the *better* attack on that transformation.
==> "hard to imagine" does not a proof make!!! <==
> I suppose it
> might be possible for some other attack to have the same power, or
> even slightly less but practically the same, but I would like to see
> some examples.
But wait, you said you had a proof of the claim. Now you say you
suppose it is possible there might be cases where the claim was wrong.
Those two statements can't both be correct. Which is it?
> >> 1. If the current best attack on an individual cipher is some sort of
> >> known-plaintext or defined-plaintext (as is quite likely), and that
> >> attack is prevented by multi-ciphering, does that *not* increase the
> >> effective strength of the cipher?
> >
> >Yes, if there are no other attacks that are as good as the one prevented
>
> That was the assumption following my "if."
No, I think the two are different.
Let's make sure we're not misunderstanding each other here.
There is a crucial difference between considering "what if multi-ciphering
makes the best known-text attack harder?" and "what if multi-ciphering
makes _all_ known-text attacks harder?". Even if the former case were true,
the latter might not be, because there might be a number of different
known-text attacks with the same complexity.
And you still haven't presented any evidence to suggest that multi-ciphering
will make even the best known-text attack any harder, let alone the others.
> >No. It is not at all clear that this will increase the strength one whit.
> >See the previously posted counterexample, using XOR.
>
> First of all, XOR is not a cipher. [...]
Oh, come on, this is word-play. I didn't say the cipher
_was_ XOR, I just said it _used_ XOR to help you identify the counterexample
in the other postings, in case you had any trouble finding it. Let's not
be obtuse. I apologize if my brevity caused any confusion, but I think my
writing should have been clear enough.
Anyway, this is irrelevant. Let's move on...
> [...] Then, if the cipher in the so-called "counterexample" was intended to
> be a one-time pad, the only reason a second level does not increase
> strength is that there is no more strength left. But I find it hard
> to take any use of the OTP in these arguments very seriously.
>
> And if the cipher in the so-called "counterexample" was intended to be
> a stream cipher, the argument is simply faulty: Stream ciphers do
> not, in general, form a group.
>
> So the argument was lame, yet you insisted that it disproves my point.
But in case you don't like that counterexample -- even though it remains
a valid counterexample to your claim! -- there are also others that you
seem to be ignoring. E.g., Vigenere encryption with a totally random
alphabet (permutation of the letters). This is also a group, but you can
hardly say that "there is no more strength left" -- there is plenty of room
for improvement, but doubling or tripling this cipher simply does not
provide it.
Lame or not, I'll let you decide, but it as far as I can see, it still
disproves the original claim.
> OK, that's right. So we need to use ciphers which do not form a
> group. Please consider that assumption added to those following my
> "if."
>
> What percentage of ciphers would you say that leaves out?
Percentage doesn't matter. You claimed it was provable. A proof means it
is true for _all_ ciphers. Now you backpedal and say maybe it is not so,
maybe there are some ciphers where the claim doesn't hold.
Ok, so now we already have a few examples where it is not true; who is to say
how many more subtle examples there may be?
At this point, you do not seem to have any proof -- you just seem to have
handwaving that "it seems unlikely to you", and general hopes that someday
the claim might be proven. That's fine, but that's not a proof.
------------------------------
** 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
******************************
