Fixpoint

2019-12-04

keksum, a Keccak implementation in C as standalone Unix utility: genesis

Filed under: Software — Jacob Welsh @ 17:36

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.
  1. 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. [^]

13 Comments »

  1. Builds, runs, and matches output of Diana's classic Keccaktron (when set to -s256.)

    Comment by Stanislav Datskovskiy — 2019-12-04 @ 17:56

  2. [...] 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

  3. From http://logs.ossasepia.com/log/ossasepia/2019-12-05#1012028 :

    jfw: http://logs.ossasepia.com/log/ossasepia/2019-12-04#1011900 - thanks diana_coman. re "how secure", sure - expected number of clock cycles required to break (collision, preimage etc.)
    ossabot: Logged on 2019-12-04 15:27:38 diana_coman: jfw: hah, certainly makes for less tense reading! can confirm too that it builds and matches expected hashes; further than that, the code will require some pen-and-paper reading though; re "as secure as SHA3", do you have some sort of "how secure" measurement at all?

    jfw: granted there's no proof on lower bounds there, but upper bounds can be found.
    jfw: In thinking about the sponge construction, I had convinced myself that 2^capacity was such an upper bound. I'm struggling to precisely recall why, perhaps I should try to have it out as a proof
    jfw: but if so, smaller capacity is less secure in that sense. However I have no idea whether larger capacity might make it less secure in some other way (more frequent iteration of the permutation 'leaking bits' or something)

    jfw: http://logs.ossasepia.com/log/ossasepia/2019-12-04#1011901 - interesting, it was deliberate (e.g I ended up with same for yrc genesis); I'd been thinking of each V 'project' as its own namespace for patches just as with the files in its tree
    ossabot: Logged on 2019-12-04 15:27:54 diana_coman: jfw: that "genesis.vpatch" is a horribly-chosen name.
    jfw: or are main.c or Makefile also horrible names?

    diana_coman: jfw: eh, re genesis vs main/makefile - don't mix stuff there really; the idea with V overall is of building yggdrasil not just having tree-stumps all over the place (and all of them starting at genesis because ofc!)
    ossabot: (trilema) 2018-10-15 mircea_popescu: kinda the fucking point, building yggdrasil over here.
    diana_coman: how do you reason anyway re similarity genesis-main/makefile? because "genesis" is whatever vpatch is the root of a tree but not really substantially different in any way from another vpatch otherwise.

    diana_coman: http://logs.ossasepia.com/log/ossasepia/2019-12-05#1012033 - this is pretty much the core trouble - there is no clear proof of "this is indeed more secure than that"; you can pick and choose various criteria, sure, but what they mean exactly is not that clearcut.
    ossabot: Logged on 2019-12-05 00:53:58 jfw: but if so, smaller capacity is less secure in that sense. However I have no idea whether larger capacity might make it less secure in some other way (more frequent iteration of the permutation 'leaking bits' or something)

    jfw: http://logs.ossasepia.com/log/ossasepia/2019-12-05#1012039 - I recall discussion of using the hash of a genesis patch to identify the trees it creates, suggesting to me that the genesis should contain some unique context
    ossabot: Logged on 2019-12-05 03:37:56 diana_coman: how do you reason anyway re similarity genesis-main/makefile? because "genesis" is whatever vpatch is the root of a tree but not really substantially different in any way from another vpatch otherwise.
    diana_coman: I can't figure out which discussion you are referencing there, hm; but even as you state it there, that would be something done from outside *with* a patch considered "genesis"; basically any vpatch has a hash anyway, could equally well use that to identify the (sub-)trees that start from it, no?
    jfw: also probable I don't quite grasp the overall vision. ATM what I see does look more like a forest of separate projects than one big tree
    jfw: let me see if I can find it.
    diana_coman: yes, it is; partly because parts are still missing (most glaringly moving files)
    ossabot: (trilema) 2019-11-06 diana_coman: mircea_popescu: not as far as I know; it was always *not done* but always popping up in people's memory as "working"; except every time I wanted to *move* a file rather than have it del/add, it turned out that ...no.

    jfw: the discussion I recalled is hereabouts
    ossabot: (trilema) 2016-06-13 mircea_popescu: mod6 the part where each press should end up collected in the /genesis-hash/ dir is settled, i thought ?

    diana_coman: jfw: the way I read that is that a v-press from a leaf that has several possible roots should end up in as many dirs as you have roots - ie as many presses effectively - with each dir named based on the hash of the corresponding root (admiteddly I didn't go back fully to see maybe there's more I don't recall on that older convo)
    diana_coman: ie not literally "genesis-hash" but "root1Name-its-hash" of sorts.

    jfw: I'm still finding the linked convo pretty confusing fwiw, a couple different aspects being discussed possibly.
    jfw: I think the "several possible roots" scenario is ruled out by the manifest
    diana_coman: yes, it is not very clear and moreover it's also a bit old by now so some things have changed, most notably - yes - the manifest part.

    diana_coman: jfw: anyways, now you basically give people a lot of work to do to catch up with your code that's finally published; I suppose that balances at least the writing-pain of sorts but I still feel like poking you in the eye for keeping silent for so long.
    jfw: More directly to the main.c/Makefile question, if patches are all existing in some unified tree (though I'm as yet unsure quite how that would work), top-level names like that could come in conflict and perhaps each 'project' needs its own subdir, as seen for example in trb and mp-wp
    jfw winces, rubs eye

    diana_coman: I think that and similars will get clarified only as the thing finally gets moving towards that yggdrasil; so yes, not clear yet and it's been stuck for ages too.
    jfw: alright, small steps then. Think I should regrind that 'keksum' genesis to include name? Could just rename the file too but the name is also in the manifest.
    diana_coman: please do, yes; it's anyway less pain now before anyone else signed it.
    jfw: aite.

    Comment by Jacob Welsh — 2019-12-05 @ 19:02

  4. > 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

  5. 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

  6. 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

  7. [...] 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

  8. 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

  9. 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 http://logs.ossasepia.com/log/ossasepia/2019-12-14#1013020 :

    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

  10. Updated to fix the noted problems except for improved full-program tests.

    Comment by Jacob Welsh — 2019-12-19 @ 11:43

  11. [...] 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

  12. [...] 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

  13. [...] 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

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by MP-WP. Copyright Jacob Welsh.