How to load a DSA Key from KeyInfo using openSSL

I am trying to verify an XML digital signature using openSSL. When I actually use EVP_VerifyFinal, I get the error code 0D07209B (ASN1_get_object:too long). He's how I load the the KeyInfo from the cert:

<KeyInfo>
 <KeyValue>
  <DSAKeyValue>
    <P>/KaCzo4Syrom78z3EQ5SbbB4sF7ey80etKII864WF64B81uRpH5t9jQTxeEu0ImbzRMqzVDZkVG9xD7nN1kuFw==</P>
    <Q>li7dzDacuo67Jg7mtqEm2TRuOMU=</Q>
    <G>Z4Rxsnqc9E7pGknFFH2xqaryRPBaQ01khpMdLRQnG541Awtx/XPaF5Bpsy4pNWMOHCBiNU0NogpsQW5QvnlMpA==</G>
    <Y>butK4tBy8dwSJFjTRpTvmYZYnsDGO4CzMVgcD8EQ2UJrQZd0ZapQI/Ea2DZzQBTFjjdnNkFuNOtjVI615lhiBQ==</Y>
  </DSAKeyValue>
 </KeyValue>
</KeyInfo>

My (pseudocode) method for loading the PDSA:

 pDSA = DSA_new();
 pDSA.p = BN_bin2bn(base64Decode(text of P element));
 pDSA.q = BN_bin2bn(base64Decode(text of Q element));
 pDSA.g = BN_bin2bn(base64Decode(text of G element));
 pDSA.pub_key = BN_bin2bn(base64Decode(text of Y element));

Using BN_bn2hex after this gives me the values:

p: FCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17
q: 962EDDCC369CBA8EBB260EE6B6A126D9346E38C5
g: 678471B27A9CF44EE91A49C5147DB1A9AAF244F05A434D6486931D2D14271B9E35030B71FD73DA179069B32E2935630E1C2062354D0DA20A6C416E50BE794CA4
pub_key: 6EEB4AE2D072F1DC122458D34694EF9986589EC0C63B80B331581C0FC110D9426B41977465AA5023F11AD836734014C58E376736416E34EB63548EB5E6586205

the, validating the signature:

  <Signature xmlns="http://www.w3.org/2000/09/xmldsig#">
    <SignedInfo>
      <CanonicalizationMethod Algorithm="http://www.w3.org/TR/2001/REC-xml-c14n-20010315"/>
      <SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#dsa-sha1"/>
      <Reference URI="">
        <Transforms>
         <Transform Algorithm="http://www.w3.org/2000/09/xmldsig#enveloped-signature"/>
       </Transforms>
       <DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1"/>      
       <DigestValue>uooqbWYa5VCqcJCbuymBKqm17vY=</DigestValue>
      </Reference>
    </SignedInfo>    
    <SignatureValue>L4h4TFDj5rDKCHm0D+aH2LeSfAMV2t0V5S91Afu6U0NlfpjxdTXRUA==</SignatureValue> 
    <KeyInfo>
     <KeyValue>
      <DSAKeyValue>         
       <P>/KaCzo4Syrom78z3EQ5SbbB4sF7ey80etKII864WF64B81uRpH5t9jQTxeEu0ImbzRMqzVDZkVG9xD7nN1kuFw=</P> 
       <Q>li7dzDacuo67Jg7mtqEm2TRuOMU=</Q> 
       <G>Z4Rxsnqc9E7pGknFFH2xqaryRPBaQ01khpMdLRQnG541Awtx/XPaF5Bpsy4pNWMOHCBiNU0NogpsQW5QvnlMpA==</G>
       <Y>POKkQtGuazaz6OEWi91P4C9z1tREpeP9f7L3piRD/3TiNFzvt0BmYzNO0CoPSjEVTXYKIRo/+HXK6MhBRk2eUw=</Y>
     </DSAKeyValue>
    </KeyValue>
   </KeyInfo>
  </Signature>
</Envelope>

Here's how I validate the signature:

  pkey = EVP_PKEY_new;
  EVP_PKEY_set1_DSA(pkey, pdsa)
  EVP_MD_CTX_init(ctx);
  EVP_VerifyInit(@ctx, EVP_sha1)
  EVP_VerifyUpdate(@ctx, digest of SignedInfo);
  bytes = unbase64(text of SignatureValue)
  EVP_VerifyFinal(@ctx, btes, length(bytes)}, pKey);

Verify final returns the following errors:

0D07207B:asn1 encoding routines:ASN1_get_object:header too long)
0D068066:asn1 encoding routines:ASN1_CHECK_TLEN:bad object header)
0D07803A:asn1 encoding routines:ASN1_ITEM_EX_D2I:nested asn1 error)

So either I am loading the certificate or the signature value wrongly. According the spec, the signature value is "The signature value consists of the base64 encoding of the concatenation of two octet-streams that respectively result from the octet-encoding of the values r and s in that order" - but I cannot find anywhere in the openSSL documentation what should be passed to EVP_VerifyInit for the signature value for a DSA signature. I found one reference in an email archive that pointed to RFC 3279 which appears to specify the same format, so far as I can tell (Dss-Sig-Value ::= SEQUENCE { r INTEGER, s INTEGER }

Solution

Yes, you've actually already answered your own question. You should split the received signature in two (two 20 byte values as specified by XML-DSig), and then create the ASN.1 signature. It would indeed consist of the following ASN.1 DER structure:

Dss-Sig-Value ::= SEQUENCE {
    r INTEGER,
    s INTEGER
}

DER is a "tag, length, value" structure. Now a SEQUENCE has tag encoding 30, then a DER length of the two encoded integers, and r and s are INTEGER values, encoded with tag 02 then the length followed by the shortest representation of a signed big endian integer.

As programming ASN.1 is tricky at best and downright vulnerable as worst (all versions up to 1.0.1 of OpenSSL had a memory corruption bug, Windows NT authentication of old was completely broken) I'll show how to create this structure using pseudo code:

convert the base64 to bytes (unsigned chars, forty of them)
use the first 20 bytes for rData, the second for sData (or better, split in half)
strip all leading (leftmost) 00 valued bytes of rData and sData
if the leading byte is 80 or over, prefix a 00 byte to rData an sData
create a structure 30 LL { 02 LL { rData } 02 LL { sData } } where LL is the size in bytes of the structure between braces

I'll leave it to you to perform the encoding. Note that this will work as long as LL is never the value of 128 or over (which should be the case for DSA).

You may want to switch to ECDSA by the way; note that it would likely require the same structure above. Also note that I cannot see if the input of the digest is correct, but it should at least resolve the ASN.1 error.

In the end you should get this structure for you current signature (note that this one is a bit boring as it doesn't contain any initial values of 00 and it does not contain any initial bytes equal to or higher than 128 either).