Cryptography-Digest Digest #38, Volume #12 Thu, 15 Jun 00 16:13:01 EDT
Contents:
Re: Finding prime numbers (Bryan Olson)
Re: Cipher design a fading field? (James Felling)
Re: Cipher design a fading field? ("Trevor L. Jackson, III")
Re: My lastest paper on Block Ciphers ("Beth Friedman")
Re: Random sboxes... real info ("Paul Pires")
Re: Is Gretchen down? ("Trevor L. Jackson, III")
Re: Random sboxes... real info (zapzing)
Re: GeekPress: Will Cyber Criminals Run the World? (zapzing)
Re: hmac and 'length' issues ([EMAIL PROTECTED])
Re: Observer 4/6/2000: "Your privacy ends here" (Colin)
Re: small subgroups in Blum Blum Shub (James Felling)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Finding prime numbers
Date: Thu, 15 Jun 2000 18:55:21 GMT
Scott Fluhrer had written:
> > > then you need to show that the gap between a prime p
> > > and next prime (the number of loop iterations) is
> > > bounded by a polynomial in log(p).
Anton Stiglic wrote:
> Even better: there is a prime between p and p + 1/5p,
> for primes p > 9.
[...]
> but these gaps are polynomial in p, not log(p).
Yes, I overlooked just that. Scott is right that this
is a flaw in my argument. We can say that for random
n, next_prime(n) is average-case polynomial in the size
of n, but the hypothesis of a constant-time next_prime
didn't say what case and the usual default is worst-case.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Thu, 15 Jun 2000 14:10:36 -0500
John Savard wrote:
> On Tue, 13 Jun 2000 21:21:52 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote, in part:
> >Tim Tyler wrote:
>
> >> If the size of the program is constrained, a halting determination program
> >> could be written which enumerates all programs of that size or shorter and
> >> lists whether they halt or not.
>
> >It "lists" them how?
>
> Well, if the size of the RAM available to a program is limited, not
> just the size of the program itself, then a program with N bits of
> storage available to it can have only 2^N distinct states. Hence, if
> it doesn't halt after 2^N instructions, it is proven that it will
> never halt.
That is true, to a point. It runs into the problem however of false
halts/indeterminate states where internal values overflow the RAM ( i.e. the
program would halt if there was more available space, but there is not...).
If one sulficiently constrains the system the halting problem may be resolved
relative to that system, but not relative to the programs being evaluated. If
the system is finite in all respects one may determine ( using a larger system
the behavior of any program that can run upon that system, but you get 3
possible evaluations (halts, doesn't halt, produces error condition) and you
really cannot claim that "produces error condition" is a "halt" in the clasic
halting problem sense.
>
>
> A program that is quite short could indeed implement a slow algorithm
> for trying to find, say, a counterexample to the Goldbach conjecture.
>
> But the proof of the halting problem being insoluble depends on one
> being able to write a program that checks to see if other programs
> halt. To prove that no such program can exist, one has to be able to
> write big programs: otherwise, one has just proven that the program
> can't be small.
>
> I think, when searching to find whether it was Turing or someone later
> who came up with the proof I recited, I came across the LISP program
> you mentioned. It is illustrative - it shows that a program, trivially
> trying to check if a program will halt by running it, gets into
> trouble if it tries to run a copy of itself. That is true, but it
> isn't directly involved in the proof: a program trying to do the much
> more difficult *opposite* task is what is being discussed.
>
> John Savard (teneerf <-)
> http://www.ecn.ab.ca/~jsavard/
------------------------------
Date: Thu, 15 Jun 2000 15:27:08 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Tim Tyler wrote:
> Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
>
> [much snip]
>
> : The key question becomes whether the program can be written small enough
> : to fit within itself (this is a data compression issue). If so then the
> : Halting Problem can't be constructed because such a lookup program will
> : halt after reporting that it will do so.
>
> While the issue of whether the table can be compressed to the size of the
> programs whose status it lists may have some curiosity value, I can't see
> it as a key question - since the halting problem doesn't exist for
> any particular finite set of programs anyway - regardless of how much
> the list mentioned can be compressed.
>
> There /will/ exist some (possibly very large) finite program that says
> which programs from the specified finite set terminate.
>
> This is a different case from that presented by the halting problem -
> which says that no such program can possibly exist.
Yes.
However, the halting problem is typically constructed by applying a program to
itself (halting if the program it's analyzing does not). If the lookup
program is too large to apply to itself, then the construction is impossible
by the premises of the problem rather than by the undecidable behavior. If
the program is small enough to fit within its lookup table then it can be
applied to itself, but will always halt, thus demonstrating decidable
behavior.
There's a deep connection to class-of-all-classes paradoxes that disappears
when the metaclass isn't required to be an element of the base class it
categorizes.
------------------------------
From: "Beth Friedman" <[EMAIL PROTECTED]>
Subject: Re: My lastest paper on Block Ciphers
Date: Thu, 15 Jun 2000 14:15:57 -0500
Runu Knips wrote in message <[EMAIL PROTECTED]>...
>Anton Stiglic wrote:
>> If you compile a .ps on one machine, you might not be able to get
>> the .pdf on another.
>
>Where did you get THAT idea ? .ps is as device independent as .dvi.
Yes and no. PostScript is device independent for printing, but I've had
times when I tried to generate a PDF from a PS file where I didn't have the
fonts used in the file on my system. The PDF would generate okay, and print
okay, but it looked like hell on the screen. See
http://www.counterpane.com/audit-logs.pdf for the sort of thing I mean.
>> If you start out with the .dvi format (which you get out of latex),
>> then you can get a .ps and .pdf on any machine.
>
>.ps is Postscript, and Postscript is a page description language.
>The only problem you might get is if you have not stored a font in
>the .ps and the other machine doesn't have it either.
Exactly. Does saving a file as .dvi allow you to generate a readable PDF on
another machine if it's missing the fonts?
--
Beth Friedman
[EMAIL PROTECTED]
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Random sboxes... real info
Date: Thu, 15 Jun 2000 12:23:24 -0700
I heard (i.e didn't pay attention to the source, probably the Discovery
Channel) that this was one of the failings of Enigma. The machine was
designed so that the output character could never be the input character &
therefore was flawed since potential settings could easily be excluded with
a small crib. Is this the kind of thing you mean?
Paul
David A. Wagner <[EMAIL PROTECTED]> wrote in message
news:8ib68s$heo$[EMAIL PROTECTED]...
> Nope, I stand by my statement.
>
> You might want to think about this more carefully. Here's a useful
> thought experiment. Consider the following two universes:
> Universe A: We encrypt using a permutation chosen uniformly at random
> from the set of all permutations.
> Universe B: We encrypt using a permutation chosen uniformly at random
> from everything but the identity permutation.
> I claim that (A) is strictly stronger than (B).
>
> The way to think about this is to look for an attack that lets you
> read encrypted traffic. If you can find an attack which works strictly
> better against (A) then (B), you will have proven your point. I claim
> you can't. Have a try! :-)
>
> To give a feeling for it, let me debunk the proposed attack you sketched:
>
> > An OTP is used once. A block cypher may potentially be used to encypher
> > *many* blocks. If the permuting transform used is the identity
> > transformation, the analyst is likely to notice this at once in (say)
ECB
> > mode. The cyphertext *is* the original plaintext. *No* other
permutation
> > would have this effect over a number of blocks of differnet plaintext.
>
> Careful here! I think you haven't thought this through deeply enough.
>
> Consider, as a representative example, the following scenario. You have
> some known plaintext/ciphertext pairs; let's say you know that "foo"
> encrypts to "foo", and "bar" encrypts to "bar". Now you have a third
> ciphertext C of unknown decryption, and you want to find the corresponding
> plaintext P. (If you can't find any information P, you don't have an
attack.)
> What possibilities are there for P?
>
> Obviously, P can be anything except "foo" and "bar". Moreover, in (A),
> all the possibilities are _equally likely_. The reason is that all
> (2^n - 2)! permutations of the remaining 2^n - 2 elements of the plaintext
> space can be permuted in every way, and each such possibility is equally
> likely. In other words, we get _no_ information whatsoever on P, in
> Universe A.
>
> Universe B, however, is slightly different. The identity permutation
> is impossible in (B), so only (2^n - 2)! - 1 of the permutations of the
> remaining elements are possible. In other words, P has an ever-so-slight
> bias: Prob[P=C] < Prob[P=x] for all x != C. So, in Universe B, we do get
> a teeny bit of extra information on P: the values other than "foo", "bar",
> and C are slightly more likely to be the plaintext than C is.
>
> (If this isn't clear, go do the math, crunch the numbers, and compare.)
>
> This shows that your proposed attack does not in fact work; you get more
> information about the unknown plaintext if the identity permutation is
> excluded than if the identity permutation is permitted.
------------------------------
Date: Thu, 15 Jun 2000 15:39:17 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Subject: Re: Is Gretchen down?
Read some history re transatlantic cables. The telegraph companies swore that the
messages were private, but everything was copied to the appropriate government
agency.
What do you think has changed since then?
Patrick Farrell wrote:
> Thanks for the input on the first few points.
>
> Well you would think that they would need permission from the carriers to do
> this. I mean you can't even splice into a 10baseT connection without issues, I
> don't see how you could tap into a fiber connection without having the carrier
> do it for you, but maybe they just don't release that technology to the public
> :)
>
> If they were having the carriers do it, I would find it hard to believe that
> with the ammount of people that would be involved at each major carrier that
> they could keep the secret of these taps from the public.
>
> Patrick
>
> Joseph Ashwood wrote:
> >
> > > A) you need a pipe equivilant to the sum of the major backbones.
> > Not if you have a significant computer present at each of those backbones
> > that performs a significant portion of the filtering for you, then you would
> > only need a much smaller pipe. Also remember that the vast majority of hose
> > pipes remain unfilled almost all the time.
> >
> > >
> > > B) you need a computer or cluster that can read and filter on the fly this
> > > ammount of information
> > Which can be done, for proof I simply point to the fact that these pipelines
> > are running, so it can obviously be read. The traffic is being generated by
> > a small portion of the cpu in a small portion of the computers in the world,
> > a trojan would be an ideal way to get the processor time needed, after all
> > the attack is obviously not bounded by lawfulness.
> >
> > >
> > > C) you need a network interface for a data pipe that doesn't exist.
> > Except that by segmenting the necessities you require much smaller network
> > interface, on a much smaller pipe.
> >
> > >
> > > D) how does a system with IP range A, on subnet B, see data between
> > systems C
> > > and D with completely seperate subnets when the data is never even routed
> > across
> > > A's network. Unless you are implying that they have a vampire tap on
> > every
> > > major circuit and subcircuit that duplicates all traffic and then reroutes
> > it to
> > > their hosts.
> > They would be forced to have a vampire on each of the major backbones, or at
> > least the ones with anything of interest. It would be a massive undertaking,
> > cost a hundred million dollars or so (just a very rough guess), but it is
> > possible. The next questions should be: what are the necessary backbones?
> > where is the best location to tap them?
> > Joe
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Random sboxes... real info
Date: Thu, 15 Jun 2000 19:19:55 GMT
In article <8i7smf$mvo$[EMAIL PROTECTED]>,
Rex Stewart <[EMAIL PROTECTED]> wrote:
> I don't see anything wrong with putting one part or another
> under a microscope. Most of the progress in this field is
> accomplished by dissecting constructions into thier parts,
> looking for peculiarities in each part and then seeing if a
> peculiarity will provide a weakness in the overall construction.
>
> Also, he seems to be placing several parts under the microscope
> this month - as you noticed, he is also seeing how these s-boxes
> work in constructions (see your own last paragraph).
> (Frankly I don't see how he covers so much ground in such
> a short time)
I must confess I didn't follow it all exactly,
and I could be wrong, but I didn't see
anywhere where he tried using large key
dependent sboxes.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: GeekPress: Will Cyber Criminals Run the World?
Date: Thu, 15 Jun 2000 19:25:29 GMT
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
> zapzing wrote:
> > If you know about a retail source of
> > inexpensive DES chips, please let
> > me know, thanks.
>
> You can get DES and 3-DES cores for about $10k. See Xilinx and
Xentec.
> www.xilinx.com/ipcenter has data sheets.
Hmmm ... $10K? Well I was thinking more in
the range of 100-200 dollars. I don't
need to do several Mbits per second, only
say about 1/100 of that.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: hmac and 'length' issues
Date: Thu, 15 Jun 2000 19:40:02 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> HMAC prevents this type of attack because a direct hash of the message
> is not exposed:
David, thank you. :)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Colin)
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,alt.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: 15 Jun 2000 19:31:05 GMT
On Thu, 15 Jun 2000 10:47:30 +0200, Mok-Kong Shen wrote:
>
>
>Paul Shirley wrote:
>
>> Mok-Kong Shen <[EMAIL PROTECTED]> writes
>> >The scheme is for use with arbitrary texts from books, e.g. religious
>> >ones, and newspapers and such stuffs and doesn't carry any secret
>> >messages. Its purpose is only to waste and hopefully exhaust the
>> >resources of the interceptors. I originally had that idea in a thread
>> >of sci.crypt discussing better ways (than incorporating sentitive
>> >words into e-mails) of jamming Echelon and similar machineries.
>>
>> Then you've missed the point of monkey wrenching RIP. It does not matter
>> what the message is, only that its been encrypted. If it has been
>> encrypted the options for 'wasting time' are severely limited. Either
>> you hand the key over or go to prison.
>
>You didn't read a previous post of mine which had a bit detail saying
>that the key, a seed of a PRNG, is sent as a prefix to the ciphertext.
>So handing over the key is trivial and I remain outside of the prison :)
You could also modify your method to serve as an offbeat steganographic
algorithm:
If you were feeling malicious, you wouldn't use a 'set text' - you'd
start with a one byte message (e.g. "G"). Get your 'key' from a genuine
RNG, and use it to seed the PRNG to encrypt your one-byte file.
Then you'd get another 'key' for the PRNG from the RNG and encrypt the
cypher-text + the first key. Then repeat the process a few hundreds of
thousands of times.
The Men In Black have no reliable way of telling whether or not, at
iteration n, there is a genuine cypher-text - if there is, it would
still unvravel to an arbitrary, single byte 'plaintext' if the reverse
algorithm were applied to it.
Are they going to serve you with warrants to disclose the 'key' to
all of the thousands of possible cypher-texts in the document, in the
vague hope that one of them will decode to something incriminating?
They have to decide for themselves whether the file contains one byte
of information + 100k of junk, 100k of encrypted information + no junk,
or something in between. Then a judge has to be convinced of their
reasons for beliveing this.
Regards, Colin.
--
"It's the only thing I can't lie about."
Tony Blair, on cooking (CEEFAX 1 p146-1, 8/4/00).
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 14:50:27 -0500
tomstd wrote:
> In article <[EMAIL PROTECTED]>, Nicol So
> <[EMAIL PROTECTED]> wrote:
> >Terry Ritter wrote:
> >>
> >> On Wed, 14 Jun 2000 18:08:23 -0700, in
> >> <[EMAIL PROTECTED]>, in sci.crypt
> lordcow77
> >> <[EMAIL PROTECTED]> wrote:
> >>
> >> >Essentially, the existence of exploitable cycles in BBS would
> >> >neccesarily lead to an efficient algorithm for decomposing
> RSA
> >> >moduli into primes. As such, if you believe that the
> factoring
> >> >of numbers in that range is a difficult problem, you need not
> >> >loose sleep over the miniscule probability that you will
> land in
> >> >a short cycle. The nonsense about choosing "strong primes" or
> >> >good initialization values is a remnant to the past where it
> was
> >> >thought that a relatively small prime (if well chosen) would
> be
> >> >adaquately strong.
> >>
> >> I think your interpretation is wrong, and I recommend the
> BB&S paper
> >> to you:
> >>
> >> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-
> Random
> >> Number Generators. Advances in Cryptology: CRYPTO '82
> Proceedings.
> >> Plenum Press: New York. 61-78.
> >>
> >> BB&S did expect large primes; the requirement for "special"
> primes was
> >> to guarantee that the system had cycles of some long, known
> and
> >> computable length. The existence of cycles of known length
> made it
> >> possible to efficiently check that any particular initial
> value x0 was
> >> on such a cycle, and to choose another x0 if not. Short
> cycles
> >> certainly do exist in BB&S, and short cycles
> are "exploitable." The
> >> selection procedure thus eliminates the possibility that x0
> is on a
> >> short cycle, and so provides a *guarantee* of that form of
> strength.
> >> That sort of a *guarantee* is simply not present when we just
> choose
> >> x0 at random and hope for the best, even if x0 is very, very
> likely to
> >> be on a long cycle.
> >
> >lordcow77's interpretation is correct. The safety of using
> randomly
> >chosen primes of appropriate sizes is built into the underlying
> >intractability assumption. To put things in perspective, the
> whole point
> >of using cryptography is to reduce the probability of "bad
> things
> >happening" to some acceptably low level, say 2^{-L} for some
> >sufficiently large L. (There's no defense against dumb luck on
> the part
> >of the adversary). Not using special primes may affect the
> value of L
> >for a given choice of security parameter (so you may have to
> adjust your
> >security parameter), but it does not affect the asymptotic
> behavior of
> >security as a function of the security parameter.
>
> I don't know why people still consider the BBS generator. It's
> not very safe.
>
> Let's ask some questions:
>
> 1. How do you use it? Well construct "special" primes and use
> a relatively prime root. I have seen to use 3 mod 4 primes and
> p- strong primes...
>
> 2. What is the period? Gosh-geez I dunno, pretty darn big!
>
> 3. How fast is it? Well at 2kb/sec we now have the fastest
> prng.
>
> Woopy. It's hard to use, big and slow. BAD IDEA!
>
> Tom
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
> The fastest and easiest way to search and participate in Usenet - Free!
Yes, it is big, ugly and slow. OTOH it is provably as good as the underlying
intractible problem, and it is one of the only PRNG's with that property.
Given we want something PROVABLY difficult to attack with a long period, it
really is the only game in town. Sure it isn't a great game, but its all that is
available.
------------------------------
** 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
******************************
