{"thread":{"id":"5482","subject":"Re: Starting to think about sha-256?","startedAt":"2006-09-05T09:05:21Z","lastAt":"2006-09-05T09:05:21Z","messageCount":1,"participants":["linux@horizon.com"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26354","messageId":"20060905090521.24944.qmail@science.horizon.com","threadId":"5482","inReplyTo":null,"subject":"Re: Starting to think about sha-256?","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-05T09:05:21Z","receivedAt":"2006-09-05T09:05:21Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"For those worrying, note that even a \"complete\" break of SHA-1 doesn't\nimply the ability to sneak a trojan into a git repository via a patch\nor something.\n\nWhat cryptographers consider a break is finding a collision, two messages\nx and y such that hash(x) == hash(y).  But note that the attacker gets\nto pick both x and y!\n\nA so-called second pre-image attack, where x is fixed beforehand is far\nharder, even if you get to choose from the 320K or so objects in the\nlinux kernel repository.\n\nMerely inducing you to somehow import the trojan object y into your\nobject database doesn't help unless you trust and are willing to build\nand run source including the object x that it is a doppelgänger for.\nSo, armed with only a collision-finding attack, the attacker has to\ncreate a collision pair including an innocent source file that can get\nincluded (without any bizarre contents getting \"fixed\" by a maintainer)\nbefore anyone can attempt to substitute the trojan y.\n\nThat requirement eliminates most collision attacks, which generate\ngood-sized binary blobs.  There's a demo where someone did it with a\npostscript file, but that was basically\n\n\tif (parity(\"line noise\"))\n\t\tprint innocent message\n\telse\n\t\tprint trojan message\n\nNow, admittedly, this sort of fine reasoning does reduce the possible\napplication domain of git to human-readable source.  If I'm using git\nas a back-end for (say) an archive of statically verified but opaque\njava byte-code files, then there's potential for trouble.\n\nBut I just want to remind people that even if a \"complete\" break of SHA-1\nwere announced tomorrow, it wouldn't imply that using git is dangerous.\nFrankly, it would *still* probably be less work to hide a trojan in the\nsource code well enough that it sneaks under the maintainer's radar.\n\n\n> Why? Because a git SHA1 is actually _not_ the SHA1 of the file itself, \n> it's the SHA1 of the file _with_the_git_header_added_.\n> \n> So if you find two files that have the same SHA1, they would also have to \n> have the same length in order to actually generate the same object name. \n> If they have different lenths, you can just check them into git, and \n> they'll get two different git SHA1 names and you'll have a cool git \n> archive that when you check the files out, they checked-out files will \n> share the same SHA1 ;)\n\nThis has always seemed silly to me.  Every cryptographic hash\nalgorithm since the (catastrophically broken) MD4 has used the standard\nMerkle-Damgård strengthening construction to include the length.\nThere's no point in doing it a second time.\n\nIt's done as a suffix, not a prefix, but it's there.  And an odd-sized\nprefix makes it hard to have a fast-path aligned hash for the bulk of\nthe data on machines with alignment restrictions.\n\nNow, the case can be made that a prefix is slightly stronger \n(http://cs.nyu.edu/~puniya/papers/merkle.pdf), but I don't think\nthat's why it was done.\n\nNote that since the length is included, you can avoid the odd-sized prefix\nproblem by putting any extra data you like on the hash as a trailer.\nAs long as it's suffix-free, (e.g. leading null byte), you haven't\nhurt anything.\n\n\n\nAnyway, SHA-256 is tricky on x86, because it has 8 words of state and\nx86 has only 7 registers.\n\nBut here's some (public domain) code which works well on x86, and doesn't\nsuck too badly on other processors.  It's designed to be benchmarked\nagainst Brian Gladman's implementation; if you have that, change the\nobvious #define and link against sha2.o.\n\nThe other interesting benchmark is \"nm -n *.o\"; on x86, it's 290 bytes\nof core transform vs. 4773 bytes for sha256_compile.\n\n\n#include <stdint.h>\n#include <stdio.h>\n#include <string.h>\n\n#define DEBUG 0\n#define HAVE_GLADMAN_CODE 0\n\nstruct sha256_state {\n\tuint32_t iv[8];\t/* h, g, f, e, d, c, b, a */\n\tuint32_t w[64];\t/* Fill in first 16 with ntohl(input) */\n\tuint32_t d2, c2, b2, a2;\n\tuint32_t bytes_hi, bytes_lo;\n};\n\n/* Rotate right macro.  GCC can usually get this right. */\n#define ROTR(x,s) ((x)>>(s) | (x)<<(32-(s)))\n\n/*\n * An implementation of SHA-256 for register-starved architectures like\n * x86 or perhaps the MSP430.  (Although the latter's lack of a multi-bit\n * shifter will doom its performance no matter what.)\n * This code is also quite small.\n *\n * If you have 12 32-bit registers to work with, loading the 8 state\n * variables into registers is probably faster.  If you have 28 registers\n * or so, you can put the input block into registers as well.\n *\n * The key idea is to notice that each round consumes one word from the\n * key schedule w[i], computes a new a, and shifts all the other state\n * variables down one position, discarding the old h.\n *\n * So if we store the state vector in reverse order h..a, immediately\n * before w[i], then a single base pointer can be incremented to advance\n * to the next round.\n */\nvoid\nsha256_transform(uint32_t p[76])\n{\n\tstatic uint32_t const k[64] = {\n\t\t0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b,\n\t\t0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01,\n\t\t0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7,\n\t\t0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,\n\t\t0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152,\n\t\t0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147,\n\t\t0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,\n\t\t0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,\n\t\t0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819,\n\t\t0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08,\n\t\t0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f,\n\t\t0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,\n\t\t0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2\n\t};\n\t/*\n\t * Look, ma, only 6 local variables including p!\n\t * Too bad they're so overloaded it's impossible to give them\n\t * meaningful names.\n\t */\n\tregister uint32_t const *kp;\n\tregister uint32_t a, s, t, u;\n\n\t/* Step 1: Expand the 16 words of w[], at p[8..23] into 64 words */\n\tfor (u = 8; u < 8+64-16; u++) {\n\t\t/* w[i] = s1(w[i-2]) + w[i-7] + s0(w[i-15]) + w[i-16] */\n\t\t/* Form s0(x) = (x >>> 7) ^ (x >>> 18) ^ (x >> 3) */\n\t\ts = t = p[u+1];\n\t\ts = ROTR(s, 18-7);\n\t\ts ^= t;\n\t\ts = ROTR(s, 7);\n\t\ts ^= t >> 3;\n\t\t/* Form s1(x) = (x >>> 17) ^ (x >>> 19) ^ (x >> 10) */\n\t\ta = t = p[u+14];\n\t\ta = ROTR(a, 19-17);\n\t\ta ^= t;\n\t\ta = ROTR(a, 17);\n\t\ta ^= t >> 10;\n\n\t\tp[u+16] = s + a + p[u] + p[u+9];\n\t}\n\n\t/* Step 2: Copy the initial values of d, c, b, a out of the way */\n\tp[72] = p[4];\n\tp[73] = p[5];\n\tp[74] = p[6];\n\tp[75] = a = p[7];\n\n\t/*\n\t * Step 3: The big loop.\n\t * We maintain p[0..7] = h..a, and p[8] is w[i]\n\t * Only the variable a is actually kept in a local register.\n\t */\n\tkp = k;\n\n\tdo {\n\t\t/* T1 = h + S1(e) + Ch(e,f,g) + k[i] + w[i] */\n\t\t/* Form Ch(e,f,g) = g ^ (e & (f ^ g)) */\n\t\ts = t = p[1];\t/* g */\n\t\ts ^= p[2];\t/* f ^ g */\n\t\ts &= u = p[3];\t/* e & (f ^ g), copy of e left in u */\n\t\ts ^= t;\n\t\t/* Form S1(e) = (e >>> 6) ^ (e >>> 11) ^ (e >>> 25) */\n\t\tt = u;\n\t\tu = ROTR(u, 25-11);\n\t\tu ^= t;\n\t\tu = ROTR(u, 11-6);\n\t\tu ^= t;\n\t\tu = ROTR(u, 6);\n\t\ts += u;\n\t\t/* Now add other things to t1 */\n\t\ts += p[0] + p[8] + *kp;\t/* h + w[i] + kp[i] */\n\t\t/* Round function: e = d + T1 */\n\t\tp[4] += s;\n\t\t/* a = t1 + (t2 = S0(a) + Maj(a,b,c) */\n\t\t/* Form S0(a) = (a >>> 2) ^ (a >>> 13) ^ (a >>> 22) */\n\t\tt = a;\n\t\tt = ROTR(t, 22-13);\n\t\tt ^= a;\n\t\tt = ROTR(t, 13-2);\n\t\tt ^= a;\n\t\tt = ROTR(t, 2);\n\t\ts += t;\n\t\t/* Form Maj(a,b,c) = (a & b) + (c & (a ^ b)) */\n\t\tu = p[6];\t/* b */\n\t\tt = a;\n\t\ta ^= u;\t\t/* a ^ b */\n\t\tu &= t;\t\t/* a & b */\n\t\ta &= p[5];\t/* c & (a + b) */\n\t\ts += u;\n\t\ta += s;\t/* Sum final result into a */\n\n\t\t/* Now store new a on top of w[i] and shift... */\n\t\tp[8] = a;\n\t\tp++;\n#if DEBUG \n\t\t/* If debugging, print out the state variables each round */\n\t\tprintf(\"%2u:\", kp-k);\n\t\tfor (t = 8; t--; )\n\t\t\tprintf(\" %08x\", p[t]);\n\t\tputchar('\\n');\n#endif\n\t} while (++kp != k+64);\n\n\t/* Now, do the final summation. */\n\tkp = p;\n\tp -= 64;\n\t/*\n\t * Now, the final h..a are in p[64..71], and the initial values\n\t * are in p[0..7].  Except that p[4..7] got trashed in the loop\n\t * above, so use the copies we made.\n\t */\n\tp[0] += kp[0];\n\tp[1] += kp[1];\n\tp[2] += kp[2];\n\tp[3] += kp[3];\n\tp[4] = kp[4] + kp[8];\n\tp[5] = kp[5] + kp[9];\n\tp[6] = kp[6] + kp[10];\n\tp[7] = a     + kp[11];\n}\n\n/* Initial values H7..H0 for SHA-256, and SHA-224. Note reverse order! */\nstatic uint32_t const _sha256_iv[8] = {\n\t0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,\n\t0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667\n};\nstatic uint32_t const _sha224_iv[8] = {\n\t0xbefa4fa4, 0x64f98fa7, 0x68581511, 0xffc00b31,\n\t0xf70e5939, 0x3070dd17, 0x367cd507, 0xc1059ed8\n};\n\n#if HAVE_GLADMAN_CODE\n\n#include \"sha2.h\"\n\n#else\n\n/* Compatibility wrappers */\n\ntypedef struct sha256_state sha256_ctx;\n\nvoid\nsha256_begin(struct sha256_state *s)\n{\n\tmemcpy(s->iv, _sha256_iv, sizeof _sha256_iv);\n\ts->bytes_lo = s->bytes_hi = 0;\n}\n\n#include <netinet/in.h>\t/* For ntohl, htohl */\n\nvoid\nsha256_hash(unsigned char const *data, size_t len, struct sha256_state *s)\n{\n\tunsigned space = 64 - (unsigned)s->bytes_lo % 64;\n\tunsigned i;\n\n\ts->bytes_lo += (uint32_t)len;\n\ts->bytes_hi += s->bytes_lo < (uint32_t)len;\n\tif ((size_t)-1 > (uint32_t)-1)\n\t\ts->bytes_hi += (uint32_t)(len >> 16 >> 16);\n\n\twhile (len >= space) {\n\t\tmemcpy((unsigned char *)s->w + 64 - space, data, space);\n\t\tlen -= space;\n\t\tspace = 64;\n\t\tfor (i = 0; i < 16; i++)\n\t\t\ts->w[i] = ntohl(s->w[i]);\n\t\tsha256_transform(s->iv);\n\t}\n\tmemcpy((unsigned char *)s->w + 64 - space, data, len);\n}\n\nvoid\nsha256_end(unsigned char hash[32], struct sha256_state *s)\n{\n\tunsigned i, pos = (unsigned)s->bytes_lo % 64;\n\tuint32_t *out;\n\n\t((unsigned char *)s->w)[pos++] = 0x80;\n\tif (pos > 56) {\n\t\tmemset((unsigned char *)s->w + pos, 0, 64-pos);\n\t\tfor (i = 0; i < 16; i++)\n\t\t\ts->w[i] = ntohl(s->w[i]);\n\t\tsha256_transform(s->iv);\n\t\tpos = 0;\n\t}\n\tmemset((unsigned char *)s->w + pos, 0, 56-pos);\n\tfor (i = 0; i < 14; i++)\n\t\ts->w[i] = ntohl(s->w[i]);\n\ts->w[15] = s->bytes_lo << 3;\n\ts->w[14] = s->bytes_hi << 3 | s->bytes_lo >> 29;\n\tsha256_transform(s->iv);\n\n\tout = (unsigned)hash % sizeof s->iv[0] ? s->w : (uint32_t *)hash;\n\tfor (i = 0; i < 8; i++)\n\t\tout[i] = htonl(s->iv[7-i]);\n\tif (out == s->w)\n\t\tmemcpy(hash, out, sizeof s->iv);\n\tmemset(s, 0, sizeof s);\t/* Good cryptographic hygiene */\n}\n\nvoid\nsha256(unsigned char hash[32], const unsigned char *data, size_t len)\n{\n\tstruct sha256_state s;\n\tsha256_begin(&s);\n\tsha256_hash(data, len, &s);\n\tsha256_end(hash, &s);\n}\n\n#endif /* !HAVE_GLADMAN_CODE */\n\n#include <string.h>\n#include <sys/time.h>\n\n#define TESTSIZE 100000000\n#if TESTSIZE & 64 != 0\n#error For now, TESTSIZE must be a multiple of 64.\n#endif\n\nint\nmain(void)\n{\n\tuint32_t array1[76] = {\n\t\t/* Initial values, h..a */\n\t\t0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,\n\t\t0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667,\n\t\t/* First 16 w[i] values */\n\t\t0x61626380, 0, 0, 0, 0, 0, 0, 0,\n\t\t0, 0, 0, 0, 0, 0, 0, 0x00000018\n\t};\n\tuint32_t array2[76] = {\n\t\t/* Initial values, h..a */\n\t\t0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,\n\t\t0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667,\n\t\t/* First 16 w[i] values */\n\t\t0x61626364, 0x62636465, 0x63646566, 0x64656667,\n\t\t0x65666768, 0x66676869, 0x6768696a, 0x68696a6b,\n\t\t0x696a6b6c, 0x6a6b6c6d, 0x6b6c6d6e, 0x6c6d6e6f,\n\t\t0x6d6e6f70, 0x6e6f7071, 0x80000000, 0x00000000\n\t};\n\tuint32_t array3[76] = {\n\t\t/* Initial values, h..a */\n\t\t0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,\n\t\t0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667\n\t};\n\tunsigned i;\n\tstruct timeval start, stop;\n\tsha256_ctx s256;\n\tunsigned char buf[64];\n\n\t/* The FIPS180-2 appendix B.1 example */\n\tprintf(\"Appendix B.1 example:\\n\");\n\tsha256_transform(array1);\n\tprintf(\"==>\");\n\tfor (i = 8; i--; )\n\t\tprintf(\" %08x\", array1[i]);\n\tputchar('\\n');\n\n\tprintf(\"\\nAppendix B.2 example:\\n\");\n\tsha256_transform(array2);\n\tprintf(\"==>\");\n\tfor (i = 8; i--; )\n\t\tprintf(\" %08x\", array2[i]);\n\tputchar('\\n');\n\tputchar('\\n');\n\n\tfor(i = 8; i < 23; i++)\n\t\tarray2[i] = 0;\n\tarray2[23] = 0x000001c0;\n\tsha256_transform(array2);\n\tprintf(\"==>\");\n\tfor (i = 8; i--; )\n\t\tprintf(\" %08x\", array2[i]);\n\tputchar('\\n');\n\n\t/* Now to hash 1,000,000 letters 'a' */\n\tprintf(\"\\nAppendix B.3 example:\\n\");\n\n\tgettimeofday(&start, 0);\n\tfor (i = 0; i < TESTSIZE/64; i++) {\n\t\tmemset((char *)(array3+8), 'a', 64);\n\t\tsha256_transform(array3);\n\t}\n\tarray3[8] = 0x80000000;\n\tarray3[23] = i*64*8;\t/* Length in bits */\n\tfor (i = 9; i < 23; i++)\n\t\tarray3[i] = 0;\n\tsha256_transform(array3);\n\tgettimeofday(&stop, 0);\n\tstop.tv_sec -= start.tv_sec;\n\tstop.tv_usec -= start.tv_usec;\n\tif (stop.tv_usec < 0) {\n\t\tstop.tv_usec += 1000000;\n\t\tstop.tv_sec--;\n\t}\n\tprintf(\"New code: %u.%06ld\\n\", (unsigned)stop.tv_sec, stop.tv_usec);\n\tprintf(\"==>\");\n\tfor (i = 8; i--; )\n\t\tprintf(\" %08x\", array3[i]);\n\tputchar('\\n');\n\n\n\tsha256_begin(&s256);\n\tgettimeofday(&start, 0);\n\tfor (i = 0; i < TESTSIZE/64; i++) {\n\t\tmemset(buf, 'a', 64);\n\t\tsha256_hash(buf, 64, &s256);\n\t}\n\tsha256_end(buf, &s256);\n\tgettimeofday(&stop, 0);\n\tstop.tv_sec -= start.tv_sec;\n\tstop.tv_usec -= start.tv_usec;\n\tif (stop.tv_usec < 0) {\n\t\tstop.tv_usec += 1000000;\n\t\tstop.tv_sec--;\n\t}\n\tprintf(\n#if HAVE_GLADMAN_CODE\n\t\t\"Gladman code: %u.%06ld\\n\",\n#else\n\t\t\"Wrapper code: %u.%06ld\\n\",\n#endif\n\t\t(unsigned)stop.tv_sec, stop.tv_usec);\n\n\tprintf(\"==>\");\n\tfor (i = 0; i < 32; i++) {\n\t\tif (i % 4 == 0)\n\t\t\tputchar(' ');\n\t\tprintf(\"%02x\", buf[i]);\n\t}\n\tputchar('\\n');\n\n\treturn 0;\n}\n"}]}