If it is only on specific communication channel, then you just need to get a private signing key, i.e. by dumping same type of ECU. And we are back at the beginning.
The signing key would of course be unique per ECU/keyfob that needs to sign stuff so dumping another ECU doesn't help you crack it.
Loading a new private key from the server? Well, thief's device can probably pretend to be a server and load a new private key into the control unit behaving as a master of immobilizer. Then the thief will get car and instantly new set of keys.
Erm... using the LSB of a network RX timer is common way to add entropy (and perfectly feasible here). You could also use the LSB of the +voltage rail sense or the thermometer that probably exists on your MCU.