Some sort of public key crypto scheme + including hard-to-change local device characteristics in the challenge.

I guess the path of least resistance then would have been to patch the executable to remove the check.