[c7DJTLrn]

>How complex would a device have to be to not be trivially defeated by a replay attack?

Not very.

>How do you get both ends to reliably communicate without requiring an always-on internet connection in both the dongle and the vehicle to sync timing or some other state?

You don't need an Internet connection or server. TLS would do the job just fine.