I wonder, how many halving do I need to reduce a 125 bit key down to 40 bit?
You can always halve a key. However, if your key will be odd, then after halving it, you will end up in a worse situation.
SHA-256("125-bit")=c383a1ae19ff4401f72fdfbb4ffeb6fc7a38c6692b07b188edcbdc31b0160ee7
mask125=0000000000000000000000000000000020000000000000000000000000000000
(hash%mask125)=key=000000000000000000000000000000001a38c6692b07b188edcbdc31b0160ee7
key/2=7fffffffffffffffffffffffffffffff6a73d1a7ed2828e256cf1d5f40262814
key-1=000000000000000000000000000000001a38c6692b07b188edcbdc31b0160ee6
(key-1)/2=000000000000000000000000000000000d1c63349583d8c476e5ee18d80b0773
See? You can reach a key with less bits, only if you know if it is even or odd. So, if you want to go from 125-bit key to 40-bit key, then guess what: you have to know the last 85 bits.