I've been doing some preliminary research in the area of message digests. Specifically collision attacks of cryptographic hash functions such as MD5 and SHA-1, such as the Postscript example and X.509 certificate duplicate.From what I can tell in the case of the postscript attack, specific data was generated and embedded within the header of the postscript (which is ignored during rendering) which brought about the internal state of the md5 to a state such that the modified wording of the document would lead to a final MD equivalent to the original. The X.509 took a similar approach where by data was injected within the comment/whitespace of the certificate.Ok so here is my question, and I can't seem to find anyone asking this question:Why isn't the length of ONLY the data being consumed added as a final block to the MD calculation?In the case of X.509 - Why is the whitespace and comments being taken into account as part of the MD?Wouldn't a simple processes such as one of the following be enough to resolve the proposed collision attacks:$MD(M + |M|) = xyz$$MD(M + |M| + |M| * magicseed_0 +...+ |M| * magicseed_n) = xyz$where :M : is the message|M| : size of the message in bitsMD : is the message digest function (eg: md5, sha, whirlpool etc)xyz : is the pairing of the acutal message digest value for the message M and |M|. <M,|M|>$magicseed_{i}$: Is a set of random values generated with seed based on the internal-state prior to the size being added.'+' : is a concatentation operation A+B+C = ABCThis technqiue should work, as to date all such collision attacks rely on adding more data to the original message.In short, the level of difficulty involved in generating a collision message such that:It not only generates the same MDBut is also comprehensible/parsible/compliantand is also the same size as the original message,is immensely difficult if not near impossible. Has this approach ever been discussed? Any links to papers etc would be nice.Further Question: What is the lower bound for collisions of messages of common length for a hash function H chosen randomly from U, where U is the set of universal hash functions ?Is it $1/N$ (where N is $2^{|M|}$) or is it greater? If it is greater, that implies there is more than 1 message of length |M| that will map to the same MD value for a given H.If that is the case, how practical is it to find these other messages? bruteforce would be of $O(2^N)$, is there a method of time complexity less than bruteforce?Links:Postscript: http://www.schneier.com/blog/archives/2005/06/more_md5_collis.htmlX.509: http://www.win.tue.nl/~bdeweger/CollidingCertificates/Note: This question is NOT as easy as it seems. Please read it very carefully and make sure you have understood exactly what is being asked. The answer will require understanding of martingales and distribution ensembles. If you are unsure what these are or how they apply to this particular problem then please do not post answers. Prior knowledge of this class of attack is required, please access the links above and the following: csse question. Please DO NOT focus on answers that relate to generating messages of length different from the original message as any such solution is invalid.
Collision Attacks, Message Digests and a Possible solution
cr.crypto security;hash function