Cryptography-Digest Digest #571, Volume #14 Sat, 9 Jun 01 00:13:00 EDT
Contents:
Re: Alice and Bob Speak MooJoo ([EMAIL PROTECTED])
Re: cubing modulo 2^w - 1 as a design primitive? ("Tom St Denis")
Re: Knapsack security??? Ah....huh (John Bailey)
Re: Knapsack security??? Ah....huh (John Bailey)
Anyone Heard of "Churning" (Stephen Thomas)
Re: Alice and Bob Speak MooJoo ("Robert J. Kolker")
Re: Alice and Bob Speak MooJoo ([EMAIL PROTECTED])
Re: Alice and Bob Speak MooJoo (SCOTT19U.ZIP_GUY)
The 94 cycle 64-bit block cipher :-) ("Tom St Denis")
Re: The 94 cycle 64-bit block cipher :-) ("Scott Fluhrer")
Re: Simple C crypto (Paul Schlyter)
----------------------------------------------------------------------------
Subject: Re: Alice and Bob Speak MooJoo
From: [EMAIL PROTECTED]
Date: 08 Jun 2001 21:33:51 -0400
"Robert J. Kolker" <[EMAIL PROTECTED]> writes:
> "Douglas A. Gwyn" wrote:
>>
>> Not so. There is enough common ("cultural") context to
>> infer some things by analyzing the plaintexts...
>
> The common context is ostention. The pointing finger...You can't
> start of defining basic words with other words, else an infinite
> regress follows.
Granted--but given time and a large enough corpus, there is sufficient
basis to make surprising progress. Something like this:
1. Catalog individual phonemes (and attempt to classify as words). That's
not hard; statistical analysis will identify a great many words.
2. Transcribe messages and build an online concordance.
3. Notice repeating patterns, such as: the word "koch-ba'a" crops up
an awful lot when supply convoys are on the move; the word "tlu-upicha"
occurs only in naval messages; etc.
4. Notice that the words "moor-tahr" and "tuhnka" seem to crop up an awful
lot. Conjecture that the Navajo don't have words for "mortar" and "tank".
Recall that a person can understand the gist of a conversation with
astonishingly small vocabulary. Travellers' phrasebooks actually do
serve a useful purpose.
> If there were no Rosetta Stone Egyptian hieroglyphs would
> be opaque to us.
Perhaps--but if we were able to observe living Egyptians in action, we
would eventually get the idea.
Of course, whether that's practical in wartime or not is a separate
question. There are other weaknesses to this idea, which I mentioned
before: (1) if there are no native speakers, then the cost of teaching
the "language" is high. (2) If there are dictionaries, then a stolen
dictionary == a stolen codebook. (3) If a unit loses its Orawanee
Eskimo radioman, it must communicate in the clear.
Len.
--
Frugal Tip #22:
Get free refills.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: cubing modulo 2^w - 1 as a design primitive?
Date: Sat, 09 Jun 2001 01:47:07 GMT
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:H5eU6.62238$[EMAIL PROTECTED]...
> I was wondering if anyone ever considered cubing modulo 2^w - 1 as a
design
> primitive?
Even more nonlinear and lower DPmax is
f(x) = (x(x+x+1) mod 2^w)^3 mod (2^w - 1)
With W=8 the DPmax is 12/256. With W=32 it takes 11 cycles to compute (on
my Athlon)
Any comments?
Tom
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Knapsack security??? Ah....huh
Date: Sat, 09 Jun 2001 01:59:41 GMT
On Fri, 8 Jun 2001 00:21:58 -0400, "rosi" <[EMAIL PROTECTED]> wrote:
>Dear John,
>
> Thank you for the reply.
>
> I will perhaps never know why you think I am taunting you.
>But if you do, whether it is really due to me, I apologize.
>
> Merc42 asked in pretty general terms about the knapsack
>problem and you seem eager to know. I offered to share
>information. Is this fair?
>
> First, I do not know how far we can go. The requirement for
>basic knowledge will still apply. Without that, we can get stuck
>anywhere.
>
> So, is it a go?
>
> I think it is only fair that I give you enough information on
>what is ahead. I have some simple stuff, from which I would like
>to see if certain things are as trivial as I seem to see. So I give the
>best shot I can fire and would like you to help me. I will put
>forth two quite non-technical questions, which do not require
>definitive answers (or in other words, what answers come back is
>not that important). There is one technical issue I would appreciate
>it if you could share your thoughts with us, but that is not really
>expected. It is up to you. The issue is to prove from what I
>give you that P != NP. (Hope you are still in your chair if you
>were:). Checked, I am still in mine)
Would it help if we used Rojas' papers as a common ground of
understanding?
http://arXiv.org/find/math/1/au:+rojas/0/1/0/1998/0/1
> Please do not be alarmed. It should be simple. Ideas about
>both the two questions and the P!=NP issue can be formed in
>your head by simply ‘staring at’ a construction I give you for a
>few minutes. I am not saying that you may come up with all
>the boring details of a proof after reading and thinking about
>it for a few minutes. I mean that you can get the sense of it.
>
If you are heading off in the direction of complexity theory, I don't
think its productive. To me the issue is far simpler. Standard
format knapsack systems have been shown sufficiently suspect that
nothing commercial is likely to be trusted. NTRU may have gone one of
two ways. 1) they may have found a basis (excuse the pun) on which a
knapsack or sparse diophantine system can be made secure OR 2) they
just hide the knapsack formal equivalence. If the latter, I hope this
isn't regarded as an attack on their business. If the former, it
would be useful to understand the underlying source of the improvement
because other parallel approaches might yield something useful as
well.
Given Rojas' (and certailnly others) work, it should not be hard to
find a one way function which would require solving Hilbert's tenth
problem, in order to reverse (short of an exhaustive search)
> So you now may see that I am not in NTRU, not just because
>I have nothing to do with NTRU. What I want is to complete the
>sentence about "THE" whole issue and put a small fullstop to
>it. Simple enough?
>
> I caution that I am not interested in other way of proving this
>time and you may not use the material on P!=NP for the past
>couple of years (should there have been any). Of course, you
(snipped--see previous post for details)
> So if you think this is of interest to you and this can be
>a go, please let me know. But I repeat, if you are only
>interested in NTRU, we are definitely not on the same track.
>(I am pretty sure that is the case, which makes a pretty good
>excuse. :) But please prove me wrong.)
My comments above and on another post confirm you understanding. The
whole basis for my questioning is an attempt to understand what if
anything is different about the NTRU system and to apply the
principles underlying such difference to other systems. If your
approach is to treat them all alike, its of interest to me only if its
a more general approach than outlined in previous papers on knapsack
cracking. I'll happily watch.
John
> Any other readers are interested? Want to help? Please
>let me know.
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Knapsack security??? Ah....huh
Date: Sat, 09 Jun 2001 01:59:51 GMT
On Fri, 8 Jun 2001 11:14:38 +0200, "Jakob Jonsson"
<[EMAIL PROTECTED]> wrote:
>> Diophantine encryption for public key encoding
>>
>http://www.frontiernet.net/~jmb184/interests/sci.crypt/numerical_encryption.
>html
>> In this last one, an encrypted message e = r*h + m*k where e is the
>> encrypted message, r is a random number, h and k are public key
>> values, and m is the encrypted message (number) m is recovered by
>> computing m = e*g mod p mod q where g, p, and q are calculated from
>> the private keys.
>
>This scheme doesn't look terribly secure to me.
It isn't. If I didn't say so in the immediate context of what you
read, I say it in several other places--cryptographically this is
about as secure as hiding your door key under a flower pot. Its only
possible value is as a demonstration of a public key like system which
exhibits superficially the process of using a public key and private
key to conceal information. In the context of this thread--the
important think is that it IS EASILY reversed. If you believe there
is a formal equivalence to the NTRU system, the question then becomes
whether there is something else that makes a system using a more
elaborate and less well known basis secure?
> If q divides p, then we may
>decrypt messages as follows. We assume that h and k have no divisors in
>common. Multiply e with the inverse k' of k modulo h and compute modulo h:
>
>e*k' == r*h*k' + m*k*k' == m (mod h).
>
(see original post for complete math)
>This scheme does not seem to have anything in common with the NTRU scheme.
>
quoting from:
The NTRU Public Key Cryptosystem
http://www.ntru.com/technology/tutorials/pkcstutorial.htm
This tutorial describes how the NTRU Public Key Cryptosystem (PKCS)
works.
The basic collection of objects used by the NTRU Public Key
Cryptosystem is the ring R that consists of all truncated polynomials
of degree N-1 having integer coefficients:
a = a0 + a1X + a2X 2 + a3X 3 + . . . + aN-2X
N-2 + aN-1X
N-1
Isn't that formally equivalent to a knapsack?
John
------------------------------
From: [EMAIL PROTECTED] (Stephen Thomas)
Subject: Anyone Heard of "Churning"
Date: 8 Jun 2001 19:21:22 -0700
[This didn't get a response in sci.crypt.research, so I thought I'd try here.]
Apparently, ATM Passive Optical Networks (APONs) have standardized on
an "encryption" algorithm refered to as "churning." Does anyone know
anything about this? Especially details on the algorithm. (FWIW, PONs
are shared media networks like cable modems.)
The only references I can find are:
APON uses a 24-bit key churning mechanism
Churning is a memoryless transformation of one byte to a
different byte
Key strength is 2^key length
Drawbacks and weak points:
IP header
FCS
[http://grouper.ieee.org/groups/802/3/efm/public/may01/haran_1_0501.pdf]
And
While some dissenters voice doubts about whether churning keys
and existing encryption constitute adequate security measures,
Comcast Business Communications, one of the few real-world adopters
of PON, has put it through the wringer and has no fears pertaining
to PON's shared-medium nature. "We've spent some time in the
lab trying to intercept messages not intended for a particular IOT
[Intelligent Optical Terminal, analogous to an ONU], but we've
been incapable of breaking anything" says Steve Linskey, vice
president of technology and planning at the Competitive Local
Exchange Carrier (CLEC).
[http://www.networkmagazine.com/article/NMG20010518S0008]
Stephen
------------------------------
From: "Robert J. Kolker" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Fri, 08 Jun 2001 22:35:40 -0400
[EMAIL PROTECTED] wrote:
>
> > If there were no Rosetta Stone Egyptian hieroglyphs would
> > be opaque to us.
>
> Perhaps--but if we were able to observe living Egyptians in action, we
> would eventually get the idea.
At the time the French got a hold of the Rossetta Stone there
were no living speakers or writers of ancient egyptian. The
closest thing to it, was the liturgy of the coptic church and
the written language had been lost by then.
>
>
> Of course, whether that's practical in wartime or not is a separate
> question. There are other weaknesses to this idea, which I mentioned
> before: (1) if there are no native speakers, then the cost of teaching
> the "language" is high. (2) If there are dictionaries, then a stolen
> dictionary == a stolen codebook. (3) If a unit loses its Orawanee
> Eskimo radioman, it must communicate in the clear.
Or go back to using crypto.
The best form of cryptography is clear communiction in
a mostly unknown language.
Bob Kolker
------------------------------
Subject: Re: Alice and Bob Speak MooJoo
From: [EMAIL PROTECTED]
Date: 08 Jun 2001 22:52:50 -0400
"Robert J. Kolker" <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>>
>>> If there were no Rosetta Stone Egyptian hieroglyphs would be opaque
>>> to us.
>>
>> Perhaps--but if we were able to observe living Egyptians in action, we
>> would eventually get the idea.
>
> At the time the French got a hold of the Rossetta Stone there
> were no living speakers or writers of ancient egyptian.
Correct. That's why your example of the Egyptians does not accurately
reflect the situation with modern-day code talkers.
>> There are other weaknesses to this idea, which I mentioned before:
>> (1) if there are no native speakers, then the cost of teaching the
>> "language" is high. (2) If there are dictionaries, then a stolen
>> dictionary == a stolen codebook. (3) If a unit loses its Orawanee
>> Eskimo radioman, it must communicate in the clear.
>
> Or go back to using crypto.
In which case, there's no reason not to use crypto in the first place,
thus bypassing measures which are likely to be hugely expensive, but
with only dubious benefit.
The Navajo code-talkers were a special case: the US had essentially
exclusive access to native speakers of a little-used language, while
the enemy had nobody experienced with any similar language.
Further, the code-talkers did not simply speak Navajo. They started
with a written message in English, and then for each letter they spoke
a Navajo word whose English translation started with that letter. (In
addition, they had code words for common terms.) The Japanese even
captured a Navajo (not a code-talker), and he was completely baffled
by the code.
> The best form of cryptography is clear communiction in a mostly
> unknown language.
Sure. But it's not good enough, in general--and much better alternatives
exist. Your statement reveals that, BTW; it amounts to saying, ``The
best way to communicate secretly without secret communication is to
speak a foreign language.''
Len.
--
Alert! Jones is abusing the passive voice!
-- Dan Bernstein
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Alice and Bob Speak MooJoo
Date: 9 Jun 2001 03:08:56 GMT
[EMAIL PROTECTED] wrote in <[EMAIL PROTECTED]>:
>Further, the code-talkers did not simply speak Navajo. They started
>with a written message in English, and then for each letter they spoke
>a Navajo word whose English translation started with that letter. (In
>addition, they had code words for common terms.) The Japanese even
>captured a Navajo (not a code-talker), and he was completely baffled
>by the code.
I have watched a show where some of the old code talkers where
talking. They said since the white man never new what they where
saying sometimes they would just gab about home or what ever.
But I never heard that a Navajo was captured. But I got the impression
the code was not complex. Only that words for tanks planes and
nouns that are not part of the language really had to be added.
Actaully I have been around Navajos to my hear it sounds like
spanish. But then so does Italian.
>
>> The best form of cryptography is clear communiction in a mostly
>> unknown language.
>
>Sure. But it's not good enough, in general--and much better alternatives
>exist. Your statement reveals that, BTW; it amounts to saying, ``The
>best way to communicate secretly without secret communication is to
>speak a foreign language.''
>
>Len.
>
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: The 94 cycle 64-bit block cipher :-)
Date: Sat, 09 Jun 2001 03:21:28 GMT
Just for fun. (Hey if this works it could be the fastest, simplest block
cipher).
I used the quadratic function x(2x + 1) modulo 2^32 as the round function.
It has one nasty differential which is a difference in the high bit goes to
a difference in the high bit with a prob of 1. The rest of the
differentials are fairly low bounded by as far as I can tell 2^-16. (I'm
extrapolating from the case of W=8 where the highest is 16/256. Since we
are four times bigger we get (16/256)^4 = 65536/2^32.
To avoid this nasty one I used a cyclic rotate left by five bits. Now the
trail has a much lower probability (from the W=8 case it's zero).
So we get two rounds for free (first and last). Given 6 rounds we have a
bounded prob of (2^-16)^6 = 2^-96 which means most likely differential
analysis won't break the cipher with eight rounds.
Of course take heed and remember this is a toy cipher design. It's still
fairly neat that 8 rounds will run in 94 cycles (11.75 cycles per byte). I
want to see about mixing in a PHT with two quadratics.... :-)
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: The 94 cycle 64-bit block cipher :-)
Date: Fri, 8 Jun 2001 20:28:06 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:YCgU6.63976$[EMAIL PROTECTED]...
> Just for fun. (Hey if this works it could be the fastest, simplest block
> cipher).
>
> I used the quadratic function x(2x + 1) modulo 2^32 as the round function.
> It has one nasty differential which is a difference in the high bit goes
to
> a difference in the high bit with a prob of 1. The rest of the
> differentials are fairly low bounded by as far as I can tell 2^-16. (I'm
> extrapolating from the case of W=8 where the highest is 16/256. Since we
> are four times bigger we get (16/256)^4 = 65536/2^32.
Actually, it's worse than that -- it never propogates differentials
rightward.
>
> To avoid this nasty one I used a cyclic rotate left by five bits. Now the
> trail has a much lower probability (from the W=8 case it's zero).
>
> So we get two rounds for free (first and last). Given 6 rounds we have a
> bounded prob of (2^-16)^6 = 2^-96 which means most likely differential
> analysis won't break the cipher with eight rounds.
(I'm assuming that you're talking about using the above function in a
Feistel network, and you mix in key somehow). Assume that, at round N,
consider a partial differential where the differential is confined to bits
31-x on both sides, for some x>5. Then, with probability 2**-5, the upper
five bits of x(2x+1) mod 2^{32} will have zero differential, and so the
partial differential will be preserved. This truncated differential will go
through 8 rounds with probability 2**-40.
>
> Of course take heed and remember this is a toy cipher design. It's still
> fairly neat that 8 rounds will run in 94 cycles (11.75 cycles per byte).
I
> want to see about mixing in a PHT with two quadratics.... :-)
> --
> Tom St Denis
> ---
> http://tomstdenis.home.dhs.org
>
>
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Simple C crypto
Date: 9 Jun 2001 00:23:04 +0200
In article <[EMAIL PROTECTED]>, Samuel Paik <[EMAIL PROTECTED]> wrote:
> Dirk Bruere wrote:
>> Let's see now...
>> I've got a time budget of about $50 to spend on this, including coding
>> and> code integration.
>
> $50? That's barely enough time for me to start up Microsoft Developer's
> Studio!
Are you running it on a 10 MHz 386SX or what? Ever considered a hardware
upgrade? <g>
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
** 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
******************************
