Re: [Cfrg] My thoughts on randomized signature generation

Phillip Hallam-Baker <> Mon, 11 May 2020 17:38 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 665953A098A for <>; Mon, 11 May 2020 10:38:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.396
X-Spam-Status: No, score=-1.396 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id IyUNdEQIBYrV for <>; Mon, 11 May 2020 10:38:30 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 45B933A0854 for <>; Mon, 11 May 2020 10:38:30 -0700 (PDT)
Received: by with SMTP id v17so278694ote.0 for <>; Mon, 11 May 2020 10:38:29 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=GAvgi+m/k0zDWlS/XhiI9f2bRwT1YpWg15s/vC42sIo=; b=PwfT6tu3+w14lwtKhAdux9om6H9HcIiG0mZl5pdM6RJjrktWSSHkzHVBOnb9UBE2XU Bc1xwIYgklAe2DqcZk2afVQrw+G/YiWProvHpOA1xpSgDzZDlu2d4qyhvEbPbzqhVvoH +wZLWMlfwg0QOBI6n1hViKkX+brwkPZwHCPTdVCtmAnHLeQme6sF2vAUh76Dk1muWCYe r0mtN5BzdN5a8HaFZwmzGhTGg6wKYlxJd/IaWOLnYo14MTo6Bg5uofySH5WkiES+OOb5 EMdbQmfSMluVqL0t30StVkqOpiTELD2+NoorBMcLKv2IaslRHcTN6P0gU7StorTEw8hl 67dg==
X-Gm-Message-State: AGi0PubLa76k9q4TcehNzkco1XRDwGEWowSAYvzQchOAYno2vd+X+riP /ARoa4bwuNfUM/KomwzfRA/4ovmjx2kw+RuCbGc=
X-Google-Smtp-Source: APiQypI/IDWwq6onsZFpWCkBmIL7gXbGSfFi9Gs8pKpHmR8klAy9x7nPAF7LIBrt1AvMuZwWGdvf7Z88wxdcr6a/mnw=
X-Received: by 2002:a9d:bd1:: with SMTP id 75mr14516803oth.155.1589218709213; Mon, 11 May 2020 10:38:29 -0700 (PDT)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Phillip Hallam-Baker <>
Date: Mon, 11 May 2020 13:38:17 -0400
Message-ID: <>
To: Watson Ladd <>
Cc: CFRG <>
Content-Type: multipart/alternative; boundary="000000000000a2189c05a562d0ce"
Archived-At: <>
Subject: Re: [Cfrg] My thoughts on randomized signature generation
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 11 May 2020 17:38:52 -0000

I agree with Watson's conclusion but for the opposite reason.

If you follow the MtGox saga you will know that a particular malleability
attack was claimed as the reason for the disappearance of the funds.

The use of deterministic signatures sets up similar opportunities for
attack. While I have not identified a specific exploit, I don't see the
need. It is clear that this is an area where the construction of the
signature algorithm invites the relying party to rely on a property of the
signature that is not actually guaranteed by the algorithm itself.

That is just bad practice.

The only circumstance in which I would want to be able to distinguish these
specific cases is if I had bought a HSM and wanted to verify it was
generating k in a principled fashion. There is a genuine problem that
arises from having HSMs act non deterministically. As Moti Yung pointed
out, your RSA keygen can be encrypting the random seed used to generate a
key pair and using the public key itself as the side channel.

So I support adding a non deterministic mode of signature generation.
Recognizing the fact that once you do that, there is no way to prohibit
online/offline signing and pregenerating values of k.

On Tue, May 5, 2020 at 8:36 AM Watson Ladd <> wrote:

> Dear participants,
> I apologize for the long delay between the virtual meeting and this
> email. I'm writing to expand upon my opposition at the mike to
> distinguishing between interoperable signatures based on the method of
> generation.
> My opposition is rooted in the following facts: the signature
> generation method doesn't introduce any incompatibility with existing
> verfiers, and the existing installed verifiers expect the already
> allocated codepoints. A new system using randomized generation that
> doesn't use the existing codepoints will thus be incompatible. It
> would of course be possible to avoid this, and the right way is simply
> to use the existing codepoints rather then implement the less secure
> generation method.
> Sincerely,
> Watson Ladd
> _______________________________________________
> Cfrg mailing list