The Bad Guys Just Broke My Crypto - What Do I Do?

### Overview In this talk presented at a virtual Linux Foundation event, Chris Chaplin, an embedded technology specialist for Intel UK, addresses the evolving threats to modern cryptography. Chaplin discusses how systems that are considered secure today may quickly become obsolete or vulnerable due to advances in computing power, mathematical algorithms, and emerging quantum computing capabilities. He evaluates how organizations can prepare their systems—especially long-lived industrial, automotive, and medical hardware—for shifting cryptographic standards and potential regulatory pressures.

### Key Topics - **Evolution of Cryptographic Security**: Security is a continuous process rather than a static goal. Examples like WEP in Wi-Fi and ongoing updates to the Linux kernel (`libcrypto`) illustrate how standards deprecate over time as computing power grows. - **Public Key Cryptography & Factorization**: Classic asymmetric cryptography (such as RSA and ECDSA) relies on mathematical functions that are easy to compute in one direction but difficult to invert (e.g., finding large prime factors $p$ and $q$ from $n$). Chaplin reviews historical milestones from the RSA Factoring Challenge (1991–2007) and the breaking of RSA-768 in 2009. - **Shor's Algorithm and Quantum Threats**: Shor's algorithm utilizes a quantum period-finding subroutine that can factor integers in polynomial time. While physical quantum systems (e.g., IBM, Google, and Intel prototypes) had reached up to 72 qubits around 2017–2019, breaking a 1024-bit key would require an estimated 2,000 qubits. - **Longevity of Data vs. Product Lifespan**: Evaluating cryptographic risk requires balancing product lifespan against data sensitivity duration. Short-term data (session cookies, daily keys, token passwords) faces low risk, whereas long-term data (medical records, bitcoin wallet credentials, private keys, social security numbers) requires planning for post-quantum algorithms. - **Hardware Acceleration and Adaptability**: Traditional CPUs incorporate specialized instruction sets to accelerate legacy algorithms like AES. Transitioning to post-quantum algorithms may incur severe performance penalties on standard CPUs. Chaplin recommends integrating programmable logic (such as discrete or SoC FPGAs) to dynamically implement and update hardware accelerators in the field. - **Government and Policy Challenges**: Beyond technical cryptanalysis, nation-state policies and law enforcement efforts challenge end-to-end encryption. Chaplin highlights discussions from US Attorney General William Barr, joint governmental letters (UK, US, Australia) regarding Facebook messaging, and the GCHQ 'Ghost Protocol' proposal by Ian Levy and Crispin Robinson.

### Technical Details - **Compute Complexity**: Factoring RSA-768 in 2009 required the equivalent of 2,000 years of computation on a single 2.2 GHz AMD Opteron CPU ($2^{67}$ instructions). Each bit added to an RSA key exponentially increases factorization difficulty. - **Quantum Progression**: Historical progress in quantum factorization advanced from $15 = 3 \times 5$ in 2001, to 21 and 143 in 2012, with multi-qubit systems gradually scaling, though remaining far below the scale needed to crack standard asymmetric keys. - **Crypto Agility & Programmable Logic**: Systems can adopt hybrid SoC architectures (such as ARM Cortex cores paired with FPGA fabric) or PCIe FPGA accelerator cards for data centers. This allows replacing or augmenting crypto engines via field firmware updates as post-quantum standards (e.g., lattice-based schemes) crystallize.

### Takeaways Developers must design systems for crypto agility, ensuring both software and firmware are field-updatable. For products with long market lifetimes or handling long-term sensitive records, architects should evaluate hardware that incorporates programmable logic (FPGAs) to future-proof acceleration engines against evolving post-quantum algorithms and changing legislative environments.