sha3: fix to conform to final SHA3 padding standard, add -a BITS option

function                                             old     new   delta
hash_file                                            331     396     +65
md5_sha1_sum_main                                    485     538     +53
packed_usage                                       30423   30464     +41
sha3_begin                                            17      31     +14
sha3_hash                                            101     110      +9
sha3_end                                              41      49      +8

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>

7 files changed, 143 insertions, 90 deletions

diff --git a/coreutils/Config.src b/coreutils/Config.src
index 619c2efe8..b9dde1209 100644
--- a/coreutils/Config.src
+++ b/coreutils/Config.src
@@ -328,12 +328,6 @@ config FEATURE_LS_COLOR_IS_DEFAULT
 	  configurable, and the output may not be legible on
 	  many output screens.
 
-config MD5SUM
-	bool "md5sum"
-	default y
-	help
-	  md5sum is used to print or check MD5 checksums.
-
 config MKDIR
 	bool "mkdir"
 	default y
@@ -458,30 +452,6 @@ config SEQ
 	help
 	  print a sequence of numbers
 
-config SHA1SUM
-	bool "sha1sum"
-	default y
-	help
-	  Compute and check SHA1 message digest
-
-config SHA256SUM
-	bool "sha256sum"
-	default y
-	help
-	  Compute and check SHA256 message digest
-
-config SHA512SUM
-	bool "sha512sum"
-	default y
-	help
-	  Compute and check SHA512 message digest
-
-config SHA3SUM
-	bool "sha3sum"
-	default y
-	help
-	  Compute and check SHA3 (512-bit) message digest
-
 config SLEEP
 	bool "sleep"
 	default y
@@ -731,17 +701,4 @@ config FEATURE_HUMAN_READABLE
 	help
 	  Allow df, du, and ls to have human readable output.
 
-comment "Common options for md5sum, sha1sum, sha256sum, sha512sum, sha3sum"
-	depends on MD5SUM || SHA1SUM || SHA256SUM || SHA512SUM || SHA3SUM
-
-config FEATURE_MD5_SHA1_SUM_CHECK
-	bool "Enable -c, -s and -w options"
-	default y
-	depends on MD5SUM || SHA1SUM || SHA256SUM || SHA512SUM || SHA3SUM
-	help
-	  Enabling the -c options allows files to be checked
-	  against pre-calculated hash values.
-
-	  -s and -w are useful options when verifying checksums.
-
 endmenu
diff --git a/coreutils/Kbuild.src b/coreutils/Kbuild.src
index 4ec075ac6..5a64fee35 100644
--- a/coreutils/Kbuild.src
+++ b/coreutils/Kbuild.src
@@ -41,7 +41,6 @@ lib-$(CONFIG_LN)        += ln.o
 lib-$(CONFIG_LOGNAME)   += logname.o
 lib-$(CONFIG_LS)        += ls.o
 lib-$(CONFIG_FTPD)      += ls.o
-lib-$(CONFIG_MD5SUM)    += md5_sha1_sum.o
 lib-$(CONFIG_MKDIR)     += mkdir.o
 lib-$(CONFIG_MKFIFO)    += mkfifo.o
 lib-$(CONFIG_MKNOD)     += mknod.o
@@ -58,10 +57,6 @@ lib-$(CONFIG_REALPATH)  += realpath.o
 lib-$(CONFIG_RM)        += rm.o
 lib-$(CONFIG_RMDIR)     += rmdir.o
 lib-$(CONFIG_SEQ)       += seq.o
-lib-$(CONFIG_SHA1SUM)   += md5_sha1_sum.o
-lib-$(CONFIG_SHA256SUM) += md5_sha1_sum.o
-lib-$(CONFIG_SHA512SUM) += md5_sha1_sum.o
-lib-$(CONFIG_SHA3SUM)   += md5_sha1_sum.o
 lib-$(CONFIG_SLEEP)     += sleep.o
 lib-$(CONFIG_SPLIT)     += split.o
 lib-$(CONFIG_SORT)      += sort.o
diff --git a/coreutils/md5_sha1_sum.c b/coreutils/md5_sha1_sum.c
index c0e816ba6..5e017b191 100644
--- a/coreutils/md5_sha1_sum.c
+++ b/coreutils/md5_sha1_sum.c
@@ -5,6 +5,60 @@
  *
  * Licensed under GPLv2 or later, see file LICENSE in this source tree.
  */
+//config:config MD5SUM
+//config:	bool "md5sum"
+//config:	default y
+//config:	help
+//config:	  md5sum is used to print or check MD5 checksums.
+//config:
+//config:config SHA1SUM
+//config:	bool "sha1sum"
+//config:	default y
+//config:	help
+//config:	  Compute and check SHA1 message digest
+//config:
+//config:config SHA256SUM
+//config:	bool "sha256sum"
+//config:	default y
+//config:	help
+//config:	  Compute and check SHA256 message digest
+//config:
+//config:config SHA512SUM
+//config:	bool "sha512sum"
+//config:	default y
+//config:	help
+//config:	  Compute and check SHA512 message digest
+//config:
+//config:config SHA3SUM
+//config:	bool "sha3sum"
+//config:	default y
+//config:	help
+//config:	  Compute and check SHA3 (512-bit) message digest
+//config:
+//config:comment "Common options for md5sum, sha1sum, sha256sum, sha512sum, sha3sum"
+//config:	depends on MD5SUM || SHA1SUM || SHA256SUM || SHA512SUM || SHA3SUM
+//config:
+//config:config FEATURE_MD5_SHA1_SUM_CHECK
+//config:	bool "Enable -c, -s and -w options"
+//config:	default y
+//config:	depends on MD5SUM || SHA1SUM || SHA256SUM || SHA512SUM || SHA3SUM
+//config:	help
+//config:	  Enabling the -c options allows files to be checked
+//config:	  against pre-calculated hash values.
+//config:
+//config:	  -s and -w are useful options when verifying checksums.
+
+//applet:IF_MD5SUM(APPLET_NOEXEC(md5sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, md5sum))
+//applet:IF_SHA1SUM(APPLET_NOEXEC(sha1sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, sha1sum))
+//applet:IF_SHA3SUM(APPLET_NOEXEC(sha3sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, sha3sum))
+//applet:IF_SHA256SUM(APPLET_NOEXEC(sha256sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, sha256sum))
+//applet:IF_SHA512SUM(APPLET_NOEXEC(sha512sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, sha512sum))
+
+//kbuild:lib-$(CONFIG_MD5SUM)    += md5_sha1_sum.o
+//kbuild:lib-$(CONFIG_SHA1SUM)   += md5_sha1_sum.o
+//kbuild:lib-$(CONFIG_SHA256SUM) += md5_sha1_sum.o
+//kbuild:lib-$(CONFIG_SHA512SUM) += md5_sha1_sum.o
+//kbuild:lib-$(CONFIG_SHA3SUM)   += md5_sha1_sum.o
 
 //usage:#define md5sum_trivial_usage
 //usage:	IF_FEATURE_MD5_SHA1_SUM_CHECK("[-c[sw]] ")"[FILE]..."
@@ -57,13 +111,14 @@
 //usage:	)
 //usage:
 //usage:#define sha3sum_trivial_usage
-//usage:	IF_FEATURE_MD5_SHA1_SUM_CHECK("[-c[sw]] ")"[FILE]..."
+//usage:	IF_FEATURE_MD5_SHA1_SUM_CHECK("[-c[sw]] ")"[-a BITS] [FILE]..."
 //usage:#define sha3sum_full_usage "\n\n"
-//usage:       "Print" IF_FEATURE_MD5_SHA1_SUM_CHECK(" or check") " SHA3-512 checksums"
+//usage:       "Print" IF_FEATURE_MD5_SHA1_SUM_CHECK(" or check") " SHA3 checksums"
 //usage:	IF_FEATURE_MD5_SHA1_SUM_CHECK( "\n"
 //usage:     "\n	-c	Check sums against list in FILEs"
 //usage:     "\n	-s	Don't output anything, status code shows success"
 //usage:     "\n	-w	Warn about improperly formatted checksum lines"
+//usage:     "\n	-a BITS	224 (default), 256, 384, 512"
 //usage:	)
 
 //FIXME: GNU coreutils 8.25 has no -s option, it has only these two long opts:
@@ -97,7 +152,10 @@ static unsigned char *hash_bin_to_hex(unsigned char *hash_value,
 	return (unsigned char *)hex_value;
 }
 
-static uint8_t *hash_file(const char *filename)
+#if !ENABLE_SHA3SUM
+# define hash_file(f,w) hash_file(f)
+#endif
+static uint8_t *hash_file(const char *filename, unsigned sha3_width)
 {
 	int src_fd, hash_len, count;
 	union _ctx_ {
@@ -125,27 +183,47 @@ static uint8_t *hash_file(const char *filename)
 		update = (void*)md5_hash;
 		final = (void*)md5_end;
 		hash_len = 16;
-	} else if (ENABLE_SHA1SUM && hash_algo == HASH_SHA1) {
+	}
+	else if (ENABLE_SHA1SUM && hash_algo == HASH_SHA1) {
 		sha1_begin(&context.sha1);
 		update = (void*)sha1_hash;
 		final = (void*)sha1_end;
 		hash_len = 20;
-	} else if (ENABLE_SHA256SUM && hash_algo == HASH_SHA256) {
+	}
+	else if (ENABLE_SHA256SUM && hash_algo == HASH_SHA256) {
 		sha256_begin(&context.sha256);
 		update = (void*)sha256_hash;
 		final = (void*)sha256_end;
 		hash_len = 32;
-	} else if (ENABLE_SHA512SUM && hash_algo == HASH_SHA512) {
+	}
+	else if (ENABLE_SHA512SUM && hash_algo == HASH_SHA512) {
 		sha512_begin(&context.sha512);
 		update = (void*)sha512_hash;
 		final = (void*)sha512_end;
 		hash_len = 64;
-	} else if (ENABLE_SHA3SUM && hash_algo == HASH_SHA3) {
+	}
+#if ENABLE_SHA3SUM
+	else if (ENABLE_SHA3SUM && hash_algo == HASH_SHA3) {
 		sha3_begin(&context.sha3);
 		update = (void*)sha3_hash;
 		final = (void*)sha3_end;
-		hash_len = 64;
-	} else {
+		/*
+		 * Should support 224, 256, 384, 512.
+		 * We allow any value which does not blow the algorithm up.
+		 */
+		if (sha3_width >= 1600/2 /* input block can't be <= 0 */
+		 || sha3_width == 0      /* hash len can't be 0 */
+		 || (sha3_width & 0x1f)  /* should be multiple of 32 */
+		/* (because input uses up to 8 byte wide word XORs. 32/4=8) */
+		) {
+			bb_error_msg_and_die("bad -a%u", sha3_width);
+		}
+		sha3_width /= 4;
+		context.sha3.input_block_bytes = 1600/8 - sha3_width;
+		hash_len = sha3_width/2;
+	}
+#endif
+	else {
 		xfunc_die(); /* can't reach this */
 	}
 
@@ -176,18 +254,30 @@ int md5_sha1_sum_main(int argc UNUSED_PARAM, char **argv)
 {
 	int return_value = EXIT_SUCCESS;
 	unsigned flags;
+#if ENABLE_SHA3SUM
+	unsigned sha3_width = 224;
+#endif
 
 	if (ENABLE_FEATURE_MD5_SHA1_SUM_CHECK) {
 		/* -s and -w require -c */
 		opt_complementary = "s?c:w?c";
 		/* -b "binary", -t "text" are ignored (shaNNNsum compat) */
-		flags = getopt32(argv, "scwbt");
-		argv += optind;
-		//argc -= optind;
+#if ENABLE_SHA3SUM
+		if (applet_name[3] == HASH_SHA3)
+			flags = getopt32(argv, "scwbta:+", &sha3_width);
+		else
+#endif
+			flags = getopt32(argv, "scwbt");
 	} else {
-		argv += 1;
-		//argc -= 1;
+#if ENABLE_SHA3SUM
+		if (applet_name[3] == HASH_SHA3)
+			getopt32(argv, "a:+", &sha3_width);
+		else
+#endif
+			getopt32(argv, "");
 	}
+	argv += optind;
+	//argc -= optind;
 	if (!*argv)
 		*--argv = (char*)"-";
 
@@ -222,7 +312,7 @@ int md5_sha1_sum_main(int argc UNUSED_PARAM, char **argv)
 				*filename_ptr = '\0';
 				filename_ptr += 2;
 
-				hash_value = hash_file(filename_ptr);
+				hash_value = hash_file(filename_ptr, sha3_width);
 
 				if (hash_value && (strcmp((char*)hash_value, line) == 0)) {
 					if (!(flags & FLAG_SILENT))
@@ -251,7 +341,7 @@ int md5_sha1_sum_main(int argc UNUSED_PARAM, char **argv)
 			}
 			fclose_if_not_stdin(pre_computed_stream);
 		} else {
-			uint8_t *hash_value = hash_file(*argv);
+			uint8_t *hash_value = hash_file(*argv, sha3_width);
 			if (hash_value == NULL) {
 				return_value = EXIT_FAILURE;
 			} else {
diff --git a/include/applets.src.h b/include/applets.src.h
index 6e1b02fc3..248d539c4 100644
--- a/include/applets.src.h
+++ b/include/applets.src.h
@@ -205,7 +205,6 @@ IF_MAKEDEVS(APPLET(makedevs, BB_DIR_SBIN, BB_SUID_DROP))
 IF_MAKEMIME(APPLET(makemime, BB_DIR_BIN, BB_SUID_DROP))
 IF_MAN(APPLET(man, BB_DIR_USR_BIN, BB_SUID_DROP))
 IF_MATCHPATHCON(APPLET(matchpathcon, BB_DIR_USR_SBIN, BB_SUID_DROP))
-IF_MD5SUM(APPLET_NOEXEC(md5sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, md5sum))
 IF_MICROCOM(APPLET(microcom, BB_DIR_USR_BIN, BB_SUID_DROP))
 IF_MKDIR(APPLET_NOFORK(mkdir, mkdir, BB_DIR_BIN, BB_SUID_DROP, mkdir))
 IF_MKFS_VFAT(APPLET_ODDNAME(mkdosfs, mkfs_vfat, BB_DIR_SBIN, BB_SUID_DROP, mkfs_vfat))
@@ -280,10 +279,6 @@ IF_SETKEYCODES(APPLET(setkeycodes, BB_DIR_USR_BIN, BB_SUID_DROP))
 IF_SETLOGCONS(APPLET(setlogcons, BB_DIR_USR_SBIN, BB_SUID_DROP))
 IF_SETSEBOOL(APPLET(setsebool, BB_DIR_USR_SBIN, BB_SUID_DROP))
 IF_SETSID(APPLET(setsid, BB_DIR_USR_BIN, BB_SUID_DROP))
-IF_SHA1SUM(APPLET_NOEXEC(sha1sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, sha1sum))
-IF_SHA3SUM(APPLET_NOEXEC(sha3sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, sha3sum))
-IF_SHA256SUM(APPLET_NOEXEC(sha256sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, sha256sum))
-IF_SHA512SUM(APPLET_NOEXEC(sha512sum, md5_sha1_sum, BB_DIR_USR_BIN, BB_SUID_DROP, sha512sum))
 IF_SHOWKEY(APPLET(showkey, BB_DIR_USR_BIN, BB_SUID_DROP))
 IF_SLATTACH(APPLET(slattach, BB_DIR_SBIN, BB_SUID_DROP))
 /* Do not make this applet NOFORK. It breaks ^C-ing of pauses in shells: */
diff --git a/include/libbb.h b/include/libbb.h
index b2e4299dd..bf356d727 100644
--- a/include/libbb.h
+++ b/include/libbb.h
@@ -1737,6 +1737,7 @@ typedef struct sha512_ctx_t {
 typedef struct sha3_ctx_t {
 	uint64_t state[25];
 	unsigned bytes_queued;
+	unsigned input_block_bytes;
 } sha3_ctx_t;
 void md5_begin(md5_ctx_t *ctx) FAST_FUNC;
 void md5_hash(md5_ctx_t *ctx, const void *buffer, size_t len) FAST_FUNC;
diff --git a/libbb/hash_md5_sha.c b/libbb/hash_md5_sha.c
index d08c6b2f7..7e7d8da2f 100644
--- a/libbb/hash_md5_sha.c
+++ b/libbb/hash_md5_sha.c
@@ -941,10 +941,6 @@ void FAST_FUNC sha512_end(sha512_ctx_t *ctx, void *resbuf)
 # define OPTIMIZE_SHA3_FOR_32 1
 #endif
 
-enum {
-	SHA3_IBLK_BYTES = 72, /* 576 bits / 8 */
-};
-
 #if OPTIMIZE_SHA3_FOR_32
 /* This splits every 64-bit word into a pair of 32-bit words,
  * even bits go into first word, odd bits go to second one.
@@ -1352,6 +1348,8 @@ static void sha3_process_block72(uint64_t *state)
 void FAST_FUNC sha3_begin(sha3_ctx_t *ctx)
 {
 	memset(ctx, 0, sizeof(*ctx));
+	/* SHA3-512, user can override */
+	ctx->input_block_bytes = (1600 - 512*2) / 8; /* 72 bytes */
 }
 
 void FAST_FUNC sha3_hash(sha3_ctx_t *ctx, const void *buffer, size_t len)
@@ -1361,7 +1359,7 @@ void FAST_FUNC sha3_hash(sha3_ctx_t *ctx, const void *buffer, size_t len)
 	unsigned bufpos = ctx->bytes_queued;
 
 	while (1) {
-		unsigned remaining = SHA3_IBLK_BYTES - bufpos;
+		unsigned remaining = ctx->input_block_bytes - bufpos;
 		if (remaining > len)
 			remaining = len;
 		len -= remaining;
@@ -1373,38 +1371,41 @@ void FAST_FUNC sha3_hash(sha3_ctx_t *ctx, const void *buffer, size_t len)
 			remaining--;
 		}
 		/* Clever way to do "if (bufpos != N) break; ... ; bufpos = 0;" */
-		bufpos -= SHA3_IBLK_BYTES;
+		bufpos -= ctx->input_block_bytes;
 		if (bufpos != 0)
 			break;
 		/* Buffer is filled up, process it */
 		sha3_process_block72(ctx->state);
 		/*bufpos = 0; - already is */
 	}
-	ctx->bytes_queued = bufpos + SHA3_IBLK_BYTES;
+	ctx->bytes_queued = bufpos + ctx->input_block_bytes;
 #else
 	/* +50 bytes code size, but a bit faster because of long-sized XORs */
 	const uint8_t *data = buffer;
 	unsigned bufpos = ctx->bytes_queued;
+	unsigned iblk_bytes = ctx->input_block_bytes;
 
 	/* If already data in queue, continue queuing first */
-	while (len != 0 && bufpos != 0) {
-		uint8_t *buf = (uint8_t*)ctx->state;
-		buf[bufpos] ^= *data++;
-		len--;
-		bufpos++;
-		if (bufpos == SHA3_IBLK_BYTES) {
-			bufpos = 0;
-			goto do_block;
+	if (bufpos != 0) {
+		while (len != 0) {
+			uint8_t *buf = (uint8_t*)ctx->state;
+			buf[bufpos] ^= *data++;
+			len--;
+			bufpos++;
+			if (bufpos == iblk_bytes) {
+				bufpos = 0;
+				goto do_block;
+			}
 		}
 	}
 
 	/* Absorb complete blocks */
-	while (len >= SHA3_IBLK_BYTES) {
+	while (len >= iblk_bytes) {
 		/* XOR data onto beginning of state[].
 		 * We try to be efficient - operate one word at a time, not byte.
 		 * Careful wrt unaligned access: can't just use "*(long*)data"!
 		 */
-		unsigned count = SHA3_IBLK_BYTES / sizeof(long);
+		unsigned count = iblk_bytes / sizeof(long);
 		long *buf = (long*)ctx->state;
 		do {
 			long v;
@@ -1412,7 +1413,7 @@ void FAST_FUNC sha3_hash(sha3_ctx_t *ctx, const void *buffer, size_t len)
 			*buf++ ^= v;
 			data += sizeof(long);
 		} while (--count);
-		len -= SHA3_IBLK_BYTES;
+		len -= iblk_bytes;
  do_block:
 		sha3_process_block72(ctx->state);
 	}
@@ -1433,8 +1434,22 @@ void FAST_FUNC sha3_end(sha3_ctx_t *ctx, void *resbuf)
 {
 	/* Padding */
 	uint8_t *buf = (uint8_t*)ctx->state;
-	buf[ctx->bytes_queued]   ^= 1;
-	buf[SHA3_IBLK_BYTES - 1] ^= 0x80;
+	/*
+	 * Keccak block padding is: add 1 bit after last bit of input,
+	 * then add zero bits until the end of block, and add the last 1 bit
+	 * (the last bit in the block) - the "10*1" pattern.
+	 * SHA3 standard appends additional two bits, 01,  before that padding:
+	 *
+	 * SHA3-224(M) = KECCAK[448](M||01, 224)
+	 * SHA3-256(M) = KECCAK[512](M||01, 256)
+	 * SHA3-384(M) = KECCAK[768](M||01, 384)
+	 * SHA3-512(M) = KECCAK[1024](M||01, 512)
+	 * (M is the input, || is bit concatenation)
+	 *
+	 * The 6 below contains 01 "SHA3" bits and the first 1 "Keccak" bit:
+	 */
+	buf[ctx->bytes_queued]          ^= 6; /* bit pattern 00000110 */
+	buf[ctx->input_block_bytes - 1] ^= 0x80;
 
 	sha3_process_block72(ctx->state);
 
diff --git a/testsuite/sha3sum.tests b/testsuite/sha3sum.tests
index 82fada633..2cd8e3bf2 100755
--- a/testsuite/sha3sum.tests
+++ b/testsuite/sha3sum.tests
@@ -1,3 +1,3 @@
 #!/bin/sh
 
-. ./md5sum.tests sha3sum c29d77bc548fa2b20a04c861400a5360879c52156e2a54a3415b99a9a3123e1d5f36714a24eca8c1f05a8e2d8ba859c930d41141f64a255c6794436fc99c486a
+. ./md5sum.tests sha3sum 11659f09370139f8ef384f4a6260947fafa6e4fcd87a1ef3f35410e9