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

Thomas Garcia <tgarcia.3141@gmail.com> Wed, 26 July 2017 11:32 UTC

Return-Path: <tgarcia.3141@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 2A907131FFC for <cfrg@ietfa.amsl.com>; Wed, 26 Jul 2017 04:32:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.449
X-Spam-Level:
X-Spam-Status: No, score=-2.449 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, 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=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 MfXrXFY7S9Vz for <cfrg@ietfa.amsl.com>; Wed, 26 Jul 2017 04:32:11 -0700 (PDT)
Received: from mail-lf0-x232.google.com (mail-lf0-x232.google.com [IPv6:2a00:1450:4010:c07::232]) (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 5D842131FF7 for <cfrg@irtf.org>; Wed, 26 Jul 2017 04:32:11 -0700 (PDT)
Received: by mail-lf0-x232.google.com with SMTP id t128so37112107lff.2 for <cfrg@irtf.org>; Wed, 26 Jul 2017 04:32:11 -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=21q23PDTgBieJNQb+1QskSPHF4nLdTNaN716qy9iYws=; b=iBqLsbTTM+O1XFpSdIALheMumakxS7k8Lk9pIdZIFl9j/l+ngvykDPnG6Oy05iP5of gmt3hg/nNd4Omjs8UEFozHmlJOBDOpBPzHTGDNml2o/nhXXndLN3HN180LHqxx/lpIyY xiKxKabw4m147RFtiw7LSAH/oCauy3RwN9hZOwwaVuuubvuly/mPpBhcu8QFV35Wc/Qx AazUVZ746bC0jURl9GjT/WmSyxX1K/57a5aovVeZkokNb60Kw6XAkgubrKl7nheBZXH1 DSorjLAHaV6Zy0WYpIEVPaDqAO0TpHFnLUo4Z5DszKM1TVAdBxPObi+75l/5kNe/G1ff Sdig==
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=21q23PDTgBieJNQb+1QskSPHF4nLdTNaN716qy9iYws=; b=W2TA7XcyVDXv3KbBUHoTkQ62UcHAeAh2JycofS2i31dY307513svhHFuqqpMFljiRK 9CNY8l6vWmSU3BN36X13hMWxA5u71LlrBepj7WoekYNa4n7ZKhkv88/gMOTzte8OO/bV NJ39yw0OG+M0uHLVaS8FeQl5YTUQ2qqeTCt1ke02PpDRS0IqE1MAh1dGUW3lJ6ZFY8Oj osoSselat+bh9LU15kyyMtH3yiy/QbWddBzUBcTNCz5CaiBM0izvNqDMQkv6+HIAD7nT s8XD0oX3/CMwx8kRFq2LHn+96zjYHV1R50woLrEbatgqnD4+0x6+XVa10h18fXJF95LJ JTgQ==
X-Gm-Message-State: AIVw113DXGsLROKq6bFceCbq7JIqgavoV46gLUScqHPsWNvm+2Dgi1AI jgSFyc/wG4Yxsgt9dw4eKitCjTuiCA==
X-Received: by 10.46.69.87 with SMTP id s84mr311183lja.129.1501068729470; Wed, 26 Jul 2017 04:32:09 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.25.37.83 with HTTP; Wed, 26 Jul 2017 04:32:08 -0700 (PDT)
In-Reply-To: <CAJHGrrTbjL3rd_XU9tx28g3QcBe9tJBOxs2t1OebfvZR_c7epA@mail.gmail.com>
References: <CAJHGrrROHxR6WLQFO4+tL7N6DGKSAbwSzQZP-x3es+iy2O6TDg@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF501B63B22@XMB116CNC.rim.net> <20170721163204.8573013.1016.15939@blackberry.com> <CAJHGrrTbjL3rd_XU9tx28g3QcBe9tJBOxs2t1OebfvZR_c7epA@mail.gmail.com>
From: Thomas Garcia <tgarcia.3141@gmail.com>
Date: Wed, 26 Jul 2017 12:32:08 +0100
Message-ID: <CAFTSWvfwf34uH1AjzQq7zCMEARGH8rH310pSRe7kkYCZ3TMNeQ@mail.gmail.com>
To: Sharon Goldberg <sharon.goldbe@gmail.com>
Cc: Dan Brown <danibrown@blackberry.com>, "jan@ns1.com" <jan@ns1.com>, "cfrg@irtf.org" <cfrg@irtf.org>, Dimitrios Papadopoulos <dipapado@umd.edu>, Leonid Reyzin <reyzin@cs.bu.edu>
Content-Type: multipart/alternative; boundary="001a114b0cda675212055536cc3a"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/UX1fHbz6wYg557dAF1PNQ-3pyqI>
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: Wed, 26 Jul 2017 11:32:15 -0000

Hello,
A couple of questions:
1. It seems that one of the properties that you are interested that the VRF
will have is determinism. On the other hand, the EC-VRF value is dependent
on the choice of some random number k. How are these two facts compatible?
Am I missing something?
2. The value c calculated in EC-VRF is only 128 bits long for Ed25519. In
normal usage of Ed25519 the signature uses the full length of the hash
output. Doesn't this expose the signature to collision attacks?

Thomas G.

On Sun, Jul 23, 2017 at 6:10 AM, Sharon Goldberg <sharon.goldbe@gmail.com>
wrote:

> Hi Dan,
>
> Thank you for your comments. Indeed, VRFs have been around since 1999.
> They are really "verifiable PRFs" but the name is by now standard in the
> crypto literature, and changing it will cause more confusion than keeping
> it.
>
> In terms of the VRF's security properties, there are three:  uniqueness,
> collision resistance, and pseudorandomness. These are defined in our draft (
> https://tools.ietf.org/html/draft-goldbe-vrf-01#section-3).
>
> How VRFs prevent dictionary attacks: a public hash is subject to a
> dictionary attack because, given the output, an adversary can evaluate the
> hash on different inputs and see what hits the outputs. In a VRF, the
> adversary can't evaluate the hash on different inputs.
>
> You say it's not surprising that "random oracle model proof can prove the
> output of a hash to be random". But actually, the output of a hash is NOT
> random if the input and the hash function are known. This is because the
> output of a hash is deterministic (every input maps to a unique output).
> That's exactly what enables dictionary attacks. This is in contrast to a
> VRF, where the output is (pseudo)random even given knowledge of the input.
> Only once the VRF proof is given, does the VRF output stop looking random.
> Note that random oracles are not essential for VRFs, and non-random-oracles
> constructions exist (but are less efficient than what we propose to
> standardize).
>
> As far as use cases, here are a few:
>
> In the NSEC5 use case for DNSSEC, you have sensitive data (domain names)
> and you sign consecutive pairs of hashes of domain names in order to be
> able to prove absence of a name. If you just use standard hashing, whenever
> signed hash values are disclosed, your sensitive data is subject to
> dictionary attacks. VRFs solve that problem, and sensitive names don't have
> to be disclosed at all. More details are in https://eprint.iacr.org/201
> 7/099.pdf
>
> In CONIKS (also Google Key Transparency, Signal secure messaging, Yahoo!
> Coname) you also have some sensitive data (user names) that are put into a
> Merkle-like authenticated data structure. If you just use standard hashing,
> whenever hash values are disclosed, sensitive data is subject to dictionary
> attacks. If you use VRFs, sensitive data again can be disclosed only on an
> as-needed basis. More details are in  https://eprint.iacr.org/2014/
> 1004.pdf.
>
> In a cryptocurrency use case, you wish perform a coin flip that is
> deterministic and provably correct, but cannot be done by just anyone.
> More details are in https://people.csail.mit.ed
> u/nickolai/papers/gilad-algorand-eprint.pdf and possibly other
> cryptocurrency papers.
>
> Bryan Ford mentioned an additional usecase at the mic on Tuesday:
> distributed password protection protocols
>
> Many of these use case are already putting VRFs into production use (esp.
> the CONIKS one).  You can see a list of the various implementations we have
> found in the "implementation status" section of our draft.  One of the
> reasons we think this spec is so important is that we found flaws in
> several of the implementations that can be used to trivially break
> uniqueness.  (See eg: https://github.com/google/keytransparency/issues/567
> )
>
> Thanks,
> Sharon
>
> On Fri, Jul 21, 2017 at 7:32 PM, 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
>>
>
>
>
> --
> ---
> 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
>
>