Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 00D53D7E; Fri, 4 Oct 2019 18:41:08 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4A35D735; Fri, 4 Oct 2019 18:41:07 +0000 (UTC) Received: from mail-io1-f49.google.com (mail-io1-f49.google.com [209.85.166.49]) (authenticated bits=0) (User authenticated as jlrubin@ATHENA.MIT.EDU) by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id x94If5Vk032243 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT); Fri, 4 Oct 2019 14:41:05 -0400 Received: by mail-io1-f49.google.com with SMTP id z19so15791469ior.0; Fri, 04 Oct 2019 11:41:05 -0700 (PDT) X-Gm-Message-State: APjAAAUgueGOyBnK1g1expWdlupR1LQjeR3emk2XzTD3rADIDl8oUXmS mMOLktY8c9p/PDWy8RbSzsYYrcIU5Lwq+81zjBU= X-Google-Smtp-Source: APXvYqyHb3F6Y7Wiau1aPPSs3v3RtpD8gKyBhfkUSAV8cIm1qGI9cSCSN9du0ybmU2NyOpW8QZoHeNWKrLp8u4JsLzg= X-Received: by 2002:a92:9:: with SMTP id 9mr17774535ila.49.1570214465026; Fri, 04 Oct 2019 11:41:05 -0700 (PDT) MIME-Version: 1.0 References: <87wodp7w9f.fsf@gmail.com> <20191001155929.e2yznsetqesx2jxo@erisian.com.au> <20191004111536.w7snbgpoe27xutfu@petertodd.org> In-Reply-To: <20191004111536.w7snbgpoe27xutfu@petertodd.org> From: Jeremy Date: Fri, 4 Oct 2019 11:40:53 -0700 X-Gmail-Original-Message-ID: Message-ID: To: Peter Todd Content-Type: multipart/alternative; boundary="00000000000068c19c05941a0b9a" X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,HTML_MESSAGE, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Protocol Discussion , "lightning-dev@lists.linuxfoundation.org" Subject: Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 04 Oct 2019 18:41:08 -0000 --00000000000068c19c05941a0b9a Content-Type: text/plain; charset="UTF-8" Interesting point. The script is under your control, so you should be able to ensure that you are always using a correctly constructed midstate, e.g., something like: scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM <-2> OP_SHA256STREAM OP_EQUALVERIFY would hash all the elements on the stack and compare to a known hash. How is that sort of thing weak to midstateattacks? -- @JeremyRubin On Fri, Oct 4, 2019 at 4:16 AM Peter Todd wrote: > On Thu, Oct 03, 2019 at 10:02:14PM -0700, Jeremy via bitcoin-dev wrote: > > Awhile back, Ethan and I discussed having, rather than OP_CAT, an > > OP_SHA256STREAM that uses the streaming properties of a SHA256 hash > > function to allow concatenation of an unlimited amount of data, provided > > the only use is to hash it. > > > > You can then use it perhaps as follows: > > > > // start a new hash with item > > OP_SHA256STREAM (-1) -> [state] > > // Add item to the hash in state > > OP_SHA256STREAM n [item] [state] -> [state] > > // Finalize > > OP_SHA256STREAM (-2) [state] -> [Hash] > > > > <-1> OP_SHA256STREAM <3> OP_SHA256STREAM > <-2> > > OP_SHA256STREAM > > One issue with this is the simplest implementation where the state is just > raw > bytes would expose raw SHA256 midstates, allowing people to use them > directly; > preventing that would require adding types to the stack. Specifically I > could > write a script that rather than initializing the state correctly from the > official IV, instead takes an untrusted state as input. > > SHA256 isn't designed to be used in situations where adversaries control > the > initialization vector. I personally don't know one way or the other if > anyone > has analyzed this in detail, but I'd be surprised if that's secure. I > considered adding midstate support to OpenTimestamps but decided against > it for > exactly that reason. > > I don't have the link handy but there's even an example of an experienced > cryptographer on this very list (bitcoin-dev) proposing a design that falls > victim to this attack. It's a subtle issue and we probably don't want to > encourage it. > > -- > https://petertodd.org 'peter'[:-1]@petertodd.org > _______________________________________________ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > --00000000000068c19c05941a0b9a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Interesting point.

The script is under your control, so you should be able to ensure that= you are always using a correctly constructed midstate, e.g., something lik= e:

scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM= <-2> OP_SHA256STREAM
<hash> OP_EQUALVERIFY

would hash all the elements on the stack and compare to a known hash.
=
How is that sort of thing weak to midstatea= ttacks?




On Fri, Oct 4, 20= 19 at 4:16 AM Peter Todd <pete@pet= ertodd.org> wrote:
On Thu, Oct 03, 2019 at 10:02:14PM -0700, Jeremy via bitcoin-dev= wrote:
> Awhile back, Ethan and I discussed having, rather than OP_CAT, an
> OP_SHA256STREAM that uses the streaming properties of a SHA256 hash > function to allow concatenation of an unlimited amount of data, provid= ed
> the only use is to hash it.
>
> You can then use it perhaps as follows:
>
> // start a new hash with item
> OP_SHA256STREAM=C2=A0 (-1) -> [state]
> // Add item to the hash in state
> OP_SHA256STREAM n [item] [state] -> [state]
> // Finalize
> OP_SHA256STREAM (-2) [state] -> [Hash]
>
> <-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3= > <3> OP_SHA256STREAM <-2>
> OP_SHA256STREAM

One issue with this is the simplest implementation where the state is just = raw
bytes would expose raw SHA256 midstates, allowing people to use them direct= ly;
preventing that would require adding types to the stack. Specifically I cou= ld
write a script that rather than initializing the state correctly from the official IV, instead takes an untrusted state as input.

SHA256 isn't designed to be used in situations where adversaries contro= l the
initialization vector. I personally don't know one way or the other if = anyone
has analyzed this in detail, but I'd be surprised if that's secure.= I
considered adding midstate support to OpenTimestamps but decided against it= for
exactly that reason.

I don't have the link handy but there's even an example of an exper= ienced
cryptographer on this very list (bitcoin-dev) proposing a design that falls=
victim to this attack. It's a subtle issue and we probably don't wa= nt to
encourage it.

--
http= s://petertodd.org 'peter'[:-1]@petertodd.org
_______________________________________________
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/ma= ilman/listinfo/lightning-dev
--00000000000068c19c05941a0b9a--