flat assembler
Message board for the users of flat assembler.

 Index > Heap > md5 of md5, sha1 of sha1, hash of hash
Author
sleepsleep

Joined: 05 Oct 2006
Posts: 8885
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
i am curious, and hopefully i could confirm in this life time,

does hash of hash will loop every possible hash or maybe just part of possible hash output.

eg.

md5 of 00000000000000000000000000000000
is cd9e459ea708a948d5c2f5a6ca8838cf

then we continue md5 the output and we get
521214d453fe36d20ac094dec9916bbd

and repeat, until we get back 00000000000000000000000000000000

what i thought could be or maybe possible results.

1. the process loop through every possible md5 value, and we find an input to output 00000000000000000000000000000000

2. the process loop part of possible md5 value,

3. the process break a apart and find a pair to already md5 output
eg. A > B > C > D > E ....... X > C > D > E > ....

is that possible in 2015, with current available technology,
to store all possible md5 or sha1 hash pair values?

might be interesting too to see the distribution of each char output to what char, so maybe we could get some sort of hint.

because maybe after a few millions input, we could formulate a different formula to get 80 or 90 percent possible output. i guess.
30 Jan 2015, 21:54
redsock

Joined: 09 Oct 2009
Posts: 357
Location: Australia
redsock
Quoting the same question on quora, Robert Neuhaus, Software Engineer at Google said:

"It must be cyclic, the domain is finite. I'd venture that no one knows the shortest cycle and that it's probably similar to knowing how to generate collisions."

I think he covered it one hit.
30 Jan 2015, 22:23
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
sleepsleep:

We don't know if every possible value is reachable for anything but the most simple hashes.

Even for MD5 there are no storage or computation resources available today that could store or compute all possible values. But note that there is no such thing as "pair values" in a hash because it is a many-to-one relationship.
30 Jan 2015, 23:13
Bargest

Joined: 09 Feb 2012
Posts: 79
Location: Russia
Bargest
Quote:
is that possible in 2015, with current available technology,
to store all possible md5 or sha1 hash pair values?

MD5 is 16 bytes long (128-bit). Numebr of possible md5's is 2^128.
2^64 = 18446744073709551616. 2^128 = 2^64*2^64 = 3,4e+38.
Each MD5->MD5 pair will contain at least 1 md5 (second can be calculated as offset of this md5 on disk), so it will be at least 16 bytes long. Total space needed is 5,4e+39 bytes = 4951760157141521099596496896 Terabytes. If you have nearly 10^27 10-terabyte disks, you surely can store all md5->md5 pairs.
31 Jan 2015, 11:31

Joined: 25 Nov 2013
Posts: 216
Location: %x
for get char save it in unicode
31 Jan 2015, 19:54
cod3b453

Joined: 25 Aug 2004
Posts: 619
cod3b453
In the case of MD5 there are known block collisions so it can't be totally cyclic:

http://marc-stevens.nl/research/md5-1block-collision/
31 Jan 2015, 22:42

Joined: 25 Nov 2013
Posts: 216
Location: %x
wow thanks this is useful to know
31 Jan 2015, 22:56
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
cod3b453 wrote:
In the case of MD5 there are known block collisions so it can't be totally cyclic:

http://marc-stevens.nl/research/md5-1block-collision/
All hashes have collisions by definition. Actually finding a collision is a different problem that leads to people claiming the hash is "broken". So in principle all hashes are broken and are merely waiting for someone to find a collision.
01 Feb 2015, 09:13
cod3b453

Joined: 25 Aug 2004
Posts: 619
cod3b453
revolution wrote:
cod3b453 wrote:
In the case of MD5 there are known block collisions so it can't be totally cyclic:

http://marc-stevens.nl/research/md5-1block-collision/
All hashes have collisions by definition. Actually finding a collision is a different problem that leads to people claiming the hash is "broken". So in principle all hashes are broken and are merely waiting for someone to find a collision.
Not quite. Yes, in practice, the domain is larger than the range so there have to be collisions but here we're considering the case where they are the same. A cyclic series could exist if the function is total injective (perfect hash function which by definition has no collisions) and so finding a such a collision proves this is not the case.
01 Feb 2015, 11:27
sleepsleep

Joined: 05 Oct 2006
Posts: 8885
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
Harvard cracks DNA storage, crams 700 terabytes of data into a single gram
http://www.extremetech.com/extreme/134672-harvard-cracks-dna-storage-crams-700-terabytes-of-data-into-a-single-gram

exciting technology in coming years,
04 Feb 2015, 19:47
DOS386

Joined: 08 Dec 2006
Posts: 1901
DOS386
> In the case of MD5 there are known block
> collisions so it can't be totally cyclic:
> http://marc-stevens.nl/research/md5-1block-collision/

WOW!!! 2 blocks per 64 Octet's differ by just 2 bits ... and same MD5 !!!

But surely every hash algo is cyclic ... but seems that nobody found an MD5 cycle yet.
09 Feb 2015, 09:16
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
DOS386 wrote:
But surely every hash algo is cyclic ... but seems that nobody found an MD5 cycle yet.
Yes. By the fact that the output is fixed length so there will always be at least one cycle, and possibly more than one cycle depending upon the hash function and inputs used.
09 Feb 2015, 09:21
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum