Subject: [sfc] proof-of-transit: continue with both approaches, or choose one?

From: "Frank Brockners (fbrockne)" <[email-masked]>
Date: Sat, 15 Dec 2018 20:19:24 +0000

During the SFC WG at IETF 103 in Bangkok we raised the question, whether we could simplify the draft and choose a single algorithm for proof-of-transit only (see also https://datatracker.ietf.org/meeting/103/materials/minutes-103-sfc-01). Given that we could not come to a conclusion, we decided to take the discussion to the list.

Background:
draft-ietf-sfc-proof-of-transit-01 describes two different approaches: "nested encryption" and "Shamir's secret sharing scheme (SSSS)". We documented both approaches in the initial version of the draft, because the two approaches had different qualities: While SSSS was computationally cheaper (each node only needs to perform two additions, a multiplication and a modulo-division), nested-encryption allowed to verify that packets traversed a set of nodes in a particular order ("ordered POT - OPOT") - something that the SSSS-approach in the initial version of the draft did not offer. With the changes discussed in IETF 102 and now documented in draft-ietf-sfc-proof-of-transit-01, both approaches offer order preservation.
In summary, we can now observe the following qualities of the two approaches:

  *   SSSS: Allows verification that a given set of nodes has been traversed in a specific order (POT and OPOT). SSSS without order preservation requires 2 additions, 1 multiplication, 1 division per node participating in POT. Order preservation on top of that requires an additional XOR (or similar).
  *   Nested-encryption: Allows verification that a given set of nodes has been traversed in a specific order (POT and OPOT). The computational effort of nested encryption depends on the crypto algorithm chosen and typically higher than SSSS, i.e. it requires/benefits from hardware with specific capabilities (e.g. AES-NI).

Question:
Given that both approaches both solve the problem of POT and ordered POT, should we consider simplifying the draft and describe only a single approach? If so, which approach should we choose?
I.e. when taking the computational effort into account and the fact that options increase the burden for any implementor, we could decide to only describe the SSSS approach in the draft.

Thoughts? Opinions?

Many thanks, Frank

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 16 Dec 2018 15:52:41 -0500

<no hats>
Personally, the argument for just using SSSS, given that it now can 
provide ordered verification, seems quite persuasive to me.
Yours,
Joel
<hat floating back on slowly>

On 12/15/18 3:19 PM, Frank Brockners (fbrockne) wrote:
> During the SFC WG at IETF 103 in Bangkok we raised the question, whether 
> we could simplify the draft and choose a single algorithm for 
> proof-of-transit only (see also 
> https://datatracker.ietf.org/meeting/103/materials/minutes-103-sfc-01). 
> Given that we could not come to a conclusion, we decided to take the 
> discussion to the list.
> 
> Background:
> 
> draft-ietf-sfc-proof-of-transit-01 describes two different approaches: 
> “nested encryption” and “Shamir’s secret sharing scheme (SSSS)”. We 
> documented both approaches in the initial version of the draft, because 
> the two approaches had different qualities: While SSSS was 
> computationally cheaper (each node only needs to perform two additions, 
> a multiplication and a modulo-division), nested-encryption allowed to 
> verify that packets traversed a set of nodes in a particular order 
> (“ordered POT - OPOT”) – something that the SSSS-approach in the initial 
> version of the draft did not offer. With the changes discussed in IETF 
> 102 and now documented in draft-ietf-sfc-proof-of-transit-01, both 
> approaches offer order preservation.
> 
>   * SSSS: Allows verification that a given set of nodes has been
>     traversed in a specific order (POT and OPOT). SSSS without order
>     preservation requires 2 additions, 1 multiplication, 1 division per
>     node participating in POT. Order preservation on top of that
>     requires an additional XOR (or similar).
>   * Nested-encryption: Allows verification that a given set of nodes has
>     been traversed in a specific order (POT and OPOT). The computational
>     effort of nested encryption depends on the crypto algorithm chosen
>     and typically higher than SSSS, i.e.. it requires/benefits from
>     hardware with specific capabilities (e.g. AES-NI). 
> 
> Question:
> 
> Given that both approaches both solve the problem of POT and ordered 
> POT, should we consider simplifying the draft and describe only a single 
> approach? If so, which approach should we choose?
> 
> I.e. when taking the computational effort into account and the fact that 
> options increase the burden for any implementor, we could decide to only 
> describe the SSSS approach in the draft.
> 
> Thoughts? Opinions?
> 
> Many thanks, Frank
> 
> 
> 
> _______________________________________________
> sfc mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sfc
>

---

From: "Adrian Farrel" <[email-masked]>
Date: Thu, 20 Dec 2018 18:52:32 -0000

I think I agree with Joel on this point.

The nested encryption approach really did smell a bit :-) It was functional,
but a rather sad solution.

Since the 4S approach can now meet the requirement (that is quite important
in security applications of SFC) to show ordered proof of transit, I should
think the decision easy.

Cheers,
Adrian

-----Original Message-----
From: sfc <[email-masked]> On Behalf Of Joel M. Halpern
Sent: 16 December 2018 20:53
To: Frank Brockners (fbrockne) <[email-masked]>; [email-masked]
Subject: Re: [sfc] proof-of-transit: continue with both approaches, or
choose one?

<no hats>

On 12/15/18 3:19 PM, Frank Brockners (fbrockne) wrote:
> "nested encryption" and "Shamir's secret sharing scheme (SSSS)".. We 
> ("ordered POT - OPOT") - something that the SSSS-approach in the initial

---

From: "Diego R. Lopez" <[email-masked]>
Date: Thu, 20 Dec 2018 20:55:50 +0000

Hi,

I agree with Stephen and Joel. In fact, finding a "happier" solution for OPOT was what moved us to explore the ideas introduced in Montreal.

Be goode,

--
"Esta vez no fallaremos, Doctor Infierno"

Dr Diego R. Lopez
Telefonica I+D
https://www.linkedin.com/in/dr2lopez/

e-mail: [email-masked]
Tel:         +34 913 129 041
Mobile:  +34 682 051 091
----------------------------------

On 20/12/2018, 19:52, "sfc on behalf of Adrian Farrel" <[email-masked] on behalf of [email-masked]> wrote:

    Cheers,
    Adrian

    -----Original Message-----
    From: sfc <[email-masked]> On Behalf Of Joel M. Halpern
    Sent: 16 December 2018 20:53
    To: Frank Brockners (fbrockne) <[email-masked]>; [email-masked]
    Subject: Re: [sfc] proof-of-transit: continue with both approaches, or
    choose one?

    <no hats>

________________________________

Este mensaje y sus adjuntos se dirigen exclusivamente a su destinatario, puede contener información privilegiada o confidencial y es para uso exclusivo de la persona o entidad de destino. Si no es usted. el destinatario indicado, queda notificado de que la lectura, utilización, divulgación y/o copia sin autorización puede estar prohibida en virtud de la legislación vigente. Si ha recibido este mensaje por error, le rogamos que nos lo comunique inmediatamente por esta misma vía y proceda a su destrucción.

The information contained in this transmission is privileged and confidential information intended only for the use of the individual or entity named above. If the reader of this message is not the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this transmission in error, do not read it. Please immediately reply to the sender that you have received this communication in error and then delete it.

Esta mensagem e seus anexos se dirigem exclusivamente ao seu destinatário, pode conter informação privilegiada ou confidencial e é para uso exclusivo da pessoa ou entidade de destino. Se não é vossa senhoria o destinatário indicado, fica notificado de que a leitura, utilização, divulgação e/ou cópia sem autorização pode estar proibida em virtude da legislação vigente. Se recebeu esta mensagem por erro, rogamos-lhe que nos o comunique imediatamente por esta mesma via e proceda a sua destruição

---

From: "Diego R. Lopez" <[email-masked]>
Date: Thu, 20 Dec 2018 20:56:59 +0000

Aaargh, wrong Farrel! I agree with *Adrian* and Joel!!

Dr Diego R. Lopez
Telefonica I+D

On 20/12/2018, 21:55, "Diego R. Lopez" <[email-masked]> wrote:

    Hi,

    Be goode,

    Dr Diego R. Lopez
    Telefonica I+D

        Cheers,
        Adrian

        -----Original Message-----
        From: sfc <[email-masked]> On Behalf Of Joel M. Halpern
        Sent: 16 December 2018 20:53
        To: Frank Brockners (fbrockne) <[email-masked]>; [email-masked]
        Subject: Re: [sfc] proof-of-transit: continue with both approaches, or
        choose one?

        <no hats>

---

From: <[email-masked]>
Date: Fri, 21 Dec 2018 10:21:52 +0800 (CST)

I agree with Joel. Since SSSS already has mechanism to provide ordered verification requirment, only this one approach is enough.

Regards.

敖婷 Ting Ao

原始邮件

发件人：JoelM.Halpern <[email-masked]>
收件人：Frank Brockners (fbrockne) <[email-masked]>;[email-masked] <[email-masked]>;
日 期 ：2018年12月17日 04:53
主 题 ：Re: [sfc] proof-of-transit: continue with both approaches,or choose one?

<no hats>

On 12/15/18 3:19 PM, Frank Brockners (fbrockne) wrote:
> “nested encryption” and “Shamir’s secret sharing scheme (SSSS)”... We