SHA256 + concatenation as good as scrypt?

StarfishPrime

sr. member

Activity: 358

Merit: 250

Quote from: lsparrish on October 18, 2013, 10:49:05 AM

Quote from: gmaxwell on October 18, 2013, 02:48:34 AM

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.

theonewhowaskazu

sr. member

Activity: 448

Merit: 250

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.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: lsparrish on October 18, 2013, 10:49:05 AM

Quote from: Come-from-Beyond on October 18, 2013, 09:45:00 AM

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

lsparrish

newbie

Activity: 31

Merit: 0

Quote from: gmaxwell on October 18, 2013, 02:48:34 AM

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.

Quote from: Come-from-Beyond on October 18, 2013, 09:45:00 AM

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

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: lsparrish on October 18, 2013, 12:47:10 AM

Am I missing something critical here?

Yes, Scrypt also put high pressure on CPU cache.

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: lsparrish on October 18, 2013, 12:47:10 AM

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

lsparrish

newbie

Activity: 31

Merit: 0

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?

Topic: SHA256 + concatenation as good as scrypt? (Read 1645 times)