It changes the content of the commit (by iterating the hash in the commit message itself) until the hash of the child commit matches. A big part of the trick is that it only looks at a prefix of the hash, so the search space is much smaller than the full SHA1 hash.
Not true! With git time-travel, you can refer to a future commits in the commit message. Eg:
https://github.com/hundt/git-time-travel:p