Cryptography-Digest Digest #555, Volume #13 Fri, 26 Jan 01 09:13:01 EST
Contents:
Re: William's P+1 (Bob Silverman)
Re: Dynamic Transposition Revisited (long) (Mok-Kong Shen)
Re: William's P+1 ([EMAIL PROTECTED])
Re: What do you do with broken crypto hardware? (John Veldhuis)
Re: Dynamic Transposition Revisited (long) (Mok-Kong Shen)
Re: What do you do with broken crypto hardware? (Paul Rubin)
Re: Paranoia ([EMAIL PROTECTED])
Re: Cryptographic Camouflage (Mok-Kong Shen)
Re: Dynamic Transposition Revisited (long) (Rob Warnock)
Re: Fitting Dynamic Transposition into a Binary World (Rob Warnock)
Re: What do you do with broken crypto hardware? (John Veldhuis)
Re: Why Microsoft's Product Activation Stinks (Richard Heathfield)
Re: Producing "bit-balanced" strings efficiently for Dynamic Transposition (Rob
Warnock)
----------------------------------------------------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: William's P+1
Date: Fri, 26 Jan 2001 12:39:25 GMT
In article <94n6eq$lhj$[EMAIL PROTECTED]>,
"The Death" <[EMAIL PROTECTED]> wrote:
> I saw several websites, and they all mentioned this algorithm but
didn't
> have any info about it. Can any1 give me information about this
algorithm?
It finds a factor p dividing n if p+1 only has small prime
factors.
It only works 1/2 the time even when p has the required property.
(you choose a Lucas sequence. It succeeeds iff the discriminant is a
non-residue mod p)
It is obsolete.
What more would you like?
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Fri, 26 Jan 2001 13:56:11 +0100
Mok-Kong Shen wrote:
>
> Terry Ritter wrote:
> >
[snip]
> My knowledge is too meager to enable me to offer more
> points than I have already done. However, it is my
> impression that your arguments todate somehow (I have
> no definite idea of that) need strenthening, if DT is
> to be accepted as on a par with the theoretical OTP
> (which seems to be your goal), in particular by the
> academics, assuming DT has in fact that property.
> (Apology, if my open words are inappropriate in some
> way.)
After some re-thinking, I do like to elaborate a little
a previous point of mine concerning the question of
perfectness of DT.
Suppose we have block size of n and we agree not to use
the non-balanced groups of bits but only the balanced
ones to transmit informations (in other words, we have
an 'alphabet' of a certain size m that is less than n). This
serves to separate out the issue of bit balancing in order to
simpify the argumentation below.
Now what we have is the following: Given an information block,
we do permutations of its bits to produce an enciphered block
with the help of a PRNG. A PRNG never provides a perfect bit
sequence in the sense used in the context of the theoretical
OTP. How can it be that this imperfectness does not manifest
itself in some form (possibly in certain very much reduced,
practically entirely negligible, intensity) AT ALL in our
encryption result? Let's order all the distinct balanced bit
groups into a sequence S and feed repetitions of S into our
algorithm. This input is evidently perfectly predictable. Can
the output be perfectly unpredictable? It certainly cannot.
For the PRNG has a finite period and hence the ciphertext
must cycle ultimately. This shows that, while DT could be
practically very secure (an issue that certainly merits
careful study before its being used in practice), it cannot
offer perfect security that pertains to the theoretical OTP.
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: William's P+1
Date: Fri, 26 Jan 2001 12:45:54 GMT
In article <94n6eq$lhj$[EMAIL PROTECTED]>,
"The Death" <[EMAIL PROTECTED]> wrote:
> I saw several websites, and they all mentioned this algorithm but
didn't
> have any info about it. Can any1 give me information about this
algorithm?
>
>
There's a description in "A Survey of Modern Integer Factorization
Algorithms" CWI Quarterly, v.7 (4), 1994, pp. 337 - 365, by Peter
Montgomery which is available here:
http://ftp.cwi.nl/ftp/CWIQuarterly/1994/7.4/Montgomery.ps.Z
Chris
Sent via Deja.com
http://www.deja.com/
------------------------------
From: John Veldhuis <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: Fri, 26 Jan 2001 13:01:33 GMT
Paul Rubin wrote:
> =
> I'm wondering if anyone else here is using crypto hardware modules for
> key management. What do you do if one malfunctions? Throw it into a
> blast furnace? Send it back to the manufacturer for warranty
> repair/replacement, with your secret keys inside?
I just send it back to the manufacturer. The moment it is tampered with
(eg. removed from a computer) all keys are erased. That=B4s what the
tamperproof-part is for. I have to add that the manufacturer is the
Belgian Utimaco branch, and I work at the Dutch branch. =
Regards,
John
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Fri, 26 Jan 2001 14:06:48 +0100
Errata to my previous follow-up:
''an 'alphabet' of a certain size m that is less than n''
should read
''an 'alphabet' of a certain size m that is less than 2^n''
M. K. Shen
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: 26 Jan 2001 05:09:58 -0800
John Veldhuis <[EMAIL PROTECTED]> writes:
> I just send it back to the manufacturer. The moment it is tampered with
> (eg. removed from a computer) all keys are erased. Thatīs what the
> tamperproof-part is for. I have to add that the manufacturer is the
> Belgian Utimaco branch, and I work at the Dutch branch.
Huh? The modules I'm using aren't made in Belgium. And the keys
aren't erased by removing the module from a computer.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Paranoia
Date: Fri, 26 Jan 2001 13:02:57 GMT
Ellis had retired when he met Diffie (hadn't he?). As he wasn't working
there any more, "You did more with it than we did" seems to be a
natural turn of phrase.
Andrew
In article <[EMAIL PROTECTED]>,
Simon Jenkins <[EMAIL PROTECTED]> wrote:
> I have just read Stven Levy's book 'Crypto' and was again struck by
the
> description of the meeting between Whitfield Diffie and James Ellis.
> Ellis' parting comment has him saying to Diffie, "You did more with it
> than we did."
>
> As an Englishman, this is an interesting phrase - it implies that GCHQ
> don't bother with RSA any more. If they were still using it, Ellis
would
> have said, "You've done more with it than we have."
>
> Paranoia now sets in. If GCHQ aren't interested any more, it means
they
> can break it. If they can break it, they've cracked fast factoring. My
> question is, what other uses would fast factoring have and would it be
> economically viable to keep the method secret rather than release it
> into the public domain?
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cryptographic Camouflage
Date: Fri, 26 Jan 2001 14:11:35 +0100
Thomas Wu wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> writes:
>
> > Darren New wrote:
> > >
> > > I.e., it looks like it's protecting against offline searches of passwords
> > > you can only truely verify online.
> > >
> > > Of course, that's just my interpretation. Read the actual patent for what
> > > they're actually covering.
> >
> > Thank you very much. For, trusting that you are right, I don't
> > think I would spend time to study the detailed document.
> >
> > So it seems that it is virtually the 'employment' of a checksum
> > that gets patented. When I was in school, solving some systems
>
> Huh? It's just the opposite. Having a checksum (MAC, etc.) that
> validates a password guess is exactly what camouflage avoids.
> By removing this checksum, and doing some other cleverness, you
> get a blob of data that leaks no information about the PIN that
> unlocks it. Yet when the right guy comes along with the right
> PIN, the correct private key (RSA, DSA, etc.) is constructed and
> used. Doing this right involves designing the key formats,
> algorithms, and protocols carefully so that this property is
> preserved, and that's where the non-triviality comes in.
>
> I happen to work with this technology on a daily basis, so I get
> to see those non-trivialities quite often.
I based on the information from Darren New, which I hope
to have interpreted correctly.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: Dynamic Transposition Revisited (long)
Date: 26 Jan 2001 13:18:37 GMT
John Savard <[EMAIL PROTECTED]> wrote:
+---------------
| [EMAIL PROTECTED] (Terry Ritter) wrote,
| >In my experience with actually running such a cipher, bit-balancing
| >adds 25 percent to 33 percent to simple ASCII text.
|
| Well, it is possible to map 6 arbitrary bits (64 possibilities) to a
| string of 8 balanced bits (70 possibilities) for an increase of 33
| percent.
|
| However, for larger block sizes, one can indeed do better than that.
|
| One can map 37 arbitrary bits (137438953472 possibilities) to 40
| balanced bits (137846528820 possibilities) for only an 8.11% increase
| in bandwidth cost.
|
| Or one can map 158 arbitrary bits
| (365375409332725729550921208179070754913983135744 possibilities) to
| 162 balanced bits (365907784099042279561985786395502921046971688680
| possibilities), which further reduces the bandwidth cost to 2.532%.
|
| So I suppose you could say that I am quite seriously in need of
| "recalibration".
+---------------
I'd say so! ;-} ;-}
You guys need to talk to some hardware types more often. This "bit
balancing" stuff is a long-ago-solved problem in the data-transmission
domain, where it's known as "bounded-disparity encoding" [where the
"disparity" is the excess of 1's over 0's in a bit stream (or sometimes
the absolute value of the difference)]. You can make the overhead for
perfect bit balancing (a.k.a. "zero disparity") as low as you like for
arbitrary data, as long as you allow the blocks to be large enough.
One version that seems useful/applicable for Ritter's DT is the scheme
used in the "21b/24b" code used in the HIPPI-Serial standard. One bit
of each codeword says whether the remaining bits of that codeword are to
be inverted or not before being sent (and before being used after being
received). The encoder counts the running disparity of all codewords
sent so far, looks at the pop. count of the current word to be sent,
and either inverts or leaves alone the current word, depending on which
way will lower the running disparity. In the case of HIPPI-Serial, this
guarantees that the running disparity never exceeds +/-35 even momentarily,
and never exceeds +/-23 at codeword boundaries. Padding the message with
just one additional codeword of chosen content allows one to force the
disparity for the whole message to 0.
Clearly, by choosing codewords and messages (blocks) large enough, one
can get the overhead for zero-disparity encoding "as low as you like".
However, for ease of computing in software, I wouldn't copy the HIPPI-
Serial scheme exactly. Instead, I'd probably do something like this:
Let a "symbol" (codeword) be something convenient like a multiple of
the machine's wordsize, say, "k" bits. Then let the plaintext block size
be "k-2" symbols, that is, "k*(k-2)" bits. Then let the last symbol of
the block be the "polarity" bits for every symbol in the block, and
the next-to-last symbol (and its corresponding polarity bit) is adjusted
to make the total disparity for the block be zero -- that is, exactly
"bit balanced". For k==32, the overhead is ~6%, for k==64 it's ~3%, etc..
Or here's a better idea: Let the block consist of some large number of
bits, plus a small pad field, plus a small count field big enough to
cover the block. The block is logically split in two pieces at the bit
named by the count. The bits to the left are inverted; the bits to the
right are left alone. The pad bits are adjusted to make the resulting
disparity exactly zero. [You need the pad bits so the algorithm will
converge, otherwise "count==x" might be too small while "count==x+1"
was too large. Using a Gray-code counter may help here, too.]
Or, the counter could count bytes. E.g., consider a 256-byte block,
with one byte of "polarity count", two bytes [I think you need two]
of adjustable pad, and 253 bytes of payload. That's about 1% overhead.
A polarity count of 0 means no payload bytes get inverted; 1-253 means
that that many payload bytes are inverted (one's-complement). One byte
of pad gets the 1's-compl. of the count; the other byte of pad carries
enough ones to balance the residual disparity between the two pieces of
the payload. [I *think* that always works, but there may be a fencepost
error in there -- I haven't done a formal proof. But even if so, using
a Gray-code counter may let you pick up enough bits of pad to fix it.]
In any case, using "partitioned polarity inversion" (to coin a phrase),
it's possible to achieve zero disparity (exact bit balancing) in an
"n"-bit block with about lg(n) bits of overhead, and lg(n)/n --> 0
asymptotically. And it will be *fast* -- much, much faster than the
bit permutations themselves.
-Rob
p.s. I can supply demo code, if the above desciption isn't obvious enough.
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
SGI Network Engineering http://reality.sgi.com/rpw3/
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: Fitting Dynamic Transposition into a Binary World
Date: 26 Jan 2001 13:49:54 GMT
John Savard <[EMAIL PROTECTED]> wrote:
+---------------
| Maybe there already is a mapping to balanced strings that has a simple
| and optimal algorithm, faster than the one for the mapping in binary
| numerical order.
+---------------
See my recent posting <URL:news:94rtfd$4b7p4$[EMAIL PROTECTED]>
in the original ST thread. The key notion, extended from the HIPPI-Serial
Standard's 21b/24b code, is "partitioned polarity inversion" (to coin
a phrase). Summary: Exact bit balancing can be very fast to compute,
and asymptotically cheap in bandwidth: ~1% for 256-byte blocks.
-Rob
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
SGI Network Engineering http://reality.sgi.com/rpw3/
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
------------------------------
From: John Veldhuis <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: Fri, 26 Jan 2001 13:55:50 GMT
Paul Rubin wrote:
> =
> John Veldhuis <[EMAIL PROTECTED]> writes:
> > I just send it back to the manufacturer. The moment it is tampered wi=
th
> > (eg. removed from a computer) all keys are erased. That=B4s what the
> > tamperproof-part is for. I have to add that the manufacturer is the
> > Belgian Utimaco branch, and I work at the Dutch branch.
> =
> Huh? The modules I'm using aren't made in Belgium. And the keys
> aren't erased by removing the module from a computer.
Mine are. But that shouldn=B4t make a difference. I was merely informing
that I work for such a manufacturer, only in another country than were
they are manufactured.
But if a device for storing secret keys has no tamperprotection, brrrr.
You can call it a crypto module, but I wouldn=B4t trust it.
Regards,
John
Please remove the no.spam.please. part from my address if you want to
reply by email.
------------------------------
Date: Fri, 26 Jan 2001 10:46:04 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Crossposted-To: or.politics,talk.politics.crypto,misc.survivalism
Subject: Re: Why Microsoft's Product Activation Stinks
Anthony Stephen Szopa wrote:
>
> Pointless program where to stop software piracy could increase
> revenues by tens of billions of dollars each year? Pointless?
Pretty much, yes. It's like trying to protect Pythagoras' Theorem.
Counter-productive.
> I will not defend copy protection here and now. You slide on this
> point.
(I don't know whether "slide on this point" is American idiomatic usage,
but I don't /quite/ understand it. But I'm guessing it means you don't
want to talk about copy protection. Fair enough.)
>
> Some people like the XOR program and have downloaded it. It works
> just fine as someone in this news group pointed out.
It would be astonishing if it /didn't/ work just fine. It's not exactly
a tricky program to write, is it?
> And here you
> go again, trying to assail my software's aesthetics.
I don't have to assail it. People only need look at it to make their own
minds up.
> Can't prove anything negative about the theory of OAP-L3?
Until you release the source code, why should anyone bother trying?
And, until it can be *used* conveniently (my understanding is that, at
present, the user is obliged to shuffle cards for an hour or three), why
should anyone bother trying?
> Say, you don't want anybody stealing your money: give it away, it's
> that simple, too.
That's the first rational debating point you've made.
My answer? Simple, really. High quality software is being written for
free, every day. It's very competitive on price. Example: I can get a
very powerful operating system that works for 100% less than it costs me
to buy a slightly less powerful and broken operating system. Think about
it. It'll take a while for people to catch on to the idea that they
don't have to pay for their software, but they'll cotton on eventually.
This works in encryption software too (to get us at least marginally
back on-topic). Since people are writing better cryptographic products
than yours for free, why should anyone pay for yours?
By the way, the source code for Twofish is freely available, and Twofish
has been heavily analysed.
>
> You still haven't figured out why I wrote the XOR program and posted
> it on my web site for all to download. I guess if you don't get it:
> you just don't get it.
No, I don't get it. But I can't /wait/ for you to explain. What will
your next masterpiece be? A program to add two numbers together? Without
source code, and weighing in at 300 KB?
>
> I mentioned to a guy once that US laser weapons are only about 10%
> efficient. He said who cares, they get the job done.
If you have the choice between 10% efficiency and 90% efficiency, which
do you choose? If I have the choice between OAP-L3 and Twofish, I choose
Twofish. Why? Because it's free, it is known to work (or, at least, has
been extensively cryptanalysed with no known breaks surfacing as yet),
it's fast, and the source code is available.
> What are MSs objectives? It matters.
>
> MS is losing a bundle on its software being pirated. You are just
> spamming when you ask who would want MSs software. The answer is
> just about everybody, especially if its free.
The price is still too high. If you can persuade MS to /pay/ me to have
their software, I /might/ consider it.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: Producing "bit-balanced" strings efficiently for Dynamic Transposition
Date: 26 Jan 2001 14:00:54 GMT
John Savard <[EMAIL PROTECTED]> wrote:
+---------------
| Well, I finally came up with an algorithm that is reasonably workable.
| To convert 37-bit arbitrary strings into 40-bit bit-balanced strings,
+---------------
Hmmm... I think for truly *arbitrary* 37-bit strings you'll need at
least a 44-bit result.
+---------------
| I need an _enumeration_ of 40-bit balanced strings. Instead of
| directly splitting up a 40-bit bit-balanced string into five 8-bit
| strings, I can keep the number of cases manageable if I split it up
| into two 20-bit strings.
...
| To actually produce the bits of 40-bit string number such-and-such, I
| simply _continue the process_.
| Thus, a bit-balanced 20-bit string becomes two 10-bit strings:
...
| and I can even split the 10 bit strings into two 5-bit strings.
|
| Doing a cascading conversion in this way means that I have a limited
| number of cases at each step, so the tables I work with have
| reasonable size.
+---------------
If you recurse all the way down to 1-bit "strings", I think you
end up with the same number of overhead bits as my "partitioned
polarity inversion" method, namely, lg N. And the latter is simpler
and faster.
-Rob
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
SGI Network Engineering http://reality.sgi.com/rpw3/
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
------------------------------
** 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
******************************
