Subject: [sfc] Secdir last call review of draft-ietf-sfc-proof-of-transit-08

From: Christian Huitema via Datatracker <[email-masked]>
Date: Sun, 19 Sep 2021 20:48:18 -0700

Reviewer: Christian Huitema
Review result: Serious Issues

I have reviewed this document as part of the security directorate's  ongoing
effort to review all IETF documents being processed by the  IESG.  These
comments were written primarily for the benefit of the security area directors.
Document editors and WG chairs should treat these comments just like any other
last call comments.

This document proposes a security mechanism to prove that traffic transited through
all specified nodes in a path. The mechanism works by adding a short option to
each packet for which transit shall be verified. The option consists of a random number
set by the originator of the packet, and a sum field to which each transit node
adds a value depending on public parameters, on the random number and on secrets
held by the node. The destination has access to all the secrets held by the nodes
on the path, and can verify whether or not the final sum corresponds to the sum
of expected values. The proposed size of the random number and the sum field is 64 bits.

In the paragraph above, I described the mechanism without mentioning the algorithm
used to compute these 64 bit numbers. The 64 bit size is obviously a concern: for
cryptographic applications, 64 bits is not a large number, and that might be a
weakness whatever the proposed algorithm. The actual algorithm appears to be a
bespoke derivation of Shamir's Secret Sharing algorithm (SSS). In other word, it is
a case of "inventing your own crypto".

SSS relies on the representation of polynomials as a sum of
Lagrange Basis Polynomials. Each of the participating nodes holds a share of the
secret represented by a point on the polynomial curve. A polynomial of degree
K on the field of integers modulo a prime number N can only be revealed if at
list K+1 participants reveal the value of their point. The safety of the
algorithm relies on the size of the number N and on the fact that the
secret shall be revealed only once. But the algorithm does not use SSS
directly, so it deserves its own security analysis instead of relying 
simply on Shamir's work.

The proposed algorithm uses two polynomials of degree K for a path containing
K+1 nodes, on a field defined by a prime number N of 64 bits. One of the
polynomial, POLY-1, is secret, and only fully known by the verifying node.
The other, POLY-2 is public, with the constant coefficient set at a random
value RND for each packet.

For each packet, the goal is compute the value of POLY-1 plus POLY-2 at the
point 0 -- that is, the constant coefficient of POLY-3 = POLY-1 + POLY-2.

Without going in too much details, one can observe that the constant
coefficient of POLY-3 is equal to the sum of the constant coefficients
of POLY-1 and POLY-2, and that the constant coefficient of POLY-2 is
the value RND present in each packet. In the example given in section
3.3.2, the numbers are computed modulo 53, the constant coefficient
of POLY-1 is 10, and the value RND is 45. The final sum  CML is indeed
10 + 45 = 2 mod 53.

To me, this appears as a serious weakness in the algorithm. If an adversary
can observe the value RND and CML for a first packet, it can retrieve the
constant coefficient of POLY-1, and thus can predict the value of CML for
any other packet. That does not seem very secure.

My recommendation would be to present the problem and ask the CFRG for 
algorithm recommendations.

---

From: "Frank Brockners (fbrockne)" <[email-masked]>
Date: Thu, 23 Sep 2021 19:31:31 +0000

Hi Christian,

Thanks a lot for your detailed review. Please see inline.

> -----Original Message-----
> From: Christian Huitema via Datatracker <[email-masked]>
> Sent: Monday, 20 September 2021 05:48
> To: [email-masked]
> Cc: [email-masked]; [email-masked]; [email-masked]
> Subject: Secdir last call review of draft-ietf-sfc-proof-of-transit-08
> 
> Document editors and WG chairs should treat these comments just like any
> other last call comments.
> 
> This document proposes a security mechanism to prove that traffic transited
> through all specified nodes in a path. The mechanism works by adding a short
> option to each packet for which transit shall be verified. The option consists of a
> random number set by the originator of the packet, and a sum field to which
> each transit node adds a value depending on public parameters, on the random
> number and on secrets held by the node. The destination has access to all the
> secrets held by the nodes on the path, and can verify whether or not the final
> sum corresponds to the sum of expected values. The proposed size of the
> random number and the sum field is 64 bits.
> 
> In the paragraph above, I described the mechanism without mentioning the
> algorithm used to compute these 64 bit numbers. The 64 bit size is obviously a
> concern: for cryptographic applications, 64 bits is not a large number, and that
> might be a weakness whatever the proposed algorithm. The actual algorithm
> appears to be a bespoke derivation of Shamir's Secret Sharing algorithm (SSS). In
> other word, it is a case of "inventing your own crypto".

...FB: SSS is a well know algorithm and draft-ietf-sfc-proof-of-transit does not modify it.
All draft-ietf-sfc-proof-of-transit does is to operationalize the SSS algorithm for the proof of transit use case.

Also note that the draft does not require the use of 64 bit numbers.
Nor does draft require a minimum time between changing the secrets. 
What particular attack are you concerned about where 64 bit numbers are a concern?

> 
> SSS relies on the representation of polynomials as a sum of Lagrange Basis
> Polynomials. Each of the participating nodes holds a share of the secret
> represented by a point on the polynomial curve. A polynomial of degree K on the
> field of integers modulo a prime number N can only be revealed if at list K+1
> participants reveal the value of their point. The safety of the algorithm relies on
> the size of the number N and on the fact that the secret shall be revealed only
> once. But the algorithm does not use SSS directly, so it deserves its own security
> analysis instead of relying simply on Shamir's work.
> 
> The other, POLY-2 is public, with the constant coefficient set at a random value
> RND for each packet.
> 
> coefficient of POLY-3 is equal to the sum of the constant coefficients of POLY-1
> and POLY-2, and that the constant coefficient of POLY-2 is the value RND
> present in each packet. In the example given in section 3.3.2, the numbers are
> computed modulo 53, the constant coefficient of POLY-1 is 10, and the value
> RND is 45. The final sum  CML is indeed
> 10 + 45 = 2 mod 53.
> 
> To me, this appears as a serious weakness in the algorithm. If an adversary can
> observe the value RND and CML for a first packet, it can retrieve the constant
> coefficient of POLY-1, and thus can predict the value of CML for any other
> packet. That does not seem very secure.

...FB: There seems to be a bit of confusion or misreading of how the method works. In the above statement you seem to assume that the verifier would not be part of the proof-chain, so that the final CML value would be somehow exposed to an external entity along with RND. This is not the case. The verifier is the last node (k+1) in the proof-chain. 

At concept level, the method reconstructs the polynomial hop by hop, picking up a point on the curve at every hop. Only final node in the proof-chain, which is also the verifier, acts on the information of all the k+1 points and as such is able to reconstruct the polynomial. 

In section 3.2.1, the draft explicitly states that the verifier *is* part of the proof-chain: "Each of the k+1 nodes (including verifier) are assigned a point on the polynomial i.e., shares of the SECRET." The fact that the verifier, i.e., the last node in the proof-chain ("k+1"),  can retrieve the secret, is desired and intentional, because the verifier needs to compare the result of the iterative construction of the secret with the secret value it received from the controller. This is how the system is designed, and the calculation of (10+45) mod 53 = 2 is part of the verification. 

Cheers, Frank

---

From: Christian Huitema <[email-masked]>
Date: Thu, 23 Sep 2021 13:13:12 -0700

> In section 3.2.1, the draft explicitly states that the verifier *is* part of the proof-chain: "Each of the k+1 nodes (including verifier) are assigned a point on the polynomial i.e., shares of the…

OK. That's slightly less bad. But it is still very bad crypto, because 
you are effectively doing a linear combination.

You are evaluating POLY-3 = POLY-1 + POLY-2

POLY-2 can be written as POLY-2 = RND + POLY-2-NC, in which POLY2-NC 
only contains the non constant terms -- that is, POLY-2-NC(0) = 0

Then for any point X, we get POLY-3(X) = POLY-1(X) + POLY2-NC(X) + RND
For a given value Xj of X, this means we can express : POLY-3(Xj) = Vj + RND
In which Vj is a constant term = POLY-1(Xj) + POLY2-NC(Xj)

Each node will increment the cumul by the value LPCj * POLY-3(Xj) = LPCj 
* (Vj + RND)

Suppose that an adversary can observe the value of CML before and after 
being incremented by node Xj. Suppose that it could do that twice. Then 
it has the values:

CML1-before-j = C1b
CML1-after-j = C1a
D1 = C1a - C1b = LPCj * (Vj + RND1)

CML1-before-j = C2b
CML1-after-j = C2a
D2 = C2a - C2b = LPCj * (Vj + RND2)

D2-D1 = LPCj*(RND2-RND1)

LPCj = (RND2-RND1)/(D2-D1)
Vj = D2/LPCj - RND2

The inverse of numbers modulo a prime P is easily computed -- see 
Fermat's little theorem.

Once the input and output of a node have been observed twice, it becomes 
easy to update the cumulative sum CML while bypassing these nodes.

The scheme described in the draft is definitely not equivalent to SSS. 
It boils down to linear combinations of coefficients, and it is not secure.

-- Christian Huitema

---

From: "Frank Brockners (fbrockne)" <[email-masked]>
Date: Fri, 24 Sep 2021 08:39:55 +0000

Hi Christian,

Thanks a lot for the detailed follow-up. Please see inline.

> From: Christian Huitema <[email-masked]>
> Sent: Thursday, 23 September 2021 22:13
> To: Frank Brockners (fbrockne) <[email-masked]>; [email-masked]
> Cc: [email-masked]; [email-masked]; Youell, Stephen
> <[email-masked]>; [email-masked]; draft-ietf-sfc-proof-of-
> [email-masked]
> Subject: Re: [Last-Call] Secdir last call review of draft-ietf-sfc-proof-of-transit-
> 08
> 
> 
> >> I have reviewed this document as part of the security directorate's
> >> ongoing effort to review all IETF documents being processed by the
> >> IESG.  These comments were written primarily for the benefit of the security
> area directors.
> >> Document editors and WG chairs should treat these comments just like
> >> any other last call comments.
> >>
> >> This document proposes a security mechanism to prove that traffic
> >> transited through all specified nodes in a path. The mechanism works
> >> by adding a short option to each packet for which transit shall be
> >> verified. The option consists of a random number set by the
> >> originator of the packet, and a sum field to which each transit node
> >> adds a value depending on public parameters, on the random number and
> >> on secrets held by the node. The destination has access to all the
> >> secrets held by the nodes on the path, and can verify whether or not
> >> the final sum corresponds to the sum of expected values. The proposed size
> of the random number and the sum field is 64 bits.
> >>
> >> In the paragraph above, I described the mechanism without mentioning
> >> the algorithm used to compute these 64 bit numbers. The 64 bit size
> >> is obviously a
> >> concern: for cryptographic applications, 64 bits is not a large
> >> number, and that might be a weakness whatever the proposed algorithm.
> >> The actual algorithm appears to be a bespoke derivation of Shamir's
> >> Secret Sharing algorithm (SSS). In other word, it is a case of "inventing your
> own crypto".
> >> SSS relies on the representation of polynomials as a sum of Lagrange
> >> Basis Polynomials. Each of the participating nodes holds a share of
> >> the secret represented by a point on the polynomial curve. A
> >> polynomial of degree K on the field of integers modulo a prime number
> >> N can only be revealed if at list K+1 participants reveal the value
> >> of their point. The safety of the algorithm relies on the size of the
> >> number N and on the fact that the secret shall be revealed only once.
> >> But the algorithm does not use SSS directly, so it deserves its own security
> >> K+1 nodes, on a field defined by a prime number N of 64 bits. One of
> >> K+the
> >> The other, POLY-2 is public, with the constant coefficient set at a
> >> random value RND for each packet.
> >>
> >> For each packet, the goal is compute the value of POLY-1 plus POLY-2
> >> at the point 0 -- that is, the constant coefficient of POLY-3 = POLY-1 + POLY-
> 2.
> >>
> >> coefficient of POLY-3 is equal to the sum of the constant
> >> coefficients of POLY-1 and POLY-2, and that the constant coefficient
> >> of POLY-2 is the value RND present in each packet. In the example
> >> given in section 3.3.2, the numbers are computed modulo 53, the
> >> constant coefficient of POLY-1 is 10, and the value RND is 45. The
> >> final sum  CML is indeed
> >> 10 + 45 = 2 mod 53.
> >>
> >> To me, this appears as a serious weakness in the algorithm. If an
> >> adversary can observe the value RND and CML for a first packet, it
> >> can retrieve the constant coefficient of POLY-1, and thus can predict
> >> the value of CML for any other packet. That does not seem very secure.
> > ...FB: There seems to be a bit of confusion or misreading of how the method
> works. In the above statement you seem to assume that the verifier would not
> be part of the proof-chain, so that the final CML value would be somehow
> exposed to an external entity along with RND. This is not the case. The verifier is
> the last node (k+1) in the proof-chain.
> >
> > At concept level, the method reconstructs the polynomial hop by hop, picking
> up a point on the curve at every hop. Only final node in the proof-chain, which is
> also the verifier, acts on the information of all the k+1 points and as such is able
> to reconstruct the polynomial.
> >
> > In section 3.2.1, the draft explicitly states that the verifier *is* part of the
> proof-chain: "Each of the k+1 nodes (including verifier) are assigned a point on
> the polynomial i.e., shares of the SECRET." The fact that the verifier, i.e., the last
> node in the proof-chain ("k+1"),  can retrieve the secret, is desired and
> intentional, because the verifier needs to compare the result of the iterative
> construction of the secret with the secret value it received from the controller.
> This is how the system is designed, and the calculation of (10+45) mod 53 = 2 is
> part of the verification.
> 
> OK. That's slightly less bad. But it is still very bad crypto, because you are
> effectively doing a linear combination.
> 
> POLY-2 can be written as POLY-2 = RND + POLY-2-NC, in which POLY2-NC only
> contains the non constant terms -- that is, POLY-2-NC(0) = 0
> 
> Then for any point X, we get POLY-3(X) = POLY-1(X) + POLY2-NC(X) + RND For a
> given value Xj of X, this means we can express : POLY-3(Xj) = Vj + RND In which Vj
> is a constant term = POLY-1(Xj) + POLY2-NC(Xj)
> 
> Suppose that an adversary can observe the value of CML before and after being
> incremented by node Xj. Suppose that it could do that twice. Then it has the
> values:
> 
> CML1-before-j = C1b
> CML1-after-j = C1a
> The inverse of numbers modulo a prime P is easily computed -- see Fermat's
> little theorem.
> 
> Once the input and output of a node have been observed twice, it becomes easy
> to update the cumulative sum CML while bypassing these nodes.

...FB: This is great. Thanks for spelling out the details.  You raise a good point: For the solution to make sense, we need to ensure that an attacker cannot observe the input and output of a node. 
To ensure this does not happen, we must require the communication to/from the node to be encrypted, e.g., through link layer encryption of at least the proof-of-transit data fields. 
We'll add this requirement to the draft - and also detail the threat you describe above in detail in the security considerations section.

Thanks again, Frank

---

From: Christian Huitema <[email-masked]>
Date: Fri, 24 Sep 2021 08:16:12 -0700

> We'll add this requirement to the draft - and also detail the threat you describe above in detail in the security considerations section.

That still will not be sufficient, because you also have to deal with 
the nodes themselves. By definition, they see the intermediate results 
of other nodes. For example, if the function chain is A->B->C->D->E, the 
node B sees the output of B and the node D sees the input of D. If B and 
D  collude, they have access to the input and output of C. They can 
easily find the secrets of C, and then execute a chain A->B---->D->E in 
which the input of D is "corrected" to hide the absence of C from the 
evaluator E.

The linear combination scheme in the draft is not sound crypto. My 
recommendation is to present the problem and the threat model clearly to 
the crypto community, for example by presenting to the CFRG, and solicit 
advice on better algorithms.

-- Christian Huitema

---

From: "Frank Brockners (fbrockne)" <[email-masked]>
Date: Sat, 25 Sep 2021 11:20:19 +0000

Hi Christian,

Thanks for the follow-up. Please see below.

> Sent: Friday, 24 September 2021 17:16
> [email-masked]; [email-masked]
> >>>> Document editors and WG chairs should treat these comments just
> >>>> like any other last call comments.
> >>>>
> >>>> transited through all specified nodes in a path. The mechanism
> >>>> works by adding a short option to each packet for which transit
> >>>> shall be verified. The option consists of a random number set by
> >>>> the originator of the packet, and a sum field to which each transit
> >>>> node adds a value depending on public parameters, on the random
> >>>> number and on secrets held by the node. The destination has access
> >>>> to all the secrets held by the nodes on the path, and can verify
> >>>> whether or not the final sum corresponds to the sum of expected
> >>>> values. The proposed size
> >>>> In the paragraph above, I described the mechanism without
> >>>> mentioning the algorithm used to compute these 64 bit numbers. The
> >>>> 64 bit size is obviously a
> >>> ...FB: SSS is a well know algorithm and
> >>> draft-ietf-sfc-proof-of-transit does not
> >> modify it.
> >>> All draft-ietf-sfc-proof-of-transit does is to operationalize the
> >>> SSS algorithm
> >> for the proof of transit use case.
> >>> What particular attack are you concerned about where 64 bit numbers
> >>> are a
> >> concern?
> >>>> Lagrange Basis Polynomials. Each of the participating nodes holds a
> >>>> share of the secret represented by a point on the polynomial curve.
> >>>> A polynomial of degree K on the field of integers modulo a prime
> >>>> number N can only be revealed if at list K+1 participants reveal
> >>>> the value of their point. The safety of the algorithm relies on the
> >>>> size of the number N and on the fact that the secret shall be revealed only
> once.
> >>>> K+1 nodes, on a field defined by a prime number N of 64 bits. One
> >>>> K+of the
> >>>> For each packet, the goal is compute the value of POLY-1 plus
> >>>> POLY-2 at the point 0 -- that is, the constant coefficient of
> >>>> POLY-3 = POLY-1 + POLY-
> >> 2.
> >>>> Without going in too much details, one can observe that the
> >>>> constant coefficient of POLY-3 is equal to the sum of the constant
> >>>> coefficients of POLY-1 and POLY-2, and that the constant
> >>>> coefficient of POLY-2 is the value RND present in each packet. In
> >>>> the example given in section 3.3.2, the numbers are computed modulo
> >>>> 53, the constant coefficient of POLY-1 is 10, and the value RND is
> >>>> 45. The final sum  CML is indeed
> >>>> 10 + 45 = 2 mod 53.
> >>>>
> >>>> can retrieve the constant coefficient of POLY-1, and thus can
> >>>> predict the value of CML for any other packet. That does not seem very
> secure.
> >> works. In the above statement you seem to assume that the verifier
> >> would not be part of the proof-chain, so that the final CML value
> >> would be somehow exposed to an external entity along with RND. This
> >> is not the case. The verifier is the last node (k+1) in the proof-chain.
> >> up a point on the curve at every hop. Only final node in the
> >> proof-chain, which is also the verifier, acts on the information of
> >> all the k+1 points and as such is able to reconstruct the polynomial.
> >> proof-chain: "Each of the k+1 nodes (including verifier) are assigned
> >> a point on the polynomial i.e., shares of the SECRET." The fact that
> >> the verifier, i.e., the last node in the proof-chain ("k+1"),  can
> >> retrieve the secret, is desired and intentional, because the verifier
> >> needs to compare the result of the iterative construction of the secret with
> the secret value it received from the controller.
> >> This is how the system is designed, and the calculation of (10+45)
> >> mod 53 = 2 is part of the verification.
> >>
> >> OK. That's slightly less bad. But it is still very bad crypto,
> >> because you are effectively doing a linear combination.
> >>
> >> Then for any point X, we get POLY-3(X) = POLY-1(X) + POLY2-NC(X) +
> >> RND For a given value Xj of X, this means we can express : POLY-3(Xj)
> >> = Vj + RND In which Vj is a constant term = POLY-1(Xj) + POLY2-NC(Xj)
> >>
> >> Suppose that an adversary can observe the value of CML before and
> >> after being incremented by node Xj. Suppose that it could do that
> >> twice. Then it has the
> >> values:
> >>
> >> CML1-before-j = C1b
> >> CML1-after-j = C1a
> >> Once the input and output of a node have been observed twice, it
> >> becomes easy to update the cumulative sum CML while bypassing these
> nodes.
> > ...FB: This is great. Thanks for spelling out the details.  You raise a good point:
> For the solution to make sense, we need to ensure that an attacker cannot
> observe the input and output of a node.
> > To ensure this does not happen, we must require the communication to/from
> the node to be encrypted, e.g., through link layer encryption of at least the
> proof-of-transit data fields.
> > We'll add this requirement to the draft - and also detail the threat you describe
> above in detail in the security considerations section.
> 
> That still will not be sufficient, because you also have to deal with the nodes
> themselves. By definition, they see the intermediate results of other nodes. For
> example, if the function chain is A->B->C->D->E, the node B sees the output of B
> and the node D sees the input of D. If B and D  collude, they have access to the
> input and output of C. They can easily find the secrets of C, and then execute a
> chain A->B---->D->E in which the input of D is "corrected" to hide the absence of
> C from the evaluator E.

Thanks much. You raise another valid point and we will add it to the security considerations section.
That said, IMHO we'd need to put the scenario you raise into perspective:
If the nodes B and D would be compromised by an attacker, the deployment would face a much more serious security issue than what any proof-of-transit method could protect against.

> recommendation is to present the problem and the threat model clearly to the
> crypto community, for example by presenting to the CFRG, and solicit advice on
> better algorithms.

There has been quite a bit of discussion on proof of transit in several WGs, even before the SFC WG picked it up. And the SFC working group has considered different approaches early on in the solution specification, including e.g., using nested encryption, which is probably more in line with your preferences. See https://datatracker.ietf.org/doc/html/draft-ietf-sfc-proof-of-transit-01#section-3.5.1. From my recollection of the discussion - others please chime in - one main reason of why the current approach was chosen was its computational simplicity, i.e., hardware platforms which do not support native encryption capabilities like AES-NI can implement it without considerable impact on the computational latency. So in other words, the current method is the result of a trade-off decision.

Cheers, Frank

---

From: Christian Huitema <[email-masked]>
Date: Sat, 25 Sep 2021 07:42:06 -0700

> There has been quite a bit of discussion on proof of transit in several WGs, even before the SFC WG picked it up. And the SFC working group has considered different approaches early on in the solut…
We are discussing mathematics, not opinions. It is not a matter of 
preferences, it is a matter of threat model. The draft that I reviewed 
does not mention that the scheme should only be used in a benign 
environment in which no attacker can see the traffic and all nodes are 
fully trusted to not try gaming the system. The proposed scheme uses 
crypto vocabulary, with references to SSS and use of terms like "proof" 
or "cryptanalysis". Indeed, the header paragraph of the security 
considerations says:

    POT is a mechanism that is used for verifying the path through which
    a packet was forwarded.  The security considerations of IOAM in
    general are discussed in [I-D.ietf-ippm-ioam-data].  Specifically, it
    is assumed that POT is used in a confined network domain, and
    therefore the potential threats that POT is intended to mitigate
    should be viewed accordingly.  POT prevents spoofing and tampering;
    an attacker cannot maliciously create a bogus POT or modify a
    legitimate one.  Furthermore, a legitimate node that takes part in
    the POT protocol cannot masquerade as another node along the path.
    These considerations are discussed in detail in the rest of this
    section.

The previous discussions have shown that an attacker CAN "maliciously 
create a bogus POT or modify a legitimate one", provided it is able to 
see the traffic, or some of the traffic. The discussions also show that 
"a legitimate node that takes part in the POT protocol" CAN "masquerade 
as another node along the path". Contrary to statements in the 
"cryptanalysis" section, "A passive attacker observing CML values across 
nodes (i.e., as the packets entering and leaving)" CAN  "perform 
differential analysis". The attack cannot "be mitigated using a good 
PRNG for generating RND".

If the system was only designed for operation in a "benign environment" 
and you were only concerned with detecting operation failures, I am 
pretty sure that you could come out with something less complicated. For 
example you could exploit the analysis that I made to radically simplify 
the implementation and describe the scheme as "CML = Sum (Xj*RNDp)", 
where Xj is a secret coefficient provisioned to node j, and RNPp is per 
packet random number. The verification by the evaluator will check that 
"RND == CML + Xe*RND", where "Xe = 1 - Sum Xj". That would get you an 
easy-to-implement checksum. But you would need to be very clear about 
the domain of application, and the failure mode if the traffic can be 
observed or nodes can be compromised, and the draft should probably drop 
the references to Shamir's SSS, because they just obfuscate the analysis.

-- Christian Huitema

---

From: "Frank Brockners (fbrockne)" <[email-masked]>
Date: Tue, 28 Sep 2021 15:12:48 +0000

Hi Christian,
Thanks for the follow up – and the suggestion of an alternate approach. IMHO – and I checked with other authors, who voiced similar views – it would be best to follow your guidance and have the working group crispen up the requirements as well as assumptions for the operational environment and only then discuss and evaluate solution approaches.
Depending on the target set of requirements and the operational environment, the WG can choose an appropriate approach with guidance from CFRG. That could be, per what you suggest below, something much simpler from a control plane perspective - avoiding the complexities of SSS  – with a data-plane as simple as what the draft currently suggests. That could also be another, yet to be determined approach, such as the approach based on nested encryption that the WG discussed before, or an SSS based approach with a polynomial per packet, etc. Hopefully we’ll get it right the next time.

Martin, Jim, Joel – any thoughts and guidance from your end, on whether the document should be handed back to the working group?

Thanks again, Frank

From: Christian Huitema <[email-masked]>
Sent: Saturday, 25 September 2021 16:42
To: Frank Brockners (fbrockne) <[email-masked]>; [email-masked]
Cc: [email-masked]; [email-masked]; Youell, Stephen <[email-masked]>; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Last-Call] Secdir last call review of draft-ietf-sfc-proof-of-transit-08

Hi Christian,

-----Original Message-----

From: Christian Huitema <[email-masked]><mailto:[email-masked]>

To: Frank Brockners (fbrockne) <[email-masked]><mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>

Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; Youell, Stephen

<[email-masked]><mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; draft-ietf-sfc-proof-of-

[email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>

08

Hi Christian,

-----Original Message-----

From: Christian Huitema <[email-masked]><mailto:[email-masked]>

To: Frank Brockners (fbrockne) <[email-masked]><mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>

Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; Youell, Stephen

<[email-masked]><mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; draft-ietf-sfc-proof-of-

[email-masked]<mailto:[email-masked]>

Subject: Re: [Last-Call] Secdir last call review of

draft-ietf-sfc-proof-of-transit-

08

Hi Christian,

-----Original Message-----

From: Christian Huitema via Datatracker <[email-masked]><mailto:[email-masked]>

To: [email-masked]<mailto:[email-masked]>

Cc: [email-masked]<mailto:[email-masked]>;

[email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>

Subject: Secdir last call review of

draft-ietf-sfc-proof-of-transit-08

IESG.  These comments were written primarily for the benefit of the

security

area directors.

Secret Sharing algorithm (SSS). In other word, it is a case of

"inventing your

own crypto".

modify it.

SSS algorithm

are a

concern?

once.

But the algorithm does not use SSS directly, so it deserves its own

security

The proposed algorithm uses two polynomials of degree K for a path

containing

K+of the

POLY-3 = POLY-1 + POLY-

2.

10 + 45 = 2 mod 53.

secure.

...FB: There seems to be a bit of confusion or misreading of how the

method

At concept level, the method reconstructs the polynomial hop by hop,

picking

In section 3.2.1, the draft explicitly states that the verifier *is*

part of the

Each node will increment the cumul by the value LPCj * POLY-3(Xj) =

LPCj

* (Vj + RND)

twice. Then it has the

values:

CML1-before-j = C1b

CML1-after-j = C1a

CML1-before-j = C2b

CML1-after-j = C2a

D2-D1 = LPCj*(RND2-RND1)

Vj = D2/LPCj - RND2

Fermat's little theorem.

nodes.

C from the evaluator E.

better algorithms.

There has been quite a bit of discussion on proof of transit in several WGs, even before the SFC WG picked it up. And the SFC working group has considered different approaches early on in the solution specification, including e.g., using nested encryption, which is probably more in line with your preferences. See https://datatracker.ietf.org/doc/html/draft-ietf-sfc-proof-of-transit-01#section-3.5.1. From my recollection of the discussion - others please chime in - one main reason of why the current approach was chosen was its computational simplicity, i.e., hardware platforms which do not support native encryption capabilities like AES-NI can implement it without considerable impact on the computational latency. So in other words, the current method is the result of a trade-off decision.
We are discussing mathematics, not opinions. It is not a matter of preferences, it is a matter of threat model. The draft that I reviewed does not mention that the scheme should only be used in a benign environment in which no attacker can see the traffic and all nodes are fully trusted to not try gaming the system. The proposed scheme uses crypto vocabulary, with references to SSS and use of terms like "proof" or "cryptanalysis". Indeed, the header paragraph of the security considerations says:

   section.

The previous discussions have shown that an attacker CAN  "maliciously create a bogus POT or modify a legitimate one", provided it is able to see the traffic, or some of the traffic. The discussions also show that "a legitimate node that takes part in the POT protocol" CAN "masquerade as another node along the path". Contrary to statements in the "cryptanalysis" section, "A passive attacker observing CML values across nodes (i.e., as the packets entering and leaving)" CAN  "perform differential analysis". The attack cannot "be mitigated using a good PRNG for generating RND".

If the system was only designed for operation in a "benign environment" and you were only concerned with detecting operation failures, I am pretty sure that you could come out with something less complicated. For example you could exploit the analysis that I made to radically simplify the implementation and describe the scheme as "CML = Sum (Xj*RNDp)", where Xj is a secret coefficient provisioned to node j, and RNPp is per packet random number. The verification by the evaluator will check that "RND == CML + Xe*RND", where "Xe = 1 - Sum Xj". That would get you an easy-to-implement checksum. But you would need to be very clear about the domain of application, and the failure mode if the traffic can be observed or nodes can be compromised, and the draft should probably drop the references to Shamir's SSS, because they just obfuscate the analysis.

-- Christian Huitema

---

From: "Joel M. Halpern" <[email-masked]>
Date: Tue, 28 Sep 2021 13:15:49 -0400

(Keeping the SFC group on copy in hopes they will prove me wrong.)

I am not sure what to recommend here.  Neither Jim nor I are in a 
posiition to mediate a dispute about cryptography.
The document got through WG last call with barely sufficient support. 
The odds of getting meaningful feadback if we ask the WG about the 
problem scope are very low.   We have had to push people to get enough 
response to things on the charter that we commited to.

If the proposed document does not work as written, then we shouldn't 
progress it in its current form.  As ntoed, getting meaningful WG 
discussion of changes seems unlikely.

Martin, if you have a suggestion, Jim and I (and presumably the WG) are 
listening.

Yours,
Joel

On 9/28/2021 11:12 AM, Frank Brockners (fbrockne) wrote:
> Hi Christian,
> 
> Thanks for the follow up – and the suggestion of an alternate approach. 
> IMHO – and I checked with other authors, who voiced similar views – it 
> would be best to follow your guidance and have the working group crispen 
> up the requirements as well as assumptions for the operational 
> environment and only then discuss and evaluate solution approaches.
> 
> Depending on the target set of requirements and the operational 
> environment, the WGcanchoose an appropriate approach with guidance 
> fromCFRG. That could be, per what you suggest below, something much 
> simpler from a control plane perspective - avoiding the complexities of 
> SSS  – with a data-plane as simple as what the draft currently suggests. 
> That could also be another, yet to be determined approach, such as the 
> approach based on nested encryption that the WG discussed before, or an 
> SSS based approach with a polynomial per packet, etc. Hopefully we’ll 
> get it right the next time.
> 
> Martin, Jim, Joel – any thoughts and guidance from your end, on whether 
> the document should be handed back to the working group?
> 
> Thanks again, Frank
> 
> *From:*Christian Huitema <[email-masked]>
> *Sent:* Saturday, 25 September 2021 16:42
> *To:* Frank Brockners (fbrockne) <[email-masked]>; [email-masked]
> *Cc:* [email-masked]; [email-masked]; Youell, Stephen 
> <[email-masked]>; [email-masked]; 
> [email-masked]; [email-masked]
> *Subject:* Re: [Last-Call] Secdir last call review of 
>         From: Christian Huitema<[email-masked]>  <mailto:[email-masked]>
> 
>         To: Frank Brockners (fbrockne)<[email-masked]>  <mailto:[email-masked]>;[email-masked]  <mailto:[email-masked]>
> 
>         Cc:[email-masked]  <mailto:[email-masked]>;[email-masked]  <mailto:[email-masked]>; Youell, Stephen
> 
>         <[email-masked]>  <mailto:[email-masked]>;[email-masked]  <mailto:[email-masked]>; draft-ietf-sfc-proof-of-
> 
>         [email-masked]  <mailto:[email-masked]>;[email-masked]  <mailto:[email-masked]>
> 
>                 From: Christian Huitema<[email-masked]>  <mailto:[email-masked]>
> 
>                 To: Frank Brockners (fbrockne)<[email-masked]>  <mailto:[email-masked]>;[email-masked]  <mailto:[email-masked]>
> 
>                 Cc:[email-masked]  <mailto:[email-masked]>;[email-masked]  <mailto:[email-masked]>; Youell, Stephen
> 
>                 <[email-masked]>  <mailto:[email-masked]>;[email-masked]  <mailto:[email-masked]>; draft-ietf-sfc-proof-of-
> 
>                 [email-masked]  <mailto:[email-masked]>
> 
>                         From: Christian Huitema via Datatracker<[email-masked]>  <mailto:[email-masked]>
> 
>                         To:[email-masked]  <mailto:[email-masked]>
> 
>                         Cc:[email-masked]  <mailto:[email-masked]>;
> 
>                         [email-masked]  <mailto:[email-masked]>;[email-masked]  <mailto:[email-masked]>
> 
>     There has been quite a bit of discussion on proof of transit in several WGs, even before the SFC WG picked it up. And the SFC working group has considered different approaches early on in the solution specification, including e.g., using nested encryption, which is probably more in line with your preferences. Seehttps://datatracker.ietf.org/doc/html/draft-ietf-sfc-proof-of-transit-01#section-3.5.1  <https://datatracker.ietf.org/doc/html/draft-ietf-sfc-proof-of-transit-01#section-3.5.1>. From my recollection of the discussion - others please chime in - one main reason of why the current approach was chosen was its computational simplicity, i.e., hardware platforms which do not support native encryption capabilities like AES-NI can implement it without considerable impact on the computational latency. So in other words, the current method is the result of a trade-off decision.
>