Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Let's assume a simple algorithm like the Skein hash function.

Is it possible, given the algorithm, to construct a proof that it does not have a particular distinguisher, something like:

$P(xyz)$ is the probability that $xyz$ is truly random over some alphabet,

Given $\vert y \vert = l$, for some fixed length l, $z = f(x)$ (i.e., $z$ is dependent on $x$).

Not in general, of course, but for a particular such distinguisher.

share|improve this question

migrated from stackoverflow.com Apr 23 '12 at 9:05

This question came from our site for professional and enthusiast programmers.

    
Welcome to crypto.se; your Q has been moved here on account of being more on topic here than on SO - do feel free to register an account to pick up your rep and more importantly responses here :) –  Ninefingers Apr 23 '12 at 9:12
    
Whats the policy on here on helping people answer what are pretty homework questions/ facilitating cheating? –  imichaelmiers Apr 24 '12 at 1:59
3  
1 - This isn't a homework question. I asked because I was wondering if such proofs are constructed for hash functions. 2 - If it was a homework, the homework would have been turned in long ago - the question was first asked over a year ago! –  Vanwaril Apr 24 '12 at 2:13
    
There is at least some PRNGs for which proofs exist that show that they're indistinguishable provided a certain other problem is hard. en.wikipedia.org/wiki/Blum_Blum_Shub –  CodesInChaos Apr 25 '12 at 12:18
    
The hash function Skein is not exactly what I would call "simple" from the point of view of understanding the way it maps its inputs to outputs. Otherwise, one would "simply" find pre-images and collisions for it! –  bob Oct 29 '12 at 12:46
add comment

1 Answer 1

There are a number of distinguishers that it it would be easy to prove are not present in a hash function.

For example, I can easily prove that Skein does not have the distinguisher "the 2nd bit in the output is equal to the first bit of the output with probability 1". The proof would be a simple example of a message whose digest does not have this property (which should be fairly easy to find).

For more interesting distinguishers, the problem becomes much harder (on a side note, is the distinguisher really interesting if I can prove it doesn't hold for a particular hash function?).

My gut feeling is that yes, one could come up with an "interesting" distinguisher and then show that it doesn't hold for the hash function, but I can not offer more than a gut feeling.

share|improve this answer
    
Yeah, I was wondering if there were 'real' arguments for 'real' hashing functions that showed one did not contain a distinguisher that another is susceptible to. –  Vanwaril Apr 25 '12 at 1:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.