For those worrying, note that even a "complete" break of SHA-1 doesn't
imply the ability to sneak a trojan into a git repository via a patch
or something.
What cryptographers consider a break is finding a collision, two messages
x and y such that hash(x) == hash(y). But note that the attacker gets
to pick both x and y!
A so-called second pre-image attack, where x is fixed beforehand is far
harder, even if you get to choose from the 320K or so objects in the
linux kernel repository.
Merely inducing you to somehow import the trojan object y into your
object database doesn't help unless you trust and are willing to build
and run source including the object x that it is a doppelgänger for.
So, armed with only a collision-finding attack, the attacker has to
create a collision pair including an innocent source file that can get
included (without any bizarre contents getting "fixed" by a maintainer)
before anyone can attempt to substitute the trojan y.
That requirement eliminates most collision attacks, which generate
good-sized binary blobs. There's a demo where someone did it with a
postscript file, but that was basically
if (parity("line noise"))
print innocent message
else
print trojan message
Now, admittedly, this sort of fine reasoning does reduce the possible
application domain of git to human-readable source. If I'm using git
as a back-end for (say) an archive of statically verified but opaque
java byte-code files, then there's potential for trouble.
But I just want to remind people that even if a "complete" break of SHA-1
were announced tomorrow, it wouldn't imply that using git is dangerous.
Frankly, it would *still* probably be less work to hide a trojan in the
source code well enough that it sneaks under the maintainer's radar.
> Why? Because a git SHA1 is actually _not_ the SHA1 of the file itself,
> it's the SHA1 of the file _with_the_git_header_added_.
>
> So if you find two files that have the same SHA1, they would also have to
> have the same length in order to actually generate the same object name.
> If they have different lenths, you can just check them into git, and
> they'll get two different git SHA1 names and you'll have a cool git
> archive that when you check the files out, they checked-out files will
> share the same SHA1 ;)
This has always seemed silly to me. Every cryptographic hash
algorithm since the (catastrophically broken) MD4 has used the standard
Merkle-Damgård strengthening construction to include the length.
There's no point in doing it a second time.
It's done as a suffix, not a prefix, but it's there. And an odd-sized
prefix makes it hard to have a fast-path aligned hash for the bulk of
the data on machines with alignment restrictions.
Now, the case can be made that a prefix is slightly stronger
(http://cs.nyu.edu/~puniya/papers/merkle.pdf), but I don't think
that's why it was done.
Note that since the length is included, you can avoid the odd-sized prefix
problem by putting any extra data you like on the hash as a trailer.
As long as it's suffix-free, (e.g. leading null byte), you haven't
hurt anything.
Anyway, SHA-256 is tricky on x86, because it has 8 words of state and
x86 has only 7 registers.
But here's some (public domain) code which works well on x86, and doesn't
suck too badly on other processors. It's designed to be benchmarked
against Brian Gladman's implementation; if you have that, change the
obvious #define and link against sha2.o.
The other interesting benchmark is "nm -n *.o"; on x86, it's 290 bytes
of core transform vs. 4773 bytes for sha256_compile.
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#define DEBUG 0
#define HAVE_GLADMAN_CODE 0
struct sha256_state {
uint32_t iv[8]; /* h, g, f, e, d, c, b, a */
uint32_t w[64]; /* Fill in first 16 with ntohl(input) */
uint32_t d2, c2, b2, a2;
uint32_t bytes_hi, bytes_lo;
};
/* Rotate right macro. GCC can usually get this right. */
#define ROTR(x,s) ((x)>>(s) | (x)<<(32-(s)))
/*
* An implementation of SHA-256 for register-starved architectures like
* x86 or perhaps the MSP430. (Although the latter's lack of a multi-bit
* shifter will doom its performance no matter what.)
* This code is also quite small.
*
* If you have 12 32-bit registers to work with, loading the 8 state
* variables into registers is probably faster. If you have 28 registers
* or so, you can put the input block into registers as well.
*
* The key idea is to notice that each round consumes one word from the
* key schedule w[i], computes a new a, and shifts all the other state
* variables down one position, discarding the old h.
*
* So if we store the state vector in reverse order h..a, immediately
* before w[i], then a single base pointer can be incremented to advance
* to the next round.
*/
void
sha256_transform(uint32_t p[76])
{
static uint32_t const k[64] = {
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b,
0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01,
0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7,
0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152,
0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147,
0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,
0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819,
0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08,
0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f,
0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};
/*
* Look, ma, only 6 local variables including p!
* Too bad they're so overloaded it's impossible to give them
* meaningful names.
*/
register uint32_t const *kp;
register uint32_t a, s, t, u;
/* Step 1: Expand the 16 words of w[], at p[8..23] into 64 words */
for (u = 8; u < 8+64-16; u++) {
/* w[i] = s1(w[i-2]) + w[i-7] + s0(w[i-15]) + w[i-16] */
/* Form s0(x) = (x >>> 7) ^ (x >>> 18) ^ (x >> 3) */
s = t = p[u+1];
s = ROTR(s, 18-7);
s ^= t;
s = ROTR(s, 7);
s ^= t >> 3;
/* Form s1(x) = (x >>> 17) ^ (x >>> 19) ^ (x >> 10) */
a = t = p[u+14];
a = ROTR(a, 19-17);
a ^= t;
a = ROTR(a, 17);
a ^= t >> 10;
p[u+16] = s + a + p[u] + p[u+9];
}
/* Step 2: Copy the initial values of d, c, b, a out of the way */
p[72] = p[4];
p[73] = p[5];
p[74] = p[6];
p[75] = a = p[7];
/*
* Step 3: The big loop.
* We maintain p[0..7] = h..a, and p[8] is w[i]
* Only the variable a is actually kept in a local register.
*/
kp = k;
do {
/* T1 = h + S1(e) + Ch(e,f,g) + k[i] + w[i] */
/* Form Ch(e,f,g) = g ^ (e & (f ^ g)) */
s = t = p[1]; /* g */
s ^= p[2]; /* f ^ g */
s &= u = p[3]; /* e & (f ^ g), copy of e left in u */
s ^= t;
/* Form S1(e) = (e >>> 6) ^ (e >>> 11) ^ (e >>> 25) */
t = u;
u = ROTR(u, 25-11);
u ^= t;
u = ROTR(u, 11-6);
u ^= t;
u = ROTR(u, 6);
s += u;
/* Now add other things to t1 */
s += p[0] + p[8] + *kp; /* h + w[i] + kp[i] */
/* Round function: e = d + T1 */
p[4] += s;
/* a = t1 + (t2 = S0(a) + Maj(a,b,c) */
/* Form S0(a) = (a >>> 2) ^ (a >>> 13) ^ (a >>> 22) */
t = a;
t = ROTR(t, 22-13);
t ^= a;
t = ROTR(t, 13-2);
t ^= a;
t = ROTR(t, 2);
s += t;
/* Form Maj(a,b,c) = (a & b) + (c & (a ^ b)) */
u = p[6]; /* b */
t = a;
a ^= u; /* a ^ b */
u &= t; /* a & b */
a &= p[5]; /* c & (a + b) */
s += u;
a += s; /* Sum final result into a */
/* Now store new a on top of w[i] and shift... */
p[8] = a;
p++;
#if DEBUG
/* If debugging, print out the state variables each round */
printf("%2u:", kp-k);
for (t = 8; t--; )
printf(" %08x", p[t]);
putchar('\n');
#endif
} while (++kp != k+64);
/* Now, do the final summation. */
kp = p;
p -= 64;
/*
* Now, the final h..a are in p[64..71], and the initial values
* are in p[0..7]. Except that p[4..7] got trashed in the loop
* above, so use the copies we made.
*/
p[0] += kp[0];
p[1] += kp[1];
p[2] += kp[2];
p[3] += kp[3];
p[4] = kp[4] + kp[8];
p[5] = kp[5] + kp[9];
p[6] = kp[6] + kp[10];
p[7] = a + kp[11];
}
/* Initial values H7..H0 for SHA-256, and SHA-224. Note reverse order! */
static uint32_t const _sha256_iv[8] = {
0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667
};
static uint32_t const _sha224_iv[8] = {
0xbefa4fa4, 0x64f98fa7, 0x68581511, 0xffc00b31,
0xf70e5939, 0x3070dd17, 0x367cd507, 0xc1059ed8
};
#if HAVE_GLADMAN_CODE
#include "sha2.h"
#else
/* Compatibility wrappers */
typedef struct sha256_state sha256_ctx;
void
sha256_begin(struct sha256_state *s)
{
memcpy(s->iv, _sha256_iv, sizeof _sha256_iv);
s->bytes_lo = s->bytes_hi = 0;
}
#include <netinet/in.h> /* For ntohl, htohl */
void
sha256_hash(unsigned char const *data, size_t len, struct sha256_state *s)
{
unsigned space = 64 - (unsigned)s->bytes_lo % 64;
unsigned i;
s->bytes_lo += (uint32_t)len;
s->bytes_hi += s->bytes_lo < (uint32_t)len;
if ((size_t)-1 > (uint32_t)-1)
s->bytes_hi += (uint32_t)(len >> 16 >> 16);
while (len >= space) {
memcpy((unsigned char *)s->w + 64 - space, data, space);
len -= space;
space = 64;
for (i = 0; i < 16; i++)
s->w[i] = ntohl(s->w[i]);
sha256_transform(s->iv);
}
memcpy((unsigned char *)s->w + 64 - space, data, len);
}
void
sha256_end(unsigned char hash[32], struct sha256_state *s)
{
unsigned i, pos = (unsigned)s->bytes_lo % 64;
uint32_t *out;
((unsigned char *)s->w)[pos++] = 0x80;
if (pos > 56) {
memset((unsigned char *)s->w + pos, 0, 64-pos);
for (i = 0; i < 16; i++)
s->w[i] = ntohl(s->w[i]);
sha256_transform(s->iv);
pos = 0;
}
memset((unsigned char *)s->w + pos, 0, 56-pos);
for (i = 0; i < 14; i++)
s->w[i] = ntohl(s->w[i]);
s->w[15] = s->bytes_lo << 3;
s->w[14] = s->bytes_hi << 3 | s->bytes_lo >> 29;
sha256_transform(s->iv);
out = (unsigned)hash % sizeof s->iv[0] ? s->w : (uint32_t *)hash;
for (i = 0; i < 8; i++)
out[i] = htonl(s->iv[7-i]);
if (out == s->w)
memcpy(hash, out, sizeof s->iv);
memset(s, 0, sizeof s); /* Good cryptographic hygiene */
}
void
sha256(unsigned char hash[32], const unsigned char *data, size_t len)
{
struct sha256_state s;
sha256_begin(&s);
sha256_hash(data, len, &s);
sha256_end(hash, &s);
}
#endif /* !HAVE_GLADMAN_CODE */
#include <string.h>
#include <sys/time.h>
#define TESTSIZE 100000000
#if TESTSIZE & 64 != 0
#error For now, TESTSIZE must be a multiple of 64.
#endif
int
main(void)
{
uint32_t array1[76] = {
/* Initial values, h..a */
0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667,
/* First 16 w[i] values */
0x61626380, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0x00000018
};
uint32_t array2[76] = {
/* Initial values, h..a */
0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667,
/* First 16 w[i] values */
0x61626364, 0x62636465, 0x63646566, 0x64656667,
0x65666768, 0x66676869, 0x6768696a, 0x68696a6b,
0x696a6b6c, 0x6a6b6c6d, 0x6b6c6d6e, 0x6c6d6e6f,
0x6d6e6f70, 0x6e6f7071, 0x80000000, 0x00000000
};
uint32_t array3[76] = {
/* Initial values, h..a */
0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667
};
unsigned i;
struct timeval start, stop;
sha256_ctx s256;
unsigned char buf[64];
/* The FIPS180-2 appendix B.1 example */
printf("Appendix B.1 example:\n");
sha256_transform(array1);
printf("==>");
for (i = 8; i--; )
printf(" %08x", array1[i]);
putchar('\n');
printf("\nAppendix B.2 example:\n");
sha256_transform(array2);
printf("==>");
for (i = 8; i--; )
printf(" %08x", array2[i]);
putchar('\n');
putchar('\n');
for(i = 8; i < 23; i++)
array2[i] = 0;
array2[23] = 0x000001c0;
sha256_transform(array2);
printf("==>");
for (i = 8; i--; )
printf(" %08x", array2[i]);
putchar('\n');
/* Now to hash 1,000,000 letters 'a' */
printf("\nAppendix B.3 example:\n");
gettimeofday(&start, 0);
for (i = 0; i < TESTSIZE/64; i++) {
memset((char *)(array3+8), 'a', 64);
sha256_transform(array3);
}
array3[8] = 0x80000000;
array3[23] = i*64*8; /* Length in bits */
for (i = 9; i < 23; i++)
array3[i] = 0;
sha256_transform(array3);
gettimeofday(&stop, 0);
stop.tv_sec -= start.tv_sec;
stop.tv_usec -= start.tv_usec;
if (stop.tv_usec < 0) {
stop.tv_usec += 1000000;
stop.tv_sec--;
}
printf("New code: %u.%06ld\n", (unsigned)stop.tv_sec, stop.tv_usec);
printf("==>");
for (i = 8; i--; )
printf(" %08x", array3[i]);
putchar('\n');
sha256_begin(&s256);
gettimeofday(&start, 0);
for (i = 0; i < TESTSIZE/64; i++) {
memset(buf, 'a', 64);
sha256_hash(buf, 64, &s256);
}
sha256_end(buf, &s256);
gettimeofday(&stop, 0);
stop.tv_sec -= start.tv_sec;
stop.tv_usec -= start.tv_usec;
if (stop.tv_usec < 0) {
stop.tv_usec += 1000000;
stop.tv_sec--;
}
printf(
#if HAVE_GLADMAN_CODE
"Gladman code: %u.%06ld\n",
#else
"Wrapper code: %u.%06ld\n",
#endif
(unsigned)stop.tv_sec, stop.tv_usec);
printf("==>");
for (i = 0; i < 32; i++) {
if (i % 4 == 0)
putchar(' ');
printf("%02x", buf[i]);
}
putchar('\n');
return 0;
}
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html