"Keccak" is a cryptographic hash function, or rather, some primitives for constructing such functions in a desired size and shape, of relatively recent design as these things go. It was brought to the attention of the forum in early 2016 in the context of contemplating changes to the Bitcoin protocol,(i) (ii) (iii) and subsequently differentiated from SHA3.(iv)
Compared to the prevailing standards at the time - mostly variants on the MD4 concept, processing blocks of input through an iterated compression function - Keccak is based on a large pseudorandom permutation (1600 bits, though the spec also defines smaller variants). As this is readily invertible, the desired "one-way" property is provided by a "sponge construction", mixing in blocks of input and extracting output while iterating the permutation and keeping some number of its bits secret as internal state. This number is called the capacity (or by complement the rate, the two summing to the permutation bit width) and can be tuned for the desired balance of security and computational intensity. The construction can take unlimited input, or produce unlimited output as a kind of stream cipher.(v)
I started out in 2017 playing with a C implementation found in the wild, supposedly a "readable and compact" version written by the original team. With some cleanup I got it into a state that could be described as compact, but I couldn't get very far in reading it, at least without having first digested the spec. And it had the unfortunate limitation of requiring the full input and output to exist in memory, no streaming. My confidence as an applied cryptographer was growing and I soon implemented a number of classical hash functions, but set Keccak aside as not being an immediate necessity. Meanwhile, Diana Coman produced and incrementally published a very nice and documented reference implementation in Ada, which was adopted for use in V and soon became non-optional.
While I was well convinced by the Republican rationale for Ada, I was much less keen on introducing GNAT, the flagship implementation, into my environment. It was a million-plus-line-of-code beast that I wouldn't stand a chance to ever really understand; making matters worse, it was a "Thompsonism", a circular dependency requiring existing binaries in order to build from source and thus dubiously "open source" at all. While I already depended on one such thing - the C compiler - I was hoping to somehow keep this to ONE thing, or at least ensure a way to work with the crucial V on existing machines without pulling all this in.
Stay tuned for the result.
mircea_popescu: actually i wouldn't go to war over keccak.
mircea_popescu: letting bitfury & friends eat 100mn in unrecoupable engineering costs would provide exactly the correct lesson as to what it's a good idea to say and when it's a good idea to shut the fuck up and toe the line.[^]
- The necessary prerequisite for any change to the Bitcoin protocol [^]
mircea_popescu: http://log.bitcoin-assets.com/?date=01-02-2016#1393026 << at least it wasn;t fucking developed by teh nsa.
assbot: Logged on 01-02-2016 19:29:18; ascii_butugychag: ;;later tell mircea_popescu in what sense is adoptinc keccak a rejection of usg standards? it was actually adopted as sha3...
mircea_popescu: as far as we know. whatevs. minor point.
ascii_butugychag: btw between that thread and now i went and read the keccak spec
ascii_butugychag: it is mighty spiffy.
ascii_butugychag: accordionizes to size.
mircea_popescu: :)
mircea_popescu: i don't need to explain what i meant by not finite then ?
ascii_butugychag: aha.
ascii_butugychag: other hashes also accept infinite bits but they eat where they shit.
mircea_popescu: quite.
mircea_popescu: and mind that while in no means do i propose this is "Asic resistant", from a designer perspective you must appreciate i'm giving you a fun job to do.
mircea_popescu: at least therer's that.
mircea_popescu: always make sure everyone's having fun.
ascii_butugychag: quite! nobody will be plagiarizing old verilog from fpga docs to bake this one.
ascii_butugychag: very asian-resistant.
ascii_butugychag: which is a mega-plus.[^]
asciilifeform: holyshit the original keccak www is gone
asciilifeform: replaced with some horrorshow
asciilifeform: ada code -- gone
asciilifeform: fortunately still on my hdd
asciilifeform: check this out, keccak.noekeon.org now forwards to buncha tards
asciilifeform: https://archive.is/GkmgU < original
shinohai: Notice that happened after nist.gov declared their spec
asciilifeform: shinohai: not immediately , iirc was still intact last yr
asciilifeform: incidentally shinohai keccak != usg.sha3
asciilifeform: they adopted ~particular params~ of keccak as the new national whatever
asciilifeform: orig is ~family~ of functions.
asciilifeform: see also https://archive.is/lViVh << since 'unhappened' article
asciilifeform: ' The SHA-3 version of Keccak being proposed appears to provide essentially the same level of security guarantees as SHA-2, its predecessor. If we are going to develop a next generation hash, there certainly should be standardized versions that provide a higher security level than the older hash functions! NIST, in the original call for submissions, specifically asked for four versions in each submission, with at least two that would
asciilifeform: be stronger than what was currently available, so it's hard to understand this post-competition weakening.'
asciilifeform: didjaknow.
asciilifeform: notice how 'everyone' nao thinks 'oh, keccak? that's called sha3 nao' [^]- Since state is still finite, output will of course repeat eventually; one would hope this cycle length approaches that order of 21600. [^]
I hear you re GNAT. There is however ave1's work on owning that beast.
Comment by Diana Coman — 2019-12-03 @ 19:20
Re: Ada/GNAT -- as described on Mocky's (RIP) www -- I picked it (and later other folks grudgingly agreed) via a "healthiest horse in glue factory" exhaustive search process, starting from a "pointer arithmetic and type casting Must Die" precept.
It was the one and only prog. language I turned up where: overflowism goes to its long-overdue grave; paper standards exist, going back to 1980s; reasonably-mature compiler for all commonplace irons; no GC or other heavy runtime ball-and-chains.
IMHO it is possible to implement a sane (i.e. less than 50kLoc, say) self-eating compiler for the subset of the language I and others made use of (snip out the OOPisms; microshit, vax, etc. dead platforms support, other superfluous rubbish.)
Re: Keccak -- similar "glue factory" process, but orig. initiated by MP (I found no catastrophic flaw such as to disagree); must note that it suffers from same problem as e.g. Serpent (and all known symmetric ciphers) -- i.e. neither Keccak nor any other known hash algo rests on any number-theoretical conjecture, but instead all were made by the same process as the other "voodoo products" in the "hashes-PRNGs-symmciphers triangle" -- "it appeared to be hard to break for author himself, therefore Must Be strong".
Comment by Stanislav Datskovskiy — 2019-12-03 @ 20:27
[...] produced a Keccak implementation in May 2019, through about one week of intensive study and hacking. It builds on [...]
Pingback by keksum, a Keccak implementation in C as standalone Unix utility: genesis « Fixpoint — 2019-12-04 @ 17:37