Bitcoin Forum
August 21, 2018, 07:23:13 AM *
News: Latest stable version of Bitcoin Core: 0.16.2  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: SHA256 + concatenation as good as scrypt?  (Read 1538 times)
lsparrish
Jr. Member
*
Offline Offline

Activity: 31
Merit: 0



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

Posts: 1534836193

View Profile Personal Message (Offline)

Ignore
1534836193
Reply with quote  #2

1534836193
Report to moderator
1534836193
Hero Member
*
Offline Offline

Posts: 1534836193

View Profile Personal Message (Offline)

Ignore
1534836193
Reply with quote  #2

1534836193
Report to moderator
Goat says: "Bitcoin is NOT Illegal in Thailand. There is no law against Bitcoin in Thailand!"
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1534836193
Hero Member
*
Offline Offline

Posts: 1534836193

View Profile Personal Message (Offline)

Ignore
1534836193
Reply with quote  #2

1534836193
Report to moderator
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2478
Merit: 1384



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: 2044
Merit: 1007

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
Merit: 0



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: 2044
Merit: 1007

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
Merit: 250


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: 358
Merit: 250


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!