Subject: [Cfrg] Degenerate curve attack

From: Dan Brown <[email-masked]>
Date: Tue, 29 Dec 2015 14:38:47 +0000

http://eprint.iacr.org/2015/1233

Relevant to CFRG new curve draft? (Not following draft details closely enough to know answer, further excuse being vacation.)

Gist of paper is new reason to need public key validation.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 29 Dec 2015 10:23:06 -0500

The Curve25519 and Ed448 functions are designed to accept all byte
strings of the correct length and operate on them safely. Nothing in
this paper contradicts that.

On Tue, Dec 29, 2015 at 9:38 AM, Dan Brown <[email-masked]> wrote:
> Relevant to CFRG new curve draft? (Not following draft details closely
> enough to know answer, further excuse being vacation.)
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 29 Dec 2015 17:43:55 +0200

On Tue, Dec 29, 2015 at 02:38:47PM +0000, Dan Brown wrote:
> Relevant to CFRG new curve draft? (Not following draft details
> closely enough to know answer, further excuse being vacation.)
> 

Well, I did briefly look at wrong square roots (which arise in
careless point decompression) in context of Edwards curves a while
back and noticed that if wrong square root is 0 (one algorithm for
computing square roots mod 8k+5 can give those), the scalar
multiplication maps to exponentation, which I know is quite weak.

And that paper indeed seems to use the same kind of scalar
multiplication to exponention mapping at x=0, but via bit other
vector.

Didn't look too much on what happens with the usual 4k+3 square
root algorithm (probably because that case was way harder to
analyze than the 0 case.

So in summary, if decompressing points, check that the points exist
(EdDSA specifies the needed checks), otherwise decompression won't
save you. Or use ladders on twist-secure curves (like X25519 and
X448 do).

-Ilari