Subject: [Crypto-panel] Request for review of two erratas opened against RFC 8032 (EdDSA)

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Fri, 28 Jan 2022 09:19:46 +0300

Dear Crypto Review Panel experts,

We've received a request to have a closer look at two errata opened against
RFC 8032: https://www.rfc-editor.org/errata/eid5758,
https://www.rfc-editor.org/errata/eid5759.

Previously these two errata were rejected since no mistakes in the current
text of the draft had been found. At the same time, the two errata might
provide more effective ways for square-roots-mod-p.

We would like to ask a Crypto Panel expert (or two experts) to check the
proposed formulas, i.e., to verify that they are correct and more effective
(always or in a vast majority of cases).

Any volunteers?

Best regards,
Stanislav (for chairs)

---

From: Chloe Martindale <[email-masked]>
Date: Fri, 28 Jan 2022 11:22:56 +0000

Hi all,

I can take a look at this.

All the best,
Chloe

On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev <[email-masked]>
wrote:

> We've received a request to have a closer look at two errata opened
> against RFC 8032: https://www.rfc-editor.org/errata/eid5758,
> _______________________________________________
> Crypto-panel mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/crypto-panel
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Fri, 28 Jan 2022 14:31:40 +0300

Great, thanks a lot, Chloe!

Regards,
Stanislav

On Fri, 28 Jan 2022 at 14:23, Chloe Martindale <[email-masked]>
wrote:

>> Previously these two errata were rejected since no mistakes in the
>> current text of the draft had been found. At the same time, the two errata
>> might provide more effective ways for square-roots-mod-p.
>>

---

From: Thomas Pornin <[email-masked]>
Date: Fri, 28 Jan 2022 12:42:54 +0000

I will have a look too. This looks weird.

Thomas

From: Crypto-panel <[email-masked]> on behalf of Chloe Martindale <[email-masked]>
Date: Friday, January 28, 2022 at 06:24
To: "Stanislav V. Smyshlyaev" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: EXTERNAL: Re: [Crypto-panel] Request for review of two erratas opened against RFC 8032 (EdDSA)

Hi all,

All the best,
Chloe

On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev <[email-masked]<mailto:[email-masked]>> wrote:
Dear Crypto Review Panel experts,

We've received a request to have a closer look at two errata opened against RFC 8032: https://www.rfc-editor.org/errata/eid5758<https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5758&data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C9b6b47ddc1a347fdf79d08d9e25096d5%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789658780088689%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=1imcbOxH0OiY8d9m%2FjZaYvDNHNQb%2BETEBLkvt5WFd6A%3D&reserved=0>, https://www.rfc-editor.org/errata/eid5759<https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5759&data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C9b6b47ddc1a347fdf79d08d9e25096d5%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789658780088689%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=5jFY5LzH2kM7nk7PiHjm4EHljh9H9rjwEP7QlJUVArU%3D&reserved=0>.

Previously these two errata were rejected since no mistakes in the current text of the draft had been found. At the same time, the two errata might provide more effective ways for square-roots-mod-p.

We would like to ask a Crypto Panel expert (or two experts) to check the proposed formulas, i.e., to verify that they are correct and more effective (always or in a vast majority of cases).

Any volunteers?

Best regards,
Stanislav (for chairs)
_______________________________________________
Crypto-panel mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/crypto-panel<https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C9b6b47ddc1a347fdf79d08d9e25096d5%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789658780088689%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=8jrHBbaCOeaV2NL%2F6JxGiV%2F2X2fqK0oazTtbEtCXsoU%3D&reserved=0>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Fri, 28 Jan 2022 15:45:09 +0300

Thank you, Thomas!

Regards,
Stanislav

On Fri, 28 Jan 2022 at 15:43, Thomas Pornin <thomas.pornin=
[email-masked]> wrote:

> *From: *Crypto-panel <[email-masked]> on behalf of Chloe
> Martindale <[email-masked]>
> *Date: *Friday, January 28, 2022 at 06:24
> *To: *"Stanislav V. Smyshlyaev" <[email-masked]>
> *Cc: *"[email-masked]" <[email-masked]>, "
> [email-masked]" <[email-masked]>
> *Subject: *EXTERNAL: Re: [Crypto-panel] Request for review of two erratas
> opened against RFC 8032 (EdDSA)
>
>
>
> Hi all,
>
>
>
> against RFC 8032: https://www.rfc-editor.org/errata/eid5758
> <https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5758&data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C9b6b47ddc1a347fdf79d08d9e25096d5%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789658780088689%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=1imcbOxH0OiY8d9m%2FjZaYvDNHNQb%2BETEBLkvt5WFd6A%3D&reserved=0>,
> https://www.rfc-editor.org/errata/eid5759
> <https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5759&data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C9b6b47ddc1a347fdf79d08d9e25096d5%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789658780088689%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=5jFY5LzH2kM7nk7PiHjm4EHljh9H9rjwEP7QlJUVArU%3D&reserved=0>
> .
>
>
>
> <https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C9b6b47ddc1a347fdf79d08d9e25096d5%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789658780088689%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=8jrHBbaCOeaV2NL%2F6JxGiV%2F2X2fqK0oazTtbEtCXsoU%3D&reserved=0>
>

---

From: Thomas Pornin <[email-masked]>
Date: Fri, 28 Jan 2022 13:42:37 +0000

OK, the proposed formulas are correct. The original formulas were correct, too.

For p = 2^255-19: given u and v in the field, then:
v*x^2 = v*(u*(u*v)^((p-5)/8))^2 = v*(u^2)*(u^((p-5)/4))*(v^((p-5)/4)) = u * (u^((p-1)/4) * v^((p-1)/4))
If u/v is a square (and u != 0, v != 0) then u^((p-1)/2) * v^((p-1)/2) = 1 (i.e. both u and v are squares, or both u and v are non-squares).
(u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) * v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 = u or -u. In both cases, this leads to a square root of (u/v) by applying step 3 of RFC 8032 section 5.1.3: if we got x such that v*x^2 = u, then x is a square root of u/v; if x is such that v*x^2 = -u, then x*i is a square root of u/v, using i = sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), and it is indeed a square root of -1).
Thus, the proposed formula, inserted in the RFC text, indeed yields a square root of u/v if it exists. It does not necessarily yield the same square root as the original formula, but that does not matter since step 4 of the decoding process normalizes the solution using the least significant bit.
Note that step 3 of section 5.1.3 includes explicitly checking that v*x^2 = u or -u, and if u/v is not a square then there cannot be a x value that matches that test; thus, the new formula does not incorrectly return a value for a non-square u/v.

For p = 2^448 - 2^224 - 1, it is slightly simpler:
v*x^2 = v*(u*(u*v)^((p-3)/4))^2 = u * (u^((p-1)/2) * v^((p-1)/2)
If u/v is a square then u^((p-1)/2) * v^((p-1)/2) = 1 (see above), hence v*x^2 = u and x is necessarily a solution. Again, this is tested explicitly (step 3 of section 5.2.3) so there is no risk of incorrectly accepting a non-square.

As noted above, the normalizing step means that it makes no difference which of the two square roots you get, at least in the context of RFC 8032. I think it has some slight impact in another context, where the exact choice of the square root can help simplify a formula, but my memory is a bit hazy here. This may be related to the fact that, with p = 2^448 - 2^224 - 1, exactly one of the two square roots of u/v is itself a square, and the original RFC formula always returns that one, while the proposed formula may return the square root which is a non-square; again, this does not matter in the case of RFC 8032.

Thomas

From: Crypto-panel <[email-masked]> on behalf of "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Friday, January 28, 2022 at 07:45
To: Thomas Pornin <thomas.pornin=[email-masked]>
Cc: Chloe Martindale <[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two erratas opened against RFC 8032 (EdDSA)

Thank you, Thomas!

Regards,
Stanislav

On Fri, 28 Jan 2022 at 15:43, Thomas Pornin <thomas.pornin=[email-masked]> wrote:
I will have a look too. This looks weird.
 
Thomas

Hi all,

All the best,
Chloe
 
On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev <[email-masked]> wrote:
Dear Crypto Review Panel experts,
 
We've received a request to have a closer look at two errata opened against RFC 8032: https://www.rfc-editor.org/errata/eid5758, https://www.rfc-editor.org/errata/eid5759. 

 
Any volunteers?
 
Best regards,
Stanislav (for chairs)

---

From: Thomas Pornin <[email-masked]>
Date: Fri, 28 Jan 2022 13:48:39 +0000

As for efficiency, the gain is slight. The modular exponentiation (with exponent (p-5)/8) costs at least 250 squarings, and an extra dozen multiplications. The proposed formula saves two squarings and three multiplications, i.e. we are talking about an improvement of less than 2%. Nothing ground-breaking here.

Thomas

On 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Pornin" <[email-masked] on behalf of thomas.pornin=[email-masked]> wrote:

    Thomas

    Thank you, Thomas!

    Regards,
    Stanislav

    Thomas

    Hi all,

    All the best,
    Chloe

    We've received a request to have a closer look at two errata opened against RFC 8032: https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5758&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=k49Gr2WuYIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&amp;reserved=0, https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5759&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=B6QR5Z50rB0Vz3XkgFEtteBSLLL7iV1qFjiRWu8LyfE%3D&amp;reserved=0. 

    Any volunteers?

    Best regards,
    Stanislav (for chairs)
    _______________________________________________
    Crypto-panel mailing list
    [email-masked]
    https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=GEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=0
    _______________________________________________
    Crypto-panel mailing list
    [email-masked]
    https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=GEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=0

    _______________________________________________
    Crypto-panel mailing list
    [email-masked]
    https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=GEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=0