2
$\begingroup$

I'm trying to implement own DSA signature check as per guide at this site page 20 in python.

kp = 0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
kq = 0xc773218c737ec8ee993b4f2ded30f48edace915f
kg = 0x626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
ky = 0x19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333

sh = 0xa9993e364706816aba3e25717850c26c9cd0d89d
sr = 0x8bac1ab66410435cb7181f95b16ab97c92b341c0
ss = 0x41e2345f1f56df2458f426d155b4ba2db6dcd8c8

w = pow(ss, -1, kq)
u1 = (sh * w ) % kq 
u2 = (sr * w ) % kq
v = ((pow(kg, u1, kp) * pow(ky, u2, kp)) % kp) % kq
print("v", hex(v), v)

print("signature is (r = v):", sr == v)

it gives true and works as expected. then knowing private key, I've decided to export key to OpenSSL with

key = DSA.construct((ky, kg, kp, kq, kx))
print(key.exportKey())

and then got public key, generated certificate and signed "abc" from example and verification in OpenSSL is also valid. I've also used openssl asn1parse in attempt to get r and s from new signature.

929:d=5 hl=2 l= 9 cons: SEQUENCE
931:d=6 hl=2 l= 7 prim: OBJECT :dsaWithSHA1 940:d=5 hl=2 l= 46 prim: OCTET STRING [HEX DUMP]:302C02140977C4B483B4C9E9620BA2679EBB7A03D020FB3B02143E6E3616A1034D4D24E387A5FDC5FB77DD8362A4

I've tried to use 0x0977C4B483B4C9E9620BA2679EBB7A03D020FB3B as r and 0x3E6E3616A1034D4D24E387A5FDC5FB77DD8362A4 as s and it doesn't work. What should be done to get r and s from this octet string?

Thank you in advance.

UPDATE 1: what is NOT working

kp = 0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
kq = 0xc773218c737ec8ee993b4f2ded30f48edace915f
kg = 0x626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
ky = 0x19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333

sh = 0xa9993e364706816aba3e25717850c26c9cd0d89d
sr = 0x0977C4B483B4C9E9620BA2679EBB7A03D020FB3B
ss = 0x3E6E3616A1034D4D24E387A5FDC5FB77DD8362A4

w = pow(ss, -1, kq)
u1 = ( sh * w ) % kq 
u2 = ( sr * w ) % kq
v = ((pow(kg, u1, kp) * pow(ky, u2, kp)) % kp) % kq
print("v", hex(v), v)

print("signature is (r = v):", sr == v)

I've checked sha1 digest in signature and it is the same

  662:d=5  hl=4 l= 263 cons:      cont [ 0 ]        
  666:d=6  hl=2 l=  24 cons:       SEQUENCE          
  668:d=7  hl=2 l=   9 prim:        OBJECT            :contentType
  679:d=7  hl=2 l=  11 cons:        SET               
  681:d=8  hl=2 l=   9 prim:         OBJECT            :pkcs7-data
  692:d=6  hl=2 l=  28 cons:       SEQUENCE          
  694:d=7  hl=2 l=   9 prim:        OBJECT            :signingTime
  705:d=7  hl=2 l=  15 cons:        SET               
  707:d=8  hl=2 l=  13 prim:         UTCTIME           :220606200747Z
  722:d=6  hl=2 l=  35 cons:       SEQUENCE          
  724:d=7  hl=2 l=   9 prim:        OBJECT            :messageDigest
  735:d=7  hl=2 l=  22 cons:        SET               
  737:d=8  hl=2 l=  20 prim:         OCTET STRING      [HEX DUMP]:A9993E364706816ABA3E25717850C26C9CD0D89D
...
  929:d=5  hl=2 l=   9 cons:      SEQUENCE          
  931:d=6  hl=2 l=   7 prim:       OBJECT            :dsaWithSHA1
  940:d=5  hl=2 l=  46 prim:      OCTET STRING      [HEX DUMP]:302C02140977C4B483B4C9E9620BA2679EBB7A03D020FB3B02143E6E3616A1034D4D24E387A5FDC5FB77DD8362A4

Key seems to be the same as well

    0:d=0  hl=3 l= 240 cons: SEQUENCE          
    3:d=1  hl=3 l= 168 cons:  SEQUENCE          
    6:d=2  hl=2 l=   7 prim:   OBJECT            :dsaEncryption
   15:d=2  hl=3 l= 156 cons:   SEQUENCE          
   18:d=3  hl=2 l=  65 prim:    INTEGER           :8DF2A494492276AA3D25759BB06869CBEAC0D83AFB8D0CF7CBB8324F0D7882E5D0762FC5B7210EAFC2E9ADAC32AB7AAC49693DFBF83724C2EC0736EE31C80291
   85:d=3  hl=2 l=  21 prim:    INTEGER           :C773218C737EC8EE993B4F2DED30F48EDACE915F
  108:d=3  hl=2 l=  64 prim:    INTEGER           :626D027839EA0A13413163A55B4CB500299D5522956CEFCB3BFF10F399CE2C2E71CB9DE5FA24BABF58E5B79521925C9CC42E9F6F464B088CC572AF53E6D78802
  174:d=1  hl=2 l=  67 prim:  BIT STRING        
      0000 - 00 02 40 19 13 18 71 d7-5b 16 12 a8 19 f2 9d 78   [email protected].[......x
      0010 - d1 b0 d7 34 6f 7a a7 7b-b6 2a 85 9b fd 6c 56 75   ...4oz.{.*...lVu
      0020 - da 9d 21 2d 3a 36 ef 16-72 ef 66 0b 8c 7c 25 5c   ..!-:6..r.f..|%\
      0030 - c0 ec 74 85 8f ba 33 f4-4c 06 69 96 30 a7 6b 03   ..t...3.L.i.0.k.
      0040 - 0e e3 33   

and private as well

    0:d=0  hl=3 l= 198 cons: SEQUENCE          
    3:d=1  hl=2 l=   1 prim:  INTEGER           :00
    6:d=1  hl=3 l= 168 cons:  SEQUENCE          
    9:d=2  hl=2 l=   7 prim:   OBJECT            :dsaEncryption
   18:d=2  hl=3 l= 156 cons:   SEQUENCE          
   21:d=3  hl=2 l=  65 prim:    INTEGER           :8DF2A494492276AA3D25759BB06869CBEAC0D83AFB8D0CF7CBB8324F0D7882E5D0762FC5B7210EAFC2E9ADAC32AB7AAC49693DFBF83724C2EC0736EE31C80291
   88:d=3  hl=2 l=  21 prim:    INTEGER           :C773218C737EC8EE993B4F2DED30F48EDACE915F
  111:d=3  hl=2 l=  64 prim:    INTEGER           :626D027839EA0A13413163A55B4CB500299D5522956CEFCB3BFF10F399CE2C2E71CB9DE5FA24BABF58E5B79521925C9CC42E9F6F464B088CC572AF53E6D78802
  177:d=1  hl=2 l=  22 prim:  OCTET STRING      [HEX DUMP]:02142070B3223DBA372FDE1C0FFC7B2E3B498B260614
$\endgroup$
5
  • $\begingroup$ An online ASN.1 decoder confirms you got the decoding right. One possibility is that your sh is not the same as OpenSSL's. It's surprisingly hard to get OpenSSL to DSA-sign 3 bytes after hashing them with SHA-1 exactly once! Another possibility is that somehow OpenSSL does not use the same key as you do. $\endgroup$
    – fgrieu
    Commented Jun 8, 2022 at 9:23
  • $\begingroup$ To me "and it doesn't work" doesn't really cover the error... What exactly are you trying to do and how? $\endgroup$
    – Maarten Bodewes
    Commented Jun 8, 2022 at 17:10
  • $\begingroup$ The key is consistent: $p$ is prime, $q$ is prime, $p\bmod q=1$, $g^q\bmod p=1$, $g^x\bmod p=y$. The hash is the SHA-1 of abc in ASCII. The issue could be that what's signed is not abc in ASCII, but a larger data block including the SHA-1 of abc in ASCII, the signing time, and possibly other stuff. How exactly was that signature obtained? $\endgroup$
    – fgrieu
    Commented Jun 8, 2022 at 19:58
  • 1
    $\begingroup$ I've performed following sequence after export of the key to dsa-priv.key: first I've got a public key openssl dsa -in dsa-priv.key -outform der -pubout -out dsa-pub.key then I've generated a cert file: openssl req -new -x509 -key dsa-priv.key -out dsacert.pem then I've signed a sample.dat with abc inside using private key and certfile openssl smime -sign -in ../sample.dat -out sample.test -signer dsacert.pem -inkey dsa-priv.key -outform pem. Yes, I have impression signing time somehow considered. $\endgroup$ Commented Jun 8, 2022 at 21:01
  • 2
    $\begingroup$ (@fgrieu) Yes openssl smime -sign -outform pem does CMS/PKCS7 SignedData which by default computes the signature over signedAttributes which includes the data digest, contentType, signingTime, and (sometimes? mostly-useless) smimeCapabilities (and re-encoded without the implicit tagging used in the message). Use -noattr to get a signature over only the data. Compare crypto.stackexchange.com/questions/87009/… . $\endgroup$ Commented Jun 8, 2022 at 23:58

1 Answer 1

2
$\begingroup$

The question has the following things correct:

  • $(p,q,g)$ = (0x8df2…0291, 0xc773…915f, 0x626d…8802) are a consistent set of DSA-1024 parameters: $\|p\|=1024\,$, $\|q\|=160\,$, $p$ and $q$ are prime, $p\bmod q=1\,$, $1<g<p\,$, $g^q\bmod p=1\,$.
  • $y$ = 0x1913…e333 is a consistent public key value for these parameters: $1<y<p\,$, $y^q\bmod p=1$.
  • $y$ is consistent with the private key value $x$ = 0x2070…0614 : $g^x\bmod p=y\,$.
  • $h$ = 0xa999…d89d is the SHA-1 hash of the 3-byte bytestring coding the three characters abc per UTF-8 (or ASCII extended to 8 bits by adding a high-order bit at zero, or any of the many 8-bit character sets compatible with ASCII).
  • $(r,s)$ = (0x0977…FB3B,0x3E6E…62A4) is the pair of ASN.1-decorated integers in the bytestring 302C02140977…62A4 and is consistent with being a DSA signature per the above parameters: $0<r<q$ and $0<s<q$.
  • except for lacking the range check for $r$ and $s$, the python code for the signature verification is correct.

The reason why the signature $(r,s)$ does not check is that it's not a signature of the 3-byte bytestring coding the three characters abc per UTF-8, but of a more complex message, including the signingTime field. See dave_thompson_085's comment which explains why, and suggests a modifier that may help towards the difficult goal of controlling what OpenSSL actually signs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.