I produced a Keccak implementation in May 2019, through about one week of intensive study and hacking. It builds on some techniques and routines I'd been developing for small, self-contained C programs on Unix, whereby the standard I/O library is thrown out in favor of a minimalistic interface fitting the needs of the program, requiring for portability only the system call wrappers, which generally have direct translations to assembly language. The approach ensures that system errors are detected without requiring effort by calling code and leaves no uncertainty regarding signal behavior, flushing of buffers or integer overflow. The resulting binary here (musl/amd64, static, unstripped) weighs in at 19K and contains not so much as a "malloc".
Regarding the permutation and sponge construction themselves, I found the Keccak reference quite comprehensible; the only topics I needed to brush up on were Linear Feedback Shift Registers and the polynomial algebra used to describe them.
Having previously written what ended up as possibly the world's slowest hash functions in an interpreted language, I was itching to make something fast for once: not pouring vast efforts into optimization but at least avoiding obvious slowdowns. I wish I could say I got it all right on the first try, or that I identified all mistakes through careful re-reading, but not quite:
jfw: well my keccak proggy hashes; now to look for some test vectors
jfw: sure enough I botched it:
jfw: mathematically, (x-1) mod y is equivalent to (x+y-1) mod y
jfw: (pretty much the definition of mod...)
jfw: but if x is an unsigned type -- which I made it, because it's used as an array index and those better be nonnegative -- the subtraction wraps *mod 2*
jfw: er, mod power-of-two
jfw: the arrays in question are indexed mod 5, which being coprime to any power of 2, gives a decidedly different result from if x were a signed or mathematical integer.
jfw: (in another part of the code I had in fact anticipated this.)
The arithmetic in question sure looked correct on the surface, so I tracked this down by adding fine-grained test probes to compare each step of the permutation against provided data.(i) Further contemplation lead me to see that the mod-5 operations were entirely invariant in the permutation's input and thus amenable to a lookup table without introducing a timing side-channel.
I did a full re-read a month after writing; the only mistake found was a comment with off-by-one range description.
Capacity and output length parameters are user-selectable; I chose a default of 512 bits for both, as explained in the code:
Sponge capacity is an upper bound on security level because the permutation is readily inverted if its full output is known. Beyond that, its relationship to actual security is not clear to me (or perhaps anyone); some margin of safety seems prudent. In the FIPS202 parameters, capacity under 512 is seen only in "SHAKE128" and none of the "SHA3" fixed-width hashes. The EuCrypt default is 256 (bitrate 1344); I have not found a discussion of this choice.
I should have piped up and asked about this at the time; though I was still a WoT non-entity living in the shadows, it happens that blog comments are one of the easier ways to get started in the grand conversation, and certainly if you have something interesting to say or ask.
The past being what it is, I will ask now: do any mathematical minds in the readership have input on what constitutes a "good" choice of capacity and why? If as I'd been thinking it's more than 256 to be at least as secure as SHA3, it would seem to suggest a need to regrind the existing Keccak vpatches or otherwise deal with a multiplicity of standards.
A compiler with 64-bit integer support is required; there is no dependence on machine byte order. The little-endian convention is used for interpreting bytes as the bit strings the permutation is defined on. I believe the code to be timing-invariant with respect to potentially secret bits, with the exception of output hex encoding. This would be good to fix. The other main deficiency I see is lack of a working "-c" option to verify provided hashes.
Finally, some basic performance numbers, from a modest Core 2 @2.26GHz, 3072K cache:
$ dd if=/dev/zero bs=1048576 count=100 | keksum 100+0 records in 100+0 records out 104857600 bytes (100.0MB) copied, 2.656227 seconds, 37.6MB/s 7a37879dcc634482775f4c1ebf294a0a02c9bcf924222cf6d2fe1c6beca3574debfe73f9034b868deefd7bbad4f5c251333bc3c735f1a82de045c7980814a2c2 $ dd if=/dev/urandom bs=1048576 count=100 > rand $ dd if=rand bs=1048576 count=100 | keksum 100+0 records in 100+0 records out 104857600 bytes (100.0MB) copied, 2.648968 seconds, 37.8MB/s ec4eab1cff9198e1ef23d663cc9da505eaeda713168bf31ed7807ec63fb1ddfa3454aea212fab193b071ad98e2cc47b5d004a4d1737d23ae8804978995ae1b7a
Download vpatches
genesis (seals: jfw)keksum_genesis (seals: jfw) - redone to include project name as prefix in patch name and change default capacity to 256.- keksum_genesis_3 (seals: jfw diana_coman) - redone to include project name as prefix in patch name, change default capacity to 256, update self-test invocation including fixing on BSD-likes, and avoid false success in Makefile.
- The spiffy modular types in Ada would have prevented this mistake entirely, though not without some cost either in runtime performance or compiler complexity (and thus potential bugs...), I would imagine. [^]
Builds, runs, and matches output of Diana's classic Keccaktron (when set to -s256.)
Comment by Stanislav Datskovskiy — 2019-12-04 @ 17:56
[...] Bitcoin project presently rests on some shaky foundations. Despite apparently intricate efforts, a Keccak based vtree has seen little progress, in that the original patch signers besides mod6 have not [...]
Pingback by Basic getrawtransaction patch proposal for bitcoind « Fixpoint — 2019-12-05 @ 17:35
From the #o log :
Comment by Jacob Welsh — 2019-12-05 @ 19:02
> what constitutes a "good" choice of capacity and why?
The sizes are not really relevant ; even 128 will be far beyond amply sufficient, if the presuppositions hold. And if not, obviously, 128mb or any other size is in principle equally useless.
This leaves the choice of capacity, once freed from such considerations, to be matched to more practical concerns. If, for instance, you're contemplating deployment in a UDP scheme, you might want to make it packet size, or half packet size, or somesuch.
Comment by Mircea Popescu — 2019-12-05 @ 20:52
Redid genesis for patch naming and default capacity. Apologies for the inconvenience if anyone's already scrutinized the original; one can always diff though.
Comment by Jacob Welsh — 2019-12-13 @ 06:19
Eh, as long as they haven't published their signature of the previous vpatch, nobody can complain of the regrind!
Comment by Diana Coman — 2019-12-13 @ 07:36
[...] Two implementations of Keccak hashing: one in Ada signed by diana_coman as part of EuCrypt and then translated to vtools & signed as part of that by bvt and phf; one in C signed by jfw. [...]
Pingback by A Walk among the Trees of V « Ossa Sepia — 2019-12-13 @ 18:29
It seems you forgot to update the expected test hash in test-sponge.sh so now the test will fail.
Also, why the -Woverlength-strings in main.c, isn't that included in -pedantic that I see you are using anyway in Makefile? (The "wat" comment is... very helpful, too :D )
Comment by Diana Coman — 2019-12-14 @ 11:26
Will Haack reports successful build and run on OSX 10.9 after removal of -static from LDFLAGS in the Makefile. Some hitches were encountered in getting the tests to run.
From the #o log :
diana_coman: jfw: I went through your keksum proggy and it's been quite a pleasure really; a few nitpicks on top of those: 1. why default/fallthrough on "bad option" instead of the more useful help option? 2. you have nicely \t everywhere except in usage_err in main.c where it's \s 3. just out of curiosity really since otherwise it's of course not a problem at all: since you unrolled various bits basically + made the table for rho, how/why did you choose where to stop with the unrolling anyway? and why not use the constants for iota instead of calc each time (ie lfsr)? 4. why oh why only self-gen test? not like there weren't values and/or ways to obtain them, lolz!
diana_coman: jfw: anyways, once you regrind perhaps to fix the test at least, I'll gladly sign and mirror it.
jfw: 1. usage_err does show the help, but returns a failure status whereas explicit help returns success.
jfw: 2. mixed spaces and tab too, good catch!
jfw: 3. iirc I unrolled where it would allow precomputing arithmetic and especially mod-5 ops in inner loops. Iota does relatively little work, just touching one lane per round, so I preferred to keep it in 'source' form rather than magic numbers which you'd then have to verify against someone else's.
jfw: The table in rho I cribbed straight from the pdf.
jfw: 4. just to clarify, I did use the provided tests for the permutation, but don't recall seeing any for the sponge, perhaps I should look harder.
jfw: "It seems you forgot to update the expected test hash in test-sponge.sh so now the test will fail." - yep, that's what I meant in http://logs.ossasepia.com/log/ossasepia/2019-12-13#1012925
ossabot: Logged on 2019-12-13 17:32:13 jfw: gah, one test broken anyway by the default capacity change, but otherwise working for me, let me check on those errors.
jfw: "why the -Woverlength-strings in main.c, isn't that included in -pedantic" - the way the pragma works is to *disable* that warning as it's tripped by the help text. The 'wat' expands to roughly: 'why does c89 allow compilers to limit strings to something as low as 509 characters? wtf am I supposed to do about this? I have no intention of supporting such broken compilers, next they'll be limiting source file length too.'
Comment by Jacob Welsh — 2019-12-15 @ 20:45
Updated to fix the noted problems except for improved full-program tests.
Comment by Jacob Welsh — 2019-12-19 @ 11:43
[...] signed and mirrored jfw's updated keksum genesis and noted he had borked the article [...]
Pingback by From the forum log, 24-26 December 2019 « Fixpoint — 2020-01-26 @ 02:41
[...] to press the Bitcoin code, or rather the VTree that grew from it, swap out the hash with my own keksum so as to avoid a hefty and otherwise unnecessary GNAT requirement, add my version of the classic [...]
Pingback by Adventures in the forest of V « Fixpoint — 2020-03-31 @ 19:11
[...] second patch, "v_keksum_busybox", swaps keksum and patch in for ksum and vpatch, making V presses possible again on systems with little more than [...]
Pingback by V in Perl with parsing fix, keksum, and starter, plus the ill-fated vdiff « Fixpoint — 2020-04-02 @ 17:50
[...] of files both raw and in the more usual numerical format (e.g. hex as given for instance by the keksum implementation). More importantly for me, Eulora's client can now check the hash of a received file [...]
Pingback by EuCrypt addition: Keccak File Hashing « Ossa Sepia — 2020-07-08 @ 13:37
[...] keksum - for verifying patch output hashes; as a concession to the bootstrapping conundrum, this checking is skipped with a warning displayed if this utility is not found on the system. (Signatures are always checked.) [...]
Pingback by The simplest way yet to fetch Bitcoin code « Fixpoint — 2022-02-04 @ 00:22
[...] experience using and teaching with my keksum utility informed that its main deficiency was not in fact the lack of an equivalent to GNU's old [...]
Pingback by File-level error recovery for keksum « Fixpoint — 2024-03-09 @ 21:03