Cryptography-Digest Digest #374, Volume #12 Mon, 7 Aug 00 14:13:01 EDT
Contents:
Secrets and Lies: New Book by Schneier (Bruce Schneier)
Re: Looking for a *different* type of cipher... (Mark Wooding)
Re: New William Friedman Crypto Patent (filed in 1933) (Eric Lee Green)
Re: Note on text compression ("Tony T. Warnock")
Re: Functions that are slow to invert ("Scott Fluhrer")
Special RSA moduli (JCA)
Re: New William Friedman Crypto Patent (filed in 1933) - Prior Art ("Ed Suominen")
Re: Proposal: Timestamping Roundtable w/ PGP Sigs. (John Myre)
Re: What is the word on TC5? ([EMAIL PROTECTED])
Re: Secrets and Lies: New Book by Schneier (Bruce Schneier)
Re: Proposal: Timestamping Roundtable w/ PGP Sigs. ("JL")
Re: Note on text compression (Mok-Kong Shen)
Re: Q: CD (Mok-Kong Shen)
Questions about Rijndael (Mok-Kong Shen)
Re: Coupon collector's problem (Mok-Kong Shen)
Re: New William Friedman Crypto Patent (filed in 1933) ("Douglas A. Gwyn")
Re: Special RSA moduli (Bob Silverman)
FFT-Hash II (Daniel Leonard)
Re: Authentication over the internet (Bill Unruh)
----------------------------------------------------------------------------
From: Bruce Schneier <[EMAIL PROTECTED]>
Subject: Secrets and Lies: New Book by Schneier
Date: Mon, 07 Aug 2000 09:11:26 -0500
Secrets and Lies: Digital Security in a Networked World
I've written a new book.
"Secrets and Lies" discusses computer security, and the issues
surrounding computer security. It explains, in an accessible style,
how different security technologies work and how they fail. It
discusses the process of security: what the threats are, who the
attackers are, and how to live in the their world.
It'll change the way you think about computer security.
I've spent a long time writing this book, and I'm very proud of it.
Please take a look.
Information about the book:
<http://www.counterpane.com/sandl.html>
A detailed table of contents is at that URL.
Order the book (at a 30% discount) from Amazon:
<http://www.amazon.com/exec/obidos/ASIN/0471253111/counterpane/104-8286037-2313547>
If use that URL to order the book from Amazon, a portion of the
purchase price will go to EPIC.
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Tel: 408-556-2401
3031 Tisch Way, Suite 100PE, San Jose, CA 95128 Fax: 408-556-0889
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Looking for a *different* type of cipher...
Date: 7 Aug 2000 14:24:00 GMT
RavingCow <[EMAIL PROTECTED]> wrote:
> I was just wondering if anyone out there knew of a type of cipher which
> given plaintext and a positive integer n, could form cipher text in
> constant time, taking n steps to decode back into plaintext. For
> example:
>
> ciphertext = encode(plaintext, n) --- O(1)
> plaintext = decode(ciphertext, n) --- O(n)
One possibility: use RSA backwards.
The *sender* makes a pair of large primes p and q. He chooses an
encryption exponent e relatively prime to p - 1 and q - 1 at random.
Compute \lambda = \lambda(n) = lcm(p - 1, q - 1) and d = e^{-1} (mod
\lambda). Let k be the desired workfactor for decryption. Then compute
e' = e^k mod \lambda. Give d to the recipient.
Encryption of a message now consists of exponentiating by e'.
Decryption requires exponentiating by d^k (or, equivalently, doing k
exponentiations by d). Since the recipient doesn't know the factors of
n (or \lambda), he can't reduce d^k to anything more manageable.
There are obvious parallels between this and proving continued
possession of a file (see the earlier thread on this subject).
-- [mdw]
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: New William Friedman Crypto Patent (filed in 1933)
Date: Mon, 07 Aug 2000 14:24:32 GMT
Steve wrote:
> The machine was thus electro mechanical in nature in that it sent a
> signal through the rotors which were internally wired differently from
> one side to the other in random positions. Thus input under the <a> on
> the left side of the rotor might come out under the <q> on the other
> side. The path the electrical impulse followed through the set of
> rotors produced an impulse on a printer and thus printing an encoded
> message in 5 letter code groups. This output was on a sticky back or
> glue backed tape similar to what a western union message might have.
> You simply cut and pasted the message on a piece of paper and mailed
> it or sent the encoded message via any other means of transmission.
>
> If you set the machine back to its starting position and typed in the
> encoded letters from the tape you got out of the machine a plane text
> tape with the original message.
>
> I am wondering if any of you have seen this machine in the past and
> know of it's current use or classification. I'm talking about wide use
> in the 1950's and 1960's and up to the 1970's. I used it for several
> years up to 1971 almost weekly for some of the things I did. Funny
> thing I can not remember its military name but I can picture it like
> it was yesterday.
A former military member mentioned a similar machine to me, his duty for
a while was to input the daily rotor settings for his base's machine,
but he would not say what year he last used it or give any additional
details, saying that they had not told him at muster out time what he
was allowed to say about it or not. But he enlisted in 1975. So
apparently it was still in use in the late 70's, at least in arms of the
service that did not get the latest/greatest equipment. I would be very
suprised if details of the machine were made public, given that there
are probably still (encrypted) messages in the Kremlin archives
encrypted with that machine that would be very embarrassing if revealed
today. Nevermind that there's probably already a duplicate of the
machine in a Kremlin sub-basement, courtesy of paying some NCO big money
for a copy of a repair manual or some other such means... it would be
embarrassing to certain people within the U.S. government, which is what
matters in such cases (in many such cases, "national security" is a
straw man to avoid embarrassment... see "Pentagon Papers, The" for a
fuller description of the syndrome and the the U.S. government's
reaction to it).
--
Eric Lee Green There is No Conspiracy
[EMAIL PROTECTED] http://www.badtux.org
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Note on text compression
Date: Mon, 07 Aug 2000 08:47:59 -0600
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen wrote:
> Texts that are normally entered via keyboards consist of 7-bit
> ASCII symbols but are stored by computer as 8-bit bytes, if I
> don't err, i.e. the leading bit is not used.
>
> I suppose one could consider doing the following which may be
> beneficial as a pre-processing step for compression schemes that
> use the Huffman algorithm.
>
> Complile a list of 128 most common words. Let these, including
> the accompanying space at end of words, be coded into 7 bits
> to be prefixed by a leading bit of '1' to form a byte. Let
> everything not coded this way be as usual.
>
> Thanks for comments in advance.
>
> M. K. Shen
Been there, done that. It gave compressions to between 25% and 30% of
original file size. I also included the blanks after words. Only the
first 16 words give significant compression. I used the others for
special symbols, things like repeated number compression. It does have
the advantage that the compressed text can be searched.
PS: Are you the M. K. Shen that did the stuff on Goldbach's conjecture
some years ago?
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Functions that are slow to invert
Date: Mon, 7 Aug 2000 07:37:46 -0700
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Scott Fluhrer wrote:
> >
>
> > Another possibility would be to pick a random N bit key, and encrypt the
> > argument with it, along with enough redundancy so that the solver can
> > recognize the correct key. As long as you use a cipher which has brute
> > force as the strongest attack, this appears to meet your criteria.
> >
> > BTW: what's this for?
>
> Would you please elaborate the phrase 'along with enough redundancy
> so that the solver can recognize the correct key'?
Certainly. One method is to append the plaintext with a M bit checksum, and
encrypt that. Then, when the solver attempts to check a particular N bit
key, he decrypts the ciphertext with it, and then checks the checksum.
Assuming you pick M sufficiently large, this should have an arbitrarily
small probability of having a second, unintended solution.
>
> If one uses a function that has fairly asymetrical computation
> times in inversion in a cipher, then one could cause the decryption
> to be rather long while optimizing the encryption phase, which
> translates to higher work for the opponent if he brute force. A
> fancy use I could think of is that one wants to tell someone
> something but the recipient should not learn the message
> immediately but at some delayed period.
Well, making brute force harder is (IMHO) a nonproblem -- use sufficiently
long keys (256 bits is good for all but the ultraparanoid), and it becomes
unthinkable. And, the two constructions I listed do not sound suitable for
sending someone a delayed message -- there is a nontrivial probability that
the message will be found early (if the user happens to select the right key
early on).
I have heard of a few uses of puzzles of selected difficulty. One is
Merkle's Puzzle method for doing (essentially) weak public key cryptography
with one-way functions. Another is a scheme that attempts to prevent some
Internet denial of service attacks -- before you can talk to someone, you
must first solve a puzzle for him. This would, at least, make attacks where
you just send lots of SYN requests somewhat more difficult.
--
poncho
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Special RSA moduli
Date: Mon, 07 Aug 2000 07:37:02 -0700
I am looking for discussions on RSA moduli N of the
form N= p^r*q, where p, q are odd primes, and r is a
positive integer. I am particularly interested in security/
speedup tradeoffs for this kind of moduli.
Any pointers will be appreciated.
------------------------------
From: "Ed Suominen" <[EMAIL PROTECTED]>
Subject: Re: New William Friedman Crypto Patent (filed in 1933) - Prior Art
Date: Mon, 7 Aug 2000 08:09:32 -0700
In the U.S., any information that has been made publicly available before
the inventor's date of invention (which may be prior to the filing of a
patent application) is considered prior art. Presentations by the inventor
are not considered prior art against that inventor (in the U.S.), but *any*
printed publication, public use, or commercial offer for sale is considered
prior art against the inventor and everyone else if it happens more than one
year before filing of a patent application. In other words, the inventor has
a one-year grace period in which to publish his or her invention or try to
make money off of it before filing a patent application.
While I do not practice before the European patent office, I understand that
most foreign jurisdictions (including the EU) have no such grace periods.
The definition of prior art has been the subject of many interesting legal
cases. For example, a web page that is never actually printed can be
considered a "printed publication" if a reasonably diligent researcher can
find it. A thesis that is cataloged in a single university library but never
otherwise published is also considered prior art, but good luck finding it
in a patentability search!
Nothing in this message is to be construed as legal
advice, or the opinion of my firm or any client.
====================================
Ed Suominen
Registered Patent Agent
Web Site: http://eepatents.com
PGP Public Key: http://eepatents.com/key
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: Proposal: Timestamping Roundtable w/ PGP Sigs.
Date: Mon, 07 Aug 2000 10:13:36 -0600
Ed Suominen wrote:
<snip>
> All participants will agree to testify as to the
> authenticity of their digital signature if necessary.
<snip>
"Testify" as in "in a court of law"? Where?
Before I made legal promises I'd want a more explicit
(and limited!) description of what I was promising...
JM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: What is the word on TC5?
Date: Mon, 07 Aug 2000 16:17:15 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >Yes, I think using big enough round keys will defeat this
> >particular attack, although there may well be other ways
> >to exploit the given impossible differential.
> >
> >Also, it looks to me like TC5 is really an eight-round Feistel
> >cipher, so the attack on a four-round Feistel cipher wouldn't
> >apply, anyway.
Oops, I guess not. You increment the loop variable twice in the
body of the loop, so it's really just 4 rounds after all.
>
> TC5 actually has a 16/32/64 and 128 bit Feistel in the
> definition. The 16-bit feistel uses actual key bytes by xoring
> them in and has eight rounds.
>
> The 32/64/128 feistels used the feistel below it as a F function
> in four rounds.
>
> Which means a single round of the 128-bit Feistel calls the 16-
> bit feistel sixteen times.
Cute. Now if you'd use 4 rounds in the 16-bit Feistel network,
and 8 in the 128-bit network, then you'd avoid that impossible
differential. But perhaps that would introduce worse problems
somewhere else. Like Socrates and Sergeant Schulz, I know
nothing.
--
Cordially,
Dave Empey
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bruce Schneier <[EMAIL PROTECTED]>
Subject: Re: Secrets and Lies: New Book by Schneier
Date: Mon, 07 Aug 2000 11:29:37 -0500
On Mon, 07 Aug 2000 09:11:26 -0500, Bruce Schneier
<[EMAIL PROTECTED]> wrote:
>
>Order the book (at a 30% discount) from Amazon:
><http://www.amazon.com/exec/obidos/ASIN/0471253111/counterpane/104-8286037-2313547>
I just looked at the Amazon website, and they reduced the discount
from 30% to 20%. My publisher is attempting to figure out why the
discount was reduced, and whether it can be increased again. In the
menetime, wait before ordering the book.
And their August 10th date is wrong, too. That's the publication
date; Amazon won't have books to ship for another two weeks after
that.
Bruce
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Tel: 408-556-2401
3031 Tisch Way, Suite 100PE, San Jose, CA 95128 Fax: 408-556-0889
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: "JL" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: Proposal: Timestamping Roundtable w/ PGP Sigs.
Date: Mon, 07 Aug 2000 17:10:40 GMT
"John Myre" <[EMAIL PROTECTED]> a écrit dans le message news:
[EMAIL PROTECTED]
> > All participants will agree to testify as to the
> > authenticity of their digital signature if necessary.
>
> "Testify" as in "in a court of law"? Where?
>
> Before I made legal promises I'd want a more explicit
> (and limited!) description of what I was promising...
"at the expense of the person requesting such testimony". Wouldn't you like
some nice holidays at the other end of the wolrd ?
JL.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Note on text compression
Date: Mon, 07 Aug 2000 19:24:16 +0200
"Tony T. Warnock" wrote:
>
> Mok-Kong Shen wrote:
>
> > Texts that are normally entered via keyboards consist of 7-bit
> > ASCII symbols but are stored by computer as 8-bit bytes, if I
> > don't err, i.e. the leading bit is not used.
> >
> > I suppose one could consider doing the following which may be
> > beneficial as a pre-processing step for compression schemes that
> > use the Huffman algorithm.
> >
> > Complile a list of 128 most common words. Let these, including
> > the accompanying space at end of words, be coded into 7 bits
> > to be prefixed by a leading bit of '1' to form a byte. Let
> > everything not coded this way be as usual.
> Been there, done that. It gave compressions to between 25% and 30% of
> original file size. I also included the blanks after words. Only the
> first 16 words give significant compression. I used the others for
> special symbols, things like repeated number compression. It does have
> the advantage that the compressed text can be searched.
Did you follow that processing with a Huffman and have you compared
it to Huffman without that processing?
> PS: Are you the M. K. Shen that did the stuff on Goldbach's conjecture
> some years ago?
You have a good memory, remembering such a tiny paper long ago.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: CD
Date: Mon, 07 Aug 2000 19:24:34 +0200
"Frank M. Siegert" wrote:
>
> On Sun, 06 Aug 2000 23:08:29 GMT, [EMAIL PROTECTED] wrote:
>
> >Is this for that CD-one-time-pad topic that came up earlier?
>
> Sounds more like a quest for randomness to me. If you only need a one
> time pad why not simply use an ISO9660 filesystem...?
>
> Sure you can get more data on a CD by using the full sector size - no
> error correction - just like VCDs are doing it for their data track.
If the error probability is of some appropriate magnitude,
I guess that there could be at least the following application:
One purposedly create, presumably with special hardware, groups
of 'pits' that are errors when interpreted by the normal
reading device and hence are ignored by it. Through an appropriate
scheme one could embed information bits there. For an outsider,
these groups of bits would be hardly distinguishable from
those that are naturally expected to occur. One achieves thus
a steganographical transmission of information with CDs.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Questions about Rijndael
Date: Mon, 07 Aug 2000 19:24:44 +0200
In another thread David Wagner has posed a question about
Rijndael's S-box. I like to elaborate that a little bit and
add a few questions of my own for discussion.
1. In ByteSub only one 8-bit S-box is used, which is defined
by an inversion in GF(2^8) and an affine transformation.
a. How has the affine transformation been chosen? Wouldn't
a random invertible boolean matrix and a random boolean
vector do as well?
b. Wouldn't it be advantageous to have more than one affine
transformations, thus rendering more S-boxes available,
which may even be used differently in different rounds?
2. In ShiftRow shifting of bytes are specified for the four
rows.
a. Wouldn't it be better to shift different amounts in
different rounds?
b. Why does one use shifting of bytes and not shifting
of (arbitrary number of) bits?
c. (Non-technical): Wouldn't shifting of bytes, which is
a circular shift by 8 or multiple of 8 bits, also be
in conflict with the Hitachi's patent claims about
circular shift, just as the other AES candidates do?
3. In MixColumn the columns are multipled by a 3rd degree
polynomial with coeffcients in GF(2^8) and reduced
modulo a 4th degree polynomial.
a. How has the 3rd degree polynomial been chosen (besides
the invertibility)?
b. Wouldn't it be advantageous to have more than one
such polynomials available for the various columns,
which may even be used differently in different rounds?
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Coupon collector's problem
Date: Mon, 07 Aug 2000 19:24:24 +0200
"Artemios G. Voyiatzis" wrote:
>
> Thanks for the reply, but I am interested in proving this formula,
> not using it (well, I do use it, but I need a proof). I already
> read Knuth, but it didn't provide the proof - maybe it's too obvious :-)
Knuth gives some references. I haven't studied these. Proofs of
such statistical tests are usually non-trivial.
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: New William Friedman Crypto Patent (filed in 1933)
Date: Mon, 7 Aug 2000 16:34:03 GMT
"SCOTT19U.ZIP_GUY" wrote:
> I wonder if it is a govenment attempt to rewrite history.
> Who really knows if it was filed in 1933.
Although I don't have direct evidence that that particular
patent was filed in 1933, I do have substantial evidence
that the invention occurred around then and that there
were some "secret" patents issued to WFF and colleagues
for similar inventions of that era.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Special RSA moduli
Date: Mon, 07 Aug 2000 17:22:51 GMT
In article <[EMAIL PROTECTED]>,
JCA <[EMAIL PROTECTED]> wrote:
>
> I am looking for discussions on RSA moduli N of the
> form N= p^r*q, where p, q are odd primes, and r is a
> positive integer. I am particularly interested in security/
> speedup tradeoffs for this kind of moduli.
See the appendix in item #13 of:
http://www.rsalabs.com/bulletins/index.html
--
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/
Before you buy.
------------------------------
From: Daniel Leonard <[EMAIL PROTECTED]>
Subject: FFT-Hash II
Date: Mon, 07 Aug 2000 17:33:23 GMT
To those who knows,
I am trying to implement the FFT-Hash II message digest algorithm. I base
my implementation on the paper "FFT-Hash III, Efficient Cryptographic
Hashing", C.P.Schnorr.
I have questions about the equations the author uses. The first step in
the hashing function is :
FOR i =3D 0..15 DO
=09e_(i) =3D e_(i) + e^*_(i-1) * e^*_(i-2) + e_(i-3) + 2^i (mod p)
- where e^* =3D e if e =3D/=3D 0 and e^* =3D 1 if e =3D 0
- p =3D 65537 (2^16 + 1).
- Each e seems to be a short int (16 bits)
does the (mod p) apply to the entire equation like=20
e_i =3D ...;
e-I %=3D p;
or does (mod p) apply only to the last term (which seems useless since 2^i
will be at max 2^15, smaller than 65537) ?
Second, concerning the discrete Fourier transform:
FT_8(a0,..,a7) =3D (b0,..,b7) with
b_i =3D sommation(j=3D0..7) 2^(4*i*j)a_j (mod p)
2^(4*i*j) =3D> 2 at the (4*i*j) power, which range from 0 to 4*7*7 =3D 196
once again, the mod p applies to which par of the sommation, each term, or
the whole equation ? It seems a little silly to apply it to the whole
equation since the small term of the seventh sommation ( 2^0, 2^28,
2^56,.., 2^196) are going to be eclipsed by the last term, even on double
precision.
Also, I was trying to find some source code for that algorithm and most of
all, test vectors. Are there any source for test vectors and source code ?
Thank you
==========
Daniel L=E9onard
OGMP Informatics Division E-Mail: [EMAIL PROTECTED]
D=E9partement de Biochimie Tel : (514) 343-6111 ext 5149
Universit=E9 de Montr=E9al Fax : (514) 343-2210
Montr=E9al, Quebec Office: Pavillon Principal G-312
Canada H3C 3J7 WWW :
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Authentication over the internet
Date: 7 Aug 2000 18:03:42 GMT
In <[EMAIL PROTECTED]> MJYoung <[EMAIL PROTECTED]> writes:
>Has anyone written a white paper about strong authentication over the
>internet?
>I'm looking for various ways to authenticate people without using any
>client software.
>Cost should be minimal and web-based.
You cannot. If there is no client software, then the only thing the
client can do is to send material in clear text over the net. That is
not even minimally secure. You need client side software.
Now, if you are willing to use the web, you could always send them the
appropriate software as say a java applet. (eg, see the srp Java applet)
The Java(tm) Telnet Applet
1996, 97 Matthias L. Jugel, Marcus Meiszner
http://www.first.gmd.de/persons/leo/java/Telnet/
See also srp.stanford.edu
------------------------------
** 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
******************************
