Re: [Cfrg] Side channel attack and Edwards curves...

Tony Arcieri <bascule@gmail.com> Wed, 05 July 2017 22:01 UTC

Return-Path: <bascule@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2B29313169F for <cfrg@ietfa.amsl.com>; Wed, 5 Jul 2017 15:01:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5yhm1hon3gQj for <cfrg@ietfa.amsl.com>; Wed, 5 Jul 2017 15:01:36 -0700 (PDT)
Received: from mail-yb0-x229.google.com (mail-yb0-x229.google.com [IPv6:2607:f8b0:4002:c09::229]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EC03C131545 for <cfrg@irtf.org>; Wed, 5 Jul 2017 15:01:32 -0700 (PDT)
Received: by mail-yb0-x229.google.com with SMTP id s15so673769ybe.2 for <cfrg@irtf.org>; Wed, 05 Jul 2017 15:01:32 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=/9bAixlAYrcDr8r67axy27lN4BtF0kCq40N4ryEAdQY=; b=Kj+YE90/0fanRARwua7T5HDQkssmUr/BInqj5Q8ueesJQbvSTqieJIWh2gIjCh8sTL FeYLF3aYsBaIOuxqLajsGMpLvzxM7Ahg1sWgVWl8ZCM8uxZO89ksnRlDVyD9K+sjfHRA 2bQOytleBYemxTqy4fYjo+HIV/pu0KS0ehAmzzdLuqlZ+Nt2UAeNL42sFTU007oaH8i7 caAOF1AInFCVJ5dFLUN+AWptJArYXG41Lm4Iz0WWq/GS0hlxUapKNC55f29z16JZCw4W H6eKGI3TrO/S4v6XrD4oVEhNyMZnTkocj/zT/HIf2tc2NdTyBJxLW3QQ+3XflFXsyhE3 zw5Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=/9bAixlAYrcDr8r67axy27lN4BtF0kCq40N4ryEAdQY=; b=FepL6n0Y/z3YwTfmOl2x9TXH2Dcf27fRpfNz9pTkMRgqyObZ3m+q78ej2RJVF9aF1s 6N6kpQVHZM7aSkToooEfwj+VF3FBJ/7OklSEhDCdJil+9w7ZXuKLjd8wzWy4js/+1voo wJVRhDopccwQjuS9FzKGVqB8ILojReQ2ako6rzjbC6gQYuLBw9fizUgy8XYY2qv9mWbI QuaoG1UskPu+2JIpOnflsmrGb4j55w1AWYFgXJC2cvbw+REt7sDw/G+Jwaqwjc2cq01m /k/m64ViMerVImYgFJnLozqqYgtxoFMx2N+hTN9a4XaK9iZLepJQYEl9M0aWJY+0vwcA S0LA==
X-Gm-Message-State: AIVw110r4sBe0zjKpayitlstIeRc/+pDRe4s/ogS3Wm+9p5beULAi8zM 3nPEqyUGOk2zAElsa4YsbPsjb2k+yg==
X-Received: by 10.37.203.139 with SMTP id b133mr224971ybg.209.1499292091718; Wed, 05 Jul 2017 15:01:31 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.37.228.134 with HTTP; Wed, 5 Jul 2017 15:01:11 -0700 (PDT)
In-Reply-To: <CAMm+LwiDbjq7nENzvqKGmsQnz=y49nBSVhU0boddtbz3dJAHfw@mail.gmail.com>
References: <CAMm+LwiDbjq7nENzvqKGmsQnz=y49nBSVhU0boddtbz3dJAHfw@mail.gmail.com>
From: Tony Arcieri <bascule@gmail.com>
Date: Wed, 5 Jul 2017 15:01:11 -0700
Message-ID: <CAHOTMVLyB6+r6XX3z5ifi7Ey7Qpi1uiZDLsGREsWhgxjqotPxQ@mail.gmail.com>
To: Phillip Hallam-Baker <phill@hallambaker.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="001a114faf108abb6a0553992417"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/QqM5RrsPRFcGKgJygEo82cO4JBQ>
Subject: Re: [Cfrg] Side channel attack and Edwards curves...
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 05 Jul 2017 22:01:38 -0000

On Wed, Jul 5, 2017 at 11:38 AM, Phillip Hallam-Baker <phill@hallambaker.com
> wrote:

> Just another side channel attack and not something that bothers me writing
> reference code. But have we maybe put our eggs in the Montgomery ladder
> basket when maybe we should have gone for 'randomly split the private key
> into two parts, perform two separate multiplications with each part and add
> the result'.
>

I'm not sure why you're talking about Montgomery vs Edwards here. This is a
Flush+Reload attack similar to:

- "Just A Little Bit": https://eprint.iacr.org/2014/161.pdf
- "Just A Little Bit More": https://eprint.iacr.org/2014/434.pdf
- Cachebleed: https://eprint.iacr.org/2016/224.pdf

If there was a conclusion I drew from these attacks, it's the need to
include random values, as the security proofs say we should do.

I will note that BoringSSL was not vulnerable to Cachebleed because they
continued to use random blinding in addition to Intel's allegedly "constant
time" RSA code. Though many are quick to dismiss it, random blinding seems
to provide defenses against a multitude of attacks, not just cache timing
but DPA as well.

-- 
Tony Arcieri