Cryptography-Digest Digest #942, Volume #13 Mon, 19 Mar 01 15:13:00 EST
Contents:
Re: Is SHA-1 Broken? (Mok-Kong Shen)
Re: My cypher system (Mok-Kong Shen)
Re: An extremely difficult (possibly original) cryptogram (daniel mcgrath)
Re: Algebraic 1024-bit block cipher ("Simon Johnson")
Re: OTP unbreakable? ("Douglas A. Gwyn")
Re: One-time Pad really unbreakable? ("Douglas A. Gwyn")
Re: How to eliminate redondancy? ("Douglas A. Gwyn")
Re: OTP unbreakable? ("Simon Johnson")
Re: Bacon's cryptography? (Frank Gerlach)
Re: hardwire prime & generator in Diffie-Hellman? (Mark Wooding)
Re: IP (David Schwartz)
Re: An extremely difficult (possibly original) cryptogram (Jim Gillogly)
Re: PGP key expiration (was Re: Encryption software) ("Joseph Ashwood")
Re: How to eliminate redondancy? (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Is SHA-1 Broken?
Date: Mon, 19 Mar 2001 19:08:50 +0100
Jim Steuert wrote:
>
[snip]
> However, a lot of us have been misled into thinking that SHA-1 was
> basically usable in any sense. Have I been too trusting of the
> "conventional wisdom" of cryptography? Of course we can use
> universal hashing/UMAC constructions, which require random
> number generators (which themselves are likely iterated ciphers
> or hash functions). The entire cryptography world is a LOT less secure
> in all areas given what Richard Dean has done, with a general
> package and general purpose slow hardware.
I guess, though, that those in practice who are prudent
have always been (a bit overly) conservative in respect of
security and don't get into pitfalls e.g. equating
'provable secure' (without explict mention of underlying
assumptions) and 'absolute secure'. An ancient Chinese
proverb says trusting everything that the books say is
worse than having no books at all.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: My cypher system
Date: Mon, 19 Mar 2001 20:04:55 +0100
bookburn wrote:
>
> This is a "what if" by a mere bumbler who looked at an encyclopedia
> article, so I expect to be shot down.
>
> My cipher system is basically a simple three-layered process using: 1)
> clear text; 2) use of a published text, like a page of a daily
> newspaper, which is chosen by a formula based on something variable
> like time and temperature of alternating cities on certain days, with
> identification of letters of the alphabet by numbered spaces in the
> text; 3) random use of the numbered spaces identifying letters of the
> alphabet, blank spaces, and punctuation, producing a long list of
> single numbers in bytes (spaces before and after set off numbers) ; 4)
> use of a mask to select only words in the clear text that are the
> message; 5) in addition, a key list of coded terms could be used to
> refer to some things.
>
> I'm basically thinking my system could be set up with computer
> programs at each end so that the long list of numbers can be instantly
> converted with the use of the same key text.
>
> Is this a workable cipher system? How could you ever break it?
> bookburn
Point (2) of using some contrived (uncommon, hence difficult
to guess) scheme to identify a piece of publically available
text for the purpose of deriving a shared secret is known.
How secure that is, is difficult to say in my view. (I would
vaguely say 'it depends'.) Points (3-5) are unclear to me.
Perhaps you could provide a tiny example to illustrate your
scheme.
I my humble view answering questions like your last one is
in general difficult. For breaking a given cipher (that
is susceptible to be broken by the current state of
knowledge) may often require much thoughts/intuitions and
experimentations/work/time. Thus it is always easy to put
up a challenge but hard to take it up. If nobody answers
that question of yours, it doesn't follow at all that your
cipher is strong. An analogy: In mathematics it is easy to
put up problems that are hard to get worked out. Some may
need much work to be solved, others may be not solvable
but the non-solvability is rather difficult to prove (e.g.
the trisection of an angle). But this is all opionions of
a humble non-expert like me. I don't exclude that some
experts would at once give a very easy break of your scheme
or prove the opposite.
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (daniel mcgrath)
Crossposted-To: rec.puzzles
Subject: Re: An extremely difficult (possibly original) cryptogram
Date: Mon, 19 Mar 2001 19:15:12 GMT
Jim Gillogly ([EMAIL PROTECTED]) wrote:
>daniel mcgrath wrote:
>>
>> On Thu, 15 Mar 2001 11:43:18 -0800, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>> >The first hint is consistent with my monome-dinome hypothesis, and the
>> >second hint could mean something like HTML.
>>
>> HTML it is. I thought at the time that telling you that would make it
>> too easy, but apparently you really want bigger hints.
>
>Certainly. As people (including me) keep saying, a very strong
>algorithm will still be strong even if everything except the key
>used for that message has been totally exposed. Even if you give
>away the plaintext to all but the last 10% of a message, this
>should give the cryptanalyst no help in decrypting the last 10%.
>A few people enjoy working on ciphertext-only challenges in unknown
>cipher systems, but for most that gets very old in a hurry.
>
>Just to add a little content, here's the sorted dictionary from
>this, gathered together from my hypotheses with Daniel's
>confirmations, and from the messages from Henk and Doug:
>
>> >6. Daniel gave a big clue, as follows:
>> >
>> > You came 620711143 close with 54006 of the 806648
>> > first hypotheses 711015 you had 450103. The code
>> > 696690137 used here, 27465680662, is based 7774
>> > the same 20650362042 idea as 71112 system used
>> > 1743 my cryptograms.
>
>for 1743 (probably)
>general 20650362042
>however 27465680662
>made 450103
>one 54006
>rather 620711143
>system 696690137
>that 711015
>the 71112
>upon 7774
>very 806648
All of the above equivalences are correct. So have you figured out
the system? (I think Douglas has it.)
>Note that pieces of words fit into this ordering: the "ther"
>from "rather" fits in well after "the", the end of "very"
>(either 6648 or 648) fits after "rather", "tem" may be 690137,
>the "ver" from "however" fits just before "very", and so on.
>Given enough of these, one could use one-part code methods
>even without recovering the actual algorithm used to create
>the codes. Assuming this property is representative of the
>actual messages, I'd expect exposing half of the plaintext
>to make it fairly straightforward to recover the other half.
>
>Note that this clue is illustrative only: it demonstrates
>the encoding idea without giving away the actual system.
>In particular, 71112 and the longer strings do not appear
>in the real challenge cryptograms.
==================================================
daniel g. mcgrath
a subscriber to _word ways: the journal of recreational linguistics_
http://www.wordways.com/
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Crossposted-To:
alt.computer.security,alt.security,alt.security.pgp,comp.security.misc,de.comp.security.firewall,de.comp.security.misc
Subject: Re: Algebraic 1024-bit block cipher
Date: Mon, 19 Mar 2001 19:22:20 -0800
Alexander Ernst <[EMAIL PROTECTED]> wrote in message
news:98supd$jrk$[EMAIL PROTECTED]...
> An objective of this cipher is to use
> pure finite group algebra for encryption and decryption.
> In this design we do not use permutations or XOR
> operations. Performance of this implementation is
> approximately 4,8 Mbyte/sec. Measured avalanche
> effect is 49,7%. Block size is 1024 bit or 128 bytes.
> Secret key length is 256 bytes. We use finite group
> of the order 65536. Elements of the group are words
> (2 bytes). So we call this word architecture.
hrm, 1024-bit blocks are not needed. To have a complete list of blocks, one
would have to obtain more matter then exists in the universe to build such a
drive. Brute-force searching a 256-byte keyspace would require more a few
hundred billion universes of energy.
Anyway, at 4.8 Megabytes a second, its not really fast enough. Any analysis
of your design?
Simon.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: OTP unbreakable?
Date: Mon, 19 Mar 2001 18:52:21 GMT
Tom St Denis wrote:
> Is the OTP really really really really really unbreakable?
> How many times are people gonna ask this.... ARRG
Probably about as many times as people are going to give
misleading answers about it.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Date: Mon, 19 Mar 2001 18:51:13 GMT
Tim Tyler wrote:
> One is that this is a study - of Douglas A. Gwyn - under computer
> simulation. An elaborate model of your intellect has been built, ...
Sophomoric philosophy, and intellectually destructive.
For somebody who lectures scientists about the conduct of science,
you don't appear to have made a serious study of the properties of
knowledge, how it is obtained and validated, etc. If you had, the
utter lack of evidence for the theory you put forth would rule it
out of consideration.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Mon, 19 Mar 2001 18:57:53 GMT
Benjamin Goldberg wrote:
> If a transformation is simultaneously one to one and onto,
> then it is a bijection.
What confuses things here is that D.Scott's notion of bijection
forces an essentially infinite domain; it's not just N-bit onto
N-bit but N-bit onto M-bit. And by the pigeonhole principle,
if M < N for some inputs (fixed N) then M > N for other inputs.
While it is possible that a compression transformation might
generate (by iteration over all inputs) a proper subset of the
infinite universe, it seems more likely that it would span the
entire universe.
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: OTP unbreakable?
Date: Mon, 19 Mar 2001 19:25:40 -0800
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:1_lt6.80245$[EMAIL PROTECTED]...
> Is the OTP really really really really really unbreakable?
>
> hehehehe
>
> How many times are people gonna ask this.... ARRG
>
> Tom
>
My estimate is a further 2^56 times..but its not a really a problem, this
group is as much about the newbies as the seasoned professional..... most of
us come in the first category and I'm damned sure some of our questions
annoy the pro's =)
Simon.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Bacon's cryptography?
Date: Mon, 19 Mar 2001 21:01:31 +0100
Mok-Kong Shen wrote:
> bookburn wrote:
> >
> > I read a couple books years ago about history of cryptography and
> > remember that Francis Bacon developed a study of cryptography that has
> > been used in classrooms as textbook. Looking for such a tomb in
> > encyclopedias and on the Net doesn't identify such a work, though.
> > Can anyone suggest where Bacon's writing on cryptography are brought
> > together systematically? bookburn
>
> Are there really treatises on the history of cryptography
> (excepting books like Kahn's The Codebreakers and some
> textbooks that deal with quite an amount of historical
> ciphers)? I doubt that any specific collection of Bacon's
A comprehensive history of cryptology would definitely be interesting.
The dominance of UKUSA in crypto definitely deserves some analysis. Why
were they so much better than the rest of the world ?
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: hardwire prime & generator in Diffie-Hellman?
Date: 19 Mar 2001 14:53:13 GMT
Julian Morrison <[EMAIL PROTECTED]> wrote:
> 1) What is the security implications of hardwiring in the
> prime/genrator startup pair for DH key exchange? Does it compromise
> the protocol or is it safe?
It means that it's harder to change the group if anyone compromises it,
i.e., finds an easy way to compute discrete logs in it.
In a typical integer-discrete-log system, there are two security
parameters you can fiddle with: the sizes of $p$ and $q$. Here, $p$ is
your modulus, and $q$ is the order of the subgroup within which you're
working. You'll always have $q$ a factor of $p - 1$; you're best off
choosing $(p - 1)/2$ so that all of its prime factors are `large' -- at
least as big as $q$. I recommend against `safe' primes (where
$(p - 1)/2$ is also prime), because (a) it's loads of hassle finding the
things, and (b) it increases the length of time required for a modular
exponentiation for no particularly good reason.
The effect of increasing the size of $q$ is that collision-finding
attacks (e.g., Pollard's rho) are made more difficult. The effect of
increasing the size of $p$ is that index-calculus attacks (e.g., the
number-field sieve) are made more difficult. Usually, we try to balance
the sizes of $p$ and $q$ so that both attacks are about the same
difficulty. Hence, 1024-bit $p$ and 160-bit $q$ are a common choice.
In your case, if you're /only/ using Diffie-Hellman key exchange in this
group, you might be better off making index-calculus harder than
collision-finding: an index-calculus attack makes general discrete-log
computations in the group easy, whereas collision-finding doesn't get
easier the more you do it.
> 2) If it's safe to do this, does it become more safe the larger the
> prime is?
Yes. It also becomes slower to do the arithmetic.
-- [mdw]
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: IP
Date: Mon, 19 Mar 2001 11:47:28 -0800
Mxsmanic wrote:
> "David Schwartz" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Anonymity is not a defense against any vulnerability
> > I know of.
> Do you know of any anonymous banks that have been robbed? You have to
> be able to identify something before you can target it for attack.
Attackers don't care what they attack. They sweep the ranges of dynamic
IP addresses constantly because they're always filled with new
vulnerable machines.
DS
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: An extremely difficult (possibly original) cryptogram
Date: Mon, 19 Mar 2001 11:51:30 -0800
daniel mcgrath wrote:
>
> Jim Gillogly ([EMAIL PROTECTED]) wrote:
>
> >daniel mcgrath wrote:
> >> HTML it is. I thought at the time that telling you that would make it
> >> too easy, but apparently you really want bigger hints.
> >
> >Certainly. As people (including me) keep saying, a very strong
> >algorithm will still be strong even if everything except the key
> >used for that message has been totally exposed. Even if you give
> >away the plaintext to all but the last 10% of a message, this
> >should give the cryptanalyst no help in decrypting the last 10%.
> >A few people enjoy working on ciphertext-only challenges in unknown
> >cipher systems, but for most that gets very old in a hurry.
What is your reaction to this paragraph? Whether or not your
system survives attacks on the ciphertext only without the
system being exposed, you can't consider it strong unless it
can also survive the kind of attack I describe above, with
a completely described algorithm.
> >> > You came 620711143 close with 54006 of the 806648
> >> > first hypotheses 711015 you had 450103. The code
> >> > 696690137 used here, 27465680662, is based 7774
> >> > the same 20650362042 idea as 71112 system used
> >> > 1743 my cryptograms.
> >
> >for 1743 (probably)
> >general 20650362042
> >however 27465680662
> >made 450103
> >one 54006
> >rather 620711143
> >system 696690137
> >that 711015
> >the 71112
> >upon 7774
> >very 806648
>
> All of the above equivalences are correct. So have you figured out
> the system? (I think Douglas has it.)
Not altogether. It seems to me that digraphs get converted into
trinomes starting from the beginning of the word, and that individual
letters at the end of the word may be represented by monomes or
dinomes, but I fall apart near the end. For example, the
final 'e' in "the" could be represented by "12", but the final
'e' in "one" would be "06", which doesn't fit well. In addition,
the 'r' in "for" would be converted to "3" and the "we" in
"however" would be "656", both of which are out of order. Further,
the "on" in "upon" would be '4' instead of a trinome. This
means I don't quite see what's going on. I made a chart of the
known correspondences for digraphs->trinomes in alphabetical to
numerical order, and they're pretty consistent. I still don't
have that under control either -- the distance from xa to xz
is more than 26, for various values of x, and the average
changes across the chart. Ah, well. I'll look forward to
Doug's explication, if you're right about his insight into it.
I assume, since HTML is being encrypted, that there's a way
to encrypt every possible (printable?) digraph. However,
it couldn't just be trinomes, since there are only enough trinomes
to cover the whole printable space... only enough for 31 chars
in each place. Perhaps it's a 31x31 space for the letters, with
the remaining 38 values for other printables. It's also clear
that the process restarts frequently, since there are long repeats
that do not appear at multiples of 3. Similarly, if there's an
additive it must restart frequently (e.g. on word boundaries),
since the long repeats have internal repeats. For example, one
116-digit repeat has the following significant internal structure:
7504059116
946359421
802044883
8020402504558
946367751008941
5204187
57641367
204436144084100778945
5204138
57645595669445761
I've looked at variations of <html><head><title> as a
crib for the top and </html> at the bottom, but didn't get
far with that.
--
Jim Gillogly
Trewesday, 27 Rethe S.R. 2001, 19:17
12.19.8.1.3, 10 Akbal 6 Cumku, Fifth Lord of Night
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: PGP key expiration (was Re: Encryption software)
Date: Mon, 19 Mar 2001 11:43:45 -0800
I personally prefer the "set the expiration date" method. I simply don't
create PGP keys that won't expire. If you do a standard search on my name
you'll find (or at least I just did) 5 expired PGP certs. Of course I also
have a set of backups for all the current ones (all one of them). I chose my
time period(s) based on my situation, I suggest that each person choose a
time period other than infinite, if for no other reason than within 100
years you'll be dead and won't be able to decrypt it ayway.
Joe
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Joe H. Acker wrote:
> [snip]
> > I have another problem with PGP: I once forgot my passphrase for a
> > non-expiring key and didn't make a key revocation certificate, which
> > means that there will now be two keys (the new one and the old one)
> > forever on the keyserver, but I can only decrypt for one. That's
> > really bad... and I think this can happen to many unexperienced PGP
> > users. Wouldn't it be possible to require regular confirmation of key
> > expiry or not, instead of no expiry at all or fixed expiry? That way,
> > if somebody lost his passphrase to a private key, he could not confirm
> > "no don't expire this public key" and so the public key would expire
> > automatically.
>
> It's an interesting idea, but it requires rather alot of work on the
> part of the keyserver (ie, regularly asking each user with a
> conditionally expiring cert whether or not he wants it to expire).
> Plus, if the user goes on vacation, he's got a problem.
>
> A better method would be to design a special "advance expiration date"
> message, which one would send to the keyserver, so that we only need a
> one-way communication, not a two-way communication.
>
> A more practical solution would be to have PGP automatically create a
> key revocation certificate when a new key is made, and nag the user into
> putting it on a floppy disk, and further nag him into sticking that
> floppy in a safe place.
>
> --
> The difference between theory and practice is that in theory, theory and
> practice are identical, but in practice, they are not.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Mon, 19 Mar 2001 21:03:20 +0100
"Joe H. Acker" wrote:
>
[snip]
> At least to me, it seems plausible why a bijective compressor in Scott's
> sense is desirable. The question is rather, wether the overall
> enhancement of security by this kind of compression is significant or
> almost neglectible.
It may be noted that one could also get some (arguably
how much) enhancement through a compression that depends
on some 'key', I suppose. For in that case, without that
secret, a failure of the decompression-compression pair
to be the identity operation need not be the consequence
of having used the wrong key of the cipher to decrypt (but
only having used the wrong 'key' of the compression scheme).
M. K. Shen
------------------------------
** 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
******************************
