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

Dan Brown <danibrown@blackberry.com> Fri, 21 July 2017 16:32 UTC

Return-Path: <danibrown@blackberry.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 B6082131B71 for <cfrg@ietfa.amsl.com>; Fri, 21 Jul 2017 09:32:14 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.4
X-Spam-Level:
X-Spam-Status: No, score=-5.4 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H2=-2.8, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 DKiWEN4s00w8 for <cfrg@ietfa.amsl.com>; Fri, 21 Jul 2017 09:32:11 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) (using TLSv1.2 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 7B82E131B29 for <cfrg@irtf.org>; Fri, 21 Jul 2017 09:32:11 -0700 (PDT)
Received: from xct103cnc.rim.net ([10.65.161.203]) by mhs211cnc.rim.net with ESMTP/TLS/DHE-RSA-AES256-SHA; 21 Jul 2017 12:32:08 -0400
Received: from XCT116CNC.rim.net (10.65.161.216) by XCT103CNC.rim.net (10.65.161.203) with Microsoft SMTP Server (TLS) id 14.3.319.2; Fri, 21 Jul 2017 12:32:09 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT116CNC.rim.net ([::1]) with mapi id 14.03.0319.002; Fri, 21 Jul 2017 12:32:09 -0400
From: Dan Brown <danibrown@blackberry.com>
To: Sharon Goldberg <goldbe@cs.bu.edu>, "cfrg@irtf.org" <cfrg@irtf.org>
CC: "jan@ns1.com" <jan@ns1.com>, Leonid Reyzin <reyzin@cs.bu.edu>, Dimitrios Papadopoulos <dipapado@umd.edu>
Thread-Topic: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
Thread-Index: AQHS+vM6+DG9anuMcU+xW6RwdHg7uaJZ5FlggASji3c=
Date: Fri, 21 Jul 2017 16:32:08 +0000
Message-ID: <20170721163204.8573013.1016.15939@blackberry.com>
References: <CAJHGrrROHxR6WLQFO4+tL7N6DGKSAbwSzQZP-x3es+iy2O6TDg@mail.gmail.com>, <810C31990B57ED40B2062BA10D43FBF501B63B22@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501B63B22@XMB116CNC.rim.net>
Accept-Language: en-US, en-CA
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Content-Type: multipart/alternative; boundary="_000_201707211632048573013101615939blackberrycom_"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ImNk05DFmX7HdUflklvtpaBr-Mc>
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: Fri, 21 Jul 2017 16:32:15 -0000

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>; 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