Timeline for Looking for cryptographic secure hash algorithm(s) that produces identical root hash for differently sliced hash list
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 30, 2011 at 10:58 | comment | added | David Cary | @D.W. Good points. In the best case -- a segment of length 2^n blocks, and starts and ends on a boundary that is a multiple of 2^n blocks -- the user only needs to send 1 hash with (the encrypted version of) that segment to the server. In the worst case -- a segment of of length (2^n - 1) blocks -- the user needs to send O(log k) hashes, as you said, but the server doesn't need to "retain" any of them -- once it has all the hashes for all parts of the file, the server can calculate the one root hash and then discard all the other hashes. | |
| Aug 28, 2011 at 7:56 | comment | added | D.W. | I don't think this answer fully solves the problem of ensuring that you can compute the root hash from the segment hashes, regardless of how the file is partitioned into segments. In this scheme, it's not enough to retain a single hash of the segment: one has to retain O(log k) hashes. This has performance implications, and may also have security implications, potentially making it easier to guess the contents of part of a segment given the hash information for that segment. | |
| Aug 24, 2011 at 11:34 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Added back the size of the partial hashes at step 6
|
| Aug 24, 2011 at 0:08 | comment | added | fgrieu♦ | @Paŭlo Ebermann : 2^n was a leftover of the original version of my answer where the superblock size was 512*2^n bits rather than 512*n now. Now I have started a rewrite of the whole thing, as the earlier description was wrong. This is tricky and I wish I could just link to a reference (thanks for pointing Skein), or leave it to someone else to write the answer! | |
| Aug 24, 2011 at 0:06 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Reintroduced discussion on overhead.
|
| Aug 24, 2011 at 0:02 | comment | added | Paŭlo Ebermann | Look at the description in the Skein specification. It does not show distribution to multiple "parties", but multiple processors. | |
| Aug 23, 2011 at 23:56 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Rewrite, remove details
|
| Aug 23, 2011 at 23:26 | comment | added | user12889 | Thanks for the very detailed answer. I'll have to do some thinking if I can apply it to my use case. I'll add the use case to the questions as well to make it more specific. | |
| Aug 23, 2011 at 14:04 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Fix more formulas using parameter n (formerly 2^n)
|
| Aug 23, 2011 at 11:28 | comment | added | Paŭlo Ebermann | Okay, now it looks better. Some details: Why do you do 2^n hashes in step 3? I would think n should be enough. Why do you have this special-casing for the last block? | |
| Aug 23, 2011 at 11:20 | comment | added | David Schwartz | You can populate the tree any way you want. So long as the final tree is the same in all cases, the hashed output will be the same. This generally solves the real problem people have when they ask the question asked here. Skein has a specific mode for this. | |
| Aug 23, 2011 at 11:19 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Explain why it works. Detail what happens for the last hash.
|
| Aug 23, 2011 at 10:54 | comment | added | Paŭlo Ebermann | This is a nice description of distributed tree hashing, but I fail to see how this helps for "independently of how we chop up the file, we'll get the same results" - you are chopping it up the same way each time, don't you? | |
| Aug 23, 2011 at 8:24 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Fix link.
|
| Aug 23, 2011 at 8:19 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Simplified parameterisation: n does not need to be a power of 2. Gave overhead.
|
| Aug 23, 2011 at 7:52 | history | answered | fgrieu♦ | CC BY-SA 3.0 |