Re: [TLS] TLS 1.3: Deterministic RSA-PSS and ECDSA

Brian Smith <brian@briansmith.org> Sun, 07 August 2016 22:44 UTC

Return-Path: <brian@briansmith.org>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3F5FA12D12E for <tls@ietfa.amsl.com>; Sun, 7 Aug 2016 15:44:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.601
X-Spam-Level:
X-Spam-Status: No, score=-2.601 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=briansmith-org.20150623.gappssmtp.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 OrDiEWUZ2kMw for <tls@ietfa.amsl.com>; Sun, 7 Aug 2016 15:44:33 -0700 (PDT)
Received: from mail-io0-x22a.google.com (mail-io0-x22a.google.com [IPv6:2607:f8b0:4001:c06::22a]) (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 6191712B019 for <tls@ietf.org>; Sun, 7 Aug 2016 15:44:33 -0700 (PDT)
Received: by mail-io0-x22a.google.com with SMTP id q83so344103914iod.1 for <tls@ietf.org>; Sun, 07 Aug 2016 15:44:33 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=briansmith-org.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=uMvKPViM45NRcvP+E4CC1qFxPPJygVUjoYAQlUW3TJY=; b=BNtOtNJTgp3ApwTDuBaxrxdvjcwW/vS+SJ1o5Y9LXEe4+NDBpXhBR0RAGpt91wYo7h S8PjGsrcc0KpSZjuklpOkU2Vr6fj+E9/JRGNkXFCkt5+6rm38UpITiwL/wLF+AAlPOyG Yon9dEe6QVqjMlTwLtQ8oeqtDIjsd9usThT938Qzl4hWI5ejMJOjhS45wHabx7E8LTT2 bg9XyIwHfR7gmbJV7/4uQgRnUTZz6O+ZJg/UuS0sw63fGsmmnJ9fyRe2fgc+zsKU6SvI 36qZ882SNQBxSqnD1LGx8ACtjI3QG38NC+Jxwz2uZdj1kuZqcFNKiqSLgjPmr4VI2FKa CD0A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=uMvKPViM45NRcvP+E4CC1qFxPPJygVUjoYAQlUW3TJY=; b=Oi3ZZcSD8wZzb+sj+Gl2VorWuPd0P/i9CAzrF8dBruNhmFBS21rvXEvFxlm+ImiPmZ jfSGpTmbdiaHh2tjFCoP3k1C2lctakSZAULM4x8ZpL8mUnto9UjSsuhrxG1efNcNJN+C TatZwKfVkgc0zNv7lrUN6YpKnunYBo8GO96A+xXApm0dGpHXDSa0KIxl9hDUAcIyNcAK 88yqUFQm/4lfmY6A54Wgfe3zDM7RDVD7bfS3p/imF3bR3yqdmxC0CgLjkmlqa6802Tn3 w7QCcG36YsO9rpII3zNe9zpQa/qp2bbFHmd9y5Gj1P0AqKGTsMW3bBablVLDMBhZmbpO i/7g==
X-Gm-Message-State: AEkoouvWeLzTd80TqHO/ohbZ2acEhnqN9OAT8OMFHSwH0XeG/NFDQOId8O2BHoR1viE5O5pz7ZhO9Vp/K6ZVuQ==
X-Received: by 10.107.9.231 with SMTP id 100mr92133343ioj.196.1470609872592; Sun, 07 Aug 2016 15:44:32 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.36.74.73 with HTTP; Sun, 7 Aug 2016 15:44:32 -0700 (PDT)
In-Reply-To: <782287ea-f491-0298-baa6-aa82e650fe6e@gmail.com>
References: <CAFewVt5CyooWhOWHwD+sLv9qVqS8YQJMnFLRFbLZtJVVDF6RvQ@mail.gmail.com> <20160806235716.726a0e4e@pc1> <782287ea-f491-0298-baa6-aa82e650fe6e@gmail.com>
From: Brian Smith <brian@briansmith.org>
Date: Sun, 7 Aug 2016 12:44:32 -1000
Message-ID: <CAFewVt5NAdpxg5jZL26xjv_xLTprBcMZZtCYTqYEEtRb1WE21g@mail.gmail.com>
To: Rene Struik <rstruik.ext@gmail.com>
Content-Type: text/plain; charset=UTF-8
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/303BrXJWtR4unYLytJBpQCZW36c>
Cc: "<tls@ietf.org>" <tls@ietf.org>
Subject: Re: [TLS] TLS 1.3: Deterministic RSA-PSS and ECDSA
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 07 Aug 2016 22:44:35 -0000

Rene Struik <rstruik.ext@gmail.com> wrote:
> The papers [1] and [2] may be of interest here. In [2], Section 3.3, Alfred
> Menezes and Neil Koblitz compare FDH-hash RSA signatures, PSS (lots of
> randomness in the salt), and a scheme by Wang and Katz that only contains
> one bit of randomness with signing and is claimed to have tight reductions
> (see also [1]) and argue a "Pass on PSS".
>
> [1] Signature Schemes - Efficient, with Tight Security Reductions (Jonathan
> Katz, Nan Wang, CCCS 2003). Available from
> https://www.cs.umd.edu/~jkatz/papers/CCCS03_sigs.pdf
> [2] Provable Security, Another Look at (Alfred Menezes, Neal Koblitz, IACR
> ePrint 2004-152). Available from https://eprint.iacr.org/2004/152

Right, these are the papers I read that made me start to think it
might actually be dumb to randomize the salt when generating a PSS
signature. It seems like the randomization is purely needed purely as
an artifact of the method used in the security reduction, and seems
unlikely to actually improve security. In fact, it would hurt security
because it adds significant complexity to PSS signature generation and
provides a means to efficiently smuggle secrets out of the security
module containing the RSA private key. Thus, an implementer of RSA-PSS
signature generation who wants to maximize security likely won't want
to randomize the salt.

Another interesting paper is [3], which says "However, since PSS (with
random salt of arbitrary length) is at least as secure as FDH, we
obtain as a corollary from Section 3 a tight security proof from
lossiness to the security of PSS, with random salt of arbitrary
(possibly zero) length."

At the time I suggested [4] that the salt length be fixed to the
length of the digest function for RSA PSS signatures in TLS, I wasn't
aware of all the research that had been done. Unfortunately, my
under-informed suggestion is what is currently prescribed in the
current draft. I'd like to make sure that whatever the spec ultimately
prescribes is actually motivated by a current scientific argument,
even if it means I have to admit I was wrong.

[3] Optimal Security Proofs for Full Domain Hash, Revisited (Saqib A.
Kakvi and Eike Kiltz). Available from
https://www.iacr.org/archive/eurocrypt2012/72370533/72370533.pdf.
[4] https://www.ietf.org/mail-archive/web/tls/current/msg15601.html

Cheers,
Brian
--
https://briansmith.org/