Markowitz' confusion merely temporary

[Markowitz () DOCKMASTER NCSC MIL <Markowitz () DOCKMASTER NCSC MIL>]

I'm almost beginning to enjoy this.  :-)

> Mike Markowitz says:

> > 1.  In 1991, Rivest was party to a report that gave ElGamal- (more
> > generally, discrete log-) based schemes a 40-bit security advantage
> > over ... (stuff deleted) ...  Let's have no more of this nonsense.

> > Jim Bidzos writes:

> I said "DSS is too weak." DSS = Digital Signature *Standard*, A NIST
> proposal which specified a Digital Signature *Algorithm* *and*
> spelled out a cap on the key size for the DSA. (Among other things.)
> I don't see anything in my post that says "discrete log systems are
> weak."  At the time it was called weak, _DSS limited keys to 512
> bits._ Why was it nonsense to challenge this limitation in a proposed
> national standard?

I wasn't just referring to your post--I was reacting to your 2-year
campaign of misinformation.  Have you forgotten your letter of Sept.
20, 1991 to Rep.  Tim Valentine?  If so, let me quote a few lines:

 "The referenced research [2] on the security of the discrete
 logarithm problem, on which the DSS system is based, is well known
 worldwide, ensuring that the NIST system would never be used by any
 company not forced to do so, and would never be purchased from U.S.
 suppliers by companies outside of the U.S."

The "referenced research," an article by LaMacchia and Odlyzko,
specifically criticized discrete log cryptographic schemes which "use a
fixed prime which cannot easily be changed..."

The DSS never mandated use of a fixed prime and, in fact, allows it to
be easily changed--but I'm sure you counted on Rep.  Valentine not
noticing these subtleties.

I continue to quote from your letter:

 "DSS specifies a 512-bit prime modulus, and states that such a
 modulus *can* [emphasis added by mjm] be shared by groups.  This is
 important as the discrete log problem is known to be "brittle,"
 meaning a table of discrete logarithms could be built, allowing an
 attacker to simply "look up," rather than have to "break," a user
 key."

While this is true in characteristic 2, I welcome evidence that it can
be done for characteristic p > 2^511.  I'm unaware of results more
current than last year when the largest prime for which this *had* been
done was only 224 bits long.

In fact, to get an idea of the complexity we're talking about here, it
might help to compare the current state of the art in factoring to that
of computing discrete logs in characteristic p > 2.

1.  The factorization of a special 513-bit number (F9) in 1991 took
Lenstra et al.  4 months on 700 workstations.  It involved sieving about
10^14 numbers and solving the resulting system of equations in 199,203
unknowns (the latter being performed relatively rapidly).

2.  The of a special 523-bit number (2^523-1) last October took
Bernstein and Lenstra less than 1 month but required 2 16384- processor
maspars for a 3 week sieving step, followed by 2 days on a workstation
to reduce the 280,000x240,000 system to something one maspar could solve
in 5 days.

3.  According to Dan Gordon [1], using a similar (and currently optimal
in this situation) number field sieve algorithm to compute a discrete
log for the *worst* of his 512-bit "trapdoor primes" would require
sieving 2x10^14 numbers, solving a 400,000 variable system, then
performing 2x10^7 trial elliptic curve factorizations and a second sieve
on 1.4x10^14 numbers.

So, yes, challenging NIST on the 512-bit limitation was reasonable; but
I object to the little intellectual dishonesty involved in your
comparison of the factoring and discrete log problems.  NIST corrected
their mistake, then went on to an even bigger blunder by publishing
Fougner's proposal.  Go figure.  :-)

Interestingly enough, a copy of MailSafe we purchased from Fischer three
or four years ago used a standard RSA modulus size of 400 bits.  The
manual (written in 1988) claimed that "On today's fastest
supercomputers, this [factoring such a number] would take at least 5 to
10 years of dedicated computing." [Crypt Master supported up to 1280 bit
moduli as early as 1983 but, alas, it is not longer available.  :-) ]

In this regard, I'm sure you remember Lenstra's announcement last month
on the successful factorization of the (approx.)  400-bit "RSA-120
challenge number." Only took 83 days via email on the net.  Seems NIST
is entitled to at least one mistake.

> > > 2. DSS could force users to employ a trapped system-wide p.
> > >    (Demonstrated clearly by Lenstra and Haber.)
> > > DSS now includes information on how to avoid trapped primes.

> The "trapdoor" concern was as follows: someone constructs and
> publishes a "trapped prime" p.  You generate your public key y and
> your own secret value x using this p (and maybe other supplied
> parameters such as q and g.)  The supplier of p can, with only your
> public key, compute your secret key.  If DSA becomes the basis for
> key management as well as signatures, then the supplier of p can
> *surreptitiously read your encrypted messages, even though you
> generated your own public/private key pair.

Even before NSA published their suggested method of allowing third
parties to certify that no trapdoor exists (now part of the draft
standard), Dan Gordon [1] presented a paper at Crypto '92 identifying a
certain class of trapdoor primes and giving the analysis outlined in (3)
above.  In essence, he showed that the Lenstra-Haber concern could be
easily avoided.

Funny, I don't remember you advertising Lenstra's subsequent retraction
of his condemnation of the DSA.

> Was DSA designed, at least partially, to drive a wedge into the
> public-key community in advance of the sure-to-be-controversial
> privacy proposal?

Not being privy to policy making at that level, I truly don't know.  But
I'm sure the folks at the fort are chuckling over these conspiracy
theories--it's even been said RSADSI is an NSA front.  :-)

> Do people argue DSA vs. RSA?

People argue DES/IDEA and all sorts of things.  It's simply amazing,
though, how much the particular controversy to which you refer has died
down now that Fougner has announced his pleasure with the DSS and given
it his blessing.

> > > 6. DSS is slow and cumbersone.
> > > What happened?
> > > Still true.

> > 6. More nonsense.  Many of our customers are quite happy with signing
> > in 300 or so milliseconds and validating in 600. And that's in
> > software on today's hardware with random p,q,g,k and h values;with a
> > Pentium, SuperSPARC, or Capstone chip, we'd of course do much better.

> You conveniently ignore things like the need to secure the information
> used in the precomputation (or compromise your private key) as well as
> the need to secure the random value required by *every signature* or,
> again, compromise your private key. Also, the precomputation requires
> the intermediate storage of a fairly large volume of data, securely.
> That's cumbersome.

Even Bill Stewart seems to have bought your argument:

> ... the issue of precomputation that Jim brought up is especially
> a concern for smartcards.

I should have mentioned that we accomplish the 300 msec.  signature and
600 msec.  validation times *without precomputation* of any kind:  the
300 msec.  figure includes the computation of r and 1/k and no tables of
powers of g are used for either procedure; though techniques such as
those suggested by Brickell and McCurley would surely speed up our
computations.

Since we don't precompute r or use precomputed powers of g, there simply
is no "large volume of data" to store.  In fact, as all computations are
performed modulo the 160-bit prime q, storage requirements are much less
than those for RSA.  We can also switch p/q/g parameters in a fraction
of a second so there is no performance penalty in allowing them to vary
with each user.

Securing the random value required by every signature is as easy as
throwing it away, i.e., zero-izing the RAM it occupied immediately after
the signature computation is complete--it need exist for less than half
a second or so.  I'm sure you know that this random value is not needed
for signature validation.

> And 600ms to verify is still 40 *times* slower than RSA.

I congratulate you if you can indeed perform an RSA signature validation
in 600/40 = 15 msecs.  on a 486.  OTOH, if your estimate is slightly off
(say, by a factor of at least 2), Kaliski might be unaware of our
methods--that's a possibility worth considering.

Perhaps I should have said "misinformation" instead of "nonsense." I
apologize.

Michael

[1] Gordon, Daniel M., Designing and Detecting Trapdoors for Discrete
Log Cryptosystems, Proc.  Crypto '92.  Springer-Verlag (to appear)

----------
  Michael J. Markowitz, VP R&D      markowitz () dockmaster ncsc mil
  Information Security Corp.        708 405-0500, fax: 708 405-0506
  1141 Lake Cook Rd., Suite D       MCI:  363-1959
  Deerfield, IL  60015              CIS: 76206,2617