Wednesday, March 28, 2018

Find Number of Sub-Sets That Add Up To A Target Sum - Dynamic Programming

Problem Definition

Given an array of positive integers greater than 0, find the number of subsets whose sum is equal to a given target sum.
input[] = {2, 7, 9, 12, 14, 7}
target sum = 14

output: 3
Explanation: There are 3 subsets that sum to 14. These are {2, 12}, {14}, {7, 7}
This can be solved using Recursion and Dynamic Programming. First recursion will be applied, then to minimize the complexity, DP is used to store and retrieve the already computed values.

Recursion

To compute subset, during the iteration of given array, at each item we have a choice whether the item will be in the subset or not.
If we decide to include the item in subset, then new target sum will be targetSum - item.
If we decide not to include the item, then the we need to keep on looking for the same target sum.

In other word, for an index i,
total subsets = total subsets that includes input[i] + total subsets that excludes input[i]

This is relation we will use for the recursion.

Recursive Solution

Time Complexity

Time complexity is determined by the number of times the recursive method compute() is called. Problem here is the method compute() is called over and over again for the same arguments. The Time Complexity for this recursive method will be ${\cal O}(2^n)$ which is exponential.

Obviously this is not an efficient solution. Since we calling the method compute() over and over again for the same arguments, we can optimize our solution using Dynamic Programming,Memoization in this case by memorizing the intermediate results.

Recursive Solution with Dynamic Programming

Time Complexity

Again, time complexity is determined by the number of times the recursive method computeDP() is called. Unlike previous method, now at most this method will be called $n \times targetSum * 2$ where $n$ is number of elements in the input array.

So the Time Complexity is ${\cal O}(n * targetSum)$ time.






Tuesday, March 27, 2018

Open SAML - Decryption of Encrypted Assertions

Recently I had a task to parse a SAML Response and extract necessary parameter to make a decision. I used OpenSaml for this task.

The parsing portion was easy. You will be receiving SAML Response in XML format. The XML might be Base64 Encoded, in which case, you will need to decode using the same Base64 to get plain XML Response.

  public String decodeBase64(String base64EncodedInput) {
    // its safe to URL Decode first
    URLCodec encoder = new URLCodec();
    String urlDecoded = encoder.decode(base64EncodedInput);
    
    byte[] bytes = Base64.getDecoder().decode(urlDecoded);
    
    return new String(bytes);
  }

    
Once we have the plain XML SAML Response, we can construct org.oopensaml2.saml.core.Response object from the following code snippet:

  public Response parse(String samlXml) throws IOException, SAXException, ParserConfigurationException {
    Response response;
    Element root;
    StringReader reader = new StringReader(samlXml);
    InputSource is = new InputSource(reader);

    DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
    factory.setNamespaceAware(true);
    DocumentBuilder documentBuilder = null;
    documentBuilder = factory.newDocumentBuilder();

    Document doc = documentBuilder.parse(is);
    root = doc.getDocumentElement();
    response = unmarshall(root);

    return response;
  }

  public  T unmarshall(Element element) {
    try {
      UnmarshallerFactory unmarshallerFactory = Configuration.getUnmarshallerFactory();
      return (T) unmarshallerFactory.getUnmarshaller(element).unmarshall(element);
    } catch (UnmarshallingException ux) {
      throw new RuntimeException(ux);
    }
  }

      
After we have Response object, we can access parameters which are normally stored as Assertions. An Assertion in turn contains a list of AttributeStatements. In the AttributeStatement, we can see list of Attributes, which we can use for making required decision.

  Assertion assertion = response.getAssertions().get(0);
  AttributeStatement statement = assertion.getAttributeStatements().get(0);
  Attribute attribute = statement.getAttributes().get(0);

      

Problem

The problem is, you cannot expect to get Unencrypted Assertions every time. They will be encrypted most of the times. To extract the actual data from encrypted Assertions, we first need to decrypt it.

Public and Private Key

A public certificate is required to encrypt an Asssertion and a private key is required to decypt. SAML Tool is great tool for testing with SAML Responses. There you can generate test Public and Private keys for testing.

Decrypt Encrypted Assertion

Following method can be used for the Decryption.

  private Assertion decryptEncryptedAssertion(EncryptedAssertion encryptedAssertion) throws IOException, NoSuchPaddingException,
      NoSuchAlgorithmException, InvalidKeyException, BadPaddingException, IllegalBlockSizeException,
      DecryptionException, InvalidKeySpecException, CertificateException {
      File privateKeyFile = new File(FORMATTED_PRIVATE_KEY_FILE_PATH);
      InputStream privateKeyStream = new FileInputStream(privateKeyFile);

      PKCS8EncodedKeySpec spec = new PKCS8EncodedKeySpec(IOUtils.toByteArray(privateKeyStream));
      KeyFactory factory = KeyFactory.getInstance("RSA"); // Algorithm as "RSA" here can differ based on your actual encryption
      PrivateKey privateKey = factory.generatePrivate(spec);
      BasicX509Credential cred = new BasicX509Credential();
      cred.setPrivateKey(privateKey);

      StaticKeyInfoCredentialResolver resolver = new StaticKeyInfoCredentialResolver(cred);
      Decrypter decrypter = new Decrypter(null, resolver, new InlineEncryptedKeyResolver());
      decrypter.setRootInNewDocument(true);
      Assertion decrypted = decrypter.decrypt(encryptedAssertion);
      return decrypted;
    } // decryptEncryptedAssertion

      

Issue 1 : Formatted Private Key File

In the above code snippet, if you set the path FORMATTED_PRIVATE_KEY_FILE_PATH to point to the actual private key file you have generated, then you will have following exception:
java.security.InvalidKeyException: invalid key format

Solution

The problem is, you cannot directly use the private key you have generated. You need to convert it into a Java readable format and can be done using the following Commandlint Command:

  openssl pkcs8 -topk8 -inform PEM -outform DER -in <PRIVATE_KEY_FILE_NAME> -nocrypt > pkcs8_key
      
Then FORMATTED_PRIVATE_KEY_FILE_PATH should point to this generated file pkcs8_key

Issue 2 : saml:Assertion is not bound

At some time I also had a issue where the encrypted assertion could not be decrypted. Upone debugging, I found the following message:
invalid xml, prefix saml in saml:Assertion is not bound
This was a minor error because of namespace for the prefix saml. This was fixed using a proper namespace declaration in the element saml:Assertion before encryption.
<saml:Assertion xmlns="urn:oasis:names:tc:SAML:2.0:assertion"> .... </saml:Assertion>

Issue 3: Issue During JUnit Test Using Mockito

This issue was particularly nasty one. Nasty because it was hard for me to pin point the real cause (Although it turned out to be very simple.) So my implementation was working fine when running in server mode. I fell into problem when I wrote JUnit test for it. I wrote JUnit test using Mockito. I got the following exception when running the test.

  ERROR [main] encryption.Decrypter - Failed to decrypt EncryptedKey, valid decryption key could not be resolved
  [2018-03-02 15:05:16,478] ERROR [main] encryption.Decrypter - Failed to decrypt EncryptedData using either EncryptedData KeyInfoCredentialResolver or EncryptedKeyResolver + EncryptedKey KeyInfoCredentialResolver
  [2018-03-02 15:05:16,482] ERROR [main] encryption.Decrypter - SAML Decrypter encountered an error decrypting element content
  org.opensaml.xml.encryption.DecryptionException: Failed to decrypt EncryptedData

      
The exception message valid decryption key could not be resolved was misleading the key was working in server mode and was placed in proper location.

I had to debug deep down into the library class itself to finally find the following:

 java.lang.ClassCastException: com.sun.crypto.provider.AESCipher cannot be cast to javax.crypto.CipherSpi 
 com.sun.crypto.provider.RSACipher cannot be cast to javax.crypto.CipherSpi

      

Solution

This exception message led me to HERE and found the solution was to include the following in the test class.

  @PowerMockIgnore({"com.sun.net.ssl.internal.ssl.Provider", "javax.crypto.*"})

      
Issue 4: Issue due to AES256 and AES128 Compatibility
I encountered this error after long time the solution was deployed. What happened was, all our PCs joined company network, so that we could log into our PCs through company credentials. So new profiles were created. When I tried to run this already deployed, it didn't run. Actually a JUnit test failed (Thanks to JUnit test that I encountered this error). The JUnit test was showing an error message org.opensaml.xml.encryption.DecryptionException: Failed to decrypt EncryptedData. My initial idea was, during the import of the project, the test private key file might have changed. I was completely wrong. I went on to run the whole server and tried to log in using a sample response. It failed!! Then I checked log files where I found this error message.

        org.opensaml.xml.validation.ValidationException: Unable to evaluate key against signature
 at org.opensaml.xml.signature.SignatureValidator.validate(SignatureValidator.java:74)
 at com.worldlingo.servlet.SamlServlet.verifySignature(SamlServlet.java:447)
 at com.worldlingo.servlet.SamlServlet.validateResponse(SamlServlet.java:315)
        ...........
        ...........

        Caused by: org.apache.xml.security.signature.XMLSignatureException: Signature length not correct: got 256 but was expecting 128
        Original Exception was java.security.SignatureException: Signature length not correct: got 256 but was expecting 128
 at org.apache.xml.security.algorithms.implementations.SignatureBaseRSA.engineVerify(SignatureBaseRSA.java:93)
 at org.apache.xml.security.algorithms.SignatureAlgorithm.verify(SignatureAlgorithm.java:301)
 at org.apache.xml.security.signature.XMLSignature.checkSignatureValue(XMLSignature.java:723)
 at org.opensaml.xml.signature.SignatureValidator.validate(SignatureValidator.java:69)

      
This exception reminded me of JVM jar file changes that I had made during the development. By default Java can handle only upto AES128. In order to handle AES256, I had to replace,
  1. jdk/jre/lib/security/local_policy.jar
  2. jdk/jre/lib/security/US_export_policy.jar
From the site http://www.oracle.com/technetwork/java/javase/downloads/jce8-download-2133166.html