Cracking a 512-bit DKIM key for less than $8 in the cloud

Doing this only provides deniability in public. If this was brought to a court there are enough server logs to build out if that DKIM record was valid along with a number of DNS history providers.

In the link in the parent comment. :-)

I've been doing this since around 2018, and have seen a few others implement it.

https://rya.nc/dkim-privates.html

That was Matt Green, the person you replied to =)

Ha, at least ! Thank you for the comment.

If there is some mail from my addr, with a valid DKIM signature, it proves nothing: - perhaps the mail was sent by somebody else on the same plateform, but in my name (identity usurpation of the user part of the mail) - perhaps somebody got illegal access to my email account, without me knowing - .. ?

In no case it proves that I, as a human, sent this email.

But of course, justice is a fiction that cannot exist: there is no justice, only probabilities (and feelings :( ).

No. DKIM is meant to apply to emails in transit; it is part of the transaction of exchanging emails. But DKIM signatures are verifiable long after that transaction has completed. That was not an intended feature of DKIM, and it's a grave privacy violation.

To satisfy DKIM's design goal, you only need a "current" DKIM key that is secure for a window of time. When that window of time passes, you rotate the secret and publish your own key, repairing (hopefully) much of the privacy injury.

When using deniable authentication (e.g. Diffie-Hellman plus a MAC), the recipient can verify that the email came from the sender. But they can't prove to a third party that the email came from the sender, and wasn't forged by the recipient.

Do take a look at the blog post I cited above, where I go into this in loads of detail. The TL;DR is that DKIM only needs to ensure origin authenticity for the time it takes to deliver an email, which is usually a few hours or a day at most.

The unintentional problem DKIM is causing is that it actually provides non-repudiation for many years. Those signed emails can sit in someone's mailbox for years, then get stolen by a hacker. The hacker can then blackmail the owner by threatening to dump the email trove, or for newsworthy targets they can just do it. Reasonable people (e.g., high-integrity newspapers, courts of law) will say "how can we trust that these stolen emails are authentic given that there's no chain of custody?" DKIM signatures nearly answer that question, which makes stolen emails much more valuable than they would be otherwise.

Yes.

Deniability and perfect forward secrecy are at odds with how people use email anyway. But that doesn't stop people from demanding both very loudly, and some people from promising them.

You should read the blog post Prof. Green linked to. All of your questions are addressed there.

That's not quite what he's saying.

DKIM's goal is that the receiving system can trust that the message presented to it has come from a host that knows the key, and so could sign it. At the time that message is received, you should be able to assume that only people authorised to send from that domain are able to do so.

By publishing older keys, you gain deniability back, because anybody could have forged the message and signed it. Even if you have timestamps that show when you received the message, the onus is one you to prove that those timestamps are not fabricated. This is a much harder problem because secrets can be revealed later but not forgotten.

To be able to prove that you did it fact receive the message on that date, you'd probably have to record e.g. the message ID, signature and timestamp (perhaps all encrypted with a key that you can reveal later) on a blockchain, which would then serve as proof of when the message was received. Even then, you'd still have to prove that the key hadn't been disclosed before that time.

The idea isn't to stop Google from signing and validating DKIM. It's that the major players who do DKIM should rotate and publish their keys, so that at any given instant their current DKIM key is only valid for N hours, and after that it's public, so anyone can forge backdated messages.

The issue here isn't rules of evidence, it's user privacy. In the real world, DKIM has repeatedly been used to violate privacy. More importantly: latent verifiable secure DKIM signatures on archived emails offer no value to users; they literally only have real-world value to attackers.

Only if the defendant doesn't challenge the evidence. If I'm the defendant and I know I sent those emails, I'm not going to challenge the screenshot. If I know I did not send those emails, then I'll do my best to pay for forensic analysts to generate evidence to exonerate me.

I absolutely believe you - lawyers, judges, and juries alike tend to be technologically illiterate, but do you have any references/links to this happening?

It's tiring that most things have to come back to politics nowadays.

It's more "I want you to be able to verify I sent an email to you, but I don't want you to be able to prove to a third party that I sent it."

The fact that this is possible is some cryptography black magic.

I'm wondering if this process can be GPU optimized. It's possible to rent really beefy GPU cloud instances for a few bucks per hour. <1 hour seems to be in reach.

That would be true if RSA scaled proportionally with the number of bits, but the exponent involved is much lower than 1. 1024->2048 gives you around the same difficulty as adding 30 bits to a symmetric key.

What? Just use normal name servers. The registrar doesn't matter one bit, they delegate the zone to whatever name servers you specify. Those can serve whatever records properly.

Is there a compelling reason to use 3072 instead of 4096? If you're going to kick the can down the road you might as well put some effort into it. The difference in memory use/compute time has to be marginal at this point. It's not like the old days when jumping from 512 to 4096 made the encryption unusably slow.

RSA 2048 isn't broken, but experts consider it a matter of time. How long I don't know, but since the attacks are known (prime numbers) someone (read not me) can make an estimate with error bars that are concerning enough to consider it as good as broken.

Nobody is recommending RSA-3072 per se. The recommendation if wanting to stick with RSA is to move beyond RSA-2048, and the world at large jumped all the way to RSA-4096 long ago.

But perhaps with not a very solid justification to do so:

* https://articles.59.ca/doku.php?id=em:20482030

X25519 has seen broad adoption (in the key exchange). Ed25519 has not, you can't actually use an Ed25519 certificate on the web. It's in a deadlock between CAs, browsers and TPM manufacturers (and to some extent NIST, because Ed25519 has not been approved by them).

It's not being blocked per se, you can use it mostly (98%) without any issues. Though things like Amazon SES incorrectly reject letters with multiple signatures. Google and Microsoft can't validate them when receiving. It's more that a few common implementations lack the support for them so you can't use _just_ Ed25519.

Everyone has to be onboard before the switch can be made, and not everyone is happy about the somewhat messy solution of running dual-stack RSA+Ed25519 setups in the interim - it's a bit different than e.g. supporting multiple methods for key exchange or multiple ciphers for symmetric crypto. It's just one of those things that take time to happen.

> What’s blocking it for DKIM uniquely?

Mail server administrators.

Larger keys won't make the algorithms quantum-safe either.

It's not quantum-broken though, it might just make it a bit faster. Just half a Dyson sphere.

> IMO this is not a valid excuse.

The world is full of things that aren't "valid excuses". Explaining why something is the way it is is not the same as justifying it.

Altering headlines automatically is really irresponsible.

It should achieve the same level, yes. It's not exactly described what could attack it. Right now it seems that 2048-bits would be the last allowed step and they're not going to push people past 2048, they want to phase out RSA in general.

Counterproductive how and to what/whom? For the sake of keeping DNS TXT entries and e-mail headers compact? Would you stand by this statement also in the context of a certificate authority's root signing key, or an RSA host key for an ssh daemon?

Yep, the formula is a bit complicated, it comes from the general number field sieve (GNFS) algorithm, you can find some equivalences online between symmetric key algorithms and RSA and 23 bits seems about right. I have also seen lists where they give RSA-512 64 bits and RSA-1024 80 bits, just a 16 bit difference, but it looks a bit arbitrary to me. I think the NIST doesn't even look at RSA-512 anymore, as it is definitely broken, it only starts at 1024.

A RSA key is the product of two primes, not any number, so you need a lot more bits to get equivalent security to, say, AES. That's also a reason for elliptic-curve cryptography, which needs a lot less bits than RSA for the same level of security.

Yes, so you use multiple strings (in a single record) if you need longer values:

"first 255 bytes" "second 255 bytes" "etc"

DNS clients combine the 255-byte strings back into a single string.

> The UK government also has several huge arm based solutions dedicated to cracking internet encryption, zero chance that isn't breaking mostly everything, for sure the Chinese and Russians have similar.

So you seriously think that almost all current RSA is being decrypted in real time by at least UK, China and Russia (and I would assume US)? Do you have any source or reference for this at all?

>There are several open source GNFS tools that can do 1024 very efficiently on GPUs, ...

Reference? Why has no one demonstrated this?

Yet nobody is collecting the RSA-numbers bounties?

RSA-270 (much, much easier than 1024 compute-wise) has a bounty of $75k, why would it be unclaimed then when you can spend three years worth of cloud rented H100 (I'm being conservative here and count $3/h which is far from the best deal you can get) and still make a profit?

Also a GPU core and CPU cores really aren't comparable individually, so your “consumer graphic card having thousands of core already” is comparing apples to oranges.

Those service providers have had plenty of time to migrate to 2048 and most of them have already.

> a "tragicomic" tendency to forget mankind's unstoppable progress

When it comes to compute, it's no faster than Moore's Law, which means roughly one bit of symmetric encryption every two years.

> and we've been heading down this path for decades at an exponentially increasing pace.

Given that the encryption security is itself exponential in bit length, we are in fact heading down this path linearly! (A doubling in compute power means the ability to crack twice as hard cryptosystems, which means ones that have 1 bit more of security).

Key must be extended over time, and they are, and have been for decades. A PoC of an attack of a security system broken since 1999 should be treated exactly like how we are amazed at little computing power was available to the Apollo program: this is a cool bit of trivia that shows the growth of available computing power, but not a display of any kind of security issue.

Oh excellent. I didn't realize rfc6376 had been superseded.

> If you crack someone's key, they might be well within their rights to pursue a criminal prosecution.

If that were true there would be no market for white hat hackers collecting bug bounties. You need to be able to demonstrate cracking the working system for that to be of any use at all. No company will listen to your theoretical bug exploit, but show them that you can actually break their system and they will pay you well for disclosure.

They can pursue what they want, it doesn't mean it will go through.

Looking at public data, using some other public knowledge to figure out something new does not make it inherently illegal. They didn't crack it on their systems, they didn't subvert it on their systems, they did not use it against their systems. I'd love to see some specific examples under what it could be prosecuted under specifically. Because "that door doesn't actually have a lock" or "the king doesn't actually have clothes" is not practically prosecutable anywhere normal just like that.

Especially in the EU, making such cryptographic blunders might even fall foul of NIS2, should it apply to you.

In general this also quickly boils down to the topic of "illegal numbers" (https://en.wikipedia.org/wiki/Illegal_number) as well.

> showing "hey it fits"

That's exactly what I meant in terms of not actually doing anything with the result. That said, it's obviously somewhat different with a physical key than a cryptographic key.