Date: Tue, 02 Sep 2014 10:46:53 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - Schvrch

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 09/01/2014 11:25 PM, Rade Vuckovac wrote:
> “The time cost has weak average memory*time because only one 2KiB
> block is used while applying time cost.”
> 
> The time cost argument is as it should be, for the time algorithm
> hardening only. The memory cost argument is independent on the time
> cost argument and deals with memory hardening as it is expected.

This kind of statement is why Schvrch is difficult to fix.  Instead of
dismissing claims of weakness in your code, you should try and
understand why I think there is a weakness.  I am not the only poster
to point out flaws in Schvrch, and not a single concern was properly
addressed.  Simply claiming "The time cost argument is as it should
be," says nothing other than you think you are right and I am wrong.
I happen to believe the opposite in this case.

I posted a simple ASIC attack this morning that benefits by about a
factor of 200X in speed due to this weakness in Schvrch.  Let's talk
about this again when you understand this attack.

> “No cryptographic primitives are applied, yet the mixing function
> seems weak.”
> 
> Could not be more wrong. It was tried in the April discussion to
> point some crypto analysis relevant to the Schvrch submission. One
> of them is here http://dakhilalian.iut.ac.ir/pdff/C26.pdf

I pointed out real weaknesses in the mixing last spring, but you
continue to simply claim everyone else is wrong about the weaknesses
they're finding.

I posted another attack this morning that takes advantage of the
mixing weakness when m_cost == 0.  An attacker basically can ignore
the revolve rounds and determine if his guess is correct in constant
time, independent of t_cost.

> “The evolve function at end just XORs states together and
> complements them, leaving each as a simple linear combination of
> the original. The author seems to have the mistaken impresion that
> just XORing data over and over will mix it well.”
> 
> The very last program listing in Appendix (Schvrch submission) is a
> random number generator which just “XORs states together and
> complements them” and just do “XORing data over and over” and still
> produces descent random streams.
> 
> However that does not mean it is secure.

I agree with this last statement.

> If the submission paper is read / understood, then it will be clear
> that the branching programing structure is a force behind “mix it
> well”. The toy password hash scheme using the same security
> paradigm as Schvrch may serve as an example.
> 
> Let n be a 512 bit string (salt and password combo). Treat n as a
> positive integer. Apply (3n+1)/2 if n is odd else do n/2. The
> result is new n. Repeat step above 256 times to the every new n
> created to acquire a 256 bit parity string (recording 1 when new n
> is odd and 0 when new n is even). Discard first 128 bits and use
> the remaining 128 bits as the hash of n (arguably the tiniest
> secure password hashing scheme around).

Very cool...

> The paper has 2 lines of argumentation of why above is perfectly
> secure:
> 
> 1.      While toy algorithm is sort of described that does not mean
> that function description (in theoretical sense) is there. Without
> knowledge of the input the toy function can be composed in 2^256
> ways and the composition depends entirely on the input. There is
> the case mentioned in random oracle theory when input complexity is
> on the par with function description complexity. While this case
> guaranties non-correlation between function instances (the
> randomness) it is considered as impractical exercise (requires
> gigantic table with records of fair coin flips).The toy algorithm
> is practical when input (or output) is known. But with partial 
> output (the toy case) the only way to match input is exhaustive
> search because only complete input or output can define function
> composition.
> 
> 2.      If there is possibility of finding some pattern /
> correlation between instances when above algorithm is run, then
> that possibility is a reduction of 2^256 complexity mentioned
> above. In effect it will mean that branching can be reduced by
> combination of the sequence and the looping algorithm structures.
> That runs against structural programming theorem claiming branching
> as a basic structure. Simply put, it is impossible to make program
> for checking inputs of 3n+1 problem without using the branching
> structure or some sort of exhaustive search.

Both of these statements may be true about your code, but it is still
dangerously insecure.  Defensive password hashing involves additional
criteria over cryptographic hash functions, such as insuring the
attacker must use as much memory for just as long as the user (or as
close to this as possible).

By the way, after reading this, I take back my statement that there's
no reason to believe Schvrch produces a "secure" hash.  It sounds like
you have done plenty in this area.  However, I see several angles for
attacking your code.  Obviously there is a disconnect between the
paper's proof of security and the reality of attacks against your code.

> “I don't think there's much reason to spend a lot of time
> discussing this version of Schvrch.”
> 
> The last statement and entire Mr Cox’s post is maybe fine as a
> blog material where expressing opinions without substantiating them
> is a norm. The frequency of that kind of posting, here, is not
> helpful either.
> 
> Rade
> 

I apologize for that.

I do make a lot of mistakes in my posts.  Part of it is I have no real
idea about how real people respond emotionally.  I did not want to
take time arguing with you when you've been quite clear about not
caring about the weaknesses we pointed out so far.  I figured that
anyone reading along would have noticed, and would have already
dropped Schvrch as a potential winner, and that just skipping the
review would be better for everyone.  I was wrong.

Until the weaknesses we pointed out already are addressed, there isn't
much point spending more time on Schvrch, IMO.  The simple fact that
you refuse to address the time*memory cost weakness (as you restated
above) should be enough to make this clear.  Your dismissal of the
hashing weakness in the t_cost loop is a similar situation.

Anyway, try and figure out what's wrong with Schvrch that allows for
so many simple attacks against it.  That's not my job.  I'm just
pointing out weaknesses I see.  If you don't want to address real
weaknesses, we should just move on.

Bill
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJUBdhZAAoJEAcQZQdOpZUZ1DsP/3HO8F2r52GlO8taedx92ZFg
jjbx27NXqGWTqsj2j00m+TmQhK1uYILBPFCCLx2V9O6zOcb549RCrWh/dCZoK55a
kxlCzFv1Pxt9L+LNc5R6E0tOzukdikP8A7UZw8yfxOxhHm3tea3tG4r2NYF/FZk4
VeQR8g8AKFbyXo894zgtPu5aVmCh2hCQgscXUhc4Q2uYAnNpSjMiMpYqm1Y6xe3l
pPJieEs8B/uSqcH7zAjfxIayoldqzIT7GoqpbMK4d7gfYv6FMs5BKAUsyrJMuOnV
8c0cAba+bECP5b7rAxqPzWHEMzTtyZ7iHkPlxEbqBTokBI1oayTqzlbrCyFnJL4T
6YFN77mbRs344qByVMX0gdLEwR3jRO+ulgee5PX3PMrXuLGx6TEHHIXJhe5TnFtS
tuOW98iAWbOPrInJqOZdQrQxXEHDCq9QlWw1VtDlnf6q37VSsX8nHGHiA1x8HhMi
j9gK+ayMLVnJ0HuHXPFL6onylvOxtIA9zEBgcblFBrdG+CG5f4g9fHhGEr8skpBv
7SJuvTFxSahDGcttjY7oHzFYB9ZNgPrGYHsNkz/wqERnoVZKZoC7GU7cyHqDy6Ms
ryOQqO+cnWHun8bbmh15OzzlgPJp15uxDPRekuVSGxMlKpYejwhjHmzmPoXihji/
XvFILe2t0wJVnKPttf5s
=bVh8
-----END PGP SIGNATURE-----

Powered by blists - more mailing lists