github: server certificate verification failed

I just created a github account and a repository therein, but when trying to create a local working copy using the recommende url via

git clone https://github.com/<user>/<project>.git

I get an error like

fatal: unable to access 'https://github.com/<user>/<project>.git': server certificate verification failed. CAfile: /home/<user>/.ssl/trusted.pem CRLfile: none

I'm on Debian Jessie, and I would have expected both Debian and GitHub to provide / rely on a selection of commonly accepted CAs, but apparently my system doesn't trust GibHub's certificate.

Any simple way to fix this (without the frequently recommended "GIT_SSL_NO_VERIFY=true" hack and similar work-arounds)?

EDIT:

Additional information:

The ca-certificate package is installed.
Installing cacert.org's certificates as suggested by @VonC didn't change anything.
My personal ~/.ssl/trusted.pem file does contain a couple of entries, but to be honest, I don't remember where the added certificates came from...

When removing ~/.ssl/trusted.pem, the git error message changes to

 fatal: unable to access 'https://github.com/tcrass/scans2jpg.git/': Problem with the SSL CA cert (path? access rights?)

Solution

2016: Make sure first that you have certificates installed on your Debian in /etc/ssl/certs.

If not, reinstall them:

sudo apt-get install --reinstall ca-certificates

Since that package does not include root certificates, add:

sudo mkdir /usr/local/share/ca-certificates/cacert.org
sudo wget -P /usr/local/share/ca-certificates/cacert.org http://www.cacert.org/certs/root.crt http://www.cacert.org/certs/class3.crt
sudo update-ca-certificates

Make sure your git does reference those CA:

git config --global http.sslCAinfo /etc/ssl/certs/ca-certificates.crt

Jason C mentions another potential cause (in the comments):

It was the clock. The NTP server was down, the system clock wasn't set properly, I didn't notice or think to check initially, and the incorrect time was causing verification to fail.

Certificates are time-sensitive.

dopamane confirms in the comments:

This was the issue for me on WSL.
Ran sudo hwclock -s, and I could successfully clone the submodule.

2022: Auspex adds in the comments:

ca-certificates does indeed contain root certificates.
It doesn't contain the CAcert root certificates.

This might have been a good answer 6 1/2 years ago, but those certificates were suspect way back then and haven't improved.
There's a reason they're not in the ca-certificates package.

These days we have LetsEncrypt, so everyone has certificates with reliable auditing and nobody needs to rely on CAcert.