Could you please sign this?

Right, so i started thinking I'm doing too many trips, because the client and server could just sign their packages. But that doesn't actually prove anything. After all, someone could have just connected to a server, received their package and then used it to respond to someone connecting to them. That way they'd be pretending to be the other server. The package would be validly signed but not prove the servers identity. Basically we do still need the random phrase challenges from both sides

This does bring up the whole Man-In-The-Middle problem. I could still simply become a proxy between two peers. Not wanting any central service for registering, I'll probably just go with adding the IP in both the client and server packets. That way we can check that the message originates from the same IP we're talking to.