Vagrant is stuck: "Authentication failure. Retrying..."

Problem

When running "vagrant up" to bring up a Vagrant Virtualbox, it can't authenticate.  It's retries forever and eventually gives up:

Bringing machine 'default' up with 'virtualbox' provider...
==> default: Clearing any previously set forwarded ports...
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
    default: Adapter 2: hostonly
==> default: Forwarding ports...
    default: 8000 (guest) => 8000 (host) (adapter 1)
    default: 8001 (guest) => 8001 (host) (adapter 1)
    default: 8002 (guest) => 8002 (host) (adapter 1)
    default: 8003 (guest) => 8003 (host) (adapter 1)
    default: 8031 (guest) => 8031 (host) (adapter 1)
    default: 8120 (guest) => 8120 (host) (adapter 1)
    default: 8765 (guest) => 8765 (host) (adapter 1)
    default: 9200 (guest) => 9200 (host) (adapter 1)
    default: 18080 (guest) => 18080 (host) (adapter 1)
    default: 8100 (guest) => 8100 (host) (adapter 1)
    default: 8110 (guest) => 8110 (host) (adapter 1)
    default: 9876 (guest) => 9876 (host) (adapter 1)
    default: 50070 (guest) => 50070 (host) (adapter 1)
    default: 8088 (guest) => 8088 (host) (adapter 1)
    default: 22 (guest) => 2222 (host) (adapter 1)
==> default: Running 'pre-boot' VM customizations...
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
    default: SSH address: 127.0.0.1:2222
    default: SSH username: vagrant
    default: SSH auth method: private key
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
Timed out while waiting for the machine to boot. This means that
Vagrant was unable to communicate with the guest machine within
the configured ("config.vm.boot_timeout" value) time period.

If you look above, you should be able to see the error(s) that
Vagrant had when attempting to connect to the machine. These errors
are usually good hints as to what may be wrong.

If you're using a custom box, make sure that networking is properly
working and you're able to connect to the machine. It is a common
problem that networking isn't setup properly in these boxes.
Verify that authentication configurations are also setup properly,
as well.

If the box appears to be booting properly, you may want to increase
the timeout ("config.vm.boot_timeout") value.

Solution

You can unstick the vagrant machine, but it involves some careful copying and pasting.

Find the IdentityFile vagrant is using:

$ vagrant ssh-config
Host default
  HostName 127.0.0.1
  User vagrant
  Port 2222
  UserKnownHostsFile /dev/null
  StrictHostKeyChecking no
  PasswordAuthentication no
  IdentityFile /Users/ned/.vagrant.d/insecure_private_key
  IdentitiesOnly yes
  LogLevel FATAL
$

Look in the IdentityFile to see the public key. This will be a long line (380 characters or so):

$ ssh-keygen -y -f /Users/ned/.vagrant.d/insecure_private_key
ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAA...rucXzcWyLbIbEgE98OHlnVYCzRdK8jlqm8tehUc9c9WhQ==
$

Log in to the vagrant machine with the password "vagrant":

$ ssh -p 2222 -o UserKnownHostsFile=/dev/null vagrant@127.0.0.1
The authenticity of host '[127.0.0.1]:2222 ([127.0.0.1]:2222)' can't be established.
RSA key fingerprint is dc:48:73:c3:18:e4:9d:34:a2:7d:4b:20:6a:e7:3d:3e.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '[127.0.0.1]:2222' (RSA) to the list of known hosts.
vagrant@127.0.0.1's password: vagrant
Welcome to Ubuntu 16.04.1 LTS (GNU/Linux 4.4.0-31-generic x86_64)
...
Last login: Sun Feb 19 14:23:24 2017 from 10.0.2.2
$

Add the public key to the authorized_keys file. You need to copy the entire ssh-rsa line from the ssh-keygen command above, and paste it here, then type Control-D to end the command:

vagrant@vagrant:~$ cat >> /home/vagrant/.ssh/authorized_keys
ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAA...rucXzcWyLbIbEgE98OHlnVYCzRdK8jlqm8tehUc9c9WhQ==
<Ctrl-D>
vagrant@vagrant:~$

Log out of the vagrant machine and halt it:

vagrant@vagrant:~$ exit
logout
Connection to 127.0.0.1 closed.
$ vagrant halt
==> default: Attempting graceful shutdown of VM...
    default:
    default: Vagrant insecure key detected. Vagrant will automatically replace
    default: this with a newly generated keypair for better security.
    default:
    default: Inserting generated public key within guest...
    default: Removing insecure key from the guest if it's present...
    default: Key inserted! Disconnecting and reconnecting using new SSH key...
==> default: [vagrant-hostsupdater] Removing hosts
$

Bring up the vagrant machine again:

$ vagrant up
Bringing machine 'default' up with 'virtualbox' provider...
==> default: Clearing any previously set forwarded ports...
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
    default: Adapter 2: hostonly
==> default: Forwarding ports...
    default: 8000 (guest) => 8000 (host) (adapter 1)
    default: 8001 (guest) => 8001 (host) (adapter 1)
    default: 8002 (guest) => 8002 (host) (adapter 1)
    default: 8003 (guest) => 8003 (host) (adapter 1)
    default: 8031 (guest) => 8031 (host) (adapter 1)
    default: 8120 (guest) => 8120 (host) (adapter 1)
    default: 8765 (guest) => 8765 (host) (adapter 1)
    default: 9200 (guest) => 9200 (host) (adapter 1)
    default: 18080 (guest) => 18080 (host) (adapter 1)
    default: 8100 (guest) => 8100 (host) (adapter 1)
    default: 8110 (guest) => 8110 (host) (adapter 1)
    default: 9876 (guest) => 9876 (host) (adapter 1)
    default: 50070 (guest) => 50070 (host) (adapter 1)
    default: 8088 (guest) => 8088 (host) (adapter 1)
    default: 22 (guest) => 2222 (host) (adapter 1)
==> default: Running 'pre-boot' VM customizations...
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
    default: SSH address: 127.0.0.1:2222
    default: SSH username: vagrant
    default: SSH auth method: private key
==> default: Machine booted and ready!
[default] GuestAdditions 5.1.10 running --- OK.
==> default: Checking for guest additions in VM...
==> default: [vagrant-hostsupdater] Checking for host entries
==> default: Configuring and enabling network interfaces...
==> default: Exporting NFS shared folders...
==> default: Preparing to edit /etc/exports. Administrator privileges will be required...
==> default: Mounting NFS shared folders...
==> default: Machine already provisioned. Run `vagrant provision` or use the `--provision`
==> default: flag to force provisioning. Provisioners marked to run always will still run.
$ vagrant ssh
Welcome to Ubuntu 16.04.1 LTS (GNU/Linux 4.4.0-31-generic x86_64)
...
Last login: Mon Feb 20 14:05:39 2017 from 10.0.2.2
vagrant@vagrant:~$

Now your vagrant machine is usable again.