Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Steve Davis via bitcoin-dev]

> On Feb 26, 2017, at 12:36 AM, Pieter Wuille  wrote:
> 
> The 80-bit collision attack only applies to jointly constructed addresses 
> like multisig P2SH, not single-key ones.

That’s the part I’m less convinced about, and why I asked the original question 
re SHA1 vs RIPEMD. 

I’m checking my own numbers (and as you’ll appreciate it’s a powers of ten 
thing), but I do see a vector. Which would mean that if RIPEMD were weakened in 
any way, single-key transactions could suddenly become badly exposed.

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

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Steve Davis via bitcoin-dev]

Hi Pieter,

> On Feb 25, 2017, at 4:14 PM, Pieter Wuille  wrote:
> 
> Any alternative to move us away from RIPEMD160 would require:

> 

“Any alternative”? What about reverting to:

[, OP_CHECKSIG]

or perhaps later

[<“compressed” public_key>, OP_CHECKSIG]

This appears to get away from the issue without introducing a lot of other 
concerns?

(IIRC the RIPEMD thing was justified on convenience and compactness).

Could that be the alternative?

/s

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

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Pieter Wuille via bitcoin-dev]

On Feb 25, 2017 22:26, "Steve Davis"  wrote:

Hi Pieter,

> On Feb 25, 2017, at 4:14 PM, Pieter Wuille 
wrote:
>
> Any alternative to move us away from RIPEMD160 would require:

> 

“Any alternative”? What about reverting to:

[, OP_CHECKSIG]


snip


Could that be the alternative?


Ok, fair enough, that is an alternative that avoids the 160-bit hash
function, but not where it matters. The 80-bit collision attack only
applies to jointly constructed addresses like multisig P2SH, not single-key
ones. As far as I know for those we only rely preimage security, and
RIPEMD160 has 160 bit security there, which is even more than our ECDSA
signatures offer.

-- 
Pieter
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] Moving towards user activated soft fork activation

[shaolinfry via bitcoin-dev]

Some thoughts about the activation mechanism for soft forks. In the past we 
used IsSuperMajority and currently use BIP9 as soft fork activation methods, 
where a supermajority of hashrate triggers nodes to begin enforcing new rules. 
Hashrate based activation is convenient because it is the simplest and most 
straightforward process. While convenient there are a number limitations with 
this method.

Firstly, it requires trusting the hash power will validate after activation. 
The BIP66 soft fork was a case where 95% of the hashrate was signaling 
readiness but in reality about half was not actually validating the upgraded 
rules and mined upon an invalid block by mistake[1].

Secondly, miner signalling has a natural veto which allows a small percentage 
of hashrate to veto node activation of the upgrade for everyone. To date, soft 
forks have taken advantage of the relatively centralised mining landscape where 
there are relatively few mining pools building valid blocks; as we move towards 
more hashrate decentralization, it's likely that we will suffer more and more 
from "upgrade inertia" which will veto most upgrades.

Upgrade inertia in inevitable for widely deployed software and can be seen for 
example, with Microsoft Windows. At the time of writing 5.72% of all Microsoft 
Windows installations are still running Windows XP, despite mainstream support 
ending in 2009 and being superseded by 4 software generations, Vista, 7, 8 and 
10.

Thirdly, the signaling methodology is widely misinterpreted to mean the hash 
power is voting on a proposal and it seems difficult to correct this 
misunderstanding in the wider community. The hash powers' role is to select 
valid transactions, and to extend the blockchain with valid blocks. Fully 
validating economic nodes ensure that blocks are valid. Nodes therefore define 
validity according to the software they run, but miners decide what already 
valid transactions gets included in the block chain.

As such, soft forks rules are actually always enforced by the nodes, not the 
miners. Miners of course can opt-out by simply not including transactions that 
use the new soft fork feature, but they cannot produce blocks that are invalid 
to the soft fork. The P2SH soft fork is a good example of this, where 
non-upgraded miners would see P2SH as spendable without a signature and 
consider them valid. If such an transaction were to be included in a block, the 
block would be invalid and the miner would lose the block reward and fees.

So-called "censorship" soft forks do not require nodes to opt in, because >51% 
of the hash power already have the ability to orphan blocks that contain 
transactions they have blacklisted. Since this is not a change in validity, 
nodes will accept the censored block chain automatically.

The fourth problem with supermajority hash power signaling is it draws 
unnecessary attention to miners which can become unnecessarily political. 
Already misunderstood as a vote, miners may feel pressure to "make a decision" 
on behalf of the community: who is and isn't signalling becomes a huge public 
focus and may put pressures onto miners they are unprepared for. Some miners 
may not be in a position to upgrade, or may prefer not to participate in the 
soft fork which is their right. However, that miner may now become a lone 
reason that vetoes activation for everyone, where the soft fork is an opt-in 
feature! This situation seems to be against the voluntary nature of the Bitcoin 
system where participation at all levels is voluntary and kept honest by well 
balanced incentives.

Since miners already have the protocol level right to select whatever 
transaction they prefer (and not mine those they don't), it would be better if 
a miner could chose to not participate in triggering activation of something 
they won't use, but, without being a veto to the process (and all the ire they 
may have to experience as a consequence).

The alternative discussed here is "flag day activation" where nodes begin 
enforcement at a predetermined time in the future. This method needs a longer 
lead time than a hash power based activation trigger, but offers a number of 
advantages and perhaps provides a better tradeoff.

Soft forks are still entirely optional to use post activation. For example, 
with P2SH, many participants in the Bitcoin ecosystem still do not use P2SH. 
Only 11% of bitcoins[2] are stored in P2SH addresses at the time of writing. 
Miners are free to not mine P2SH transactions, however, the incentives are such 
that miners should still validate transactions so they don't accidentally 
include invalid transactions and cause their block to be rejected. As an 
additional safety measure for well designed soft forks, relay policy rules 
prevent non-standard and invalid transactions from being relayed and mined by 
default; a miner would have to purposefully mine an invalid transaction, which 
is against their own economic interest.

Since the incentives

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Leandro Coutinho via bitcoin-dev]

If people split their bitcoins in multiple addresses, then maybe there
would be no need to worry(?), because the computational cost would be
higher than what the attacker would get.


>From Google:
https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

*Here are some numbers that give a sense of how large scale this
computation was: *

   - *Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in
   total*
   - *6,500 years of CPU computation to complete the attack first phase*
   - *110 years of GPU computation to complete the second phase*


https://bitinfocharts.com/top-100-richest-bitcoin-addresses.html
Richest address: 124,178 BTC ($142,853,079 USD)



On Sat, Feb 25, 2017 at 6:40 PM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Sat, Feb 25, 2017 at 03:34:33PM -0600, Steve Davis wrote:
> > Yea, well. I don’t think it is ethical to post instructions without an
> associated remediation (BIP) if you don’t see the potential attack.
>
> I can't agree with you at all there: we're still at the point where the
> computational costs of such attacks limit their real-world impact, which is
> exactly when you want the *maximum* exposure to what they are and what the
> risks are, so that people develop mitigations.
>
> Keeping details secret tends to keep the attacks out of public view, which
> might be a good trade-off in a situation where the attacks are immediately
> practical and the need to deploy a fix is well understood. But we're in the
> exact opposite situation.
>
> > I was rather hoping that we could have a fuller discussion of what the
> best practical response would be to such an issue?
>
> Deploying segwit's 256-bit digests is a response that's already fully
> coded and
> ready to deploy, with the one exception of a new address format. That
> address
> format is being actively worked on, and could be deployed relatively
> quickly if
> needed.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Ethan Heilman via bitcoin-dev]

I strongly encourage Bitcoin to move from 80-bit collision resistance
(RIPEMD-160) to 128-bit collision resistance (SHA-256).

On Sat, Feb 25, 2017 at 5:14 PM, Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
>
> On Feb 25, 2017 14:09, "Steve Davis via bitcoin-dev"  linuxfoundation.org> wrote:
>
> Hi Peter,
>
>
> I really, really don’t want to get into it but segwit has many aspects
> that are less appealing, not least of which being the amount of time it
> would take to reach the critical mass.
>
> Surely there's a number of alternative approaches which could be explored,
> even if only to make a fair assessment of a best response?
>
>
> Any alternative to move us away from RIPEMD160 would require:
> * A drafting of a softfork proposal, implementation, testing, review.
> * A new address format
> * Miners accepting the new consensus rules
> * Wallets adopting the new address format, both on the sender side and
> receiver side (which requires new signatures).
>
> I.e., exactly the same as segwit, for which most of these are already
> done. And it would still only apply to wallets adopting it.
>
> --
> Pieter
>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Pieter Wuille via bitcoin-dev]

On Feb 25, 2017 14:09, "Steve Davis via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

Hi Peter,


I really, really don’t want to get into it but segwit has many aspects that
are less appealing, not least of which being the amount of time it would
take to reach the critical mass.

Surely there's a number of alternative approaches which could be explored,
even if only to make a fair assessment of a best response?


Any alternative to move us away from RIPEMD160 would require:
* A drafting of a softfork proposal, implementation, testing, review.
* A new address format
* Miners accepting the new consensus rules
* Wallets adopting the new address format, both on the sender side and
receiver side (which requires new signatures).

I.e., exactly the same as segwit, for which most of these are already done.
And it would still only apply to wallets adopting it.

-- 
Pieter
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Steve Davis via bitcoin-dev]

Hi Peter,

> On Feb 25, 2017, at 3:40 PM, Peter Todd  wrote:
> 
> On Sat, Feb 25, 2017 at 03:34:33PM -0600, Steve Davis wrote:
>> Yea, well. I don’t think it is ethical to post instructions without an 
>> associated remediation (BIP) if you don’t see the potential attack.
> 
> I can't agree with you at all there: we're still at the point where the
> computational costs of such attacks limit their real-world impact, which is
> exactly when you want the *maximum* exposure to what they are and what the
> risks are, so that people develop mitigations.
> 

I agree with the latter part of your statement but am actually much less 
confident about the first part… I need to run some numbers on that.

> Keeping details secret tends to keep the attacks out of public view, which
> might be a good trade-off in a situation where the attacks are immediately
> practical and the need to deploy a fix is well understood. But we're in the
> exact opposite situation.
> 
>> I was rather hoping that we could have a fuller discussion of what the best 
>> practical response would be to such an issue?
> 
> Deploying segwit's 256-bit digests is a response that's already fully coded 
> and
> ready to deploy, with the one exception of a new address format. That address
> format is being actively worked on, and could be deployed relatively quickly 
> if
> needed.
> 

I really, really don’t want to get into it but segwit has many aspects that are 
less appealing, not least of which being the amount of time it would take to 
reach the critical mass. 

Surely there's a number of alternative approaches which could be explored, even 
if only to make a fair assessment of a best response?

/s
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Steve Davis via bitcoin-dev]

Yea, well. I don’t think it is ethical to post instructions without an 
associated remediation (BIP) if you don’t see the potential attack.

I was rather hoping that we could have a fuller discussion of what the best 
practical response would be to such an issue?


> On Feb 25, 2017, at 3:21 PM, Dave Scotese  wrote:
> 
> I was under the impression that RIPEMD160(SHA256(msg)) is used to turn a 
> PUBLIC key (msg) into a bitcoin address, so yeah, you could identify ANOTHER 
> (or the same, I guess - how would you know?) public key that has the same 
> bitcoin address if RIPEMD-160 collisions are easy, but I don't see how that 
> has any effect on anyone.  Maybe I'm restating what Peter wrote.  If so, 
> confirmation would be nice.
> 
> On Sat, Feb 25, 2017 at 1:04 PM, Peter Todd via bitcoin-dev 
>  > wrote:
> On Sat, Feb 25, 2017 at 03:53:12PM -0500, Russell O'Connor wrote:
> > On Sat, Feb 25, 2017 at 2:12 PM, Peter Todd via bitcoin-dev <
> > bitcoin-dev@lists.linuxfoundation.org 
> > > wrote:
> >
> > > On Sat, Feb 25, 2017 at 11:10:02AM -0500, Ethan Heilman via bitcoin-dev
> > > wrote:
> > > > >SHA1 is insecure because the SHA1 algorithm is insecure, not because
> > > > 160bits isn't enough.
> > > >
> > > > I would argue that 160-bits isn't enough for collision resistance.
> > > Assuming
> > > > RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle),
> > > collisions
> > >
> > > That's something that we're well aware of; there have been a few
> > > discussions on
> > > this list about how P2SH's 160-bits is insufficient in certain use-cases
> > > such
> > > as multisig.
> > >
> > > However, remember that a 160-bit *security level* is sufficient, and
> > > RIPEMD160
> > > has 160-bit security against preimage attacks. Thus things like
> > > pay-to-pubkey-hash are perfectly secure: sure you could generate two
> > > pubkeys
> > > that have the same RIPEMD160(SHA256()) digest, but if someone does that it
> > > doesn't cause the Bitcoin network itself any harm, and doing so is
> > > something
> > > you choose to do to yourself.
> > >
> >
> > Be aware that the issue is more problematic for more complex contracts.
> > For example, you are building a P2SH 2-of-2 multisig together with someone
> > else if you are not careful, party A can hand their key over to party B,
> > who can may try to generate a collision between their second key and
> > another 2-of-2 multisig where they control both keys. See
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012205.html
> >  
> > 
> 
> I'm very aware of that, in fact I think I may have even been the first person
> to post on this list the commit-reveal mitigation.
> 
> Note how I said earlier in the message you're replying to that "P2SH's 
> 160-bits
> is insufficient in certain use-cases such as multisig"
> 
> --
> https://petertodd.org  'peter'[:-1]@petertodd.org 
> 
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org 
> 
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev 
> 
> 
> 
> 
> 
> -- 
> I like to provide some work at no charge to prove my value. Do you need a 
> techie?  
> I own Litmocracy  and Meme Racing 
>  (in alpha). 
> I'm the webmaster for The Voluntaryist  which 
> now accepts Bitcoin.
> I also code for The Dollar Vigilante .
> "He ought to find it more profitable to play by the rules" - Satoshi Nakamoto

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

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Peter Todd via bitcoin-dev]

On Sat, Feb 25, 2017 at 03:34:33PM -0600, Steve Davis wrote:
> Yea, well. I don’t think it is ethical to post instructions without an 
> associated remediation (BIP) if you don’t see the potential attack.

I can't agree with you at all there: we're still at the point where the
computational costs of such attacks limit their real-world impact, which is
exactly when you want the *maximum* exposure to what they are and what the
risks are, so that people develop mitigations.

Keeping details secret tends to keep the attacks out of public view, which
might be a good trade-off in a situation where the attacks are immediately
practical and the need to deploy a fix is well understood. But we're in the
exact opposite situation.

> I was rather hoping that we could have a fuller discussion of what the best 
> practical response would be to such an issue?

Deploying segwit's 256-bit digests is a response that's already fully coded and
ready to deploy, with the one exception of a new address format. That address
format is being actively worked on, and could be deployed relatively quickly if
needed.

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


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Dave Scotese via bitcoin-dev]

I was under the impression that RIPEMD160(SHA256(msg)) is used to turn a
PUBLIC key (msg) into a bitcoin address, so yeah, you could identify
ANOTHER (or the same, I guess - how would you know?) public key that has
the same bitcoin address if RIPEMD-160 collisions are easy, but I don't see
how that has any effect on anyone.  Maybe I'm restating what Peter wrote.
If so, confirmation would be nice.

On Sat, Feb 25, 2017 at 1:04 PM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Sat, Feb 25, 2017 at 03:53:12PM -0500, Russell O'Connor wrote:
> > On Sat, Feb 25, 2017 at 2:12 PM, Peter Todd via bitcoin-dev <
> > bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > > On Sat, Feb 25, 2017 at 11:10:02AM -0500, Ethan Heilman via bitcoin-dev
> > > wrote:
> > > > >SHA1 is insecure because the SHA1 algorithm is insecure, not because
> > > > 160bits isn't enough.
> > > >
> > > > I would argue that 160-bits isn't enough for collision resistance.
> > > Assuming
> > > > RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle),
> > > collisions
> > >
> > > That's something that we're well aware of; there have been a few
> > > discussions on
> > > this list about how P2SH's 160-bits is insufficient in certain
> use-cases
> > > such
> > > as multisig.
> > >
> > > However, remember that a 160-bit *security level* is sufficient, and
> > > RIPEMD160
> > > has 160-bit security against preimage attacks. Thus things like
> > > pay-to-pubkey-hash are perfectly secure: sure you could generate two
> > > pubkeys
> > > that have the same RIPEMD160(SHA256()) digest, but if someone does
> that it
> > > doesn't cause the Bitcoin network itself any harm, and doing so is
> > > something
> > > you choose to do to yourself.
> > >
> >
> > Be aware that the issue is more problematic for more complex contracts.
> > For example, you are building a P2SH 2-of-2 multisig together with
> someone
> > else if you are not careful, party A can hand their key over to party B,
> > who can may try to generate a collision between their second key and
> > another 2-of-2 multisig where they control both keys. See
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
> 2016-January/012205.html
>
> I'm very aware of that, in fact I think I may have even been the first
> person
> to post on this list the commit-reveal mitigation.
>
> Note how I said earlier in the message you're replying to that "P2SH's
> 160-bits
> is insufficient in certain use-cases such as multisig"
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>


-- 
I like to provide some work at no charge to prove my value. Do you need a
techie?
I own Litmocracy  and Meme Racing
 (in alpha).
I'm the webmaster for The Voluntaryist  which
now accepts Bitcoin.
I also code for The Dollar Vigilante .
"He ought to find it more profitable to play by the rules" - Satoshi
Nakamoto
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Watson Ladd via bitcoin-dev]

On Sat, Feb 25, 2017 at 11:12 AM, Peter Todd via bitcoin-dev
 wrote:
> On Sat, Feb 25, 2017 at 11:10:02AM -0500, Ethan Heilman via bitcoin-dev wrote:
>> >SHA1 is insecure because the SHA1 algorithm is insecure, not because
>> 160bits isn't enough.
>>
>> I would argue that 160-bits isn't enough for collision resistance. Assuming
>> RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle), collisions
>
> That's something that we're well aware of; there have been a few discussions 
> on
> this list about how P2SH's 160-bits is insufficient in certain use-cases such
> as multisig.
>
> However, remember that a 160-bit *security level* is sufficient, and RIPEMD160
> has 160-bit security against preimage attacks. Thus things like
> pay-to-pubkey-hash are perfectly secure: sure you could generate two pubkeys
> that have the same RIPEMD160(SHA256()) digest, but if someone does that it
> doesn't cause the Bitcoin network itself any harm, and doing so is something
> you choose to do to yourself.

P2SH is not secure against collision. I could write two scripts with
the same hash, one of which is an escrow script and the other which
pays it to me, have someone pay to the escrow script, and then get the
payment. Some formal analysis tools would ignore the unused
instructions even if human analysis would not.

>
> In any case, segwit will provide a 256-bit pay-to-witness-script-hash(1), 
> which
> provides a 128-bit security level against collision attacks.
>
> 1) https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki#Native_P2WSH
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Peter Todd via bitcoin-dev]

On Sat, Feb 25, 2017 at 03:53:12PM -0500, Russell O'Connor wrote:
> On Sat, Feb 25, 2017 at 2:12 PM, Peter Todd via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> > On Sat, Feb 25, 2017 at 11:10:02AM -0500, Ethan Heilman via bitcoin-dev
> > wrote:
> > > >SHA1 is insecure because the SHA1 algorithm is insecure, not because
> > > 160bits isn't enough.
> > >
> > > I would argue that 160-bits isn't enough for collision resistance.
> > Assuming
> > > RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle),
> > collisions
> >
> > That's something that we're well aware of; there have been a few
> > discussions on
> > this list about how P2SH's 160-bits is insufficient in certain use-cases
> > such
> > as multisig.
> >
> > However, remember that a 160-bit *security level* is sufficient, and
> > RIPEMD160
> > has 160-bit security against preimage attacks. Thus things like
> > pay-to-pubkey-hash are perfectly secure: sure you could generate two
> > pubkeys
> > that have the same RIPEMD160(SHA256()) digest, but if someone does that it
> > doesn't cause the Bitcoin network itself any harm, and doing so is
> > something
> > you choose to do to yourself.
> >
> 
> Be aware that the issue is more problematic for more complex contracts.
> For example, you are building a P2SH 2-of-2 multisig together with someone
> else if you are not careful, party A can hand their key over to party B,
> who can may try to generate a collision between their second key and
> another 2-of-2 multisig where they control both keys. See
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012205.html

I'm very aware of that, in fact I think I may have even been the first person
to post on this list the commit-reveal mitigation.

Note how I said earlier in the message you're replying to that "P2SH's 160-bits
is insufficient in certain use-cases such as multisig"

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


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Peter Todd via bitcoin-dev]

On Sat, Feb 25, 2017 at 12:42:56PM -0800, Watson Ladd wrote:
> On Sat, Feb 25, 2017 at 11:12 AM, Peter Todd via bitcoin-dev
>  wrote:
> > On Sat, Feb 25, 2017 at 11:10:02AM -0500, Ethan Heilman via bitcoin-dev 
> > wrote:
> >> >SHA1 is insecure because the SHA1 algorithm is insecure, not because
> >> 160bits isn't enough.
> >>
> >> I would argue that 160-bits isn't enough for collision resistance. Assuming
> >> RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle), collisions
> >
> > That's something that we're well aware of; there have been a few 
> > discussions on
> > this list about how P2SH's 160-bits is insufficient in certain use-cases 
> > such
> > as multisig.
> >
> > However, remember that a 160-bit *security level* is sufficient, and 
> > RIPEMD160
> > has 160-bit security against preimage attacks. Thus things like
> > pay-to-pubkey-hash are perfectly secure: sure you could generate two pubkeys
> > that have the same RIPEMD160(SHA256()) digest, but if someone does that it
> > doesn't cause the Bitcoin network itself any harm, and doing so is something
> > you choose to do to yourself.
> 
> P2SH is not secure against collision. I could write two scripts with
> the same hash, one of which is an escrow script and the other which
> pays it to me, have someone pay to the escrow script, and then get the
> payment. Some formal analysis tools would ignore the unused
> instructions even if human analysis would not.

That's what I said: "P2SH's 160-bits is insufficient in certain use-cases such
as multisig"

Obviously any usecase where multiple people are creating a P2SH redeemScript
collaboratively is potentially vulnerable. Use-cases where the redeemScript was
created by a single-party however are _not_ vulnerable, as that party has
complete control over whether or not collisions are possible, by virtue of the
fact that they're the ones who have to make the collision happen!

Similarly, even in the multisig case, commit-reveal techniques can mitigate the
vulnerability, by forcing parties to commit to what pubkeys/hashlocks/etc.
they'll use for the script prior to pubkeys/hashlocks/etc. being revealed.
Though a better long-term approach is to use a 256-bit digest size, as segwit
does.

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


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Russell O'Connor via bitcoin-dev]

On Sat, Feb 25, 2017 at 2:12 PM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Sat, Feb 25, 2017 at 11:10:02AM -0500, Ethan Heilman via bitcoin-dev
> wrote:
> > >SHA1 is insecure because the SHA1 algorithm is insecure, not because
> > 160bits isn't enough.
> >
> > I would argue that 160-bits isn't enough for collision resistance.
> Assuming
> > RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle),
> collisions
>
> That's something that we're well aware of; there have been a few
> discussions on
> this list about how P2SH's 160-bits is insufficient in certain use-cases
> such
> as multisig.
>
> However, remember that a 160-bit *security level* is sufficient, and
> RIPEMD160
> has 160-bit security against preimage attacks. Thus things like
> pay-to-pubkey-hash are perfectly secure: sure you could generate two
> pubkeys
> that have the same RIPEMD160(SHA256()) digest, but if someone does that it
> doesn't cause the Bitcoin network itself any harm, and doing so is
> something
> you choose to do to yourself.
>

Be aware that the issue is more problematic for more complex contracts.
For example, you are building a P2SH 2-of-2 multisig together with someone
else if you are not careful, party A can hand their key over to party B,
who can may try to generate a collision between their second key and
another 2-of-2 multisig where they control both keys. See
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012205.html
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Peter Todd via bitcoin-dev]

On Sat, Feb 25, 2017 at 11:10:02AM -0500, Ethan Heilman via bitcoin-dev wrote:
> >SHA1 is insecure because the SHA1 algorithm is insecure, not because
> 160bits isn't enough.
> 
> I would argue that 160-bits isn't enough for collision resistance. Assuming
> RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle), collisions

That's something that we're well aware of; there have been a few discussions on
this list about how P2SH's 160-bits is insufficient in certain use-cases such
as multisig.

However, remember that a 160-bit *security level* is sufficient, and RIPEMD160
has 160-bit security against preimage attacks. Thus things like
pay-to-pubkey-hash are perfectly secure: sure you could generate two pubkeys
that have the same RIPEMD160(SHA256()) digest, but if someone does that it
doesn't cause the Bitcoin network itself any harm, and doing so is something
you choose to do to yourself.

In any case, segwit will provide a 256-bit pay-to-witness-script-hash(1), which
provides a 128-bit security level against collision attacks.

1) https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki#Native_P2WSH

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


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Shin'ichiro Matsuo via bitcoin-dev]

We should distinguish collision resistance from 2nd pre-image resistance, in 
general.

As previously written, we should care both hash output length and algorithm 
itself. The weakness of SHA-0 (preliminary version of SHA-1) was reported in 
2004, then many research on the structure of SHA-1 were conducted. In the case 
of SHA-2, it is harder than SHA-1 to find collisions.

Existing security consideration and evaluation criteria were extensively 
discussed in the NIST SHA-3 competition. Please see the following sites.

https://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo
https://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories

We need similar analysis on RIPEMD160 and impacts of attacks on 
(RIPEMD160(SHA2(msg)). 

We can also refer the security assumption of hash chain in Asiacrypt 2004 
Paper. 
https://home.cyber.ee/~ahtbu/timestampsec.pdf

In the discussion of SHA3 competition, we choose another hash design structure, 
so called "sponge structure." This leads diversity of design principles of hash 
function and gives resilience even when one hash design structure becomes 
vulnerable. As Peter Todd wrote, discussion on design structure and algorithm 
is important. Discussions on all of algorithm, output length and security 
requirements are needed.

At some future moment, we should think about transition of underlying hash 
functions. I’m working on this subject and will present an idea at IEEE S&B.

Shin’ichiro Matsuo


> On Feb 25, 2017, at 8:10 AM, Ethan Heilman via bitcoin-dev 
>  wrote:
> 
> >SHA1 is insecure because the SHA1 algorithm is insecure, not because 160bits 
> >isn't enough.
> 
> I would argue that 160-bits isn't enough for collision resistance. Assuming 
> RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle), collisions 
> can be generated in 2^80 queries (actually detecting these collisions 
> requires some time-memory additional trade-offs). The Bitcoin network at the 
> current hash rate performs roughly SHA-256 ~2^78 queries a day or 2^80 
> queries every four days. Without any break in RIPEMD-160(SHA-256(msg)) the US 
> could build an ASIC datacenter and produce RIPEMD-160 collisions for a 
> fraction of its yearly cryptologic budget.
> 
> The impact of collisions in RIPEMD-160(SHA-256(msg)) according to "On Bitcoin 
> Security in the Presence of Broken Crypto 
> Primitives"(https://eprint.iacr.org/2016/167.pdf):
> 
> >Collisions are similar, though in this case both public keys are under the 
> >adversary’s control, and again the adversary does not have access to the 
> >private keys. In both scenarios, there is a question of nonrepudiation 
> >external to the protocol itself: by presenting a second pre-image of a key 
> >used to sign a transaction, a user/adversary can claim that his coins were 
> >stolen. 
> 
> How would such an event effect the price of Bitcoin when headlines are 
> "Bitcoin's Cryptography Broken"? How much money could someone make by playing 
> the market in this way? 
> 
> For both reasons of credibility and good engineering (safety margins) Bitcoin 
> should strive to always use cryptography which is beyond reproach.
> 
> 
> On Sat, Feb 25, 2017 at 9:50 AM, Leandro Coutinho via bitcoin-dev 
>  wrote:
> Google recommeds "migrate to safer cryptographic hashes such as SHA-256 and 
> SHA-3"
> It does not mention RIPEMD-160
> 
> https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html?m=1
> 
> 
> Em 25/02/2017 10:47, "Steve Davis via bitcoin-dev" 
>  escreveu:
> 
> > On Feb 24, 2017, at 7:01 PM, Peter Todd  wrote:
> >
> > On Fri, Feb 24, 2017 at 05:49:36PM -0600, Steve Davis via bitcoin-dev wrote:
> >> If the 20 byte SHA1 is now considered insecure (with good reason), what 
> >> about RIPEMD-160 which is the foundation of Bitcoin addresses?
> >
> > SHA1 is insecure because the SHA1 algorithm is insecure, not because 
> > 160bits isn't enough.
> >
> > AFAIK there aren't any known weaknesses in RIPEMD160,
> 
> …so far. I wonder how long that vacation will last?
> 
> > but it also hasn't been
> > as closely studied as more common hash algorithms.
> 
> ...but we can be sure that it will be, since the dollar value held in 
> existing utxos continues to increase...
> 
> > That said, Bitcoin uses
> > RIPEMD160(SHA256(msg)), which may make creating collisions harder if an 
> > attack
> > is found than if it used RIPEMD160 alone.
> 
> Does that offer any greater protection? That’s not so clear to me as the 
> outputs (at least for p2pkh) only verify the public key against the final 20 
> byte hash. Specifically, in the first (notional) case the challenge would be 
> to find a private key that has a public key that hashes to the final hash. In 
> the second (realistic) case, you merely need to add the sha256 hash into the 
> problem, which doesn’t seem to me to increase the difficulty by any 
> significant amount?
> 
> 
> /s
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> ht

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Ethan Heilman via bitcoin-dev]

>You have to not only produce a ripemd160 collision, you have to produce a
collision that is also a valid sha-256 hash - and that's much much much
more difficult.

I agree that merely finding a collision in RIPEMD-160 will be hard to use
in Bitcoin.

However finding a collision in RIPEMD-160(SHA-256(msg)) via bruteforce
(2^80 queries) is not particular more difficult than finding a collision in
RIPEMD-160 via brute force. Furthermore if you find a collision in
RIPEMD-160(SHA-256(msg)) you also get a valid SHA-256 hash for which you
know the preimage.


On Sat, Feb 25, 2017 at 1:19 PM, Alice Wonder via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On 02/25/2017 08:10 AM, Ethan Heilman via bitcoin-dev wrote:
>
>> SHA1 is insecure because the SHA1 algorithm is insecure, not because
>>>
>> 160bits isn't enough.
>>
>> I would argue that 160-bits isn't enough for collision resistance.
>> Assuming RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random
>> oracle), collisions can be generated in 2^80 queries (actually detecting
>> these collisions requires some time-memory additional trade-offs). The
>> Bitcoin network at the current hash rate performs roughly SHA-256 ~2^78
>> queries a day or 2^80 queries every four days.
>>
>
> You have to not only produce a ripemd160 collision, you have to produce a
> collision that is also a valid sha-256 hash - and that's much much much
> more difficult.
>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Alice Wonder via bitcoin-dev]

On 02/25/2017 08:10 AM, Ethan Heilman via bitcoin-dev wrote:

SHA1 is insecure because the SHA1 algorithm is insecure, not because

160bits isn't enough.

I would argue that 160-bits isn't enough for collision resistance.
Assuming RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random
oracle), collisions can be generated in 2^80 queries (actually detecting
these collisions requires some time-memory additional trade-offs). The
Bitcoin network at the current hash rate performs roughly SHA-256 ~2^78
queries a day or 2^80 queries every four days.


You have to not only produce a ripemd160 collision, you have to produce 
a collision that is also a valid sha-256 hash - and that's much much 
much more difficult.


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

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Ethan Heilman via bitcoin-dev]

>SHA1 is insecure because the SHA1 algorithm is insecure, not because
160bits isn't enough.

I would argue that 160-bits isn't enough for collision resistance. Assuming
RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle), collisions
can be generated in 2^80 queries (actually detecting these collisions
requires some time-memory additional trade-offs). The Bitcoin network at
the current hash rate performs roughly SHA-256 ~2^78 queries a day or 2^80
queries every four days. Without any break in RIPEMD-160(SHA-256(msg)) the
US could build an ASIC datacenter and produce RIPEMD-160 collisions for a
fraction of its yearly cryptologic budget.

The impact of collisions in RIPEMD-160(SHA-256(msg)) according to "On
Bitcoin Security in the Presence of Broken Crypto Primitives"(
https://eprint.iacr.org/2016/167.pdf):

>Collisions are similar, though in this case both public keys are under the
adversary’s control, and again the adversary does not have access to the
private keys. In both scenarios, there is a question of nonrepudiation
external to the protocol itself: by presenting a second pre-image of a key
used to sign a transaction, a user/adversary can claim that his coins were
stolen.

How would such an event effect the price of Bitcoin when headlines are
"Bitcoin's Cryptography Broken"? How much money could someone make by
playing the market in this way?

For both reasons of credibility and good engineering (safety
margins) Bitcoin should strive to always use cryptography which is beyond
reproach.


On Sat, Feb 25, 2017 at 9:50 AM, Leandro Coutinho via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Google recommeds "migrate to safer cryptographic hashes such as SHA-256
> and SHA-3"
> It does not mention RIPEMD-160
>
> https://security.googleblog.com/2017/02/announcing-first-
> sha1-collision.html?m=1
>
>
> Em 25/02/2017 10:47, "Steve Davis via bitcoin-dev"  linuxfoundation.org> escreveu:
>
>
> > On Feb 24, 2017, at 7:01 PM, Peter Todd  wrote:
> >
> > On Fri, Feb 24, 2017 at 05:49:36PM -0600, Steve Davis via bitcoin-dev
> wrote:
> >> If the 20 byte SHA1 is now considered insecure (with good reason), what
> about RIPEMD-160 which is the foundation of Bitcoin addresses?
> >
> > SHA1 is insecure because the SHA1 algorithm is insecure, not because
> 160bits isn't enough.
> >
> > AFAIK there aren't any known weaknesses in RIPEMD160,
>
> …so far. I wonder how long that vacation will last?
>
> > but it also hasn't been
> > as closely studied as more common hash algorithms.
>
> ...but we can be sure that it will be, since the dollar value held in
> existing utxos continues to increase...
>
> > That said, Bitcoin uses
> > RIPEMD160(SHA256(msg)), which may make creating collisions harder if an
> attack
> > is found than if it used RIPEMD160 alone.
>
> Does that offer any greater protection? That’s not so clear to me as the
> outputs (at least for p2pkh) only verify the public key against the final
> 20 byte hash. Specifically, in the first (notional) case the challenge
> would be to find a private key that has a public key that hashes to the
> final hash. In the second (realistic) case, you merely need to add the
> sha256 hash into the problem, which doesn’t seem to me to increase the
> difficulty by any significant amount?
>
>
> /s
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Leandro Coutinho via bitcoin-dev]

Google recommeds "migrate to safer cryptographic hashes such as SHA-256 and
SHA-3"
It does not mention RIPEMD-160

https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html?m=1


Em 25/02/2017 10:47, "Steve Davis via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> escreveu:


> On Feb 24, 2017, at 7:01 PM, Peter Todd  wrote:
>
> On Fri, Feb 24, 2017 at 05:49:36PM -0600, Steve Davis via bitcoin-dev
wrote:
>> If the 20 byte SHA1 is now considered insecure (with good reason), what
about RIPEMD-160 which is the foundation of Bitcoin addresses?
>
> SHA1 is insecure because the SHA1 algorithm is insecure, not because
160bits isn't enough.
>
> AFAIK there aren't any known weaknesses in RIPEMD160,

…so far. I wonder how long that vacation will last?

> but it also hasn't been
> as closely studied as more common hash algorithms.

...but we can be sure that it will be, since the dollar value held in
existing utxos continues to increase...

> That said, Bitcoin uses
> RIPEMD160(SHA256(msg)), which may make creating collisions harder if an
attack
> is found than if it used RIPEMD160 alone.

Does that offer any greater protection? That’s not so clear to me as the
outputs (at least for p2pkh) only verify the public key against the final
20 byte hash. Specifically, in the first (notional) case the challenge
would be to find a private key that has a public key that hashes to the
final hash. In the second (realistic) case, you merely need to add the
sha256 hash into the problem, which doesn’t seem to me to increase the
difficulty by any significant amount?


/s
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Steve Davis via bitcoin-dev]

> On Feb 24, 2017, at 7:01 PM, Peter Todd  wrote:
> 
> On Fri, Feb 24, 2017 at 05:49:36PM -0600, Steve Davis via bitcoin-dev wrote:
>> If the 20 byte SHA1 is now considered insecure (with good reason), what 
>> about RIPEMD-160 which is the foundation of Bitcoin addresses?
> 
> SHA1 is insecure because the SHA1 algorithm is insecure, not because 160bits 
> isn't enough.
> 
> AFAIK there aren't any known weaknesses in RIPEMD160,

…so far. I wonder how long that vacation will last?

> but it also hasn't been
> as closely studied as more common hash algorithms.

...but we can be sure that it will be, since the dollar value held in existing 
utxos continues to increase...

> That said, Bitcoin uses
> RIPEMD160(SHA256(msg)), which may make creating collisions harder if an attack
> is found than if it used RIPEMD160 alone.

Does that offer any greater protection? That’s not so clear to me as the 
outputs (at least for p2pkh) only verify the public key against the final 20 
byte hash. Specifically, in the first (notional) case the challenge would be to 
find a private key that has a public key that hashes to the final hash. In the 
second (realistic) case, you merely need to add the sha256 hash into the 
problem, which doesn’t seem to me to increase the difficulty by any significant 
amount? 


/s
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev