How can I reinstall OS X without a valid App Store connection?

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).


Solution 1:

use Cmd + Option + R to go into internet recovery then follow these steps https://support.apple.com/en-nz/HT201314

Solution 2:

I've solved the problem!

Like I said, for some reason, I couldn't get the recovery mode to work (Cmd + R). Nor could I connect to the app store to (re)download the OS.

I did, however, have another Mac. SO, I used the other system to download El Capitan, install it to a flash drive, which I used to wipe the "problem" system and reinstall the OS.

I followed these instructions: https://support.apple.com/en-us/HT201372

Two important steps:

  1. My first attempt failed because my flash drive wasn't partitioned with the "GUID" partition table option. Re-partitioning with this option enabled fixed the problem.
  2. In order to completely eradicate the malware, I formatted the internal drive before installing the OS (to ensure that a completely fresh install was performed instead of merely an upgrade).

Everything is working great! Hopefully something here helps someone else out there. Thanks everyone for your input!