[Bitcoin-development] Malleable booleans

[Bitcoin-development] Malleable booleans

[Pieter Wuille]

Hi all,

while working on a BIP62 implementation I discovered yet another type
of malleability: the interpretation of booleans.

Any byte array with non-zero bytes in it (ignoring the highest bit of
the last byte, which is the sign bit when interpreting as a number) is
interpreted as true, anything else as false. Other than numbers,
they're not even restricted to 4 bytes. Worse, the code for dealing
with booleans is not very consistent: OP_BOOLAND and OP_BOOLOR first
interpret their arguments as numbers, and then compare them to 0 to
turn them into boolean values.

This means that scripts that use booleans as inputs will be inherently
malleable. Given that that seems actually useful (passing in booleans
to guide some OP_IF's during execution of several alternatives), I
would like to change BIP62 to also state that interpreted booleans
must be of minimal encoded size (in addition to numbers).

Any opinions for or against?

Re: [Bitcoin-development] Malleable booleans

[Gregory Maxwell]

On Tue, Oct 14, 2014 at 2:34 AM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> Hi all,
>
> while working on a BIP62 implementation I discovered yet another type
> of malleability: the interpretation of booleans.
>
> Any byte array with non-zero bytes in it (ignoring the highest bit of
> the last byte, which is the sign bit when interpreting as a number) is
> interpreted as true, anything else as false. Other than numbers,
> they're not even restricted to 4 bytes. Worse, the code for dealing
> with booleans is not very consistent: OP_BOOLAND and OP_BOOLOR first
> interpret their arguments as numbers, and then compare them to 0 to
> turn them into boolean values.
>
> This means that scripts that use booleans as inputs will be inherently
> malleable. Given that that seems actually useful (passing in booleans
> to guide some OP_IF's during execution of several alternatives), I
> would like to change BIP62 to also state that interpreted booleans
> must be of minimal encoded size (in addition to numbers).
>
> Any opinions for or against?


An argument against is that you can currently do something like this:


OP_DUP OP_IF OP_HASH160 PUSH OP_EQUALVERIFY OP_ELSE  <stuff>
OP_CHECKSIGVERIFY OP_ENDIF

E.g. if your input is non-zero you're giving a hash, if it's zero
you're skipping that and running another branch.

Of course you could just encode your script another way... but by that
same logic you can 1 OP_QUALVERIFY to bool-ize any input in the true
path.  The inconsistency in handling makes it more likely that script
authors will screw up with bad (for them) consequences, however.

[I just asked pieter out of band to clarify if he means "minimal
encoded size", or must be 0 or 1 minimally encoded... as the former
doesn't fix the malleability, but the later is more disruptive]

Re: [Bitcoin-development] Malleable booleans

[Thomas Zander]

On Tuesday 14. October 2014 04.34.16 Pieter Wuille wrote:
> This means that scripts that use booleans as inputs will be inherently
> malleable.

I've ran into this issue in C++ often enough,
a funny example is assigning "2" to a native c++ bool and then you can do a
 if (myBool == true)
 else if (myBool == false)
and neither of them will hit.

> I
> would like to change BIP62 to also state that interpreted booleans
> must be of minimal encoded size (in addition to numbers).

What about rejecting a script where a bool is not explicitly zero or one?
-- 
Thomas Zander

Re: [Bitcoin-development] Malleable booleans

[Gregory Maxwell]

On Tue, Oct 14, 2014 at 7:27 AM, Thomas Zander <thomas@thomaszander.se> wrote:
> What about rejecting a script where a bool is not explicitly zero or one?

I believe this is what he actually meant.

Re: [Bitcoin-development] Malleable booleans

[Wladimir]

On Tue, Oct 14, 2014 at 9:27 AM, Thomas Zander <thomas@thomaszander.se> wrote:
> On Tuesday 14. October 2014 04.34.16 Pieter Wuille wrote:
>> This means that scripts that use booleans as inputs will be inherently
>> malleable.
>
> I've ran into this issue in C++ often enough,
> a funny example is assigning "2" to a native c++ bool and then you can do a
>  if (myBool == true)
>  else if (myBool == false)
> and neither of them will hit.

Off topic nit: I think you're confused with custom BOOL typedefs in C?
C++ booleans are protected against this (C++ standard §4.7/4 according
to Google).:

```
#include <stdio.h>

int main()
{
    bool myBool;
    myBool = 2;
    if (myBool == true)
        printf("It is true!\n");
    else if (myBool == false)
        printf("It is false!\n");
    else
        printf("It is something else!\n");
}
```

Prints 'It is true'. You can also use bool(something) as equivalent of
`x != 0`; as in `assert(bool(2) == true);`.

Wladimir

Re: [Bitcoin-development] Malleable booleans

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2252 bytes --]

On Mon, Oct 13, 2014 at 07:34:16PM -0700, Pieter Wuille wrote:
> Hi all,
> 
> while working on a BIP62 implementation I discovered yet another type
> of malleability: the interpretation of booleans.
> 
> Any byte array with non-zero bytes in it (ignoring the highest bit of
> the last byte, which is the sign bit when interpreting as a number) is
> interpreted as true, anything else as false. Other than numbers,
> they're not even restricted to 4 bytes. Worse, the code for dealing
> with booleans is not very consistent: OP_BOOLAND and OP_BOOLOR first
> interpret their arguments as numbers, and then compare them to 0 to
> turn them into boolean values.
> 
> This means that scripts that use booleans as inputs will be inherently
> malleable. Given that that seems actually useful (passing in booleans
> to guide some OP_IF's during execution of several alternatives), I
> would like to change BIP62 to also state that interpreted booleans
> must be of minimal encoded size (in addition to numbers).
> 
> Any opinions for or against?

I noticed this awhile back myself. More interestingly, I remember
noticing some non-std scripts on mainnet that had opcodes that appeared
to be attempts to solve this issue with variations of the following:

    DUP
    IF
        1 EQUALVERIFY
        <do stuff>
    ELSE
        0 EQUALVERIFY
        <do stuff>
    ENDIF

I'll have to admit, I decided to keep quiet about it because it's a good
example of how relying on BIP62 for specialty contract applications that
absolutely need to avoid malleability for security reasons is a dubious
idea; it's hard to be sure that we've really gotten every relevant case
correct.

I think a decent argument *for* doing this is that if a script author
fails to properly 'bool-ize' every boolean-using path that can have
non-minimal encodings in normal execution, you can always create a
nVersion=1 transaction manually to spend the output, preventing funds
from getting lost. Meanwhile in the general case of a compenent script
author having the canonical bool testing in every boolean-using opcode
saves a lot of bytes.

-- 
'peter'[:-1]@petertodd.org
0000000000000000147fe2005d7d4490938a7ab96901b8256dcd9d4eac78cb8c

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [Bitcoin-development] Malleable booleans

[Pieter Wuille]

To be clear: I indeed meant to only allow 0 and 1 as booleans (or,
more precisely: [] and [0x01]). Evaluating any stack element as a
boolean that is not any of these would result in script failure.

The only places where this is relevant:
* Inputs to OP_IF and OP_NOTIF (which are currently allowed to be any
byte array).
* Inputs to OP_BOOLAND and OP_BOOLOR (which are currently allowed to
be any valid number).
* The resulting final element on the stack for validity.

The code for converting stack elements to booleans is also invoked for
all OP_*VERIFY operators, but for those it is always the output of a
previous operator, so it will not have any semantic impact.

On Tue, Oct 14, 2014 at 1:09 AM, Peter Todd <pete@petertodd.org> wrote:
> I noticed this awhile back myself. More interestingly, I remember
> noticing some non-std scripts on mainnet that had opcodes that appeared
> to be attempts to solve this issue with variations of the following:
>
>     DUP
>     IF
>         1 EQUALVERIFY
>         <do stuff>
>     ELSE
>         0 EQUALVERIFY
>         <do stuff>
>     ENDIFo.
>
> I'll have to admit, I decided to keep quiet about it because it's a good
> example of how relying on BIP62 for specialty contract applications that
> absolutely need to avoid malleability for security reasons is a dubious
> idea; it's hard to be sure that we've really gotten every relevant case
> correct.

I think my goal is to have the property that for every possible
script, there is an equivalent one that is non-malleable. There are
likely still holes in that idea, but at least for just standard
scripts I think BIP62 (as is) covers this. And as your example points
out (Greg and I discussed this, though we didn't come up with such a
concise one), it is already possible for boolean inputs too.

> I think a decent argument *for* doing this is that if a script author
> fails to properly 'bool-ize' every boolean-using path that can have
> non-minimal encodings in normal execution, you can always create a
> nVersion=1 transaction manually to spend the output, preventing funds
> from getting lost. Meanwhile in the general case of a compenent script
> author having the canonical bool testing in every boolean-using opcode
> saves a lot of bytes.

The real question is whether there are use cases for not having this
requirement. I can't come up with any, as that would imply a boolean
that is also interpretable as a hash, a pubkey or a signature - all of
which seems crpytographically impossible to ever result in false.

-- 
Pieter

Re: [Bitcoin-development] Malleable booleans

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1410 bytes --]

On Tue, Oct 14, 2014 at 11:54:36AM -0700, Pieter Wuille wrote:
> > I think a decent argument *for* doing this is that if a script author
> > fails to properly 'bool-ize' every boolean-using path that can have
> > non-minimal encodings in normal execution, you can always create a
> > nVersion=1 transaction manually to spend the output, preventing funds
> > from getting lost. Meanwhile in the general case of a compenent script
> > author having the canonical bool testing in every boolean-using opcode
> > saves a lot of bytes.
> 
> The real question is whether there are use cases for not having this
> requirement. I can't come up with any, as that would imply a boolean
> that is also interpretable as a hash, a pubkey or a signature - all of
> which seems crpytographically impossible to ever result in false.

I'm kinda inclined to agree, however there is an opposing argument too:
How often is BOOLAND and BOOLOR applied to unsanitised input from the
scriptSig? I can't think of a script type where that would be the case,
unlike OP_IF where the logical way of writing scripts is to have the
scriptSig select which brance you take. In every script I've ever
thought of BOOLAND and BOOLOR is applied to stuff generated within the
script itself, which isn't a malleability concern.

-- 
'peter'[:-1]@petertodd.org
000000000000000005f3f265a1636bd90c2c8098093c2db2ccfc91c17890a714

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]