0
$\begingroup$

Take a sequence of byte buffers, hash each of them, interpret the hash digests as square matrices with 8-bit unsigned int elements, and (matrix) multiply them in order. Define the final matrix to be the "hash" of the list of elements.

This definition has some useful properties. In particular, the associative property of matrix multiplication enables calculating the list-hash of the concatenation of two lists by calculating each list's hash independently and then reducing them by multiplication to get the final list-hash. This works with any arbitrary partitioning. Non-commutativity provides that different element orders create a different hash for the list, as one would expect for a list.

(I explore this definition in more detail including working code samples in a python jupyter notebook that I published entitled Merklist. You can also play with it yourself on Google Colab, and add hypothes.is annotations on the post for general feedback. I can lift detail from there to this question if needed.)

Question

  1. Is this definition resistant to preimage attacks? Stated another way, is it possible to select a sequence of elements that results in an arbitrary target list hash?

Note that the elements must exist, so the element digests that go into the list-hash have preimage resistance based on the underlying hash function (which we can assume holds in the scope of this question). So really the question becomes: Can the order or presence of these hash digests be used to arbitrarily alter the contents of the final matrix? For example, can you generate a sequence of elements that produces a list-hash that is the zero matrix? (Hitting a zero matrix means game over, afaict.)

I did some searching and didn't find answers to any of these questions, though I suspect that could be due as much to my ignorance of the correct terminology as to the non-existence of the answers.

$\endgroup$
9
  • $\begingroup$ BTW: I just tried it; when I hashed a sequence of circa 3000 different (not maliciously chosen) preimages together, the result was the all-zero matrix. $\endgroup$
    – poncho
    Jul 9 at 20:42
  • $\begingroup$ Whelp it looks like my "didn't do his homework" is showing. How embarrassing 😬 Guess I'll have to try again with $GF(256)$, and maybe test it a bit more carefully. $\endgroup$
    – infogulch
    Jul 10 at 0:26
  • $\begingroup$ I suspect that, while $GF(256)$ would be considerably better, even then if you need to exclude noninvertable matrices, a large enough series will still end up as all 0's - it just might take perhaps a million elements, rather than just 3,000. $\endgroup$
    – poncho
    Jul 10 at 2:37
  • $\begingroup$ You think? I feel like if candidate entries are restricted to invertible matrices only that should fix it. Take this example: $X A B C C^{-1} B^{-1} A^{-1}$; this should always result in $X$ again, no matter how long the initial $ABC$ sequence. Like, if it didn't then one or more of the matrices would not be invertible by definition. No? I feel like the biggest problem is going to be finding an invertible matrix for each possible entry in reasonable time. $\endgroup$
    – infogulch
    Jul 10 at 4:33
  • $\begingroup$ @poncho I just tried it with $GF(256)$ matrix elements and it still seems fine after 10M entries. Soon I'll post another question like this one but with the $GF(256)$ formulation instead. $\endgroup$
    – infogulch
    Jul 14 at 14:21
1
$\begingroup$

For example, can you generate a sequence of elements that produces a list-hash that is the zero matrix?

Yes; the most obvious way is to find a buffer that hashes to a matrix with all $n^2$ matrix elements even; replicate that buffer 8 times, and you'll get a product that's all zeros.

This takes an expected $2^{n^2}$ work to find such a buffer; for $n=8$, this is plausible.

It could likely be improved; by looking at pairs of noninvertible matrices, it would appear plausible that, with considerably less work than $2^{64}$, you could find two whose product has all elements even (and in which case the above observation would apply).

$\endgroup$
3
  • $\begingroup$ That makes a lot of sense. To clarify, is this caused by my choice of ring (256) which has factors of 2? Do you think this could be improved by choosing a prime ring (say, 257)? $\endgroup$
    – infogulch
    Jul 9 at 17:41
  • 1
    $\begingroup$ @infogulch: or $GF(2^8)$? Well, it would help, but not all that significantly; one still has a good probability (probability circa 1/256 per attempt) of finding noninvertible matrices; it looks plausible that you could glue them together to find products of decreasing rank, resulting in the all 0 matrix. Actually, my original answer was going to be this, until I realized that the 'all lsbits 0' answer was considerably easier to justify. Still, if you did use a field such as $GF(256)$ or $GF(257)$, and deliberately skipped (using rejection sampling) noninvertible matrices, that might work $\endgroup$
    – poncho
    Jul 9 at 17:45
  • $\begingroup$ Thanks for the pointer to Galois fields and invertible matrices. I had considered that invertible matrices might be a nice-to-have, but they're probably a requirement for this to work and not result in degenerate cases like a zero matrix. $\endgroup$
    – infogulch
    Jul 9 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.