RFC #1: Timestamp Field

[brannondorsey]

Proposal

Add a timestamp field to the chattervox packet to protect against replay attacks. Initially proposed here.

Details

Protocol v1 supports cryptographic message signatures but provides no mechanism to protect against the replay of signed messages by parties other than the original sender/signer of a message.

From https://github.com/brannondorsey/chattervox/issues/10:

Someone could resend a month old "yes" with your valid signature to a question someone asks now.

The goal of this RFC is to add protocol-level protection from replay attacks using timestamps. Timestamps will be included in packets, however, it is up to the chattervox client software to choose how use them.

Considerations

• The timestamp field should be optional. Applications that don't require replay protection can opt out of timestamp inclusion in their chattervox packets to reduce packet size overhead.
• Communicating clients/stations must agree on the current time (using UTC time etc.) within some degree of accuracy in order to make use of the timestamp field. The method of clock synchronization is beyond the scope of this RFC and should be determined independent of the chattervox protocol.
• Timestamp format...
  • Should be high enough precision that clients can choose strict "no replay after" windows. Ideally 1 second or less.
  • Can be unsigned as messages don't need to represent time before some epoch.
  • Should be Stored in a format that won't rollover for a long time (i.e. not a Unix timestamp due to the Year 2038 problem).
    • Unsigned 32-bit integers last 136 years before a rollover.
    • Unsigned 40-bit integers last 34,865 years before a rollover.
  • Can use a custom epoch.
    • 00:00:00 January 1, 2000 (A millineum epoch)
    • Tue Sep 11 17:46:35 2018 -0400 (The moment of the first chattervox commit)
  • Should be as small as possible to reduce packet size and overhead.

Protocol Changes

Byte Offset	# of Bits	Name	Value	Description
0x0000	16	Magic Header	0x7a39	A constant two-byte value used to identify chattervox packets.
0x0002	8	Version Byte	Number	A protocol version number between 1-255.
0x0003	5	Unused Flag Bits	Null	Reserved for future use.
0x0003	1	Timestamp Flag	Bit	A value of 1 indicates that the message contains a timestamp.
0x0003	1	Digital Signature Flag	Bit	A value of 1 indicates that the message contains a ECDSA digital signature.
0x0003	1	Compression Flag	Bit	A value of 1 indicates that the message payload is compressed.
[0x0004]	[8]	[Signature Length]	Number	The length in bytes of the digital signature. This field is only included if the Digital Signature Flag is set.
[0x0004 or 0x0005]	[0-2048]	[Digital Signature]	Bytes	The ECDSA digital signature created using a SHA256 hash of the message contents and the sender's private key.
[0x0004-0x104]	32	**[Timestamp]***	Unsigned Integer	A time value representing seconds since Midnight Jan 1, 2000.
0x0004-0x125	0-∞	Message*	Bytes	The packet's UTF-8 message payload. If the Compression Flag is set the contents of this buffer is a raw DEFLATE buffer containing the UTF-8 message.

bold values indicate proposed changes.
[] indicates an optional field.
* indicates a member of the signed message if a digital signature is present.

Implementation Notes

The addition of a timestamp field in the chatttervox protocol doesn't itself protect against replay attacks but it provides a mechanism for client software to do so. It's up to the chattervox client to use a computer's clock to compare the timestamp value in a packet to the time a message was received. If the distance between these two values is greater than some threshold then the message is likely being replayed and should be ignored by the client or alert the user of the attack. It is up to the client software to implement this comparison check as well as to define an appropriate threshold. A threshold should be large enough that it allows messages to be digipeated over a busy channel or across several digipeater hops but small enough that it doesn't leave the receiver vulnerable to replay attacks for a prolonged period of time. A threshold value of 5 minutes would allow the replay of messages within a 5 minute window. Transmission time should also be factored into the threshold value as a message may take a second or longer to transmit via 300 or 1200 baud. The chattervox typescript client will likely set this threshold at 30 seconds for initial testing.

Open Questions

• Would a 32-bit timestamp value be large enough? An epoch starting at Jan 1 2000 would rollover in 2136. That seems long enough to me, especially considering that these timestamps, at least used to protect against replay attacks, can represent relative time, not absolute time. We need them only to measure the distance in time between when a message was sent and the current time, not the absolute moment when the message was sent. In this way, rollovers aren't necessarily a problem. The likelyhood that a message would be replayed > 136 years after it was sent is highly unlikely. And even then, depending on the behavior of the client software, an attacker would only have a very short window to replay a message every 136 years.
• Is there a cheaper way to encode the time?

Updates

• UPDATE (October 7, 2018): Change timestamp value from 40 bits to 32 bits. Fix incorrect message offset value.

[lukeburns]

Some points from our conversation as I remember, in case others have thoughts...

One downside to this approach to replay prevention is that it depends on "network conditions" -- if a message is delayed for some reason (eg delayed send, slow propagation across a repeater network, delayed processing, or unsynchronized sender/receiver clocks), then a valid message may be invalidated by a client.

A deterministic approach might be inclusion of a nonce field that can be used by clients interested in recency guarantees. A sender generates a nonce, then receivers can use that nonce to prove their response is not a replay (at least to the sender -- others can not necessarily trust the recency of another sender's nonce). This of course has downsides, especially if I want to reply to multiple messages at once with recency proofs for multiple senders.

[kmarekspartz]

Can't the signature of the most recent (or "deepest") message work as a nonce?

[brannondorsey]

That's an interesting idea, but it doesn't work in this case as the signatures generated via elliptic.js are deterministic.

const EC = require('elliptic').ec;
const ec = new EC('p192');
const key = ec.genKeyPair();
const msgHash = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
const one = key.sign(msgHash);
const two = key.sign(msgHash);
one
// Signature {
//  r: <BN: fa6c7741d8bd83e7088d27285dbf42b097161020d76b800a>,
//  s: <BN: c0cabfec613f049bc100bb6ec724ea9c5a8c35995e2ec3cd>,
//  recoveryParam: 0 }
two
// Signature {
//  r: <BN: fa6c7741d8bd83e7088d27285dbf42b097161020d76b800a>,
//  s: <BN: c0cabfec613f049bc100bb6ec724ea9c5a8c35995e2ec3cd>,
//  recoveryParam: 0 }

We don't want two messages by the same sender containing the text "yes" to have the same message nonce (if we go with a nonce-related solution). If the message signatures contain the timestamp, that becomes less of a problem, but still would prevent two different messages with the same contents sent during the same second from being differentiated.

All this said, I do think nonces may be useful in the protocol down the road. Even as a solution to the replay attack problem should one choose not to use timestamps. The way I see it, the protocol could have support for both, and the client/user could pick which method (timestamp or nonce) to use.

[kmarekspartz]

A deterministic signature is a good thing. My suggestion is to include the previous ("deepest") message in the message body and sign that. A sequence of messages will build up and if a replay happens it shows up as a node earlier in the sequence.

[kpcyrd]

I think this approach requires a reliable transport and wouldn't work with message loss.

[brannondorsey]

I would have to agree. I favor a solution that doesn't require a reliable connection. Consider a scenario where a station broadcasts a weather beacon each hour. The protocol should provide a mechanism to protect against replay attacks even when the communication is entirely one way.

[kmarekspartz]

I used to launch weather balloons! :)

Not sure why reliability is needed, was thinking reliability would be built on top of that, something like a query for a signature you heard referenced but don’t have.

[brannondorsey]

Right on :balloon:

My suggestion is to include the previous ("deepest") message in the message body and sign that. A sequence of messages will build up and if a replay happens it shows up as a node earlier in the sequence.

In my mind anything that builds on sequence starts to fall apart with unreliable connections. I'm also hesitant to include entire signatures or hashes of past messages as that could dramatically increase the payload size. A solution like you mentioned could be implemented on top of the protocol though.

[brannondorsey]

I'm leaning towards implementing this in the next version of the Chattervox protocol. Any objections or comments? Specifically, I'm planning on including the timestamp field as a 32-bit unsigned integer that represents a time value in seconds since Midnight Jan 1, 2000.

[lukeburns]

👍