Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 6 Nov 2018 20:21:31 +0100
From: Solar Designer <>
Subject: Re: CVE-2018-5407: new side-channel vulnerability on SMT/Hyper-Threading architectures

On Fri, Nov 02, 2018 at 04:42:33PM +0200, Billy Brumley wrote:
> It's coming -- I promise. I submitted it as an IACR eprint yesterday
> ("Port Contention for Fun and Profit") -- currently under moderation,
> but will eventually pop out here:
> (Side note: I have raised this issue several times with IACR. I can't
> get a permalink from them until I submit and it clears the mod queue.
> But I can't submit stuff that's still under embargo. It's a catch 22.
> Ofc there are technical solutions from IACR side but they won't
> address it. Share your opinion: @IACR_News current co-editor is
> @Leptan.)

I pinged @Leptan on Twitter earlier today with:

"@Leptan Any chance you could push "Port Contention for Fun and Profit"
through @IACR_News moderation? It's in mainstream news since Friday, but
the paper is still not public. I think moderation should be quick (one
day) at least in cases like this. Thanks!"

And promptly heard back with:

"Done. Special cases where publication should be timed with the
mainstream news requires to let us know because we cannot guess..."

Cesar Pereida Garcia already posted the link to oss-security (thanks!),
but unfortunately not (reliably) to this thread (no In-Reply-To header),
so here it is again for those browsing the thread in archives:

> The code in question certainly had lots of SCA issues :) I was the
> first to show it vulnerable with an L1 dcache SMT attack (ASIACRYPT
> 2009). OpenSSL didn't respond during disclosure. Side note:
> openssl-security is so much better since HeartBleed. They're really on
> top of things, and being GitHub-based now the code is constantly
> improving. If you're reading, go contribute to the project!
> If there's something good about a vulnerability being unpatched for
> almost a decade: that code path sparked quite a lot of academic work
> in microarchitecture attacks.

> For the 1.1.0 branch, at
> everything starting from aab7c770353b1dc4ba045938c8fb446dd1c4531e

Per my reading, this introduces a closer-to-constant-time implementation
and invokes it in some special cases ("the common cases where the scalar
is secret") at the start of ec_wNAF_mul, letting that function fall
through to its old presumably non-constant-time code in other cases.
Further commits don't change that.  For someone like me not familiar
with ECC nor with this codebase it's tricky to figure out which
side-channel leaks and where exactly were in the old/generic
implementation (but I tried, below) and whether it's somehow safe to use
in cases where it's still reachable.

The paper says:

"In OpenSSL 1.1.0h and below, P-384 calls ecdsa_sign_setup @
crypto/ec/ecdsa_ossl.c when generating an ECDSA signature.  There, the
underlying ec_wNAF_mul function gets called to perform scalar
multiplications, where r = [k]G is the relevant computation for this
work.  That function first transforms the scalar representation, the
actual scalar multiplication algorithm executes a series of double and
add operations.  To perform double and add operations, OpenSSL calls
ec_GFp_simple_dbl and ec_GFp_simple_add respectively.  There, these
methods have several function calls to simpler and lower level
Montgomery arithmetic, e.g. shift, add, subtract, multiply, and square
operations.  A single ECC double (or add) operation performs several
calls to these arithmetic functions."

I assume ec_GFp_simple_dbl and ec_GFp_simple_add are in fact called via
EC_POINT_dbl and EC_POINT_add (via function pointer indirection inside
them, which I didn't follow), respectively.  This code skips the call to
EC_POINT_add when digit is 0, and the setting and handling of is_neg is
also potentially leaky:

    for (k = max_len - 1; k >= 0; k--) {
        if (!r_is_at_infinity) {
            if (!EC_POINT_dbl(group, r, r, ctx))
                goto err;

        for (i = 0; i < totalnum; i++) {
            if (wNAF_len[i] > (size_t)k) {
                int digit = wNAF[i][k];
                int is_neg;

                if (digit) {
                    is_neg = digit < 0;

                    if (is_neg)
                        digit = -digit;

                    if (is_neg != r_is_inverted) {
                        if (!r_is_at_infinity) {
                            if (!EC_POINT_invert(group, r, ctx))
                                goto err;
                        r_is_inverted = !r_is_inverted;

                    /* digit > 0 */

                    if (r_is_at_infinity) {
                        if (!EC_POINT_copy(r, val_sub[i][digit >> 1]))
                            goto err;
                        r_is_at_infinity = 0;
                    } else {
                        if (!EC_POINT_add
                            (group, r, r, val_sub[i][digit >> 1], ctx))
                            goto err;

Wikipedia confirms that this is a known issue in double-and-add, and
Montgomery ladder is a way to avoid it:

Also, while the newly introduced implementation is still called
ec_mul_consttime in OpenSSL_1_1_0-stable, it's renamed to
ec_scalar_mul_ladder in OpenSSL_1_1_1-stable and has this comment on it:

 * NB: This says nothing about the constant-timeness of the ladder step
 * implementation (i.e., the default implementation is based on EC_POINT_add and
 * EC_POINT_dbl, which of course are not constant time themselves) or the
 * underlying multiprecision arithmetic.

Is this still an issue needing fixing, or is it e.g. believed to be
sufficiently mitigated by blinding?



P.S. Congrats on receiving the grant for "SCARE: Side-Channel Aware
Engineering", and I hope we'll see more excellent research from your
team in the next 5 years:

Powered by blists - more mailing lists

Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.