# The identity hash **URL:** \ **Category:** Factual Questions\ **Created:** [September 4, 2008, 9:22am UTC](https://boards.straightdope.com/t/the-identity-hash/461964 "2008-09-04T09:22:43Z")\ **Posts on this page:** 13\ **Page:** 1
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [September 4, 2008, 9:22am UTC](https://boards.straightdope.com/t/the-identity-hash/461964/1 "2008-09-04T09:22:43Z")
Is there a string which, when hashed with md5, returns itself? Same for SHA-1 and all the other hash functions. I tried googling for it but I couldn’t find anything. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [September 4, 2008, 9:42am UTC](https://boards.straightdope.com/t/the-identity-hash/461964/2 "2008-09-04T09:42:50Z")
What a fascinating question (to which I don’t have an answer) Thinking about a practical way to discover such a thing - it would be fairly easy to set up a brute-force test on a random seed string and keep feeding the result back into the input, keeping track of the results - One other possibly interesting scenario that might arise here is to get stuck in a loop - where a small set of results lead to each other in turn, then back to the first one. ---
**Author:** ![kferr](https://avatars.discourse-cdn.com/v4/letter/k/71e660/32.png) [@kferr](https://boards.straightdope.com/u/kferr)\ **Post date:** [September 4, 2008, 11:21am UTC](https://boards.straightdope.com/t/the-identity-hash/461964/3 "2008-09-04T11:21:13Z")
MD5 produces a 128 bit result so you’d have to take at each possible 128 value, hash it, and compare the input to the output. Assuming a single computer doing 1000 checks/second, it would approx 10.8e28 years to find all possible collisions. ---
**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\ **Post date:** [September 4, 2008, 12:19pm UTC](https://boards.straightdope.com/t/the-identity-hash/461964/4 "2008-09-04T12:19:31Z")
**Mangetout** : You’ve just given the naïve ‘solution’ to the Halting Problem (to wit: run it and see what happens). Turing is laughing up his sleeve at you. 😉 **Shalmanese** : Perfect hash functions (a mathematical abstraction real hash functions attempt to emulate) are allowed to have fixed points, as I understand it, and knowing about them tells you no more about the function than knowing any other arbitrary input-output pair. The magic of a perfect hash function is that every input from the arbitrary-sized domain always has the same output within the fixed range, but given an output value it’s still impossible to calculate any input values that map to it. Caching arbitrary numbers of input-output pairs is not even helpful when the input value you desire isn’t already in your cache. Needless to say we still haven’t produced such a beast, but we can use the abstraction to prove weaknesses in other parts of the system ("Even if the hash function were perfect, it still breaks… "). Finding an easy way to answer this for real hash functions would involve breaking those functions, because otherwise the search (as per **Mangetout** ) may never end. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 4, 2008, 3:06pm UTC](https://boards.straightdope.com/t/the-identity-hash/461964/5 "2008-09-04T15:06:58Z")
If you’re Googling, use the phrase “fixed point” rather than identity (as **Derleth** alluded to). ---
**Author:** ![Bytegeist](https://avatars.discourse-cdn.com/v4/letter/b/9dc877/32.png) [@Bytegeist](https://boards.straightdope.com/u/Bytegeist)\ **Post date:** [September 4, 2008, 3:21pm UTC](https://boards.straightdope.com/t/the-identity-hash/461964/6 "2008-09-04T15:21:53Z")
> [@Derleth](#): > > **Mangetout** : You’ve just given the naïve ‘solution’ to the Halting Problem (to wit: run it and see what happens). The brute-force search will halt eventually, assuming you’re methodical about it. The longest possible cycle is 2[sup]128[/sup]. If there are any MD5 cycles, they’re all limited to that — and, there can only be a finite number of them in total. Still, I don’t think I’ll wait around for the brute-force search to finish. Or even make much of a start. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [September 4, 2008, 8:48pm UTC](https://boards.straightdope.com/t/the-identity-hash/461964/7 "2008-09-04T20:48:27Z")
> [@](#): > > The brute-force search will halt eventually, assuming you’re methodical about it. The longest possible cycle is 2[sup]128[/sup]. Likewise, you can brute-force the halting problem, for a computer only slightly smaller than the one you’re using. You just can’t use a computer to solve its _own_ halting problem. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [September 4, 2008, 9:00pm UTC](https://boards.straightdope.com/t/the-identity-hash/461964/8 "2008-09-04T21:00:41Z")
> [@Bytegeist](#): > > The brute-force search will halt eventually, assuming you’re methodical about it. The longest possible cycle is 2[sup]128[/sup]. If there are any MD5 cycles, they’re all limited to that — and, there can only be a finite number of them in total. > > Still, I don’t think I’ll wait around for the brute-force search to finish. Or even make much of a start. In case it wasn’t apparent, I wasn’t proposing a brute force search as any kind of efficient answer to the OP’s question - merely a thought experiment. I think I’m right in saying that all possible cycles cannot add to more than 2[sup]128[/sup] steps either - or some of them would intersect (and would therefore be part of the same cycle) ---
**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\ **Post date:** [September 4, 2008, 10:22pm UTC](https://boards.straightdope.com/t/the-identity-hash/461964/9 "2008-09-04T22:22:37Z")
> [@ultrafilter](#): > > If you’re Googling, use the phrase “fixed point” rather than identity (as **Derleth** alluded to). Note that there is also a [‘fixed point attack’ on hash functions, which doesn’t apply here](http://deadhacker.com/2006/02/22/formal-aspects-of-mobile-code-security-chapter-5/): > [@](#): > > A Fixed Point Attack involves finding a random block whose properties allow the attacker to insert the block into the original message without changing the final hash. As a result two different messages are created with the same hash (the original message and the original+the special block). It’s a break in the function, but it isn’t what you’re looking for here. **Mangetout** : OK, you’re right. In my defense, though, you did say ‘practical’. I don’t think waiting around for the generation of all possible 128-bit numbers is practical given the current methods of designing computer hardware. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [September 4, 2008, 10:27pm UTC](https://boards.straightdope.com/t/the-identity-hash/461964/10 "2008-09-04T22:27:21Z")
Sure - no problem - I was thinking about how to do it. I wasn’t thinking of doing it though. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [September 4, 2008, 10:31pm UTC](https://boards.straightdope.com/t/the-identity-hash/461964/11 "2008-09-04T22:31:09Z")
> [@Mangetout](#): > > One other possibly interesting scenario that might arise here is to get stuck in a loop - where a small set of results lead to each other in turn, then back to the first one. Since the range is finite, everything must eventually get stuck in a loop. That loop might be kind of large. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [September 4, 2008, 10:33pm UTC](https://boards.straightdope.com/t/the-identity-hash/461964/12 "2008-09-04T22:33:48Z")
> [@Lance\_Turbo](#): > > Since the range is finite, everything must eventually get stuck in a loop. > That loop might be kind of large. Can’t help wondering if there would be any kind of pattern to the distribution and layout of the loops… ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [September 5, 2008, 12:11am UTC](https://boards.straightdope.com/t/the-identity-hash/461964/13 "2008-09-05T00:11:36Z")
> [@Mangetout](#): > > Can’t help wondering if there would be any kind of pattern to the distribution and layout of the loops… I’ve been thinking about this. Picture a bunch of rooted trees in the graph theoretical sense where all the edge are directed toward the root. The trees can come in all shapes and sizes. Now attach each root node to a directed cycle. There are a bunch of these cycles in many lengths to choose from. Your hash is one such picture like this, but I’m not sure which one, and I don’t expect any additional structure than what I’ve given to be apparent, but I’m willing to be wrong about that.