Bitcoin Forum
December 09, 2016, 12:02:25 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 3 4 [5] 6 »  All
  Print  
Author Topic: New Attack Vector  (Read 37616 times)
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 06:35:26 PM
 #81

Sipa's patch last year changed how this particular implementation behaves, only.  It was not a change in the protocol.  The change was not binding on anyone else.
... and that is why we need: http://www.ietf.org/rfc/rfc2119.txt

To be able to know what we can except from other clients and the rest of the network.

bitcoin need standardization or the crappy satoshi client will continue to dictate the path of bitcoin

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481284945
Hero Member
*
Offline Offline

Posts: 1481284945

View Profile Personal Message (Offline)

Ignore
1481284945
Reply with quote  #2

1481284945
Report to moderator
1481284945
Hero Member
*
Offline Offline

Posts: 1481284945

View Profile Personal Message (Offline)

Ignore
1481284945
Reply with quote  #2

1481284945
Report to moderator
1481284945
Hero Member
*
Offline Offline

Posts: 1481284945

View Profile Personal Message (Offline)

Ignore
1481284945
Reply with quote  #2

1481284945
Report to moderator
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 06:36:42 PM
 #82

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
They don't strike me like people who like to write code Smiley
And I guess you never tried to describe what a code does, in a human readable language.
Otherwise you would know that it's impossible.

if you can't describe what your code does, you should stop writing it.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2030



View Profile
July 17, 2013, 06:40:57 PM
 #83

It mutates with every commit to the satoshi client repo. Code is not a standard.
Prior versions do not mutate with commits to GIT. Those prior versions deployed in the network are the reference against which future compatibility is compared.

Refactoring the code to eventually make a better executable specification out of it, isolating out the bitcoin rules from the low level aspects of their implementation and building a great test framwork around all of it would be a very useful goal that would make this more powerful.

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
Just like the rfc's describe what the protocol look like down to the smallest detail, and then don't change it. Describe how clients interact with keyword defined in http://www.ietf.org/rfc/rfc2119.txt.
Having worked on RFCs (Perhaps I'll see you in Berlin in a couple weeks? Will you be at the IETF meeting? I will be speaking in the Technical Plenary.), I don't agree.  Not that I disagree that having a Bitcoin RFC would be a good thing— but I don't actually believe it would usefully solve any of the concerns you wish to solve.  When the behavior must be _exact_ it is exceptionally difficult to write a specification that is correct, and the end result ends up being— effectively— code, though it may be a kind of odd quasi English pseudo-code where no tools exist to actually execute it, analyze it, or test it. Behavior specified in standards is only infrequently tightly bound, in the blockchain rules most of the behavior is tightly bound— there is very little implementation freedom available.

Say we were to have written an RFC for Bitcoin in 2010.  It wouldn't have documented that weird invalid DER signatures were accepted, because we didn't know about that then.  Someone who implemented according to the specification might accept them, or might not, depending on how they implemented their code.  When a block arose that exposed the inconsistency the network would suffer an irreparable fork.  What behavior would win?  That would depend on a lot of things— technical, political, and economic. Most likely the most restrictive behavior would win— since restrictions are only soft-forking from the perspective of the permissive implementation, even if the spec said you must be permissive.  What it _wouldn't_ depend on is what the text of the RFC said.

A non-executable specification is a dead letter in a consensus system. It may be informative. It may be helpful.  But what it cannot be is normative: Normative behavior arises out of participating in the consensus and a non-executable specification cannot participate in the consensus.
piotr_n
Legendary
*
Offline Offline

Activity: 1498


aka tonikt


View Profile WWW
July 17, 2013, 06:46:02 PM
 #84

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
They don't strike me like people who like to write code Smiley
And I guess you never tried to describe what a code does, in a human readable language.
Otherwise you would know that it's impossible.

if you can't describe what your code does, you should stop writing it.
not, if you still understand what it does.
if the human readable language is not able to express the real meaning of C, why would anyone who knows C limit his further lexical possibilities? Smiley

Check out gocoin - my original project of a bitcoin client written in Go, with some unique features.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 07:04:40 PM
 #85

It mutates with every commit to the satoshi client repo. Code is not a standard.
Prior versions do not mutate with commits to GIT. Those prior versions deployed in the network are the reference against which future compatibility is compared.
just because the mutation are compatible to older versions of the satoshi client, does not mean that they are nonexistent. its much better to have a fixed protocol, instaed of just working code.

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
They don't strike me like people who like to write code Smiley
And I guess you never tried to describe what a code does, in a human readable language.
Otherwise you would know that it's impossible.

if you can't describe what your code does, you should stop writing it.
not, if you still understand what it does.
if the human readable language is not able to express the real meaning of C, why would anyone who knows C limit his further lexical possibilities? Smiley
natural language have extremely flexible usages. Natural languages can express c code, but c code cannot express natural language, it works the other way around.

also if you write too complex and super optimized code the first time around, you are properly doing it wrong. write simple and easily understandable code.

i dare you give me a piece of c code(10-20 lines) that i can't explain.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2030



View Profile
July 17, 2013, 07:25:44 PM
 #86

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?

Code:
uint32_t f(int l, uint32_t val) {
  if (l > 16) {
    val = (val >> (l - 16)) + (((val&((1<<(l - 16)) - 1)) + (1<<(l - 16)) - 1)>>(l - 16));
  } else val <<= 16-l;
  return val;
}
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
July 17, 2013, 07:36:59 PM
 #87

Having worked on RFCs (Perhaps I'll see you in Berlin in a couple weeks? Will you be at the IETF meeting? I will be speaking in the Technical Plenary.), I don't agree.  Not that I disagree that having a Bitcoin RFC would be a good thing— but I don't actually believe it would usefully solve any of the concerns you wish to solve.  When the behavior must be _exact_ it is exceptionally difficult to write a specification that is correct, and the end result ends up being— effectively— code, though it may be a kind of odd quasi English pseudo-code where no tools exist to actually execute it, analyze it, or test it. Behavior specified in standards is only infrequently tightly bound, in the blockchain rules most of the behavior is tightly bound— there is very little implementation freedom available.

Say we were to have written an RFC for Bitcoin in 2010.  It wouldn't have documented that weird invalid DER signatures were accepted, because we didn't know about that then.  Someone who implemented according to the specification might accept them, or might not, depending on how they implemented their code.  When a block arose that exposed the inconsistency the network would suffer an irreparable fork.  What behavior would win?  That would depend on a lot of things— technical, political, and economic. Most likely the most restrictive behavior would win— since restrictions are only soft-forking from the perspective of the permissive implementation, even if the spec said you must be permissive.  What it _wouldn't_ depend on is what the text of the RFC said.

Very good summary.  That said the protocol should be better documented.  The client specific features should also be better documented and indicated as such.  I am not blaming anyone but the fact that the code is the spec doesn't mean that the spec "as we understand it" can't be written down outside of the code.  If nothing else it will help to highlight areas of concern "tricky issues", and areas where the spec didn't match execution in the past. 

As time goes on the spec would encapsulate a lot of trial and error, issues, etc.  For people like kokjo they still won't be happy because the spec will need to be updated over time to better reflect the actual expectation of nodes in the wild (which is the "real" protocol).  It won't be possible to say "nope the spec says X so we do X going forward even if it means a catastrophic hard fork because all existing nodes don't do X they do X'".  Still having it all in black and white makes it easier for new developers to get up to speed. 

Plus putting something in black and white allows knowledgable people to spot omissions or inaccuracies.  The spec can include both required behavior and best hehavior going forward (i.e. non-standard signatures are accepted however all nodes should implement checks to ensure that only canonical signatures along with some test examples).

kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 07:59:41 PM
 #88

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?

Code:
uint32_t f(int l, uint32_t val) {
  if (l > 16) {
    val = (val >> (l - 16)) + (((val&((1<<(l - 16)) - 1)) + (1<<(l - 16)) - 1)>>(l - 16));
  } else val <<= 16-l;
  return val;
}
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

a function f is given 2 arguments, one integer named l and and a 32-bit unsigned integer named val and returns a 32 bit unsigned integer.
if the value of l is strictly larger then 16 we reassign the variable val to the sum of:
val shifted l minus 16 to the left(or is it right? im left-right confused!)
the lower l minus 16 bits of val plus 2 to the l - 16 power minus 1, shifted l - 16 times to the left
if the value of l is less or equal to 16 set val to itself shifted 16  - l times to the right
return val

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 08:06:38 PM
 #89

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?

Code:
uint32_t f(int l, uint32_t val) {
  if (l > 16) {
    val = (val >> (l - 16)) + (((val&((1<<(l - 16)) - 1)) + (1<<(l - 16)) - 1)>>(l - 16));
  } else val <<= 16-l;
  return val;
}
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

but no i have no idea of what the code is doing, but it seems like some insanely optimized bit twiddling computation, its probably a estimation of some mathematical function. I really dislike bit twiddling magic, its just as incomprehensible as brainfuck or APL.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
grue
Global Moderator
Legendary
*
Offline Offline

Activity: 1932



View Profile
July 17, 2013, 08:24:46 PM
 #90

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

a function f is given 2 arguments, one integer named l and and a 32-bit unsigned integer named val and returns a 32 bit unsigned integer.
if the value of l is strictly larger then 16 we reassign the variable val to the sum of:
val shifted l minus 16 to the left(or is it right? im left-right confused!)
the lower l minus 16 bits of val plus 2 to the l - 16 power minus 1, shifted l - 16 times to the left
if the value of l is less or equal to 16 set val to itself shifted 16  - l times to the right
return val
But what you're not understanding the function. All you're doing is repeating it word for word. He meant you couldn't explain it colloquially.

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

but no i have no idea of what the code is doing, but it seems like some insanely optimized bit twiddling computation, its probably a estimation of some mathematical function. I really dislike bit twiddling magic, its just as incomprehensible as brainfuck or APL.
hey look, gmaxwell delivered and you failed.

It is pitch black. You are likely to be eaten by a grue.

Tired of annoying signature ads? Ad block for signatures
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 09:13:33 PM
 #91

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

a function f is given 2 arguments, one integer named l and and a 32-bit unsigned integer named val and returns a 32 bit unsigned integer.
if the value of l is strictly larger then 16 we reassign the variable val to the sum of:
val shifted l minus 16 to the left(or is it right? im left-right confused!)
the lower l minus 16 bits of val plus 2 to the l - 16 power minus 1, shifted l - 16 times to the left
if the value of l is less or equal to 16 set val to itself shifted 16  - l times to the right
return val
But what you're not understanding the function. All you're doing is repeating it word for word. He meant you couldn't explain it colloquially.

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

but no i have no idea of what the code is doing, but it seems like some insanely optimized bit twiddling computation, its probably a estimation of some mathematical function. I really dislike bit twiddling magic, its just as incomprehensible as brainfuck or APL.
hey look, gmaxwell delivered and you failed.
its a part of a code that computed a overestimate of log_2

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
razorfishsl
Sr. Member
****
Offline Offline

Activity: 406


View Profile WWW
July 18, 2013, 03:37:09 AM
 #92

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
They don't strike me like people who like to write code Smiley
And I guess you never tried to describe what a code does, in a human readable language.
Otherwise you would know that it's impossible.

if you can't describe what your code does, you should stop writing it.
not, if you still understand what it does.
if the human readable language is not able to express the real meaning of C, why would anyone who knows C limit his further lexical possibilities? Smiley

If you cannot explain something in a simple language.. then the truth is , that you  are only fooling yourself and just don't understand it....


High Quality USB Hubs for Bitcoin miners
https://bitcointalk.org/index.php?topic=560003
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 18, 2013, 05:21:49 AM
 #93

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

a function f is given 2 arguments, one integer named l and and a 32-bit unsigned integer named val and returns a 32 bit unsigned integer.
if the value of l is strictly larger then 16 we reassign the variable val to the sum of:
val shifted l minus 16 to the left(or is it right? im left-right confused!)
the lower l minus 16 bits of val plus 2 to the l - 16 power minus 1, shifted l - 16 times to the left
if the value of l is less or equal to 16 set val to itself shifted 16  - l times to the right
return val
But what you're not understanding the function. All you're doing is repeating it word for word. He meant you couldn't explain it colloquially.

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

but no i have no idea of what the code is doing, but it seems like some insanely optimized bit twiddling computation, its probably a estimation of some mathematical function. I really dislike bit twiddling magic, its just as incomprehensible as brainfuck or APL.
hey look, gmaxwell delivered and you failed.
its a part of a code that computed a overestimate of log_2

An overestimate of log2 is easy.  It doesn't need two parameters...

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2030



View Profile
July 18, 2013, 06:29:50 AM
 #94

An overestimate of log2 is easy.  It doesn't need two parameters...
He went and found the origin of the code, these particular lines are not a log2 (obviously) but they're used as part of an integer implementation of a log2.

He didn't actually describe what those lines do, which is amusing since there is actually a comment that explains them right above them in the code they came from.

I thought it was a fun example because I know that an adequate programmer can, in fact, understand it purely from the code— since I was given an algebraic simplification of that code (taking advantage of the fact that in the calling enviroment case it's never used with val==0) by a random OSS contributor, and I think that was even before it had a comment explaining what it was doing.

A detailed description of this code ends up being an opaque transliteration which people will convert back to $language incorrectly (noting that kokjo actually did have trouble figuring out what computation it was performing and doubted his understanding of the mere behavior).  While, a high level description "This is (val>>(l-16)), but guaranteed to round up, even if adding a bias before the shift would cause overflow (e.g., for 0xFFFFxxxx)." would almost certainly be implemented incorrectly, as you can see it's a bit tricky and joe-random-programmer doesn't generally know how to make fixed point division round up even before you worry about overflow.  (How many people know about the truncation vs floor behavior of >> and / operators, and that they're not the same in, e.g. C and python or how you convert one to another, or would even realize that they had to take special care— even if the spec called it out?)

I'm sure a sufficiently deft drafter could write a spec that handles this... but this is two lines.  Getting exact behavior when you need to worry about things like overflow and correct performance over the entire range of a machine number is simply hard and a lot of programmers are not mentally prepared for it. Writing spec text which doesn't create hazards can be tricky.
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
July 19, 2013, 05:05:55 PM
 #95

it makes it nearly impossible to create a alternative client, when the "standard" mutates all the time. bitcoin needs diversity in clients.

Do you have any idea what you're talking about?

The DER encoding for signatures is the most standard one that exists. We've been discussing enforcing the standard for a _year_ before implementing it - because, unfortunately, not everyone was following the same rules.

Do you know why we want to enforce this standard? To make sure Bitcoin can be implemented without relying on OpenSSL.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
hydrogenesis
Newbie
*
Offline Offline

Activity: 17

hydrogen genesis


View Profile
February 10, 2014, 01:36:04 PM
 #96

FYI this issue is re-opened by mtgox and gmaxwell.

https://www.mtgox.com/press_release_20140210.html
https://en.bitcoin.it/wiki/Transaction_Malleability
http://www.cryptocoinsnews.com/2014/02/10/mt-gox-blames-bitcoin-core-developer-greg-maxwell-responds/

Wir müssen wissen. Wir werden wissen.

Trading reputation thread:
https://bitcointalk.org/index.php?topic=448993
mccoyspace
Full Member
***
Offline Offline

Activity: 237


View Profile WWW
February 10, 2014, 01:54:47 PM
 #97

great thread reboot.
a very interesting read.
this issue has been know about for a long time, but it's still here and now it's causing problems.
Zzzack
Full Member
***
Offline Offline

Activity: 168


View Profile
February 10, 2014, 05:17:45 PM
 #98

I was wondering how block intervals relate to this issue.

Would a coin with a 30 minute block interval be more susceptible to such a problem?

Producer
metacoin
Sr. Member
****
Offline Offline

Activity: 264


live free


View Profile WWW
February 10, 2014, 07:08:15 PM
 #99

I was wondering how block intervals relate to this issue.

Would a coin with a 30 minute block interval be more susceptible to such a problem?
The coin itself isn't affected by transaction malleability, as one of the transactions will eventually be mined and at some point the coins will successfully be sent to their destination address as the sender intended. Software written to rely on tracking a txid alone is susceptible to such a problem. A solution would be tracking coins by their confirmed (immutable) outputs rather than tracking the txid that contains those outputs.

Block time specifically, or any function of time, does not have much to do with this.

Florin block explorer: http://florincoin.info
David Rabahy
Hero Member
*****
Offline Offline

Activity: 603



View Profile
February 10, 2014, 09:39:27 PM
 #100

Is there concrete evidence in the block chain?  Are there indeed altered transactions in the pool?  Is Mt. Gox blowing smoke?
Pages: « 1 2 3 4 [5] 6 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!