Cryptography-Digest Digest #452, Volume #12 Tue, 15 Aug 00 16:13:01 EDT
Contents:
Attacking TC5 (tomstd)
Re: OTP using BBS generator? (David Hopwood)
Re: OTP using BBS generator? (Doug Kuhlman)
Re: Crypto Related Professional Attitude (Mok-Kong Shen)
Re: Looking for password statistical data (Mok-Kong Shen)
Re: OTP using BBS generator? (Mok-Kong Shen)
Re: OTP using BBS generator? (Mok-Kong Shen)
Re: OTP using BBS generator? (Mok-Kong Shen)
Re: OTP using BBS generator? (Mok-Kong Shen)
Re: Unauthorized Cancel Messages (Jim)
BBS agreement? (Doug Kuhlman)
Re: Unauthorized Cancel Messages (Mok-Kong Shen)
Re: BBS agreement? (Mok-Kong Shen)
Re: What is up with Intel? (Sander Vesik)
Re: Crypto Related Professional Attitude (Ichinin)
Re: Copyright isue - SERPENT ("Tor Rustad")
Looking for a DES or RSA chip with write-only key. (Sniggerfardimungus)
----------------------------------------------------------------------------
Subject: Attacking TC5
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 15 Aug 2000 11:12:13 -0700
I agree and understand that the four round impossible
differential can work against the 128-bit feistel without too
much gut work.
However, to suggest keys or extract them you have to attack the
lower feistels.
So how would this attack proceed to unsuggest keys?
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Date: Wed, 16 Aug 2000 06:57:40 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: OTP using BBS generator?
=====BEGIN PGP SIGNED MESSAGE=====
Terry Ritter wrote:
> In BB&S we don't get the full state output, but we do get a bit of it,
> and if we record that sequence and compare it to the incoming data,
> presumably we can find a match. (There is a potential lead-in prior
> to getting on a cycle, but I think that is limited to a single step.)
There is no potential lead in. If x is the seed then the first bit output
is the LSB of x^2 mod N, not the LSB of x. Since x^2 is a quadratic
residue, it falls on a cycle.
- --
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
iQEVAwUBOZllKDkCAxeYt5gVAQHW0QgAnIPrQA0pudhmiGrtRseBYRusP1cEVgQ5
PCNtgUt29NWM0cI8I/ywIFSG3yBrb8hG6QZA5NtjchjSPy3eEOnc2oPWVt8TenI7
SmQCVwEzCX7rXbEZVf/S5Vh26PPZFH9++2lGmTDua30pdJYQP7UhBpZk3H2D/4H5
qFCOJB4KUCoeiZ7fRHX75pcsVoNvpymFo3CHRxPbjt+ArVDjnqqK94FlKfD+6Ddo
4D2t0TiCTNwmTnOz9sTkQYhhdqfT34HEN9z19FzxuAzcNh5k4rhlvGDb5gbR3OoR
Jt2JZxo1ocauy12w+zeyYbRXIy7XOPNlFySYfRiyzZqtbBet4unNeg==
=owO+
=====END PGP SIGNATURE=====
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Tue, 15 Aug 2000 13:40:38 -0500
Terry Ritter wrote:
>
> On Thu, 10 Aug 2000 13:51:58 -0500, in
> <[EMAIL PROTECTED]>, in sci.crypt Doug Kuhlman
> <[EMAIL PROTECTED]> wrote:
>
> >Terry Ritter wrote:
> >>
> ><SNIP>
> >>
> >> No; a "negligable probability" means that some probability remains.
> >> And with random selection, that result will eventually occur.
> >>
> >You should know better than that. The probability that the sound of air
> >coming through a naturally shaped tunnel will play the entire
> >VeggieTales collection is non-zero, but it's not gonna happen in the
> >lifetime of the universe. Same thing applies here.
>
> Sorry, but *you* should know better than that. None of this is about
> weakness in practice, it is about falsely appearing to claim strength
> on the basis of mathematical proof. The short-cycle weakness is a
> theoretical weakness in the sense that it almost never occurs in
> practice. But it is a practical weakness in the sense that the reason
> to use BB&S in practice is to achieve the results of the theoretical
> claim. But theoretically, if long cycle operation is not guaranteed,
> short cycle operation will occur, and the "proven secure" system will
> be insecure, sooner or later.
> <SNIP>
> Nope, that seems to be *your* problem: Possibility and probability
> are statistical terms. If something is *possible* under random
> selection, it eventually *will* *happen*. This concept is important
> and you need to understand it. The same concept occurs in computer
> programming.
>
>
First you argue that you're not claiming it's a weakness in practice and
less than a page later, you're trying to claim that it will happen.
Which is it?
Can you pick the right atom of the Earth in the exact millisecond of the
day? Your odds of landing on a short cycle are worse. "Can happen" is
not the same as "will happen". Lots of things can happen, very few
actually do or even will happen.
> <SNIP>
> So, basically, you are fine with changing the current description of
> "proven secure," to "proven to have a negligible likelihood of
> weakness." That's not as straightforward as "almost always secure,"
> but it is an improvement.
>
Sure! Always a chance of weakness. Maybe some hotshot will figure out
how to factor arbitrarily large numbers in constant time. All kinds of
things are potential weaknesses. The possibility of landing on a short
cycle is the least of my concerns (about BBS).
Doug
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Crypto Related Professional Attitude
Date: Tue, 15 Aug 2000 21:21:13 +0200
Terry Ritter wrote:
>
> <[EMAIL PROTECTED]> wrote:
>
> >[...]
> >THe big names have alot on their plate, and since there are those on
> >these NG with a desire to "take down" a big name crypto guy, they are
> >much more prone to spam and nasty gram and other such counter posting
> >tendencies.
>
> I suppose there is some of that, but the whole point of a discussion
> is to *discuss*, and discussion here is commonly about *differences*.
> If the big name has been saying things which seem wrong, those issues
> need to be confronted, just like with anybody else. That can be a
> very abrupt change for someone used to adulation and passive general
> acceptance.
It is natural that the top experts are hardly experiencing
'oppositions' because they are almost always doing right
and as a result tend to be with time no longer accoustomed
to hearing differing opinions. But a genuinely great (as
against half-great) scientist should have no problems of
any kind, I believe, of encountering and appropriately
dealing with counter-arguments, if these do have some
weight from the view point of science.
A problem of having a big name is of course that one
becomes a centre of big attraction and that could be a
disadvantage. Being a nobody, I can at any time leisurely
walk down the main streets in my city and enjoy looking
at the shop-windows. But a film star would have been
impossible to do the same. This could be one, though I
would say a comparatively fairly minor, reason why a
number of the lustrous scientists in crypto never visit
our group.
M. K. Shen
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Looking for password statistical data
Date: Tue, 15 Aug 2000 21:21:19 +0200
Anders Thulin wrote:
>
[snip]
> As to password-by-dice, assuming full disclosure of
> password file: 8 digits in the range 1-6 can be tested in
> short order -- a 233 MHz PII computer manages around 3000 guesses/second,
I generate my password with a pair of dice (equivalent
to throw one die twice) to get first a number in [0,35]
and then map that to {a-z, 0-9}. I find that quite
practical.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Tue, 15 Aug 2000 21:21:23 +0200
Mark Wooding wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > I that case, I wonder, since one is using the LSB, what is the sense
> > of disputing long vs. short cycles. (We have NO idea at all of the
> > probability of getting cycles of LSB of any given magnitudes. Is that
> > right?)
>
> We know that finding cycles *of the LSB* is no easier than factoring!
My problem is in knowing the (rough) path of attaining that
knowledge, without having to deeply study the BBS article
which I guess is way beyond my capability. My thought is
this: BBS must proceed from the properties of the congruence
relation to that of the LSB. They presumably could have
first established that finding cycles of the direct output
of the congruence relation is no easier than factoring.
Since there is a gap in proceeding from the cycles of
this kind to the cycles of LSB, I conjecture there could
be some difficulties of continuing from the above point to
establish that finding cycles of LSB is no easier than
factoring.
Looking from another perspective, what does 'finding cycles
in LSB' mean? If the distribution of cycles lengths of LSB
is (of course I don't know) is such that the majority of
cycles are very short, then encountering a cycle would be
easy. So I conjecture that one has to be able to say
something definite about the distribution of cycle lengths
of LSB, if one can prove that finding cycles of the LSB is
no easier than factoring.
>
> > > No. The proof of unpredictability is a two-step thing:
> > >
> > > * firstly, it shows that, if you can predict a BBS generator with
> > > probability 1/2 + \epsilon then you can also decide quadratic
> > > residuosity with probability 1/2 + \epsilon;
> > >
> > > * and secondly, it gives a simple algorithm for `amplifying' advantage
> > > in deciding quadratic residuosity so that small biases can be used
> > > to efficiently solve QRP completely, in expected polynomial time.
> >
> > Does that refer to the LSB?
>
> Yes.
>
> > I guess that this is certainly the case. But then how can it be that
> > there is a 'gap' mentioned above without causing any consequneces in
> > the proof of the unpredictablity of LSB? Note what I wrote in
> > parentheses.
>
> Either finding such cycles, either by accident or malice, is neglibly
> difficult, or factoring is surprisingly easy. There is no `gap'.
Why is it then, as David Hopwood said, that BBS leave the
issue of the connection between the cycles of the direct
output of the congruence relation and the cycles of LSB
explicitly to be an open question? I surmise that that gap
or open question must have some non-trivial bearing on
the present issue.
[snip]
> > A tiny toy example of mine indicates, however, that LSB of BBS could
> > have poor statistical properties, though unfortunately the size of the
> > example doesn't allow much to be said concretely/strongly.
>
> That's because your modulus is too small. Your test is (and cannot be)
> polynomial time, and allows you to factor the toy modulus. But we know
> that's easy anyway, so the test tells us nothing new.
If a bit sequence has grave statistical defects, then
that can be readily exploited by the opponent, he wouldn't
then need any 'polynomial' time or what not for doing the
analysis. Or am I missing something?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Tue, 15 Aug 2000 21:21:32 +0200
Terry Ritter wrote:
>
> [EMAIL PROTECTED] (Mark Wooding) wrote:
>
> >Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >[...]
> >> (3) Does the 'check' being disputed really prevent a certian
> >> lower bound of the cycle lengths of the LSB sequences
> >> (not the direct output of the congruence relation) of
> >> being inadvertently 'under-run' or does the check only
> >> do that in a probabilistic sense (i.e. with certain
> >> probability not equal to 1)? What is that lower bound
> >> actually (in relation to p and q)?
> >
> >It doesn't do anything of the kind.
>
> That's a wrong answer: The construction as described in BB&S first
> guarantees that cycles of a given length must exist, and then shows
> how to check that x0 is on such a cycle. The check is thus absolute
> proof that a short cycle has not been selected.
Excuse me for being hardnecked in asking questions. Does
the phrase 'cycles of a given length' refer to cycles of
the direct output of the congruence relation or does it
refer to cycles of LSB. If it is the former case, then
the fact mentioned by David Hopwood implies that one
doesn't get results applicable to the cycles of LSB and
one would have a problem.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Tue, 15 Aug 2000 21:21:28 +0200
Terry Ritter wrote:
>
> I would say that I do have such an analysis, and it does back me up:
> If we use the BB&S construction, we are *guaranteed* not to use a
> short cycle. If we don't, then we are just very, very *unlikely* to
> use a short cycle. To me, the distinction is the essence of what we
> want from a proof of strength. If we were willing to accept a little
> weakness here and there, it seems unlikely that we would have much
> interest in cryptographic proof.
Please correct me if I am wrong. I guess that you have
investigated the cycle lengths of the direct output of
the congruence relation but not the cycle lengths of
the LSB, which could be comparatively much shorter.
Further there seems to be no 'apriori' reason that there
should exist a neat and simple relation between these
two types of cycle lengths.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Tue, 15 Aug 2000 21:21:38 +0200
Mark Wooding wrote:
>
> Terry Ritter <[EMAIL PROTECTED]> wrote:
>
> > That's a wrong answer: The construction as described in BB&S first
> > guarantees that cycles of a given length must exist, and then shows
> > how to check that x0 is on such a cycle. The check is thus absolute
> > proof that a short cycle has not been selected.
>
> No, it only shows the cycle length for the sequence <x_i>, not the
> sequence of parity bits.
Sorry, I am really confused. 'Parity bits' or 'LSB'? Thanks.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Jim)
Subject: Re: Unauthorized Cancel Messages
Date: Tue, 15 Aug 2000 18:11:22 GMT
Reply-To: Jim
On Tue, 15 Aug 2000 10:12:42 -0700, "Paul Pires" <[EMAIL PROTECTED]> wrote:
>It happens to my posts. They don't linger as long as most. I my case, it's
>probably a plus. I think it is just different behavior for different
>servers.
Could that be why, on some servers, I don't see my own
posts? Others do - obviously, because they reply to them,
but I only see my own posts when someone quotes me!
Just some newsgroups on some news-servers.
(Using Free Agent).
--
Jim Dunnett
amadeus at netcomuk.co.uk
nordland at lineone.net
g4rga at thersgb.net
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: BBS agreement?
Date: Tue, 15 Aug 2000 13:49:04 -0500
Hey all! I'd like to try to bring some of the BBS discussion to some
sort of agreed-upon conclusions. I *think* everyone has agreed to the
following:
1. Finding a cycle (any length) in BBS allows factoring the modulus
2. Long cycles *do* exist with properly chosen BBS primes
These two are a large part of the BBS paper.
3. Short cycles exist
4. The chance of landing on a short cycle is microscopic [1]
5. This chance is so small as to be unimportant in practice
I think we have agreed to:
6. Using BBS with no cycle check gives an attacker no advantage in
factoring
What is not agreed upon is the terminology to be used. This, while
important, seems to be the least of our concerns.
Doug
[1] We're not talking winning the lottery here. We're talking winning
the lottery on 20 consecutive drawings. Or we're talking of selecting
one atom from Earth and its atmosphere in one specified microsecond of a
century.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Unauthorized Cancel Messages
Date: Tue, 15 Aug 2000 21:38:39 +0200
"Ron B." wrote:
>
> It appears to me that someone is sending bogus cancel messages to
> sci.crypt and the alt.security.* groups. My newsreader shows several
> "This message is no longer available" messages for several legitimate
> messages. This are clearly not anti-spam cancels as they are new
> responses to postings. Has anyone else seen this?
The administrator of the news server sets, as far as I know,
the expiration periods, after which you either get an error
message on access as you reported or, at a much later date,
don't see the articles at all. On my news server, different
groups can have fairly different expiration periods.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: BBS agreement?
Date: Tue, 15 Aug 2000 21:45:09 +0200
Doug Kuhlman wrote:
>
> Hey all! I'd like to try to bring some of the BBS discussion to some
> sort of agreed-upon conclusions. I *think* everyone has agreed to the
> following:
>
> 1. Finding a cycle (any length) in BBS allows factoring the modulus
> 2. Long cycles *do* exist with properly chosen BBS primes
>
> These two are a large part of the BBS paper.
>
> 3. Short cycles exist
> 4. The chance of landing on a short cycle is microscopic [1]
> 5. This chance is so small as to be unimportant in practice
>
> I think we have agreed to:
>
> 6. Using BBS with no cycle check gives an attacker no advantage in
> factoring
>
> What is not agreed upon is the terminology to be used. This, while
> important, seems to be the least of our concerns.
Why are you so impatient? Couldn't you wait a little bit
till the BBS-thread become quiescent??
M. K. Shen
------------------------------
From: Sander Vesik <[EMAIL PROTECTED]>
Subject: Re: What is up with Intel?
Date: 15 Aug 2000 19:30:53 GMT
Jonathan Thornburg <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>>I recall hearing as long ago as 1983 about a small company
>>(whose name I have forgotten but would recognize if I heard)
>>that held the patent on use of XOR to undraw/redraw, as in
>>cursor bitmap images. Since this is obvious and essential
>>technology, it raised quite a stink when they tried to
>>collect royalties.
> Another such case... a company in Russia recently received a Russian
> patent on the combination of concave and convex surfaces, and surface
> thicknesses, in a beer bottle. They're currently trying to get 1.5%
> royalties from all the beer manufacturers in Russia. Sigh...
> [[no, this is not an urban legend... source is an article by a
> local resident in the most recent issue of the Manchester Guardian
> Weekly newspaper]]
Just it being unthinkably syrrealistic almost proves it.
Applying the patent is the difference between 'maffia' and 'maffia under
legalistic cover'.
> --
> -- Jonathan Thornburg <[EMAIL PROTECTED]>
> http://www.thp.univie.ac.at/~jthorn/home.html
> Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
> Seen on usenet (dueling .signature quotes):
> #1: "If we're not supposed to eat animals, why are they made of meat?"
> #2: "If we're not supposed to eat people, why are they made of meat?"
--
Sander
FLW: "I can banish that demon"
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Crypto Related Professional Attitude
Date: Tue, 15 Aug 2000 10:28:24 +0200
Hmmm... at least, AC hit the nail on the head:
25.11 Sci.Crypt
"..Most of the posts are nonsense, bickering, or both"
I do not see this newsgroup as serious, i see it as a
"playground" if, you all excuse me, for new ideas aka,
and a place to ask for information.
If i want to read about serious crypto stuff, i'll
simply order the newest cd from springer. For those
who want to learn about crypto, i suggest you ignore
the bickering of the "big shots" (if you people
pardon my choise of words), read all that is to read
from them and make up your own mind, since most ideas
have N-sides.
Example(s):
1. Most experts here say "Researched Static S-Boxes
are the best", because they have been taught that.
As a home researcher myself, having been taught
nothing, think that "self modifying code" is the best,
since it is harder to "lock your sights onto", and
some papers indicate that secret self-generated
s-boxes is a simple way to twart differential
cryptanalysis.
(I cannot tell which Sboxes are in use, you cannot
know which s-boxes are in use, because to know which
s-boxes are in use, you need to know the K, and
since the S-Boxes change, not position, but 100% of
their contence - this _MAY_ be VERY hard to analyse
depending on how you implement the S-Box modification
code.)
2. Previously, i also asked a question about if the concept
of randomness could be used to identify a secure output
sequence of all the crypto components (Keyschedule,
SBoxes + the rest of the stuff) and if you could use that
method on different types of data to determine what kind
of algorithm you'd use for application XYZ.
That idea was ridiculed by someone who clearly didn't
even understand what the hell i was talking about, and
someone else thought it was funny, i ask _WHY_?
What it comes down to: We all have different oppinions
and we should all respect them.
Regards,
Glenn
Crypto novice.
.SE
(P.S: One generic solution is not always the best,
diversity rules!)
------------------------------
From: "Tor Rustad" <[EMAIL PROTECTED]>
Subject: Re: Copyright isue - SERPENT
Date: Tue, 15 Aug 2000 21:53:00 +0200
"Runu Knips" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tor Rustad wrote:
> > "Runu Knips" <[EMAIL PROTECTED]> wrote in message
> > > Tor Rustad wrote:
> > However, I favor Serpent most.
>
> Which is the slowest in software. However, you're
> starting to make me fan of Serpent instead of
> Twofish ;-).
If the AES winner is going to be as big success as DES has been, I really think
a good HW implementation is important. In fact I miss a comparison with 3DES
which will be final competitor to the AES winner.
BTW if DES had been equally fast in SW, the industri would have needed to change
to 3DES sooner...slow in SW can be a benefit. ;-)
> > > > So if RC6 is choosen anyway, they have to choose another
> > > > winner aswell.
> > >
> > > IMHO the main advantage of RC6 over the other
> > > algorithms is that it is that easy to implement
> > > in SW on ordinary PC hardware.
> >
> > I can't see the importance of this, but RC6 has
> > very good performance in SW,
>
> No. On most architectures (exception for example
> Intel Pentium II with its fast multiplication) it
> is slower than Twofish and Rijndael
Ooops. You are right, to my excuse I tested RC6 myself on a Pentium Pro and my
reference chipher is (of course) Serpent...
--
Tor
------------------------------
From: ronb.cc@usu@edu (Sniggerfardimungus)
Subject: Looking for a DES or RSA chip with write-only key.
Date: 15 Aug 00 14:01:00 MDT
I'm looking for a DES or RSA chip with one unique quality - I want to be able
to burn the key into the thing and have it permanant and non-readable... in
some physical fashion, the key on the chip needs to be inaccessible. Is there
any IC out there that does this, or am I going to have to go to the drawing
boards on this one?
rOn (note the email address munging.)
------------------------------
** 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
******************************
