Subject: Re: [Teep] Scalability of nonce-based freshness

From: Thomas Fossati <[email-masked]>
Date: Fri, 12 Mar 2021 21:09:31 +0000

Hi Göran,

On 12/03/2021, 19:00, "Göran Selander" <[email-masked]> wrote:
> Hi Dave, and all,
>
> Referring to the TEEP protocol presentation at the WG meeting, there
> was a discussion about the use of tokens and what method of freshness
> to apply in TEEP (slides 11-16 in the presentation).
>
> If I understood right the main argument against the nonce-based method
> (slide 15) is the question of scalability: "Receivers have to keep
> state to remember each nonce supplied until it’s used"
>
> If I'm not mistaken, this condition on the receiver could be relaxed
> by the receiver generating nonces as encrypted time stamps. This would
> only require the receiver to remember an encryption context used to
> encrypt/decrypt the time stamps used as nonces. The encryption context
> can be small (say, less than 50 bytes for key, IV and counter) and
> doesn't grow with the number of TAs (but would typically be updated
> for each nonce generated, e.g. stepping the counter).
>
> Note that the receiver needs a clock but it need not be synced because
> the time stamps are only used by receiver; once when nonces are
> generated, and then again when freshness is determined from the nonce
> received back in the evidence. Such a clock coincides with the
> assumption of this method according to slide 15: "Receivers need a
> clock to “expire” nonces, but need not be synced".
>
> Perhaps this should be an input to RATS rather than TEEP. But since
> this seemed to be the main argument against the nonce-based method I
> just wanted to share my 2 cents to the discussion.

I think this is all correct.  (BTW, that's what I meant when I said the
TAM should make this a verifier problem as there is no need for the
nonce to be stored at the TAM.)

With your nonce generation scheme:

A. Verifier is initialised with secret key k

B.1: TAM asks Verifier for a nonce;
B.2: Verifier generates nonce n = E(t_req, k) and sends it to TAM;

C: TAM runs the challenge-response protocol with the Attester, sending
   N and obtaining Evidence(n) in return;

D.1: TAM forwards Evidence(n) to Verifier for verification;
D.2: Verifier extract n and does D(n, k):
  D.2.1: If decryption fails, goto drop;
  D.2.2: If decryption succeeds, extract t_req
D.3: Verifier checks |now - t_req| < acceptable_recentness_threshold:
  D.3.1: If so, proceed with verification of Evidence;
  D.3.2: If not, return ESTALE

Note that if B.* is done once every "period", thus avoiding the extra
round-trip per nonce / attestation session, this scheme falls back to
the epoch-id based model.

cheers!

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: Göran Selander <[email-masked]>
Date: Mon, 15 Mar 2021 07:34:18 +0000

Hi Thomas,

Seems we have the same line of thought :-)

Some more details.

In addition to encryption key, the encryption context typically also requires an initialization vector (a.k.a. "nonce", but using that term would be confusing here) which must only be used once with a given key. This may e.g. involve a counter which is stepped for each encryption. The value of the counter needs to be reproduced at decryption time, e.g. by defining the token nonce to be the counter concatenated with the encrypted time stamp (using same notation as below: n = counter ||  E(t_req, k) ).

While this part is straightforward there are some subtleties as to how the nonces are used which may have an impact on security. 

If only the nonces are tracked (or encryption context cached, in the case of encrypted time stamps) it is not necessarily possible to determine that a particular response is actually matching a request with the same nonce. For example, two colluding attesters who both have received a request from the same verifier could in theory exchange their nonces which would not be noticed. This is not necessarily a problem depending on different things e.g. the policy for expiring nonces: If only freshness is sought, then it is only required that a recently issued nonce is presented, since that restricts the time when the response could have been created. It may not even matter if the same nonce is used by different attesters. In this setting the properties may be similar with nonces taken directly from a PRNG or encrypted time stamps. 

The nonce could also carry information about the request, e.g. encrypting parts of the request, in which case it is possible to verify a stronger binding to a particular request. Or, in the interest of saving bytes on the wire at the expense of caching more about the request, the nonce coule be a MAC over parts of the request. In the ase of a MAC, however, it doesn't make much sense to use encrypted time stamps since they would need to be cached.

Again, not sure how much this matters for this work. Just input to the discussion.

Göran

On 2021-03-12, 22:10, "TEEP on behalf of Thomas Fossati" <[email-masked] on behalf of [email-masked]> wrote:

    Hi Göran,

    cheers!

    IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.
    _______________________________________________
    TEEP mailing list
    [email-masked]
    https://www.ietf.org/mailman/listinfo/teep

---

From: Thomas Fossati <[email-masked]>
Date: Mon, 15 Mar 2021 12:06:54 +0000

Hi Göran,

On 15/03/2021, 07:34, "Göran Selander" <[email-masked]>
wrote:
> Some more details.
>
> In addition to encryption key, the encryption context typically also
> requires an initialization vector (a.k.a. "nonce", but using that term
> would be confusing here) which must only be used once with a given
> key. This may e.g. involve a counter which is stepped for each
> encryption. The value of the counter needs to be reproduced at
> decryption time, e.g. by defining the token nonce to be the counter
> concatenated with the encrypted time stamp (using same notation as
> below: n = counter ||  E(t_req, k) ).

Right.

And looking a bit more at the practical side here, the whole crypto
overhead including the IV/counter and the authentication tag can make it
unfeasible for a "time token" of the sort you have described to stay
below ~32 bytes (note that EAT nonces are bstr .size (8..64)).  Taking
AES-GCM as benchmark you'd need a 12o nonce and a 16o authentication
tag, which leaves 4o for UNIX time with second resolution.  Cutting down
a bit on the tag size, but not too much because malleability is
absolutely not acceptable, you could get back maybe 4 bytes, which you
might or might not want to use for other kind of overhead (e.g., a
context identifier if you are doing some load balancing or for key
rotation, or have higher time resolution, etc.)

> While this part is straightforward there are some subtleties as to how
> the nonces are used which may have an impact on security.
>
> If only the nonces are tracked (or encryption context cached, in the
> case of encrypted time stamps) it is not necessarily possible to
> determine that a particular response is actually matching a request
> with the same nonce. For example, two colluding attesters who both
> have received a request from the same verifier could in theory
> exchange their nonces which would not be noticed.

Sure, the simple "time token" you described is just a bearer token that
can be "redeemed" more than once by one or more parties.  Per se, the
only proof it carries is about the time it was minted and the identity of
the minter.  If you need more than that, you need to boost it up a notch.

> This is not necessarily a problem depending on different things e.g.
> the policy for expiring nonces: If only freshness is sought, then it
> is only required that a recently issued nonce is presented, since that
> restricts the time when the response could have been created. It may
> not even matter if the same nonce is used by different attesters. In
> this setting the properties may be similar with nonces taken directly
> from a PRNG or encrypted time stamps.
>
> The nonce could also carry information about the request, e.g.
> encrypting parts of the request, in which case it is possible to
> verify a stronger binding to a particular request. Or, in the interest
> of saving bytes on the wire at the expense of caching more about the
> request, the nonce coule be a MAC over parts of the request. In the
> ase of a MAC, however, it doesn't make much sense to use encrypted
> time stamps since they would need to be cached.

Indeed, if one needs the "redeem time token" operation to be unique
(i.e., effectively asking the time token to be a nonce in the
cryptographic sense), one could look at some form of binding (e.g.,
RFC8471) or minimal state keeping - possibly playing with rate limiting
within the sliding validity window.

It doesn't look like TEEP has this requirement though.

> Again, not sure how much this matters for this work. Just input to the

Thanks, that was very helpful, for me at least :-)

Cheers!

---

From: Göran Selander <[email-masked]>
Date: Thu, 18 Mar 2021 13:45:58 +0000

Wrapping up this discussion: we had an offline discussion and Thomas suggested the use of a time stamp concatenated with a MAC as the nonce, which makes sense to me. So, the nonce-based method should allow for scalable deployment, e.g. with a pool of verifiers assuming a fixed size state (shared key used in MAC) and reasonably synchronized clocks.

Göran

On 2021-03-15, 13:07, "Thomas Fossati" <[email-masked]> wrote:

    Hi Göran,

    Right.

    Cheers!

---

From: Thomas Fossati <[email-masked]>
Date: Fri, 19 Mar 2021 09:30:37 +0000

On 18/03/2021, 13:46, "Göran Selander" <[email-masked]> wrote:
> Wrapping up this discussion: we had an offline discussion and Thomas
> suggested the use of a time stamp concatenated with a MAC as the nonce,
> which makes sense to me. So, the nonce-based method should allow for
> scalable deployment, e.g. with a pool of verifiers assuming a fixed size
> state (shared key used in MAC) and reasonably synchronized clocks.

And just to reiterate one important point: this all works fine only if
replay attacks are not a threat, i.e.: either they have no impact on the
protocol outcome, or they can be prevented at some other layer.

cheers, t