Subject: [CFRG] Please review draft-ietf-drip-rid

From: Robert Moskowitz <[email-masked]>
Date: Tue, 14 Sep 2021 16:25:10 -0400

Dear cfrg:

I am doing some interesting things with hashing in draft-ietf-drip-rid, 
and I have been instructed to get feedback from CFRGers.

A little background:

The various Civil Aviation Authorities (e.g. FAA) around the world are 
regulating the requirement that Unmanned Aircraft (AKA drones) broadcast 
their Identity (Remote Identification of Unmanned Aircraft) that can 
then be used to learn more about the UA.  ASTM International has 
published a specification, F3411-19, that is the reference document for 
UA manufacturers to meet these regulatory requirements.  Thing is what 
is in F3411-19 is a non-provable claim and open to misuse.

In IETF DRIP, we are defining a Trustable Device Entity Tag (DET) based 
on the Host Identity Tag in RFC 7401 by adding an entity hierarchical 
registry making a Hierarchical Host Identity Tag (HHIT).  This DET will 
be included as an option in the upcoming revision to F3411.  A 
manufacturer does not have to use a provable ID, but here is one way of 
doing it...

Remote IDs are broadcast over:  Bluetooth 4 or 5 or Wifi BEACONs or 
NAN.  The messages for WiFi and BT 5 are 250 bytes, but BT4 limits it to 
25 bytes!  The actual ID in F3411 is limited to 20 bytes.  In 
draft-ietf-drip-rid we define a Trustable Remote ID of 16 bytes which is 
a valid, non-routable IPv6 address.  In draft-ietf-drip-auth we define 
how to authenticate ownership of our DET within the 250 byte message 
limit or 9 chained BT4 messages (chaining of BT4 messages supported in 
F3411).

Here I am only asking for a review of draft-ietf-drip-rid.  We will get 
to draft-ietf-drip-auth later!  But looking at it will help fill in some 
whys.

Now on to the actual review request:

DETs are constructed by hashing a public ED25519 Host Identity with 
other information (see sec 3) using cSHAKE128.  A python script to 
create HHITs is available (see Informative Ref hhit-gen).

In most uses the actual hash size is 64 bytes.  Per Appendix C, the 
probablity of a collision is .01% in a population of 66M and 1% in a 
population of 663M.  We have a script that we will be making available 
that we ran to 1M HHITs and did not produce a collision. This script 
will be posted on github with its next version (right now it is 3 
separate scripts).

First level review is how I am creating this Cyptographically Generated 
Address.  Second is my math correct on the probablity of collisions.

It is expected that each DET registrar will protect against the 
registration of duplicate DETs (draft draft-wiethuechter-drip-registries 
is really drafty) so only one UA will be able to register a specific 
public ED25519 Host Identity and DET with that DET registrar.

Note that a UA may register a new DET for each "operation" (e.g. for 
each FEDEx delivery flight or 'only' one per day per UA), so a DET 
registrar could run through a LOT of DETs and could easily be rejecting 
a registration attempt as a duplicate.

The next concern is that of pre-image attacks against the hashing. I 
have not found any literature on this.  What is the risk?  How 'easy' is 
it to do with a hash of 64 bits.  I have text on this in the Security 
Considerations section.  This this adequate?  Is more information 
available that I can incude here?

I do not talk at all about the risk of multiple private keys for a 
public ED25519 key.  Do I need to include this?  I ASSuME that given the 
signature from draft-ietf-drip-auth and the public key, the receiver can 
trust the sender.

So that is pretty much it on request of CFRG to review 
draft-ietf-drip-rid.  DET privacy stuff (sec 8) I will take to SAAG.

I am looking forward to your responses.  I will be back to you on 
drip-auth when it is a little closer to done.  Though feel free to 
advise on it to.

Thank you

Robert Moskowitz

---

From: Watson Ladd <[email-masked]>
Date: Fri, 17 Sep 2021 06:58:32 -0700

I've read your email and have only one response.

Why?

There is enough room for an entire certificate chain using Ed25519 and
compact encodings. That would be a lot simpler.

Sincerely,
Watson Ladd

--
Astra mortemque praestare gradatim

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 17 Sep 2021 14:20:57 +0000

I have not read the draft, but my answer to Watson is - because there is not enough room for Post-Quantum certificates, and Ed25519 is not an acceptable alternative for some of us.

--
Regards,
Uri
 
There are two ways to design a system. One is to make is so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                     -  C. A. R. Hoare

On 9/17/21, 09:59, "CFRG on behalf of Watson Ladd" <[email-masked] on behalf of [email-masked]> wrote:

    Why?

    Sincerely,
    Watson Ladd

    _______________________________________________
    CFRG mailing list
    [email-masked]
    https://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Fri, 17 Sep 2021 07:24:07 -0700

> I have not read the draft, but my answer to Watson is - because there is not enough room for Post-Quantum certificates, and Ed25519 is not an acceptable alternative for some of us.

ECDSA takes the same place, and unless I'm missing something this
scheme isn't post-quantum either. In fact this proposal can only use
Ed25519 unless I'm misreading it.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 17 Sep 2021 14:33:30 +0000

On 9/17/21, 10:25, "Watson Ladd" <[email-masked]> wrote:

    On Fri, Sep 17, 2021 at 7:21 AM Blumenthal, Uri - 0553 - MITLL
    <[email-masked]> wrote:
    >>
    >> I have not read the draft, but my answer to Watson is - because
    >> there is not enough room for Post-Quantum certificates, and Ed25519
    >> is not an acceptable alternative for some of us.
    >
    > ECDSA takes the same place,

And, unfortunately, is equally unacceptable.

    > and unless I'm missing something this scheme isn't post-quantum either.
    > In fact, this proposal can only use d25519 unless I'm misreading it.

If that's true - my comment/answer does not apply.

Thanks!

---

From: Michael Scott <[email-masked]>
Date: Fri, 17 Sep 2021 16:34:59 +0100

On Fri, Sep 17, 2021 at 3:21 PM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> I have not read the draft, but my answer to Watson is - because there is
> not enough room for Post-Quantum certificates, and Ed25519 is not an
> acceptable alternative for some of us.
>
>
I for one would be interested in just how extensive this "some of us" group
is. In the interests of transparency I think they should step forward and
identify themselves. It is a view I respect, but personally disagree with.

If people in good faith are willing to make major efforts to put forward
proposals to this forum, it would only be fair for them to be aware of the
extent of that grouping who would reject such proposals out-of-hand.

Mike

> On 9/17/21, 09:59, "CFRG on behalf of Watson Ladd" <[email-masked]
> on behalf of [email-masked]> wrote:
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 17 Sep 2021 15:56:01 +0000

On Fri, Sep 17, 2021 at 3:21 PM Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:

I for one would be interested in just how extensive this "some of us" group is. In the interests of transparency I think they should step forward and identify themselves. It is a view I respect, but personally disagree with.

While we both understand that I am not a spokesman for such a group, as nobody appointed or authorized me to do so – IMHO, this group would include all the US Government, all the vendors who sell to US Government, and probably same contingent for other countries.

If people in good faith are willing to make major efforts to put forward proposals to this forum, it would only be fair for them to be aware of the extent of that grouping who would reject such proposals out-of-hand. 

Sure. Though be aware that only a tiny fraction of the above appears present here, and I can’t speak even for them.

Also, please consider that from the common-sense point of view, if the security concern I expressed is valid – the number of people or organizations who share it is irrelevant. So far, there has been no way to either prove or disprove convincingly this concern. And we’ve been erring on the side of caution pretty much everywhere else – so, why not here?

 

    Why?

    Sincerely,
    Watson Ladd

---

From: Robert Moskowitz <[email-masked]>
Date: Fri, 17 Sep 2021 13:31:45 -0400

I am not aware of any PQ signature that will work here and accepted for 
production systems.  So I continue to work with pre-PQ so vendors can 
make hardware today to meet their 2023 mandate to support these rules.  
That means manufacturing soon.  The manufacturers are very unhappy on 
how long it is taking ASTM to finish the revision and get FAA approval 
of the Memorandum Of Compliance.  And we in DRIP will have to do an 
addendum to the ASTM MoC for our contribution.

So please keep the discuss is:

Do I use EdDSA properly?
Is my use of cSHAKE right?
What are the collision and pre-image attacks.  Is there more that I 
should reference.

On 9/17/21 11:34 AM, Michael Scott wrote:
>
> On Fri, Sep 17, 2021 at 3:21 PM Blumenthal, Uri - 0553 - MITLL 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     there is not enough room for Post-Quantum certificates, and
>     Ed25519 is not an acceptable alternative for some of us.
>
>
> I for one would be interested in just how extensive this "some of us" 
> group is. In the interests of transparency I think they should step 
> forward and identify themselves. It is a view I respect, but 
> personally disagree with.
>
> If people in good faith are willing to make major efforts to put 
> forward proposals to this forum, it would only be fair for them to be 
> aware of the extent of that grouping who would reject such proposals 
> out-of-hand.
>
> Mike
>
>     --
>     Regards,
>     Uri
>
>     On 9/17/21, 09:59, "CFRG on behalf of Watson Ladd"
>     <[email-masked] <mailto:[email-masked]> on behalf of
>     [email-masked] <mailto:[email-masked]>> wrote:
>
>     [email-masked] <mailto:[email-masked]>
>     <https://www.irtf.org/mailman/listinfo/cfrg>
>     [email-masked] <mailto:[email-masked]>
>     <https://www.irtf.org/mailman/listinfo/cfrg>
>
>

---

From: Robert Moskowitz <[email-masked]>
Date: Fri, 17 Sep 2021 13:33:38 -0400

Watson,

There is more than just a cert chain.  I have looked into this approach 
at the beginning and ruled it out.  If you wish to discuss this further, 
I am open to doing that, if nothing more than checking that I did make 
an informed choice.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 17 Sep 2021 17:35:59 +0000

I am not aware of any PQ signature that will work here and accepted for production systems.  

That I can’t comment on – except that among the NIST PQC candidates, Falcon seems both fast enough and “compact” enough, offering smallest key- and signature-size (small as PQ goes 😉).

So, I continue to work with pre-PQ so vendors can make hardware today to meet their 2023 mandate to support these rules.  That means manufacturing soon. 

Sure. You know your use case better.

Mike

--
Regards,
Uri

    Why?

    Sincerely,
    Watson Ladd

---

From: Robert Moskowitz <[email-masked]>
Date: Fri, 17 Sep 2021 13:44:32 -0400

On 9/17/21 1:35 PM, Blumenthal, Uri - 0553 - MITLL wrote:
> That I can’t comment on – except that among the NIST PQC candidates, 
> Falcon seems both fast enough and “compact” enough, offering smallest 
> key- and signature-size (small as PQ goes 😉).
>

I will keep an 'eye' on it.  But I can only propose something is 
'standardized'.

Otherwise I would be using a Xoodyak equiv to cSHAKE!

> So, I continue to work with pre-PQ so vendors can make hardware today 
> to meet their 2023 mandate to support these rules.  That means 
> manufacturing soon.
>

As often the case, by the time things reach this point a lot of water 
has flowed under the bridge.

I am on the ASTM call right now, but the debate is on RF attenna 
location to meet coverage pattern.  Not a component that I can contrbute 
on, but REALLY important to the FAA.

>         I have not read the draft, but my answer to Watson is -
>         because there is not enough room for Post-Quantum
>         certificates, and Ed25519 is not an acceptable alternative for
>         some of us.
>
>     I for one would be interested in just how extensive this "some of
>     us" group is. In the interests of transparency I think they should
>     step forward and identify themselves. It is a view I respect, but
>     forward proposals to this forum, it would only be fair for them to
>     be aware of the extent of that grouping who would reject such
>     proposals out-of-hand.
>
>     Mike
>
>         --
>         Regards,
>         Uri
>
>         There are two ways to design a system. One is to make is so
>         simple there are obviously no deficiencies.
>         <[email-masked] <mailto:[email-masked]> on
>         behalf of [email-masked]
>         <mailto:[email-masked]>> wrote:
>
>     https://www.irtf.org/mailman/listinfo/cfrg  <https://www.irtf.org/mailman/listinfo/cfrg>
>
>
>
>

---

From: "Riad S. Wahby" <[email-masked]>
Date: Fri, 17 Sep 2021 14:41:14 -0400

Hello Uri,

As I've said privately, I appreciate your position even though
I disagree with it. But this thread seems to be going in a slightly
concerning direction:

"Blumenthal, Uri - 0553 - MITLL" <[email-masked]> wrote:
> While we both understand that I am not a spokesman for such a group,
> as nobody appointed or authorized me to do so – IMHO, this group
> would include all the US Government, all the vendors who sell
> to US Government, and probably same contingent for other countries.

The "some of us" context here was "Ed25519 is not acceptable".

Broadening this to include morally equivalent (PQ-wise) cryptography
(e.g., the NIST curves, ECDSA, ...), it seems pretty clear that the
official position of the US Government is that such cryptosystems
*are* acceptable. After all, they are in-use and recommended.

Perhaps once the current NIST competition concludes we will see a quick
shift to PQ cryptosystems as sole recommendations. But I doubt this
very much: experience tells us that breaking newly deployed and
not-yet-well-understood cryptosystems is much easier than building
crypto-threatening quantum computers.

So: I do not think it is correct to claim the USG and its subsidiaries
as ideological allies here.

But I'm not sure this matters much either way, because:

> Mike Scott wrote:
> Sure. Though be aware that only a tiny fraction of the above appears
> present here, and I can’t speak even for them.

With respect, this appears to be non sequitur. The question was how
many people would be likely to shoot down new non-PQ proposals:

>> forward proposals to this forum, it would only be fair for them
>> to be aware of the extent of that grouping who would reject such
>> proposals out-of-hand.

From that perspective, the only relevant people are those who participate
or who are likely to participate in discussing those proposals.

> Also, please consider that from the common-sense point of view,
> if the security concern I expressed is valid – the number of people
> or organizations who share it is irrelevant. So far, there has been
> no way to either prove or disprove convincingly this concern. And
> we’ve been erring on the side of caution pretty much everywhere
> else – so, why not here?

This argument does not seem productive: essentially all cryptography
is based on hardness assumptions that have not been proved or disproved
(and, given our current knowledge, seem unlikely to be). If we accept
the above argument, the logical conclusion seems to be "disband CFRG".

Cheers,

-=rsw

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 17 Sep 2021 19:10:56 +0000

>    *are* acceptable. After all, they are in-use and recommended.

Acceptable as *new* designs? I'm not a spokesman for the US Government, but I doubt that. For reasons listed below. 

Acceptable as part of "sustainment"? E.g., a new email client that does good old RSA-based S/MIME? Very likely yes - but that's not what CFRG does, is it?

>    crypto-threatening quantum computers.

Well, none of us can build a crypto-threatening quantum computer yet, I agree. Can you break, e.g., SABER (if it's that much easier ;)?

Once NIST PQC publishes its first PQ standards (Jan 2022), we'll see if recommendations change then.

>    as ideological allies here.

I cannot claim anybody as "ideological allies". I'm appealing to the common sense here. 

Designing and standardizing a new protocol takes time. So does creating commercial implementation(s) - once the protocol is reasonably stable. Once there is a product, it needs to gain some market share. Again, time.

>From the time this is done, and until the time some other (e.g., quantum) technology or science makes this product obsolete and vulnerable - is the actual "useful lifetime" of this "new thing". And I'm saying that investing in something that may have only a few years of "useful lifetime" is not worth it.

Question to all: I understand it's fun to design new things, and it's fun to publish something - but how long should the *expected* "useful lifetime" of "it" be for the effort to actually make sense (and bring benefits other than adding to a list of pubs)?

My personal experience - recently came up with a new protocol (details are irrelevant here, and not of interest to the wide audience), and was asked to make sure it is quantum-resistant. 

>    .  .  .  .  .

You equate "make new designs quantum-resistant" with "let's disband CFRG"??? Hmm...

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 17 Sep 2021 13:58:25 -0700

On 17 Sep 2021, at 12:10, Blumenthal, Uri - 0553 - MITLL wrote:

> Acceptable as *new* designs? I'm not a spokesman for the US 
> Government, but I doubt that.

Then you seem to be doubting the NSA FAQ on quantum computing and 
cryptanalysis. 
https://media.defense.gov/2021/Aug/04/2002821837/-1/-1/1/Quantum_FAQs_20210804.PDF

> if recommendations change then.

This assumes that they are "standards", yet NIST has waffled mightily 
about what the next step will be, particularly about authentication 
mechanisms.

Maybe we can cut this thread here? If any of us are not a spokesperson 
for $ZZgovt, we should not immediately follow such statements with 
suppositions about what $ZZgovt will do. Let's let them do that and then 
we can respond.

--Paul Hoffman

---

From: Robert Moskowitz <[email-masked]>
Date: Fri, 17 Sep 2021 17:19:51 -0400

And just respond to the requested review of what I think is the best I 
can do within the RF constraints and currently available cryptography.

Thank you.

On 9/17/21 4:58 PM, Paul Hoffman wrote:
> suppositions about what $ZZgovt will do. Let's let them do that and 
> then we can respond.
>
> --Paul Hoffman
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 17 Sep 2021 21:28:47 +0000

>    > Acceptable as *new* designs? I'm not a spokesman for the US 

>    > Government, but I doubt that.

>    https://media.defense.gov/2021/Aug/04/2002821837/-1/-1/1/Quantum_FAQs_20210804.PDF

Thanks for bringing this up - I wasn't aware of a fresh update (Aug 2021, wow!).

However, what I find there seems to support what I've been saying:

Q: What about new elliptic curves and associated algorithms?

A: Given the transition time required for most government programs to integrate new cryptography; the large established base of existing solutions; the desire to preserve interoperability with existing systems; and the expected standardization of post-quantum algorithms, NSA does not anticipate including additional algorithms or parameter selections in the CNSA Suite.

. . .

Q: When will CNSA be updated to quantum-resistant algorithms?

A: The intention is to update CNSA to remove quantum-vulnerable algorithms and replace them with a subset of the quantum-resistant algorithms selected by NIST at the end of the third round of the NIST post-quantum effort – NIST determines the timeline for each round. See the Future Cryptography section of this FAQ for more information.

>    > Once NIST PQC publishes its first PQ standards (Jan 2022), we'll see 

>    > if recommendations change then.

>    mechanisms.

NIST promised to set the standards by Jan 2022. That set will include KEM (probably more than one), and Signature (authentication ;) - again, probably more than one. Whatever *subsequent* standards may come out of PQC, according to NIST, will *augment* rather than replace the 3rd-round selection. 

>    we can respond.

OK, sure, I agree. (But couldn't refuse myself the pleasure of the last word in this sub-thread. 😉)

---

From: "Riad S. Wahby" <[email-masked]>
Date: Fri, 17 Sep 2021 17:56:21 -0400

Hello Uri,

(Changed the subject line since we're pretty off-topic here.)

It seems silly for us to go back and forth point-by-point, especially
since most of our specific disagreements are minor and definitional.

    (e.g., What does CFRG do? Depends who you ask. From a research
    cryptographer's point of view the things we're documenting right
    now---pairing-friendly curves, hashing to curves, etc.---are
    roughly the same vintage as S/MIME!)

    (e.g., is USG making new quantum-susceptible standards? Well,
    should we count NIST's adding Ed25519 to FIPS-186?)

The high-level question is whether CFRG should act as if it's all but
certain that crypto-threatening quantum computers will exist in the
next few years. I think no; reasonable people can certainly disagree.
But let's try to avoid spitting contests. We will win by reaching
consensus, not by saying the cleverest things.

In that vein:

> You equate "make new designs quantum-resistant" with "let's disband CFRG"??? Hmm...

The argument was: "there is no way to prove or disprove convincingly
this [security] concern", in the context of constructing crypto-threatening
quantum computers, implies "make all new designs quantum-resistant."

The point is, this doesn't go nearly far enough: "there is no way
to prove or disprove convincingly this [security] concern", in the
context of cryptography more broadly (and given prevailing beliefs
vis-a-vis complexity theory), implies "give up".

But we both agree that's absurd. So maybe we should rethink the premise
here.

Cheers,

-=rsw

---

From: Soatok Dreamseeker <[email-masked]>
Date: Fri, 17 Sep 2021 18:16:38 -0400

> But we both agree that's absurd. So maybe we should rethink the premise

I'm agnostic to the threat of quantum computers. My stance is simply:
Design for the threat model you have, not the one you're worried about
having in 10 years. If you're worried about having to migrate to new
cryptography, ever, you should build versioning into whatever you're
building, so you can migrate when your threat model evolves. This is true
even if practical quantum computers somehow turn out to be impossible.

Thus, there's not much value in such speculation.

---

From: Dan Harkins <[email-masked]>
Date: Fri, 17 Sep 2021 15:34:32 -0700

"What does CFRG do?"

   In my view it bridges the gap between the academic paper and
the protocol implementation. Its a crucial role that exists
regardless of whether the crypto is QC-susceptible or not.

   Dan.

-- 
"The object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." -- Marcus Aurelius

---

From: Russ Housley <[email-masked]>
Date: Fri, 17 Sep 2021 19:01:17 -0400

> On Sep 17, 2021, at 6:16 PM, Soatok Dreamseeker <[email-masked]> wrote:
> 
> I'm agnostic to the threat of quantum computers. My stance is simply: Design for the threat model you have, not the one you're worried about having in 10 years. If you're worried about having to migrate to new cryptography, ever, you should build versioning into whatever you're building, so you can migrate when your threat model evolves. This is true even if practical quantum computers somehow turn out to be impossible.

W have alway needed to transition to new hash functions, bigger key sizes, wider block ciphers, and so on.  Thus, versioning is always needed.

Russ

---

From: "Gajcowski, Nicholas H" <[email-masked]>
Date: Thu, 23 Sep 2021 17:15:48 +0000

Concerning pre-image resistance, the threat as I understand is that someone can create a separate Host Identity, i.e., EdDSA public key, that produces an already taken HHIT, i.e, satisfies a 64-bit condition on the output of cSHAKE128( static data || public key ).  The way to do this would be through brute force, i.e., compute private, public EdDSA key pairs until you find one with the desired cSHAKE128 output.  This should take about 2^64 attempts.  To get an idea of how hard this would be, consider that a *single* bitcoin mining ASIC can do on the order of 2^46 sha256 hashes a second or about 2^62 hashes in a single day. (Also, note there are DES crackers available that will exhaust the space of 2^56 keys).  The point being, 2^64 is not prohibitive esp. as this can be done in parallel.

To address this shortcoming, RFC 3972 includes a hardening function that ups the cost of finding a pre-image by increasing the number of hashes needed to create a CGA. However, this has obvious limitations as it increases the cost of creating a CGA by the same factor it increases the cost of stealing a CGA.  A better tradeoff is to increase the number of bits taken from the hash such as the 96 bits used in ORCHIDv2.

Now it should be noted that the 2^64 attempts is for stealing a *specific* HHIT/CGA. As noted in the case of CGAs (RFC 3972),stealing *a* CGA with the same prefix out of many becomes commensurately cheaper and so that applies here.  Say there are roughly 1,024 such possible HHITs for which you'd be happy stealing any one of.  Then rather trying to satisfy a 64-bit condition on the cSHAKE128 output, you need only satisfy a 54-bit condition (since you have 2^10 more opportunities for success).

In the end, I suspect this boils down to not to whether it's feasible to find a 64 bit preimage, but rather how expensive you want to make it.

As for collisions of the CGA, I'm not sure what that buys an attacker as the threat model is unclear.  I suppose an attacker will then have two UAs with the same CGA with one being legitimate/registered.  Unclear how that is better than simply having the two use the same public key/HOST_ID unless perhaps you want to retain some form of deniability.

Nick G

From: CFRG <[email-masked]> On Behalf Of Robert Moskowitz
Sent: Friday, September 17, 2021 1:32 PM
To: [email-masked]
Subject: [Non-DoD Source] Re: [CFRG] Please review draft-ietf-drip-rid

I am not aware of any PQ signature that will work here and accepted for production systems.  So I continue to work with pre-PQ so vendors can make hardware today to meet their 2023 mandate to support these rules.  That means manufacturing soon.  The manufacturers are very unhappy on how long it is taking ASTM to finish the revision and get FAA approval of the Memorandum Of Compliance.  And we in DRIP will have to do an addendum to the ASTM MoC for our contribution.

Do I use EdDSA properly?
Is my use of cSHAKE right?
What are the collision and pre-image attacks.  Is there more that I should reference.

On Fri, Sep 17, 2021 at 3:21 PM Blumenthal, Uri - 0553 - MITLL <[email-masked]<mailto:[email-masked]>> wrote:
I have not read the draft, but my answer to Watson is - because there is not enough room for Post-Quantum certificates, and Ed25519 is not an acceptable alternative for some of us.

Mike

--
Regards,
Uri

On 9/17/21, 09:59, "CFRG on behalf of Watson Ladd" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

    Why?

    Sincerely,
    Watson Ladd

    _______________________________________________
    CFRG mailing list
    [email-masked]<mailto:[email-masked]>
    https://www.irtf.org/mailman/listinfo/cfrg
_______________________________________________
CFRG mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

CFRG mailing list

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

---

From: Robert Moskowitz <[email-masked]>
Date: Fri, 24 Sep 2021 09:47:19 -0400

Nick,

Thank you for this analysis.  I will incorporate it in the Security 
Considerations of the next version.

It points to the importance of validating the self-attestion with the 
public key in the online registry or receiving the offline 
self-attestion and validating the Registry (HDA) public key from cache.  
See Appendix B and draft=-ietf-drip-auth.

Determined adversaries CAN produce an EdDSA that duplicates an HHIT, but 
not yet produce the private key for a published EdDSA public key.

It would be nice to have more bits in the hash component, but then I 
loose the feature of using the HHIT as a non-routable IPv6 address. 
Don't think I want to go that way.  There are already apps in devlopment 
that use this.

On 9/23/21 1:15 PM, Gajcowski, Nicholas H wrote:
>
> Concerning pre-image resistance, the threat as I understand is that 
> someone can create a separate Host Identity, i.e., EdDSA public key, 
> that produces an already taken HHIT, i.e, satisfies a 64-bit condition 
> on the output of cSHAKE128( static data || public key ).  The way to 
> do this would be through brute force, i.e., compute private, public 
> EdDSA key pairs until you find one with the desired cSHAKE128 output. 
> This should take about 2^64 attempts.  To get an idea of how hard this 
> would be, consider that a *single* bitcoin mining ASIC can do on the 
> order of 2^46 sha256 hashes a second or about 2^62 hashes in a single 
> day. (Also, note there are DES crackers available that will exhaust 
> the space of 2^56 keys).  The point being, 2^64 is not prohibitive 
> esp. as this can be done in parallel.
>
> To address this shortcoming, RFC 3972 includes a hardening function 
> that ups the cost of finding a pre-image by increasing the number of 
> hashes needed to create a CGA. However, this has obvious limitations 
> as it increases the cost of creating a CGA by the same factor it 
> increases the cost of stealing a CGA.  A better tradeoff is to 
> increase the number of bits taken from the hash such as the 96 bits 
> used in ORCHIDv2.
>
> Now it should be noted that the 2^64 attempts is for stealing a 
> *specific* HHIT/CGA. As noted in the case of CGAs (RFC 3972),stealing 
> *a* CGA with the same prefix out of many becomes commensurately 
> cheaper and so that applies here. Say there are roughly 1,024 such 
> possible HHITs for which you'd be happy stealing any one of.  Then 
> rather trying to satisfy a 64-bit condition on the cSHAKE128 output, 
> you need only satisfy a 54-bit condition (since you have 2^10 more 
> opportunities for success).
>
> In the end, I suspect this boils down to not to whether it's feasible 
> to find a 64 bit preimage, but rather how expensive you want to make it.
>
> As for collisions of the CGA, I'm not sure what that buys an attacker 
> as the threat model is unclear.  I suppose an attacker will then have 
> two UAs with the same CGA with one being legitimate/registered.  
> Unclear how that is better than simply having the two use the same 
> public key/HOST_ID unless perhaps you want to retain some form of 
> deniability.
>
> Nick G
>
> *From:*CFRG <[email-masked]> *On Behalf Of *Robert Moskowitz
> *Sent:* Friday, September 17, 2021 1:32 PM
> *To:* [email-masked]
> *Subject:* [Non-DoD Source] Re: [CFRG] Please review draft-ietf-drip-rid
>
> I am not aware of any PQ signature that will work here and accepted 
> for production systems.  So I continue to work with pre-PQ so vendors 
> can make hardware today to meet their 2023 mandate to support these 
> rules.  That means manufacturing soon.  The manufacturers are very 
> unhappy on how long it is taking ASTM to finish the revision and get 
> FAA approval of the Memorandum Of Compliance.  And we in DRIP will 
> have to do an addendum to the ASTM MoC for our contribution.
>