Mailing List Archive

On Wed, 23 Aug 2000, Stefan Nobis wrote:

> I found the following on the web, which says that the DSS standard is
> a bit bad and not very secure - is this true?

Nonsense.

> -----------------------------------------------------------------------
> [.Y - public key, X - secret key, G - generator, P - prime]
> Y = GX mod P
>
> The DSS (Digital Signature Standard) restricts the size of the prime P
> to 1024 bits, which appears as a minor restriction compared to the RSA
> algorithm which commonly uses 1024-2048 bits. But it's more important
> for the datafiend, that this standard restricts the secret key to 160
> bits as well. Therefore it is enough to check a relevant part of the
> numbers between 0 and 2160 to find the secret key, while the size of

s/2160/2^160/

> the prime does only increase the time for calculation of one single
> test but does not increase the amount of possible secret keys.

It does not help to have huge keys if you don't have a hash algorithm
with a matching length of the digest. Matching here does mean, that
the time to break the secret key is of the same order as the one to
calculate collisions in the hash digests.

RSA+MD5 of any keysize is weaker than 1024 bit DSA+SHA1.

BTW, the NSA is working on a larger hash and as soon as it has been
"proofed" that this is one is secure, we can use DSA with larger key
sizes.


Werner


--
Werner Koch GnuPG key: 621CC013
OpenIT GmbH http://www.OpenIT.de

--
Archive is at http://lists.gnupg.org - Unsubscribe by sending mail
with a subject of "unsubscribe" to gnupg-users-request@gnupg.org

Quoting "L. Sassaman" <rabbi@quickie.net>, who wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Wed, 23 Aug 2000, Werner Koch wrote:
>
> > BTW, the NSA is working on a larger hash and as soon as it has been
> > "proofed" that this is one is secure, we can use DSA with larger key
> > sizes.
>
> SHA-2 is due next month, isn't it? (Along with AES, the new DSS, and a
> patent-free RSA)

Sounds like a good month!

--
Sam Roberts (sam@cogent.ca), Cogent Real-Time Systems (www.cogent.ca)

Werner Koch <wk@gnupg.org> writes:

> > [.Y - public key, X - secret key, G - generator, P - prime]
> > Y = G^X mod P
> >
> > The DSS (Digital Signature Standard) restricts the size of the prime P
> > to 1024 bits, which appears as a minor restriction compared to the RSA
> > algorithm which commonly uses 1024-2048 bits. But it's more important
> > for the datafiend, that this standard restricts the secret key to 160
> > bits as well. Therefore it is enough to check a relevant part of the
> > numbers between 0 and 2^160 to find the secret key, while the size of
> > the prime does only increase the time for calculation of one single
> > test but does not increase the amount of possible secret keys.
>
> It does not help to have huge keys if you don't have a hash algorithm
> with a matching length of the digest. Matching here does mean, that

Hmmm... let me get this right: The hash is used for digital signatures
and then the generated hash is crypted with the secret key, so if the
text is changed or you use the wrong public key an error occurs. This
way the secret key should not be stronger than the hash.

But what about encrypting the whole text and not signing it? There you
use a conventional symetric cipher to encrypt the text and the
symetric key is crypted with the public key of the receiver. In this
szenario the secret key need not to be stronger than the conventional
cipher.

Do i understand things right when i assume there are two secret keys,
one for signing and one for encryption and that the first is not
longer than 160 bits but the later may be 1024 bit or more?

> RSA+MD5 of any keysize is weaker than 1024 bit DSA+SHA1.

This 1024 bits are the size of the prime to generate the 160 bits of
the secret key for signing?

--
Until the next mail...,
Stefan.

--
Archive is at http://lists.gnupg.org - Unsubscribe by sending mail
with a subject of "unsubscribe" to gnupg-users-request@gnupg.org

Stefan Nobis wrote:

> But what about encrypting the whole text and not signing it? There you
> use a conventional symetric cipher to encrypt the text and the
> symetric key is crypted with the public key of the receiver. In this
> szenario the secret key need not to be stronger than the conventional
> cipher.

This is true, but DSS will not be used in this situation. There is a
variant of ElGamal encryption that works with DSA style keys, but it
is not in wide use and OpenPGP does not use it.

> Do i understand things right when i assume there are two secret keys,
> one for signing and one for encryption and that the first is not
> longer than 160 bits but the later may be 1024 bit or more?

No. DSA uses two parameters, one 160 bits and one which is 512 to
1024 bits. These parameters can be shared among as many users of DSA
as you want without weakening security. Then, of course, a user has a
public and a private key as with simpler systems such as RSA. So each
user will have his or her own public and private key. Then there will
be two parameters which might or might not be the same as the ones
used by other people's keys.

You can attack DSA by solving one of two discrete logarithm problems.
One is in a group of order 160 bits and the other is in a group of
order 512 to 1024 bits depending on the length of the other
parameter. However, some types of discrete log are easier than
others; it is believed that the two problems are about equivalent when
the variable length parameter is 1024 bits.

There is therefore no point in making the variable length parameter
longer than 1024 bits unless you make the other one longer as well.
AFAIK there is no reason not to do this, but because SHA-1 is 160 bits
it doesn't make any sense in the context of the DSS (which specifies
SHA-1 as the hash function).

--
Pete

--
Archive is at http://lists.gnupg.org - Unsubscribe by sending mail
with a subject of "unsubscribe" to gnupg-users-request@gnupg.org

Pete Chown <Pete.Chown@skygate.co.uk> writes:

> > one for signing and one for encryption and that the first is not
> > longer than 160 bits but the later may be 1024 bit or more?
>
> No. DSA uses two parameters, one 160 bits and one which is 512 to

But there are two keys, one for encryption and one for signing, or not?

--
Until the next mail...,
Stefan.

--
Archive is at http://lists.gnupg.org - Unsubscribe by sending mail
with a subject of "unsubscribe" to gnupg-users-request@gnupg.org

On Thu, 24 Aug 2000, Stefan Nobis wrote:

> But there are two keys, one for encryption and one for signing, or not?

Right. It is better to use different keys for signing and encryption;
it has also the advantage that you can retire the encryption key from
time to time (Hello RIP) to gain forward secrecy.

The usually used encryption key is an ElGamal (aka DH) key which has
other properties than DSA. ElGamal can also be used for signing but
this is seen as a non so secure way and quite complicated to do right;
therefor it is better to use DSA for signing - Phil Zimmermann calls
DSA "ElGamal debugged".


Werner


--
Werner Koch GnuPG key: 621CC013
OpenIT GmbH http://www.OpenIT.de

--
Archive is at http://lists.gnupg.org - Unsubscribe by sending mail
with a subject of "unsubscribe" to gnupg-users-request@gnupg.org