Cryptography-Digest Digest #467, Volume #13 Sun, 14 Jan 01 06:13:00 EST
Contents:
Re: Challenge/response with MD5 (David Schwartz)
Re: Yet another cipher idea (David Wagner)
Re: NSA and Linux Security (David Wagner)
64-bit/Solaris 8 DES crypt() source? ("The Zedi Warrior")
Re: The Word Problem and Group Isomorphism (MikeAt1140)
Re: Cavell Challenge #1 (Richard John Cavell)
Re: that security proof for ECDSA ?? (David A Molnar)
Re: The Word Problem and Group Isomorphism (David A Molnar)
Re: Cavell Challenge #1 (Richard Heathfield)
Re: Cavell Challenge #1 ("John A. Malley")
----------------------------------------------------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Challenge/response with MD5
Date: Sat, 13 Jan 2001 18:05:58 -0800
> Any opinions?
How many bits is the shared secret and how is it generated? This
information is necessary to analyze the security of the algorithm.
DS
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Yet another cipher idea
Date: 14 Jan 2001 02:22:40 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Benjamin Goldberg wrote:
>The concept: Make 8x8 matrix, and put one bit [of the plaintext]
>in each [row]. Encipher each row with a secure 8 bit PRP. Then
>transpose rows and columns.
>
>Three rounds are needed to prevent a MIM attack.
An interesting idea!
But at least 12 rounds (probably more) will be needed to defend
against differential cryptanalysis.
In the following differential characteristic, our two plaintexts
will differ by one bit, and after one round of encipherment, this
property will remain true. Note that this gives an iterative diff.
char., and it has probability 8/255.
Hence, iterating over 12 rounds gives probability (8/255) ~ 2^-60,
which is large enough to distinguish the cipher from a PRP.
You'll probably need to add a few extra rounds at the start and
end to defend against advanced diff. crypt. techniques, such as
use of structures and 1-R attacks and so on.
Also, you'll need to be sure that each of the PRP's in a round are
independent (they can't be the same, or there will be symmetry attacks,
I think), and that each round uses independent keys (they can't be
all the same, or there will be slide attacks).
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NSA and Linux Security
Date: 14 Jan 2001 02:49:40 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
John Myre wrote:
>Question: how could the NSA "prove" that it did *not*
>do something (wrong)? Moreover, how could it do so in
>such a way as to keep (some) secrets?
It's a fair question.
And I won't suggest it's an easy one.
But I do believe we can do much, much better than what we have today.
One possible answer might involves public,
independent, and credible oversight.
Unfortunately, much of today's oversight seems to operate in secret
(and hence is hard to verify whether it is doing any good; justice must
be public to be seen to be just).
Moreover, any independent investigation must be clueful enough to know
to ask the right questions (and I can cite many examples of failures in
this regard; if you're not very well-informed, you won't understand enough
to ask the right questions, and this can make meaningful oversight very
difficult [1]).
Do we have any oversight of this form today?
(If we do, we ought to find them some good publicists!)
[1] Let me give, by way of example, some "responses" to Echelon
allegations, "responses" which are supposed to address people's
concerns, but which instead indicate a complete failure to take the
allegation seriously and sound much like an attempt to pull the wool
over the eyes of the public.
Consider, for instance, the allegations that the NSA is engaged
in commercial intelligence and some US companies are benefitting
from the NSA's intelligence take. The denials are most interesting.
I've seen denials that say things like "the NSA is prohibited from
giving intelligence information to companies, and does not do so".
This is, apparently, supposed to reassure us.
But no mildly informed party would ever find this to be terribly
responsive. Those in the know have never suggested that a NSA official
directly approaches a company and offers intelligence; instead, the most
credible allegations suggest that such intelligence information is routed
to another agency (part of the White House? I can't remember), which
then makes the determination and hands over information as appropriate.
Does this really happen? I don't know. But the way the
allegation was handled should perhaps concern us more than the
substance of the allegation! Such "responses" feel highly deceptive.
(And this is supposed to inspire trust?)
And only if you have been following the issues
with care will you know enough to notice the evasions.
I could give plenty of other examples of this type of "reassurance".
They cause much more harm than the original allegation,
and they are all too common, in my opinion.
------------------------------
From: "The Zedi Warrior" <[EMAIL PROTECTED]>
Subject: 64-bit/Solaris 8 DES crypt() source?
Date: Sun, 14 Jan 2001 03:57:30 -0000
When I compile libdes-4.01 and libdes-4.04b with a target of v9 (64-bit
binary) under Solaris 8 with the Sun WorkStation Pro compiler, it fails the
"destest" verification routine.
Can anyone point me toward source for a fast DES-based crypt()
implementation which compiles properly as a 64-bit binary?
-Anthony
------------------------------
From: [EMAIL PROTECTED] (MikeAt1140)
Date: 14 Jan 2001 04:39:36 GMT
Subject: Re: The Word Problem and Group Isomorphism
David Wagner's points are well taken.
However this question has led to a recent thread of research. Some papers and
URL's are listed below.
1985:
N.R.Wagner and M.R.Magyarik,
"A public key cryptosystem based on the word problem",
Advances in Cryptology: Proceedings of Crypto 84,ed.G.R.Blakely and D.Chaum,
LNCS,196 Springer Verlag (1985) 19-36
(detailed discussion in W.Patterson,"Mathematical Cryptology" Rowman and
Littlefield
(1987) including a discussion of word problems).
1988
Do Long van,AJeyanthi,R.Siromoney and K.G.Subramanian,
"Public key cryptosystems based on word problems"
ICOMIDC Sym.Math.of Computation,Ho Chi Minh City April (1988)
( descibed in the monograph by N.Koblitz cited below)
1991
M.Garzon and Y.Zalcstein,
"The complexity of Grigorchuk groups with applications to cryptography",
Theoretical Computer Science 88:1(1991) 83-98
(additional discussion may be found in M.Garzon, "Models of Massive
Parallelism"
Springer-Verlag (1995))
1993
I. Anshel and M. Anshel,
"From the Post-Markov Theorem through Decision Problems to Public-Key
Cryptography", American Mathematical Monthly Vol.100, No. 9 (November 1993)
835-845.
1994
V.M.Sidel'nikov,M.A.Cherepenev and V,V Yashichenko,
"Systems of open distribution of keys on the basis of noncommutative
semigroups",
Russian. Acad. Sci. Dokl. Math. Vol.48 No.2 (1994) 384-386
1997
Rabi, Muhammad, and Alan T. Sherman,
``An observation on associative one-way functions in complexity theory,''
Information Processing Letters 64 (2) (1997) 239-244
1999
I. Anshel,M. Anshel,and D. Goldfeld,
"An Algebraic Method for Public-Key Cryptography",
Mathematical Research Letters 6 (1999) 1-5
http://www.msri.org/publications/ln/msri/2000/crypto/anshel/1/index.html
2000
K.H.Ko,S.J.Lee,J.H.Chean,J.W.Han,J.S.Kang,C.Park,
"New Public-Key Cryptosystem Using Braid Groups"
(presented at Crypto 2000)
[HT] J.Hughes and A.Tannenbaum
"Length-based attacks for certain group-based encryption rewriting systems",
preprint, 9/7/2000
[AAG] and [HT] are discussed in
[Gar] Paul Garrett, "Making,Breaking Codes:An Introduction to Cryptology",
Prentice Hall (2001) pp.183-187
and at http://www.math.umn.edu/~garrett/crypto/arithm.html
also see
http://www.tml.hut.fi/~helger/crypto/link/public/braid/
*****************************************
Professor Michael Anshel
Department of Computer Sciences R8/206
The City College of New York
New York,New York 10031
------------------------------
From: Richard John Cavell <[EMAIL PROTECTED]>
Subject: Re: Cavell Challenge #1
Date: Sun, 14 Jan 2001 15:51:49 +1100
On Sat, 13 Jan 2001, Richard Heathfield wrote:
> This is not rec.puzzles. Still, let's see just how far we can get
> without a key or an algorithm.
You haven't tried at all. Might I remind you that MI5 cracked Enigma
using mainly pen and paper and a little bit of perseverance. The code I
posted is hardly that complex. At some point, one must learn how to do
the simple codes on paper before building ginormous codecracking engines.
Yah, boo, sucks to you.
=============================================================
Richard Cavell - [EMAIL PROTECTED]
Newsgroups - Please keep any discussion on the group, and copy your
replies to me via email. (Server problems). Sending me bulk email
guarantees a nasty response.
Judge Thomas Penfield Jackson on Bill Gates: "He has a Napoleonic concept
of himself and his company, an arrogance that derives from power"
=============================================================
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: that security proof for ECDSA ??
Date: 14 Jan 2001 05:44:56 GMT
DJohn37050 <[EMAIL PROTECTED]> wrote:
> Nope that is not it. The only reason I have not mentioned it is the author has
> not yet publicly.
Ok, understood. I wasn't sure.
Thanks,
-David
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: The Word Problem and Group Isomorphism
Date: 14 Jan 2001 07:14:37 GMT
Ben Hopson <[EMAIL PROTECTED]> wrote:
> I realise that many group based systems have exhibited exactly the kind of
> patterns which are undesirable and wonder whether the freedom offered by
> semi-groups has been looked into in much depth.
This is interesting. Do you have any semigroups in mind?
The short answer is that I am aware of only a small bit of work on using
semi-groups for cryptography, as opposed to groups. This work has not, as far
as I know, led to a widely accepted cryptosystem.
(and indeed, why not deal with various groups? It has not been obvious that
using a semigroup gives us any advantage over using a group, and for whatever
reason there seem to be more number theorists than pure group theorists, much
less semi-group theorists, involved in cryptography. What semi-groups arise
from number theory? )
More depth:
Michael Anshel posted a short bibliography of work on cryptography following
from group theory and some semi-group theory in response to a similar question
I asked a few months ago. That's in the archives at
http://x70.deja.com/getdoc.xp?AN=692619668&CONTEXT=979453155.449839120&hitnum=0
or a deja search for "anshel molnar sci.crypt" will pull it up.
(I thank him again for the list, and regret that I haven't had time to look it
up. The paper on "Systems of open distribution of keys on the basis of
noncommutative semigroups" looks especially interesting.)
To this should be added recent work by S. Hahn, E. Lee, and J.H. Park of the
Korean Advanced Institute for Science and Technology, abstracted at
http://com2mac.postech.ac.kr/wshop6_abstract.htm#S. Hahn
Also of possible interest, though it deals with groups instead of semigroups,
might be S. Magliveras D.R. Stinson and Tran van Trung
"New Approaches to Designing Public Key Cryptosystems Using One-way Functions
and Trap-doors in Finite Groups"
http://www.cacr.math.uwaterloo.ca/~dstinson/papers/pkpgm.ps
Bach remarked in an invited talk at CRYPTO '88 that many examples exist in
which Diffie-Hellman key exchange works and asked what the limits of DH
might be. His words are worth reproducing:
"With such an abundance of examples, one might well ask how far the
genralization can be pushed. It seems that nothing about [Diffie-Hellman]
requires that the group be finite, or even that inverses be
computable; perhaps one could use semigroups instead of groups."
There is also work by Rivest and Sherman and later by Rabi and Sherman which
also gives insight into what properties may be required for a
cryptographic function. They show that a function * which is
1) associative,
2) one-way -- given x * y, hard to find x or y
3) "strong" one-way -- given x * y, and x, hard to find y
given x * y, and y, hard to find x
for a domain in which it's easy to sample random x and y can be used to
implement protocols for key exchange. If semigroup composition * for a
particular semigroup has these properties, then you're in very good shape.
For semigroup composition to have these properties, though, it must be the case
that the semigroup does not "embed" in some other group in such a way that
semigroup composition can be reversed feasibly. David Wagner has pointed out
that because matrices have a group structure, it seems any semigroup
expressible as nonsingular matrices will have this problem. Translate to
matrices, invert, and you reverse the composition.
Do we know anything about the class of semigroups whose elements are not
representable by nonsingular matrices? (does that question make proper sense?)
(and where would I go to learn more about such things?)
> I know from experience the difficulty in trying to enumerate the cosets of >
large groups, most of which can be generated by very few >
generators/relations. Even trying to determine whether a given group is >
trivial is a hard problem (in general undecidable, but in practice there are >
Todd-Coxeter stratergies which will yield a result eventually - but with >
provably no bound on time (or storage)). Similarly there are quick and dirty >
stratergies but these aren't even guarenteed to terminate.
As David Wagner pointed out, the fact that decryption must terminate (in
polynomial time), combined with the finite length of the ciphertext and finite
length of the key, means that the "brute forcing problem" is guaranteed to be
decidable. More than that, if you happen to guess the correct secret key, then
you can prove that you have the correct key in polynomial time by decrypting
the ciphertext and obtaining the plaintext.
Therefore the "key-cracking problem" is in NP. (The term is from an article by
Grollman and Selman on "Complexity Measures for Public-Key Cryptography" in a
1988 AMS symposium on computational complexity theory; they state it
differently than I have). This means it's not possible to base cryptography on
undecidable problems in the normal sense of "base."
Even so, undecidable problems may be useful if we can prove that some version
of the problem is NP-hard. I am not familiar with the area, but I did look
at Rotman's presentation in _Introduction to Combinatorial Group Theory_ of the
proof that the word problem for some groups is undecidable. As I recall, the
theorem went roughly like this.
1) Markov-Post theorem showing that a semigroup exists for which
the word problem is undecidable. This is the semigroup formed by
Turing machine transitions. (AKA "Syntactic Monoid")
So it's not surprising that its word problem is undecidable; you
fix it so that a particular sequence is the identity iff a
particular TM halts.
2) Embed this semi-group in a group.
3) Show that the embedding does not affect the proof of 1).
Now you have a group for which the word problem is undecidable. It seems that
if you reduce from TM computation, then you can reduce from polynomially
bounded TM computation, which would allow you to define an NP-hard subclass of
the general undecidable problem. I haven't worked it through, so it may be and
probably is wrong. After that, you have the fun task of justifying that the
instances you can generate are actually hard - as you've noted, heuristic means
seem to work "often." That can be embarassing for a cryptosystem.
Then the next task seems to be to define some kind of one-way function we can
use from the problem at hand. That's where looking at existing cryptosystems
based on group theory might be useful.
In any case, good luck with this...
thanks,
-David
------------------------------
Date: Sun, 14 Jan 2001 08:26:23 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Cavell Challenge #1
Richard John Cavell wrote:
>
> On Sat, 13 Jan 2001, Richard Heathfield wrote:
>
> > This is not rec.puzzles. Still, let's see just how far we can get
> > without a key or an algorithm.
>
> You haven't tried at all.
But I have. I have published the key and the algorithm. Fit the key and
the ciphertext into the algorithm, and out comes English plaintext.
Your problem is cooked, because it admits of more than one correct
answer (in fact, it admits of an infinite number of correct answers). I
have published one correct answer. It may not be the answer you thought
of, but it fits the puzzle (because that's what it is - just a puzzle)
perfectly.
This is not rec.puzzles. If you want people to have a fun time cracking
your stuff for the hell of it, rec.puzzles is the right newsgroup for
it.
> Might I remind you that MI5 cracked Enigma
> using mainly pen and paper and a little bit of perseverance.
The BP crowd, not MI5, cracked Enigma. They used pen, paper, IBM data
collation equipment, "bombes", a digital computer, some of the brightest
minds in mathematics, and several years.
> The code I posted is hardly that complex.
I agree. It's a simple one-time pad, to which I have published the key.
You cannot claim anything different until you publish the algorithm.
> At some point, one must learn how to do
> the simple codes on paper before building ginormous codecracking engines.
If you publish your algorithm, perhaps the experts here will help you to
cryptanalyse it. And perhaps they won't. You never can tell, with
experts.
> Yah, boo, sucks to you.
Ah. This would be some attempt at humour, would it?
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Cavell Challenge #1
Date: Sun, 14 Jan 2001 02:25:02 -0800
Richard John Cavell wrote:
>
[snip]
>
> Here's challenge #1:
>
> LZAKRUAHZWJRAKRESVWRTQRJGLSLAFYRLZWRSDHZSTWLRWAYZLRDWLLWJKRRBMDAMKRUSWKS
> JRAFNWFLWVRALRRARZSNWRMKWVRLZWRDWLLWJRRRLGRJWHJWKWFLRKHSUWKRRKWWRAXRQGMR
> USFRVWUGVWRLZAKREWKKSYWRR
>
Here is answer #1:
This cipher is made by rotating the alphabet eight letters Julius Caesar
invented it I have used the letter R to represent spaces see if you can
decode this message
John A. Malley
[EMAIL PROTECTED]
P.S. Frequency analysis revealed the ciphertext came from a substitution
cipher. The presence of spaces from the plaintext encoded as "r" skewed
the frequency profile for the English alphabet but I soon spotted it as
the decoding proceeded. I homed in on the repeated ciphertext "LZAK" and
identified it as "This" which is a probable word 'start' for a message.
And then the ball got rolling.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
