From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 540E6A1B for ; Tue, 12 Jan 2016 23:22:19 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f45.google.com (mail-wm0-f45.google.com [74.125.82.45]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8A26014F for ; Tue, 12 Jan 2016 23:22:18 +0000 (UTC) Received: by mail-wm0-f45.google.com with SMTP id f206so274080947wmf.0 for ; Tue, 12 Jan 2016 15:22:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=z-cash.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc :content-type:content-transfer-encoding; bh=JhlnDR78yvZX6/A6NmsKrkLAf90xzzS2HX6NCF8ypl0=; b=nqG4kk3jQgooKBD3gBKU9ot8FHmiLHHWptN+qSFtqnyEoCcbbUBiYhcZS8fV4ttYR9 nNy03skCabdhJss3L4SepEU4+3BT1KPTiEB6HkJrp4kU+JXhq/yI0g7hwzNPkW618BSr dXEv0xpFuE1uhzKEqAyFzzihFLh7y9Zu0FzI8TP9ozei5+mG4gSQsjzw50bF18y++VLG Eu6Y9c+9CNpsctRpTCdi4bfcjrCzwplDr7WTtdB5gdDvsXiVh5eL+ZCHczMlGwOZN/pc WjGjaepDoCRdM8Lp5xvqVnbMYKqNASla6rvtHHdSrkqEI3djiOjOKwbRDbDbm6+hLzWi ppDg== 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:date :message-id:subject:from:cc:content-type:content-transfer-encoding; bh=JhlnDR78yvZX6/A6NmsKrkLAf90xzzS2HX6NCF8ypl0=; b=fP4ZuNXWLRArQmzO25RNSFi78SPYqrwzOpqsP0i2KuKu64nXkORilSXkVgbg6EA4l6 +16PO+hKyqkhrR36TLCHTP0M+HrOfQRXDMQcqXwXF2jh2IfNzRZAbfP9XpwyXx5NvzX8 mRPVwfaio0GAR/iM0FozORUvYTdRoZtJkqlTtnJpBWGKoxFXpz3PcYiyHTEw7YdaQ/59 pHZkggPEvxFWclcl+9XLAqySbOuPNYQkqB/ry9tOcaXKEQ7EmIZ4m8puZ3N4QHG1yRM4 4o0uLAMWeAiTsRLV/CHX6xrgkWV8bkGKwGE5vzVhy1pVmvS/0+9ArT/dvwOfRsMy6J/R 04iw== X-Gm-Message-State: ALoCoQkVzKju2hhx2Tv8JKnx5xfUqihIU1w513lVbJwGnTNBHcjIrqSwLyk/EZYKlp2NIQPyuDvqND42uQJi53e/Y72bW+FTGQ== MIME-Version: 1.0 X-Received: by 10.194.113.227 with SMTP id jb3mr15413425wjb.49.1452640937176; Tue, 12 Jan 2016 15:22:17 -0800 (PST) Received: by 10.28.96.197 with HTTP; Tue, 12 Jan 2016 15:22:17 -0800 (PST) X-Originating-IP: [24.9.79.61] In-Reply-To: References: <8760z4rbng.fsf@rustcorp.com.au> <8737u8qnye.fsf@rustcorp.com.au> <20160108153329.GA15731@sapphire.erisian.com.au> Date: Tue, 12 Jan 2016 23:22:17 +0000 Message-ID: From: "Zooko Wilcox-O'Hearn" Cc: Bitcoin Dev Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-1.6 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, MISSING_HEADERS, RCVD_IN_DNSWL_LOW autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Tue, 12 Jan 2016 23:23:41 +0000 Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not? X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 12 Jan 2016 23:22:19 -0000 Folks: I don't fully understand this thread, but it sounds like to me it might be omitting consideration of multi-target attacks. For example, Tier Nolan's attack (http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012230= .html), which seems to be the best attack on this thread, seems to start with one specific public key of an intended victim, but if the attacker is happy to find a collision with *any* one out of a large number of potential victims, he gets an advantage proportional to the number of potential victims. So it would be wise, in addition to the kind of analysis already done on this thread (which appears to have already settled at "Yes, we need > 80-bit security."), to make a nice optimistic estimate of how many public keys we could eventually have in use. 2=E2=81=B4=E2=81=B0? 2=E2=81= =B5=E2=81=B0? Or maybe be *very* optimistic, with some added IoT [*] goodness, and budget for 2=E2=81=B6=E2=81=B0? Then we need to budget that many more bits of security to keep the future attacker's chances of success low enough that the attacker will never succeed. (Assuming that's our requirement.) You might enjoy this recent blog post by DJB, legendary cryptographer who works in this niche of cryptography as well as several other niches: http://blog.cr.yp.to/20151120-batchattacks.html It has some interesting philosophical musings about the "Attacker Economist" approach. (N.B. My respect for DJB's accomplishments is tremendous, but that doesn't mean I automatically agree with everything he says. I haven't made up my mind what I think about this particular philosophical argument.) Sincerely, Zooko [*] The Internet of Targets