Cracking a 512-bit DKIM key for less than $8 in the cloud
432 comments
·January 8, 2025jgrahamc
matthewdgreen
For a number of years it was (non-officially) thought to be a feature to use weak DKIM keys. Some folks argued that short keys allowed you to preserve deniability, since DKIM signatures would only be short-lived and nobody would be able to use DKIM signatures to prove that any email was authentic. (I’m not saying that this is why most companies used short keys, just that there was a general view that short keys were not all bad.)
DKIM deniability is a particular hobbyhorse of mine [1]. These short keys are obviously not the way to achieve it, but I view this kind of thing as a result of the muddled thinking that’s been associated with DKIM and the community’s lack of desire to commit to the implications of an all-email signing mechanism.
[1] https://blog.cryptographyengineering.com/2020/11/16/ok-googl...
linsomniac
I forget where but someone proposed regularly rotating your DKIM key and publishing old keys for deniability. So you can still use strong keys and provide a level of deniability.
jabart
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.
rsc
In the link in the parent comment. :-)
Ar-Curunir
That was Matt Green, the person you replied to =)
ryan-c
I've been doing this since around 2018, and have seen a few others implement it.
matja
I don't think this rationale is correct. DKIM doesn't authenticate a user, since the user doesn't the private key - DKIM authenticates that the MTA knows the private key on behalf of the domain owner, which isn't necessarily the users using that domain to send email.
What's more dangerous is that a jury wouldn't know the difference.
JackSlateur
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 :( ).
password4321
For 20 years Fastmail allowed any customer to spoof From: another
GTP
Isn't deniability at odds with DKIM's goal? What would be the point of setting DKIM then? Sure, it helps with spam scores. But most companies rely on a major email provider to send emails, so maybe they wouldn't have deliverability issues anyway?
tptacek
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.
CodesInChaos
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.
matthewdgreen
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.
ralferoo
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.
marcosdumay
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.
dfc
You should read the blog post Prof. Green linked to. All of your questions are addressed there.
lupusreal
Meanwhile in the real world, screenshots of emails without any cryptographic authentication at all are good enough to send people to prison.
tptacek
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.
reaperman
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.
anonym29
I absolutely believe you - lawyers, judges, and juries alike tend to be technologically illiterate, but do you have any references/links to this happening?
rstuart4133
From the blog:
> The fix would cost you basically nothing, and would remove a powerful tool from hands of thieves.
Maybe that was true a while ago, but it becoming much less true now. Most people and organisations outsource the email handling to the likes of Google and Microsoft. They tend to reject email that isn't DKIM signed, and add a "DKIM validated" header to those that are. "Tend" is probably too weak a word now - email that isn't signed isn't likely to be delivered.
So the mostly likely scenario now is "someone steaks email that can no longer be DKIM validated, but it is possible prove it was DKIM validated when it was received". If that's true rotating keys doesn't help.
tptacek
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.
phkahler
What's the problem with verifiable email? You can just delete old emails (if gmail or whoever archives them that's another problem). Most people probably operate under the assumption that email is verifiable in some way anyway. If you receive malicious email, isn't it a good thing to be able to verify where it came from? Doesn't that benefit senders and receivers alike? Or is this a case of "I want to verify you, but I don't want you to verify me"?
infogulch
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.
null
brightball
Reminds me of the story of a guy cracking one thinking it was a Google headhunting challenge.
https://www.wired.com/2012/10/dkim-vulnerability-widespread/
raverbashing
> "Keys of 512 bits have been shown to be practically breakable in 1999 when RSA-155 was factored by using several hundred computers and are now factored in a few weeks using common hardware."
So we went to a few weeks to 8h in 14 years give or take
bee_rider
86 hours. 8 dollars. I wonder how scalable it is. They only used:
> We chose a server with 8 dedicated vCPUs (AMD EPYC 7003 series) and 32 GB of RAM from Hetzner
Not very beefy really. Beating this time is easily in range of, what, millions of people high end gaming machines?
andix
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.
raverbashing
> 86 hours
I stand corrected
null
chias
86h, wasn't it? But regardless your point stands.
ryan-c
I'm pretty sure I can do it in two hours.
stingraycharles
Just as an interesting FYI for those who care: the parent poster is the CTO of CloudFlare.
codegladiator
Your blog got a mention in the comments of http://www.wired.com/threatlevel/2012/10/dkim-vulnerability-...
null
littlestymaar
First time a 512-bits RSA number (RSA-155) was factored was in 1999!
dusted
If you want to try something fun:
Provision a 4096-bit DKIM key.
Every online DKIM/SPF checker will say all is good when looking at your DNS.
They will also fail any test email you send, with more or less excellent descriptions such as:
STATUS: Fail
DKIM: Pass
SPF: Pass
There's this fun thing that, apparently:
It's permitted and valid to use keys larger than 2048 bits in your DKIM entry.
It is not, however, required to process keys larger than 2048 bits.
This cost me some hair to learn the hard way.
dusted
Addendum: You need to set a strict dmarc policy for the checks to fail. Interestingly, the sites will tell you all three are correct and valid, but still fail the mail.. This is probably due to different pieces of software doing the dns record checking and the email validation.
maxed
The latest RFC does require it though (RFC8301):
Verifiers MUST be able to validate signatures with
keys ranging from 512 bits to 2048 bits, and they MAY be able to
validate signatures with larger keys.
Twirrim
Unfortunately MAY is not MUST. When it comes to RFCs, it's all too common that people won't implement MAYs, and you should operate expecting that. I wouldn't trust any key over 2048 bits to work.
maxed
Sorry, I somehow made a typo in the quoted text, the RFC says
Verifiers MUST be able to validate signatures with keys ranging from 1024 bits to 4096* bits
Havoc
Could someone help me understand why we're not dramatically ramping up key sizes across the board on all encryption? Not as a solution, but as a buy-some-time measure.
Compute is rapidly increasing, there is continuous chatter about quantum and yet everyone seems to be just staring at their belly buttons. Obviously bigger keys are more expensive in compute, but we've got more too...why only use it on the cracking side, but not on defense?
Even simple things like forcing TLS 1.3 instead of 1.2 from client side breaks things...including hn site.
JackSlateur
Old but still relevant: https://www.schneier.com/blog/archives/2009/09/the_doghouse_...
These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.
nmadden
That’s true for AES-256. But brute force attacks are not the most efficient way to attack RSA, so it’s not true in that case. (Eg quantum computers would break RSA-4096 but not AES-256).
ironhaven
Grover’s algorithm could be described as quantum brute force that is able to break AES-128 but not AES-256
tptacek
We are. 1024-bit keys are being retired across cryptosystems everywhere, and have been for over a decade (don't get me started on the one laggard). Nothing threatens 2048 bit keys other than QC, which threatens RSA altogether. Progress isn't linear; it's not like 2048 falls mechanically some time after 1024 (which itself is not practical to attack today).
sedatk
People might be assuming that 2048-bits is only twice as strong as 1024-bits, but it's in fact a billion times better. (corrected, thanks!)
AlotOfReading
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.
1oooqooq
we are definitely not.
most countries registrar's won't support DNS hacks requied for larger dkim.
we still use the minimum key size in most countries.
Avamander
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.
daneel_w
Probably because RSA 2048 is not yet broken, and once there we still have RSA 4096 to lean back on which is since quite some time the most common key size for most things using RSA (DKIM being one of the exceptions).
In the context of DKIM we're waiting for Ed25519 to reach major adoption, which will solve a lot of annoyances for everyone.
throw0101c
> Probably because RSA 2048 is not yet broken […]
3072 has been recommended by various parties for a few years now:
jandrese
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.
bluGill
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.
upofadown
But perhaps with not a very solid justification to do so:
daneel_w
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.
woodruffw
Ed25519 has seen broad adoption in TLS and other stacks that are used pervasively where DKIM is also used. What’s blocking it for DKIM uniquely?
(This isn’t intended as a leading question.)
Avamander
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.
daneel_w
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.
paulnpace
> What’s blocking it for DKIM uniquely?
Mail server administrators.
Suzuran
Because the only way to force their use is to break things, mostly this means transferring the pain directly to the user instead of the service operators in the hope that they will bitch loudly enough for the service operator to care, and this has a good chance of instead causing the user to move to your competitors instead, who will be more than willing to not let a little thing like security get between them and revenue.
elif
512 DKIM was exceedingly rare even 8 years ago when I worked in email.
You're essentially asking "why aren't we doing what we're doing"
hannob
"dramatically ramping up key sizes" is not done, because it's overly expensive, and not needed.
What people don't realize: key size recommendations are surprisingly stable over long timeframes, and have not changed for a very long time. In the early 2000s, some cryptographers started warning that 1024 bit RSA is no longer secure enough, and in the following years, recommendations have been updated to 2048 bit minimum. That's now been a stable recommendation for over 20 years, and there's not the slightest sign that 2048 bit can be broken any time soon.
The only real danger for RSA-2048 is quantum computers. But with quantum computers, increasing your RSA key sizes does not buy you much, you have to move to entirely different algorithms.
Avamander
> That's now been a stable recommendation for over 20 years, and there's not the slightest sign that 2048 bit can be broken any time soon.
Except that now the recommendation by NIST at least is to switch to 2048-bit by 2030 and then deprecate RSA altogether by 2035.
But yeah, not being on at least 1024-bit RSA is weird and careless.
marcosdumay
The key sizes we use today are expected to hold against a Dyson sphere focused on breaking them with the best exploit we know today.
What size do you suggest?
RobotToaster
It's not quantum-safe though.
marcosdumay
Larger keys won't make the algorithms quantum-safe either.
Avamander
It's not quantum-broken though, it might just make it a bit faster. Just half a Dyson sphere.
littlestymaar
> Could someone help me understand why we're not dramatically ramping up key sizes across the board on all encryption? Not as a solution, but as a buy-some-time measure.
We've been doing it for decades now… (DES used 56bits back then, AES started at 128).
Also, keep in mind that increasing the key length by 1 means that you need twice as much compute to crack it through brute force (that is, unless cryptanalysis shows an attack that reduces the difficulty of the scheme, like for instance with the number field sieve on RSA) so you don't need to increase key size too often: following Moore's law, you need to increase it by on bit every two years, or 5 bits every decades. Additionally key size generally account for many years of compute progress and theoretical advance, so that you really don't need to worry about that over a short period (for the record higest RSA factorization to date is 829 bits, yet people started recommending migration away from 1024 bit RSA a decade ago or so, and the industry is in the process in deprecating it entirely even though it's probably going to take years before an attack on it becomes realistic.
bmenrigh
CADO-NFS makes this surprisingly easy to do. A few weeks back I factored a 512bit RSA DKIM key for work using my desktop computer in only 28 hours. Specifically, an AMD Zen 5 9900X.
Unfortunately 1024 bit keys are still out of reach of a hobbyist effort but could be pulled off by academics roughly of the same scale as the 2010 effort to factor a 768 bit key (https://eprint.iacr.org/2010/006.pdf)
fortran77
I got an email from Bank of America yesterday about a problem setting up my account. I had set up a new account, and this email knew that, and knew the name of the company, etc. There were no links in the email, just a note to call the BofA business number. I verified the number on the BofA website -- it was the same number -- and I called them.
They couldn't tell me why I got the email, and what the problem was with my account. The representative couldn't see a record of this email set.
I'm 100% certain this email came from Bank Of America. There was nothing in the email that was phishing -- no links, no bad phone numbers.
The SPF, DKIM, and DMARC all passed googles's ARC-Authentication-Results. The DKIM key is 2048 bits long.
I asked Bank of America to investigate, and they said "it must have been a phishing message" and sent me a link on how to look out for phishing.
I'm pretty sure this was just a glitch; some system that does some consistancy check ran too early while the account was being set up and generated that email.
However, because they told me it was "phishing" I just sent a FedEx to the CTO with the complete paper trail advising them that EITHER their DKIM keys were compromised and they need to issue a public warning immediately OR their incompetent staff and IT system gave me the runaround and wasted an hour of my time. Either way, I want a complete investigation and resolution.
zelphirkalt
Some DNS providers suck and only let you set 1024 bit long keys. For example wordpress.com.
littlestymaar
1024 is still many orders of magnitude hard to crack than 512. For the record, the last RSA number having been broken was RSA-250 (829 bits) and it took 2700 core-years to crack back in 2020[1]. In comparison, RSA-155 (512 bits) was factorized as early as 1999!
You aren't in danger.
[1]: https://sympa.inria.fr/sympa/arc/cado-nfs/2020-02/msg00001.h...
DarkmSparks
There are several open source GNFS tools that can do 1024 very efficiently on GPUs, and even cheap consumer GPUs have 10s of thousands of cores now, even by your measure "2700 core-years" is only around a month or so on a single consumer grade GPU.
Not "free", but any malicious actor has access to a lot more than a single GPU.
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.
SahAssar
> 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?
littlestymaar
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.
upofadown
>There are several open source GNFS tools that can do 1024 very efficiently on GPUs, ...
Reference? Why has no one demonstrated this?
daneel_w
You and I aren't the ones in immediate danger. The service providers we rely on are. In discussions like these we have a "tragicomic" tendency to forget mankind's unstoppable progress. RSA-1024 offers 80 symmetric equivalent bits of security and we've been heading down this path for decades at an exponentially increasing pace.
littlestymaar
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.
null
Avamander
Yikes. NIST wants to forbid even 2048-bit RSA by 2035, because it doesn't offer a good enough security level.
tptacek
2048 achieves the same security level NIST requires from AEADs, doesn't it? What plausibly attacks it? Pushing people past 2048 seems counterproductive.
Avamander
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.
daneel_w
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?
GuB-42
RSA-1024 seems to be about 8 million times better than RSA-512, so cracking that would be $64 million in compute.
Not NSA-proof, but should be more than enough to keep spammers out, especially considering that DKIM is just one layer of protection.
upofadown
That's just the extra compute required. There is a large increase in required memory that needs to be quickly accessible in a particular way. One estimate I saw claimed that breaking 1024 bit RSA would take more than 2 billion dollars over a period of years.
zahlman
512 extra bits of key only gets you 23 bits of entropy?
GuB-42
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.
null
mjl-
DKIM records are just DNS TXT records. Do they have a limit on the size of TXT records? Or are they going out of their way to try to parse the TXT records you're adding that look like DKIM records, failing on them, and then refusing to add them?
colmmacc
Breaking a 512-bit key for a good demonstration is very valuable security research, even if it's been done before. It's also legit to call out "Hey, here's a list of folks still using 512 bit, they should move off." ... but for me, actually cracking a real-world in-use key crosses an ethical line that makes me uncomfortable. IANAL but it might even be criminal. Just seems a bit unnecessary.
phoe-krk
> for me, actually cracking a real-world in-use key crosses an ethical line that makes me uncomfortable
They've contacted the company with the vulnerability and resolved it before publishing the article - search the original article for the substring "now no longer available".
Usually, you demonstrate that an online system is vulnerable by exploiting that vulnerability in good faith, documenting the research, and submitting it for review. It does not matter if you're cracking an encryption scheme, achieving custom code execution for a locked-down game console, proving that you can tamper with data in a voting machine, or proving that you can edit people's comments on a Google Meet Q&A session - the process is the same.
If you say something's vulnerable, people can shrug it off. If you say and prove something's vulnerable, the ability to shrug it off shrinks. If you say and prove something's vulnerable and that you'll publish the vulnerability - again, using the industry standard of disclosure deadlines and making the vulnerability public after 60-or-so days of attempting to contact the author - the ability to shrug it off effectively disappears.
colmmacc
I read the article, and I don't think it changes it. If you crack someone's key, they might be well within their rights to pursue a criminal prosecution. Of course it would also have a Streisand effect and there's reasons not to, but I personally wouldn't allow or recommend a security researcher to do it. It's needlessly risky.
In general, subverting security and privacy controls tends to be illegal in most jurisdictions. Best case is when you have clear permission or consent to do some testing. Absent that there's a general consensus that good faith searching for vulnerabilities is ok, as long as you report findings early and squarely. But if you go on to actually abuse the vulnerability to spy on users, look at data etc ... you've crossed a line. For me, cracking a key is much more like that second case. Now you have a secret that can be used for impersonation and decryption. That's not something I'd want to be in possession of without permission.
alt227
> 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.
Avamander
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.
mmastrac
Breaking a key isn't criminal. It's just math. Sending emails that would constitute fraud or a violation of another jurisdictional law, relying on that math, is illegal. But again -- it's not the math, it's the action and intent.
Pointing out that someone is doing something stupid is also not illegal, though they make try to make your life painful for doing so.
colmmacc
Secrets themselves are often regarded as sensitive information, and often also categorized in the highest classifications for information protection. This stuff isn't just a game, and in my experience it's not how law enforcement authorities or courts see things.
Just as if you made a copy of the physical key for a business's real-world premises, you could well find yourself in trouble. Even if you never "use" it.
yellow_lead
You can say this about a lot of security research, i.e "Showing a bug is exploitable is one thing, but writing a POC is crossing the line!" The problem is that most people won't listen to your security research unless you demonstrate that something is actually possible.
croemer
They only called out 1 out of the ~1.7k domains they found with keys shorter than 1024bits.
They _did_ call out the 3 of 10 tested major email providers that don't follow the DKIM RFC properly: Yahoo, Tuta, Mailfence (after having notified them).
Tutanota
Actually, we did not get notified, but we did see this message - so thanks! We have now fixed the issue and the fix will go live in the next days.
Matthias, co-founder of Tuta Mail
michaelmior
I am also not a lawyer, but I would suspect it's not criminal to crack a real-world in-use key if you do so using only publicly available information and you don't actually do anything with the result.
colmmacc
Let's say you local coffee shop is featured in a local news piece and the blithe owner happened to get photographed holding the store key. That's now easy to clone from public information. Would you be comfortable actually doing it? Reporting the issue is fine - "Hey you should rekey your locks!".
Actually making a clone of the key, and then showing "hey it fits" will get you more traction more quickly ... but there's also plenty of Police Departments who might well arrest you for that.
michaelmior
> 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.
tptacek
I don't think there's a way to make it criminal, any more than publishing a vulnerability that got you code execution on their servers could be. Actually exploiting it, of course, would be.
colmmacc
I think many in cryptography would see cracking a key as a precondition to "actually exploiting it" ... because you've only gotten a cryptographic secret, not "actual data".
But I think many others, and many in law enforcement, will see cracking a key as "actually exploiting it". You've exploited the cracking vulnerability to target a particular key, is how they'll see it. Law enforcement also have a natural incentive to want possession of harm-adjacent paraphernalia to carry substantial liability.
I think they have a point; that key is private data, and there's a reason people lock keys up in KMSs and HSMs; they can have a large blast radius, and be hard for companies to revoke and rotate. Importantly, a compromise of a key will often trigger notification requirements and so now it is a breach or an incident, in a way that a good faith security vulnerability report is not.
To make an extreme example; if you were to crack an important key for a government agency, good luck with that is all I'll say. I sure wouldn't.
tptacek
The US law most at play in criminal prosecution of computer usage is CFAA, and a clear CFAA predicate is intentional access to a protected computer (18 USC 1030(a)(2)). This distinction is what makes vulnerability research on things like Chrome vulnerabilities generally safe (as long as you don't knowingly spirit exploits to people who are actually attacking people), while vulnerability research on other people's websites (looking for SQLI and SSRF) is risky.
The CFAA has a clause about "trafficing in passwords or similar information" (18 USC 1030(a)(6)), but the mental state requirements are very high: that trafficking has to be knowing and with intent to defraud (that intent will be something prosecutors will have to prove at trial).
There might be some state law somewhere that makes this risky, but virtually every hacking prosecution in the US anyone has heard of happens under CFAA. I'm not a lawyer, but I've spent a lot of time with CFAA, and I think cracking DKIM keys is pretty safe.
cafeinux
As mentioned in the article, the key's no longer available and I presume the article has been released only after responsible disclosure was done and with the approval of the key owner (hope so). At this point, it's not more unethical than any other security research performed in the same conditions and with the same outcome.
prophesi
This is the reason I had to stop using Hover for DNS management. They don't support TXT records longer than 255 characters, and I've not found any instance of someone getting split records to work with Hover. Ended up using Digital Ocean for it. I would love for elliptic curve crypto to become the status quo if this is going to continue to be an issue for yet another decade.
dizhn
> Although most providers correctly identified the 512-bit key as insecure and rejected our DKIM signature, three major providers — Yahoo Mail, Mailfence, and Tuta — reported a dkim=pass result.
Did google really FAIL because of DKIM signature being insecure or because SPF failed?
austin-cheney
In case anybody is wondering about whether the 512bit number is big or small it depends on whether it is symmetric or asymmetric encryption technique. Always presume asymmetric encryption is 8x weaker than symmetric encryption.
DKIM is asymmetric. So a 512bit DKIM equivalent symmetric hash would be 64bits, which is long broken. Even 160bit SHA1 is considered broken. A DKIM of roughly equivalent strength to a 512bit SHA3 would be at least 4096bits and still does not include SHA3's techniques for mitigating replay attacks.
bmenrigh
DKIM is not an encryption algorithm. It is a standard for embedding and validating signatures in email headers.
Unfortunately DKIM only supports rsa-sha1 and rsa-sha256 signatures (https://datatracker.ietf.org/doc/html/rfc6376/#section-3.3). It'd be nice to see DKIM get revised to allow Ed25519 or similar signatures.
Avamander
Ed25519-SHA256 support has existed for a while now.
bmenrigh
Oh excellent. I didn't realize rfc6376 had been superseded.
austin-cheney
Wikipedia says it is a correlation check based upon a public key based signature. How is that not a form of encryption? Google says encryption is a process that scrambles data into a secret code that can only be decoded with a unique digital key, which is exactly what public keys are for.
dist-epoch
> Always presume asymmetric encryption is 8x weaker than symmetric encryption.
RSA encryption is 10x weaker than Elliptic curve (224 bits ECC ~= 2048 bits RSA). Both are asymmetric.
Alternatively, asymmetric Elliptic curve is as strong as AES symmetric encryption. But it's quantum vulnerable, of course.
kingforaday
Love the practicality demonstrated here. It is unclear how old this article is. Based on the poster's previous submissions, I assume today?
awulf
I published the article today, though it was written a few months ago (when the DKIM record was still online).
philipwhiuk
Was redfin aware you were trying to break their DKIM record?
Avamander
It was already broken.
This comment also serves as a public notice that I'm going to factor all the 512-bit DKIM RSA keys out there from now on. Start migrating.
supernova87a
This is a little bit of a layman's question but maybe someone is interested:
When people go searching for prime numbers / bitcoin with massive compute, I assume that there are huge libraries of "shortcuts" to reduce the searching space, like prime numbers only appear with certain patterns, or there are large "holes" in the number space that do not need to be searched, etc. (see videos e.g. about how prime numbers make spirals on the polar coord. system, etc). I.e. if you know these you can accelerate/reduce your search cost by orders of magnitude.
For whatever various encryption algorithm that people choose to test or attack (like this story), is there somewhere such libraries of "shortcuts" are kept and well known? To reduce the brute force search need?
And is the state of sharing these to the point that the encryption services are designed to avoid the shortcut vulnerabilities?
Was always wondering this.
tomesco
There exist certain classes of prime numbers that should not be used for some cryptographic operations because algorithms exist that reduce the computation required for factoring attacks. This more often applies to cases where smaller primes are applied. Sources for this king of knowledge are mathematics or cryptography textbooks.
For other cryptographic operations, almost any sufficiently large prime can be used. Even a 50% reduction on a computation that will take trillions of years, has no practical impact.
cryptizard
That's not really how it works. There aren't any noticeable patterns in prime numbers (besides trivial ones like they are all odd numbers) and they remain dense (no big gaps) even for very large numbers like what are used in RSA. The best algorithm for generating prime numbers is to just pick a really big random odd number and then test if it is prime, repeat until you find one.
Now, factoring large numbers is a separate thing. You don't brute force all the possible factors, that would be a really bad approach. Modern algorithms are called "sieves," this is a gross oversimplification but essentially they keep picking random numbers and computing relations between them until they come up with enough that have a certain property that you can combine them together to find one of the factors. It doesn't have anything to do with shortcuts or patterns or tricks, it is just a fundamental number theory algorithm.
Me writing over 14 years ago: https://blog.jgc.org/2010/06/facebooks-dkim-rsa-key-should-b... This was doable 14 years ago for 512-bit keys.