Imagine I have a computer where all the trafic is being sent through the MitM. How would it be possible to have a secure connection through this setup?
In this case it would be OK to design a new protocol just for this. I just want to know if there is a way to do this. If there is a new protocol we need to make it unbruteforceable for the next 10 years.
EDIT: Assume you didn't exchange any keys before you got MitM'd. Absolutely every communication from/to you to/from the server is being MitM'd.