SHA256 + concatenation as good as scrypt?

[lsparrish]

I have been thinking about a possible algorithm for key derivation, for use with brainwallets and so forth:

Code:

import hashlib
def derivekey(passphrase,rounds=1024):
    def getdigest(x):
        return hashlib.sha256(x).digest()
    concatenation=getdigest(passphrase)
    for i in range(rounds):
        result=getdigest(concatenation)
        concatenation=result+concatenation
    return result
print derivekey('this is a test').encode('hex')

It simply applies sha256 a bunch of times while prepending results to expand the size, with the final result being based on the whole series (as is the case with each intermediate result).

This is an extremely simple algorithm, but as far as I can tell it seems to be just as useful as scrypt (which is more complex). The succession of digests each rely on the presence of the past ones, so it has to be done sequentially, and has to use up memory.

Am I missing something critical here?

[1714962389]

1714962389

[1714962389]

1714962389

[1714962389]

1714962389

[1714962389]

1714962389

[gmaxwell]

Am I missing something critical here?

Please don't go inventing your own cryptography when it can be avoided.

Scrypt did the work to write up an extensive analysis of their effort, and it was reviewed by many people at great cost. And even then the result has not been totally criticism free (http://eprint.iacr.org/2013/525).

With a quick glance at the shape of your implementation, it could have trivially failed to be memory hard at all had you appended instead of prepending. I expect that it's actually spending all of its time shuffling around strings, and that a gpu implementation of it would still end up being a zillion times faster...

[Come-from-Beyond]

Am I missing something critical here?

Yes, Scrypt also put high pressure on CPU cache.

[lsparrish]

Please don't go inventing your own cryptography when it can be avoided.

Scrypt did the work to write up an extensive analysis of their effort, and it was reviewed by many people at great cost. And even then the result has not been totally criticism free (http://eprint.iacr.org/2013/525).

I understand that new crypto has to go through a complicated vetting process to be trusted, and there are good reasons for this. I am just curious as to why something simpler was not settled on in this case. Unnecessary complexity is not our friend.

With a quick glance at the shape of your implementation, it could have trivially failed to be memory hard at all had you appended instead of prepending. I expect that it's actually spending all of its time shuffling around strings, and that a gpu implementation of it would still end up being a zillion times faster...

Lower level code that preinitializes the byte array and moves the pointer down with each iteration could eliminate string-shuffling in software. (I don't know what Python is doing when it prepends -- maybe it's all linked lists or something.) Why would a GPU implementation be faster?

Yes, Scrypt also put high pressure on CPU cache.

Can you elaborate on this? I couldn't find anything in the scrypt paper, or its Wikipedia article regarding "high pressure on the cpu cache". What does that even mean?

[Come-from-Beyond]

Yes, Scrypt also put high pressure on CPU cache.

Can you elaborate on this? I couldn't find anything in the scrypt paper, or its Wikipedia article regarding "high pressure on the cpu cache". What does that even mean?

Scrypt intensively reads small chunks of memory from random locations. You implementation reads RAM in ascending order so CPU can easily predict what to put into a cache before u need that data. For Litecoin it's necessary to have 128 KiB stored as close to CPU as possible (512 KiB for SIMD implementation).

[theonewhowaskazu]

It really depends on what you're trying to do. You can't expect us to tell you if something is "as good as" something else if you don't even tell us the intended use.

If you're trying to design an altcoin, then in my humble opinion, yes, this would be superior to Scryptcoins, just because it uses Sha (a much more tested algy) than scrypt. And sure, you do require memory, so that's a thing.

[StarfishPrime]

Please don't go inventing your own cryptography when it can be avoided.

Scrypt did the work to write up an extensive analysis of their effort, and it was reviewed by many people at great cost. And even then the result has not been totally criticism free (http://eprint.iacr.org/2013/525).

I understand that new crypto has to go through a complicated vetting process to be trusted, and there are good reasons for this. I am just curious as to why something simpler was not settled on in this case. Unnecessary complexity is not our friend.

Scrypt can be resource intensive and slow, and can appear to have unnecessary complexity, but the algorithm's slow execution speed and extensive resource requirement is actually a feature: It's far more difficult to attempt 100K password hashes in a brute force attack if each one takes 3.5s than if each one takes 3.5ms.
If you need speed and resource efficiency, scrypt is probably not your first choice anyway.