Verify ssh-agent signature in Python

Question

Python's Paramiko library lets you request that the ssh-agent sign a bit of data for you. That's great! But how do I verify that signature when I only have access to the public key, not the agent?

from base64 import b64encode
from paramiko.agent import Agent
agent = Agent()
key = agent.get_keys()[0]
sig = key.sign_ssh_data(None, "Hello World!")
print b64encode(sig)
# AAAAB3NzaC1yc2EAAAEAqZFIGxm1Zz3ALeTa2YiiYX2rbr9Cnb3gj4tJj1Fl19sNsRy6UbbauYnmahYWl6mWqhOHJaj0sAtVqPab8U1RiyeZyQB+Bwp0MUal4ZGCmrJxJ7ykVE+BeJnpOxXyutHHV376TXC5l+tx0PjFsylL1vVbBm6J927Nyc/cq1uk0q2QpcRexg0iJ51i1WGyISVvu1PC+g0LmW1dGh2mXTo/fpt+Cu45/hjWpMlcBUg8O60+nkj2jYxxGVh/z7U6zTYrDSJU4hTEveuKG5I38gsaMRBw/YkSIaMtkGNJX36Ybc+/EVolL4Z/NOOCV+kd7WPHjSTf1hVZ02ulTTrnMN4HfA==

I've tried every solution I can come up with. OpenSSL can't even look at the key I'm using (generated via ssh-keygen):

$ ssh-keygen -f ~/.ssh/testssh.pub -e -m pem > test.pub
$ cat test.pub
-----BEGIN RSA PUBLIC KEY-----
MIIBCgKCAQEA7Zs6ZyrHk3RpDKv7Kzd7NCU2Qk5k5ajVJvntRPiEukWOIe4CkcBo
B76HSDyPvEDI50DUyebj2Qj77NDX/lh5AhDrVTEmX/Lfzx2iCwgpWwQcu8dgAaN5
qhsCMYOc77d2YykcnbDUhgxus/KiieLnruKmviVdSHoLBs6ygnVEa+8nx+DhJwSB
B3+6gClM89QnKrPYOonj9z4zi+UeWPX9TVwJVOAADnXEC6LCmDCgHDb+FrCaiNT9
d4yam3iZJ2RMQ+ajBj6JWvoig2LdUBI7eSgmrREjjEEskBCNRkD4YmjeT8mfZg9d
FhbGz0CQjnF31jiohIvhABTwcUQnDdrPEQIDAQAB
-----END RSA PUBLIC KEY-----
$ openssl rsa -inform PEM -in test.pub -pubin -text
unable to load Public Key
140735078689212:error:0906D06C:PEM routines:PEM_read_bio:no start line:pem_lib.c:696:Expecting: PUBLIC KEY

PyCrypto comes up with a completely different signature for the same data:

from base64 import b64encode
from Crypto.Hash import SHA
from Crypto.PublicKey import RSA
from Crypto.Signature import PKCS1_v1_5

# PyCrypto
key = RSA.importKey(open('.ssh/testssh').read())
signer = PKCS1_v1_5.new(key)
h = SHA.new()
h.update("Hello World!")
sig = signer.sign(h)
print "CRYPTO: %s" % b64encode(sig)
# CRYPTO: qZFIGxm1Zz3ALeTa2YiiYX2rbr9Cnb3gj4tJj1Fl19sNsRy6UbbauYnmahYWl6mWqhOHJaj0sAtVqPab8U1RiyeZyQB+Bwp0MUal4ZGCmrJxJ7ykVE+BeJnpOxXyutHHV376TXC5l+tx0PjFsylL1vVbBm6J927Nyc/cq1uk0q2QpcRexg0iJ51i1WGyISVvu1PC+g0LmW1dGh2mXTo/fpt+Cu45/hjWpMlcBUg8O60+nkj2jYxxGVh/z7U6zTYrDSJU4hTEveuKG5I38gsaMRBw/YkSIaMtkGNJX36Ybc+/EVolL4Z/NOOCV+kd7WPHjSTf1hVZ02ulTTrnMN4HfA==

Obviously, I'm not a crytpologist. I've been reading code for the last 12 hours trying to figure out how to verify an ssh-agent signature. Is there something painfully obvious I'm missing? What's the "Right" way to do this?

Update

Following the M2Crypto verify process outlined here, I'm getting this error against the ssh-agent's signature:

Traceback (most recent call last):
  File "test.py", line 36, in <module>
    print key.verify(datasha.digest(), agentsig)
  File "/Users/shbeta/virtualenvs/dev/lib/python2.7/site-packages/M2Crypto-0.21.1-py2.7-macosx-10.7-intel.egg/M2Crypto/RSA.py", line 259, in verify
M2Crypto.RSA.RSAError: wrong signature length

Testing against the Crypto-generated signature, however, succeeds. Is the ssh-agent using a nonstandard signature algorithm?

Update 2: redacted. I misread.

Answer 1

It seems that the general ideas around building an RSA key object from the public SSH key are...not quite accurate. Again, I'm no cryptographer. But this works:

from paramiko import Message
from paramiko.rsakey import RSAKey
from sshkey import load_rsa_pub_key
with open('.ssh/testssh.pub') as fh:
  ketype, b64key, _ = fh.next().strip().split(None, 2)
decoded_key = base64.b64decode(b64key)
pkey = RSAKey(data=decoded_key)
psig = Message(agentsig)
print pkey.verify_ssh_sig(plaintext, psig)
# True
print pkey.verify_ssh_sig("bogus", psig)
# False

I'd love to understand why using the converted PEM format didn't work. Does ssh-keygen dump it incorrectly?