I should have said "exponentially harder in length of the message".
Sure - this approach is only really suitable for short messages (not for storing files in the blockchain).
Topic: Signature Mining (to embed messages into the blockchain without using OP_RETURN) - page 2. (Read 3547 times)
October 29, 2014, 09:48:31 AM
Sure - this approach is only really suitable for short messages (not for storing files in the blockchain).
October 29, 2014, 09:47:34 AM
What you are talking about seems along the lines of subliminal channels.
http://www.emsec.rub.de/media/crypto/attachments/files/2011/03/subliminal_channels.pdf
http://www.emsec.rub.de/media/crypto/attachments/files/2011/03/subliminal_channels.pdf
Nice find (and not something I was aware of) - for sure I didn't expect that my idea was the first about this (just thought I'd share my afternoon of fun *hacking*).
October 29, 2014, 09:47:11 AM
I should have said "exponentially harder in length of the message".
October 29, 2014, 09:45:13 AM
What you are talking about seems along the lines of subliminal channels.
http://www.emsec.rub.de/media/crypto/attachments/files/2011/03/subliminal_channels.pdf
http://www.emsec.rub.de/media/crypto/attachments/files/2011/03/subliminal_channels.pdf
October 29, 2014, 09:32:43 AM
I meant it literally. The signature (r, s) is
r = kG|x
s = (H+rd)/k
[where H is the hash of the message and d the private key]
Choosing r or s means that you managed to find the matching k. It's the same problem as finding the private key. So far the best algorithm is in O(exp(n))
r = kG|x
s = (H+rd)/k
[where H is the hash of the message and d the private key]
Choosing r or s means that you managed to find the matching k. It's the same problem as finding the private key. So far the best algorithm is in O(exp(n))
I am only fixing 2 bytes of the signature (so not at all a method that would work to crack a private key - just look at the timings I recorded doing the two bytes).
It is exactly the same principle that vanitygen works on (and as @cbeast hinted at using vanitygen would be a more efficient approach).
Of course it would be a very bad idea to *re-use* an address (or addresses) that were used to transmit such secrets but also understand that because the message is encrypted with a shared secret there is no way for anyone to know even which two bytes were *mined* (apart from Bob and Jane).
October 29, 2014, 09:30:36 AM
I meant it literally. The signature (r, s) is
r = kG|x
s = (H+rd)/k
[where H is the hash of the message and d the private key]
Choosing r or s means that you managed to find the matching k. It's the same problem as finding the private key. So far the best algorithm is in O(exp(n))
r = kG|x
s = (H+rd)/k
[where H is the hash of the message and d the private key]
Choosing r or s means that you managed to find the matching k. It's the same problem as finding the private key. So far the best algorithm is in O(exp(n))
October 29, 2014, 09:26:22 AM
Of course another approach (used much earlier in a non-secret manner) is to use the last X decimal points to encode data (but that would generally be more costly than what I've outlined in terms of BTC).
October 29, 2014, 09:04:59 AM
Well - this becomes exponentially harder. If not, it would be a new attack on EC.
Sorry - I am not sure exactly what you mean but I'll take a guess...
The "difficulty" of inserting a couple of bytes remains the same per sig (just like the difficulty for creating a vanitygen address).
It is not a *competition* like normal mining is - so is more comparable to "vanity address mining" than Bitcoin mining (luck is still involved but there is no race or competition with others).
Perhaps I should not have used the term mining at all but it still requires work in much the same way as hashcash does (and I recall the word *mining* being used for vanity address creation when the idea of *safe* vanitygen address creation came into existence).
October 29, 2014, 09:00:35 AM
Well - this becomes exponentially harder. If not, it would be a new attack on EC.
October 29, 2014, 05:33:43 AM
Would vanity addresses offer much?
Vanity addresses would indeed provide another way that you could "mine data" and put it into the blockchain (nice one - now we have two ways and in fact vanitygen would be a far more efficient approach).
October 29, 2014, 05:26:07 AM
Would vanity addresses offer much?
October 29, 2014, 04:56:32 AM
After having played around with OP_RETURN recently I was thinking about how it could be used for sending small encrypted messages to another Bitcoin user (much like the way Stealth addresses work). The thing that was concerning me is that OP_RETURN is "in your face" so if some authority wants to try and find your secret then they do have an obvious starting point (even if cracking the message is not feasible).
So I began to wonder - is there a simple way that such a message could be completely hidden? Then suddenly the actual ECDSA signatures jumped out at me and shouted "use us"!
I then promptly jumped into the "crypto_keys.cpp" file from CIYAM (https://github.com/ciyam/ciyam/blob/master/src/crypto_keys.cpp#L700) and made the following change:
I then began to record some "timing" figures and I later modified the two values from 0xff to other things and the results are here:
I will note that a few times it *failed* to work (presumably this would become significantly less likely if the loop were made 10x bigger).
If you look carefully at the column of bytes I have put the VV and ^^ markers on you'll see that I am *in control* of those bytes that are part of the ECDSA signature (because of the looping).
What am I actually doing?
I am *mining* the signature in order to store information in it (possible because of the *random* k value that is used when creating such signatures).
How could this be useful?
Imagine Bob wishes to send his friend Jane a private small message. Firstly he would send a normal Bitcoin transaction to Jane (exposing the public key of a UTXO he owns) and then Jane would send a transaction back (exposing her public key). Using ECDSA it is now possible for Bob and Jane to create a "shared secret" (same as is done for Stealth Addresses).
After this Bob would ask Jane for a new address and then Bob would encrypt his message with the "shared secret" and embed it into a set of UTXOs within the actual ECDSA signatures which would be sent to Jane as a normal Bitcoin transaction (nothing to make it stand out like OP_RETURN at all).
Jane knowing that this came from Bob and it has been sent to the address she gave him to send the secret message to can now use her "shared secret" to extract this message.
My initial tests suggest that on average hardware a small message (say 50 characters) might take an hour or so to "mine" (althugh I made no attempt to optimise anything).
Is this useful?
I think it could be of some use in at least providing another way that small amounts of data can be stored in the blockchain without it being at all *obvious* that such data is actually there.
Enjoy!
So I began to wonder - is there a simple way that such a message could be completely hidden? Then suddenly the actual ECDSA signatures jumped out at me and shouted "use us"!
I then promptly jumped into the "crypto_keys.cpp" file from CIYAM (https://github.com/ciyam/ciyam/blob/master/src/crypto_keys.cpp#L700) and made the following change:
Code:
<< p_impl->sign_message( buf, signature );
>> for( int i = 0; i < 100000; i++ )
>> {
>> p_impl->sign_message( buf, signature );
>> if( signature[ 27 ] == 0xff && signature[ 63 ] == 0xff )
>> {
>> cout << "*** here: i = " << i << endl;
>> break;
>> }
>> }
>> for( int i = 0; i < 100000; i++ )
>> {
>> p_impl->sign_message( buf, signature );
>> if( signature[ 27 ] == 0xff && signature[ 63 ] == 0xff )
>> {
>> cout << "*** here: i = " << i << endl;
>> break;
>> }
>> }
I then began to record some "timing" figures and I later modified the two values from 0xff to other things and the results are here:
Code:
*** here: i = 62594 (~60 seconds)
*** here: i = 40436 (~40 seconds)
*** here: i = 4725 (~5 seconds)
*** here: i = 23288 (~20 seconds)
*** here: i = 51403 (~50 seconds)
*** here: i = 93054 (~100 seconds)
*** here: i = 19706 (~20 seconds)
*** here: i = 19298 (~20 seconds)
*** here: i = 5552 (~5 seconds)
*** here: i = 24582 (~25 seconds)
*** here: i = 16175 (~15 seconds)
*** here: i = 35453 (~35 seconds)
*** here: i = 2873 (~3 seconds)
*** here: i = 46175 (~46 seconds)
*** here: i = 27349 (~30 seconds)
*** here: i = 33235 (~30 seconds)
*** here: i = 68612 (~70 seconds)
*** here: i = 39141 (~40 seconds)
*** here: i = 2187 (~2 seconds)
*** here: i = 22733 (~20 seconds)
*** here: i = 4713 (~5 seconds)
*** here: i = 9029 (~10 seconds)
*** here: i = 8428 (~10 seconds)
*** here: i = 485 (~0 seconds)
*** here: i = 13602 (~15 seconds)
*** here: i = 1231 (~1 second)
*** here: i = 66202 (~65 seconds)
*** here: i = 28185 (~30 seconds)
*** here: i = 35853 (~35 seconds)
*** here: i = 21734 (~20 seconds)
*** here: i = 40436 (~40 seconds)
*** here: i = 4725 (~5 seconds)
*** here: i = 23288 (~20 seconds)
*** here: i = 51403 (~50 seconds)
*** here: i = 93054 (~100 seconds)
*** here: i = 19706 (~20 seconds)
*** here: i = 19298 (~20 seconds)
*** here: i = 5552 (~5 seconds)
*** here: i = 24582 (~25 seconds)
*** here: i = 16175 (~15 seconds)
*** here: i = 35453 (~35 seconds)
*** here: i = 2873 (~3 seconds)
*** here: i = 46175 (~46 seconds)
*** here: i = 27349 (~30 seconds)
*** here: i = 33235 (~30 seconds)
*** here: i = 68612 (~70 seconds)
*** here: i = 39141 (~40 seconds)
*** here: i = 2187 (~2 seconds)
*** here: i = 22733 (~20 seconds)
*** here: i = 4713 (~5 seconds)
*** here: i = 9029 (~10 seconds)
*** here: i = 8428 (~10 seconds)
*** here: i = 485 (~0 seconds)
*** here: i = 13602 (~15 seconds)
*** here: i = 1231 (~1 second)
*** here: i = 66202 (~65 seconds)
*** here: i = 28185 (~30 seconds)
*** here: i = 35853 (~35 seconds)
*** here: i = 21734 (~20 seconds)
I will note that a few times it *failed* to work (presumably this would become significantly less likely if the loop were made 10x bigger).
Code:
VV VV
304502203c7af96966a4be769db2f6a13695c9163de188cec0672cff9e3a37f9c348e0d10221008e7f1f70d39766526f6c58f67dfc43685f005319c2b0fc1effdba84c8ccba958
3045022100c29da2a99193f7a014e343956e93fe8f056d330c770eff276e8cca7adb847f4a022016d1a3c497c06031ea52328b599f2448f39d7006fe3766edff2e9e37af47c123
304402203077ae523785fa689dd9b707c90a064240bb978e4ed737ff28a779ccb9697ead02201db68357b8b84f4e23f3a50424f91d64fbc0f05f572f1d2005ffd2fe5f2be360
3044022039460074e1c5a5770c790338ed76ef67e025c7d9748d30ff856b904f2dc3301d0220220771f7cd93d74669cde5d3c6acc75b0ef089d212b32470ecfff438f904f825
3044022031a74ec810cf2f6b767fabd5134dd136277fb530002a4bff21f7472ad26ae91702200898dce422a478b812cd257696feb78e2af40fdea2eb316d86ffafb9f1cf21d2
304502206e7b22c53c6a661daad1acdcc0b08dea256e6639c786f5ffe1ad2170d668b1b3022100bdfd93322e02ab114b0ba5b6eb2a2906cb35e97d76b4069cff9551b6aef80847
3045022025978e0a3bcc03d2f566cb035c67fe2e1a4e07addb2b8cff306761e58ef85394022100cfd649a81a82feb27015fdf5d31d79ee49a5077fe63f5b32ffa69bb109209454
304502201d49cdb57a48063743ebdcdd08c177e69610a89389e391ff36988957893e8802022100dd76901f1fa82a809067fa0bf852be86d420f258ccba21aeff8b049de39c6e6a
3046022100a4170fef1ed852fcffc5f6ead06dc494f5995145cda200eff6bc50446c5993bb022100a13168cc19bada7973bbb7e20a07836105eb653ee37a5500412113b43dbbb5ae
3045022100f81ac86878e0ae4d1efe45fae61074c047f1a89fefac00730344b7238d844bc802203215e3004435b66e64a0d0d490ee898e648f257efab09fe5006419cf05280a
304402200cdcd5e38b9ac6f6ce64af4b905a488595278595889243005a6c3b98db68bcf502200dfced0d4d93ac5079962695e26a917f125e96e577f0acf3ba001c9eea1b593f
30450220255a87cfecb578bd92fd59ed5d64922252d97fc77e4fd300784eea89e51f80760221008f1f123fcb419908dfe1ab61df1d768f2049f3bba57975fd00b6199046ed5069
3044022073c05467ba7b7494cf555b25d87fabe60e771d5bec04440017b72bf8c6f369e20220645f061baea9e64ab26296c06992d6375deab5dae3197f2e8c00d1e8208ed424
3046022100a8d9f61a674d0c2c33a315f2b39ed5aa209caf77287900713d21b71579d370f1022100e1a10e7ad5fb35a3b9a120b9d2dd4e06c82d478546249c006ae7ce571ca25899
3046022100bad3f490830c00031f0c9c48d233fd2cf0a2a380b4da0069c5e72d93c173aeda022100cf500cf504f281a74994e4d14e3b4176bfdddeae1bf53200834e4a26e7835ca4
304402204dca5e0205de87527f3a6cb441971c12375978c04172b300515f09c9544eecb10220735f77895021f228448ef40fb5a20c17979b07b29d047b206a00edf3e4ef35b2
304402200c58a2af05b52e22204aa8b665ccf0e7ac26219d518350ff71dc5a8cce3eb71002206bb7e4048c2dd758f69970a534176ed276563e5de605f3783a00d0741afa98fc
3044022052529d097530db109a2d4abf6b7153423e713f6b98e6f7ff34378a950bd534bd02202411585bd37ea0f37ac876adf4fd66e234481d610cd024d7a5008e9d7d00ba2a
304502206fd07059190a0a911fb17ad9db6c3effce9980747833c5ff6835a4777baf210e022100e9682236b9c62318df5c3a885d581df417ba917dcc254d5400f8c15e528a1ca2
3045022100fadb120ee656e5b15d1f627d16cf22342a029fcf3580ff2d0f3b6a7f6ffd2bd6022058ab8f851fd27694476a3cf9efcd86511baee8342231861b00f0c9ef12def41e
30450220157dada2594d8deeb796a1febc22a4d6f37d9ae70cf474008b41261d7804872a022100c3f1b2caa33f7630a99e5eeaccf54a2b71d0a16b2384e2dafff81b7e25b9ce97
3045022016ed0e589674cd6da54bbadda751199a1a3b8b7907df2500d46b0719ba5c2db9022100b018f3416d3ae4116b50e18e6c0204e8574fcf03fc56694dff6ea776bc0f3259
304402205c4e5588d8eec6fec579e0f312d0528f4312a89c34862e007466f89e21fdd5600220469273b123361889281595ea4ed50b9340ed5fd0613de2f30eff774874225b76
304502207349da2efe4de858e2cb0aef7cfd06cf0027ad2b5e47b70021a3b3bf885bfeea022100876d52c01fcfbe9cba9f315ffad529f047428f0482c9b535ff5372d487ef3bf2
3045022030c0efecadc6e5e8c09c86ca8084df1711817882cf4d28018faf98d578e84a5d0221008d65c4af49e1de65bdb5bbc5453ddc107b913ece9012712402e3902be4da47e5
30440220085ac17ad265c0a40891f357cd9a323d94743b20f100d30330ae331d086ba2490220402f9a53c8b3e087c61f9df8efe0c78b4e95f1dcc3e2c5757104af9eac0380f2
3045022100dd063e119149e1b902a2d4cad08e823f018bdb175a8105cbf158cbefd9659f80022022564ba20b5fd65780a14bfb34a665e20c20f979bc4fb06e06e378d2d2225acf
3045022100eaf76c3f2f94a9f9e66ddad40ab36721a09a670dffc907390d01b8c87170cf7d02202189be2ee195869d4a7fac206b5624787c7a1b03e58b8903084ae6986a207f9c
3046022100d028bd2d3587abbed253615da8e67bb8d9006c4b2baa138d688b1a3a0d296274022100c55309b7de2af7a8d96f266892718d89792369fd23fe1737f8833eda31a9b1aa
3045022100dec32fe7b0a2e7fa407cdf2a6bb1bc3675fcb1ff39ce1360526093cde12172e0022033aab7cc7e3b42a24813f68a1495b331e3b9ac4ffa2fcb413778b1600d7f055e
^^ ^^
304502203c7af96966a4be769db2f6a13695c9163de188cec0672cff9e3a37f9c348e0d10221008e7f1f70d39766526f6c58f67dfc43685f005319c2b0fc1effdba84c8ccba958
3045022100c29da2a99193f7a014e343956e93fe8f056d330c770eff276e8cca7adb847f4a022016d1a3c497c06031ea52328b599f2448f39d7006fe3766edff2e9e37af47c123
304402203077ae523785fa689dd9b707c90a064240bb978e4ed737ff28a779ccb9697ead02201db68357b8b84f4e23f3a50424f91d64fbc0f05f572f1d2005ffd2fe5f2be360
3044022039460074e1c5a5770c790338ed76ef67e025c7d9748d30ff856b904f2dc3301d0220220771f7cd93d74669cde5d3c6acc75b0ef089d212b32470ecfff438f904f825
3044022031a74ec810cf2f6b767fabd5134dd136277fb530002a4bff21f7472ad26ae91702200898dce422a478b812cd257696feb78e2af40fdea2eb316d86ffafb9f1cf21d2
304502206e7b22c53c6a661daad1acdcc0b08dea256e6639c786f5ffe1ad2170d668b1b3022100bdfd93322e02ab114b0ba5b6eb2a2906cb35e97d76b4069cff9551b6aef80847
3045022025978e0a3bcc03d2f566cb035c67fe2e1a4e07addb2b8cff306761e58ef85394022100cfd649a81a82feb27015fdf5d31d79ee49a5077fe63f5b32ffa69bb109209454
304502201d49cdb57a48063743ebdcdd08c177e69610a89389e391ff36988957893e8802022100dd76901f1fa82a809067fa0bf852be86d420f258ccba21aeff8b049de39c6e6a
3046022100a4170fef1ed852fcffc5f6ead06dc494f5995145cda200eff6bc50446c5993bb022100a13168cc19bada7973bbb7e20a07836105eb653ee37a5500412113b43dbbb5ae
3045022100f81ac86878e0ae4d1efe45fae61074c047f1a89fefac00730344b7238d844bc802203215e3004435b66e64a0d0d490ee898e648f257efab09fe5006419cf05280a
304402200cdcd5e38b9ac6f6ce64af4b905a488595278595889243005a6c3b98db68bcf502200dfced0d4d93ac5079962695e26a917f125e96e577f0acf3ba001c9eea1b593f
30450220255a87cfecb578bd92fd59ed5d64922252d97fc77e4fd300784eea89e51f80760221008f1f123fcb419908dfe1ab61df1d768f2049f3bba57975fd00b6199046ed5069
3044022073c05467ba7b7494cf555b25d87fabe60e771d5bec04440017b72bf8c6f369e20220645f061baea9e64ab26296c06992d6375deab5dae3197f2e8c00d1e8208ed424
3046022100a8d9f61a674d0c2c33a315f2b39ed5aa209caf77287900713d21b71579d370f1022100e1a10e7ad5fb35a3b9a120b9d2dd4e06c82d478546249c006ae7ce571ca25899
3046022100bad3f490830c00031f0c9c48d233fd2cf0a2a380b4da0069c5e72d93c173aeda022100cf500cf504f281a74994e4d14e3b4176bfdddeae1bf53200834e4a26e7835ca4
304402204dca5e0205de87527f3a6cb441971c12375978c04172b300515f09c9544eecb10220735f77895021f228448ef40fb5a20c17979b07b29d047b206a00edf3e4ef35b2
304402200c58a2af05b52e22204aa8b665ccf0e7ac26219d518350ff71dc5a8cce3eb71002206bb7e4048c2dd758f69970a534176ed276563e5de605f3783a00d0741afa98fc
3044022052529d097530db109a2d4abf6b7153423e713f6b98e6f7ff34378a950bd534bd02202411585bd37ea0f37ac876adf4fd66e234481d610cd024d7a5008e9d7d00ba2a
304502206fd07059190a0a911fb17ad9db6c3effce9980747833c5ff6835a4777baf210e022100e9682236b9c62318df5c3a885d581df417ba917dcc254d5400f8c15e528a1ca2
3045022100fadb120ee656e5b15d1f627d16cf22342a029fcf3580ff2d0f3b6a7f6ffd2bd6022058ab8f851fd27694476a3cf9efcd86511baee8342231861b00f0c9ef12def41e
30450220157dada2594d8deeb796a1febc22a4d6f37d9ae70cf474008b41261d7804872a022100c3f1b2caa33f7630a99e5eeaccf54a2b71d0a16b2384e2dafff81b7e25b9ce97
3045022016ed0e589674cd6da54bbadda751199a1a3b8b7907df2500d46b0719ba5c2db9022100b018f3416d3ae4116b50e18e6c0204e8574fcf03fc56694dff6ea776bc0f3259
304402205c4e5588d8eec6fec579e0f312d0528f4312a89c34862e007466f89e21fdd5600220469273b123361889281595ea4ed50b9340ed5fd0613de2f30eff774874225b76
304502207349da2efe4de858e2cb0aef7cfd06cf0027ad2b5e47b70021a3b3bf885bfeea022100876d52c01fcfbe9cba9f315ffad529f047428f0482c9b535ff5372d487ef3bf2
3045022030c0efecadc6e5e8c09c86ca8084df1711817882cf4d28018faf98d578e84a5d0221008d65c4af49e1de65bdb5bbc5453ddc107b913ece9012712402e3902be4da47e5
30440220085ac17ad265c0a40891f357cd9a323d94743b20f100d30330ae331d086ba2490220402f9a53c8b3e087c61f9df8efe0c78b4e95f1dcc3e2c5757104af9eac0380f2
3045022100dd063e119149e1b902a2d4cad08e823f018bdb175a8105cbf158cbefd9659f80022022564ba20b5fd65780a14bfb34a665e20c20f979bc4fb06e06e378d2d2225acf
3045022100eaf76c3f2f94a9f9e66ddad40ab36721a09a670dffc907390d01b8c87170cf7d02202189be2ee195869d4a7fac206b5624787c7a1b03e58b8903084ae6986a207f9c
3046022100d028bd2d3587abbed253615da8e67bb8d9006c4b2baa138d688b1a3a0d296274022100c55309b7de2af7a8d96f266892718d89792369fd23fe1737f8833eda31a9b1aa
3045022100dec32fe7b0a2e7fa407cdf2a6bb1bc3675fcb1ff39ce1360526093cde12172e0022033aab7cc7e3b42a24813f68a1495b331e3b9ac4ffa2fcb413778b1600d7f055e
^^ ^^
If you look carefully at the column of bytes I have put the VV and ^^ markers on you'll see that I am *in control* of those bytes that are part of the ECDSA signature (because of the looping).
What am I actually doing?
I am *mining* the signature in order to store information in it (possible because of the *random* k value that is used when creating such signatures).
How could this be useful?
Imagine Bob wishes to send his friend Jane a private small message. Firstly he would send a normal Bitcoin transaction to Jane (exposing the public key of a UTXO he owns) and then Jane would send a transaction back (exposing her public key). Using ECDSA it is now possible for Bob and Jane to create a "shared secret" (same as is done for Stealth Addresses).
After this Bob would ask Jane for a new address and then Bob would encrypt his message with the "shared secret" and embed it into a set of UTXOs within the actual ECDSA signatures which would be sent to Jane as a normal Bitcoin transaction (nothing to make it stand out like OP_RETURN at all).
Jane knowing that this came from Bob and it has been sent to the address she gave him to send the secret message to can now use her "shared secret" to extract this message.
My initial tests suggest that on average hardware a small message (say 50 characters) might take an hour or so to "mine" (althugh I made no attempt to optimise anything).
Is this useful?
I think it could be of some use in at least providing another way that small amounts of data can be stored in the blockchain without it being at all *obvious* that such data is actually there.
Enjoy!
Jump to: