Bitcoin Forum
December 15, 2017, 05:37:31 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: SHA256 + concatenation as good as scrypt?  (Read 1533 times)
lsparrish
Jr. Member
*
Offline Offline

Activity: 31



View Profile
October 18, 2013, 05:47:10 AM
 #1

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?
1513316251
Hero Member
*
Offline Offline

Posts: 1513316251

View Profile Personal Message (Offline)

Ignore
1513316251
Reply with quote  #2

1513316251
Report to moderator
1513316251
Hero Member
*
Offline Offline

Posts: 1513316251

View Profile Personal Message (Offline)

Ignore
1513316251
Reply with quote  #2

1513316251
Report to moderator
1513316251
Hero Member
*
Offline Offline

Posts: 1513316251

View Profile Personal Message (Offline)

Ignore
1513316251
Reply with quote  #2

1513316251
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1513316251
Hero Member
*
Offline Offline

Posts: 1513316251

View Profile Personal Message (Offline)

Ignore
1513316251
Reply with quote  #2

1513316251
Report to moderator
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2366



View Profile
October 18, 2013, 07:48:34 AM
 #2

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

Bitcoin will not be compromised
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 1792

Newbie


View Profile
October 18, 2013, 02:45:00 PM
 #3

Am I missing something critical here?

Yes, Scrypt also put high pressure on CPU cache.
lsparrish
Jr. Member
*
Offline Offline

Activity: 31



View Profile
October 18, 2013, 03:49:05 PM
 #4

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
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
Legendary
*
Offline Offline

Activity: 1792

Newbie


View Profile
October 18, 2013, 05:49:13 PM
 #5

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
Sr. Member
****
Offline Offline

Activity: 448


View Profile
October 18, 2013, 09:23:53 PM
 #6

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
Sr. Member
****
Offline Offline

Activity: 359


View Profile
October 20, 2013, 09:25:49 PM
 #7

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.

                         
    ¦                     
  ¦    ¦¦¦               
¦¦  ¦¦¦¦                 
                             ¦¦  ¦¦¦¦
                          ¦ ¦¦ ¦¦¦¦                     
                         ¦¦¦¦¦¦¦¦
                        ¦¦¦¦¦¦¦
                        ¦¦¦¦¦¦
                  ¦¦¦  ¦¦¦¦¦¦
                   ¦ ¦¦¦¦¦¦

                    ¦¦  ¦ ¦¦¦¦
                    ¦¦    ¦¦¦¦
                    ¦¦  ¦ ¦¦¦¦
                   ¦¦¦  ¦ ¦¦¦¦¦
                ¦¦¦¦    ¦ ¦¦¦¦¦¦¦¦
             ¦¦¦¦¦    ¦ ¦¦ ¦¦¦¦¦¦¦¦¦¦
          ¦¦¦¦¦       ¦  ¦   ¦¦¦¦¦¦¦¦¦¦¦
        ¦¦¦¦         ¦        ¦¦¦¦¦¦¦¦¦¦¦¦
     ¦¦¦¦          ¦      ¦    ¦¦¦¦¦¦¦¦¦¦¦¦¦¦
    ¦¦¦         ¦¦         ¦   ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
   ¦¦        ¦¦         ¦¦  ¦   ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  ¦¦       ¦          ¦ ¦¦   ¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
 ¦¦¦     ¦¦          ¦   ¦    ¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
¦¦¦     ¦          ¦      ¦   ¦¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
¦¦¦    ¦        ¦¦         ¦¦  ¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
¦¦¦   ¦¦     ¦¦         ¦   ¦  ¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
¦¦¦   ¦     ¦¦         ¦¦¦   ¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
 ¦¦   ¦¦    ¦        ¦    ¦  ¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
 ¦¦    ¦   ¦        ¦¦    ¦  ¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  ¦¦    ¦  ¦¦       ¦     ¦  ¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
   ¦¦    ¦  ¦      ¦      ¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
    ¦¦¦   ¦ ¦¦     ¦¦     ¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
     ¦¦¦   ¦ ¦¦     ¦¦    ¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
       ¦¦¦¦  ¦ ¦¦    ¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
          ¦¦¦¦¦¦  ¦¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
             ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
                        ¦¦

.
TorCoin.....
¦
¦
¦
¦
  Fully Anonymous TOR-integrated Crypto
               ¦ Windows     ¦ Linux     ¦ GitHub     ¦ macOS
     ¦
     ¦
     ¦
     ¦
.
   ANN THREAD
     ¦
     ¦
     ¦
     ¦
[/center]
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!