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

[Martin Vigoureux <[e-mail]>]

Joel, I agree with your analysis.

Franck, I don't think it is reasonable to expect the wg to produce 
actionable requirements on the security and/or operational aspects of 
such type of solution. I sadly don't have more useful suggestions than 
to either work with cfrg to come up with a solution which would work in 
domains where sfc is typically used or design a solution based on 
Christian's suggestion, but with possibly a limited scope of applicability.

I suspect that any of these changes will require another round of review 
by the WG.

-m

Le 2021-09-28 à 19:15, Joel M. Halpern a écrit :
> (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 <[e-mail]>
>> *Sent:* Saturday, 25 September 2021 16:42
>> *To:* Frank Brockners (fbrockne) <[e-mail]>; [e-mail]
>> *Cc:* [e-mail]; [e-mail]; Youell, Stephen 
>> <[e-mail]>; [e-mail]; 
>> [e-mail]; [e-mail]
>> *Subject:* Re: [Last-Call] Secdir last call review of 
>> draft-ietf-sfc-proof-of-transit-08
>>
>> On 9/25/2021 4:20 AM, Frank Brockners (fbrockne) wrote:
>>
>>     Hi Christian,
>>
>>     Thanks for the follow-up. Please see below.
>>
>>         -----Original Message-----
>>
>>         From: Christian Huitema<[e-mail]>  
>> <mailto:[e-mail]>
>>
>>         Sent: Friday, 24 September 2021 17:16
>>
>>         To: Frank Brockners (fbrockne)<[e-mail]>  
>> <mailto:[e-mail]>;[e-mail]  <mailto:[e-mail]>
>>
>>         Cc:[e-mail]  
>> <mailto:[e-mail]>;[e-mail]  
>> <mailto:[e-mail]>; Youell, Stephen
>>
>>         <[e-mail]>  
>> <mailto:[e-mail]>;[e-mail]  
>> <mailto:[e-mail]>; draft-ietf-sfc-proof-of-
>>
>>         [e-mail]  
>> <mailto:[e-mail]>;[e-mail]  
>> <mailto:[e-mail]>
>>
>>         Subject: Re: [Last-Call] Secdir last call review of 
>> draft-ietf-sfc-proof-of-transit-
>>
>>         08
>>
>>         On 9/24/2021 1:39 AM, Frank Brockners (fbrockne) wrote:
>>
>>             Hi Christian,
>>
>>             Thanks a lot for the detailed follow-up. Please see inline.
>>
>>                 -----Original Message-----
>>
>>                 From: Christian Huitema<[e-mail]>  
>> <mailto:[e-mail]>
>>
>>                 Sent: Thursday, 23 September 2021 22:13
>>
>>                 To: Frank Brockners (fbrockne)<[e-mail]>  
>> <mailto:[e-mail]>;[e-mail]  <mailto:[e-mail]>
>>
>>                 Cc:[e-mail]  
>> <mailto:[e-mail]>;[e-mail]  
>> <mailto:[e-mail]>; Youell, Stephen
>>
>>                 <[e-mail]>  
>> <mailto:[e-mail]>;[e-mail]  
>> <mailto:[e-mail]>; draft-ietf-sfc-proof-of-
>>
>>                 [e-mail]  <mailto:[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]>  <mailto:[e-mail]>
>>
>>                         Sent: Monday, 20 September 2021 05:48
>>
>>                         To:[e-mail]  <mailto:[e-mail]>
>>
>>                         
>> Cc:[e-mail]  
>> <mailto:[e-mail]>;
>>
>>                         [e-mail]  
>> <mailto:[e-mail]>;[e-mail]  <mailto:[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
>>
>>                         K+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.
>>
>>                     ...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.
>>
>>         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.
>>
>>         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.
>>
>>     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.
>>
>> 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
>>
>