Cryptography-Digest Digest #307, Volume #12 Sat, 29 Jul 00 01:13:00 EDT
Contents:
Re: substring reversal ("Douglas A. Gwyn")
Re: substring reversal ("Douglas A. Gwyn")
Re: generating S-boxes (Tim Tyler)
Re: Skipjack (CLSV)
Re: Another PURPLE Question (John Savard)
Re: Enigma with Transpostion (German Mechanisation) (John Savard)
Re: Enigma (John Savard)
Re: Enigma (James Pate Williams, Jr.)
Is Kong strong? (William Rowden)
Re: Encrypted Message Exchange - a variant of the interlock protocol (John Savard)
Re: Encrypted Message Exchange - a variant of the interlock protocol (John Savard)
Re: substring reversal (Jerry Coffin)
Re: Proving continued possession of a file (David Hopwood)
Re: Big Brother Is Reading Your E-Mail (John)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: substring reversal
Date: Fri, 28 Jul 2000 22:29:27 GMT
[EMAIL PROTECTED] wrote:
>
> How secure is a bitwise substring reversal-based cipher? The plaintext
> is divided into substrings of length k, where k is a number between 2
> and 17 (the next 4 bits of the key), and each substring is reversed,
> but the order of the substrings themselves is kept intact. Example:
>
> k=3
> plaintext= "The dog jumped over the fence."
> ciphertext="ehTod j gpmu deevot r ehnef.ec"
>
> If the length of the plaintext is not divisible by k, white space is
> simply added:
>
> k=7
> plaintext= "The dog jumped over the fence. "
> ciphertext="god ehTdepmuj t revo nef eh .ec"
>
> This substring reversal operation is done a hundred times or so, and to
> decrypt, the same thing is done, except the key is reversed. This is
> not vulnerable to the a simple character frequency attack, because the
> characters themselves are kept intact, only they are shuffled around.
> Are there any attacks that can be used to crack this?
>
> -- Vlad
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: substring reversal
Date: Fri, 28 Jul 2000 22:30:23 GMT
[EMAIL PROTECTED] wrote:
> Are there any attacks that can be used to crack this?
? It seems very easy to me.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: generating S-boxes
Reply-To: [EMAIL PROTECTED]
Date: Fri, 28 Jul 2000 23:16:05 GMT
Tom Anderson <[EMAIL PROTECTED]> wrote:
[Re: making small changes to existing permutations in an attempt to
"improve" them?]
: Are there transformations other than swaps that might work?
I believe there's been work involving taking existing permutations and
modifying them with simple linear permutations (and the like), with the
goal of retaining the non-linearity of the original box, but providing
key-dependant characteristics rapidly at runtime.
This work may be relevant to your query.
I believe related ideas are discussed in "Practical s-box design":
http://adonis.ee.queensu.ca:8000/sac/sac96/papers.html
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Destroy Microsoft.
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: Skipjack
Date: Sat, 29 Jul 2000 01:34:04 +0200
"Douglas A. Gwyn" wrote:
> "David A. Wagner" wrote:
> > Has anyone looked at the 256-element Skipjack S-box to see if it can
> > be expressed with less memory?
> As near as I can tell, you're essentially asking whether it is (non)
> random in Chaitin's sense.
Why refer to Chaitin? Randomness in algorithmic information
theory is useful as an absolute measure and not very applicable
in this context. Even if the NSA cryptographers have created
a random S-box for Skipjack they wouldn't be able to proof it.
Regards,
CLSV
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Another PURPLE Question
Date: Fri, 28 Jul 2000 23:48:24 GMT
On Fri, 28 Jul 2000 07:55:05 -0700, Charles Petersen
<[EMAIL PROTECTED]> wrote, in part:
>I'm not quite sure I understand. So did the PURPLE work by using a table
>of inverses? I don't really see this in the machine and thought perhaps it
>was just one way that it could be done today.
I'm sorry that I was not clear.
PURPLE sent the electricity through the other way; a computer
simulation, therefore, is forced to use inverse tables.
John Savard (teneerf <-)
Now Available! The Secret of the Web's Most Overused Style of Frames!
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Enigma with Transpostion (German Mechanisation)
Date: Fri, 28 Jul 2000 23:53:09 GMT
On Fri, 28 Jul 2000 14:53:39 GMT, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>John Savard wrote:
>> But on the other hand, not only would transposition afterwards have
>> vitiated attacks on the Enigma, ...
>The trouble with counterfactual hypotheticals is that history would
>have proceeded differently had they been true. If Enigma had not
>had a plugboard (which *is* a form of transposition), you could
>have said something similar: "... not only would a plugboard have
>vitiated attacks on the Enigma ..." Other attacks on Enigma would
>undoubtedly have been used under other circumstances.
If a plugboardless Enigma were used with a transposition that wasn't
varied by an indicator, yes, there might have been attacks that could
have been employed, although they would not only have been very
different from those used, they may well have been much more
difficult. And, I suppose that is reasonable: if transposition were
used, the plugboard would not have been thought necessary.
And while one could use a plugboard to transpose the bits of 26-bit
messages, calling it "a form of transposition" uses a definition that
most people do not accept, and one that will cause great confusion.
Given the idea of a message as an array of symbols, the Enigma
plugboard changed the values of symbols in the array, it did not move
them to other positions in the array. Of course, the values in an
S-box can themselves be thought of as subject to a transposition
(i.e., the Ohaver method) - but their action on the message is still
one of substitution.
John Savard (teneerf <-)
Now Available! The Secret of the Web's Most Overused Style of Frames!
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Enigma
Date: Fri, 28 Jul 2000 23:54:54 GMT
On Fri, 28 Jul 2000 19:17:06 GMT, [EMAIL PROTECTED] (James Pate
Williams, Jr.) wrote, in part:
>Mr. or Dr. Gillogly did you develop a chess playing program back in
>the 1970s that was described in a refereed journal article?
It's quite possible, as I believe he is the same Jim Gillogly that
first ported Adventure to C.
John Savard (teneerf <-)
Now Available! The Secret of the Web's Most Overused Style of Frames!
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Enigma
Date: Sat, 29 Jul 2000 00:36:55 GMT
On Fri, 28 Jul 2000 20:27:42 +0000, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>"James Pate Williams, Jr." wrote:
>> Mr. or Dr. Gillogly did you develop a chess playing program back in
>> the 1970s that was described in a refereed journal article?
>
>Yes, the Technology Chess Program, designed to demonstrate that Shannon
>was wrong in suggesting that Type A (i.e. brute force) programs could
>not compete successfully with more intelligent ones. It was described
>in a paper of the same name in the journal Artificial Intelligence
>(Vol 3, Jan 1972), and in more detail in my doctoral disseratation
>(Carnegie-Mellon Univ 1978: Performance Analysis of the Technology
>Chess Program).
>
>It's almost relevant to sci.crypt, in that Bletchley Park screened
>puzzle solvers, chess players and musicians to try to locate people
>with cryppie potential.
>
>--
> Jim Gillogly
> Sterday, 5 Wedmath S.R. 2000, 20:13
> 12.19.7.7.9, 10 Muluc 12 Xul, Fifth Lord of Night
Chinook, the world champion checkers program, and Deep Blue, the world
champion chess program are both described in the literature as brute
force game playing programs. How large an opening book and closing
book did the Technology Chess Program possess? What sort of an
evaluation function did it use? Sorry for not looking up the journal
reference, but I will not be within walking distance of an academic
library until next Wednesday.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED] (William Rowden)
Subject: Is Kong strong?
Date: 29 Jul 2000 01:16:47 GMT
Has there been any external peer review of Crypto Kong
(http://www.jim.com/jamesd/Kong)? I'd like to see that, so I'm asking
those who post to sci.crypt for their opinion. What is the best known
attack on the algorithms? Has anyone looked at the source code for
the implementation?
I became interested after seeing "--digsig" signatures on a mailing
list recently. Kong appears to be an easy-to-use digital signature
system (that can also do encryption). Using ECC, it has a smaller key
size than RSA (or whatever we'll call it when the patent expires), and
consequently it includes the public key in the signature.
I searched the sci.crypt archives for a thread on Kong, but didn't
find one. The search was complicated somewhat by posts from
M. K. Shen. :-)
If no known attack on Kong is better than brute force (or if those
attacks take a long time), I might recommend it to friends who are
reluctant to use something as "complicated" as PGP. Now that
"electronic" signatures are binding in the US, it would be nice if
*digital* signatures became more common. I'm afraid of a
proliferation of "Click Here to Agree" buttons. That's another topic,
however.
--
-William
NEW key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2001-02-01
Fingerprint: B6E5 9732 3464 97C8 2B70 A031 6BF6 9E5C 16B5 C400
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Encrypted Message Exchange - a variant of the interlock protocol
Date: Sat, 29 Jul 2000 01:12:37 GMT
On Fri, 28 Jul 2000 08:57:30 -0600, John Myre <[EMAIL PROTECTED]>
wrote, in part:
>A seems gullible, to me. He's only talking to M. And B is only
>slightly less so: maybe msgA is actually something unique to A.
>(Or rather, was.)
I noted that what I suggested, in the longer form, had all the
limitations of the interlock protocol: it depends on the contents of
the messages whose decoding is delayed being unmistakably original to
the expected sender. (That appears to be what you've shown, but I
could be wrong.)
The shorter form is subject to a more devastating critique: instead of
exchanging a secret key after the fact, why not just authenticate
public keys by exchanging their hashes by hand?
John Savard (teneerf <-)
Now Available! The Secret of the Web's Most Overused Style of Frames!
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Encrypted Message Exchange - a variant of the interlock protocol
Date: Sat, 29 Jul 2000 01:17:57 GMT
On Fri, 28 Jul 2000 08:57:30 -0600, John Myre <[EMAIL PROTECTED]>
wrote, in part:
>Let chkA be the checksum of the message above, and define ackA as the
>acknowledgement. Now M responds as if he is B:
The whole point of any variant of the interlock protocol is that the
messages being exchanged do not contain secret information: but they
serve to authenticate the parties through the exchange of other
secrets known to them (events commonly witnessed, past conversations),
and thus A authenticates B because the plaintext of messages from B is
unmistakably from B, and vice versa.
Thus, this does prevent M from sending B's actual message to A -
hence, although A sends the key to A's message to M before having the
chance to verify B's identity, the protocol still fails, because A
ultimately recognizes M's public key as not being B's, and thus will
not use it in subsequent sensitive communications.
John Savard (teneerf <-)
Now Available! The Secret of the Web's Most Overused Style of Frames!
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: substring reversal
Date: Fri, 28 Jul 2000 19:45:50 -0600
In article <8lsipu$ses$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> How secure is a bitwise substring reversal-based cipher? The plaintext
> is divided into substrings of length k, where k is a number between 2
> and 17 (the next 4 bits of the key), and each substring is reversed,
> but the order of the substrings themselves is kept intact.
This ends up as a type of transposition cipher, though perhaps weaker
than most. Attacks have been known for a LONG time (e.g. in _Between
Silk and Cyanide_ the author describes solving them by hand while
sitting in a bathroom).
> This substring reversal operation is done a hundred times or so, and to
> decrypt, the same thing is done, except the key is reversed.
More rounds of transposition DOES improve security -- during WWII,
the usual was double transposition (i.e. two rounds) which could be
solved by hand quite a bit of the time. 100 rounds would undoubtedly
be hard to solve by hand, but no matter how many rounds you used, it
would be hard to imagine it being anywhere close to the strength of a
modern cipher.
> This is
> not vulnerable to the a simple character frequency attack, because the
> characters themselves are kept intact, only they are shuffled around.
> Are there any attacks that can be used to crack this?
Generally you'd look at digraph, trigraph, etc., frequencies instead.
You might want to look at the _Military Cryptanalysis_ books for some
guidance on how to attack transposition ciphers.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
Date: Sat, 29 Jul 2000 12:30:00 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Proving continued possession of a file
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Mark Wooding) wrote:
> > A while ago, I was asked to come up with some mechanism
> > whereby a server could ascertain whether a client, which
> > had previously transferred a particular file to the server,
> > still had a copy of that file itself.
[...]
> Alice and Bob both know the message M initially.
>
> Alice generates:
>
> p, q, c, k = randomly chosen
> n = p * q
> a = k * (M^(-1)) mod (p-1)(q-1)
> b = c^k mod n
>
> Alice publishes a signed file containing:
>
> n, a, b, c
> Alice and Bob's names, and the filename for M
>
> Alice can then forget everything. Now Victor (or anyone
> else) can verify that Bob truly has a copy of Alice's file.
> Victor generates:
>
> r = randomly chosen < n
> d = c^r mod n
>
> and gives d to Bob. Bob then calculates:
>
> e = d^M mod n
>
> and gives e to Victor. Finally, Victor checks that:
>
> e^a mod n == b^r mod n
>
> If they are equal, then Victor concludes that Bob truly has
> Alice's file.
Alice can store M mod (p-1)(q-1) instead of M (unless (p-1)(q-1) > M,
but that means the data needed to verify possession of a file is at
least as large as the file itself).
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOYLABzkCAxeYt5gVAQH9cwf/UwmJMDs5NORFx4N/v2RQDVIS1J990IoH
pLYiPbBlAHi1NJx6k66ois00npXBoEcs1aGMIylCTSxgxeezeqdIhRVJHIfRqIJC
WCsI7Sk9aJ7Np0d0ORInMrYFbet3DC8L+VnEMlUGe1HqjBGYdgOccCbxZ7/D571I
WY5s9y6k7Djo57YHAl6+2d8ZINRMkTOoFE64OtPLBEc5ZC2cK43XoIHRStcapFP3
s433q2AkEgajVghRYN8NW2bAuEQo+flwOPTzFZPaRRMyHixfkZGXxKg+M5t3FtGm
352xh+zEvyjkte9506CAOEOOEV1szFxvJHn90U8F+zINz1uZsLHY3w==
=WKIk
=====END PGP SIGNATURE=====
------------------------------
From: John <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.security.pgp
Subject: Re: Big Brother Is Reading Your E-Mail
Date: Fri, 28 Jul 2000 20:39:20 -0700
On Thu, 13 Jul 2000 16:21:38 -0400, jungle <[EMAIL PROTECTED]>
wrote:
>Samuel Hocevar wrote:
>> On Wed, 12 Jul 2000 23:44:08 -0400,
>> jungle <[EMAIL PROTECTED]> wrote:
>>
>> > > This program broke the PGP encryption in two minutes flat,
>> > > so you're not even safe with encryption.
>> >
>> > what program will broke PGP in 2 min flat ?
>>
>> If we told you, we'd have to kill you.
>
>I did not directed my question to you, but
>
Then tell me and come on and kill me! Big deal spout off and say
nothing you twerps
>-----BEGIN PGP MESSAGE-----
>hQBsA6GrOHZC9xe9AQL/blsYb5lD9DirhIa5cagH8sd57/HmXcHEmSlpvL6G30GA
>kLckpdN51TF3aAn3iIu5g1jhhtNE9WOL6ej9Vq2RrGaidyr90C70aqeihKDJ3j8g
>Ywe+PlHMNq2q5i/0J188pQGcHU//I+WXzPh1RhP5ouLK3eyUDsMCMO6mGxrpj76B
>EK/AGWnug1lZwYwE+x9LRb/rsMx285IQrWxr1VCdZZ/LH2qJ4nR1CMbIvQgt2ax4
>/LHaJ1UyA92gTVncnudd+PX/bx4SpdRRKPvMR9zV/5xOZhlzgrQp/D90TOzaetDy
>DNcjNg61TVlEg5K4s7e3rosMivNW9r7/8h1EpEYDZPNQhx6sxkULfSeb7u5DZoxP
>bTbi4xDciEaH/OznQUL0gcAIN70uf/YPP9MqkNszb4rLnremIahMUtKDFVQwZdpW
>9X/90lvOx+lVSichQQOXSiidxIGJarqnONXqWnDavPsVLTs3u/S4vnJYyo84p7ux
>yLvXXFBYtu/Rk0An/lXQ1HqqEAe4ZiWCjE7XTxEFNDwDjihAI7X/pRFInqV3gA8s
>gE/YYKFDXeXJQDS+aN27R+6akTDQ8jOXLQR0T86HpZ8FLdwvr/qBXC90DDkRqYxx
>HQ3f3W24fPrQ6oRVC1Zmoh8jwIfNx/J9cxUcvkfcb+XQ23oxTpgteWa5wIx/YA==
>=rcKe
>-----END PGP MESSAGE-----
>
>, you did read already in my encrypted message above ...
>
------------------------------
** 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
******************************
