[The MD5 algorithm] takes as input a message of arbitrary length and produces as output a 128-bit "fingerprint" or "message digest" of the input. It is conjectured that it is computationally infeasible to produce two messages having the same message digest, or to produce any message having a given prespecified target message digest.
It's therefore computationally infeasible for you to produce a message that has this MD5 fingerprint.
So you're saying that if you get access to ewx's machine, you can md5sum all the files on it, and find the one that produces the same signature as the one in this post, in which case you can read the contents of that file and find out his prediction?
That doesn't seem to be the same as decoding the signature to me.
No, what I'm saying is, that if I can make a plausible guess at the length of ewx's file, and the contents (probably ASCII text) then the search domain decreases in size dramatically.
Ah, gotcha. So if for example you know it's 1024 bytes long, you just md5sum all 256^1024 possible files till you get one that has the same signature. And if you know it's ASCII in gramatically correct English you have an even smaller search space.
Not so. Suppose the file is (say) 60 bytes long, and suppose your plausible guess at its contents limits each character to (say) 60 possibilities. I think those aren't too unreasonable; if you attempt to invoke dependency between characters (because the file is assumed to be intelligible English text) then I'll counter with the observation that any sensible player of this game will have included some random goop in their file along with the text, to defeat just this strategy.
So. If you know the file length is 60 bytes, then you have 60^60 possibilities. But what if you know it's up to 60 bytes? Well, then you have 60^0 + 60^1 + 60^2 + ... + 60^60 possibilities. But the interesting thing is that 60^0 + ... + 60^59 comes to (60^60 - 1)/(60 - 1). In other words, the number of possible strings with length strictly less than 60 is 1/59 times the number of possible strings with length exactly 60. This doesn't seem to me to be a dramatic reduction in the search space! You might just as well start from length zero and generate all possible strings until you hit the target md5sum; the longer the target string actually is, the smaller a proportion of your search time you'll turn out to have wasted by trying things of the wrong length.
any sensible player of this game will have included some random goop
It refers to things I think are happening or starting to happen now. It's a bit of a stab in the dark anyway and I'm feeling even less sure about it now than I was when I posted.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
no subject
no subject
(NB: Joking!)
no subject
It's therefore computationally infeasible for you to produce a message that has this MD5 fingerprint.
no subject
For instance:
And you ought to be able to discover what the contents of /tmp/file are without *too* much effort.
no subject
That doesn't seem to be the same as decoding the signature to me.
no subject
no subject
Well, what are you waiting for?
no subject
So. If you know the file length is 60 bytes, then you have 60^60 possibilities. But what if you know it's up to 60 bytes? Well, then you have 60^0 + 60^1 + 60^2 + ... + 60^60 possibilities. But the interesting thing is that 60^0 + ... + 60^59 comes to (60^60 - 1)/(60 - 1). In other words, the number of possible strings with length strictly less than 60 is 1/59 times the number of possible strings with length exactly 60. This doesn't seem to me to be a dramatic reduction in the search space! You might just as well start from length zero and generate all possible strings until you hit the target md5sum; the longer the target string actually is, the smaller a proportion of your search time you'll turn out to have wasted by trying things of the wrong length.
any sensible player of this game will have included some random goop
no subject
no subject
When?
no subject
no subject
(Any hints as to the time frame or probability, just for the curious?)
no subject
no subject