Appropriate AES key length for short term protection

Question

Currently I'm doing some initial research for a fully connected distributed network communication model. The context here is a peer-to-peer multiplayer protocol, using a majority-voting system. More specifically, it's distributed lockstep used in most (all?) RTS games; somewhat similar to: Age of Empires.

Given the nature of the design, I've recognized the following properties\requirements:

• A majority of peers is assumed to be valid at all times. Conversely, a minority of malicious\Byzantine peers should not undermine the 'network' as a whole at any time.
• Message payload has to be encrypted to avoid the trivial interception of plain-text messages.
• Message payload will approx. be in the range 128-512 bytes; in any case it will most certainly not exceed 1024 bytes.
• Message frequency will be at most ~8 per second, depending on commands issued by a user reissuing of dropped packets. So: 8 * (N-1) messages per second for N peers is the upper bound; N <= 6.
• One aspect of the protocol scheme is that when peers are broadcasting their vote for a proposal; another peer who receives said vote (but has not received the proposal corresponding to that vote) will request that proposal from another peer based on latency. Consequently, this is not necessarily the peer that originally issued the proposal.
• Due to the lack of a 'master' node, every node will tally any votes received individually, so:
  • Message authenticity is important: a peer should not be able to tamper with received messages without other peers being able to detect this.
• Session-wide security is only necessary for the duration of a session (see below), which is estimated to be at most a few hours.
• Per-message security is only important for some seconds, due to old messages being invalid after some time-out anyway.

To narrow the scope of the discussion, assume things like key-exchange, generation, voting-protocol etc. are correctly implemented.

After some research I'm currently leaning towards the combination of AES/RSA due to performance reasons.

The idea is:

• Session start: Each peer generates a public\private RSA-pair and distributes the public key to all other peers.
• For each message sent:
  1. Generate a random AES key and use it to encrypt the message.
  2. Encrypt the AES key using the private RSA key.
  3. Send concatenation of (1) and (2) to all peers.
• For each message received:
  1. Retrieve the AES key using the public key of original sender.
  2. Decrypt message with AES key.
  3. If message is correct parse it, otherwise drop.

If I'm not mistaken, each receiving peer can check the authenticity of a received message using the public key corresponding with the purported sender.

Is the above a good way to approach this? That is, am I on the right track or is there a fundamental problem that I'm overlooking?

Assuming the above is correct, I was contemplating things like key-sizes:

• The private\public RSA scheme has to be secure for the session; let's say 24 hours for purposes of discussion. Because the RSA key pair doesn't change during a session, the public part has to be distributed only once to every peer at session-start, so size doesn't really matter here.
• The AES key is generated randomly per packet, smaller is better.

Considering the above, what is an appropriate key-length for the per-message AES key?

I've found a lot of resources regarding proper key-lengths for (a)symmetric encryption schemes, but most of these recommendations assume data is stored and to be protected for some (or many) years.

I'm aware that the chosen AES key size will dictate which key size to choose for the RSA part.

Any other recommendations\thoughts you might have regarding the preceding text is also very welcome.

Simplified example scenario (I do not plan on sending x itself wrt 'agree' or 'request'):

A                             B                             C
--------------------------------------------------------------
 At Session Start: 
  > Each peer X generates a RSA-key pair and sends its
    public key (pb[X]) to all other peers.
  > Below is after public key exchange took place.
--------------------------------------------------------------
| (A)                         |                             |
|  x  := new proposal         |                             |
|  s  := new AES key          |                             |
|  x' := encryptAES(x, s)     |                             |
|  s' := encryptRSA(s, pr[A]) |                             |  
|                             |                             |
|        send(x', s')         |                             |
|-----------------------------+-------->(DROPPED)           |
|---------------------------->|                             | 
|                             | (B)                         |
|                             |  s := decryptRSA(s', pb[A]) |
|                             |  x := decryptAES(x', s)     |
|                             |  /* assume all is well.. */ |
|                             |                             |
|          agree(x)           |          agree(x)           |
|<----------------------------|---------------------------->|  /* C never received x */ 
|  /* A commits x locally */  |  /* B commits x locally */  |
|                             |                             |
|                             |         request(x)          |
|                             |<----------------------------|
|                             |                             |
|                             |         send(x', s')        |
|                             |---------------------------->| (C)
|                             |                             |  s := decryptRSA(s', pb[A]) 
|                             |                             |  x := decryptAES(x', s)    
|                             |                             |  /* assume all is well.. */   
|                             |                             |
|                             |                             |  /* C commits x locally */
|                             |                             |

Update! Due to the very useful comments by John Deters, I've concluded that the above is plain silly. His answer has therefore been accepted. Currently, I'm experimenting with RSA-PSSR (1024-bits) and SHA1. This way the (short) messages I'm sending can be recovered from the signature itself. Preliminary benchmarks are very encouraging: signing and verification\message extraction combined (typical message size) takes ~0.35ms.

• Library: Crypto++ 5.6.2 statically linked.
• Compiler: g++ 4.8.2 (-O2)
• System: Debian Jessie (3.10-3-amd64)
• CPU: AMD Phenom II X4 965 @ 3.6GHz

Answer 1

You say that "Every message is encrypted using a randomly chosen AES key." and "Messages frequency will be ~8 per second; so 8 * (N-1) messages per second for N peers." and "Message payload will approx. be in the range 128-512 bytes; in any case it will most certainly not exceed 1024 bytes."

It sounds like a very chatty protocol (which is fine, if that's your need.) But if each message requires a unique key, then how are you going to exchange all those random keys? DH? You'll be more than doubling your network utilization, and putting a heavy computation load on every participant, which might be a problem for small, limited CPUs (smart cards) or those with battery power consumption issues (smart phones.)

I think you might intend to use the AES keys as "session keys", generated per this point: "The private\public RSA scheme has to be secure for the session; let's say 24 hours for purposes of discussion." So if you're going to have the concept of session lasting 24 hours, consider using that time period as the lifetime of the AES session keys. Exchange the needed AES keys at the start of the protocol, then continue to reuse them throughout the day. Each message will require a unique IV, of course, and the protocol will still have to be robust enough to reject replay attacks or other MITM attacks.

There doesn't seem to be a security benefit to using RSA to encrypt every AES key for every message. Either you trust RSA and AES for at least a 24 hour period, or there isn't much point.

Of course, each message still needs to identify the RSA key used to encrypt the AES key. A hash of the public key (often used as a Subject Key Identifier on X.509 certificates) makes a good unique public key ID, and is only 20, 32, or 64 bytes long, depending on the hash algorithm chosen. The encrypted key will be the size of your RSA modulus, (256 bytes in the case of a 2048-bit RSA key) which is larger than your estimated payloads, so you might want to optimize that exchange. If you include a separate key exchange message in your protocol, then you don't need to include the large encrypted key with each message.