fpgaminer (OP)
|
|
October 20, 2013, 08:25:08 AM |
|
EEPROM Checksum AlgorithmI finally reverse engineered the algorithm KNC is using to checksum the ASIC board EEPROMs. I had initially thought it was just SHA-256, but a quick try with that failed. After digging into the code my original hypothesis proved correct, it's SHA-256, but KNC has ... taken some liberties with SHA-256. It's pretty confusing code. First, the checksum function is completely broken unless the data being checksummed is a multiple of 64 bytes (the data in the EEPROMs is). Second, they use SHA-256 without any padding. Third, they use SHA-256 with their own KNC flavored initial state. Their initial state is the ASCII representation of "KnCMiner placeholder SHA256 init". I've recreated the important bits of the algorithm in Python: # SHA-256 implementation copied from pypy/lib_pypy/_sha256.py, which is licensed under the MIT license: # https://github.com/pypy/pypy/blob/master/lib_pypy/_sha256.py # https://github.com/pypy/pypy/blob/master/LICENSE import struct
SHA_BLOCKSIZE = 64 SHA_DIGESTSIZE = 32
def new_shaobject(): return { 'digest': [0]*8, 'count_lo': 0, 'count_hi': 0, 'data': [0]* SHA_BLOCKSIZE, 'local': 0, 'digestsize': 0 }
ROR = lambda x, y: (((x & 0xffffffff) >> (y & 31)) | (x << (32 - (y & 31)))) & 0xffffffff Ch = lambda x, y, z: (z ^ (x & (y ^ z))) Maj = lambda x, y, z: (((x | y) & z) | (x & y)) S = lambda x, n: ROR(x, n) R = lambda x, n: (x & 0xffffffff) >> n Sigma0 = lambda x: (S(x, 2) ^ S(x, 13) ^ S(x, 22)) Sigma1 = lambda x: (S(x, 6) ^ S(x, 11) ^ S(x, 25)) Gamma0 = lambda x: (S(x, 7) ^ S(x, 18) ^ R(x, 3)) Gamma1 = lambda x: (S(x, 17) ^ S(x, 19) ^ R(x, 10))
def sha_transform(sha_info): W = [] d = sha_info['data'] for i in xrange(0,16): W.append( (d[4*i]<<24) + (d[4*i+1]<<16) + (d[4*i+2]<<8) + d[4*i+3]) for i in xrange(16,64): W.append( (Gamma1(W[i - 2]) + W[i - 7] + Gamma0(W[i - 15]) + W[i - 16]) & 0xffffffff ) ss = sha_info['digest'][:] def RND(a,b,c,d,e,f,g,h,i,ki): t0 = h + Sigma1(e) + Ch(e, f, g) + ki + W[i]; t1 = Sigma0(a) + Maj(a, b, c); d += t0; h = t0 + t1; return d & 0xffffffff, h & 0xffffffff ss[3], ss[7] = RND(ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],0,0x428a2f98); ss[2], ss[6] = RND(ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],1,0x71374491); ss[1], ss[5] = RND(ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],2,0xb5c0fbcf); ss[0], ss[4] = RND(ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],3,0xe9b5dba5); ss[7], ss[3] = RND(ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],4,0x3956c25b); ss[6], ss[2] = RND(ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],5,0x59f111f1); ss[5], ss[1] = RND(ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],6,0x923f82a4); ss[4], ss[0] = RND(ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],7,0xab1c5ed5); ss[3], ss[7] = RND(ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],8,0xd807aa98); ss[2], ss[6] = RND(ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],9,0x12835b01); ss[1], ss[5] = RND(ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],10,0x243185be); ss[0], ss[4] = RND(ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],11,0x550c7dc3); ss[7], ss[3] = RND(ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],12,0x72be5d74); ss[6], ss[2] = RND(ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],13,0x80deb1fe); ss[5], ss[1] = RND(ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],14,0x9bdc06a7); ss[4], ss[0] = RND(ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],15,0xc19bf174); ss[3], ss[7] = RND(ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],16,0xe49b69c1); ss[2], ss[6] = RND(ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],17,0xefbe4786); ss[1], ss[5] = RND(ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],18,0x0fc19dc6); ss[0], ss[4] = RND(ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],19,0x240ca1cc); ss[7], ss[3] = RND(ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],20,0x2de92c6f); ss[6], ss[2] = RND(ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],21,0x4a7484aa); ss[5], ss[1] = RND(ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],22,0x5cb0a9dc); ss[4], ss[0] = RND(ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],23,0x76f988da); ss[3], ss[7] = RND(ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],24,0x983e5152); ss[2], ss[6] = RND(ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],25,0xa831c66d); ss[1], ss[5] = RND(ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],26,0xb00327c8); ss[0], ss[4] = RND(ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],27,0xbf597fc7); ss[7], ss[3] = RND(ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],28,0xc6e00bf3); ss[6], ss[2] = RND(ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],29,0xd5a79147); ss[5], ss[1] = RND(ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],30,0x06ca6351); ss[4], ss[0] = RND(ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],31,0x14292967); ss[3], ss[7] = RND(ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],32,0x27b70a85); ss[2], ss[6] = RND(ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],33,0x2e1b2138); ss[1], ss[5] = RND(ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],34,0x4d2c6dfc); ss[0], ss[4] = RND(ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],35,0x53380d13); ss[7], ss[3] = RND(ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],36,0x650a7354); ss[6], ss[2] = RND(ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],37,0x766a0abb); ss[5], ss[1] = RND(ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],38,0x81c2c92e); ss[4], ss[0] = RND(ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],39,0x92722c85); ss[3], ss[7] = RND(ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],40,0xa2bfe8a1); ss[2], ss[6] = RND(ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],41,0xa81a664b); ss[1], ss[5] = RND(ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],42,0xc24b8b70); ss[0], ss[4] = RND(ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],43,0xc76c51a3); ss[7], ss[3] = RND(ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],44,0xd192e819); ss[6], ss[2] = RND(ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],45,0xd6990624); ss[5], ss[1] = RND(ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],46,0xf40e3585); ss[4], ss[0] = RND(ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],47,0x106aa070); ss[3], ss[7] = RND(ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],48,0x19a4c116); ss[2], ss[6] = RND(ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],49,0x1e376c08); ss[1], ss[5] = RND(ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],50,0x2748774c); ss[0], ss[4] = RND(ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],51,0x34b0bcb5); ss[7], ss[3] = RND(ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],52,0x391c0cb3); ss[6], ss[2] = RND(ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],53,0x4ed8aa4a); ss[5], ss[1] = RND(ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],54,0x5b9cca4f); ss[4], ss[0] = RND(ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],55,0x682e6ff3); ss[3], ss[7] = RND(ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],56,0x748f82ee); ss[2], ss[6] = RND(ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],57,0x78a5636f); ss[1], ss[5] = RND(ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],ss[5],58,0x84c87814); ss[0], ss[4] = RND(ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],ss[4],59,0x8cc70208); ss[7], ss[3] = RND(ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],ss[3],60,0x90befffa); ss[6], ss[2] = RND(ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],ss[2],61,0xa4506ceb); ss[5], ss[1] = RND(ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],ss[1],62,0xbef9a3f7); ss[4], ss[0] = RND(ss[1],ss[2],ss[3],ss[4],ss[5],ss[6],ss[7],ss[0],63,0xc67178f2); dig = [] for i, x in enumerate(sha_info['digest']): dig.append( (x + ss[i]) & 0xffffffff ) sha_info['digest'] = dig
whole_data = "4131303030303037424245434600000000000000000000000000000000000000000000000000000000000000000100000800000000000000ffffffffffffffff003084005687840174fa8402c03484038f7a860001d1860101d1860201d1860301d18500db118501b7d785023cce85033d1ce7e375f7fe6521ea8991253ae7ed".decode ('hex')
sha_info = new_shaobject () sha_info['digest'] = [0x4b6e434d, 0x696e6572, 0x20706c61, 0x6365686f, 0x6c646572, 0x20534841, 0x32353620, 0x696e6974] sha_info['data'] = [ord (whole_data[i]) for i in range (0, 64)] sha_transform (sha_info) sha_info['data'] = [ord (whole_data[i]) for i in range (64, 128)] sha_transform (sha_info)
for i in range (8): print "%08X" % sha_info['digest'][i]
whole_data in the code above is a copy of the data off one of my ASIC board EEPROMs (without the first 32 bytes, which is the stored checksum). The code prints the calculated checksum, which matched the EEPROM I tested. So, yay, but it really makes me wonder what the KNC developers were doing. I can understand not doing the padding and only working on multiples of 64 bytes; the devs probably had higher priorities. I just don't understand the initial state thing. The real SHA-256 initial state values exist within initc. It's just that the checksum function overwrites them. Wonky. Progress UpdateWe can use this to update our EEPROMs and have initc accept the checksum. I still don't know how to make sense of the PLL configuration data, but some progress is better than none. I also manually decompiled the write_eeprom function of initc. It's nothing special though, I can craft modified EEPROM data by hand easily and just use the command line to write it. Regarding the PLL configuration data. When write_eeprom is building a new EEPROM image it first fills the buffer with random data (calling rand()). This explains why the padding on all the EEPROMs was garbage data. I'm not sure why they do it, though. It leads me to believe, though, that KNC's developers may have a habit of filling unused data with rand. Perhaps the PLL 0x84 and 0x85 registers are unused in the current ASIC revision? Maybe they were used by their FPGA prototype(s). Most importantly, perhaps only 0x86 is important, and is simply a multiplier value (or two 8-bit values, Multiplier and Divider). I don't know what the chip's input clock frequency is, so it's hard to make an educated guess about how to interpret the current setting. That theory could be tested by adjusting the 0x86 registers of the PLL data and ... seeing what happens. Though if the theory is wrong, doing so could potentially set the chips a blaze. I don't personally want to try that (yet) ... if anyone with bigger balls than I wants to do so, feel free to try... I'll continue decompiling initc to see if there are more hints as to the meaning of the PLL data.
|