We assumed it was UDP because of the hint. Every time we attempted to use netcat UDP, however, it would not respond. We just thought it was down, until eventually it connected once I decided try to connect using python instead. I'm assuming that netcat didn't work because it was also sending the newline character with the sent password, so it would not authorize.
When you first connect, you are are told which directions you can go in the maze, which are other ports on the box. The passwords for those directions are also given.
When you connect to any other port, however, you are not given the port number. So, I guessed that the distance between the starting ports was the same for that entire specified direction and that it was the reverse distance for the opposite directions.
I wrote a script in python to reach each found port. The script can be found here.
The script to a awhile to run (~1 hour), since the maze was almost 256 by 256. The port that contained the key was port 65534. When I first say my script printed the response, I was confused because I didn't remember adding any printing. Then I realized it was the key...
The key was RUCTF_77pd9u784g059t0z18hjtn5d