Bidzos: Markowitz's state of confusion

[Jim Bidzos <jim () RSA COM>]

Mike Markowitz says:

> Jim Bidzos writes:

> > 1.  DSS is too weak.  (Rivest demonstrated this nicely.)  
> >    What happened?
> >    NIST increased the maximum key size to 1024 bits from 512.

> 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.

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?

> > 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.

> 2. Good enough. Has anyone suggested a solution to the analogous
> problem with RSA primes? I for one wasn't convinced by Kaliski's paper.

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.* Please demonstrate an
analogous problem with RSA primes.

(Note: There are two versions of Kaliski's paper. You should make sure
you read the latest. The author of the "RSA Trapdoor" seemed
convinced.)

> > 3. DSS had patent problems.
> > What happened?
> > This has been resolved.

> 3. The hell it has. (Not that I ever believed it infringed a valid PKP
>   patent!)

You're entitled to your opinion, as am I.

> > 4. DSS could be a prelude to a breakable privacy standard.
> > What happened?
> > Told you so.

> 4.  The connection escapes me.

Will promotion of DSA encourage people to indirectly promote
Capstone/Clipper? (Look at your own last sentence in (6) below.) 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?
Do people argue DSA vs. RSA? 

> > 5. DSS is not compatible with international standards.
> > What happened?
> > This is still true.

> 5.  But not for long.  ANSI X9.30, for example, is a good start.

Even if this is approved, which it isn't yet, it does not
automatically make DSS an international standard.  DSS does not meet
the specifications of ISO 9796, an international signature standard.

> > 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. And 600ms to verify is still 40 *times* slower than
RSA.  So I don't think it's nonsense to say DSS is slow and
cumbersome.  But I do admit, that with the Capstone chip, you'll get
better DSS performance, and Clipper thrown in for privacy.

> > The NIST/PKP deal >>This deal is basically as follows:  >>The govt is
giving PKP its DSA patent.

> On the face of it,this deal violates 35 USC 209(c)(1)(A-D) and 35 USC
> 209(c)(2), as well as the 1987 Computer Security Act. We'll have to see
> what happens.

Yes we will.

> Oh, yeah...  please feel free to share this with anyone.  :-)
> Michael

By all means.

--Jim