phc-discussions - Re: [PHC] Schvrch is broken

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Wed, 17 Sep 2014 09:19:12 +1000
From: Rade Vuckovac <rade.vuckovac@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Schvrch is broken

My err, lapsus ... apologies ... I keep forgetting that.



The solution is simple with reintroducing mixer with value 010101...
instead of 000000... (was there in the first place to nullify above
mentioned xor properties) Mixer addition is actually the only difference
between stir and revolve and it was dropped (long time ago) for the
performance sake believing it was safe thing to do.



On the positive side the 117 lines of code will shrink considerably (less
chance for bugs) and the algorithm will become significantly simpler (will
be posted in near future).



Thanks for clearing things, Rade

On Tue, Sep 16, 2014 at 8:59 PM, Bill Cox <waywardgeek@...hershed.org>
wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 09/15/2014 11:29 PM, Rade Vuckovac wrote:
> > case 1 carry = b xor c xor d
> >
> > case 2 carry = b xor c xor ~d
> >
> > case 3 carry = b xor ~c xor d
> >
> > case 4 carry = b xor ~c xor ~d
> >
> > case 5 carry = ~b xor c xor d
> >
> > case 6 carry = ~b xor c xor ~d
> >
> > case 7 carry = ~b xor ~c xor d
> >
> > case 8 carry = ~b xor ~c xor ~d
> >
> > a’ = a xor (can be any of the cases above*) carry
>
>
> The value of carry is equal in cases 1, 4, 6, and 7.  The value of
> carry is also equal in case 2, 3, 5, and 8.
>
> There are only 2 outcomes here, not 8.  These are basic XOR identities:
>
> a xor b == ~a xor ~b
> ~a xor b == a xor ~b == ~(a xor b)
> ~a = a xor 1
>
> I like to add a few more so that I can convert any Boolean equation to
> Read Muller form by hand easily.  I'll use + for xor, because xor is
> addition, and it makes it easier to see:
>
> a(b + c) = ab + bc (distributive)
> a*a = a (power)
> a + a = 0 (like terms cancel)
> a*!a = 0
> a or b = !(!a!b) = !a!b + 1 (convert OR to AND)
>
> So, for example, when I try to simplify Wolfram's Rule 30, I do it
> this way:
>
> a2 = a1 + (b1 or c1) = a1 + !b1!c1 + 1
> a3 = a2 + !b2!c2 + 1
>    = (a1 + !b1!c1 + 1) + !(b1 + !c1!d1 + 1)!(c1 + !d1!e1 + 1) + 1
>    = a1 + !b1!c1 + (b1 + !c1!d1)(c1 + !d1!e1)
>    = a1 + !b1!c1 + b1c1 + b1!d1!e1 + !c1!d1!e1
>        b1c1 = (!b1 + 1)(!c1 + 1) = !b1!c1 + !b1 + !c1 + 1
>    = a1 + !b1 + !c1 + b1!d1!e1 + !c1!d1!e1 + 1
>    = a1 + !b1 + !c1 + !d1!e1(b1 + !c1) + 1
>    = a1 + !b1 + !c1 + (!d1!e1 + 1)(b1 + !c1) + b1 + !c1 + 1
>    = a1 + (!d1!e1 + 1)(b1 + !c1)
>    = a1 + (d1 or e1)(b1 + !c1)
>
> I probably made a mistake in there...
>
> Anyway, in silicon, if I did not make a mistake, this is 2 XOR gates,
> and OR gate, and an AND gate.  I think I can get this running about
> 50% faster than the straight forward computation.
>
> Bill
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1
>
> iQIcBAEBAgAGBQJUGBgdAAoJEAcQZQdOpZUZRuMP/19YVpQqZAkzn2PF7PGfy1Lv
> f78fkSKD4803c08hIL9eoE6VbQdNxfr970yFtvc1uR/wwMFaP4tiFj/yaGJXfMgM
> Eb/wol0Nrdk7yrOgfLTf2JJJ65TtL/hOaHw2FKZT5mZUyvwdu5Bqk8UetFcRcbJx
> wwNN6dJznHbEZJs+5HWJB7GePEXNN6F9ZhpA6YtZFmyPfyruzxCoSnezyWLIF7Oe
> Wy03eWsMrM9yNg5wAzfYCqsSKreQOPO9HXJZwC6PNLTBG79RS1Izz/LKE0ksJ7WK
> cwcjYBD0q14TNAzQzk+MD4hgcohVVg+1x8bJuQOz77bnUQlSJx54H7AkrcZlYIaO
> gdI3b7ZGYE8aEc2HGHyQWSkUEF+bqGQPBeCyl6dUxPH16N5ILaJu9RVtpXLc4R4v
> ERSWMd3ZehXLuAZiMhcw2Ww6sTkbzap46THWVMkrVlvoy/5SttP3/tuqCONMHyzx
> 5DlQY8SnQFqOhrDtw1dUC2XcYqDrI029HsR9f2TOs+q/ibBOVKWbgtQ0epxvKhwq
> +qjDlFyzfNXn74bvh5kRosn5mc/NZX2AVgU0m2gK2avry4V5t9d4DDcuJMgGK/Ln
> /kKlv0Jt0aP+0zLDYiYs9262KW6RoAx2+kdl9GGFypDWzrBhoknsEcLQo6MxEg4p
> TCDxfNCMaAPufQhStftd
> =CnFd
> -----END PGP SIGNATURE-----
>

Content of type "text/html" skipped