Re: [Lightning-dev] [bitcoin-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Jeremy]

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
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] [bitcoin-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Peter Todd]

On Sun, Oct 06, 2019 at 08:46:59AM +, ZmnSCPxj wrote:
> > Obviously with care you can get the computation right. But at that point 
> > what's
> > the actual advantage over OP_CAT?
> >
> > We're limited by the size of the script anyway; if the OP_CAT output size 
> > limit
> > is comparable to that for almost anything you could use SHA256STREAM on you
> > could just as easily use OP_CAT, followed by a single OP_SHA256.
> 
> Theoretically, `OP_CAT` is less efficient.
> 
> In cases where the memory area used to back the data cannot be resized, new 
> backing memory must be allocated elsewhere and the existing data copied.
> This leads to possible O( n^2 ) behavior for `OP_CAT` (degenerate case where 
> we add 1 byte per `OP_CAT` and each time find that the memory area currently 
> in use is exactly fitting the data and cannot be resized in-place).

In even that degenerate case allocators also free memory.

Anyway, every execution step in script evaluation has a maximum output size,
and the number of steps is limited. At worst you can allocate the entire
possible stack up-front for relatively little cost (eg fitting in the MB or two
that is a common size for L2 cache).

> Admittedly a sufficiently-limited  maximum `OP_CAT` output would be helpful 
> in reducing the worst-case `OP_CAT` behavior.
> The question is what limit would be reasonable.
> 64 bytes feels too small if one considers Merkle tree proofs, due to 
> mentioned issues of lack of typechecking.

256 bytes is more than enough for even the most complex summed merkle tree with
512-byte hashes and full-sized sum commitments. Yet that's still less than the
~500byte limit proposed elsewhere.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


signature.asc
Description: PGP signature
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] [bitcoin-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[ZmnSCPxj via Lightning-dev]

Good morning Peter, Jeremy, and lists,

> On Fri, Oct 04, 2019 at 11:40:53AM -0700, Jeremy wrote:
>
> > 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?
>
> Obviously with care you can get the computation right. But at that point 
> what's
> the actual advantage over OP_CAT?
>
> We're limited by the size of the script anyway; if the OP_CAT output size 
> limit
> is comparable to that for almost anything you could use SHA256STREAM on you
> could just as easily use OP_CAT, followed by a single OP_SHA256.

Theoretically, `OP_CAT` is less efficient.

In cases where the memory area used to back the data cannot be resized, new 
backing memory must be allocated elsewhere and the existing data copied.
This leads to possible O( n^2 ) behavior for `OP_CAT` (degenerate case where we 
add 1 byte per `OP_CAT` and each time find that the memory area currently in 
use is exactly fitting the data and cannot be resized in-place).

`OP_SHASTREAM` would not require new allocations once the stream state is in 
place and would not require any copying.


This may be relevant in considering the cost of executing `OP_CAT`.

Admittedly a sufficiently-limited  maximum `OP_CAT` output would be helpful in 
reducing the worst-case `OP_CAT` behavior.
The question is what limit would be reasonable.
64 bytes feels too small if one considers Merkle tree proofs, due to mentioned 
issues of lack of typechecking.


Regards,
ZmnSCPxj


>
> --
>
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] [bitcoin-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Peter Todd]

On Fri, Oct 04, 2019 at 11:40:53AM -0700, Jeremy wrote:
> 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?

Obviously with care you can get the computation right. But at that point what's
the actual advantage over OP_CAT?

We're limited by the size of the script anyway; if the OP_CAT output size limit
is comparable to that for almost anything you could use SHA256STREAM on you
could just as easily use OP_CAT, followed by a single OP_SHA256.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


signature.asc
Description: PGP signature
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] [bitcoin-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Peter Todd]

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


signature.asc
Description: PGP signature
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev