Cryptography-Digest Digest #551, Volume #13 Thu, 25 Jan 01 23:13:01 EST
Contents:
Re: Fitting Dynamic Transposition into a Binary World (John Savard)
Re: How much of this group's discussion violates the DMCA (Mok-Kong Shen)
Re: Dynamic Transposition Revisited (long) (Mok-Kong Shen)
MIKE - alternative to SPEKE and PAK ("Michael Scott")
Re: Knots, knots, and more knots (Matthew Montchalin)
Re: Random stream testing. (long) ([EMAIL PROTECTED])
Re: Leo Marks dies ([EMAIL PROTECTED])
Re: unknown encryption algorithm ("Douglas A. Gwyn")
What do you do with broken crypto hardware? (Paul Rubin)
Re: Why Microsoft's Product Activation Stinks (zapzing)
Re: Fitting Dynamic Transposition into a Binary World (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Fitting Dynamic Transposition into a Binary World
Date: Thu, 25 Jan 2001 22:50:38 GMT
On Thu, 25 Jan 2001 22:28:38 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
in part:
>I doubt that substitution could be "just as good." Resolving that
>issue would seem to require a comparable alternative design which
>could be examined and compared.
But the specific point we disagree on, I think, is that "all possible
transpositions" are not, in my opinion, as good as "all possible
substitutions" of the whole block, so the fact that any substitution
design won't provide that is not a strike against substitution.
That's basically because "all possible transpositions" are not the
same thing as all possible substitutions over the set of balanced
blocks. This is a specific mathematical issue, and I'm puzzled why
it's not getting across.
What I have on my page at
http://home.ecn.ab.ca/~jsavard/crypto/co041205.htm
is just 'conceptual', and hence not completely specified, but then
neither is Dynamic Transposition (the stream cipher component isn't
fully defined). I can't remember the details now, but I wouldn't be
surprised if your original Dynamic Transposition design might have
even inspired it in part; I think I remember mentioning in an E-mail
to you, though, that I was thinking of using a block cipher as a
combiner simply as an alternative to Dynamic Substitution.
I can understand that interest in novel combiners is limited, but I
would have thought that even in the 'mainstream', combining a byte at
a time with byte-wide fixed S-boxes, sort of like a rotor machine,
would be popular to avoid the bit-flipping problem of the plain XOR
combiner.
My design at the URL given above, though, was more a tour-de-force
showing how a gigantic key could be used to some effect. (There is a
second design, which I consider more potentially practical, lower on
the page, but that isn't germane - even though _it_ uses
transposition...of key material.) Unlike Dynamic Transposition, which
is practical (if _unfashionable_), this is big, slow, and cumbersome.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: How much of this group's discussion violates the DMCA
Date: Fri, 26 Jan 2001 00:46:40 +0100
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > It might be of interest to recall in this connection that
> > decades ago there was once a (unrealized) suggestion that
> > editors of scientific journals voluntarily submit articles
> > about crypto, the publication of which could be of relevance
> > to national security, for preview by some institutions.
>
> Of course that raised the issue of what criteria would be
> used to judge the impact on national security. The intent
> of most of the proponents seemed to be to slow down the
> open development of the science, on the assumption that
> the national interest would benefit from reduced
> understanding slower employment of improved technology.
> That evidently begged the question of whether improving
> understanding and technology might be better for the
> nation and indeed for everybody.
It appears that this inherently difficult political issue
has at that time been 'practically' resolved not through
convincing logical arguments from the one side or the
other (for a unification of the opposite views would be
by nature barely possible) but through naturally arising
hard facts. For in the modern era there is a flux of people
across the boundaries between all nations. A citizen of one
country today may become one of another tomorrow. So keeping
certain national 'wealth' of scientific knowledge in a
'safe' to be protected by a sentiment of patriotism against
intrusion by competing foreign countries becomes an
increasingly unrealistic and fugitive goal. At the same
time the scientists themselves, partly due to the more
frequent contacts and understanding with one another and
partly due to their enhanced awareness of the necessity
of having scientific developments serving the purpose
of peace rather than war in the world, have developed
an increasingly stronger sense of internationalism and
coorperaton in their persuits. (As comparison, it may
be of interest to know that during WWII there was in
Germany a journal whose title, when translated, reads
'German Mathematics'.) Under such circumstances any
censorship, whether forced or voluntary (of the editors),
of manuscripts from independent scientists, is unlikely
to be effective. That's, I believe, why the suggestion I
mentioned previously was dropped soon after its conception.
Now that the internet has brought people all over the
world in a sense nearer and nearer together, any attempts
of restriction of scientific research, particularly in a
field like crypto, are in my conviction doomed to fail.
M. K. Shen
========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Fri, 26 Jan 2001 00:46:56 +0100
Terry Ritter wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> >[...]
> >Finally, I would like to say that part of the discussions
> >on your DT is not about its 'practical' security (i.e.
> >whether it is effectively unbreakable) but about whether
> >it could offer 'perfect' security (this is one of the
> >points that John Savard raised and doubted, if I understand
> >correctly).
>
> "Perfect secrecy" is the technical condition where every possible
> plaintext is equally likely to represent the ciphertext. This is the
> cipher as a Latin square. A "perfect" cipher is not vulnerable to
> brute force because traversing each possible plaintext will just
> produce every possible message.
>
> The bit-balancing, bit-permutation, and one-time use of each
> permutation in Dynamic Transposition allows one to argue that each
> block does in fact have the "perfect security" property in that sense.
> Moreover, since the permutation is not exposed -- even by
> known-plaintext -- the best attack would appear to be some form of
> brute force.
>
> In addition I would like to think that the tremendous reduction of
> information from stage to stage hides the imperfections which must
> exist at earlier stages.
>
> In a previous message, somebody suggested that I might be using two
> different definitions of "proof." I think that is the case, and I
> suspect it is common.
>
> In the first case, I want "proven secure" to be some sort of absolute
> mathematical statement about a cipher. I accept that the
> implementation would have to be validated to the theory in some way,
> which probably would require experimentation to complete the "proof"
> in practice. Still, such a "proof" would be an absolute statement
> about the security of the cipher per se. This is the type of proof we
> seek, but may never find.
>
> The other case is cryptographic proof as it functions today:
> Assumptions are made, and from those, conclusions drawn, all of which
> may bear on cryptographic strength. But usually there is no universal
> statement of strength which applies against any possible attack
> whatsoever. These are "security proofs" in the sense that they are
> mathematical proofs pertaining to security, but they are not a
> guarantee of overall strength.
>
> I see no reason why a "mechanistic" cipher like Dynamic Transposition
> cannot have numerous security proofs; which is to say, mathematical
> statements about various aspects of the cipher. These should fit
> right into the body of cryptography as it has grown over the past
> couple of decades.
>
> We might hope to express the difference between an ideal goal, and
> achieved practical reality, and then show that the difference tends
> toward zero as the size of some component is increased.
>
> We might be to follow the reduction of information from stage to
> stage, and describe that as increasing uncertainty with respect to the
> original value. In this way, we might be able to show that any
> information exposed by the cipher is simply insufficient to attack an
> earlier stage.
>
> Because the main strength of Dynamic Transposition lies in a single
> "arbitrary" permutation, it may be one of the cleanest possible
> mechanistic ciphers about which one might make mathematical
> statements.
My knowledge is too meager to enable me to offer more
points than I have already done. However, it is my
impression that your arguments todate somehow (I have
no definite idea of that) need strenthening, if DT is
to be accepted as on a par with the theoretical OTP
(which seems to be your goal), in particular by the
academics, assuming DT has in fact that property.
(Apology, if my open words are inappropriate in some
way.)
M. K. Shen
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: MIKE - alternative to SPEKE and PAK
Date: Fri, 26 Jan 2001 00:44:16 GMT
Some months ago I mentioned an idea I had concerning a new algorithm for a
low-entropy password-authenticated key-exchange, along the lines of SPEKE,
PAK and SRP. Tom Wu was kind enough to make a few comments.
I have since written up the idea in more detail - it may be found at
http://www.compapp.dcu.ie/CA_Working_Papers/wp00.html#1300
I have three questions
1. Has it been thought of before?
2. Are there any security problems with it that I haven't seen?
3. Are there any patents that apply?
It is not my intention to patent it - but I shouldn't give away what isn't
mine.
The method is rather like PAK. The main novel idea is the use of two
independent group generators. Its main advantage is that it works well in
any type of group (e.g. Elliptic Curves - unlike SRP), also it avoids the
sub-group membership problems that arise with SPEKE and PAK. In a common
context it is maybe 5 times faster.
Mike Scott
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Subject: Re: Knots, knots, and more knots
Date: Thu, 25 Jan 2001 16:59:53 -0800
On Thu, 25 Jan 2001, Richard Heathfield wrote:
|I must have misunderstood what you meant because, the way I figure it,
|this scheme would give maximum complexity (for a given, non-zero, series
|of operations on the punch card) to 11111111 and minimum complexity to
|00000000, whereas it seems to me that neither of these bitstreams is
|more complex than the other - they are separated only by a single NOT
|instruction.
Except we have to describe how those bits got there, from the previous
state. Thus, the punchcard, and what it dictates, is very important.
|Also, I'd argue that 10100111 is more complex than either of them.
Simple because the seed is completely black, or completely white,
does not prevent the machine from permutating it from one state
to the next state, until it has arrived at the target state. For
instance, from 00000000 to 10100111 and then to 11111111, we don't
know how many steps it takes to change the seed from one source
state to the desired target state. Again, I posted source code
that does just this, way back around June, modifying Joseph Rose's
original code so that it took something like 2^40 iterations
(I can't remember the exact number, we'd have to look it up) to
go from "light grey" $55,55,55,55,55,55 to dark grey $aa,aa,aa,aa,aa,aa
-- and then counted the number of iterations to go back to the first
seed again, completing a cycle. Since the seed was something like,
oh, perhaps 48 bits long, it was interesting that the iterations
necessary to repeat (or degrade) were on the average of two thirds
that number, about 40.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Random stream testing. (long)
Date: Fri, 26 Jan 2001 01:18:30 GMT
In article <[EMAIL PROTECTED]>,
"Paul Pires" <[EMAIL PROTECTED]> wrote:
> Well, I have what I think is a bizzare scheme for a PRNG and
> I just can't make it fail. Not even a little bit looking at
> gigabytes in every way I can think of. I'm searching for what
> to do now since I am still curious about it and more testing
> seems pointless.
Try reducing the size of the PRNG radically (use smaller arrays, smaller
words) and trying again. The flaws in scaled-down generators are the
same as the flaws in the full-scale generator, they're just more obvious
in the scaled-down one. The scaled-down generator has a shorter cycle
length too.
Use the gap test (how long does the sequence go before values repeat),
and make sure you test for all gaps up to four times the size of your
arrays (assuming you have arrays).
If you have arrays of length n, sample every nth result and run the
tests on that. Try again sampling n+1th results, and n+2ths, and
n-1ths.
If it helps, http://burtleburtle.net/bob/c/chi.c is a C program that can
do frequency, gap, run tests on terabytes of results generated on
the fly. Put your generator under "Experimental RNG -- put your RNG
here".
- Bob Jenkins
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Leo Marks dies
Date: Fri, 26 Jan 2001 01:55:18 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> On Tue, 23 Jan 2001 11:57:00 -0700, "David C. Barber"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Leo Marks WW II cryptographer died today.
>
> >http://www.theregister.co.uk/content/4/16308.html
>
> The article calls him a 'code cracker', rather than a code maker...and
> fails utterly to mention his recent book, "Between Silk and Cyanide".
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
>
True, but there's a link at the end to a more complete article in
The Telegraph.
-- Jeff Hill
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: unknown encryption algorithm
Date: Fri, 26 Jan 2001 02:38:38 GMT
[EMAIL PROTECTED] wrote:
> do you have a simple code for this vigenere?
No, I did it by hand. For example it is easy
enough to form the bitwise parity of the keys
and look for the same pattern or its complement
in the parity of the ciphertext. As I said, I
didn't find anything that way.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: What do you do with broken crypto hardware?
Date: 25 Jan 2001 18:47:35 -0800
I'm wondering if anyone else here is using crypto hardware modules for
key management. What do you do if one malfunctions? Throw it into a
blast furnace? Send it back to the manufacturer for warranty
repair/replacement, with your secret keys inside? Assume it's broken
badly enough that you can't program it to securely delete any internal
keys before sending it for service. You now either have to trash an
expensive piece of hardware, or decide to potentially compromise your
keys by sending the dead module to an outside vendor.
Besides users, do vendors have any policies about this? If I were a
vendor, I suppose I'd offer as a service option, sending a technician
out to verify non-functionality of the unit, followed by physically
disassembling it and removing the key storage elements and leaving
those elements with the customer, before taking the rest away. Of
course, getting the key storage parts out of a sealed module might not
be possible.
I haven't had any trouble with the modules I'm using, but would like
to know some typical policies people use, in case something happens.
Thanks
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,misc.survivalism
Subject: Re: Why Microsoft's Product Activation Stinks
Date: Fri, 26 Jan 2001 02:46:11 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
> In article <94lk6k$790$[EMAIL PROTECTED]>, zapzing
<[EMAIL PROTECTED]> wrote:
>
> > In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (wtshaw) wrote:
> > > In article <94i1dd$2nd$[EMAIL PROTECTED]>, zapzing
> > <[EMAIL PROTECTED]> wrote:
> > >
> > > > Void where prohibited by law.
> > > >
> > > Couldn't that get you in trouble?
> >
> > I don't think so, what do you think?
> > Do you have any info on this?
> >
> Voiding like praying is best done in private.
Oh, now I get it. Ha Ha :)
--
Void where prohibited by law.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Fitting Dynamic Transposition into a Binary World
Date: Fri, 26 Jan 2001 02:59:49 GMT
Terry Ritter wrote:
>
> On 24 Jan 2001 05:41:18 GMT, in <94lptu$[EMAIL PROTECTED]>, in
> sci.crypt [EMAIL PROTECTED] (Kenneth Almquist) wrote:
>
> >[...]
> >These algorithms can be executed moderately efficiently. The
> >combinatorial calculation used to determine the number of balanced
> >strings with a given prefix can be precomputed and stored in a
> >table. At the cost of using larger tables, we could make the
> >decoding algorithm process multiple bits of the balanced string
> >at a time. However, there is no obvious way to generate a balanced
> >string without doing one bit at a time.
>
> I simply do not understand where you guys are going with this.
>
> Is there some reason why you could not use the algorithm in my
> "revisited" article? It does bit-balance arbitrary data into a
> fixed-size block, is not limited in block size (and thus gains
> efficiency with large blocks), and decoding is trivial. Also, it does
> function byte-by-byte, not bit-by-bit.
There is indeed a reason not to use the algorithm in your "revisited"
article -- consider the case where we have a block of ciphertext, but
don't have a block of plaintext. We have some candidate keys gotten
somehow [presumably from analysis of other blocks; let's not worry about
how this might have been done], and we try decrypting this ciphertext
block with each of them. Your balancing scheme does not produce all
possible bit-balanced blocks. Like with many padding schemes, it is
easy to see upon trial decryption that a candidate key is incorrect
simply because it could not possibly have produced that [padded] block.
You might consider making it so that the contrasting byte is randomly
selected from among all bytes which have the appropriate number of bits,
but this now introduces a possible side channel (this is the same
problem as with using random padding to fill out the length of a stream
to be a multiple of a block cipher's blocksize).
To eliminate this problem, the decoding scheme should be bijective.
For the scheme I gave, this is true.
Ony might consider complaining that it is innefficient to work with one
bit at a time, rather than a byte at a time, but as has been said, the
bit manipulations of the cipher are a tiny fraction of the time
consumed, compared to the PRNG calls which create the transposition.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
** 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
******************************
