DSA and SHA-256 (It works! Or does it?! :))

[Sam Vilain]

I notice in FIPS-186-3, it specifies that the 'leftmost' N bits of the
Hash output function are to be used.

However, in the source I see this:

    /* s = (kinv * ( hash + x * r)) mod q */
    tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
    mpi_mul( tmp, skey->x, r );
    mpi_add( tmp, tmp, hash );
    mpi_mulm( s , kinv, tmp, skey->q );

This approach makes more sense to me; all of the bits in the hash output
will influence the output value of r and s.

But the standard says no, throw away those low bits.

This seems wrong; for instance assuming you are using SHA-256 and DSA -
a combination which the gnupg I'm using (Lenny's 1.4.9) will quite
happily let me configure - then instead of using an 80-round 160-bit
cipher, you're using 160 bits of a 64-round 256-bit cipher.  I may be
entirely wrong about this but that smells very bad to me.

That being said, I see in the source eg g10/sign.c that this case is
well described already.  I can't find the exact source line where this
truncation happens, but I assume it does somewhere.

So what happened when I specified to use SHA-256 and re-signed my key
using gpg --expert --edit-key KEYID?

After all, it seems to have worked;

:public key packet:
        version 4, algo 17, created 1102842997, expires 0
        pkey[0]: [1024 bits]
        pkey[1]: [160 bits]
        pkey[2]: [1023 bits]
        pkey[3]: [1022 bits]
:user ID packet: "Sam Vilain <sam at vilain.net>"
:signature packet: algo 17, keyid FC06408866B25843
        version 4, created 1263337421, md5len 0, sigclass 0x13
        digest algo 8, begin of digest 9e bf
        hashed subpkt 27 len 1 (key flags: 03)
        hashed subpkt 11 len 4 (pref-sym-algos: 9 8 7 3)
        hashed subpkt 21 len 4 (pref-hash-algos: 10 9 8 11)
        hashed subpkt 22 len 4 (pref-zip-algos: 2 3 1 0)
        hashed subpkt 30 len 1 (features: 01)
        hashed subpkt 23 len 1 (key server preferences: 80)
        hashed subpkt 2 len 4 (sig created 2010-01-12)
        hashed subpkt 25 len 1 (primary user ID)
        subpkt 16 len 8 (issuer key ID FC06408866B25843)
        data: [159 bits]
        data: [159 bits]

I haven't got --enable-dsa2 set in my .gnupg/gpg.conf

What is in that subpacket?  Pulling it apart (using
Crypt::OpenPGP::Message), I can see that r is
563842300114387388457394839662831482428878447936 and s is
377105405312767191687013088546003017320679158753 - definitely both <160 bit.

I've just tried to reproduce what's going on, but I didn't manage to get
Crypt::DSA to bend to my whim just yet.  The whole key is here:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1.4.9 (GNU/Linux)

mQGiBEG8DHURBACJ1uLqJ6ZMfz6Qz/bPDy6jNGFJTHOPrbseh8nBKmHjXW6fJiM3
sC8Y+c1E1tqcrahG57Y+XPVEX6sMbb7XLeLCfruUV6NpXeUvC1GDKTUJFAsdyB8z
W4FH6hepb9zZ3GZ/7bIN6VsanUEPJ8IprRzPpeB29XD3cF6gKuhccHkjtwCgz0N/
JTUbOvr2XOx9ccZWchXOLTED/0cA7hXjLvZNQABBH8RQrveTdVIZJXuVG2BCXAdZ
jRCphfJDGntkTznogEx67Q1KWfZx9/PdY/pUepcGHBeyOjkrhKORY5tw3ZXcUzvV
UGczOHFcK3hL+FW4V7DDjcfZJlqzWQf5O54BfdkuV3ongnft0Rr15MpeVKL6fmC7
hT5LA/45I24pSBkO9jgoVA2aGvpyBwt2S5BsPbdVuawMeCJ6YJ6sJyMYONjqh7L3
GvnI44hXJ07Yo5F7n8XXYvXPCYu2OQOUvsXmUsrQSUYahlLY/eITCP33FeTt8EDX
yGAZMrxTsEEaub3xsd4c9SwH3w7sl1JAfrhtn0AxkKaUbzNYl7QoU2FtIFZpbGFp
biAoQ1BBTiBhdXRob3IpIDxzYW12QGNwYW4ub3JnPohhBBMRCAAhBQJLTPdnAhsD
BQsJCAcDBRUKCQgLBRYCAwEAAh4BAheAAAoJEPwGQIhmslhDztEAoMQ/F7SJlgcZ
SpeQdk2bPQKcKs2BAJ975KAl1LHBfsaSJyJqV4gpEM6arLQbU2FtIFZpbGFpbiA8
c2FtQHZpbGFpbi5uZXQ+iGQEExEIACQCGwMFCwkIBwMFFQoJCAsFFgIDAQACHgEC
F4AFAktM/80CGQEACgkQ/AZAiGayWEOevwCfYsOQLFkHUzfq/EWk7diBp4c/ZUAA
n0IN/cAGNmAVjjicDQcRx6vGiTPhtCdTYW0gVmlsYWluIDxzYW0udmlsYWluQGNh
dGFseXN0Lm5ldC5uej6IYQQTEQgAIQUCS0z3ZwIbAwULCQgHAwUVCgkICwUWAgMB
AAIeAQIXgAAKCRD8BkCIZrJYQ/gcAKCd0uLxlwEsMiNBT6tws/L1WCRE4QCeIic+
sSXeCKtX6pHDT5Ke6bN5hG+0J1NhbSBWaWxhaW4gKG11Z3d1bXApIDxzYW12QHV0
c2wuZ2VuLm56PohhBBMRCAAhBQJLTPdnAhsDBQsJCAcDBRUKCQgLBRYCAwEAAh4B
AheAAAoJEPwGQIhmslhDlAwAn2MZMvhwAc6qSsePK0t2iXKPVSYGAJ9st/46fUAu
WIIjJhV93gANWnIjd7kBDQRBvAyEEAQAi7Ik8iXYjBKgmlBq2Jp7WUkHR4i7ZuyT
rJNamhh6pRjhEQHNpRENExnuEunBbrxJlUwyhGmqj4FzI9yGwtBMBCx0xyOXTqf5
AcENJmOC/W6+rN5FbleOP9PLb26MjFOjbWmG2AJeFDlh3XM3oxN2ZGyP5DcdAd7P
1p+OlvHvaP8AAwcD/3Iu8t/6D7b1pz1SouSVmFli0phAxZnuu5QKLXBC4/c+Vzqg
nmA7WPBHk/N9wTUAMvhVAGdxbzmyr6QITU1zYYWVWzqf62dZ66R/RP2ZHwIwpNfJ
tG/5VwNSLaavuW81KwDr/djsaWQUNrypOAODcjCyXJLyA+psdlfD7on1DENRiEkE
GBECAAkCGwwFAkWm0W4ACgkQ/AZAiGayWENKBwCguIZ2Cr473BEBp00+fPtxzKqo
FLIAn34sQHoLgFz5gLuXMgjZEJ1yhne6
=+UwW
-----END PGP PUBLIC KEY BLOCK-----

So my questions are;

1. is gpg doing the correct, FIPS-186-3 thing of throwing away the lower
bits?

2. is this safe?

Cheers,
Sam