Development Update #50

Changes

Skycoin Transactions are

I noticed something interesting.

The key for the first 16 rounds in SHA256 are the 16 message blocks in order. A compressed pubkey is 33 bytes. SHA256 takes input, breaks it into 512 bit blocks, adds a 64 bit length to end and then pads with 1 followed by zeros. The padding is fixed after the 33 bytes. Most of the bits in the input are fixed. The compression function takes in two 256 bit blocks and compresses to a 256 bit output. However, almost half of the inputs are determined. For SHA256(SHA256(x)) for 256 bit x and for SHA256(pubkey) for 33 byte compressed pubkey.

The key schedule for 0 to 16, is just the two 256 bit input blocks block up into 32 bit segments, in order for i from 0 to 15 w = w The key schedule from 16 to 63 is for i from 16 to 63 s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3) s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10) w := w[i-16] + s0 + w[i-7] + s1

w[8] to w[15] are fixed. 1 followed by zero padding. For any 256 bit input to SHA256 this is true. For compressed secp256k1 pubkey of 33 bytes, the w[9] to w[15] are known. The padding that fills w[8] to w[15] is only a function of the length of the input, where input length is less than or equal to 256 bits. - For bitcoin mining, most of the fields/bits are fixed for the problem. Everything except nonce bits. - For hashing a compressed pubkey to address of the 64 bytes of input to the compression function forming the key input, 33 bytes are fixed/known. - 3-SAT can invert 20 rounds assuming 512 bits of entropy in input and naive SHA256 encoding. If half the bits in the key schedule are already known, may be exponentially easier than solving for a 512 unknown bits in key schedule. If you modify SHA256 to take out the mixing and feedback in the key schedule, then this appears insecure against 3-SAT attack. The first 16 rounds fall quickly, but only 4 rounds can be broken after the key schedule mixing starts in round 16. - For Bitcoin mining, only ~32 bits in the key schedule appear undetermined which are unknown - w[0] to w[15] are just the two 512 bit input blocks. - There is optimized SHA256 encoding using carry-save adders, used for mining that is simpler to work on and may be faster - If you can find preimage for SHA256(x) for 256 bit x (x is expanded to 512 bit block but the last 256 bits are padding knows bits are known in advance), you can can find preimage for SHA256(SHA256(x)) - Ripemd160 is a similar Merkle–Damgård compression function. If you can break SHA256 with that attack its likely to break Ripemd160 - If you can preimage Ripemd160, you get random SHA256(x) for 256 bit x (and 256 bits of known padding bits in key schedule) which you then preimage to get a random compressed secp256k1 pubkey - If the probability that a random secp256k1 pubkey is weak, is 1 in 1024, then you have to do this on average 1024 times, before you get a pubkey that is valid for the address, which you can recover the private key for. If almost all randomly generated public keys are strong, then attack fails. - We know that almost all randomly generated secret keys produce strong public keys (public keys we cannot recover the private key for). The secret key is 32 bytes and the compressed public key is 33 bytes. - Recovering the private key from a random public key is the discrete logarithm problem on an elliptic curve. I dont know what percentage of random points on the curve, have easily recoverable exponents. It is probably close to zero. - The majority of headers do not have a 32 bit nonce that puts the output hash below the current difficulty target. Trying to use 3-SAT for mining would be more interesting and practical with a 64 bit nonce. I think in benchmarks it beat CPU mining with brute force trial and error SHA256 hashing, then brute force became more competitive as difficulty increased. Its not clear why. Now, brute force SHA256 miners commonly run through the nonce without generating a block below the target, so its futile even if there was fast algorithm.

No translation bounty

Discuss this post on telegram

Skycoin Telegram