Не знаю, мне почему-то кажется, что может прокатить хеш-сумма такого вида:
(-1)*(bit1) +2*(bit2) -3*(bit3) +4*(bit4)
То есть примеры сообщений:
0000 (основная часть) 000 (хеш-сумма)
0001 100
0010 101
0011 001
0100 010
1000 111
Но мне как-то трудно доказать или опровергнуть, что это будет работать. Навскидку, вроде бы ошибки находятся. Однако, не исключено, что я просто не углядел ситуации, где это не так.