Subject: [Cfrg] Query about ECDAA security

From: Ira McDonald <[email-masked]>
Date: Thu, 23 Aug 2018 14:45:56 -0400

Hi,

[please feel free to reply offlist, if this is inappropriate for Crypto
Forum]

My colleague in Trusted Computing Group, Dave Challener, co-chair
of TCG Trusted Platform WG, sent this link earlier today with a query
about whether TCG should be advising people not to use 256-bit keys
with ECDAA:

https://paragonie.com/blog/2018/08/security-concerns-surrounding-webauthn-don-t-implement-ecdaa-ye
<https://paragonie.com/blog/2018/08/security-concerns-surrounding-webauthn-don-t-implement-ecdaa-yet>
t

Any comments would be very welcome.

Cheers,
- Ira

Ira McDonald (Musician / Software Architect)
Co-Chair - TCG Trusted Mobility Solutions WG
Chair - Linux Foundation Open Printing WG
Secretary - IEEE-ISTO Printer Working Group
Co-Chair - IEEE-ISTO PWG Internet Printing Protocol WG
IETF Designated Expert - IPP & Printer MIB
Blue Roof Music / High North Inc
http://sites.google.com/site/blueroofmusic
http://sites.google.com/site/highnorthinc
mailto: [email-masked]
Jan-April: 579 Park Place  Saline, MI  48176  734-944-0094
May-Dec: PO Box 221  Grand Marais, MI 49839  906-494-2434

---

From: Jim Schaad <[email-masked]>
Date: Thu, 23 Aug 2018 15:33:11 -0700

This is beating me to the punch.  At some point in the future I had planned to ask for a CFRG review of the ECDAA algorithms prior to processing a request that code points be assigned for COSE.

I would be more than happy to see some type of review being done now if that is reasonable.

Jim

From: Cfrg <[email-masked]> On Behalf Of Ira McDonald
Sent: Thursday, August 23, 2018 11:46 AM
To: [email-masked]; Ira McDonald <[email-masked]>
Subject: [Cfrg] Query about ECDAA security

Hi,

[please feel free to reply offlist, if this is inappropriate for Crypto Forum]

with ECDAA:

https://paragonie.com/blog/2018/08/security-concerns-surrounding-webauthn-don-t-implement-ecdaa-ye <https://paragonie.com/blog/2018/08/security-concerns-surrounding-webauthn-don-t-implement-ecdaa-yet> t

Cheers,

- Ira

Ira McDonald (Musician / Software Architect)
Co-Chair - TCG Trusted Mobility Solutions WG
Chair - Linux Foundation Open Printing WG
Secretary - IEEE-ISTO Printer Working Group
Co-Chair - IEEE-ISTO PWG Internet Printing Protocol WG
IETF Designated Expert - IPP & Printer MIB
Blue Roof Music / High North Inc
 <http://sites.google.com/site/blueroofmusic> http://sites.google.com/site/blueroofmusic
 <http://sites.google.com/site/highnorthinc> http://sites.google.com/site/highnorthinc
mailto: [email-masked] <mailto:[email-masked]> 
Jan-April: 579 Park Place  Saline, MI  48176  734-944-0094
May-Dec: PO Box 221  Grand Marais, MI 49839  906-494-2434

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 24 Aug 2018 10:08:14 +0000

Ira McDonald <[email-masked]> writes:

>My colleague in Trusted Computing Group, Dave Challener, co-chair of TCG
>Trusted Platform WG, sent this link earlier today with a query about whether
>TCG should be advising people not to use 256-bit keys with ECDAA:
>
>https://paragonie.com/blog/2018/08/security-concerns-surrounding-webauthn-don-t-implement-ecdaa-yet
>

Just a general comment, it's a good analysis and while the points made are
quite valid, it looks like someone tried to come up with an exhaustive list of
nitpicks rather than a more realistic, much shorter list of real threats.  For
example PKCS #1v1.5 padding is pretty trivial to get right if you use encode-
and-memcmp() rather than trying to parse and decode the padding.  Uncompressed
points aren't used because point compression has all sorts of patents
surrounding it (I haven't checked which ones have now expired, but the patent
mess poisoned their use for a long time), and the argument for point
compression seems a bit artificial, "if x is valid y is on the curve" could
just as well state "if x and y are valid" (meaning on the curve).  Given that
every spec I've ever seen says you need to check that you've been given a
point on the curve, and that even with point compression you need to check
that "x is valid" (whatever's meant by that), just telling people to use point
compression isn't a magic solution to the problem.

OTOH there are some issues that are quite valid, in particular the extremely
brittle nature of the DLP-based signature algorithms in regard to k (not just
a completely random k but any kind of bias when generating k, e.g. generating
an n-bit value and reducing it mod the prime used, which creates a bias in k),
and the use of BN curves (why those, of all possible curves you could choose?
If you want standards-compliance use P256, if you want standard-but-better-
than-P256 use brainpool256, and if you want trendiness use 25519).

Peter.

---

From: Scott Arciszewski <[email-masked]>
Date: Fri, 24 Aug 2018 09:12:16 -0400

Hi Peter,

Thank you for taking the time to read my analysis and share your feedback.

> and-memcmp() rather than trying to parse and decode the padding.

I don't disagree with your observation, but I'd argue that it misses
the overall point I was trying to consistently make.

Just because something is "pretty trivial to get right if..." doesn't
mean most real-world systems will do the trivial correct thing.

As frustrating as it is, unless we produce standards that are easy for
non-cryptography folks to use securely in their software (and, even
better, difficult to use insecurely), we will encounter insecure
implementations in the wild.

One needs look no further than ROCA or ROBOT to see this is the case.
But if anyone needs another example, take a look at RNCryptor.

RNCryptor does something pretty boring: AES-CBC + HMAC-SHA2. It's
implemented in a lot of languages and solves a generic
"encrypted/tamper-resistant token" use case for developers. You would
think that the biggest risks for such a design are predictable IV
generation and timing attacks on the MAC validation.

But it turns out, no, at least one implementation (Haskell) just
discards the HMAC entirely when decrypting messages, which means their
users now have to worry about padding oracles attacks.

https://github.com/RNCryptor/rncryptor-hs/blob/01aca39ad51c548ef0142d70265f1ffba37cf67d/src/Crypto/RNCryptor/V3/Decrypt.hs

HMAC validation is pretty trivial to get right (as long as you have a
secure compare function on-hand), but we still see failures like this
in the ecosystem.

The solution to that problem is: Since most languages' crypto
libraries these days just wrap OpenSSL's libcrypto, and libcrypto
exposes AEAD interfaces that don't allow developers to accidentally
use unauthenticated encryption, there has been a concerted effort to
get developer to "just use AEAD".

The motivation for preferring AEAD over Encrypt-then-HMAC doesn't make
the implementing HMAC validation in a web app less trivial, but
developers are still less likely to shoot themselves in the foot with
AEAD.

That's where I'm coming from when I decry the use of PKCS1v1.5 (even
though BB'06 can be side-stepped pretty easily).

> ... Uncompressed
> just as well state "if x and y are valid" (meaning on the curve).

If you only have one coordinate to work with (and, if relevant, the
sign of the other coordinate), you _can't avoid_ checking that the
point is on the curve. If you have two coordinates, it's possible to
implement a system that omits this check. That's essentially the crux
of my argument. This is also what X25519 does.

The converse (send Y and the sign of X) is also a valid strategy. If I
remember correctly, this is what Ed25519 does.

The blog post was a little imprecise on the formality. I'm sorry if
that made the intention or message unclear. I'll try to be better
about that when writing future articles.

> ... Given that

What I meant here is: If x is valid was a shorthand meaning, at
minimum, x is an integer in the range [1, p).

There may be other validation constraints to consider as well, but if
there are, they're probably curve-specific.

> an n-bit value and reducing it mod the prime used, which creates a bias in k),

Funny enough, when I was writing this post, I completely forgot about
the biased k attacks (probably because I've yet to implement the
exploit).

On Fri, Aug 24, 2018 at 6:08 AM Peter Gutmann <[email-masked]> wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Dan Brown <[email-masked]>
Date: Fri, 24 Aug 2018 18:41:14 +0000

-----Original Message-----
From: Cfrg <[email-masked]> On Behalf Of Scott Arciszewski
...

> points aren't used because point compression has all sorts of patents 

<DB> Uncompressed points can be faster than compression - if the curve lacks
fast x-only scalar multipliers - because you can skip the step of point
decompression, so that may be another reason to prefer uncompressed.  </DB>

If you only have one coordinate to work with (and, if relevant, the sign of
the other coordinate), you _can't avoid_ checking that 

<DB> That's not fully correct. Given x, to fully decompress, meaning to
compute y, you need to compute a square root.  Many typical square root
algorithms produce an intermediate candidate square root no matter what the
input is, even if not a square.  For valid x, omitting this check is safe,
but for invalid x, this is unsafe.  Leaving out this check would result in
interoperable implementations. I would guess that an implementer leaving out
this check is as about as likely leaving the check that (x,y) is on the
curve.  I sent an example of an invalid compressed point to the CFRG list a
while back: it decompress to a small order invalid point - assuming that the
decompression skips the checking step in the square root algorithm.  (Such
points could be used as test vectors to detect such implementation faults.)
For x-only methods, such as the Montgomery ladder, you don't need to compute
y at all, but there are still invalid x, which is why "twist-security" is
valuable. </DB>

> ... Given that
> every spec I've ever seen says you need to check that you've been 
> given a point on the curve, and that even with point compression you 
> need to check that "x is valid" (whatever's meant by that), just 
> telling people to use point compression isn't a magic solution to the
problem.

What I meant here is: If x is valid was a shorthand meaning, at minimum, x
is an integer in the range [1, p).

There may be other validation constraints to consider as well, but if there
are, they're probably curve-specific.

<DB> See above. </DB>

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 25 Aug 2018 05:00:39 +0000

Scott Arciszewski <[email-masked]> writes:

>As frustrating as it is, unless we produce standards that are easy for non-
>cryptography folks to use securely in their software (and, even better,
>difficult to use insecurely), we will encounter insecure implementations in
>the wild.

Absolutely.

There's another problem though, in that a lot of the more secure mechanisms
are both really, really complex (compare just the basic OAEP vs. PKCS#1 v1.5)
and often have very little mainstream library support, or if support is
present it's little-tested and little-evaluated because of it's non-mainstream
nature.  As a result, developers have the choice of (say) RSA-PKCSv1.5 and
hoping the library gets it right, or RSA-PSS, possibly having to roll it
themselves, and being non-interoperable with most of the planet when the get
it implemented.

That's another issue with point compression that follows on from the patent
issues, standards like TLS have allowed point compression since forever (the
ec_point_formats extension is mandatory for TLS with ECC), but the spec says:

  Implementations of this document MUST support the uncompressed format for
  all of their supported curves and MUST NOT support other formats for curves
  defined in this specification.

  If the client sends the extension and the extension does not contain the
  uncompressed point format, and the client has used the Supported Groups
  extension to indicate support for any of the curves defined in this
  specification, then the server MUST abort the handshake and return an
  illegal_parameter alert.

The same thing is reflected in other standards, and in crypto libraries.  So
you often have to make a choice between "less than perfect theoretically but
universally deployed" and "(allegedly) perfect theoretically but you'll be in
for a shock when you try and deploy it".

Peter.

---

From: Shoko YONEZAWA <[email-masked]>
Date: Wed, 29 Aug 2018 23:08:22 +0900

Hi there,

As for the elliptic curves used in ECDAA,
we have similar concern about the security of
so-called pairing-friendly curves,
elliptic curves used for pairing-based cryptography,
against the attack presented in CRYPTO 2016.

Actually, we are writing an I-D
dealing with secure parameters of pairing-friendly curves.
Our I-D is based on draft-kato-threat-pairing submitted in Mar 2018.
https://datatracker.ietf.org/doc/draft-kato-threat-pairing/

We will include recommended parameters of pairing-friendly curves
and their references with each security level
(128-bit security, 256-bit security and more)
in terms of OSS, standards, and academic points of view.

At the moment, our recommendations are:

- For 128-bit security
     - BN462 - https://eprint.iacr.org/2015/1212
     - BLS12-381 - https://eprint.iacr.org/2017/1050
- For 256-bit security
     - BLS48 - https://link.springer.com/chapter/10.1007/978-3-319-61204-1_4

Best regards,
Shoko

-- 
Shoko YONEZAWA
Lepidum Co. Ltd.
[email-masked]
TEL: +81-3-6276-5103