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

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

4 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

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by MP-WP. Copyright Jacob Welsh.