Re: [CFRG] [Non-DoD Source] Re: Please review draft-ietf-drip-rid

["Gajcowski, Nicholas H" <[e-mail]>]

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 <[e-mail]> On Behalf Of Robert Moskowitz
Sent: Friday, September 17, 2021 1:32 PM
To: [e-mail]
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.

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 <[e-mail]<mailto:[e-mail]>> 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

--
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" <[e-mail]<mailto:[e-mail]> on behalf of [e-mail]<mailto:[e-mail]>> wrote:

    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

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



_______________________________________________

CFRG mailing list

[e-mail]<mailto:[e-mail]>

https://www.irtf.org/mailman/listinfo/cfrg