Comment 1 for bug 1585515

Paramiko 2.0 got released 26 days ago with [1]. Nova put a workaround in place to work with paramiko 2.x 21 days ago [2]. After that, we bumped the version in the global requirements to 2.0 [3]. I tested it locally with commit 9d99081 (Newton master) and it works for me. I also didn't find the error message in logstash. I could reproduce this issue when I used stable/Mitaka and upgraded from the pinned version paramiko 1.16 to paramiko 2.0 manually.
All of this makes me believe that your setup could be in a weird state. I'm closing this for now. If you can reproduce it, feel free to reopen.

References:
[1] https://github.com/paramiko/paramiko/commit/258cc64ab36b58c681aa974151288fc7ddc1bb31
[2] https://github.com/openstack/nova/commit/c05b338f163e0bafbe564c6c7c593b819f2f2eac
[3] https://github.com/openstack/requirements/commit/e379813e9ccd41138af969f4c8e57abd062af527