Timeline for Memory-expensive hash from an array of hashes?
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/
|
|
| Dec 8, 2014 at 4:00 | history | edited | e-sushi | CC BY-SA 3.0 |
Fixed some minor typos and linked up the referred comment.
|
| Dec 7, 2014 at 23:19 | comment | added | John Meacham | You still only have a polynomial increase but with a bigger factor, if you could calculate any bit before in 'n^2' time, you now have 'n^2' (to reproduce any bit) * nb (where b is the number of bytes in a hash) so bn^3. I also worry that any repeating pattern like that can be taken advantage of. using the result of the full hash to indicate the skip patterns for the next generation and so forth a few times may be better. I still think it may be polynomial, but with an exponential relationship to the number of 'rounds', make the skip pattern include previous rounds for more memory use. | |
| Dec 7, 2014 at 16:45 | history | edited | Behrooz | CC BY-SA 3.0 |
added 58 characters in body
|
| Dec 7, 2014 at 16:40 | comment | added | Behrooz | @JohnMeacham wow, really nice. please see the edit. | |
| Dec 7, 2014 at 16:39 | history | edited | Behrooz | CC BY-SA 3.0 |
patch?
|
| Dec 7, 2014 at 13:53 | answer | added | Alexey Vesnin | timeline score: 0 | |
| Dec 7, 2014 at 13:33 | comment | added | John Meacham | With that scheme you can reduce your memory usage to a small constant by trading a polynomial increase in CPU time for it. by just squaring the number of hash evaluations, you just start from the end and work backwards (recalculating intermediate hashes) building up your hash along the way. You can split the difference by selecting intermediate hashes like a binary tree requiring only O(n * log n) hashs and O(log n) memory. | |
| Dec 7, 2014 at 11:36 | history | edited | Behrooz | CC BY-SA 3.0 |
edited body
|
| Dec 7, 2014 at 5:31 | comment | added | Richie Frame | I would suggest that you make the array size at least 4X the size of the total largest L2 cache on whatever device you are trying to defend against (including in the future), which is currently 2MB (Maxwell), so a 16-32MB minimum array | |
| Dec 7, 2014 at 5:06 | comment | added | Richie Frame | scrypt has some issues, and has a complex implementation, there is great demand for alternatives. I use this exact method with 16 round SHA-256 in an experimental password hashing scheme, it has provable properties, but bad implementation can lead to information leakage | |
| Dec 6, 2014 at 19:44 | history | tweeted | twitter.com/#!/StackCrypto/status/541317354043768832 | ||
| Dec 6, 2014 at 19:43 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
tite; formatting
|
| Dec 6, 2014 at 15:24 | vote | accept | Behrooz | ||
| Dec 6, 2014 at 14:19 | answer | added | Maarten Bodewes♦ | timeline score: 3 | |
| Dec 6, 2014 at 12:42 | comment | added | Thomas M. DuBuisson | Why are you making your own system instead of using scrypt or something similar and well analyzed? | |
| Dec 6, 2014 at 11:48 | review | First posts | |||
| Dec 6, 2014 at 19:43 | |||||
| Dec 6, 2014 at 11:43 | history | asked | Behrooz | CC BY-SA 3.0 |