-----Original Message-----
From: Christian Huitema <huitema@xxxxxxxxxxx>
Sent: Thursday, 23 September 2021 22:13
To: Frank Brockners (fbrockne) <fbrockne@xxxxxxxxx>; secdir@xxxxxxxx
Cc: shwetha.bhandari@xxxxxxxxx; last-call@xxxxxxxx; Youell, Stephen
<stephen.youell@xxxxxxxxxxxx>; sfc@xxxxxxxx; draft-ietf-sfc-proof-of-
transit.all@xxxxxxxx
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 <noreply@xxxxxxxx>
Sent: Monday, 20 September 2021 05:48
To: secdir@xxxxxxxx
Cc: draft-ietf-sfc-proof-of-transit.all@xxxxxxxx; last-call@xxxxxxxx;
sfc@xxxxxxxx
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.
