[bitcoin-dev] Treating ‘ASICBOOST’ as a Security Vulnerability

[bitcoin-dev] Treating ‘ASICBOOST’ as a Security Vulnerability

[Cameron Garnham]

Hello Bitcoin Development Mailing List,

I wish to explain why the current approach to ‘ASICBOOST’ dose not comply with our established best practices for security vulnerabilities and suggest what I consider to be an approach closer matching established industry best practices.


1.     Significant deviations from the Bitcoin Security Model have been acknowledged as security vulnerabilities.

The Bitcoin Security Model assumes that every input into the Proof-of-Work function should have the same difficulty of producing a desired output.


2.     General ASIC optimisation cannot be considered a Security Vulnerabilities.

Quickly being able to check inputs is not a vulnerability. However, being able to craft inputs that are significantly easier to check than alternative inputs is a vulnerability.


3.     We should assign a CVE to the vulnerability exploited by ‘ASICBOOST’.

‘ASICBOOST’ is an attack on this Bitcoin’s security assumptions and should be considered an exploit of the Bitcoin Proof-of-Work Function.

For a more detailed look at ‘ASICBOOST’, please have a look at this excellent document by Jeremy Rubin:
http://www.mit.edu/~jlrubin//public/pdfs/Asicboost.pdf

The Bitcoin Community should be able to track the progress of restoring the quality of the Bitcoin Proof-of-Work function to its original assumptions.


4.     Work should be taken to prudently and swiftly restore Bitcoins Security Properties.

I recommend the Bitcoin Community fix this vulnerability with expediency.



Cameron.

PS:

With a soft-fork it probably is possible to completely fix this Proof-of-Work vulnerability.

(Here is my working list of things to do):

1.     Include extra data in the Coinbase Transaction, such as the Witness Root.

2.     Lock the Version. (Use a space in the Coinbase Transaction for signalling future upgrades).

3.     Lock the lower-bits on the Timestamp: Block timestamps only need ~1minute granularity.

4.	Make a deterministic ordering of transaction chains within a block. (However, I believe this option is more difficult).

Of course, if we have a hard-fork, we should consider the Proof-of-Work internal merkle structure directly.

Re: [bitcoin-dev] Treating ‘ASICBOOST’ as a Security Vulnerability

[James Hilliard]

Locking the lower bits on the timestamp will likely break existing
hardware that relies on being able to roll ntime.

On Thu, May 18, 2017 at 8:44 AM, Cameron Garnham via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Hello Bitcoin Development Mailing List,
>
> I wish to explain why the current approach to ‘ASICBOOST’ dose not comply with our established best practices for security vulnerabilities and suggest what I consider to be an approach closer matching established industry best practices.
>
>
> 1.     Significant deviations from the Bitcoin Security Model have been acknowledged as security vulnerabilities.
>
> The Bitcoin Security Model assumes that every input into the Proof-of-Work function should have the same difficulty of producing a desired output.
>
>
> 2.     General ASIC optimisation cannot be considered a Security Vulnerabilities.
>
> Quickly being able to check inputs is not a vulnerability. However, being able to craft inputs that are significantly easier to check than alternative inputs is a vulnerability.
>
>
> 3.     We should assign a CVE to the vulnerability exploited by ‘ASICBOOST’.
>
> ‘ASICBOOST’ is an attack on this Bitcoin’s security assumptions and should be considered an exploit of the Bitcoin Proof-of-Work Function.
>
> For a more detailed look at ‘ASICBOOST’, please have a look at this excellent document by Jeremy Rubin:
> http://www.mit.edu/~jlrubin//public/pdfs/Asicboost.pdf
>
> The Bitcoin Community should be able to track the progress of restoring the quality of the Bitcoin Proof-of-Work function to its original assumptions.
>
>
> 4.     Work should be taken to prudently and swiftly restore Bitcoins Security Properties.
>
> I recommend the Bitcoin Community fix this vulnerability with expediency.
>
>
>
> Cameron.
>
> PS:
>
> With a soft-fork it probably is possible to completely fix this Proof-of-Work vulnerability.
>
> (Here is my working list of things to do):
>
> 1.     Include extra data in the Coinbase Transaction, such as the Witness Root.
>
> 2.     Lock the Version. (Use a space in the Coinbase Transaction for signalling future upgrades).
>
> 3.     Lock the lower-bits on the Timestamp: Block timestamps only need ~1minute granularity.
>
> 4.      Make a deterministic ordering of transaction chains within a block. (However, I believe this option is more difficult).
>
> Of course, if we have a hard-fork, we should consider the Proof-of-Work internal merkle structure directly.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Treating ‘ASICBOOST’ as a Security Vulnerability

[Tier Nolan]

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

On Thu, May 18, 2017 at 2:44 PM, Cameron Garnham via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 1.     Significant deviations from the Bitcoin Security Model have been
> acknowledged as security vulnerabilities.
>
> The Bitcoin Security Model assumes that every input into the Proof-of-Work
> function should have the same difficulty of producing a desired output.
>

This isn't really that clear.

Arguably as long as the effort to find a block is proportional to the block
difficulty parameter, then it isn't an exploit.  It is just an optimisation.

A quantum computer, for example, could find a block with effort
proportional to the square root of the difficulty parameter, so that would
count as an attack.  Though in that case, the fix would likely be to tweak
the difficulty parameter update calculation.

A better definition would be something like "when performing work, each
hash should be independent".

ASICBOOST does multiple checks in parallel, so would violate that.

[-- Attachment #2: Type: text/html, Size: 1502 bytes --]

Re: [bitcoin-dev] Treating ‘ASICBOOST’ as a Security Vulnerability

[Cameron Garnham]

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

(message was originally sent off-list by mistake).

Hello Tier,

Thank-you for your insightful reply,

Am I correct that this suggest is that you think it is an optimisation to find some nonces having lower difficulty than other nonces?

I would agree with you if this was limited to a dedicated nonce area of the Bitcoin System.

However, in the case of Bitcoin it is a layer violation that the PoW function difficulty could be affected by the choice the transaction ordering, or the content of the Coinbase Transaction, etc.  Possibly giving unnatural and unintended incentives to other parts of the Bitcoin System.

I can see two issues at play here:

1.	The choice of input, outside of the dedicated nonce area, fed the PoW function should not change it’s difficulty to evaluate.
2.	Every PoW function execution should be independent.

I think that both of these are security assumptions of the Bitcoin PoW function.

I consider ASICBOOST as an attack upon both accounts.

Cameron.

> 
> On 18 May 2017, at 17:59 , Tier Nolan via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> On Thu, May 18, 2017 at 2:44 PM, Cameron Garnham via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 1.     Significant deviations from the Bitcoin Security Model have been acknowledged as security vulnerabilities.
> 
> The Bitcoin Security Model assumes that every input into the Proof-of-Work function should have the same difficulty of producing a desired output.
> 
> This isn't really that clear.
> 
> Arguably as long as the effort to find a block is proportional to the block difficulty parameter, then it isn't an exploit.  It is just an optimisation.
> 
> A quantum computer, for example, could find a block with effort proportional to the square root of the difficulty parameter, so that would count as an attack.  Though in that case, the fix would likely be to tweak the difficulty parameter update calculation.
> 
> A better definition would be something like "when performing work, each hash should be independent".  
> 
> ASICBOOST does multiple checks in parallel, so would violate that.


[-- Attachment #2: Type: text/html, Size: 4866 bytes --]

Re: [bitcoin-dev] Treating ‘ASICBOOST’ as a Security Vulnerability

[Ryan Grant]

On Thu, May 18, 2017 at 9:44 AM, Cameron Garnham via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> 3.     We should assign a CVE to the vulnerability exploited by ‘ASICBOOST’.
>
> ‘ASICBOOST’ is an attack on this Bitcoin’s security assumptions and
> should be considered an exploit of the Bitcoin Proof-of-Work
> Function.

On Thu, May 18, 2017 at 10:59 AM, Tier Nolan via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Arguably as long as the effort to find a block is proportional to the block
> difficulty parameter, then it isn't an exploit.  It is just an optimisation.

One principled way to proceed would be to fault not the exploit, but
the protocol design.

Bits in the block header have been discovered which could be used for
dual meanings, and at least one meaning does not preserve the
incentive balances intended and assumed by others.  This unexpectedly
creates an incentive to block protocol improvements.  The protocol
must be repaired.

In this view, which focuses on covert-ASICBOOST, how work is done is
up to the implementation.  But if the hashing work specified possibly
could gain from blocking development work, then we have a
vulnerability.

I believe this is clear grounds for taking action without any delay.

Re: [bitcoin-dev] Treating ‘ASICBOOST’ as a Security Vulnerability

[Erik Aronesty]

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

ASIC boost is definitely a protocol vulnerability.

It makes Bitcoin resistant to current and future modifications which are
necessary to preserve decentralization.

That alone should be enough to prioritize a swift preventative measure.

On May 18, 2017 3:29 PM, "Ryan Grant via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

On Thu, May 18, 2017 at 9:44 AM, Cameron Garnham via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> 3.     We should assign a CVE to the vulnerability exploited by
‘ASICBOOST’.
>
> ‘ASICBOOST’ is an attack on this Bitcoin’s security assumptions and
> should be considered an exploit of the Bitcoin Proof-of-Work
> Function.

On Thu, May 18, 2017 at 10:59 AM, Tier Nolan via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Arguably as long as the effort to find a block is proportional to the
block
> difficulty parameter, then it isn't an exploit.  It is just an
optimisation.

One principled way to proceed would be to fault not the exploit, but
the protocol design.

Bits in the block header have been discovered which could be used for
dual meanings, and at least one meaning does not preserve the
incentive balances intended and assumed by others.  This unexpectedly
creates an incentive to block protocol improvements.  The protocol
must be repaired.

In this view, which focuses on covert-ASICBOOST, how work is done is
up to the implementation.  But if the hashing work specified possibly
could gain from blocking development work, then we have a
vulnerability.

I believe this is clear grounds for taking action without any delay.
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[-- Attachment #2: Type: text/html, Size: 2797 bytes --]

Re: [bitcoin-dev] Treating ‘ASICBOOST’ as a Security Vulnerability

[Cameron Garnham]

Hello Bitcoin-Dev,

A quick update that CVE-2017-9230 has been assigned for the security vulnerability commonly called ‘ASICBOOST’:

"The Bitcoin Proof-of-Work algorithm does not consider a certain attack methodology related to 80-byte block headers with a variety of initial 64-byte chunks followed by the same 16-byte chunk, multiple candidate root values ending with the same 4 bytes, and calculations involving sqrt numbers. This violates the security assumptions of (1) the choice of input, outside of the dedicated nonce area, fed into the Proof-of-Work function should not change its difficulty to evaluate and (2) every Proof-of-Work function execution should be independent.”

I would like to especially thank the CVE team at Mitre for their suggested description that was more appropriate than my proposed text.

https://cve.mitre.org/cgi-bin/cvename.cgi?name=+CVE-2017-9230

Cameron.



> Begin forwarded message:
> 
> From: <cve-request@mitre.org>
> Subject: Re: [scr-xxxxx] Bitcoin - All
> Date: 24 May 2017 at 18:52:22 GMT+3
> To: <da2ce7@gmail.com>
> Cc: <cve-request@mitre.org>
> 
> Signed PGP part
> > [Suggested description]
> > The Bitcoin Proof-of-Work algorithm does not consider a certain attack
> > methodology related to 80-byte block headers with a variety of initial
> > 64-byte chunks followed by the same 16-byte chunk, multiple candidate
> > root values ending with the same 4 bytes, and calculations involving
> > sqrt numbers. This violates the security assumptions of (1) the choice
> > of input, outside of the dedicated nonce area, fed into the
> > Proof-of-Work function should not change its difficulty to evaluate
> > and (2) every Proof-of-Work function execution should be independent.
> >
> > ------------------------------------------
> >
> > [Additional Information]
> > ASICBOOST, originality promoted as a patented mining optimisation(1).
> > Has under detailed study (2), become regarded as an actively exploited
> > (3), security vulnerability (4), of Bitcoin.
> >
> > The Bitcoin Proof-of-Work Algorithm is dependent on the following two
> > security assumptions that are both broken by 'ASICBOOST':
> > 1. The choice of input, outside of the dedicated nonce area, fed into
> > the Proof-of-Work function should not change it's difficulty to
> > evaluate.
> > 2.  Every Proof-of-Work function execution should be independent.
> >
> > 'ASICBOOST' creates a layer-violation where the structure of the input
> > outside of the dedicated nonce area will change the performance of the
> > mining calculations (5). 'ASICBOOST' exploits a vulnerability where
> > the Proof-of-Work function execution is not independent (6).
> >
> > References:
> > (1) Original Whitepaper by Dr. Timo Hanke: https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf
> > (2) Academic Write-up by Jeremy Rubin: http://www.mit.edu/~jlrubin//public/pdfs/Asicboost.pdf
> > (3) Evidence of Active Exploit by Gregory Maxwell:
> >  https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/013996.html
> > (4) Discussion to assign a CVE Number, by Cameron Garnham:
> >   https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014349.html
> > (5) Discussion of the perverse incentives created by 'ASICBOOST' by Ryan Grant:
> >   https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014352.html
> > (6) Discussion of ASICBOOST's non-independent PoW calculation by Tier Nolan:
> >   https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014351.html
> >
> > The patent holder of this particular security vulnerability has a dedicated website: https://www.asicboost.com/
> >
> > ------------------------------------------
> >
> > [VulnerabilityType Other]
> > Cryptocurrency Mining Algorithm Weakness
> >
> > ------------------------------------------
> >
> > [Vendor of Product]
> > Bitcoin
> >
> > ------------------------------------------
> >
> > [Affected Product Code Base]
> > Bitcoin - All
> >
> > ------------------------------------------
> >
> > [Affected Component]
> > Bitcoin
> >
> > ------------------------------------------
> >
> > [Attack Type Other]
> > Cryptocurrency Proof-of-Work Algorithm Weakness
> >
> > ------------------------------------------
> >
> > [CVE Impact Other]
> > Creation of Perverse Incentives in a Cryptocurrency
> >
> > ------------------------------------------
> >
> > [Attack Vectors]
> > Bitcoin Mining Unfair Advantage
> > Bitcoin Layer-Violations Creating Perverse System Incentives
> >
> > ------------------------------------------
> >
> > [Reference]
> > https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf
> > http://www.mit.edu/~jlrubin//public/pdfs/Asicboost.pdf
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/013996.html
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014349.html
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014352.html
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014351.html
> >
> > ------------------------------------------
> >
> > [Has vendor confirmed or acknowledged the vulnerability?]
> > true
> >
> > ------------------------------------------
> >
> > [Discoverer]
> > Original Discovery: Dr. Timo Hanke and Sergio Lerner. Proof of Active
> > Exploit: Gregory Maxwell. CVE Reporter: Cameron Garnham
> 
> Use CVE-2017-9230.
> 
> 
> --
> CVE Assignment Team
> M/S M300, 202 Burlington Road, Bedford, MA 01730 USA
> [ A PGP key is available for encrypted communications at
>   http://cve.mitre.org/cve/request_id.html ]
>