Very slow assert in VerifyingKey.from_string()

[sigmunau]

This line:
assert ecdsa.point_is_valid(curve.generator, x, y)
takes about 26ms to complete. With my ssh known hosts file has 182 ecdsa keys in, this line alone causes a paramiko client to spend almost five seconds before even connecting to to the server. As the known_hosts file is a in essence a database of trusted keys, I think it should be possible to skip this assert in this case.

[warner]

hm, failure to validate the public point enables some attacks ("small subgroup attack" is the one that comes to mind). For DH key agreement and SRP, it enables a trivial break, rendering the generated key completely predictable. But it might be less severe for us, because we only do public-key signatures, especially because of your point that the pubkeys are generally coming from a trusted source.

Any crypto folks wanna weigh in on this one?

[sigmunau]

I'm not suggesting that the test be removed alltogether, just that there is an option to skip it if we have some reason to trust the key. In my example the public point could be validated before the key is written to the known hosts file, and this test could be skipped when reading back the file.

[warner]

Ah, ok, that sounds fine. I'll add an extra option for VerifyingKey.from_string() to disable that check.