To view parent comment, click here.

To read all comments associated with this story, please click here.

It is actually rather easy to correlate bits for a single SHA1/2 round, such that one can derive the internal state of the hash function from the output bits. Hash/crypto functions are routinely cracked for a limited number of rounds.

But when the process is repeated a sufficient number of rounds, there is no record of which round(s) are responsible for changing a bit. All traces of the original bits are diffused and all that remains is unintelligible entropy. Algebraic solutions become exponentially complex and offer no benefit over brute force scanning. (As always, we're assuming the hash has no mathematically exploitable weaknesses).

So when calculating a hash, a function that's relatively easy to reverse in itself is typically applied a large number of times on the incoming data (data -> hash 1 -> hash 2 -> hash 3...) so that the results are not exploitable algebraically anymore ?

I don't know if it's similar, but it's certainly an analogy which I can get

I'm curious at a high level, but I don't really feel like reading long papers.

It's not necessarily so long. The course only lasts 4 weeks (1/3 of the usual duration in France) and includes stuff which you probably won't care about concerning experimental implementations of quantum information. It's meant to be an introduction to the subject, not one of the central parts of my Master's.

Well, not even left college yet and I already read much less than I used to when entering it. In my case, I prefer to believe that it's because I've exhausted the very small interesting content of the "science" shelves of the book shop next to the university. I only find a subject which I'm fascinated by from time to time, the rest of my book purchases are just reference books on a given subject for later...

I'd still need to learn the mathematics anyways.

What I meant with this sentence is that you probably already know a lot of the "information theory" part. Just need to get used to a new form of logic (I think I've read somewhere that quantum computers cannot compute operations which destroy information, like "AND" or "OR", and thus require use of new logic gates and reasoning).

Neolander,

"So when calculating a hash, a function that's relatively easy to reverse in itself is typically applied a large number of times on the incoming data"

I can't say for sure that this is true of all hash functions, but it is of the SHA variants (and many block ciphers as well). Keep in mind that a major design goals for these functions is that they run well on ordinary 32bit CPUs where it'd be relatively difficult to achieve sufficient diffusion using standard opcodes in one pass.

"Just need to get used to a new form of logic (I think I've read somewhere that quantum computers cannot compute operations which destroy information, like AND or OR, and thus require use of new logic gates and reasoning)."

Yep, that's the stuff I need to learn about. I have no excuse not to learn it (other than time).

[deleted rambling personal story]

Member since:

2011-01-28

Neolander,

"I don't get how it is possible to create a hash function and publicly distribute it, in a way that mathematicians are not able to find collisions just by studying the form of the hash function itself."

This has to do with "diffusion".

It is actually rather easy to correlate bits for a single SHA1/2 round, such that one can derive the internal state of the hash function from the output bits. Hash/crypto functions are routinely cracked for a limited number of rounds.

But when the process is repeated a sufficient number of rounds, there is no record of which round(s) are responsible for changing a bit. All traces of the original bits are diffused and all that remains is unintelligible entropy. Algebraic solutions become exponentially complex and offer no benefit over brute force scanning. (As always, we're assuming the hash has no mathematically exploitable weaknesses).

This may be similar (or not) to dropping a pebble in a pool and then backtracking the point at which the pebble was dropped by observing the waves. As the waves bounce against the edge of the water, they become more and more diffused until one can no longer determine the point of origin.

"Well, I have a course on it later this school year (jan-feb 2012), so I can send you lecture notes if you want."

I'm curious at a high level, but I don't really feel like reading long papers. Whereas I used to buy computer books and read them through and through, today I can hardly bother to open the cover. I can't explain it, maybe it's the influence of the real world after college. I learned all this cool & interesting theory, but haven't much chance to really apply it in my jobs, and no ROI.

"It's targeted towards physicists...the mathematical part looking over-explained while the physical part would look under-explained."

I'd still need to learn the mathematics anyways.

Edited 2011-09-26 22:20 UTC