News for hackers. Stuff that matters.
Re:Systems Design for Advanced Beginners by dreamcompiler on Tuesday July 21, 2020 @12:22AM (#23904311)
Nice tutorial! One small nitpick:

> Calculating a hash value from an input is computationally very easy, but reversing the transformation and recovering the original input from its hash value takes so much time and computing power that it is, practically-speaking, impossible.

The above is true for encryption but not for hash codes. Recovering the original input from a hash code is not just practically impossible; it's provably impossible -- even with an infinite amount of computing power -- because in general a hash code contains less information than the original text.

Re:Systems Design for Advanced Beginners by sz4kerto on Tuesday July 21, 2020 @02:22AM (#23904737)
Actually, it might be occasionally possible. Not perfectly, of course. If the input space is limited and you have other constraints on it, then you might be able to find the original text. For example, let's say your input is a 280 character long tweet, the hash is only 16 bytes long. If you find that "I AM A STABLE GENIUS" is one of the inputs that hashes to the given hash value, then you can be reasonably sure that this was the original text, given that most of the other inputs with the same hash won't be meaningful English sentences.
Re:Systems Design for Advanced Beginners by talaketu on Tuesday July 21, 2020 @03:08AM (#23904905)
I'd say the count of believable English tweets would be many orders of magnitude greater the count of 16 byte hashes, so in general we can't just find a believable tweet and declare that we found the plaintext. There would be many possible collision.

The phrase you mentioned is notable (with a slight edit) - so I suppose you mean you could index phrases by notability, then it may be tractable find tweets of notable phrases, since the number of notable phrases is relatively low.

Re:Systems Design for Advanced Beginners by lamida on Tuesday July 21, 2020 @12:38AM (#23904358)
I think the author means recovering the hash by using dictionary attacks
Re:Systems Design for Advanced Beginners by exdsq on Tuesday July 21, 2020 @01:02AM (#23904419)
You’d still have hash collisions
Re:Systems Design for Advanced Beginners by hansvm on Tuesday July 21, 2020 @03:11AM (#23904928)
Maybe not enough to matter though. If the input space is sufficiently smaller than the hash space (e.g., you aren't hashing arbitrary strings, but instead just arbitrary English words) then the probability of any hash collision that also lies in the realm of interest is vanishingly small.
Re:Systems Design for Advanced Beginners by exdsq on Tuesday July 21, 2020 @03:38AM (#23905039)
True, but that'd be very esoteric - a string input field that only accepts values from a dictionary. Although also if the input space was only these values but the input size was infinite you'd have a similar issue :P
Re:Systems Design for Advanced Beginners by hansvm on Tuesday July 21, 2020 @11:54AM (#23907871)
It'd be esoteric for a system to enforce only containing values from a dictionary, but every sentence ever spoken by anyone alive fits in a 64-bit space by a wide margin. For real-world input you could still reverse most passwords uniquely given enough time.

It's actually kind of a fun problem -- the fewer bits you have in your hash the easier it is to find _any_ collision that gives access to the current system, but the harder it is to uniquely reverse the hash into a plausible password for stuffing into other systems.

Re:Systems Design for Advanced Beginners by KMag on Tuesday July 21, 2020 @02:37AM (#23904783)
I think the author is just using imprecise language for a preimage attack.[0]

[0] https://en.wikipedia.org/wiki/Preimage_attack

Re:Systems Design for Advanced Beginners by oconnor663 on Tuesday July 21, 2020 @08:48AM (#23906401)
Information is sometimes destroyed, but we can't count on it. An algorithm like HMAC might be used to authenticate a short message. Or even if the message is long, it might also be known, so perhaps the only unknown input (the key) is short. HMAC still provides security in this case, but it's not provable-because-information-is-destroyed in the sense you're describing.
Re:Systems Design for Advanced Beginners by netsectoday on Wednesday July 22, 2020 @05:35AM (#23915356)
215D70DA68DBDC2217D13916E40F89B87DDC3DAACA99892C943E0DCC76C8C1AF68097C86CC4CB53F15BD6C3870418A1E3577A076611A5104C6D4FC33939A21FB
Re:Systems Design for Advanced Beginners by dreamcompiler on Wednesday July 22, 2020 @10:45AM (#23917573)
I said "in general".
Re:Systems Design for Advanced Beginners by netsectoday on Wednesday July 22, 2020 @01:13PM (#23919223)
> in general a hash code contains less information

That is true, but has nothing to do with your ability to use a rainbow table or dictionary attack on my hashed statement.

The specific reason why you can reverse my hash is because it's unsalted. The time-complexity of my example hash is somewhat low.

'you are wrong' is 13 characters that spans the lowercase alphabet with spaces, in all english words that can be found in a dictionary. The actual key-space is 13^10 because of the limited characters I used, but when creating a rainbow-table it would probably take a key-space of 13^27 because you don't know the specific characters I'm using. (There are 13 characters in my statement, then there are 26 lower-case letters in the alphabet - plus space - which makes 27... 13^27)

Now, if I followed general op-sec suggestions I would have added a salt to my statement, so the process looks like SHA512('you are wrong' + '7aomAxgeVjAvyDXGrdmNJNKuuiumYbkG') which gives you the possible key-space of 45^63. Also, the salt should be something not found in a dictionary.

2812CDA67BF0EA2D5FE125C2637466FA9A81C12AE9D101771C581DB87EBEB05D7724C9DCFBC6F905B99F9737948543EC64CAC5D89C785125DDA2E3297214CC58

On the upper-side of the estimate there are 10^82 atoms in the universe. There are about 14^103 possible solutions to that salted hash above, with many possible collisions. Good luck with creating a database that needs more rows than available atoms, or waiting for a brute-force to complete on that hash, then sorting through the collisions. This is the "impossible" reversible hash you are talking about.

If you are interested in this topic and would like to do this in your code: use the HMAC function which is built for this, or specifically for passwords use bcrypt/blowfish because that algorithm is designed to run slowly (brute force protection).