Re: Hash functions & Physical Analogies

[danisch@ira.uka.de (Hadmut Danisch)]

Michael P. Brininstool wrote:


> I seem to remember someone mentioning that a hash function, like the
> one used in signatures in PGP, would show a large change for a small
> change in the file, and a small change for a large change in the file.

More important is that it is difficult (infeasible) to find a file for a 
given hash value. (This implies that small file changes result
in large hash value changes.)


> First question:
> 	I think I have seen references to topology in discussions of
> 	cryptography.  I have never had a topography class, so I was
> 	wondering, is Rubik's cube is a topology problem?

No, it is a permutation group. Use the Schreier-Sims-Algorithm to
find solutions.



> Second question:
> 	If Rubik's cube is a topo prob, is it a good analogy for trying
> 	to describe hash functions to people?

No. It is a simple thing to find a turn which fits to a given 
state of the cube. When the cube came out a german newspaper
published a simple method for solving the cube. This means everyone
can easily find a "message" which fits to a given "hash value". This must
not be possible for a cryptographic hash function. The hash-function
must be a one-way function, but the cube isn't one-way.

Further more, the cube allows some kind of differential analysis.
Since turning the front side only affects the front side, you can
see what to do to turn the front side back. That's also not good
for cryptographic context.



> Third question:
> 	If there is an analogy, how do you convince the lay person that the
> 	hash is a one-way function?  By demonstrating that it maps many to
> 	one, and the Rubik's Cude maps one to one?

It is still a problem to convince experts that a hash function is a 
one-way function...




> Fourth question:
> 	To sign a post with PGP (from within vi, under trn)  Do I include
> 	the header in the lines to be run through 'pgp -fast' or not?
> 	(I have the cp list go into a news gateway on my home machine so
> 	that threads are easier to follow)

Should not do this. The header is modified by transport agents, e.g.
paths and date are added. 


Hadmut