Good Hash and making a bad hash It is obvious that there are different hashes.  I am looking for a reference on hash complexity as it relates to strength because I am considering making a "bad hash".  I have read a few things on the impossibility of making an efficient hash based on a block cipher, and then I thought that there are cases for bad hashes.  Here is an example of why I am considering this.

In hardware, you have a branch instruction.  The branch instructions that branch on memory address are a concern  If you can augment this memory address, you can leave the memory segment.  As a simple example, consider a BRANCH of 6, and this looks like 

 BRANCH    OFFSET MEMORY
 1000      0110


It would be interesting to have a hash that results in some valid construct for a valid memory range.  The point of the hash is to not reveal the valid memory range.  

BRANCH   HASH   OFFSET
1000     XXXX   XXXX


An interrupt would occur if the memory offset is outside the allowed hash.  The time available to calculate this hash would be small, so it could not be a good hash.

Is there a reference on complexity and strength so I might consider this further?
I don't believe a hash function would be a promising looking approach.

For one, you state that The point of the hash is to not reveal the valid memory range, however you really can't do it.  If the attacker can see the program (and knows all the inputs to the hash, except for the destination address), he can simply evaluate it for all plausible destination addresses, and see which ones the hash allows access to.  Even if there were as many as a billion plausible addresses (and that's a truly huge program), that's still quite feasible.

You also state that you're interested in indirect branches whose legitimate target is within a small range; one example where this may come up with the compilation of a switch/case construct.  However, the memory addresses this uses are typically stored along side the program space, and so if the attacker could modify those addresses, they could also modify the instructions themselves, and so adding protection to this case doesn't really add much real protection.

Of course, there are the larger case, where the branch could legitimately go to a number of different locations throughout the program.  Examples where this might happen include:


Function pointers
Object method invocations
Exception handling
Function return (which, from a CPU standpoint, is a branch)


These cases are much harder; a pure range-based check might end up being "somewhere within the program executable code", which isn't a great help.  Encoding the actual legitimate addresses within the hash is going to be on the same order of magnitude as the simple concatenation of the address list, and so that'd be slow (as the CPU will need to load a nontrivial fraction of that data structure to check if the branch is legitimate).

Now, there's been a lot of work in this space (that is, how do we make sure that program branches are as intended by the correct program); this specific approach doesn't look promising.