Anyone considering lattice-based post-quantum cryptography should see this warning chart: . Full analysis is contained in new 99-page PDF "Risks of lattice KEMs" available from the same page. Page+PDF authors: NTRU Prime Risk-Management Team.
First release of djbsort: super-fast constant-time automatically verified AVX2 sorting code for int32 arrays. (Next target is ARM NEON.) Verification starts with the
#angr
toolkit for symbolic execution, which in turn uses libVEX from Valgrind.
In apparently coordinated announcements, NIST and NSA are strongly pushing for lattice-based crypto, specifically structured lattices, specifically cyclotomic lattices, including sizes where published attacks already seem to violate the minimum
#NISTPQC
security requirements.
Amazing compendium of failures of "provable security": . I saw a preprint months ago and the shock value of the huge lists still hasn't worn off. I think (and hope) this will put an end to the delusion that provable-security failures are isolated mistakes.
Another example of how easy it's becoming to deploy cryptographic software formally verified to be bug-free: As in NaCl, the only public-key option is ECC, and the only curve is Curve25519. Asking for RSA-2048 for "algorithm agility" = asking for bugs.
0.57 cycles/byte for ChaCha20 to encrypt 4KB on one core of new Intel Cannon Lake CPU. I haven't seen AES-256 results as fast as this on the same CPU, even though AES-256 has special hardware support and much smaller security margin.
Seems like a good moment to mention that, under Qubes, I have one browser window in one VM logged into Twitter, and a separate browser window in a separate VM logged into Google. The browsers aren't sharing any data. The window frames have different colors for the different VMs.
Releasing
#libcpucycles
library to count CPU cycles: Supports counters for amd64 (both PMC and TSC), arm32, arm64 (both PMC and VCT), mips64, ppc32, ppc64, riscv32, riscv64, sparc64, and x86, plus automatic fallbacks to various OS-level timing mechanisms.
Wow: Inoue and Minematsu announce a fast attack breaking OCB2. OCB2 appeared at Asiacrypt 2004; advertised provable security; is a current ISO standard. OCB3 seems safe, and Rogaway has been recommending OCB3 for years, but the OCB2 story is terrifying.
Bits in DRAM sometimes flip. Typical servers have SECDED ECC DRAM to protect against this, but typical desktops/laptops/smartphones don't. Have released a "libsecded" micro-library with secded_encode() to protect an array and secded_decode() to recover it:
New paper "A discretization attack": Identifies another NSA-exploitable weakness in standardization processes. Includes a detailed case study of how
#NISTPQC
could hypothetically have been attacked, and evidence suggesting that it was in fact attacked.
Dear
@nature
editorial board: Please withdraw the following statement, which is (1) false and (2) thoroughly deceptive. "Specialists also point to problems for which quantum computers have long been known to have a proven advantage, such as web searches."
Are you surprised to hear WHO saying that healthy skydivers don't need to and shouldn't use parachutes? This is backed up by a systematic review of randomized controlled trials, published in the British Medical Journal, cited more than 1000 times:
People who trust optimizing compilers to work correctly seem to be surprised by a 2020 gcc bug report where the optimizer treats byte arrays as equal if they pass strcmp. For comparison, here's a gcc bug report I filed last century:
Not verified yet, so don't put into production, but seems to compute inverses mod 2^255-19 in under 4800 Skylake cycles: Also speed records on Haswell, Broadwell, Kaby Lake, etc. Joint work with Bo-Yin Yang. Uses convex-hull calculations from
@pwuille
.
Cryptographers working on "verifiable delay functions" (VDF) seem to think that all known algorithms to compute x^2^T mod pq (unknown p,q) need T times the latency of a single squaring. Sorenson and I have a 2007 paper beating this in some hardware models.
Bo-Yin Yang and I have a new paper "Fast constant-time gcd computation and modular inversion": Much faster than earlier constant-time Euclid variants. Case studies: new speed records for 2^255-19 inversion (even faster than Fermat!) and NTRU-HRSS keygen.
Implementing gcd/xgcd/modinv? Heard about Microsoft SymCrypt gcd running forever () and OpenSSL gcd leaking secret keys via timing ()? Bo-Yin Yang and I have a paper with a simple constant-time gcd algorithm.
New blog post "Why EdDSA held up better than ECDSA against Minerva": Cryptosystem designers successfully predicting, and protecting against, implementation failures.
#ecdsa
#eddsa
#hnp
#lwe
#bleichenbacher
#bkw
10000 Haswell cycles to sort 1024 32-bit integers: 13x faster than radix sort in Intel's Integrated Performance Primitives library, 2.6x faster than sorting code from NTRU Prime paper. Working on formal verification.
US govt sends $1.2B to quantum salesmen making false promises: e.g. "Quantum computers will be able to sort rapidly through data sets that are too large to ever be stored on conventional devices, such as real-time video of the entire surface of the earth."
IACR is adopting NSA's clever solution to the cryptocurrency/cryptography conundrum: from now on, "crypto" means cryptocurrency, and "crypt" means cryptography. Next year's flagship IACR conferences will split into Crypto, Eurocrypto, Asiacrypto, Crypt, Eurocrypt, and Asiacrypt.
As someone who happily runs servers and laptops at constant clock frequencies (see for Linux advice) rather than heat-the-hardware random frequencies, I dispute the claim in that this has an "extreme system-wide performance impact".
"What do quantum computers do?" Focusing on the core quantum instructions that programmers need to know. Emphasizing examples much more than formulas. Trying hard to eliminate unnecessary terminology (e.g., unitaries) and unnecessary notation (e.g., kets).
18 months ago NIST suddenly switched to counting memory-access costs in lattice attacks, massively pumping up Kyber-512's claimed security level. New lattice-attack optimization from Zhao, Ding, and Yang makes the memory-access costs practically disappear:
This is clearly not the world's biggest problem in 2020, but it's still depressing to see the official software for Frodo (a high-profile candidate for post-quantum crypto) broken by a timing attack on memcmp: . We need more work on constant-time languages.
NIST now says it plans to announce its selections of post-quantum algorithms on "Tuesday, July 5th" (I presume 2022, not 2033). Given the extent to which waiting for NIST has stalled pq deployment, this announcement is an important step forward no matter what the details are.
We're now up to a solid half year of delay in post-quantum standardization, apparently because NIST picked a new design in the middle of a patent minefield and was somehow confident it could instantly buy its way out of the minefield. Half a year of data given away to attackers.
"Let's take code from the SUPERCOP benchmarking framework. Does this file supercop/crypto_stream/salsa20/e/amd64-xmm6/warning-256gb mean anything? Probably not." [Time passes] "BREAKING NEWS: We found that this implementation doesn't work after 256GB!"
My new report "Papers with computer-checked proofs" gives "case studies supporting the hypothesis that it is often affordable for a paper presenting theorems to also include proofs that have been checked with today's proof-checking software":
New resource page available on timing attacks, including recommendations for action to take regarding overclocking attacks such as
#HertzBleed
: Don't wait for the next public overclocking attack; take proactive steps to defend your data against compromise.
This news reminds me of the European Space Agency in saying that "human beings" usually cannot "access flying spacecraft" so "there is no need for side channel attack protection". Serious attackers build machines to carry out attacks beyond human ability.
NSA's secret members of pqc
@nist
.gov team: Nick Gajcowski; David Hubbard; Daniel Kirkwood; Brad Lackey; Laurie Law; John McVey; Scott Simon; Jerry Solinas; David Tuller; later Rich Davis. Jacob Farinholt was Naval Surface Warfare Center, US Navy. Not sure about Evan Bullock.
says author is "Post Quantum Cryptography Team, National Institute of Standards and Technology (NIST), pqc
@nist
.gov". FOIA results have revealed secret pqc
@nist
.gov team members in early Sep 2016, after draft NISTPQC call: more NSA people than NIST people.
Which post-quantum submissions (1) haven't suffered security losses since the
#NISTPQC
competition began and (2) are among the 26 submissions in round 2 (which is ending soon)? I think there are exactly 3: SIKE (which scares me for being too new), Classic McEliece, and SPHINCS+.
Experimenting with several variants of the TEA cipher as a teaching tool (TEAching tool, I guess) for cipher cryptanalysis: Are there any common cipher attacks that _can't_ be illustrated with TEA or minor variants of TEA? See also .
Posted an AVX2-vectorized-sorting benchmarking script covering djbsort, vxsort, vqsort. (vxsort and vqsort also support AVX-512.) The middle part of this Skylake graph is the part that matters for crypto, and also the base case for larger quicksort etc.
Still needs auditing and formal verification, but happy to announce availability of lib25519-20221222. Includes extensive new speed work from Kaushik Nath: e.g., on Skylake, 30 kcycles for DH keygen, sig keygen, signing; 90 for DH shared secret; 110 verif.
Given the current reality of desktops/laptops/smartphones almost never having ECC RAM, I'd love to see more operating-system support for periodically sweeping through pages to detect and correct errors, storing (say) 14 bytes of error-correction data for each 4096-byte page.
20 years ago, when the IETF was building Punycode instead of mandating UTF-8, I thought they were being remarkably stupid, and said so publicly. Later I started understanding the basic incentives. Simple, boring, working systems mean less money for standardization organizations.
says author is "Post Quantum Cryptography Team, National Institute of Standards and Technology (NIST), pqc
@nist
.gov". FOIA results have revealed secret pqc
@nist
.gov team members in early Sep 2016, after draft NISTPQC call: more NSA people than NIST people.
Apparently some Americans aren't making vaccination appointments despite being eligible. Will they be jealous if and when we start publicly sending spare vaccines to Mexico, Brazil, India, etc.? "I didn't want this dose but I definitely don't want those _foreigners_ to have it!"
Tried Google's new vectorized quicksort code vqsort on Skylake, and timed Sorter() as ~8000 cycles for int32[256] (big chunk of code for a size-specific sorting network), ~19000 cycles for int32[1024] (non-constant-time). djbsort is 1230, 6286 (ct). Did I misuse vqsort somehow?
After NIST's Dual EC standard was revealed in 2013 to be an actual (rather than just potential) NSA back door, NIST promised more transparency. Why does NIST keep soliciting private
#NISTPQC
input? (The submissions I'm involved in seem well positioned; that's not the point.)
The new CleverParrot exposure-notification protocol in says your phone will spend 12 minutes per day checking, for your secret s, for many pairs u,v, whether u^s = v. Here's a nearly 2x speedup: check whether u^r v^t = 1 for half-size r,t with s = -r/t.
Looks like NIST didn't actually nail down the patent buyouts before announcing Kyber's selection, so now the patent holders have even more power. But, wait, NIST's expert negotiators say that they "may consider" switching to NTRU if agreements aren't signed "by the end of 2022".
In case it's useful for more people, posted a small script built on top of pypdf () to magnify giant-margin conference/book PDFs into reasonable-margin PDFs, while preserving hyperlinks (unlike pdfjam) and anchors. More information:
Our inversion code is now generalized to handle common 256-bit primes at almost the same speed as 2^255-19, around 4000 Skylake cycles: Still haven't fully verified, so don't put into production. Tracking verification progress:
RWC2019 has some talks on formal verification, where a computer takes care of tediously checking for all the little mistakes that humans tend to miss. Particularly looking forward to the verification talk by Bhargavan, or, as the schedule says, "Bhargava".
Now under 3900 Skylake cycles for code that seems to compute inverses mod 2^255-19: This is further work with
@bo_yin
, also using ideas from Greg Maxwell and
@pwuille
. Still exploring speeds, still haven't verified the code, so don't put into production.
More document releases forced by the "NSA, NIST, and post-quantum cryptography" lawsuit: These include internal NIST slides marked "not for public distribution". Meanwhile NIST repeatedly claimed in public that this was an "open and transparent" project.
A recent preprint "The Planck Constant and Quantum Fourier Transformation" () suggests that Shor is unimplementable since it involves tiny rotations. But Coppersmith pointed out in 1994 () that Shor works _without_ the tiny rotations.
No. Lattice KEMs under consideration for deployment (NTRU, Kyber, Frodo, etc.) do _not_ have NP-hardness proofs. (There's also no serious hope of crossing the dividing lines.) Questions to ask: Where did the pervasive misinformation on this topic originate? Who benefits from it?