Reversing a Java digest function, with known public key and source code

Question

A Java application verifies that an XML string that came from a clearnet server (no SSL) has not been tampered, using a message digest. It does so with a public key stored locally, accessed with the variable pk_enc

The application asks an external server for 2 strings: the XML and a hash (both encoded base64):

String xml_enc = // ...
String hashStr_enc = // ...

The application then decodes from base64:

String xml = new String(Base64.decode(xml_enc));
byte[] hashStr = Base64.decode(hashStr_enc);

In xml we now have a readable XML string and in hashStr_dec a bunch of unreadable characters.

It then verifies that the result of these 2 functions are equal:

public String createMD5hashForResponseXMLDocument(String xml) {
    try {
        byte[] e = xml.getBytes();
        MessageDigest algorithm = MessageDigest.getInstance("MD5");
        algorithm.reset();
        algorithm.update(e);
        byte[] messageDigest = algorithm.digest();
        StringBuffer hexString = new StringBuffer();

        for (int i = 0; i < messageDigest.length; ++i) {
            hexString.append(Integer.toString((messageDigest[i] & 255) + 256, 16).substring(1));
        }

        return hexString.toString();
    } catch (Exception e) {
        e.printStackTrace();
        return "";
    }
}

and

public String decryptRSAcipherUsedForSigning(String pk_enc, byte[] hashStr) {
    try {

        X509EncodedKeySpec e = new X509EncodedKeySpec(decodeBASE64(pk_enc));
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        RSAPublicKey RSApublicKey = (RSAPublicKey) keyFactory.generatePublic(e);
        Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1PADDING");
        cipher.init(2, RSApublicKey);
        byte[] MD5hash = cipher.doFinal(hashStr);
        return new String(MD5hash);

    } catch (Exception e) {
        e.printStackTrace();
        return "";
    }
}

Everything works as long as you don't touch the XML, and the result of the 2 functions computes as equal.

---

I would now like to modify the XML and compute the hash correctly (the reverse of what happens above). Given that I have pk_enc it shouldn't be impossible.

How can I do that? Here's what I've tried. For simplicity sake, I used the same XML as the original.

First, I fed the unencoded XML to createMD5hashForResponseXMLDocument:

String xml_md5 = createMD5hashForResponseXMLDocument(my_xml_string);

Then I run this function. It's the same as decryptRSAcipherUsedForSigning but I changed cipher.init(2, RSApublicKey); to cipher.init(1, RSApublicKey);

public byte[] encryptHash(String pk_enc, String xml_m5d) {
        try {
            X509EncodedKeySpec e = new X509EncodedKeySpec(decodeBASE64(pk_enc));
            KeyFactory keyFactory = KeyFactory.getInstance("RSA");
            RSAPublicKey RSApublicKey = (RSAPublicKey) keyFactory.generatePublic(e);
            Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1PADDING");
            cipher.init(1, RSApublicKey);
            byte[] result = cipher.doFinal(xml_m5d.getBytes());
            return result;

        } catch (Exception e) {
            e.printStackTrace();
            return "".getBytes();
        }
    }

This is not working: provided with the same XML I've started with, it does not produce the same result. Furthermore, if I try to to feed it back to decryptRSAcipherUsedForSigning I get this error:

javax.crypto.BadPaddingException: Decryption error
    at sun.security.rsa.RSAPadding.unpadV15(Unknown Source)
    at sun.security.rsa.RSAPadding.unpad(Unknown Source)
    at com.sun.crypto.provider.RSACipher.doFinal(RSACipher.java:356)
    at com.sun.crypto.provider.RSACipher.engineDoFinal(RSACipher.java:389)
    at javax.crypto.Cipher.doFinal(Cipher.java:2164)
    at com.test.test.MainTest.decryptRSAcipherUsedForSigning(MainTest.java:112)
    at com.test.test.MainTest.Execute(MainTest.java:59)
    at com.test.test.test.main(test.java:13)

Please note I'm aware of the difference between String and byte[] and I've been careful to not switch inappropriately between the twos. Although I do not exclude that might be the problem, it should be ok.

Answer 1

This is impossible to do as long as I don't have the corresponding private key of pk_enc.

Decrypting with a public key means verifying: I didn't know that, saw a public key used for decryption and jumped to the wrong conclusion that it was sufficient to encrypt back the data.

It is not.