Re: [PATCH v0] Add SHA-3 hash algorithm
On 10/03/2012 01:45 AM, Jeff Garzik wrote: Whee -- SHA-3 is out! I wanted to explore the new toy a bit, and so, here is a blatantly untested rough draft of SHA-3 kernel support. Why rough draft? Because answers to the questions below will inform a more polished version. Just to update people... this has been in a holding pattern, because apparently there are revisions to SHA-3 coming down the pipe. They want to address preimage resistance, and make things faster in hardware. Random quote from NIST, on the NIST hash-forum, which doesn't provide detail but does summarize general feeling: As best we can tell, continuing to pay that performance penalty for all future uses of SHA3 has no benefit. (All this is a longwinded way of saying: we were wrong, but hopefully we got better.) Jeff -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH v0] Add SHA-3 hash algorithm
Whee -- SHA-3 is out! I wanted to explore the new toy a bit, and
so, here is a blatantly untested rough draft of SHA-3 kernel support.
Why rough draft? Because answers to the questions below will inform a
more polished version.
Code notes and questions:
1) tcrypt setup blatantly wrong. What is the best setup here? Define a
separate entry for each digest length? Is there some special string
descriptor format that is desired, like sha3-256 or sha3(256)?
2) Digest and block size are easily variable, as shown below...
do we want hand-craft individual versions for each -- sha3_256.c,
sha3_512.c, etc.?
3) Is it even feasible for struct shash_alg to have a dynamic (filled in
at context init time, not driver registration time) digestsize and
cra_blocksize? That would permit a single shash_alg for all sha3.
4) Original implementation from readable_keccak.tgz (link below). The
official sources have a bazillion different flavors for various
architectures and bit sizes, and the code is not pretty. I wanted to
start small and readable, and _then_ branch out into x86[-64]-specific
versions, etc. as users and use cases appear.
Commit e52113b7b4ace50ab586b426098c6d69d75c263a
Branch sha3
Repo git://git.kernel.org/pub/scm/linux/kernel/git/jgarzik/linux.git
References:
http://keccak.noekeon.org/
http://www.mjos.fi/dist/readable_keccak.tgz
http://www.nist.gov/itl/csd/sha-100212.cfm
Not-signed-off-by: Jeff Garzik jgar...@redhat.com
crypto/Kconfig|6 +
crypto/Makefile |1
crypto/sha3_generic.c | 280 ++
crypto/tcrypt.c | 14 ++
include/crypto/sha3.h | 26
5 files changed, 326 insertions(+), 1 deletion(-)
diff --git a/crypto/Kconfig b/crypto/Kconfig
index a323805..97f5e75 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -457,6 +457,12 @@ config CRYPTO_SHA512
This code also includes SHA-384, a 384 bit hash with 192 bits
of security against collision attacks.
+config CRYPTO_SHA3
+ tristate SHA3 digest algorithm
+ select CRYPTO_HASH
+ help
+ SHA-3 secure hash standard.
+
config CRYPTO_TGR192
tristate Tiger digest algorithms
select CRYPTO_HASH
diff --git a/crypto/Makefile b/crypto/Makefile
index 30f33d6..65150d1 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -45,6 +45,7 @@ obj-$(CONFIG_CRYPTO_RMD320) += rmd320.o
obj-$(CONFIG_CRYPTO_SHA1) += sha1_generic.o
obj-$(CONFIG_CRYPTO_SHA256) += sha256_generic.o
obj-$(CONFIG_CRYPTO_SHA512) += sha512_generic.o
+obj-$(CONFIG_CRYPTO_SHA3) += sha3_generic.o
obj-$(CONFIG_CRYPTO_WP512) += wp512.o
obj-$(CONFIG_CRYPTO_TGR192) += tgr192.o
obj-$(CONFIG_CRYPTO_GF128MUL) += gf128mul.o
diff --git a/crypto/sha3_generic.c b/crypto/sha3_generic.c
new file mode 100644
index 000..9255ea1
--- /dev/null
+++ b/crypto/sha3_generic.c
@@ -0,0 +1,280 @@
+
+#include crypto/internal/hash.h
+#include linux/init.h
+#include linux/module.h
+#include linux/types.h
+#include crypto/sha3.h
+#include asm/byteorder.h
+
+#define KECCAK_ROUNDS 24
+
+#define ROTL64(x, y) (((x) (y)) | ((x) (64 - (y
+
+static const u64 keccakf_rndc[24] =
+{
+ 0x0001, 0x8082, 0x8000808a,
+ 0x800080008000, 0x808b, 0x8001,
+ 0x800080008081, 0x80008009, 0x008a,
+ 0x0088, 0x80008009, 0x800a,
+ 0x8000808b, 0x808b, 0x80008089,
+ 0x80008003, 0x80008002, 0x8080,
+ 0x800a, 0x8000800a, 0x800080008081,
+ 0x80008080, 0x8001, 0x800080008008
+};
+
+static const int keccakf_rotc[24] =
+{
+ 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2, 14,
+ 27, 41, 56, 8, 25, 43, 62, 18, 39, 61, 20, 44
+};
+
+static const int keccakf_piln[24] =
+{
+ 10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24, 4,
+ 15, 23, 19, 13, 12, 2, 20, 14, 22, 9, 6, 1
+};
+
+// update the state with given number of rounds
+
+static void keccakf(u64 st[25], int rounds)
+{
+ int i, j, round;
+ u64 t, bc[5];
+
+ for (round = 0; round rounds; round++) {
+
+ // Theta
+ for (i = 0; i 5; i++)
+ bc[i] = st[i] ^ st[i + 5] ^ st[i + 10] ^ st[i + 15] ^
st[i + 20];
+
+ for (i = 0; i 5; i++) {
+ t = bc[(i + 4) % 5] ^ ROTL64(bc[(i + 1) % 5], 1);
+ for (j = 0; j 25; j += 5)
+ st[j + i] ^= t;
+ }
+
+ // Rho Pi
+ t = st[1];
+ for (i = 0; i 24; i++) {
+ j = keccakf_piln[i];
+ bc[0] = st[j];
+ st[j] = ROTL64(t, keccakf_rotc[i]);
+ t = bc[0];
+ }
+
+ // Chi
+ for (j = 0
Re: [PATCH v0] Add SHA-3 hash algorithm
On 10/03/2012 02:06 AM, David Miller wrote: From: Jeff Garzik j...@garzik.org Date: Wed, 3 Oct 2012 01:45:42 -0400 1) tcrypt setup blatantly wrong. What is the best setup here? Define a separate entry for each digest length? Is there some special string descriptor format that is desired, like sha3-256 or sha3(256)? Good question. The base name should probably be something without dashes. Maybe sha3_256, but yeah sha3256 would look rediculous. Well, the more basic question was... what to do when the digest length is easily variable, vis a vis kernel hash APIs? Keccak message digest size may fall anywhere within the range 8 bits - 1600 bits at runtime. You choose the digest size when you init the context. In contrast, the kernel interface appears to require a hardcoded size, chosen at driver compile time. My patch picks sizes found in common use, consistent with existing kernel practice. However, it is valid for another Keccak user to produce a 1600 bit hash, or a 1592 bit hash, or a 1584 bit hash, etc., etc. Maybe my patch is the best we can do in the current kernel, if dynamic digest size is not currently possible. Register sha3_224, sha3_256, ... as you describe, and wait for actual users to appear with unsupported digest sizes. Jeff -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v0] Add SHA-3 hash algorithm
On 10/03/2012 03:11 AM, Herbert Xu wrote: On Wed, Oct 03, 2012 at 02:53:27AM -0400, Jeff Garzik wrote: Maybe my patch is the best we can do in the current kernel, if dynamic digest size is not currently possible. Register sha3_224, sha3_256, ... as you describe, and wait for actual users to appear with unsupported digest sizes. Let's see what people use before we do anything more fancy. If the variants really start proliferating, we can add a template called trunc and then have things like trunc(sha3,224), etc. If they start proliferating, you really just want a single sha3(n), one single shash_alg registered at driver init time. Jeff -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[CRYPTO] skein hash updated
I've been quietly maintaining a Linux kernel implementation of the 'skein' hash algorithm, which is one of the proposed SHA-3 algorithms. First posted around two years ago: http://www.mail-archive.com/linux-crypto@vger.kernel.org/msg02373.html Skein is currently at version 1.3, and as slashdot readers are aware, skein is one of the finalists for SHA-3. The git URL remains unchanged: branch skein of git://git.kernel.org/pub/scm/linux/kernel/git/jgarzik/misc-2.6.git Thanks to Tobias Karnat for recent updates, including conversion to shash. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH] crypto: Add Skein hash algorithm variants
This is the first draft of the Skein hash algorithm that was recently
mentioned, as a prominent submission to NIST's SHA-3 competition.
Website:http://www.schneier.com/skein.html
It still needs more work, linux-ifying, testing, and reviewing.
One note I forgot to mention in the commit itself, but should be
considered when reviewing this:
Skein permits the output digest size to be specified by the user.
Skein-256 means 256 bits of internal state, NOT 256 bits of output
digest. The output digest size is specified to Skein at init time.
In my implementation below, I attempted to follow the Principle of Least
Surprise, by hardcoding output digest size == internal state size.
Thus, in my implementation, skein256 really does mean 256 output bits.
I am currently pushing this work to the 'skein' branch of
git://git.kernel.org/pub/scm/linux/kernel/git/jgarzik/misc-2.6.git skein
Comments welcome!
---
crypto/Kconfig | 12 +
crypto/Makefile|3 +
crypto/skein.h | 265 ++
crypto/skein1024_generic.c | 518
crypto/skein256_generic.c | 367 +++
crypto/skein512_generic.c | 417 +++
6 files changed, 1582 insertions(+), 0 deletions(-)
create mode 100644 crypto/skein.h
create mode 100644 crypto/skein1024_generic.c
create mode 100644 crypto/skein256_generic.c
create mode 100644 crypto/skein512_generic.c
Jeff Garzik (1):
[CRYPTO] Add Skein hash algorithm, 256-, 512-, and 1024-bit variants
Import the public domain reference implementation of the Skein hash
algorithm into the Linux Crypto API. This is a prominent submission
to the NIST's competition for SHA-3.
See Skein website for more info: http://www.schneier.com/skein.html
This is just a rough import, and still needs more cleaning and Linux-ifying.
Signed-off-by: Jeff Garzik [EMAIL PROTECTED]
diff --git a/crypto/Kconfig b/crypto/Kconfig
index 39dbd8e..f18868f 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -352,6 +352,18 @@ config CRYPTO_SHA512
This code also includes SHA-384, a 384 bit hash with 192 bits
of security against collision attacks.
+config CRYPTO_SKEIN256
+ tristate Skein-256(256) digest algorithm
+ select CRYPTO_ALGAPI
+
+config CRYPTO_SKEIN512
+ tristate Skein-512(512) digest algorithm
+ select CRYPTO_ALGAPI
+
+config CRYPTO_SKEIN1024
+ tristate Skein-1024(1024) digest algorithm
+ select CRYPTO_ALGAPI
+
config CRYPTO_TGR192
tristate Tiger digest algorithms
select CRYPTO_ALGAPI
diff --git a/crypto/Makefile b/crypto/Makefile
index 5862b80..10c3ca8 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -39,6 +39,9 @@ obj-$(CONFIG_CRYPTO_RMD320) += rmd320.o
obj-$(CONFIG_CRYPTO_SHA1) += sha1_generic.o
obj-$(CONFIG_CRYPTO_SHA256) += sha256_generic.o
obj-$(CONFIG_CRYPTO_SHA512) += sha512_generic.o
+obj-$(CONFIG_CRYPTO_SKEIN256) += skein256_generic.o
+obj-$(CONFIG_CRYPTO_SKEIN512) += skein512_generic.o
+obj-$(CONFIG_CRYPTO_SKEIN1024) += skein1024_generic.o
obj-$(CONFIG_CRYPTO_WP512) += wp512.o
obj-$(CONFIG_CRYPTO_TGR192) += tgr192.o
obj-$(CONFIG_CRYPTO_GF128MUL) += gf128mul.o
diff --git a/crypto/skein.h b/crypto/skein.h
new file mode 100644
index 000..2753b55
--- /dev/null
+++ b/crypto/skein.h
@@ -0,0 +1,265 @@
+#ifndef _SKEIN_H_
+#define _SKEIN_H_ 1
+/**
+**
+** Interface declarations and internal definitions for Skein hashing.
+**
+** Source code author: Doug Whiting, 2008.
+**
+** This algorithm and source code is released to the public domain.
+**
+***
+**
+** The following compile-time switches may be defined to control some
+** tradeoffs between speed, code size, error checking, and security.
+**
+** The default note explains what happens when the switch is not defined.
+**
+** SKEIN_DEBUG-- make callouts from inside Skein code
+**to examine/display intermediate values.
+**[default: no callouts (no overhead)]
+**
+** SKEIN_ERR_CHECK-- how error checking is handled inside Skein
+**code. If not defined, most error checking
+**is disabled (for performance). Otherwise,
+**the switch value is interpreted as:
+**0: use assert() to flag errors
+**1: return SKEIN_FAIL to flag errors
+**
+***/
+
+#include linux/types.h
+
+enum {
+ SKEIN_SUCCESS = 0, /* return codes from Skein calls */
+ SKEIN_FAIL = 1,
+ SKEIN_BAD_HASHLEN = 2
+};
+
+#define SKEIN_MODIFIER_WORDS ( 2)/* number
Re: [PATCH] crypto: add test vectors for skein256/512/1024
Sebastian Andrzej Siewior wrote: I grabed them from http://www.schneier.com/skein.html. The last test vector (3) in every category is currently deactivated because it failed always. It is unlikely that I made a type because I copy+pasted the tables + vim magiced them. So maybe code may missbehave on requests lengths which are not a multiple of 4 or the vectors can not be used due to some other limitations that I've overseen. Another thought: did you verify that the test vectors' output sizes matched the Linux kernel's? My implementation assumed a 256-bit output size for Skein-256, for example, but it is quite possible that Schneier and co. ran tests where the output size differed from the internal state size. Jeff -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 2/3] [CRYPTO] Add optimized SHA-1 implementation for i486+
Matt Mackall wrote: On Fri, Jun 08, 2007 at 05:42:53PM -0400, Benjamin Gilbert wrote: Add x86-optimized implementation of the SHA-1 hash function, taken from Nettle under the LGPL. This code will be enabled on kernels compiled for 486es or better; kernels which support 386es will use the generic implementation (since we need BSWAP). We disable building lib/sha1.o when an optimized implementation is available, as the library link order for x86 (and x86_64) would otherwise ignore the optimized version. The existing optimized implementation for ARM does not do this; the library link order for that architecture appears to favor the arch/arm/ version automatically. I've left this situation alone since I'm not familiar with the ARM code, but a !ARM condition could be added to CONFIG_SHA1_GENERIC if it makes sense. The code has been tested with tcrypt and the NIST test vectors. Have you benchmarked this against lib/sha1.c? Please post the results. Until then, I'm frankly skeptical that your unrolled version is faster because when I introduced lib/sha1.c the rolled version therein won by a significant margin and had 1/10th the cache footprint. Yes. And it also depends on the CPU as well. Testing on a server-class x86 CPU (often with bigger L2, and perhaps even L1, cache) will produce different result than from popular but less-capable value CPUs. Jeff - To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
