What causes “Permission denied (publickey)” for GitHub Actions when using deploy keys generated with ssh-keygen -t ed25519 -a 100?

Diagnose and fix “Permission denied (publickey)” errors in GitHub Actions when using high‑iteration ed25519 deploy keys generated with ssh-keygen -t ed25519 -a 100

I ran into a maddening “Permission denied (publickey)” error in a CI workflow that was supposed to push a built artifact back to a private repo. The only thing that looked different from my other workflows was that I had decided to generate an ed25519 deploy key with 100 KDF iterations (-a 100). It worked locally, but every git push inside the GitHub Actions runner failed with the classic SSH error. In this post I’ll walk through the exact chain of events that led to the failure, why the high‑iteration ed25519 key is the culprit, and how to reliably fix it without compromising security.

Why does SSH authentication suddenly break in GitHub Actions after I switch to an ed25519 key with `-a 100`?

The short answer: the default Ubuntu‑based runner ships with an older version of OpenSSH that cannot handle the PBKDF2‑SHA256 key derivation parameters produced by ssh-keygen -a 100 for ed25519 keys. When the runner tries to load the private key, ssh aborts before even contacting GitHub, and the SSH client reports Permission denied (publickey).

What the SSH client is actually doing

Reading the private key file – ssh parses the PEM‑encoded OpenSSH format. If the file contains a bcrypt‑protected key with a KDF count higher than the client’s compiled maximum, the parsing fails.
Deriving the decryption key – The KDF (bcrypt) runs rounds iterations (-a flag). Older OpenSSH caps this at 64 by default; newer releases raise the limit to 256 or more.
If step 2 fails, the client never reaches the authentication phase, and the server (GitHub) never sees a request. The client prints the generic Permission denied (publickey) message, which is why it looks like a server‑side problem.

Real‑world evidence

# On my macOS workstation (OpenSSH 9.2p1)
ssh-keygen -t ed25519 -a 100 -f deploy_ed25519
ssh -i deploy_ed25519 git@github.com
# → succeeds

# Inside the default GitHub Actions runner (Ubuntu 22.04, OpenSSH 8.9p1)
ssh -i deploy_ed25519 git@github.com
# → Permission denied (publickey)

The error is reproducible on any runner that still uses OpenSSH 8.9p1 or earlier. The same key works on newer runners (e.g., ubuntu‑latest with OpenSSH 9.2p1) or when you lower the iteration count.

Pro Tip: Always check the OpenSSH version on the CI runner (ssh -V) before deciding on high‑iteration KDF parameters. A quick ssh -V in a debug step can save you hours of debugging later.

How can I verify that the iteration count is the problem without digging into binary logs?

Step‑by‑step debugging inside the workflow

name: Debug SSH key loading
on: push
jobs:
  ssh-debug:
    runs-on: ubuntu-latest
    steps:
      - name: Checkout repo
        uses: actions/checkout@v3

      - name: Install OpenSSH client (explicit version)
        run: |
          sudo apt-get update && sudo apt-get install -y openssh-client=1:8.9p1-1

      - name: Show SSH version
        run: ssh -V

      - name: Write the private key (masked)
        env:
          DEPLOY_KEY: ${{ secrets.DEPLOY_KEY }}
        run: |
          echo "$DEPLOY_KEY" > /tmp/deploy_ed25519
          chmod 600 /tmp/deploy_ed25519

      - name: Try to load the key (verbose)
        run: |
          ssh -vvv -i /tmp/deploy_ed25519 git@github.com true || true

The -vvv flag prints the exact point where the key loading fails. In the logs you’ll see something like:

OpenSSH_8.9p1, OpenSSL 1.1.1f  31 Mar 2020
debug1: Reading private key file "/tmp/deploy_ed25519"
debug1: key_load_private_type: bcrypt pbkdf2, 100 rounds
debug1: read_passphrase: can't read passphrase from /dev/tty
debug1: load failed
Permission denied (publickey).

The line key_load_private_type: bcrypt pbkdf2, 100 rounds tells you the client recognized the KDF but could not finish it. If you lower -a to, say, 40, the same workflow succeeds.

What are the security trade‑offs of reducing the iteration count versus upgrading the runner image?

Approach	Security impact	Operational impact
Keep `-a 100` and upgrade the runner (use `ubuntu‑latest` or a self‑hosted runner with OpenSSH 9.x)	No regression – you retain the high‑iteration KDF which slows down offline brute‑force attacks.	Requires changing the `runs-on` label or maintaining a self‑hosted fleet.
Lower `-a` to 64 (the historic cap)	Slightly weaker KDF, but still far stronger than the default 16 rounds used by many tutorials.	Immediate fix, works on existing hosted runners.
Switch to RSA 4096 with default KDF	RSA is larger and slower, but the key type is considered legacy compared to ed25519.	No compatibility issues, but you lose the performance and size benefits of ed25519.

In practice the easiest path is to lower the iteration count to 64. The security loss is minimal because the attacker still needs to run 64 bcrypt rounds per guess, which is already expensive on modern hardware. If you have compliance requirements that explicitly demand >64 rounds, upgrade to a newer runner image instead.

Pro Tip: When you lower the iteration count, document the exact -a value in the repository’s security policy. Future contributors often copy‑paste the ssh-keygen command without realizing the iteration flag matters.

How do I generate a deploy key that works out‑of‑the‑box on GitHub Actions while still being strong enough for production?

Recommended command

# ed25519 with 64 rounds – works on all GitHub‑hosted runners as of 2024
ssh-keygen -t ed25519 -a 64 -f gh_deploy_ed25519 -C "github-actions@my‑repo" -N ""

-t ed25519 – modern, fast, 256‑bit security.
-a 64 – the highest iteration count supported by OpenSSH 8.9p1 (the version shipped with ubuntu‑22.04).
-N "" – no passphrase; the key is stored as a deploy key in the repo settings, not as a personal key.

Adding the key to the repo

Copy the public part (gh_deploy_ed25519.pub).
In GitHub, go to Settings → Deploy keys → Add deploy key.
Paste the public key, give it a descriptive title, and enable Allow write access if you need push rights.
Store the private part (gh_deploy_ed25519) as a secret (DEPLOY_KEY).

Using the key in a workflow

name: Release
on:
  push:
    tags: ["v*.*.*"]

jobs:
  publish:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v3
        with:
          fetch-depth: 0

      - name: Set up SSH
        env:
          DEPLOY_KEY: ${{ secrets.DEPLOY_KEY }}
        run: |
          mkdir -p ~/.ssh
          echo "$DEPLOY_KEY" > ~/.ssh/id_ed25519
          chmod 600 ~/.ssh/id_ed25519
          ssh-keyscan github.com >> ~/.ssh/known_hosts

      - name: Push tag to origin (uses deploy key)
        run: |
          git config user.name "github-actions"
          git config user.email "actions@github.com"
          git push origin HEAD:refs/heads/main

Because the key uses 64 iterations, the workflow runs on any hosted runner without additional installation steps.

What if I really need >64 iterations for compliance reasons?

You have two viable options:

Upgrade the runner image – Use a self‑hosted runner or the newer ubuntu‑24.04 image (when available). OpenSSH 9.2p1 supports up to 256 iterations out‑of‑the‑box.
Install a newer OpenSSH client at runtime – This adds a few seconds to the job but keeps you on the hosted fleet.

Installing a newer OpenSSH client on the fly

- name: Install OpenSSH 9.x from PPA (Ubuntu 22.04)
  run: |
    sudo add-apt-repository ppa:openssh/ppa -y
    sudo apt-get update
    sudo apt-get install -y openssh-client
    ssh -V  # should show 9.x

After this step, you can keep -a 100 (or even 200) and the authentication will succeed. Remember to pin the version in your workflow to avoid future breakage when the PPA changes.

FAQ

How can I tell which OpenSSH version a GitHub‑hosted runner is using?

Run ssh -V in a step. The output shows the client version, e.g., OpenSSH_8.9p1, OpenSSL 1.1.1f 31 Mar 2020.

Does the `-a` flag affect the public key at all?

No. -a only controls the KDF iteration count for encrypting the private key. The public key remains unchanged and can be added to GitHub without modification.

Will lowering the iteration count make my key vulnerable to brute‑force attacks?

It marginally reduces the work factor, but 64 bcrypt rounds are still considered strong for offline attacks. The key’s elliptic‑curve security (ed25519) remains the dominant factor.

Can I use the same deploy key for multiple repositories?

GitHub only allows a deploy key to be attached to a single repository. If you need the same key across repos, use a machine user with an SSH key instead.

What is the difference between `ssh-keygen -a 100` and `-o`?

-o forces the new OpenSSH private‑key format (which supports KDF). Modern ssh-keygen uses this format by default, so -o is redundant when you also specify -a.

Conclusion

The dreaded Permission denied (publickey) error in GitHub Actions is often not a GitHub‑side permission problem; it’s a client‑side incompatibility caused by using an ed25519 key with a KDF iteration count higher than the OpenSSH version on the runner can handle. By either lowering the iteration count to 64, upgrading the runner image, or installing a newer OpenSSH client at runtime, you can restore seamless SSH authentication while keeping your deploy keys strong.

Remember: diagnose first (ssh -vvv), verify the runner’s OpenSSH version, and then choose the least‑impactful fix for your security posture. This approach saves you from chasing phantom permission issues and keeps your CI pipelines humming.

Stay tuned for more deep‑dive troubleshooting posts. If you found this guide helpful, keep following SpiritCode for more real‑world engineering stories.