Cryptography-Digest Digest #909, Volume #13 Thu, 15 Mar 01 22:13:00 EST
Contents:
NTRU parameters (Colleen Marie O'Rourke)
Re: Super strong crypto ("Douglas A. Gwyn")
Re: The Art of Cryptography (was: Super strong crypto) ("Douglas A. Gwyn")
Re: Super strong crypto ("Douglas A. Gwyn")
Re: An extremely difficult (possibly original) cryptogram (daniel mcgrath)
Re: What do we mean when we say a cipher is broken? (Was Art of (Jim Gillogly)
Re: How to eliminate redondancy? ("Douglas A. Gwyn")
small SSL implementation (Paul Rubin)
Re: Computing power in the world (Ichinin)
Re: Analysis of PCFB mode (David Wagner)
Re: SSL secured servers and TEMPEST (Paul Rubin)
Re: The Art of Cryptography (was: Super strong crypto) (David Wagner)
Re: What do we mean when we say a cipher is broken? (Was Art of (William Hugh
Murray)
Re: How to eliminate redondancy? (br)
Re: Computing power in the world (Darren New)
Re: How to eliminate redondancy? ("Tom St Denis")
Re: How to eliminate redondancy? (br)
Re: primes for BBS (Terry Ritter)
Re: How to eliminate redondancy? ("Tom St Denis")
----------------------------------------------------------------------------
From: Colleen Marie O'Rourke <[EMAIL PROTECTED]>
Subject: NTRU parameters
Date: Thu, 15 Mar 2001 19:51:08 -0500
Hello :)
I am writing to anyone who knows about the NTRU cryptosystem. I have a
couple of questions.
1) The parameter, p, is supposed to be relatively small compared to q.
But, what if p was close to q but they were still relatively prime to each
other? How would that affect the security? Which attacks would NTRU be
most vulnerable to as a result?
2) For p=3, the coefficients for the random polynomials should be either
1, 0, -1 where the sample samples Lf, Lg, Lphi determine the #1's and #
-1's. If p was chosen to be something other than 3, how would this affect
the coefficients of the random polynomials? Would they still be only 1,
0, -1 or would they be -p/2 to p/2? How would this affect the user
defined sample spaces (Lf, Lg, Lphi)?
If anyone could clear up these questions, I would be most appreciative :)
Thanks, Colleen
:o) :o) :o) :o) :o) :o) :o) :o) :o) :o) :o) :o) :o) :o) :o) :o) :o) :o)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Fri, 16 Mar 2001 01:22:33 GMT
Bryan Olson wrote:
> It's awkward. It requires a source of true random numbers,
> bloats the ciphertext and has to execute the key scheduler
> repeatedly.
For any reasonable security one needs a source of randomness
anyway, e.g. to generate an IV. Since conventional schemes
transmit the IV (usually in the clear!) there is no
disadvantage in the first data block of my straw man mode of
operation being used to send (securely!) the equivalent of
an IV; I set this up so that it would be easy to integrate
into the general block-by-block iteration. Each block uses
a small fraction of channel capacity (12.5% in the example)
for what is essentially a continual key distribution
function; if that function were instead performed with a
separate protocol, it would need *at least* the same amount
of bandwidth, as well as being more awkward (because two
independent streams would have to be differently keyed and
correctly correlated). By the "key scheduler" I guess you
mean something within the block cipher function, since the
key schedule in the straw man protocol is very simple; if
so, then so what -- it might slow down execution for some
choices of block function, but that's not "awkward".
> >And my actual
> >claims for what it accomplishes, as opposed to spurious
> >claims that some of you have assumed, have not been
> >refuted. Come on, show why entropy cannot be securely
> >added to the stream, or that the scheme adds little work
> >to an attack based on flush depth. That would be worth
> >hearing.
> Wasn't that you who said the topic seemed to be provable
> security? I grant that you could specify a few things to
> overcome Dave Wagner's attacks, and then you'd have
> not-yet-disproven security. I think Ciphile Software has
> that too.
Yes, "super strong crypto" ought to involve a degree of
proof that (listen!) *simply is not available*. One can,
however, *anticipate* the features of a relevant theory
should it ever emerge, and one of those features would be
a way to connect the system structure, source language
properties, key and CT length, etc. to produce a *lower
bound* for the amount of computation needed by the analyst
to attain a given recovery rate (for specified scenario).
It is quite evident that that could be effectively inverted
to produce an *upper bound* on the amount of CT using a
fixed key before an assumed available amount of analyst's
computational resources could be expected to recover the
secret information with high enough probability to pose a
real threat. *Absent the actual theory*, it then becomes
a matter of judgment just how much CT that might be; from
my own experience as a cryppie I don't think it would take
a whole lot, as you can tell from my suggested example.
Wagner's attacks showed that the mode of operation *by
itself* doesn't make for a strong system, but then that is
not what I suggested. (Indeed, replace the block function
by an identity map and tweak the parameters as Wagner did
so half of each block is the entire subsequent key, and it
is almost trivially easy to steal the key.) But that is a
red herring, since the straw man mode of operation is meant
to be used with some decent block cipher that *might* have
some susceptibility to an unknown C/A attack. The mode is
meant to *obscure* access to the block cipher in such a way
as to foil such attacks. What I want feedback on is only
possible protocol problems (as of phase 3) that could
introduce new vulnerabilities at least as great as the ones
being obscured. Take as a given that the block function
requires some feasible but substantial amount of computation
to invert, call it K, and see if there is a way to crack the
overall scheme with on the order of K amount of computation.
If so, is there a simple fix? And if not, then my goal is
achieved -- without weakening the system, for a small amount
of trade-off whole classes of C/A attacks have been spoiled.
In that case, this *would* be a real contribution toward
"super strong crypto" *even though we don't yet have a good
theory*. I think that is preferable to waiting for the
theory to be developed before we even start to think about
this topic.
The mention of Ciphile Software was apparently meant as an
insult, but it's entirely irrelevant. I've explained, in
more detail than I intended, what I'm trying to do and why.
If you have counterarguments or further contributions to
*that*, great, let's hear them.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The Art of Cryptography (was: Super strong crypto)
Date: Fri, 16 Mar 2001 01:25:36 GMT
John Savard wrote:
> This mode does place obstacles in the way of an analytic attack.
Thank you for explaining this more clearly than I apparently did.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Fri, 16 Mar 2001 01:34:17 GMT
Mok-Kong Shen wrote:
> I like to mention in this connection another point. Your
> scheme in the original post intends to reduce the amount of
> materials encrypted by a given key of block ciphers. If one
> changes session/message keys sufficiently frequently and the
> message sizes are appropriately limited, then the problem
> could be avoided, isn't it?
Remember, the scenario I have in mind involves a one-way
channel, so any new key has to be transmitted in the same
direction (not "negotiated"). One could certainly set up a
separate protocol for key distribution, encrypted using a
"key distributing key", for example, as has been suggested
in this thread, and multiplex that with the useful-data
stream. That requires twice as much initial key as what I
proposed in my straw man mode of operation. That's clearly
a disadvantage, since the whole point is to stretch the
(reusable) initial key as far as safely can be done.
------------------------------
From: [EMAIL PROTECTED] (daniel mcgrath)
Crossposted-To: rec.puzzles
Subject: Re: An extremely difficult (possibly original) cryptogram
Date: Fri, 16 Mar 2001 01:33:59 GMT
On Thu, 15 Mar 2001 11:43:18 -0800, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>daniel mcgrath wrote:
>> Seriously, for anyone who is actually interested in breaking my
>> cryptogram, I'll say that it contains the phrase "Eppur si muove". (I
>> was hoping that Jim Gillogly would be interested and respond to my
>> posting.)
>>
>> Here is a shorter message that is (basically) in the same code:
>>
>> 34619 24112 61612 20346 69455 75457 12060 11296 67744 12504
>> 63708 94452 04025 04608 14435 61402 04608 04137 57610 09465
>...
>> 56460 20460 89100 85426 85761 00804 03709 01614 40955 50413
>> 85764 55204 03579 24137 53706 012
>>
>> ..... tysoizbyjoxs ... good luck
>> ... daniel mcgrath
>
>Perhaps it would be worth reviewing the bidding and hintage from the
>previous time Daniel was trying for feedback on this cipher.
>
[...]
>5. Daniel responded to these observations, saying
> OK, I will tell you that, of the ten digits, six of them behave one
> way, while the other four behave a different way. And the "plaintext"
> is really a sort of code to begin with.
> ...
> The code that the plaintext is in, however, is something that we all
> know. It is an important thing these days.
>
>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.
>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.
[...]
>Evidently 620711143 means very or fairly or rather or something like that.
It's one of those.
>54006 probably means "one".
Correct.
>806648 may mean "very".
Correct.
>711015 may mean "that".
Correct.
>450103 may mean "made".
Correct.
>7774 probably means "on".
Close, but not quite.
>71112 = "the"?
Correct.
>20650362042 may mean "basic" or "fundamental".
>1743 = "in"?
Try again on these.
Hint: Try putting the words in alphabetical order, with their cipher
equivalents on the side. Notice anything?
==================================================
daniel g. mcgrath
a subscriber to _word ways: the journal of recreational linguistics_
http://www.wordways.com/
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: What do we mean when we say a cipher is broken? (Was Art of
Date: Thu, 15 Mar 2001 17:35:55 -0800
William Hugh Murray wrote:
>
> John Savard wrote:
>
> > On Thu, 15 Mar 2001 22:35:51 GMT, William Hugh Murray
> > <[EMAIL PROTECTED]> wrote, in part:
> >
> > >I am not at all sure what you mean by "broken." Do you mean that the cost
> > >of recovering a message without benefit of the key suddenly falls to
> > >zero?
> >
> > A cipher is broken when that cost is less than infinity.
>
> Well, I suppose the definition has the advantage that it is binary. However,
> since it includes all of the ciphers in history, and since you cannot
> demonstrate that, by this definition, there is an unbroken one, it is simply
> not interesting.
My definition is that a cipher is broken when the cost of cryptanalyzing
a set of messages is less than the cost of obtaining the information in
them by some other means. The cost is measured in some appropriate unit --
perhaps wall clock time, money, lives, person-hours, or whatever is useful
for valuing that specific information.
> I hope that you cryptographers have fun with your abstraction but it is not
> particularly useful to security people.
Hope you like mine better.
--
Jim Gillogly
Sterday, 24 Rethe S.R. 2001, 01:32
12.19.8.0.19, 6 Cauac 2 Cumku, First Lord of Night
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Fri, 16 Mar 2001 01:39:31 GMT
br wrote:
> I didn't anything relating to redundancy and I don't understand why
> nobody had treated this question.
Probably because everybody else knows it by the name "lossless
compression". Look up "arithmetic coding".
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: small SSL implementation
Date: 15 Mar 2001 17:40:07 -0800
I'm looking for a small client side SSL implementation written in C or C++.
Commercial is ok if not too expensive. OpenSSL has everything
including the kitchen sink and I want something minimal. Anyone know
of anything?
Thanks
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Computing power in the world
Date: Tue, 13 Mar 2001 14:59:28 +0100
Darren New wrote:
> mips-years would be mips * years, right? That doesn't sound
> like a useful measurement.
MIPS Years is a well known measurement of a machine running at 1 Mips
(i.e. ~386sx25) for a lenght of (you guessed it) a year. 2 mips years
would require 2 such computers.
IIRC, Exactly which instruction to use is unspecified though, therefor
it's not a very accurate benchmarking measurement.
Regards,
Ichinin
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Analysis of PCFB mode
Date: 16 Mar 2001 01:49:31 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Henrick Hellstr�m wrote:
>Hence, I imagine that you would have to decrypt a m-bit periodic cipher text
>to expect a collision after 2**{64 - m/2) blocks.
Yes, that's right.
Note: I don't see any obvious way to build a full attack out of this,
and I don't have any evidence that it causes problems. I mention it
only as a possibly-undesirable property.
>If you have this kind of control you could
>mount exactly the same attack against e.g. XCBC mode, in this case simply by
>correspondingly asking for the encryption of X || g(X) || Y.
No, it doesn't work against XCBC mode, because in XCBC mode the g()
function is keyed. (However, if you were to use an unkeyed g() function,
then yes, the attack would work against XCBC, too.)
>At the present moment
>I have no reason to doubt that PCFB mode too is provably secure in this
>sense, provided that it is used with a suitable authentication scheme.
But -- even if you had a proof of this -- it wouldn't be a
very useful result. CBC mode already gives you this property,
and it does come with a proof.
Compare to competitors like IAPCBC, which are provably secure for
both confidentiality and integrity, and moreover don't need to be
used with a separate authentication scheme. My main interest in
PCBC mode is that it has the potential to provide both confidentiality
and message integrity; if you're suggesting use of an authentication
scheme as well, I see no reason to prefer PCBC mode to CBC mode.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: SSL secured servers and TEMPEST
Date: 15 Mar 2001 17:59:19 -0800
Frank Gerlach <[EMAIL PROTECTED]> writes:
> > The modules are typically
> > completely potted in epoxy (airtight) and surrounded by metal
> > shielding. It is very true that the connection points are hot spots
> > for leakage and the designers must work hard to make sure they don't
> > radiate any data that way.
> "any data that way" is an impossible proposition, as I am trying to
> explain all the time. This is because even the faintest noise generated
> by the RSA processor will leak millions of times. I am saying that you
> can minimize that leakage (by proper shielding and proper electronic
> design), but you will never ever make it ZERO.
Well, sure, but I don't see why that's interesting, unless you know of
a way to extract info from the emanations in practice in a real system,
not just in theory.
Otherwise, it's like saying you can't make a perfectly soundproof
room: acoustic energy will always travel through the walls and radiate
into the outside world, or if you surround the room completely by
vacuum, there still have to be some floor mountings. Does that mean
there's a way to eavesdrop on conversations happening in the Kremlin
right now, using microphones where you're sitting thousands of miles
away? If not, the theoretical issue is irrelevant.
I do remember hearing that a lot of design effort in the IBM 4758
crypto module (which I think right now is still the only reasonably
accessible FIPS 140-1 level 4 certified device) went into suppressing
leakage in the area where signals came out of the sealed part of the
module and out to the PCI connector. I talked with the 4758 designers
a little and they said they themselves knew no way to compromise the
internal keys.
Also, the module's shielding might not be 100% perfect, but it's
pretty good, and the module itself is usually inside a box with the
rest of the computer generating tons of electrical noise, and the
computer is in a room full of other equipment generating noise, and
the equipment is all in a locked room in a secured building
(www.sas70.com). So the chances of somebody outside with a van full
of electronics pulling secret keys out of the air seem close to zero.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: The Art of Cryptography (was: Super strong crypto)
Date: 16 Mar 2001 02:10:25 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
John Savard wrote:
>Thus, to design a cipher that is adequate where high security is
>desired, it is *necessary* to extend one's reach into the realms where
>cryptography ceases to be a science, and becomes an art.
What was the matter with the GGR scheme I described? It gives a provably
secure way for doing what you want, under precisely specified assumptions.
Sounds like science to me, not art.
In more detail: Under the assumption that the block cipher is secure
against all known-plaintext attacks where the adversary gets only one
block of known plaintext, the GGR scheme is secure against all efficient
chosen-plaintext/ciphertext attacks (without restriction on the number
of chosen texts the attacker can ask for).
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: What do we mean when we say a cipher is broken? (Was Art of
Date: Fri, 16 Mar 2001 02:03:13 GMT
Jim Gillogly wrote:
> William Hugh Murray wrote:
> >
> > John Savard wrote:
> >
> > > On Thu, 15 Mar 2001 22:35:51 GMT, William Hugh Murray
> > > <[EMAIL PROTECTED]> wrote, in part:
> > >
> > > >I am not at all sure what you mean by "broken." Do you mean that the cost
> > > >of recovering a message without benefit of the key suddenly falls to
> > > >zero?
> > >
> > > A cipher is broken when that cost is less than infinity.
> >
> > Well, I suppose the definition has the advantage that it is binary. However,
> > since it includes all of the ciphers in history, and since you cannot
> > demonstrate that, by this definition, there is an unbroken one, it is simply
> > not interesting.
>
> My definition is that a cipher is broken when the cost of cryptanalyzing
> a set of messages is less than the cost of obtaining the information in
> them by some other means. The cost is measured in some appropriate unit --
> perhaps wall clock time, money, lives, person-hours, or whatever is useful
> for valuing that specific information.
>
> > I hope that you cryptographers have fun with your abstraction but it is not
> > particularly useful to security people.
>
> Hope you like mine better.
Yes, I do like it better. It is a security answer.
I say, "A cipher is clearly insecure when the of cost of a cryptanlyitic attack is
lower than the value of success." I normally measure the cost of attack as work,
access, indifference to detection, special knowledge, and time to detection and
corrective action (WAIST). The value of success can be measured in dollars or
alternative values such as vengeance.
Because vengeance is hard to measure and crypto is cheap, I use it in such a way as
to raise the cost of attack several orders of magnitude higher than the value of
success.
> --
> Jim Gillogly
> Sterday, 24 Rethe S.R. 2001, 01:32
> 12.19.8.0.19, 6 Cauac 2 Cumku, First Lord of Night
------------------------------
From: br <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Thu, 15 Mar 2001 21:05:13 -0400
It will reduce little bit a redundancy. So compression is better.
Is there any other way other than compression. That's my question.
Mok-Kong Shen wrote:
>
> br wrote:
> >
> > I'm trying to find any document about how to eliminate the redondancy of
> > english language (except compression algorithm).
> > Is there any work about this question?
>
> Writing in the 'telegram style' could correspond to
> your need, I suppose.
>
> M. K. Shen
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Computing power in the world
Date: Fri, 16 Mar 2001 02:18:13 GMT
Ichinin wrote:
> MIPS Years is a well known measurement of a machine running at 1 Mips
> (i.e. ~386sx25) for a lenght of (you guessed it) a year. 2 mips years
> would require 2 such computers.
Sorry. My bad. I was thinking MIPS * years wound up with a time^2 unit
rather than having the times cancel out. Nevermind.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Fri, 16 Mar 2001 02:25:59 GMT
"br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> It will reduce little bit a redundancy. So compression is better.
> Is there any other way other than compression. That's my question.
Lossy or non lossy?
Tom
------------------------------
From: br <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Thu, 15 Mar 2001 21:40:36 -0400
Non lossy of course.
Tom St Denis wrote:
>
> "br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > It will reduce little bit a redundancy. So compression is better.
> > Is there any other way other than compression. That's my question.
>
> Lossy or non lossy?
>
> Tom
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: primes for BBS
Date: Fri, 16 Mar 2001 02:53:35 GMT
On 15 Mar 2001 12:16:04 -0800, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] wrote:
>Benjamin Goldberg <[EMAIL PROTECTED]> writes about BBS:
>>
>> Note that p, q, don't just have to be primes, they have to be *special*
>> primes (specifically "Blum integers" which are prime, aka "Blum
>> primes"), and when picking a starting value for x, you have to make sure
>> that it does not produce a short cycle.
>
>All true until the last part. You don't have to check that x doesn't
>produce a short cycle. If you ever find an x that produces a short
>cycle, you have cracked RSA and factored a 1024 bit modulus! If you
>believe that RSA with a 1024 bit modulus is secure, you don't have to
>check for short cycles. If short cycles can be found, RSA is insecure.
Note the logic error above: If the sender does choose a short cycle,
N *can* be factored. That is not an ability to factor N at will; that
is a weakness deliberately allowed to exist. It is argued that such a
thing hardly ever happens.
A similar problem occurs in any system which has weak keys: typically,
the implementor gets to decide whether checking for weak keys is
worthwhile. The difference here is that the result is supposed to be
"mathematically proven," so that users probably think it is
indisputably secure. The proof, however, works asymptotically, over a
huge universe of possible x0's. So if the sender "lucks out" and the
system chooses a short-cycle x0, the resulting cipher is unarguably
insecure anyway. That is not something the opponents must do to
factor N; that is something the sender does for them.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Fri, 16 Mar 2001 03:03:23 GMT
"br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Non lossy of course.
Then you are looking for an information presevering method of compacting
data. Sounds like compression to me.
Maybe you just don't get what you are asking.
Tom
>
> Tom St Denis wrote:
> >
> > "br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > > It will reduce little bit a redundancy. So compression is better.
> > > Is there any other way other than compression. That's my question.
> >
> > Lossy or non lossy?
> >
> > Tom
------------------------------
** 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
******************************
