Date: Tue, 2 Sep 2014 13:25:57 +1000
From: Rade Vuckovac <rade.vuckovac@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - Schvrch

On Sat, Aug 30, 2014 at 7:10 AM, Bill Cox <waywardgeek@...hershed.org>
wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Since I do not expect a lot of Tortuga discussion, I'm moving on to
> Schvrch.  Here's a link to the April discussion:
>
> http://comments.gmane.org/gmane.comp.security.phc/1330
>
> Here's my notes on Schvrch:
>
> - - Weak paper and code.  I do not believe much effort went into Schvrch.
> - - The time cost has weak average memory*time because only one 2KiB
> block is used while applying time cost.
> - - No cryptographic primitives are applied, yet the mixing function
> seems weak.
> - - 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.
>
> I don't think there's much reason to spend a lot of time discussing
> this version of Schvrch.  So... I'll post one more today...
>
> Bill
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1
>
> iQIcBAEBAgAGBQJUAOw4AAoJEAcQZQdOpZUZ0B0P/RIqxqQHHPXpo7Z69yUP+5y9
> C3vKgifAA30SELrKOaZgMMGUZeXfnWCTrFI5e/pHydpUkLHZ24vL5qKe7+yUc+ic
> gkxkl/V88lNk9szLhNfErdbfh56UgaQtWD12S+lMCpMpl5q0G39ebiqTF2B+jaMX
> mAVoFiFEZC6Zs7128QZYo16Mof8/9SNaucPcFAsOxhuF8ox8KYIVYlhuRukbIkCy
> A0wQ4m5u5OqFMARqz9663tENpGrrZ8dZiVoEJZiYjoFQuHOI42qYqRHyXjPqRlrM
> WHTQVanz/Qs7XEUeoTEZx9uyMrwWP9M+kdiHWrFutJ8m0hiOPXkr8HICvbAqM4Io
> 46j7Yfj0ZS5ReR65rlaGBgcXIXIp4OBv5WboQQhBJFKA9qfeuRbUr2bD9LvmsxG9
> JmYXtbwW+LfyJug9uJKfkPVxb5k+THSy701KVaAklpOFylTycqrssSzHJ3eto78U
> BzYR4ieZY92yeljeQCOMGbZvUPLUWscWuPBMsFm/r4BNsAaEXreuciIBJI0Cd0fS
> diR3wT/NZr/+zijIPfh8dLI2LfFQcR+eIsBcfSGvJDANOPCqma/K0dUOb6Np3JdP
> DCOk6gneSRvCef+NnyP0P7kT8UBdsOww/sgsMU5pkdGF99fZ6GI4qJ+VefXdaT3M
> Y7/IZyJmHml3mGVJEdeA
> =yJe+
> -----END PGP SIGNATURE-----
>
“Weak paper and code. I do not believe much effort went into Schvrch.”

The paper in question is published here
http://iaeng.org/publication/WCE2014/WCE2014_pp134-139.pdf (peer reviewed
conference paper).

“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.

“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

Here is the paper abstract

MAG is a synchronous stream cipher designed by Vuckovac submitted to the
eSTREAM project. Vuckovac also proposed two modified versions of MAG to
avoid the distinguishing attack on the first version of MAG presented by
Fischer. In this paper we show that, changing the Fischer’s attack we can
apply it to one of the modified versions of MAG. The modified attack
requires only 514 successive bytes of known keystream and 5 xor and 2
comparison operations between 16 bit words. In addition, we show that
distinguishing and key recovery attack proposed by Simpson and Henricksen
on all versions of MAG is feasible just by considering an assumption on
initialization of MAG that simplifies this step so much. Therefore, their
attack cannot be performed in general.

>From there it is obvious that only the Fischer’s attack is relevant to MAG
scheme and it cannot be applied to the every proposed modification.

It should be noted that MAG and Schvrch share the same primitives and it is
believed that only relevant attack so far (the Fischer’s attack above) is
irrelevant to the Schvrch.

“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. 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).

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.

“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

Content of type "text/html" skipped

Powered by blists - more mailing lists