Re: [sfc] [Last-Call] Secdir last call review of draft-ietf-sfc-proof-of-transit-08

["Frank Brockners (fbrockne)" <[e-mail]>]

Hi Christian,

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

> -----Original Message-----
> From: Christian Huitema <[e-mail]>
> Sent: Thursday, 23 September 2021 22:13
> To: Frank Brockners (fbrockne) <[e-mail]>om>; [e-mail]
> Cc: [e-mail]; [e-mail]; Youell, Stephen
> <[e-mail]>om>; [e-mail]; draft-ietf-sfc-proof-of-
> [e-mail]
> Subject: Re: [Last-Call] Secdir last call review of draft-ietf-sfc-proof-of-transit-
> 08
> 
> 
> On 9/23/2021 12:31 PM, Frank Brockners (fbrockne) wrote:
> > Hi Christian,
> >
> > Thanks a lot for your detailed review. Please see inline.
> >
> >> -----Original Message-----
> >> From: Christian Huitema via Datatracker <[e-mail]>
> >> Sent: Monday, 20 September 2021 05:48
> >> To: [e-mail]
> >> Cc: [e-mail]; [e-mail];
> >> [e-mail]
> >> Subject: Secdir last call review of
> >> draft-ietf-sfc-proof-of-transit-08
> >>
> >> 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".
> > ...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 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
> >> K+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.
> > ...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.
> 
> 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.

...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


> 
> 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
> 
> 
> 
> 
>