I have a Mid 2009 MacBook Pro that was used by a "less than responsible" user. As such, it seems to have become infected with malware that rewrites all SSL certificates. These certificates cannot be validated by OS X which is what alerted me to the fact that there is a problem.
My issue is that I cannot access the App Store to initiate a reinstallation of OS X. Since the MacBook Pro can't validate the App Store SSL certificates, nothing loads.
So, I'm stuck. What steps should I take to reinstall OS X or restore access to the App Store?
Update: Cmd + R on boot doesn't seem to work (perhaps due to the Malware). Also, the OS version is 10.9.5 (Mavericks).