Digging about in the gitolite code reveals this error is thrown when a regex fails to find a valid looking fingerprint after running ssh-keygen -l -f 'path/to/key.pub'. (See man ssh-keygen for details).

To resolve the issue, run that command locally and have it generate a valid fingerprint before you push your configuration changes to the gitolite server. I found my issue was that I had failed to include the 'ssh-rsa ' prefix to the key.

I also saw comments suggesting this issue was related to key size. I saw successful tests using the '-b 1024' and the '-b 2048' switch…