There's a bug report on Oracle's VirtualBox ticket system that seems to be caused by KB3004394. For some, uninstalling the update resolves the VirtualBox failures.
Had a look at the VirtualBox breakage.
The problem seems to be that the update does not install any catalog file C:\Windows\System32\CatRoot and it's therefore impossible to verify the new crypto32.dll file that the it installs. (Compare "sigcheck -i C:\Windows\System32\crypto32.dll" output before and after installing the update. Sigcheck says it's signed before and unsigned after.)
The Windows 8.1 version of the update works, i.e. installs C:\Windows\system32\CatRoot{F750E6C3-38EE-11D1-85E5-00C04FC295EE}\Package_1_for_KB3004394~31bf3856ad364e35~amd64~~6.3.1.0.cat that we (and sigcheck.exe from microsoft/sysinternals) can successfully validate the DLL. (I've only tried 64-bit Windows 8.1 and Windows 7, so I cannot tell exactly which updates are broken.)
The only way to make VirtualBox work again is reverting/removing the update, unless Microsoft fixes the missing .cat file issue. I sincerely hope that Microsoft will update the update with a working cat file eventually...
-bird
PS. Would be really swell if files like crypto32.dll and wintrust.dll had embedded signatures instead of only external ones. It would not only do away with these kind of issues but also make it a lot easier to verify that the files haven't been tampered with.
Files containing "3004394" in c:\windows\system32\catroot on my Windows 7 x64 system with KB3004394 installed an no issues so far:
Mode LastWriteTime Length Name
---- ------------- ------ ----
-a--s 10/31/2014 2:45 PM 23488 Package_111_for_KB3004394~31bf3856ad364e35~amd64~~6.1.1.0.cat
-a--s 10/31/2014 2:45 PM 27136 Package_112_for_KB3004394~31bf3856ad364e35~amd64~~6.1.1.0.cat
-a--s 10/31/2014 2:45 PM 7475 Package_113_for_KB3004394~31bf3856ad364e35~amd64~~6.1.1.0.cat
-a--s 10/31/2014 2:45 PM 7475 Package_114_for_KB3004394~31bf3856ad364e35~amd64~~6.1.1.0.cat
-a--s 10/31/2014 2:45 PM 9231 Package_39_for_KB3004394~31bf3856ad364e35~amd64~~6.1.1.0.cat
-a--s 10/31/2014 2:45 PM 11567 Package_40_for_KB3004394~31bf3856ad364e35~amd64~~6.1.1.0.cat
-a--s 10/31/2014 2:45 PM 12727 Package_75_for_KB3004394~31bf3856ad364e35~amd64~~6.1.1.0.cat
-a--s 10/31/2014 2:45 PM 9231 Package_76_for_KB3004394~31bf3856ad364e35~amd64~~6.1.1.0.cat
-a--s 10/31/2014 2:45 PM 7475 Package_for_KB3004394_SP1~31bf3856ad364e35~amd64~~6.1.1.0.cat
-a--s 10/31/2014 2:45 PM 7475 Package_for_KB3004394~31bf3856ad364e35~amd64~~6.1.1.0.cat
Output of sigcheck:
C:\SysinternalsSuite>sigcheck.exe c:\Windows\System32\crypt32.dll
Sigcheck v1.71 - File version and signature viewer
Copyright (C) 2004-2010 Mark Russinovich
Sysinternals - www.sysinternals.com
c:\windows\system32\crypt32.dll:
Verified: Signed
Signing date: 1:45 PM 10/31/2014
Publisher: Microsoft Corporation
Description: Crypto API32
Product: Microsoft« Windows« Operating System
Version: 6.1.7601.18526
File version: 6.1.7601.18526 (win7sp1_gdr.140706-1506)
I'm also not seeing any issues with Windows 7 32-bit or Windows Server 2008 R2.
If there are any things that I can assess in my environment to look for differences, let me know and I'll post a reply.