Welcome to the eighth edition. This week we’re deep into the cryptography. Let’s dive right in…
Did NIST Get the Maths Wrong?
Who's double-checking the maths on post-quantum algorithm submissions to NIST?
Apparently, D.J. Bernstein is. And he's not happy with the security analysis on Kyber.
Specifically, the Kyber-512 variant is claimed to be as strong as 128-bit AES, which was a requirement for the minimum PQC security level. Yet, in a 17,700-word blog post, Bernstein questions this claim.
He believes a fundamental error was made, where large numbers have been multiplied rather than added. He also argues that his own submission, NTRU Prime, would have been a better choice.
If he's correct, then Kyber-512 is not as secure as previously claimed. Bernstein believes it should be withdrawn, and claims that NIST is ignoring his pleas. He has filed a freedom of information request and has a civil lawsuit pending.
Bernstein has a long history of inventing cryptographic algorithms, as well as challenging the US government on cryptographic matters. He was part of the team behind several PQC algorithm submissions.
A link to the blog post is below.
Link to Bernstein's blog post: https://blog.cr.yp.to/20231003-countcorrectly.html.
RSA PKCS#1 Still Vulnerable after 25 Years
Apparently, a 25-year-old side-channel attack against RSA padding still works and affects common crypto libraries.
In the original 1998 paper, Daniel Bleichenbacher showed that a TLS server can be tricked into decrypting or signing a message chosen by an attacker. The attack worked when the server was using RSA with PKCS#1 v1.5 padding.
The server would attempt to decrypt incoming messages but would reject those that didn't have correct padding. Bleichenbacher's attack involved sending thousands of carefully crafted messages and observing if the server rejected or accepted the padding.
From this seemingly innocuous information, it was possible to sign or decrypt arbitrary information.
A new paper published this year shows that a variant of the attack still works. Even against crypto libraries that were thought to be immune.
By using more advanced timing of server responses to deduce whether padding is correct or incorrect, the new approach affects libraries like OpenSSL and GnuTLS.
See below for a link to a helpful overview page (with links to the paper), as well as a link to the original 1998 paper.
The project page: https://people.redhat.com/~hkario/marvin/.
The original Bleichenbacher paper: https://archiv.infsec.ethz.ch/education/fs08/secsem/bleichenbacher98.pdf.
Bounty Offered to Crack Elliptic Curve Seeds
A $12k bounty has been offered for anyone who can figure out the origin of the seeds used in NIST elliptic curves.
These elliptic curves form the basis of much of today's public key cryptography, including the ECDSA X.509 certificates used widely throughout the web.
The parameters of the curves were apparently derived from the SHA-1 hashes of simple English phrases, and supplied by the NSA. However, the details have been lost over time. And, sadly, the man who chose the seeds passed away earlier this year.
If someone deduces the phrases behind the seeds, they will not weaken the security of the curves. If anything, it will reassure those who still believe the NSA may have picked the parameters in order to deliberately weaken the curves.
Link to announcement: https://words.filippo.io/dispatches/seeds-bounty/
Turning SSO Providers into CAs
Have you heard about OpenPubkey? It's a beautifully elegant concept that turns SSO providers into certificate authorities.
Most SSO providers, such as Google, Microsoft, Okta, etc, support the OpenID Connect protocol (OIDC). This is being used under the covers whenever you click "Sign in with Google" on a website or app.
The result of an OIDC interaction is a signed token that attests to your identity. It's a signed document that says "Google confirms this person is really Duncan Jones".
OpenPubkey extends this idea further. By cleverly stuffing the right data into the client request, the signed token can also attest to your public key. Effectively, this turns the SSO provider into a certificate authority.
The neat thing is that the SSO provider doesn't need to change at all. This means OpenPubkey works out of the box with normal providers, like Google.
The clients generate short-term (ephemeral) keys, so there is no key management to worry about. Keys are generated when they are needed, used to sign documents, and then thrown away.
The initial use case is for software supply chain security, where having an simple digital signing process linked to existing ID providers is a useful thing. But this feels like a powerful idea that may impact a wide range of services across the web.
Announcement from Linux Foundation: https://www.linuxfoundation.org/press/announcing-openpubkey-project.
Paper describing the concepts: https://eprint.iacr.org/2023/296.