Timeline for Is it possible to store N bits of unique combinations, in N-1 bits? If not; why does MD5 get reprimanded for collissions?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2021 at 18:00 | history | tweeted | twitter.com/StackSoftEng/status/1367172982662197256 | ||
| Feb 27, 2021 at 18:24 | answer | added | Jörg W Mittag | timeline score: 6 | |
| Feb 27, 2021 at 13:00 | answer | added | gnasher729 | timeline score: 4 | |
| Feb 27, 2021 at 12:55 | comment | added | Christophe | It is not possible to store an independent value in a set of 16-combinations within 3 bits. It may however be possible to store multiple values in a set of 16-combinations in less than 4 bits in average. If it wouldn't, there would be no compression. | |
| Feb 27, 2021 at 9:33 | comment | added | Doc Brown | You are looking for a proof of the pigeon hole principle?Here is one at math.stackexchange | |
| Feb 26, 2021 at 20:10 | vote | accept | Anon | ||
| Feb 26, 2021 at 20:07 | answer | added | Euphoric | timeline score: 15 | |
| Feb 26, 2021 at 20:02 | comment | added | Robert Harvey | I don't understand what you just said. | |
| Feb 26, 2021 at 19:49 | comment | added | Anon | @AndrewHenle you are omitting though the fact that I said, "Of a particular size". Meaning that all the different combinations of a megabyte, is not infinite, and inside a hash, will generate collisions. | |
| Feb 26, 2021 at 19:35 | comment | added | Andrew Henle | @Akiva That's just the pigeonhole principle. There are a finite number of values for any hash that's a fixed size. There's an infinite number of different data streams that could be fed into any hash algorithm. | |
| Feb 26, 2021 at 19:35 | comment | added | John Wu | True, all hashes have collisions, but cryptographic hashes have collision resistance. If you have a cryptographically sound hash, the only way to create a plaintext that matches the hash is via brute force. With MD5, there are shortcuts that allow you to create it systematically and in less time, making collision attacks not just possible but feasible. | |
| Feb 26, 2021 at 19:33 | review | Close votes | |||
| Mar 3, 2021 at 3:03 | |||||
| Feb 26, 2021 at 19:27 | comment | added | Anon | @JohnWu Thanks for verifying that. I expanded the question a bit, as I was initially investigating why MD5 in particular was reprimanded for generating collisions. Given what you just laid out however, it is not possible for any hash to not generate collisions. | |
| Feb 26, 2021 at 19:25 | history | edited | Anon | CC BY-SA 4.0 |
expanded it a bit
|
| Feb 26, 2021 at 19:10 | comment | added | John Wu | To store N bits of information, and the information does not contain noise (unneeded bits) or equivocation (bits that change together), you need N physical bits of storage. This is basic to information theory. | |
| Feb 26, 2021 at 19:04 | history | asked | Anon | CC BY-SA 4.0 |