{"thread":{"id":"28768","subject":"[PATCH] replace sha1 with another algorithm","startedAt":"2011-10-26T00:12:37Z","lastAt":"2011-10-27T00:01:17Z","messageCount":4,"participants":["Jeff King","Michael J Gruber","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"178302","messageId":"20111026001237.GA22195@sigill.intra.peff.net","threadId":"28768","inReplyTo":null,"subject":"[PATCH] replace sha1 with another algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-26T00:12:37Z","receivedAt":"2011-10-26T00:12:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"SHA-1 is due to be cryptographically broken sometime in the\nnext decade, with collision attacks becoming possible. But\nwe don't have to wait! We can act now and replace it,\ntreating us to all of the pain of a flag day without any\ndelay!\n\nWe could of course use the SHA-2 family, or wait for the\nupcoming SHA-3. But any good cryptographer knows that you\nshould _never_ use a standard algorithm. It's always better\nto roll your own. After all, if _you_ can't break it, how\ncould anyone else?\n\nSigned-off-by: Jeff King \nReviewed-by: Brandon Casey \nMocked-by: Rick Balocca \nEnjoyed-by: Elijah Newren \n---\n block-sha1/sha1.h | 2 +-\n cache.h | 4 +++-\n sha1_file.c | 32 ++++++++++++++++++++++++++++++++\n 3 files changed, 36 insertions(+), 2 deletions(-)\n\ndiff --git a/block-sha1/sha1.h b/block-sha1/sha1.h\nindex b864df6..49331e3 100644\n--- a/block-sha1/sha1.h\n+++ b/block-sha1/sha1.h\n@@ -19,4 +19,4 @@\n #define git_SHA_CTX\tblk_SHA_CTX\n #define git_SHA1_Init\tblk_SHA1_Init\n #define git_SHA1_Update\tblk_SHA1_Update\n-#define git_SHA1_Final\tblk_SHA1_Final\n+#define real_git_SHA1_Final\tblk_SHA1_Final\ndiff --git a/cache.h b/cache.h\nindex 2e6ad36..068062b 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -13,9 +13,11 @@\n #define git_SHA_CTX\tSHA_CTX\n #define git_SHA1_Init\tSHA1_Init\n #define git_SHA1_Update\tSHA1_Update\n-#define git_SHA1_Final\tSHA1_Final\n+#define real_git_SHA1_Final\tSHA1_Final\n #endif\n \n+void git_SHA1_Final(unsigned char out[20], git_SHA_CTX *ctx);\n+\n #include \n typedef struct git_zstream {\n \tz_stream z;\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 27f3b9b..23e0107 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2833,3 +2833,35 @@ void assert_sha1_type(const unsigned char *sha1, enum object_type expect)\n \t\tdie(\"%s is not a valid '%s' object\", sha1_to_hex(sha1),\n \t\t typename(expect));\n }\n+\n+static void xor_bytes(unsigned char *out, unsigned char *a, unsigned char *b,\n+\t\t unsigned n)\n+{\n+\tunsigned i;\n+\tfor (i = 0; i < n; i++)\n+\t\tout[i] = a[i] ^ b[i];\n+}\n+\n+static void mix_hash(unsigned char *h, unsigned n)\n+{\n+\tunsigned char out[20];\n+\tunsigned mid = n / 2;\n+\n+\tif (2*mid < n)\n+\t\treturn;\n+\n+\txor_bytes(out, h, h + mid, mid);\n+\txor_bytes(out + mid, h + mid, h, mid);\n+\tmemcpy(h, out, n);\n+\n+\t/* If a little bit of mixing is good, then a lot must be GREAT! */\n+\tmix_hash(h, mid);\n+\tmix_hash(h + mid, mid);\n+}\n+\n+void git_SHA1_Final(unsigned char out[20], git_SHA_CTX *ctx)\n+{\n+\t/* We build on top of the regular SHA1, but then \"enhance\" it. */\n+\treal_git_SHA1_Final(out, ctx);\n+\tmix_hash(out, 20);\n+}\n-- \n1.7.7.troll\n"},{"id":"178313","messageId":"4EA7D9FA.6070505@drmicha.warpmail.net","threadId":"28768","inReplyTo":"20111026001237.GA22195@sigill.intra.peff.net","subject":"Re: [PATCH] replace sha1 with another algorithm","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2011-10-26T09:59:22Z","receivedAt":"2011-10-26T09:59:22Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Jeff King venit, vidit, dixit 26.10.2011 02:12:\n> SHA-1 is due to be cryptographically broken sometime in the\n> next decade, with collision attacks becoming possible. But\n> we don't have to wait! We can act now and replace it,\n> treating us to all of the pain of a flag day without any\n> delay!\n> \n> We could of course use the SHA-2 family, or wait for the\n> upcoming SHA-3. But any good cryptographer knows that you\n> should _never_ use a standard algorithm. It's always better\n> to roll your own. After all, if _you_ can't break it, how\n> could anyone else?\n> \n> Signed-off-by: Jeff King \n> Reviewed-by: Brandon Casey \n> Mocked-by: Rick Balocca \n> Enjoyed-by: Elijah Newren \nAwaited-by: Michael J Gruber \n\nStill remembering an earlier GitTogether's l33t l10n....\n> ---\n> block-sha1/sha1.h | 2 +-\n> cache.h | 4 +++-\n> sha1_file.c | 32 ++++++++++++++++++++++++++++++++\n> 3 files changed, 36 insertions(+), 2 deletions(-)\n> \n> diff --git a/block-sha1/sha1.h b/block-sha1/sha1.h\n> index b864df6..49331e3 100644\n> --- a/block-sha1/sha1.h\n> +++ b/block-sha1/sha1.h\n> @@ -19,4 +19,4 @@\n> #define git_SHA_CTX\tblk_SHA_CTX\n> #define git_SHA1_Init\tblk_SHA1_Init\n> #define git_SHA1_Update\tblk_SHA1_Update\n> -#define git_SHA1_Final\tblk_SHA1_Final\n> +#define real_git_SHA1_Final\tblk_SHA1_Final\n> diff --git a/cache.h b/cache.h\n> index 2e6ad36..068062b 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -13,9 +13,11 @@\n> #define git_SHA_CTX\tSHA_CTX\n> #define git_SHA1_Init\tSHA1_Init\n> #define git_SHA1_Update\tSHA1_Update\n> -#define git_SHA1_Final\tSHA1_Final\n> +#define real_git_SHA1_Final\tSHA1_Final\n> #endif\n> \n> +void git_SHA1_Final(unsigned char out[20], git_SHA_CTX *ctx);\n> +\n> #include \n> typedef struct git_zstream {\n> \tz_stream z;\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 27f3b9b..23e0107 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -2833,3 +2833,35 @@ void assert_sha1_type(const unsigned char *sha1, enum object_type expect)\n> \t\tdie(\"%s is not a valid '%s' object\", sha1_to_hex(sha1),\n> \t\t typename(expect));\n> }\n> +\n> +static void xor_bytes(unsigned char *out, unsigned char *a, unsigned char *b,\n> +\t\t unsigned n)\n> +{\n> +\tunsigned i;\n> +\tfor (i = 0; i < n; i++)\n> +\t\tout[i] = a[i] ^ b[i];\n> +}\n> +\n> +static void mix_hash(unsigned char *h, unsigned n)\n> +{\n> +\tunsigned char out[20];\n\nunsigned char out[n];\n\n;)\n\n> +\tunsigned mid = n / 2;\n> +\n> +\tif (2*mid < n)\n> +\t\treturn;\n> +\n> +\txor_bytes(out, h, h + mid, mid);\n> +\txor_bytes(out + mid, h + mid, h, mid);\n> +\tmemcpy(h, out, n);\n> +\n> +\t/* If a little bit of mixing is good, then a lot must be GREAT! */\n> +\tmix_hash(h, mid);\n> +\tmix_hash(h + mid, mid);\n\nn a power of 2 anyone...\n\n> +}\n> +\n> +void git_SHA1_Final(unsigned char out[20], git_SHA_CTX *ctx)\n> +{\n> +\t/* We build on top of the regular SHA1, but then \"enhance\" it. */\n> +\treal_git_SHA1_Final(out, ctx);\n> +\tmix_hash(out, 20);\n> +}\n>--\n>1.7.7.troll\n\n;)\n"},{"id":"178332","messageId":"7vaa8n35dc.fsf@alter.siamese.dyndns.org","threadId":"28768","inReplyTo":"20111026001237.GA22195@sigill.intra.peff.net","subject":"Re: [PATCH] replace sha1 with another algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-10-26T19:44:15Z","receivedAt":"2011-10-26T19:44:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> +static void xor_bytes(unsigned char *out, unsigned char *a, unsigned char *b,\n> +\t\t unsigned n)\n> +{\n> +\tunsigned i;\n> +\tfor (i = 0; i < n; i++)\n> +\t\tout[i] = a[i] ^ b[i];\n> +}\n> +\n> +static void mix_hash(unsigned char *h, unsigned n)\n> +{\n> +\tunsigned char out[20];\n> +\tunsigned mid = n / 2;\n> +\n> +\tif (2*mid < n)\n> +\t\treturn;\n> +\n> +\txor_bytes(out, h, h + mid, mid);\n> +\txor_bytes(out + mid, h + mid, h, mid);\n> +\tmemcpy(h, out, n);\n> +\n> +\t/* If a little bit of mixing is good, then a lot must be GREAT! */\n> +\tmix_hash(h, mid);\n> +\tmix_hash(h + mid, mid);\n> +}\n\nYou seem to want to reduce the hash down to 5-bytes by duplicating the\nsame value on the left and right half, and duplicate that four times to\nfill 20-byte buffer, but doesn't this look unnecessarily inefficient way\nto achieve that?\n"},{"id":"178339","messageId":"20111027000117.GA24161@sigill.intra.peff.net","threadId":"28768","inReplyTo":"7vaa8n35dc.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] replace sha1 with another algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-27T00:01:17Z","receivedAt":"2011-10-27T00:01:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 26, 2011 at 12:44:15PM -0700, Junio C Hamano wrote:\n\n> > +static void mix_hash(unsigned char *h, unsigned n)\n> > +{\n> > +\tunsigned char out[20];\n> > +\tunsigned mid = n / 2;\n> > +\n> > +\tif (2*mid < n)\n> > +\t\treturn;\n> > +\n> > +\txor_bytes(out, h, h + mid, mid);\n> > +\txor_bytes(out + mid, h + mid, h, mid);\n> > +\tmemcpy(h, out, n);\n> > +\n> > +\t/* If a little bit of mixing is good, then a lot must be GREAT! */\n> > +\tmix_hash(h, mid);\n> > +\tmix_hash(h + mid, mid);\n> > +}\n> \n> You seem to want to reduce the hash down to 5-bytes by duplicating the\n> same value on the left and right half, and duplicate that four times to\n> fill 20-byte buffer, but doesn't this look unnecessarily inefficient way\n> to achieve that?\n\nWell, yeah. But when you're writing a really bad hashing algorithm, I\nfeel like obfuscating the bugs is key.\n\n-Peff\n"}]}