lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening linuxcveannounce PHC  
Open Source and information security mailing list archives
 

Date: Mon, 15 Sep 2014 12:35:39 0400 From: Bill Cox <waywardgeek@...hershed.org> To: discussions@...swordhashing.net Subject: Re: [PHC] A review per day  Schvrch BEGIN PGP SIGNED MESSAGE Hash: SHA1 On 09/02/2014 02:49 AM, PoulHenning Kamp wrote: >  In message > <CAG+Gt9ZwKnCamXQEPP2iFSmN1HO6nBC8wqdg8QHQsS_o6BxLkQ@...l.gmail.com> > > , Rade Vuckovac writes: > > I think Bill missed the point about Schvrch *big* time. > > Cryptography is at its foundation about finding ways to mix up > bits, to make them unrecognizable without loosing their entropy. > > Once you dive into it, the actual palette of tools at our disposal > is much smaller than most people realize, and many of those tools > are even specific variants of more general tools from the same > palette. > > Schvrch adds an entirely new tool to the palette  no mean feat. > > I have no idea how Bill could overlook this, but my guess is that > the compactness of what was proposed and the lack of orthodox > encryption primitives deceived him into not paying proper > attention. > > He should. > > Schvrch was one of the submissions which made PHC worth the effort > for me. > > Schvrch's mathematical pedigree lists both Von Neumann[1] and > Wolfram, both were fascinated and frustrated by the seemingly > unlimited complexity arising out of trivially simple rules. > > That of course is no guarantee of cryptographic utility. Only > time and analysis will tell if Schvrch's new tool is any good. > > But Bills dismissal of mathematics which frustrated both Von > Neumann and Wolfram as "just XORs states together" and concluding > that "not much effort went into it" is not even wrong. > > PoulHenning > > [1] The paper inexplicably fails to credit him. > I finally got around to reading the paper behind Schvrch's hash function. The idea is cool, and I have to give the author credit for thinking of using Wolfram's CA for hashing. However, I prefer ARX hashing, and ARX hashing with multiplications. These primitives (especially multiply) are harder to speed up in an ASIC. Here's the right way to do Wolfram's Rule 30 CA in a way that may be useful for hashing: static uint128_t updateState(uint128_t a) { uint128_t lsb = a & 1; uint128_t msb = a >> 127; return ((a << 1)  msb) ^ (a  (a >> 1)  (lsb << 127)); } This updates 128 cells in parallel. We probably want this to be extended to 256 bits, or 512, but this is the function I am testing. I verified that it generates exactly the same pattern as the paper shows for the first 22 states. Note that it is a reversible permutation, and would have to be combined with some sort of data compression to be used for cryptographically irreversible hashing. When I repeatedly call updateState 97 times, and then output the 16 byte state, it passes the dieharder tests, which of course means nothing other than it is not obviously nonrandom, but at least I was not able to rule it out as a candidate with simple tests for randomness. This is very similar to ARX hashing. It has a left and right rotation, and an XOR, but an AND instead of ADD. This nonlinear operation is enough to thwart my attempts to take large shortcuts at a boolean logic level, but not as easily as with adders. I think I can speed up this hashing in hardware by computing factors needed for 3 states ahead and XORing them together. Enough factors cancel out that I think I can speed it up by about 50%. However, in reality, I would not bother, since I can pipeline the heck out of this and compute hashing for multiple passwords in parallel. This thing will really scream in silicon. It is the most ASIC friendly hash primitive I've seen, which caused me to think of Keccak. I compared this to Keccak, and I see that Keccak already uses Wolfram's CA! From Wikipedia: "χ Bitwise combine along rows, using a ← a ⊕ (¬b & c). To be precise, a[i][j][k] ← a[i][j][k] ⊕ ¬a[i][j+1][k] & a[i][j+2][k]. This is the only nonlinear operation in SHA3." For a fixed k, this is just one of Wolframs Rule's, but it is essentially the same as Rule 30. Here's the LUT for Wolfram's Rule 30: ABC Q   000 0 001 1 010 1 011 1 100 1 101 0 110 0 111 0 Keccak uses this: ABC Q   000 0 001 1 010 0 011 0 100 1 101 0 110 1 111 1 This is just Wolfram's Rule 210. This is trivially equivalent to Rule 30, since all we have to do is negate the output, and the 2nd input to get the same exact truth table. So, I think this is not a completely new idea. No wonder Keccak won the SHA3 competition! It's incredibly ASIC friendly! That's bad for our purposes. ReedMuler cannonical forms show that ANDXOR is capable of computing any Boolean function. The ROTATE is needed to for mixing between bits. This is minimal in the sense that we can't drop any of the three operations and still be capable of computing arbitrary multibit functions. Schvrch also tries to introduce ifthenelse branching as a novel way to mix data. I think AntCrypt took this to an extreme where it might be useful for GPU defense (if rewritten properly), but Schvrch got the branching wrong, and it does not do what the author intended. Except in the stir function, which introduces an ADD operation, the Wolfram CA can be factored out as a separate 256bit CA, sped up using a parallel loop like above, and applied as a postprocess to the state values, which can be computed in constant time, regardless of the number of rounds. This is not only much faster, but avoids any databased branching. On the positive side, the code above has no branching on the data, which otherwise might leak password data through the icache, it executes Wolfram's CA many times faster, and can work well in SIMD units. The place I would most likely want to use Wolfram's CA 30 is in a rewrite of AntCrypt. AntCrypt has a great idea, but poor implementation. I was thinking of replacing their function list with randomly generated ARX combinations. I think adding ANDROTATEXOR functions would be a good idea. I'm still not sure I like the idea of branching based on the data, though, especially right from the start. Maybe a hybrid algorithm could work OK, where we don't do data dependent branching or memory addressing for the first half. Bill BEGIN PGP SIGNATURE Version: GnuPG v1 iQIcBAEBAgAGBQJUFxVYAAoJEAcQZQdOpZUZGoUP/ic48+V4CRCOyAAoGQTj4iXP MbnyxgSVa7XvoH1208DbvIxgQb2r4EiaN12jybK6PRDQ8OXjqgEfQNbId0JmWrYM etxgCdFVrJWC5k+johxXvpAdB2W6KCnppuerYy+oJC0jbYEELQeGfAYdr7j9WvmR L52Jk7iLm1ppecS327C6HHi6M8JprJ1vbNunpF6ei2IziIT7GjLOJkTe5oTnf5fH x9HdZUGmxIO0iYx9dbtiChVlFj/xhIB0gZ+E9GzPopV8hbdCIoZT4vbFUhNeWT9M BPrT6uU2DTGyyXFa6jnA432iw2+hVO8sbAPBZCww6HLxp1/aKqdQIBdCaskh3eSP zzRcexubHH3ETMueepnC/GEYZDn6JnwQgL5Zpno4qIGt8U8hONdR2lANMD2Iip7l PXDFyI4nD4UMdxV+zz+9NRqgGnyh4PoPYSwoPr96PVs2Lv6hscUBwlyQcxeaQ+kh QzqC4qYQtABQI/Jcy6VxQld49peCqlGpZWxVYQNGdW8Legh2bYpKUqjcy9lrYbLA 1PlMxS5IL4ji7Vh2emG1t6U7YNBIxghgakIBrt22OIm6e+jZ3uPpoxluliOedaqR dJsf8rq/ke2VI6dgrdYcNbOHXXGe9bZrAbCnjXZ915bUeEt/P1aXQ6gvYl5Vft1z ZUV7d/hY7Kyg3wsMZvte =iVZ/ END PGP SIGNATURE
Powered by blists  more mailing lists