Git push/pull fails on GitLab in Google Compute Engine

Question

I've installed GitLab on Google Compute Engine using "Click to Deploy" from the project interface. The deployment is successful after a few minutes. I can SSH into the instance, and muck around with it as expected.

I can also log in to GitLab using the web interface, and add SSH keys to my profile. So far, so good. However, when I attempt to push or pull to a new example repository, I receive this message:

Permission denied (publickey,gssapi-keyex,gssapi-with-mic).
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

I've removed my local SSH config so it doesn't interfere. Do I need to setup an SSH tunnel of some sort? What am I missing?

UPDATE: Wiping out my local ~/.ssh folder, and regenerating an SSH key (which I've added to my profile in GitLab) produces the following error:

Received disconnect from {GITLAB_IP_ADDRESS}: 2: Too many authentication failures for git
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

UPDATE 2: It seems GitLab may already have a solution: run sudo gitlab-ctl reconfigure. See here: https://gitlab.com/gitlab-org/omnibus-gitlab/blob/master/README.md#git-ssh-access-stops-working-on-selinux-enabled-systems

Answer 1

You need to create an SSH tunnel to communicate with GitLab.

1. Log into your development server as your user, and create a key.

ssh-keygen -t rsa

Follow the steps, and create a passcode (that you can remember) as you'd need this to pull and push code from/to GitLab.

2. Now that you've created your key, we can copy it;

cat id_rsa.pub

Copy the output of that command (including ssh-rsa), and add it to your GitLab profile. (http://my-gitlab-server.com/profile/keys/new).

3. Ensure you have the correct privilege to the project(s)

Ensure you are at role developer at the very least. (Screengrab of roles: http://i.stack.imgur.com/DSSvl.jpg)

4. Now, copy the project link

Go into your project, and find the SSH link in the top right;

5. Now back to your development server

Navigate to your directory where you'd like to work, and run the following;

$ git init
$ git remote add origin <<project_url>>
$ git fetch

Where <<project_url>> is the link we copied in step 4.

You will be prompted your password (this is your ssh key password, not your server password) and to add the host to your known_hosts file. After that, the project will start to download and you can enjoy development.

I did these steps on a CentOS 6.4 machine with Digital Ocean. But they shouldn't differ from using Google CE.

Edit

Quote from Marty Penner answer as per this comment

Solved it! Thanks to @sxleixer and @Alexander Wenzowski for figuring this out.

Apparently, SELinux was interfering with a non-standard location for the .ssh directory. I needed to run the following commands on the Compute Engine instance:

sudo yum -y install policycoreutils-python # Install the `semanage` tool
sudo semanage fcontext -a -t ssh_home_t "/var/opt/gitlab/.ssh/authorized_keys" # Allow the nonstandard ssh_home_t

See the full thread here:

Google Cloud Engine. Permission denied (publickey,gssapi-keyex,gssapi-with-mic)