Good Hash and making a bad hash

Question

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?

Answer 1

Poncho points out the issues this has in the general case.

As an amusing alternative, consider that Google's Native Client (NaCl) does this, though in a rather different manner.

In NaCl you are allowed to do direct branches to anywhere in the code which can be a valid instruction. They simply do a static analysis process which identifies the starts of all valid opcodes and makes sure the branches point to them. The interesting bit is how they handle the indirect branches. These are the ones you are targeting with your question. Indirect branches are only allowed to point to instructions that are on 32-byte boundaries. In effect, this is a hash function consisting of Addr AND 31. If the value of that hash function is 0, then the branch is well formed. This is very similar (if not identical) to the structure you want.

What's beautiful about it is how easy it is to implement without any additional hardware. NaCl simply requires that all indirect branches come paired with an and operation such as

AND EAX, EAX, 0xFFFF0
BRANCH EAX

This means that NaCl can write privileged code in the same memory space as the program, as long as they write it in a way which is aware that the user may jump to any 32-byte aligned memory address within that privileged code. Insulate those points in your privileged code, and you can do anything you want elsewhere!

So yes, you can make such a hash, and Addr AND 31 has been explored by Google as a useful hash to choose.

Answer 2

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.