Package updates now fail with certificate errors and I cannot install the fix because installing needs working certificates

A variant worth checking: is it everything failing, or only third-party repositories?

If the distribution's own repositories work and only added ones fail, the trust store is fine and the problem is those repositories' certificates — expired, misconfigured, or signed by an authority that got distrusted. In that case the fix is per-repository and reinstalling CA certificates achieves nothing.

Quick way to tell them apart: try fetching a distribution URL and a third-party one with a plain HTTPS client and compare the errors. Different failure messages mean different problems, and it saves you performing surgery on a healthy trust store.

Before any of that, work out what actually broke, because the answer changes the fix and sometimes there is nothing to reinstall.

The usual causes, in rough order of frequency:

• The system clock is wrong. A certificate that is not yet valid or has expired produces exactly this error. Check the date first — it costs one command and it is the single most common cause, particularly on a virtual machine that has been suspended or on hardware with a dead battery.
• A corporate or VPN client installed an interception certificate and then removed or broke it. You mentioned installing VPN software, which makes this the leading suspect in your case.
• A root certificate genuinely expired. This happens occasionally and breaks old systems that never received the replacement.
• The store was edited or emptied by something well-meaning.

If it is the clock, fixing the clock fixes everything instantly and no download is needed.

The loop is breakable because you only need to bypass verification once, for a single file, from a source you can check another way.

The general shape:

1. Download the CA certificates package manually from the distribution's own archive, using a tool told to skip verification for that one download.
2. Verify it out of band before installing — compare the checksum against the one published by the distribution, fetched from a machine that still works.
3. Install it directly with the low-level package tool, which does not need the network.
4. Refresh the certificate store.
5. Confirm the package manager works again and turn nothing else off.

Step 2 is the one that makes this safe rather than reckless, and it is the one that gets skipped. You are downloading a trust anchor over an unverified channel, so verifying it by another route is not optional.

Whatever you do, resist the suggestion to permanently disable verification in the package manager configuration. It works, it is easy, and it converts a temporary problem into a machine that silently accepts any package from anyone forever.

If you must use an unverified fetch, use it for one file on one command line, not in a config file. The difference between those two is whether somebody finds it in three years.