I am working on a multiplayer game. I intended for all data to be exchanged over HTTPS, but it is way too slow. High latency networks take over a second for SSL handshake. While the game is turn-based and does not require blazing-fast data transfer, 1000-2000 ms ping is still unacceptable.

What protocols/approaches can I use to transfer data securely, with as low latency as possible?



Edit: Just to respond to your enquiries about the payload, here is what the result of a unit attacking an enemy building (obviously I'm not sending a string of ones and zeros, this is just a binary representation):

00000000 10010011 01010001 00100011 01011100 01010001 01010000


Message breakdown:

00000000  client's request executed with status "OK", other values correspond to specific error messages.

10        Object is owned by Player 2
010       Object is a building
0110      Object is located at x=6  (always 0<=x<=14)
101       Object is located at y=5  (always 0<=y<=6), owner and location is sufficient to describe any object uniquely
0001      1 byte-worth of modified attributes follows
0010 0011 Object's health is now 3

01        Object is owned by Player 1
011       Object is a unit
1000      Object is located at x=8
101       Object is located at y=5
0001      1 byte-worth of modified attributes follows
0101 0000 This object can no longer move/attack this turn


I don't think that I can get any more data density without making it expensive on the CPU.

HTTPS is HTTP over TLS. 

If you implement a game, using HTTP is usually not a good idea. The HTTP protocol is designed for requesting documents, not for real-time games. A better idea would be to develop your own protocol directly based on TCP or UDP (UDP is faster while TCP is easier to use, but that's a topic for game development stackexchange) and tunnel it through TLS. 

The time-consuming key exchange process only needs to happen once when establishing the connection. When you keep the same connection open during the game, the only latency overhead is caused by encryption and decryption. TLS supports multiple cipher suites (sets of cryptographic algorithms which are used). The choice of cipher suite can be used to find a compromise between performance and security.
 
