Re: [Secdispatch] EDHOC Summary

Hi all,

Sorry for the late-ish reply.  I wanted to write some code to confirm my
thoughts here and provide some concrete data.

tl;dr:
* EDHOC is not ALARP, both in the “AL” and “RP” senses
* TLS, unmodified, can be compressed to within a factor of 2 of EDHOC
* TLS can be tweaked to be smaller than EDHOC while making fewer sacrifices
cryptographically
* For the RPK case, with TLS numbers from implementation, not specification:
    * EDHOC = (39, 120, 85)
    * TLS compressed = (64, 180, 116)
    * TLS with similar but smaller sacrifices = (32, 113, 81)

It’s well-established at this point that EDHOC makes some cryptographic
compromises vis à vis TLS that not everyone is comfortable with.  Namely,
(1) it omits the random values sent in the TLS ClientHello and ServerHello
messages, and (2) it relies on an AEAD authentication tag in the role that
the Finished MAC plays in TLS.  The uncertainty around these optimizations
raises two questions:

1. How small can a TLS handshake be made *without* making these compromises?
2. If we make analogous compromises in TLS, what is the minimum message
size?

To answer these questions empirically, I made a fork of the mint TLS 1.3
library that implements these modifications for the RPK case.  You can see
the diff at the following URL; it's about 800 extra LoC:

https://github.com/bifurcation/mint/compare/ctls

(The PSK case would be straightforward, just didn’t have time.)

# Compressing TLS

We start from the observation that simply re-encoding TLS messages doesn’t
change the security proofs at all.  If the inputs to the cryptographic
functions are the same, then you get the same assurances regardless of
whether you get them off the wire or prenegotiate them.  If you assume, as
EDHOC does, that the negotiation bits of TLS can be done out of band, then
you can make a compression layer that, on sending, removes all those
unnecessary bits, and on receiving, reconstructs the original message using
the prenegotiated values.

If you do that with the standard TLS mutual-auth handshake, then you arrive
at the following message sizes and allocations of bytes:

TLS-RPK-ZIP: (64, 180, 116)
M1: 32 [rand] + 32 [DH]
M2: 32 [rand] + 32 [DH] + 4 [CertID] + 64 [SIG] + 32 [MAC] + 16 [TAG]
M3: 4 [CertID] + 64 [SIG] + 32 [MAC] + 16 [TAG]

This seems like a pretty compelling result in itself, since you get the
full power of TLS here in terms of assurance — including things like
downgrade protection on however you did the prenegotiation.  And you get it
all with less than 2x the message size of EDHOC.

# Tweaking TLS in Questionable Ways

Now let’s consider the EDHOC shortcuts noted above.  The removal of the
random values seems more plausible to me, since the DH values contribute
fresh randomness anyway.  So we can tweak the TLS stack to set the randoms
to zero, and we no longer have to send them in our messages:

TLS-ZIP-NORAND: (32, 148, 116)
M1: 32 [DH]
M2: 32 [DH] + 4 [CertID] + 64 [SIG] + 32 [MAC] + 16 [TAG]
M3: 4 [CertID] + 64 [SIG] + 32 [MAC] + 16 [TAG]

Already, we’ve surpassed EDHOC on the first message.  Removing the Finished
message is dicier, since it introduces the authentication concerns that
have been discussed elsewhere.  In TLS, we can “virtualize” the Finished
message; since each side can compute the Finished MAC, they can include it
in the key schedule even if it’s not sent.  If we do that, then we end up
below EDHOC’s message sizes:

TLS-RPK-ZIP-NORAND-VFIN: (32, 113, 81)
M1: 32 [DH]
M2: 32 [DH] + 1 [CertID] + 64 [SIG] + 16 [TAG]
M3: 1 [CertID] + 64 [SIG] + 16 [TAG]

This is an interesting structure to compare to EDHOC.  First, it’s notable
that we got here with fewer sacrifices than EDHOC.  Where EDHOC uses 8-bit
tags, we use full-size.  And the fact that Finished MACs end up in the key
schedule mean that at least the application keys will diverge if the
parties disagree.  (The things in EDHOC that this TLS variant lacks, like
connection IDs, can be added back at similar cost.)  Second, this
highlights how many bytes EDHOC wastes on framing:

EDHOC-RPK:
M1: 39  = 32 [DH] + 1 [msgType] + 1 [CID] + 2 [ciphers] + 3 [framing]
M2: 120 = 32 [DH] + 4 [KID] + 64 [SIG] + 8 [TAG] + 2 [CID] + 10 [framing]
M3: 85  = 4 [KID] + 64 [SIG] + 8 [TAG] + 1 [CID] + 8 [framing]

In summary, having taken a pretty deep dive on this problem, it’s not clear
at all to me that if you want a lightweight AKE (regardless of the
definition of “lightweight”) that EDHOC is the best starting point.  We can
get most of the way there just by profiling down TLS, and if we need to go
farther, we get more savings with higher assurance by tweaking TLS than we
do with a clean-slate design like EDHOC.

—Richard

On Thu, Mar 28, 2019 at 6:33 AM Roman Danyliw <rdd@cert.org> wrote:

> Hi!
>
> We have observed the continued discussion and interest in the topics
> discussed at the March 2019 Virtual Interim Secdispatch meeting [1].  Our
> assessment of the current state of this discuss and as well as proposed
> next steps are below.
>
> Regards,
> Roman and Ben
>
> [1]
> https://mailarchive.ietf.org/arch/msg/secdispatch/9AfqrecZfFMlMGxSXOo4ENZtrVk
>
> ==[ Summary of ADs ]==
> EDHOC Summary
>
> -----[ 1. What is the problem we are faced with?
>
> The community needs an AKE that is 'lightweight' (per slide #3 of [2]) and
> enables forward security for constrained environments using OSCORE [13].
> 'Lightweight' refers to:
>
> ** resource consumption, measured by bytes on the wire, wall-clock time to
> complete (i.e., the initial latency added to application protocols by the
> AKE), or power (per slide #12 of [2])
> ** the amount of new code required on end systems which already have an
> OSCORE stack [4]
>
> -----[ 2. Is the problem understood and narrowly scoped?
>
> Use with OSCORE implicitly assumes that this AKE would support:
> ** transport over CoAP, and
> ** COSE algorithms
>
> The specific constrained environments that we are considering use NB-IoT,
> 6TiSCH, and LoRaWAN.  The desire is to optimize the AKE to be 'as [small]
> ... as reasonably achievable' (per [3]) in these environments.
>
> ** With respect to 6TiSCH, IETF consensus on the 6TiSCH WG charter has
> already identified the need to "secur[e] the join process and mak[e] that
> fit within the constraints of high latency, low throughput and small frame
> sizes that characterize IEEE802.15.4 TSCH." [12].
> ** With respect to NB-IoT and LoRaWAN, IETF consensus on the LPWAN WG
> charter has identified the need to improve the transport capabilities of
> LPWA networks such as NB-IoT and LoRa whose "common traits include ...
> frame sizes ... [on] the order of tens of bytes transmitted a few times per
> day at ultra-low speeds" [16]. This indicates IETF interest in supporting
> these radio environments, though no security-specific requirements are
> included in the charter.
>
> It may be necessary to evaluate options that make different trade-offs
> across a number of dimensions.
>
> ** Per 'bytes on the wire', it is desirable for these AKE messages to fit
> into the MTU size of these protocols; and if not possible, within as few
> frames as possible.  Note that using multiple MTUs can have significant
> costs in terms of time and power (listed below). For 6TiSCH specifically,
> as a time-sliced network, this metric (or rather, the quantization into
> frame count) is particularly noteworthy, since more frames contribute  to
> congestion for spectrum (and concomitant error rates) in a non-linear way,
> especially in scenarios when large numbers of independent nodes are
> attempting to execute an AKE to join a network.
>
> ** Per 'time', it is desirable for the AKE message exchange(s) to complete
> in a reasonable amount of time, both for a single uncongested exchange and
> when multiple exchanges are running in an interleaved fashion.  This
> latency may not be a linear function depending on congestion and the
> specific radio technology used.  For LoRaWAN, which is legally required to
> use a 1% (or smaller) duty cycle, a payload split into two fragments
> instead of one increases the time to complete the sending of this payload
> by 10,000% (per slide #10 of [2]).
>
> ** Per 'power', it is desirable for the transmission of AKE messages and
> crypto to draw as little power as possible  The best mechanism for doing so
> differs across radio technologies.  For example, NB-IoT uses licensed
> spectrum and thus can transmit at higher power to improve coverage, making
> the transmitted byte count relatively more important than for other radio
> technologies.  In other cases, the radio transmitter will be active for a
> full MTU frame regardless of how much of the frame is occupied by message
> content, which makes the byte count less sensitive for the power
> consumption.  Increased power consumption is unavoidable in poor network
> conditions, such as most wide-area settings including LoRaWAN.
>
> ** Per 'new code', it is desirable to introduce as little new code as
> possible onto OSCORE-enabled devices to support this new AKE.  These
> devices have on the order of 10s of kB of memory and 100s of kB of storage
> on which an embedded OS; a COAP stack; CORE and AKE libraries; and target
> applications would run.  It is expected that the majority of this space is
> available for actual application logic, as opposed to the support libraries.
>
> A key question to answer is whether any new solution will reduce these
> properties to a sufficient extent to merit investment.
>
> -----[ 3. Do we believe it is possible to engineer a solution?
>
> EDHOC [1] appears to be an existence proof that it is possible to produce
> an AKE that meaningfully reduces the costs across at least two dimensions
> identified in question #1 and 2 (bytes and time).
>
> EDHOC appears to favorably outperform TLS/CoAP, the current technology,
> relative to these dimensions.
>
> ** Per 'bytes on the wire', MTU sizes and their alignment to the size of
> messages of EDHOC vs. TLS/CoAP can be found in slide #33 of [2], and in
> [5].  Additional details for 6TiSCH in particular can be found in slide
> 36-37 of [2].
>
> ** Per 'time', the latency due to back-off time estimates with EDHOC vs.
> TLS/CoAP using LoRaWAN can be found in slide #39 of [2]
>
> ** Per 'power', estimates of the power usage of EDHOC vs TLS/CoAP using
> NB-IoT can be found in slide #35 of [2]
>
> ** Per 'new code', being able to reuse primitives from the existing COSE
> stack is expected to benefit the code size for EDHOC, but no hard data is
> yet available for comparison.
>
> Exploratory work with cTLS [10] and femtoTLS [11] has suggested that
> certain optimizations used in EDHOC can also be applied to a
> TLS/CoAP-variant.  How this impacts the original assumptions and security
> analysis for (D)TLS is unknown.
>
> -----[ 4. Is this particular proposal a good basis for working on?
>
> EDHOC shows gains in defining an AKE with forward secrecy that is
> 'reasonably small[er]' than the baseline of (D)TLS.  Specifically, it
> appears that EDHOC would enable:
> ** for 6TiSCH, a more efficient network join operation, with network join
> traffic fitting in one frame per flight (that is, the optimal possible
> behavior) in up to a 5-hop network [17]
> ** for LoRaWAN, an AKE with forward secrecy that avoids the unacceptable
> backoff-induced latency
>
> A limited interop was performed on draft-selander-ace-cose-ecdhe-05
> (EDHOC) at IETF 98 between [14] and [15].  Despite the inherent challenges
> of producing a new AKE that is secure, there is reason to have confidence
> in the security claims made by EDHOC -- the security properties of -08 were
> formally verified by [8][9].  Identified issues from this formal analysis
> [8] were addressed in -11.  The CFRG crypto review panel conducted two
> reviews [6][7].  These reviews confirmed that the security claims are
> reasonable, attested that the identified issues found in the formal
> analysis [8] were fixed, and provided additional recommendations.
>
> Re-encoding of the TLS handshake as suggested by cTLS [10] may be
> possible.  However, as of yet, cTLS is an incomplete specification, cTLS
> has no formal security analysis, and is technically a new protocol.
>
> -----[ Conclusion
>
> There appears to be an understood and scoped problem that is feasible to
> engineer.  Among the available starting points to address the problem
> defined in question #1, EDHOC presents a viable choice.
>
> Chartering a narrowly scoped, short-lived WG in this space with EDHOC as a
> starting point seems to be an attractive path forward, but we would like to
> receive community feedback on the degree of support for this approach.
>
> -----[ References
> [1] https://www.ietf.org/id/draft-selander-ace-cose-ecdhe-13.txt
> [2]
> https://datatracker.ietf.org/meeting/interim-2019-secdispatch-01/materials/slides-interim-2019-secdispatch-01-sessa-edhoc.pdf
> [3]
> https://mailarchive.ietf.org/arch/msg/secdispatch/-GPqswnS-DRvrAKsPbdoes4Y4lE
> [4]
> https://mailarchive.ietf.org/arch/msg/secdispatch/rJqvstLHo7aLfu-ODril-wIVn_0
> [5]
> https://docs.google.com/document/d/1wLoIexMLG3U9iYO5hzGzKjkvi-VDndQBbYRNsMUlh-k
> [6] https://mailarchive.ietf.org/arch/msg/cfrg/6WN2C2RYGTIAInE2jIUco6L9pO8
> [7] https://mailarchive.ietf.org/arch/msg/cfrg/2OY2om1FjhNNBmUzwYJroHv7eWQ
> [8] https://alessandrobruni.name/papers/18-edhoc.pdf
> [9] https://github.com/theisgroenbech/edhoc-proverif
> [10] https://tools.ietf.org/html/draft-rescorla-tls-ctls-01
> [11] https://github.com/bifurcation/mint/compare/ftls
> [12] https://datatracker.ietf.org/doc/charter-ietf-6tisch/
> [13] https://datatracker.ietf.org/doc/draft-ietf-core-object-security/
> [14] https://github.com/alexkrontiris/EDHOC-C
> [15] https://github.com/jimsch/EDHOC-csharp
> [16] https://datatracker.ietf.org/doc/charter-ietf-lpwan/
> [17]
> https://datatracker.ietf.org/doc/draft-ietf-6tisch-dtsecurity-zerotouch-join
>
> ==[ End ]==
>
> _______________________________________________
> Secdispatch mailing list
> Secdispatch@ietf.org
> https://www.ietf.org/mailman/listinfo/secdispatch
>