Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions

Watson Ladd <watsonbladd@gmail.com> Sat, 22 July 2017 02:37 UTC

Return-Path: <watsonbladd@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 8446A1270A3 for <cfrg@ietfa.amsl.com>; Fri, 21 Jul 2017 19:37:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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] 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 i1J4YakoAB7r for <cfrg@ietfa.amsl.com>; Fri, 21 Jul 2017 19:37:34 -0700 (PDT)
Received: from mail-pg0-x236.google.com (mail-pg0-x236.google.com [IPv6:2607:f8b0:400e:c05::236]) (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 BD5AA126BF3 for <cfrg@irtf.org>; Fri, 21 Jul 2017 19:37:34 -0700 (PDT)
Received: by mail-pg0-x236.google.com with SMTP id k14so35446115pgr.0 for <cfrg@irtf.org>; Fri, 21 Jul 2017 19:37:34 -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=QRrNbnMg2WA4qPmCsK0eW2zbNf+wbFAep7Rg666aVck=; b=DZHkBcz6PSbsiZVab8N22loSp/Em4Ym9L0/VEmuFhT3HnTZLnewWpM1pM/WyxK+cLT cXygwCRTwCblqmzuoXp6FRPg9ZMSGockvTfoBaWgql3xq2gVBbE+ZGc+eMTC0JeXBfRp NAhX0a9OCeJDa+Qlr6neh6XO08fRt5re97OJFZoXgpK91iC4qxdfNcnss4eCbvOMeSoB d5UPYw2UN3Fd8zOuSiZ3lpfneAwgnqbdGn3VjrRMn4ynQXKVXQ+CvfzW+VhcPVK1dItD Cnzifx7jaGqTbDAPCb3NG23rAedlyepqsoPlhu+3QiMksn3FVe3k0LILvuQnL/P0eolh lRTg==
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=QRrNbnMg2WA4qPmCsK0eW2zbNf+wbFAep7Rg666aVck=; b=hAWPboya4FtQwCUanPnv4LKD5X0Dd29+rHPrfE47VJX0Gu4E3CX2RqXugEWrB7hE/Q ae7709Zt1XPo2Wj+MTawstRExNh6O7LtaIErempTqmrJ1NhDHp4/1yC9yiZ6zvuHNjho x7Kf7oOKdz0hD6uSvJ+WBb2wBkNHRZ6/V3YqviVTvCZHwAYMVtQZoGBJq7N46IAsHl1H yka4bVIaQo5x/sXKt6s3iDCuvnb8F+KPJAaYUsKFue335DElaBg2Htnwi8xvjpZ48I+k Di64mxy+9NsKw9+Wz6Oxc9Fr+z6NGXNxjGiaACVBtpNPOxqI7JjZ25IkFyh320sC7IQO C9Aw==
X-Gm-Message-State: AIVw112kUKyT8ql3+yAZtwHrTWlRKTRZYeYy4cPiZU5TWGdYZtJMeI9c UmevaZrII1g59LqBAwtA47rFjH6Prw==
X-Received: by 10.98.38.68 with SMTP id m65mr9280308pfm.47.1500691054342; Fri, 21 Jul 2017 19:37:34 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.100.187.77 with HTTP; Fri, 21 Jul 2017 19:37:33 -0700 (PDT)
In-Reply-To: <20170721163204.8573013.1016.15939@blackberry.com>
References: <CAJHGrrROHxR6WLQFO4+tL7N6DGKSAbwSzQZP-x3es+iy2O6TDg@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF501B63B22@XMB116CNC.rim.net> <20170721163204.8573013.1016.15939@blackberry.com>
From: Watson Ladd <watsonbladd@gmail.com>
Date: Fri, 21 Jul 2017 19:37:33 -0700
Message-ID: <CACsn0cm3QCiT9jFYp=EKfK8n6GdyW4TpyddG5NS5+zRFjLJoJg@mail.gmail.com>
To: Dan Brown <danibrown@blackberry.com>
Cc: Sharon Goldberg <goldbe@cs.bu.edu>, "cfrg@irtf.org" <cfrg@irtf.org>, "jan@ns1.com" <jan@ns1.com>, Dimitrios Papadopoulos <dipapado@umd.edu>, Leonid Reyzin <reyzin@cs.bu.edu>
Content-Type: multipart/alternative; boundary="94eb2c0ca0003643b00554deddb2"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/zVGPGuKAsJooLxl2P3W6iauPSnw>
Subject: Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
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: Sat, 22 Jul 2017 02:37:37 -0000

Two applications:
-NSEC5 uses VRFs to use online signing for zonewalking prevention and
offline signing for authenticity.
- Cloudflare uses OPRFs, a slightly different construction, to improve the
experience of Tor users



On Fri, Jul 21, 2017 at 9:32 AM, Dan Brown <danibrown@blackberry.com> wrote:

> Answering myself below: VRFs have been around since 1999, so are not so
> new.  ‎Still don't like the name, and still have trouble seeing the value.
>
> *From: *Dan Brown
> *Sent: *Tuesday, July 18, 2017 2:29 PM
> *To: *Sharon Goldberg; cfrg@irtf.org
> *Cc: *jan@ns1.com; Leonid Reyzin; Dimitrios Papadopoulos
> *Subject: *Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
>
> Hi Sharon and CFRG,
>
>
>
> On VRFs, my uncertain comments to consider at your leisure:
>
>
>
> Is it fair to say VRFs are relatively new?  If so, then maybe a little
> more caution is needed about their use.  It seems a tad hasty that it is
> being used already.
>
>
>
> To me, it seems that VRFs are basically signatures, with an extra
> feature.  My concern is that this extra feature might get overused, before
> it is thoroughly reviewed.
>
>
>
> It is unsurprising to me that random oracle model proof can prove the
> output of a hash to be random.  My intuitive concern is that at least
> informally, this is kind of circular.  Hashes often have some
> non-random-ish properties that might affect the extra security (over
> signatures) that VRFs are aiming for.  I guess I would much prefer a proof
> saying if the hash has (well-studied) properties XYZ, then your
> construction are VRFs.  (Maybe you have this already?  If so, then tell me
> so.)
>
>
>
> Since, VRFs require sending the “proofs” on the wire, I find it hard to
> see how it could be used to prevent dictionary attacks.  I assume that you
> are saying the proofs must be encrypted when one needs to avoid dictionary
> models?  I suppose all the details are there in I-D and papers, but for
> now, I am confused about the threat model (which parties have keys, etc.,
> if they require a secure channel and mutual trust, why just use plain old
> hash,…). To resist dictionary attacks, were already have PAKEs and
> PBHashing.  Now this?
>
>
>
> Finally, on a bikeshed-coloring note, I object to the name “verifiable
> random function”, on several grounds.
>
>
>
>    1. It is not a function.  It is at least four functions, keygen, sign,
>    verify, and hashify.
>    2. If you make it into a keyed function F_sk(m), as in
>    prooftohash(sign_sk(m)), it is not verifiable.
>    3. Verification requires the intermediate proof, which is certainly
>    not even pseudorandom (it is easy to distinguish valid signatures from
>    random).
>    4. It is pseudorandom, not random.  (The keys are random, but many
>    crypto has keys, without having “random” in its name: encryption, MAC,
>    signatures, key exchange, …, they also don’t verifiable or random in their
>    names either.)
>    5. The similar phrase “verifiably random”, albeit as a misnomer, has
>    past precedents, see NIST P-256 and Brainpool, etc.  When I see VRF, I
>    think a function, that aims to VR in that sense, and great, now we can
>    improve on Brainpool, etc.
>    6. “Random function” should be reserved for the ideal random mapping
>    concept, for example, as studied by Flajolet-Odlyzko (ok they only studied
>    the case of equal size domain and range).  The random oracle model, is the
>    idea of approximating this ideal, etc.  An actual approximation should not
>    be name as the ideal (sorry, I’m kind of repeating my point 4).
>
>
>
> Please forgive the fact that my comments above are not very constructive
> (or if the tone is wrong).  This is a new topic for me, so I am reluctant
> too many suggestions.  Nonetheless, I suggest (0) waiting a little, (1) a
> non-random-oracle security proof (if you don’t have it yet), (2) re-naming
> the scheme to something like re-hashable (or digestible) signatures (and
> re-name the various parts, i.e. proof -> signature, etc.).
>
>
>
> Best regards,
>
>
>
> Dan
>
>
>
>
>
> *From:* Cfrg [mailto:cfrg-bounces@irtf.org] *On Behalf Of *Sharon Goldberg
> *Sent:* Wednesday, July 12, 2017 5:42 AM
> *To:* cfrg@irtf.org
> *Cc:* jan@ns1.com; Dimitrios Papadopoulos <dipapado@umd.edu>du>; Leonid
> Reyzin <reyzin@cs.bu.edu>
> *Subject:* [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
>
>
>
> Dear CFRG,
>
> I'm presenting at next week's meeting on Verifiable Random Functions. A
> VRF is the public-key version of keyed cryptographic hash. Only the holder
> of the VRF secret key can compute the hash, but anyone with the public key
> can verify it.  VRFs can be used to prevent dictionary attacks on
> hash-based data structures, and have applications to key transparency
> (CONIKS), DNSSEC (NSEC5), and cryptocurrencies (Algorand).
>
> In advance of the meeting, please see:
>
> 1) Our substantially updated -01 draft:
> https://datatracker.ietf.org/doc/draft-goldbe-vrf/
>
> 2) Our project page, with links to various VRF implementations:
> https://www.cs.bu.edu/~goldbe/projects/vrf
>
> Comments welcome.  Thanks,
>
> Sharon
>
> --
> Sharon Goldberg
> Computer Science, Boston University
> http://www.cs.bu.edu/~goldbe
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
>


-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.