How to verify a SAML signature for HTTP-redirect binding

I'm receiving a SAML request via HTTP-redirect binding the content of the SAML request look like this

{"SigAlg"=>"http://www.w3.org/2000/09/xmldsig#rsa-sha1", "SAMLRequest"=>"lVLLaoQwFP0VyT5jEqPG4AiFoSDMtNApXXQzxDxaQRObRDqfX3XoolAKXd7DPQ/uuXUQ4zDxo3tzc3zSH7MOMWkPe3DpcixzVVVQl4RBqoiCncEYEmkoY7k00hCQvGgfemf3gOwQSNoQZt3aEIWNC4RwCRGGiD6jkmPMs2KHUPYKksPi0lsRN+Z7jFPgafqpvejtbtQpSK7jYAPfsu3B7C13IvSBWzHqwKPk57vTkS+WfPIuOukG0NSbub9R/yaJELRfzUGzrhmtFut15qdeeheciY926K2u05toUz8sIu0huXd+FPFv9RXpFTTbKp/WA4WobQT/jEYrykwhNaQ66yDNMwY7wijEtMCmysqqo6xOb8Ga+tbjWYe1jtYqfW0uCucoYwWCHS3F0kRGoajWTpAiiJRZJRmu01+Y3+CPt2i+AA=="}

It also has a Signature value

WkDaGzC6vPTlzh+EnFA5/8IMmV7LviyRh2DA5EHF0K0nl+xzBlKfNCYRnunpwoEvGhereGdI5xBpv+mc9IguiCaLZSZjDh6lIDdpvctCnmSNzORqzWQwQGeZ9vjgtCLjUn35VZLNs3WgEqbi2cL+ObrUDS2gV1XvBA3Q3RRhoDmi+XE89Ztnd1cNpR3XdA+EL2ENbMI2XAD9qSgMufUJY/3GBBpT7Vg1ODtPxBudq+sXrgPh/+WtUUitLkkfC8tdRTCS1EZPv+h27I5g/VNza23Xl8w2HdAuYP0F2FjREo8VV2aUtaOUd/jAF9+bfkGV93y1PzFttLxdBbFoxp6qBg==

But I fail to understand how to verify this signature is correct.

Section 3.4.4.1 on SAML binding https://docs.oasis-open.org/security/saml/v2.0/saml-bindings-2.0-os.pdf

To construct the signature, a string consisting of the concatenation of the RelayState (if present),
SigAlg, and SAMLRequest (or SAMLResponse) query string parameters (each one URLencoded)
is constructed in one of the following ways (ordered as below):
SAMLRequest=value&RelayState=value&SigAlg=value
SAMLResponse=value&RelayState=value&SigAlg=value

I tried the approach but

• The signature I generated using the Private key does not match to the one I received from my SP. (posted above)

• Also, I'm not able to decrypt the signed message using the Private key (I'm assuming the Signature was created using the public that I federated it with.)

<samlp:LogoutRequest ID="_36167d94-d868-4c04-aee3-8bbd4ed91317" Version="2.0" IssueInstant="2017-01-05T16:21:55.704Z" Destination="https://werain.me/" xmlns:samlp="urn:oasis:names:tc:SAML:2.0:protocol"><Issuer xmlns="urn:oasis:names:tc:SAML:2.0:assertion">urn:federation:MicrosoftOnline</Issuer><NameID Format="urn:oasis:names:tc:SAML:2.0:nameid-format:persistent" xmlns="urn:oasis:names:tc:SAML:2.0:assertion">4948f6ce-4e3b-4538-b284-1461f9379b48</NameID><samlp:SessionIndex>_eafbb730-b590-0134-a918-00d202739c81</samlp:SessionIndex></samlp:LogoutRequest>

Any help here.

A SAML authentication message is a XML document with an embedded (enveloped) XMLDSig signature or a deflated encoding signature

Enveloped XMLDSign signature

<samlp:LogoutRequest>
    <...saml message...> 
    <ds:Signature>
         <ds:SignedInfo />
         <ds:SignatureValue /> 
         <ds:KeyInfo /> 
    </ds:Signature> 
</samlp:LogoutRequest>

<ds:SignatureValue> contains the signature, <ds:SignedInfo> the signed data and a reference to the message and <ds:KeyInfo> usually contains the X509Certificate with the identity of the signer, or a reference to that certicate

Deflated encoding in URL

SAMLRequest=value&RelayState=value&SigAlg=value&Signature=value

Where each value is url encoded

SAMLRequest=urlencode(base64(<samlp:LogoutRequest> <...saml message...> </samlp:LogoutRequest>))

And the signature is done on a concatenation of query string algorithm using the algorithm SigAlg

Signature = urlencode( base64 ( SigAlg ("SAMLRequest=value&RelayState=value&SigAlg=value")))

Digital signature of SAML messages

SAML message is digitally signed (not encrypted) with the private key of the issuer (SP), and can be verified with the public key of the SP. A SAML response must be signed with the private key of the identity provider (IdP), and the SP can verify the message with the public key of the IdP.

If you act as IdP and you want to verify a SAML request of the SP, you need:

• Verify the digital signature: Verify using the public key of the SP that the signature match with the signed message to ensure the identity of the signer and the message has not been altered

• Authorize the request: Verify that the identity of the signer can perform the requested operation. Usually you have to match the serial number or the subject of the certificate with a pre-existent list, or verify that the certificate has been issued by a trusted certificate authority

• Generate the SAML response: Generate a XML message with the SAML data and sign it with your private key to send to SP

Most programming languages support XMLDsig signatures but in your case is used the deflated encoding that is a specific characteristic of SAML binding, so if your SAML library does not support it, you have to verify the signature manually. These are more or less the steps to follow according to specification

 //get params from query string 
String samlrequest = getQueryParam("SAMLRequest");
String relaystate = getQueryParam("RelayState");
String sigalg = getQueryParam("SigAlg");
String signature = getQueryParam("Signature");


//The signature
byte signature[] = URLDecoder.decode(Base64.getDecoder().decode(signature ), "UTF-8");

//The signed data. build the following string checking if RelayState is null
//SAMLRequest=samlrequest&RelayState=relaystate&SigAlg=sigalg
byte signedData[] = concat(samlrequest,relaystate,sigalg);

//The signature algorithm could be "SHA1WithRSA" or "SHA1withDSA" depending on sigalg is http://www.w3.org/2000/09/xmldsig#rsa-sha1 or http://www.w3.org/2000/09/xmldsig#dsa-sha1 
String signatureAlgorithm = extractSignatureAlgorithm(sigalg);

//get the public key of the SP. It must be registered before this process
PublicKey publicKey = ...

//Verify the signature
Signature sig = Signature.getInstance(signatureAlgorithm);
sig.initVerify(publicKey);
sig.update(signedData); 
boolean verifies = sig.verify(signature);