Subject: [Cfrg] Minimum freshness in EdDSA25519 signed messages

From: Robert Moskowitz <[email-masked]>
Date: Thu, 29 Aug 2019 11:30:32 -0400

This is for a project I am working on:

EdDSA25519 as HIP HI (rfc7401)
16 byte HHIT (draft-moskowitz-hierarchical-hip under revision)
Device has HHIT/HI (100M devices potentially)
Authorizer's HHIT/HI (see HDA bits in Device HHIT; no more than a few 
hundred HDAs)

Case 1:  Simple message construction

16 byte HHIT,
4 byte lifetime stamp,
n bytes shared context data,
64 byte sig of 16+4+n

Is the 4 bytes lifetime stamp enough freshness to protect the sig from 
attack?

Attacker can know all other information months in advance to compute an 
attack for a future time.

Is 4 bytes freshness enough?  Is more needed?  How large must n be?

Pointer to information on this?

Note:  Given device HHIT, receiver can lookup device HI (signing 
EdDSA25519 public key).

Case 2: 2nd level of sig for off-line validation.

Receiver has no Internet access to look up the HI in Case 1.
Fortunately, there are only a limited, x, number of signing authorities 
with their own EdDSA25519 HI/HHIT. Which can be cached.

Message in Case 1 PLUS

32 byte Device's HI,
4 byte Authorizer's signing date,
16 byte Authorizer's HHIT
m bytes shared context,
64 byte sig of 32+4+16+m message (that is. not including Case 1 message)

Receiver can validate outer sig based on cache of Authorizer's HHIT/HI.
With now, trusted Device HI, receiver can now validate Case 1 message.

Is 4 bytes freshness enough?  Is more needed?  How large must m be? m 
may be unique for each Authorizer.

My limited readings and searches (my search foo is terribly weak) lead 
me to believe that those 4 byte timestamps are all that I need and both 
n and m could be zero, but practice is to have something there.

Thank you for any reviews and/or pointers.

Bob