How the CIA used Crypto AG encryption devices to spy on countries for decades
Building Lattice Reduction (LLL) Intuition
> The Lenstra–Lenstra–Lovász (LLL) algorithm is an algorithm that efficiently transforms a “bad” basis for a lattice L into a “pretty good” basis for the same lattice. This transformation of a bad basis into a better basis is known as lattice reduction, and it has useful applications. For example, there is attack against ECDSA implementations that leverage biased RNGs that can lead to private key recovery. However, my experience learning why LLL works has been pretty rough. Most material covering LLL seems targeted towards mathematicians and I had to (I guess I wanted to) spend a lot of time trying to weasel out the intuition and mechanics of the algorithm. This blog post is a semi-organized brain dump of that process. My goal is to cover LLL in such a way that slowly ratchets down the hand-waving, so feel free to read until you are happy with your level of understanding.
The Hidden Number Problem
> The Hidden Number Problem (HNP) is a problem that poses the question: Are the most signficant bits of a Diffie-Hellman shared key as hard to compute as the entire secret? The original problem was defined in the paper “Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes” by Dan Boneh and Ramarathnam Venkatesan.
> In this paper Boneh and Venkatesan demonstrate that a bounded number of most signifcant bits of a shared secret are as hard to compute as the entire secret itself. They also demonstrate an efficient algorithm for recovering secrets given a significant enough bit leakage. This notebook walks through some of the paper and demonstrates some of the results.
What is the random oracle model and why should you care?
> About eight years ago I set out to write a very informal piece on a specific cryptographic modeling technique called the “random oracle model”. This was way back in the good old days of 2011, which was a more innocent and gentle era of cryptography. Back then nobody foresaw that all of our standard cryptography would turn out to be riddled with bugs; you didn’t have to be reminded that “crypto means cryptography“. People even used Bitcoin to actually buy things.
> That first random oracle post somehow sprouted three sequels, each more ridiculous than the last. I guess at some point I got embarrassed about the whole thing — it’s pretty cheesy, to be honest — so I kind of abandoned it unfinished. And that’s been a major source of regret for me, since I had always planned a fifth, and final post, to cap the whole messy thing off. This was going to be the best of the bunch: the one I wanted to write all along.
The Curious Case of WebCrypto Diffie-Hellman on Firefox - Small Subgroups Key Recovery Attack on DH
> Mozilla Firefox prior to version 72 suffers from Small Subgroups Key Recovery Attack on DH in the WebCrypto’s API. The Firefox’s team fixed the issue removing completely support for DH over finite fields (that is not in the WebCrypto standard). If you find this interesting read further below.
Microsoft's Chain of Fools
The BLAKE3 cryptographic hash function
> BLAKE3 is based on an optimized instance of the established hash function BLAKE2, and on the original Bao tree mode. The BLAKE3 specifications and design rationale are available in the BLAKE3 paper. The current version of Bao implements verified streaming with BLAKE3.
DECO - A novel privacy-preserving oracle protocol
> DECO is a privacy-preserving oracle protocol. Using cryptographic techniques, it lets users prove facts about their web (TLS) sessions to oracles while hiding privacy-sensitive data.
SHA-1 is a Shambles
> We have computed the very first chosen-prefix collision for SHA-1. In a nutshell, this means a complete and practical break of the SHA-1 hash function, with dangerous practical implications if you are still using this hash function. To put it in another way: all attacks that are practical on MD5 are now also practical on SHA-1.
Too Much Crypto
> We show that many symmetric cryptography primitives would not be less safe with significantly fewer rounds. To support this claim, we review the cryptanalysis progress in the last 20 years, examine the reasons behind the current number of rounds, and analyze the risk of doing fewer rounds. Advocating a rational and scientific approach to round numbers selection, we propose revised number of rounds for AES, BLAKE2, ChaCha, and SHA-3, which offer more consistent security margins across primitives and make them much faster, without increasing the security risk.
A few comments on ‘age’
> Age is a new tool for encrypting files, intended to be a more modern successor to PGP/GPG for file encryption. This is a welcome development, as PGP has definitely been showing its age recently. On the face of it, age looks like a good replacement using modern algorithms. But I have a few concerns about its design.
age is a simple, modern and secure file encryption tool.
> A simple, modern and secure encryption tool with small explicit keys, no config options, and UNIX-style composability.
I think it’s ready now?
Application Layer Transport Security
> Google’s Application Layer Transport Security (ALTS) is a mutual authentication and transport encryption system developed by Google and typically used for securing Remote Procedure Call (RPC) communications within Google’s infrastructure. ALTS is similar in concept to mutually authenticated TLS but has been designed and optimized to meet the needs of Google’s datacenter environments.
OpenSSH Key Shielding
> On June 21, 2019, support for SSH key shielding was introduced into the OpenBSD tree, from which the OpenSSH releases are derived. SSH key shielding is a measure intended to protect private keys in RAM against attacks that abuse bugs in speculative execution that current CPUs exhibit. This functionality has been part of OpenSSH since the 8.1 release. SSH private keys are now being held in memory in a shielded form; keys are only unshielded when they are used and re‐shielded as soon as they are no longer in active use. When a key is shielded, it is encrypted in memory with AES‐256‐CTR; this is how it works:
TPM—Fail TPM meets Timing and Lattice Attacks
> We discovered timing leakage on Intel firmware-based TPM (fTPM) as well as in STMicroelectronics’ TPM chip. Both exhibit secret-dependent execution times during cryptographic signature generation. While the key should remain safely inside the TPM hardware, we show how this information allows an attacker to recover 256-bit private keys from digital signature schemes based on elliptic curves.
> This research shows that even rigorous testing as required by Common Criteria certification is not flawless and may miss attacks that have explicitly been checked for. The STMicroelectronics TPM chip is Common Criteria certified at EAL4+ for the TPM protection profiles and FIPS 140-2 certified at level 2, while the Intel TPM is certified according to FIPS 140-2. However, the certification has failed to protect the product against an attack that is considered by the protection profile.
> Rolling forward 15 years, isogeny-based cryptography is another area with many technical subtleties, but is moving into the mainstream of cryptography. Once again, not everything that can be done with discrete logarithms can necessarily be done with isogenies. It is therefore not surprising to find papers that have issues with their security.
> It is probably time for an Isogenies for Cryptographers paper, but I don’t have time to write it. Instead, in this blog post I will mention several recent examples of incorrect papers. My hope is that these examples are instructional and will help prevent future mistakes. My intention is not to bring shame upon the authors.
'Mario Maker 2' Creators Are Using Cryptography to Make Impossible Levels
> A strange competition has popped up to create levels with audacious passcodes that you could spend a lifetime trying to guess.
Real-world measurements of structured-lattices and supersingular isogenies in TLS
> This is the third in a series of posts about running experiments on post-quantum confidentiality in TLS. The first detailed experiments that measured the estimated network overhead of three families of post-quantum key exchanges. The second detailed the choices behind a specific structured-lattice scheme. This one gives details of a full, end-to-end measurement of that scheme and a supersingular isogeny scheme, SIKE/p434. This was done in collaboration with Cloudflare, who integrated Microsoft’s SIKE code into BoringSSL for the tests, and ran the server-side of the experiment.
> Because optimised assembly implementations are labour-intensive to write, they were only available/written for AArch64 and x86-64. Because SIKE is computationally expensive, it wasn’t feasible to enable it without an assembly implementation, thus only AArch64 and x86-64 clients were included in the experiment and ARMv7 and x86 clients did not contribute to the results even if they were assigned to one of the experiment groups.
Minerva: Lattice attacks strike again
> This page describes our discovery of a group of side-channel vulnerabilities in implementations of ECDSA/EdDSA in programmable smart cards and cryptographic software libraries. Our attack allows for practical recovery of the long-term private key. We have found implementations which leak the bit-length of the scalar during scalar multiplication on an elliptic curve. This leakage might seem minuscule as the bit-length presents a very small amount of information present in the scalar. However, in the case of ECDSA/EdDSA signature generation, the leaked bit-length of the random nonce is enough for full recovery of the private key used after observing a few hundreds to a few thousands of signatures on known messages, due to the application of lattice techniques.