Subject: [CFRG] Looking for input on draft-lorlacks-license-activation-protocol

From: Maximilian Lorlacks <[email-masked]>
Date: Mon, 04 Oct 2021 17:45:25 +0000

Dear CFRG,

I'm currently working on an Internet-Draft intended as Experimental,
draft-lorlacks-license-activation-protocol, a DRM protocol.  As it
involves cryptography, I am hoping to perhaps get a few insightful
pointers from this list.

The protocol is a UDP-based request->response protocol involving
a client and a server.  The server does not trust the client.  A client
is expected to trust the server.  There is no round trip.

# Protocol overview

Every client is assumed to have a hard-coded, pre-shared set of keys:

1. a server X25519 public key for the key exchange;
2. a server Ed25519 public key for verifying the response.

The request looks like this:

1. 32 byte client ephemeral public key (X25519);
2. variable-length blob encrypted and authenticated with ChaPoly;
   there is no AAD, thus the ephermeral public key is authenticated
   implicitly through the result of the key exchange.

The key derivation for both parties looks like this:

1. PRK = HKDF-Extract(salt=none,
                      IKM=client's ephemeral X25519 public key |
                          server's X25519 public key |
                          server's Ed25519 public key |
                          the X25519 shared secret)
2. OKM = HKDF-Expand(PRK,
                     info=[ASCII representation of
                        "56065c4d-d2e0-4ba9-bf9f-76f9159e2987-LAP-V02"],
                     L=64)
3. the symmetric key for the client-to-server packet is now
   the first 32 bytes of OKM.
4. the symmetric key for the server-to-client packet is now
   the second 32 bytes of OKM.

The response looks like this:

1. 64-byte Ed25519 signature;
2. variable-length blob encrypted and authenticated with ChaPoly.

Why not TLS?  DRM is often implemented in constrained environments
(between virtual machines and trusted execution environments).
Bringing a TLS stack both complicates implementation and greatly
improves attacker visibility by virtue of there being only a very
limited amount of TLS implementations.

Why no round trips?  For much the same reason.  A trusted execution
environment does well to minimize its state.  As it stands, I am
currently unconvinced (though open to changing my mind) that the added
complexity of managing multiple packets is worth the gain in security.
I currently assume that a server-side compromise and leak of a static
secret is ultimately not a major issue as cycling the keys with the next
release is expected to be a feasible strategy.

I have strictly gone with what's tongue-in-cheek known as the djb suite
of algorithms.  This is no vote against any of the NIST algorithms.
However, in DRM scenarios, it is common practice (albeit of perhaps
questionable utility) to re-implement core algorithms that would
otherwise be outsourced to libraries.

The djb suite was thus primarily picked for ease of implementation on
the client side as a naive implementation happens to be most commonly
a correct one; it is assumed that the server-side has no such
restrictions.  In particular, I would be delighted to hear of an
asymmetric signature algorithm that is trivial to implement a verifier
for by avoiding multiple-precision arithmetic.

I am looking forward to your esteemed responses.  By all means, I invite
you to state points that seem obvious or refute my rationale
at its core.  Thank you for your time.

Cheers,

Maximilian Lorlacks

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 4 Oct 2021 18:16:09 -0700

>    the first 32 bytes of OKM.

What's the IV?  You've kind of reinvented ECIES here.

>    the second 32 bytes of OKM.

What's the IV?

> 1. 64-byte Ed25519 signature;

Signature of what?

> 2. variable-length blob encrypted and authenticated with ChaPoly.

How does the authentication here relate to the signature?

It's trivial for an attacker who captures a single request to replay
it.  What effect does that have on the protocol?

In any event, this is all very vague.  What is this protocol supposed
to do?  What security properties do you want?

---

From: Maximilian Lorlacks <[email-masked]>
Date: Thu, 07 Oct 2021 13:58:12 +0000

Thank you for taking the time to respond to my inquiry.  Please
allow me to respond:

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Tuesday, October 5, 2021 1:16 AM, Andy Lutomirski <[email-masked]> wrote:

> maxlorlax=[email-masked] wrote:
>

Since I believe that I've given all the parameters to HKDF,
I assume you are talking about the IV for the ChaPoly operations.
The IV for both packets are all zeroes.  Because both sides use
different keys for the actual decryption operation, there is no
potential for nonce reuse.

I do seem to have reinvented ECIES here except there is no ECIES
for the response.

> > 1.  64-byte Ed25519 signature;

2 and 3, the rest of the packet.  I'm sorry, I should've made that
clearer.

> How does the authentication here relate to the signature?

The authenticity and integrity of the message are already guaranteed
by the signature.  However, the authentication tag prevents a client
from accepting a packet mistakenly sent out of sequence.
Assume the following sequence of events:

1. Client sends a request. Because of the nature of UDP, the packet
   seems lost in limbo.
2. Client retries the request after the timeout for the response elapses
   with a fresh key pair and drops the state relating to the request
   in step 1.
3. Server receives and responds to request 1 before request 2 even
   arrives.
4. Server receives and responds to request 2.
5. Response 1 arrives before response 2.
6. Client checks the signature over the contents of response 1;
   it checks out.
7. Client checks the authentication tag for response 1,
   which fails because Client cycled the credentials in step 2.
   It therefore can abort instead of working with corrupted
   response data.
8. Response 2 arrives and all is well.

However, thinking about this some more, the keypairs involved could
just be added to the signature, obsoleting the authentication tag in
the response entirely.  Thank you for pointing this out.

> it. What effect does that have on the protocol?

Replay attacks are a policy consideration and assumed to be naturally
not in the interest of an attacker.
I'll get back to this.

> to do? What security properties do you want?

LAP is supposed to allow structured activation of a software
license.  In essence: Request in -> license confirmation UUID out.
A request packet contains: protocol version, packet size, client's
idea of the current time, a UUID identifying an installation, a UUID
identifying an installation of an add-on product, a SKU ID identifying
the product that was installed and - if previously obtained - the
existing license's UUID, as well as the variable-length,
centrally-issued, opaque blob uniquely identifying the license (and
perhaps other additional information such as hardware information).

A server response contains:
protocol version, packet size, server's idea of the current time,
the relevant client UUID echoed back, the SKU ID echoed back and
a UUID uniquely identifying the license.

Both parties are expected to have access to reliable network clocks
and cryptographically secure random number generators.

The threat model is limited to passive observers on the network.
It is implicitly assumed (and perhaps ought to be stated in
a coming draft-lorlacks-license-activation-protocol-05)
that replay attacks are not a (major) issue.
Let's look at replays on the server side first.

Assume a packet P that was sent by a legitimate client to the server.
By spec, the server MUST validate that the timestamp in the packet
matches the server's idea of the current time with at most 30 seconds
of difference.  Therefore, P cannot be replayed after 30 seconds pass.
Assume further that P is replayed before 30 seconds pass.  The server
has no criteria to reject the replayed packet.  It will therefore apply
a policy decision (that is out of scope for the protocol per se).
It can:

1. reject the packet because the installation ID is known to the
   server already (assuming one-time activations only); or
2. accept the packet (and refresh the current license).

Because semantically, a replayed packet is both provides no
harm to the server and does not allow the client to gain any benefits,
a replay attack is of no consequence in context.

Let's look at the issue of replaying a server packet to a client.
Assume a response packet R.  This packet is already tied to the
client's previously sent packet by means of the key derivation.  If the
client's expected key and the key involved in the server response
mismatch, the client is expected to abort due to the authentication tag
mismatch.
The replay attack thus failed.

A dishonest client could make its key generation to always lead to a
static result matching a pre-determined packet from the server.
Such a dishonest client is out of scope as the attacker behind such a
modified client would patch out the DRM mechanisms in the first place
instead.

I hope this helps clarify.  Once more, allow me to thank you for taking
the time to respond.

Cheers,

Maximilian Lorlacks

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 7 Oct 2021 07:48:14 -0700

> potential for nonce reuse.

That's an interesting leap of logic.

> not in the interest of an attacker.

Your key derivation is entirely a function of the client's incoming
packet and fixed data on the server.  If a request is replayed, the
response key and nonce get reused.  Unless the encrypted data is
bit-for-bit identical, it's game over.

---

From: Maximilian Lorlacks <[email-masked]>
Date: Fri, 08 Oct 2021 07:01:55 +0000

> bit-for-bit identical, it's game over.

I absolutely missed the interaction of the key derivation with replay
attacks since I looked at replay attacks only from a post-decryption
standpoint instead of also taking it into account at the cryptography
layer.  This is indeed a devastating, instant-loss attack.  Thanks for
pointing it out.

It's back to the drawing board with me.

Cheers,

Maximilian Lorlacks

---

From: Dan Harkins <[email-masked]>
Date: Fri, 08 Oct 2021 16:13:11 -0700

> It's back to the drawing board with me.

   Allow me to throw in a plug for AES-SIV (RFC 5297). It has a 
deterministic
authenticated encryption mode that doesn't require a nonce. That will
allow you to avoid the "devastating, instant-loss attack" and go back to
worrying about addressing replay attacks post-decryption.

   regards,

   Dan.

-- 
"The object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." -- Marcus Aurelius

---

From: Maximilian Lorlacks <[email-masked]>
Date: Sat, 09 Oct 2021 04:36:55 +0000

> worrying about addressing replay attacks post-decryption.

Thank you for the pointer (and your hard work into making RFC 5297;
I have implemented it in the past and enjoyed the clear guidance given
therein).  I am considering a SIV-style mode but all the published
RFCs for it (AES-SIV or AES-GCM-SIV) depend on AES in particular.  The
reason I am trying to avoid AES is due to my experience that in this
space, cryptography is often reimplemented and rarely by people that
have familiarity with secure implementation of cryptography.  AES is
hostile to a straightforward implementation because doing so with th
"natural" solution of lookup tables will introduce timing attacks.
Bit-slicing is neither intuitive nor necessarily trivial.  For Ed25519,
this is already on shaky ground due to the arbitrary precision
arithmetic involved (and thankfully irrelevant on the client side as
it only verifies).

At the same time, the other idea I've had so far (generating 24 bytes
of nonce by each party, involving these in the key generation as well,
and switching from ChaCha20 to XChaCha20), sets my draft into waiting
mode for draft-irtf-cfrg-xchacha being published and loses an extra
24 bytes for each party to send in the 508 bytes that you can safely
use in a UDP packet.

As it stands, it comes down to uncomfortable trade-offs with regards to
whom I expect to implement the specification.
I agree that AES-SIV would be the best way forward in principle (and
perhaps my draft shall forever serve as a reminder why SIV-style
constructions should become more commonplace);
I am just currently struggling with coming to terms with trusting
implementers in the DRM space to use a safe library for AES.

Once more, thank you for the pointer.

Cheers,

Maximilian Lorlacks