Signature Mining (to embed messages into the blockchain without using OP_RETURN)

[Luke-Jr]

You might want to look at https://github.com/Blockstream/contracthashtool

[1713960532]

1713960532

[1713960532]

1713960532

[CIYAM]

You might want to look at https://github.com/Blockstream/contracthashtool

Very interesting - thanks.

[CIYAM]

I decided to add a couple of functions to CIYAM's crypto keys implementation (https://github.com/ciyam/ciyam/blob/master/src/crypto_keys.cpp#L730) to emulate a "vanitygen" approach to "mining addresses" in order to encode a message in the address itself (just one byte per address for simplicity and because the code would need to be optimised to do more and it's obvious that vanitygen is very well optimised when I checked the timing).

Code to "encode the encrypted message" into a bunch of private keys is as follows ("Hello!" would of course be replaced with an encrypted message). The addresses and private keys are then output to the console.

Code:

vector< string > secrets;
generate_secrets_for_leading_byte_encoded_message( "Hello!", secrets );

vector< string > addresses;
for( size_t i = 0; i < secrets.size( ); i++ )
{
   addresses.push_back( private_key( secrets[ i ] ).get_address( ) );
   cout << addresses.back( ) << ' ' << secrets[ i ] << endl;
}

the other side (to decode the encrypted message) is as follows:

Code:

cout << decode_message_from_leading_byte_encoded_addresses( addresses ) << endl;

and this is a sample of the console output:

Code:

17crfGDDU1MJSdM2rrFGNXYm6db4hEQo6A bdad968085aa4b7b6cd653e4341c8845a84ccc37ce2438c3965c814d3cc686de
1AEqwSMc8rdR3jMUsSMU1Fx1x6sBKtLyhA a8f3b581a5fd2af58c7b9841df878f4631e189f69143ba6f34874ad527f6c435
1AurJRfZ8mLZfLAEonYnB2fRNKJj2sM52g a67bb9045d5bf12f89a871be3554aa798e69ab088740c3136d8111f21ba53c3b
1AujLMPYW3nkEte13PSmmrLJe6pJZYswgu 1bffc5f7d38e7a609511c89d24127b78324d74328a301ef803d539f6adcc65f6
1B85SG1dvTaF9JsM1UMaeLoQyb6MT6FHxr c180c4c1256e6b9dc1cf9ca9f9468953b3c9de9b7c25cd90969f25bb709a3164
145KFvZFLSYWHfDtJrmghcTKvaKAkp9rKu 1639eb3dce0143dd8b468abdcfe05e4f9ede0cf9a4621c6d07fc1eca44a4d56d
Hello!

Granted that only using 1 byte per address (and assuming 1 UTXO as the input) you could only fit 25 bytes for a 1K tx but it is at least a template of how this could be used by an application in order to send private messages via Bitcoin.

[btchris]

I thought that the ability to create subliminal messages in a security protocol was generally considered a flaw of that protocol.

For example, an evil ECDSA implementation could leak a user's private key to the implementation's authors. Isn't that (one) reason that newer ECDSA implementations deterministically generate k?

(I'm just repeating what I've read elsewhere on the forums and on the web, e.g. DJB's blog.)

[CIYAM]

I thought that the ability to create subliminal messages in a security protocol was generally considered a flaw of that protocol.

For example, an evil ECDSA implementation could leak a user's private key to the implementation's authors. Isn't that (one) reason that newer ECDSA implementations deterministically generate k?

(I'm just repeating what I've read elsewhere on the forums and on the web, e.g. DJB's blog.)

For a start you'd need to *be aware* that the subliminal message exists (there is no way to tell by just looking at the sigs especially if you don't know how the code that encoded them is working as the placement of the message bytes can be made arbitrary).

Also this is only removing 1 or 2 bytes of security (assuming you could work out what had been purposely injected) which is not going to let you crack a private key.

If you consider a "vanity address" it is the same thing. Just because you know that I have an address that is prefixed with 1ciyam does not mean you are going to be able to *crack its private key* (if it were that easy then there should be zero BTC at my sig address - but there isn't).

[btchris]

I thought that the ability to create subliminal messages in a security protocol was generally considered a flaw of that protocol.

For example, an evil ECDSA implementation could leak a user's private key to the implementation's authors. Isn't that (one) reason that newer ECDSA implementations deterministically generate k?

(I'm just repeating what I've read elsewhere on the forums and on the web, e.g. DJB's blog.)

For a start you'd need to *be aware* that the subliminal message exists (there is no way to tell by just looking at the sigs especially if you don't know how the code that encoded them is working as the placement of the message bytes can be made arbitrary).

Also this is only removing 1 or 2 bytes of security (assuming you could work out what had been purposely injected) which is not going to let you crack a private key.

If you consider a "vanity address" it is the same thing. Just because you know that I have an address that is prefixed with 1ciyam does not mean you are going to be able to *crack its private key* (if it were that easy then there should be zero BTC at my sig address - but there isn't).

Sorry, I wasn't very clear.

The "attack" I was trying to refer to involves an evil (and closed source) ECDSA implementation that intentionally leaks X successive bytes of a privkey in each signature it creates. Only someone aware of the leak, e.g the authors of the implementation, would able to take advantage of it. Given multiple signatures, the evil authors could reconstruct privkeys of those using their implementation.

An advantage (perhaps not the main advantage though) of a deterministically generated k is that one can validate the output of a closed-source implementation without needing the source code (assuming the method of generating k is published). If for example ProprietarySoft Corp. published an ECDSA library, researchers could verify that it wasn't using this channel to leak privkeys.

I was just bringing up that point -- none of this really applies to open source implementations.

[CIYAM]

I was just bringing up that point -- none of this really applies to open source implementations.

Okay - yes - I understand the issue of poor k values (which have been exploited already in Android).

Although deterministic is most likely a more secure method of generating addresses it of course would make this data injection method unfeasible.

[cr1776]

...
I was just bringing up that point -- none of this really applies to open source implementations.

In theory.  

But look at heartbleed, shellshock, Ken Thompson's self-referencing Unix C compiler, perhaps truecrypt etc.

Open source does not imply that one is safe.  It certainly is helpful to verify that there are not back doors, but if you don't have enough people looking at it and security audits, well hidden bugs or intentional backdoors are easy to miss.  Obfuscated code that has intentional vulnerabilities can be difficult to spot.

Consequently, it is important to bring up vulnerabilities like this and discuss them - I'm glad you mentioned it.

 

[CIYAM]

Open source does not imply that one is safe.  It certainly is helpful to verify that there are not back doors, but if you don't have enough people looking at it and security audits, well hidden bugs or intentional backdoors are easy to miss.  Obfuscated code that has intentional vulnerabilities can be difficult to spot.

Consequently, it is important to bring up vulnerabilities like this and discuss them - I'm glad you mentioned it.

 

Of course - I have made this open source and it should be audited by those that are interested (and I am not making any *guarantees* that this is 100% secure - so of course "use this at your own risk").

[btchris]

...
I was just bringing up that point -- none of this really applies to open source implementations.

In theory.  

But look at heartbleed, shellshock, Ken Thompson's self-referencing Unix C compiler, perhaps truecrypt etc.

Open source does not imply that one is safe.  It certainly is helpful to verify that there are not back doors, but if you don't have enough people looking at it and security audits, well hidden bugs or intentional backdoors are easy to miss.  Obfuscated code that has intentional vulnerabilities can be difficult to spot.

Consequently, it is important to bring up vulnerabilities like this and discuss them - I'm glad you mentioned it.

 

Yes, and it's quite salient that you brought up TrueCrypt -- it has some leaky side channels which (before the ongoing audit began) were pointed out as avenues for exactly this kind of evil-implementation attack (and yes the source code was examinable at the time, but there wasn't a reproducible build process for Windows).

[btchris]

I was just bringing up that point -- none of this really applies to open source implementations.

Okay - yes - I understand the issue of poor k values (which have been exploited already in Android).

Although deterministic is most likely a more secure method of generating addresses it of course would make this data injection method unfeasible.

The two are incompatible with one another, but there would remain no way that an outside observer (who doesn't have the privkey used for a signature) to determine if k was generated deterministically or it was "mined", so your method remains possible (and it's pretty cool that you went and implemented it ).

[CIYAM]

The two are incompatible with one another, but there would remain no way that an outside observer (who doesn't have the privkey used for a signature) to determine if k was generated deterministically or it was "mined", so your method remains possible (and it's pretty cool that you went and implemented it ).

Agreed and thanks - just trying to offer ideas for those that are interested to use them.