Modern train systems adopt communication-based train control (CBTC), which uses wireless communications to better monitor and control the train operations. Despite the well-studied security issues in wireless networking in information technology applications, security implementations in trains have been lagging; many train systems rely on security by obscurity and forgo well-established security practices such as key updates. To secure train systems against increasingly evolving and persistent attackers and mitigate key breach (which can occur due to misuse of the key), we build a key update scheme, Key Update at Train Stations (KUTS), that leverages the inherent physical aspects of train operations (mobility/infrastructure-asymmetry between the stations and the trains and the operational differences when the trains are at stations and between the stations). Furthermore, by incorporating separation of key chain and use and on the entities providing the key seeds, KUTS protects the key seeds for future updates against the breach of the current key and is both key-collision irrelevant (thwarting known collision-based threats on one-way random functions) and system-compromise resilient (protecting the key secrecy even when the train system is compromised). We theoretically analyze KUTS’s effectiveness, security strength, and security properties. We also implement KUTS on various computing devices to study the performance overhead.