diff --git a/dlls/crypt32/message.c b/dlls/crypt32/message.c
index 5e82708..fe4d4ec 100644
--- a/dlls/crypt32/message.c
+++ b/dlls/crypt32/message.c
@@ -218,9 +218,53 @@
  DWORD rgcbToBeHashed[], BYTE *pbHashedBlob, DWORD *pcbHashedBlob,
  BYTE *pbComputedHash, DWORD *pcbComputedHash)
 {
-    FIXME("(%p, %d, %d, %p, %p, %p, %p, %p, %p): stub\n", pHashPara,
-     fDetachedHash, cToBeHashed, rgpbToBeHashed, rgcbToBeHashed, pbHashedBlob,
-     pcbHashedBlob, pbComputedHash, pcbComputedHash);
-    SetLastError(ERROR_CALL_NOT_IMPLEMENTED);
-    return FALSE;
+    DWORD i, flags;
+    BOOL ret = FALSE;
+    HCRYPTMSG msg;
+    CMSG_HASHED_ENCODE_INFO info;
+
+    TRACE("(%p, %d, %d, %p, %p, %p, %p, %p, %p)\n", pHashPara, fDetachedHash,
+     cToBeHashed, rgpbToBeHashed, rgcbToBeHashed, pbHashedBlob, pcbHashedBlob,
+     pbComputedHash, pcbComputedHash);
+
+    if (pHashPara->cbSize != sizeof(CRYPT_HASH_MESSAGE_PARA))
+    {
+        SetLastError(E_INVALIDARG);
+        return FALSE;
+    }
+    /* Native seems to ignore any encoding type other than the expected
+     * PKCS_7_ASN_ENCODING
+     */
+    if (GET_CMSG_ENCODING_TYPE(pHashPara->dwMsgEncodingType) !=
+     PKCS_7_ASN_ENCODING)
+        return TRUE;
+    /* Native also seems to do nothing if the output parameter isn't given */
+    if (!pcbHashedBlob)
+        return TRUE;
+
+    flags = fDetachedHash ? CMSG_DETACHED_FLAG : 0;
+    memset(&info, 0, sizeof(info));
+    info.cbSize = sizeof(info);
+    info.hCryptProv = pHashPara->hCryptProv;
+    memcpy(&info.HashAlgorithm, &pHashPara->HashAlgorithm,
+     sizeof(info.HashAlgorithm));
+    info.pvHashAuxInfo = pHashPara->pvHashAuxInfo;
+    msg = CryptMsgOpenToEncode(pHashPara->dwMsgEncodingType, flags, CMSG_HASHED,
+     &info, NULL, NULL);
+    if (msg)
+    {
+        for (i = 0, ret = TRUE; ret && i < cToBeHashed; i++)
+            ret = CryptMsgUpdate(msg, rgpbToBeHashed[i], rgcbToBeHashed[i],
+             i == cToBeHashed - 1 ? TRUE : FALSE);
+        if (ret)
+        {
+            ret = CryptMsgGetParam(msg, CMSG_CONTENT_PARAM, 0, pbHashedBlob,
+             pcbHashedBlob);
+            if (ret && pcbComputedHash)
+                ret = CryptMsgGetParam(msg, CMSG_COMPUTED_HASH_PARAM, 0,
+                 pbComputedHash, pcbComputedHash);
+        }
+        CryptMsgClose(msg);
+    }
+    return ret;
 }
diff --git a/dlls/crypt32/tests/message.c b/dlls/crypt32/tests/message.c
index fc2a842..11b8c1c 100644
--- a/dlls/crypt32/tests/message.c
+++ b/dlls/crypt32/tests/message.c
@@ -271,27 +271,23 @@
     memset(&para, 0, sizeof(para));
     SetLastError(0xdeadbeef);
     ret = CryptHashMessage(&para, FALSE, 0, NULL, NULL, NULL, NULL, NULL, NULL);
-    todo_wine
     ok(!ret && GetLastError() == E_INVALIDARG,
      "expected E_INVALIDARG, got 0x%08x\n", GetLastError());
     para.cbSize = sizeof(para);
     /* Not quite sure what "success" means in this case, but it does succeed */
     SetLastError(0xdeadbeef);
     ret = CryptHashMessage(&para, FALSE, 0, NULL, NULL, NULL, NULL, NULL, NULL);
-    todo_wine
     ok(ret, "CryptHashMessage failed: 0x%08x\n", GetLastError());
     /* With a bogus encoding type it "succeeds" */
     para.dwMsgEncodingType = 0xdeadbeef;
     SetLastError(0xdeadbeef);
     ret = CryptHashMessage(&para, FALSE, 0, NULL, NULL, NULL, NULL, NULL, NULL);
-    todo_wine
     ok(ret, "CryptHashMessage failed: 0x%08x\n", GetLastError());
     /* According to MSDN, the third parameter (cToBeHashed) must be 1 if the
      * second parameter (fDetached) is FALSE, but again it "succeeds."
      */
     SetLastError(0xdeadbeef);
     ret = CryptHashMessage(&para, FALSE, 2, NULL, NULL, NULL, NULL, NULL, NULL);
-    todo_wine
     ok(ret, "CryptHashMessage failed: 0x%08x\n", GetLastError());
     /* Even passing parameters to hash results in "success." */
     SetLastError(0xdeadbeef);
@@ -301,13 +297,11 @@
     para.dwMsgEncodingType = PKCS_7_ASN_ENCODING;
     SetLastError(0xdeadbeef);
     ret = CryptHashMessage(&para, FALSE, 2, NULL, NULL, NULL, NULL, NULL, NULL);
-    todo_wine
     ok(ret, "CryptHashMessage failed: 0x%08x\n", GetLastError());
     /* And with valid data to hash */
     SetLastError(0xdeadbeef);
     ret = CryptHashMessage(&para, FALSE, 2, toHash, hashSize, NULL, NULL, NULL,
      NULL);
-    todo_wine
     ok(ret, "CryptHashMessage failed: 0x%08x\n", GetLastError());
     /* But requesting the size of the hashed blob and indicating there's data
      * to hash results in a crash
@@ -323,7 +317,6 @@
     SetLastError(0xdeadbeef);
     ret = CryptHashMessage(&para, FALSE, 2, toHash, hashSize, NULL,
      &hashedBlobSize, NULL, NULL);
-    todo_wine
     ok(!ret && GetLastError() == CRYPT_E_UNKNOWN_ALGO,
      "expected CRYPT_E_UNKNOWN_ALGO, got 0x%08x (%d)\n", GetLastError(),
      GetLastError());
@@ -354,7 +347,6 @@
     SetLastError(0xdeadbeef);
     ret = CryptHashMessage(&para, TRUE, 2, toHash, hashSize, NULL,
      &hashedBlobSize, NULL, NULL);
-    todo_wine
     ok(ret, "CryptHashMessage failed: 0x%08x\n", GetLastError());
     if (ret)
     {
@@ -373,7 +365,6 @@
     SetLastError(0xdeadbeef);
     ret = CryptHashMessage(&para, FALSE, 1, toHash, hashSize, NULL,
      &hashedBlobSize, NULL, NULL);
-    todo_wine
     ok(ret, "CryptHashMessage failed: 0x%08x\n", GetLastError());
     if (ret)
     {
@@ -393,9 +384,7 @@
     computedHashSize = 0xdeadbeef;
     ret = CryptHashMessage(&para, TRUE, 2, toHash, hashSize, NULL,
      &hashedBlobSize, NULL, &computedHashSize);
-    todo_wine
     ok(ret, "CryptHashMessage failed: 0x%08x\n", GetLastError());
-    todo_wine
     ok(computedHashSize == 16, "expected hash size of 16, got %d\n",
      computedHashSize);
     if (ret)