16 ms·
Cracking a 512-bit DKIM key for less than $8 in the cloud
- dspillett 2y agoHow common are such small DKIM keys? I'm pretty sure mine are 2048-bit, though I'd have to check as they were last set a fair while ago.
- daneel_w 2y agoNot common. 1024-2048 bit RSA is the most common DKIM scheme. It's been 6 years since Ed25519 was labeled "required" in a drafted RFC, but adoption is as usual taking an unfortunately long time.
- sva_ 2y agoFirst sentence: > In our study on the SPF, DKIM, and DMARC records of the top 1M websites, we were surprised to uncover more than 1,700 public DKIM keys that were shorter than 1,024 bits in length
- unwind 2y agoSo 1,700 out of 1,000,000, i.e. around 0.2%. "Not common" is one way of putting it, I guess.
- croemer 2y agoThose 1,700 are easy to find though, just need to dig a bunch of domain names and you'll find plenty vulnerable ones that you can spoof. Yahoo Mail has a market share on the order of 3%. So a black hat could then target a decent chunk of users with @yahoo addresses specifically. Has anyone heard of this being exploited in the wild? Would be interesting to find out whether there are some reputable domains among the 1.7k vulnerable ones.
- elif 2y agoYour claim that yahoo uses a 512bit key are counterfactual. Please adhere to honesty and good faith arguments.
- croemer 2y agoI never suggested that Yahoo uses 512bit keys, that's a misunderstanding. The article clearly states that Yahoo is one of the 3 clients that didn't reject 512bit keys the way they should per RFC. Yahoo Mail inbox users are vulnerable _receivers_ of spoofed emails.
- 1oooqooq 2y agoremember when yahoo mail was the first one to implement DKIM validation and then all mailing list owners added a footer telling their subscribers not to use yahoo mail because it was broken, instead of calling their mailing list providers to upload a key? yeah nobody remembers, but yahoo probably do. i doubt they will err on the side of security again.
- jaza 2y agoThe Yahoo that built Yahoo Mail no longer exists, so actually they probably don't remember.
- awulf 2y agoI agree, but to be precise, it was 1,726 out of 476,617 DKIM keys found across those 1M domains, or about 0.36%. Since it's impossible to determine all DKIM records a domain might have from the outside, I used a list of commonly used selectors (e.g., "default' or 'key1") for the search. It's likely there are additional short keys under selectors I didn't check.
- philipwhiuk 2y agoThe top million domains are more likely to be on top of their security than less prominent domains. 0.2% is therefore a fairly strict lower bound for the overall internet.
- mrweasel 2y agoThe interesting question is: Did these sites forget that they have these records, or have they perhaps forgot how to rotate their keys.
- 1oooqooq 2y agodns server limitations. txt records are 1024bits... add the prefix for the key and you get <1024. to use a larger key you must combine many txt records in a never ending comical interoperability issues. the first one usually being that your regional monopoly scoundrel, a.k.a. registrar, run a server which doesn't even allow more than one entry.
- kbolino 2y agoTXT records are 255 bytes or 2040 bits. This is plenty of space to support RSA-1024 keys even with a small prefix and after base64 encoding them. However, it is obviously not enough to support RSA-2048 which is the minimum recommended size according to NIST right now. It's also not quite enough even for RSA-1536 (not widely used) due to base64 expanding the key by 33%. There actually is a standard for adding more than 255 bytes to a TXT record and it's fairly widely supported, but it can be tricky to configure properly on a name server.
- dspillett 2y ago> but it can be tricky to configure properly on a name server. I wouldn't say it is tricky with a good name server: for instance with bind just split the value into multiple quoted strings and it'll do the rest¹. Though while it is well known, it doesn't seem to be well documented away from many forum posts discussing the matter: after a little searching I can't find reference to the issue in bind documentation or relevant RFCs. The RR format allows RDATA to be longer than 255 octets (RDLENGTH is an unsigned 16-bit value, not 8-bit) so presumably the limit is imposed by the zonefile format. The only reference to 255 octet limits in RFCs 1034 & 1035 is the length of a full name (with individual labels making up a name being limited to 63 octets). Of course many UIs for editing zone files or other stored RR information, or other DNS management interfaces, might implement longer RDATA support in a worse way or not support longer RDATA values at all. ---- [1] I'm not sure what “the rest” is (I might look deeper later)
- dspillett 2y agoI must do something about my short-term memory/attention. I must have read that and promptly blanked it during the scanning of the rest of the article.
- bell-cot 2y agoTechnically, this is very nice work. But as a security generality - email is vastly less secure* than human nature wants to assume that it is. Human nature usually wins. *Outside of a carefully run org's own network, and a few other edge cases
- xmodem 2y agoYeah, so I guess there's no point in picking any of the low hanging fruit to make it more secure.
- sam_lowry_ 2y agoEmail is actually quite secure, just in a different way that web. For instance, once you disregard so called transactional mail and spam, real email is almost all encrypted for all practical purposes. DKIM and DMARC also work quite well for spoofing protection, aside from the corner cases like the above. Average Software Engineers have an outdated idea of email, formed by 1990 era Internet.
- tredre3 2y agoI think your view of email is romanticized, or perhaps skewed because of your social circle. Email servers sometimes use TLS to talk with eachother, and emails are signed. But that's the extent of encryption when it comes to "real email". Email content is not encrypted in "almost all" of "real email" because almost nobody uses PGP.
- sam_lowry_ 2y agoI don't know what social circle I should be part of to consider email unsecure. Even Russian spies use mail.ru and their emails are compromised not by SMTP MitM but by weak passwords, google for "moscow1 moscow2 password" to see what I am talking about ) Anyway. Back to the technical point. Email servers pretty much always use TLS to talk to each other. The connection may degrade to non-encrypted for backwards compatibility, unlike HTTPS. But it's vanishingly rare. So, for all practical purposes that affect ordinary citizens: injection, scanning and sensitive information extraction, email in transit is quite secure.
- zelphirkalt 2y agoSome DNS providers suck and only let you set 1024 bit long keys. For example wordpress.com.
- Avamander 2y agoYikes. NIST wants to forbid even 2048-bit RSA by 2035, because it doesn't offer a good enough security level.
- tptacek 2y ago2048 achieves the same security level NIST requires from AEADs, doesn't it? What plausibly attacks it? Pushing people past 2048 seems counterproductive.
- Avamander 2y agoIt 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 2y agoCounterproductive 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?
- tptacek 2y agoThere is no plausible threat to 2048, but you'd still rather people switch off RSA, either to curves (because they're more resilient) or to lattices (for post-quantum). Pushing people to higher RSA key sizes is a waste of effort.
- littlestymaar 2y ago1024 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.html https://sympa.inria.fr/sympa/arc/cado-nfs/2020-02/msg00001.h...
- Havoc 2y agoCould 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.
- Suzuran 2y agoBecause 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.
- bananapub 2y ago> why we're not dramatically ramping up key sizes across the board on all encryption? because no one thinks there is a reason to, no one has any fear that classical computers will catch up with RSA-2048/AES-128 before their grand children are dead. post-quantum crypt stuff is happening and people are planning how to migrate to it.
- EVa5I7bHFq9mnYK 2y agoWell, even MD4 hasn't been cracked yet.
- kbolino 2y agoWhat is your definition of cracked? Collisions are easy to produce; there's one right on the Wikipedia page.
- 2y ago
- jgrahamc 2y agoMe writing over 14 years ago: https://blog.jgc.org/2010/06/facebooks-dkim-rsa-key-should-be.html https://blog.jgc.org/2010/06/facebooks-dkim-rsa-key-should-b... This was doable 14 years ago for 512-bit keys.
- begueradj 2y ago2010, Nostradamus :)
- jgrahamc 2y agoDepends if you're rounding up or down.
- deleted 2y ago[deleted]
- raverbashing 2y ago> "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
- chias 2y ago86h, wasn't it? But regardless your point stands.
- bee_rider 2y ago86 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 2y agoI'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.
- qwertox 2y agoBecause we need that compute for our React frameworks.
- deleted 2y ago[deleted]
- halfmatthalfcat 2y ago[flagged]
- jacob019 2y agoWell, backend is our precious server resources and front end resources belong to the lowly user. It's a matter of scale though, frontend is optinized for one concurrent user. Plenty of small websites using slow and bloated frameworks on the backend because it's easy.
- masom 2y agoSimple economics; who pays for the servers and who pays for the front-end execution? Front-ends are essentially free distributed computing resources while the backends need to be paid for.
- lelandfe 2y agoI have stopped mentioning frontend performance being my speciality on interviews as it has elicited tepid responses from all but one.
- xohails 2y ago[flagged]
- viviansolide 2y agoThanks for this
- kingforaday 2y agoLove the practicality demonstrated here. It is unclear how old this article is. Based on the poster's previous submissions, I assume today?
- awulf 2y agoI published the article today, though it was written a few months ago (when the DKIM record was still online).
- philipwhiuk 2y agoWas redfin aware you were trying to break their DKIM record?
- Avamander 2y agoIt 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.
- TheChaplain 2y agoAnyone know or have experience how well supported ECDSA is for DKIM?
- paulnpace 2y agoDKIM supports Ed25519-SHA256. https://datatracker.ietf.org/doc/html/rfc8463 https://datatracker.ietf.org/doc/html/rfc8463
- asim 2y agoI think the cynic in me says "so what" mostly because dkim as an ancient technology is hardly secure. I don't think we're any less prone to email fakery and spam. I'd be interested to see a possible new solution or a revamping of email as a protocol but that's unlikely. We're more likely to keep it like snail mail as we prioritise different forms of communication. Unfortunately nothing has beat the universal email address on the internet. Here's hoping we come up with a chat standard that sticks and people run a user@server.com chat server where you can communicate from anywhere. Sorry xmpp, you don't count.
- alt227 2y agoYou hit the nail on the head with the word 'Universal'. Because email addresses have existed since the begining of the web, anyone who has ever been on the internet has one and uses it for identification purposes. This will not change without another universal standard which everybody automatically has. Its like IPv4, we all have the ability to use IPv6 but do we? Hell no we just use NAT as its an easier quick fix. Changing any addressing on the internet is tough because you always have to have backwards compatibilty, which kind of ruins the point of moving forward.
- lazide 2y agoHaha, definitely not true outside of the US and Western Europe. Most of Asia (and probably Africa) uses phone #.
- alt227 2y agoThats because those are mostly developing countries which were late to the internet party, and are accessed mainly through mobile. Phone # could well be a replacement for email globally in the future, once all the younger generation grow up and rule the world.
- lazide 2y agoUsers in those countries already vastly outnumber users in other countries. And are growing much, much faster too.
- jedisct1 2y agoThat can be done locally on a laptop, no need for the cloud.
- colmmacc 2y agoBreaking 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.
- michaelmior 2y agoI 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 2y agoLet'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 2y ago> 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.
- phoe-krk 2y ago> 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.
- DarkmSparks 2y ago"as RSA keys shorter than 1,024 bits are considered insecure, and their use in DKIM has been deprecated since the introduction of RFC 8301 in 2018." LOL. One of my favourite internet flame wars was circa 2007 (in and around discussing the incoming financial crises) and we got talking about encryption and how none of it actually "works". Particularly vile troll, and iirc also owner of the site bet me $50,000 I couldn't reverse the 512 RSA key he posted (created by openssl). He got the factorisation less than an hour after he made the post. Strangely, the entire site disappeared pretty quickly after that (and it's not on wayback machine). given where the math guys are now with GNFS I'm not sure I would trust 8192 bit RSA in 2024, 2018 for dropping 512 bit was already more than a decade late.
- matja 2y agoWas it a key affected by CVE-2008-0166 ? :)
- SahAssar 2y ago> not sure I would trust 8192 bit RSA in 2024 Do you have any proof/quote for that? Some pretty knowledgeable and well-known people in this thread 2048 bit RSA is quite safe with current capabilities[1] 1: https://news.ycombinator.com/item?id=42635066 https://news.ycombinator.com/item?id=42635066
- DarkmSparks 2y agohttps://www.bbc.com/news/world-us-canada-23981291 https://www.bbc.com/news/world-us-canada-23981291
- bmenrigh 2y agoCADO-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 https://eprint.iacr.org/2010/006.pdf)
- austin-cheney 2y agoIn 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 2y agoDKIM 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 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 2y agoEd25519-SHA256 support has existed for a while now. https://datatracker.ietf.org/doc/html/rfc8463 https://datatracker.ietf.org/doc/html/rfc8463
- bmenrigh 2y agoOh excellent. I didn't realize rfc6376 had been superseded.
- austin-cheney 2y agoWikipedia 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 2y ago> 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.
- dizhn 2y ago> 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?
- andix 2y agoAny tips on how to easily fetch the key length of DKIM-Keys from DNS? Just by looking at the DNS entries I can't easily determine the key length ;)
- awulf 2y agoAn easy way is to check the length of the p= value in the DKIM record. If it's around 216 characters, it's likely a 1024-bit key. A 2048-bit key usually has about 388 characters.
- zorgmonkey 2y agoIf you're going to do this you should also check for k=rsa since other key types will be different lengths. But I'd really recommend something like in the other comment where you base64 decode and parse it with something like openssl.
- deathanatos 2y agoFetch the TXT record; you should see something like, k=rsa; … p=<a bunch of base64 data> The base64 data is an RSA public key. You can print in textual form with something like, your-clipboard-paste-command | base64 -d | openssl rsa -pubin -noout -inform der -text The first line of output will be something like, Public-Key: (2048 bit) Which is the key length. If you fetch with `dig`, note that sometimes dig will do this: example.com. 1800 IN TXT "k=rsa; t=s; p=blahblahblahblah" "blahblahblah" I.e., it breaks it up with a `" "`; remove those, that's not part of the data. I.e., concat the strings dig returns, then parse out the p=, then base64 decode, then openssl. (You can also do what the article does, but without Python, which is jam that base64 between some PEM header guards like the article does, and then feed it to openssl. Same command, but you don't need the -inform der b/c the "in[put] form[at]" is now pem, which is the default.)
- cchance 2y agowhy aren't people just defaulting to 2048?
- croemer 2y agoSlight change of title. The leading "How" was dropped. Original: "How We Cracked a 512-Bit DKIM Key for Less Than $8 in the Cloud"
- Uriopass 2y agoDropping the How is part of Hackernews guidelines
- layer8 2y agoThere’s no such guideline. It’s just part of the default title normalization. The submitter can adjust it afterwards.
- ClassyJacket 2y agoAltering headlines automatically is really irresponsible.
- croemer 2y agoCouldn't find it in the guidelines. Can you quote the relevant part?
- dang 2y ago"How we X'd a Y" is a linkbait trope. We edited that in accordance with the site guidelines: "Please use the original title, unless it is misleading or linkbait". https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- gauravphoenix 2y agoI don't understand why didn't Yahoo fail due to SPF check failure.
- jaza 2y agoConsidering that Yahoo doesn't really exist anymore, and that Yahoo Mail is just a relic of Yahoo's heyday that is somehow still hanging around, I assume nobody has bothered to actually maintain its handling of security protocols for about a decade.
- jabroni_salad 2y ago"existing" is basically all it does. They make 8B a year and have the 12th most popular website globally. The email product has gobbled up both AOL and Verizon and they also whitelabel to a bunch of other ISPs. Just because they are never in the news for anything cool and hackernews commenters dont use them doesnt mean they dont exist.
- SahAssar 2y agoYahoo mail still has plenty of users and yahoo still have many employees. It'd be borderline criminal to not have somebody at yahoo oversee their email security.
- fortran77 2y agoI 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.
- prophesi 2y agoThis 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.
- dusted 2y agoIf 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 2y agoAddendum: 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 2y agoThe 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. I did my master thesis on this topic one year ago and found that all popular mail providers nowadays support 4096 bits, and some even up to 16384 bits.
- Twirrim 2y agoUnfortunately 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 2y agoSorry, 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 So mail providers MUST support up to 4096 bits if they follow the latest RFC.
- yieldcrv 2y agoThanks for sharing this article, I think people have been doing this for some time! I’ve gotten a lot of spear phishing attacks, as far back of 2018, with emails that passed many verification checks. Getting representation to this issue is notoriously difficult because people assume an undiscerning victim and end user. They also rely on the false idea that scammers can’t spell or don’t spell correctly, specifically to weed out discerning people. When there is a subset that makes everything as legit and impersonating as possible.
- supernova87a 2y agoThis 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 2y agoThere 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 2y agoThat'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.
- loeg 2y agoReminds me of factoring 512-bit RSA signing keys used on Ti calculators in 2009: https://en.wikipedia.org/wiki/Texas_Instruments_signing_key_controversy https://en.wikipedia.org/wiki/Texas_Instruments_signing_key_...
- irfan786 2y ago[dead]
- fernvenue 2y agoDon't know how Apple's iCloud Email will handle it, after all, Apple has always prided itself on being extremely attentive to user privacy and data security.
- maxed 2y agoI tested this last year, they properly reject mails signed with DKIM keys from <1024 bits
- jgalt212 2y agoWhile the DKIM passes, the SPF fails (per the Yahoo screenshot), so if I have this right a bad actor would still need to hack the legitimate senders DNS records (assuming DMARC rules are set up somewhat strictly). Do I have this right? Of course, if you can modify the SPF records, you can make the DMARC record say whatever you want.
- lakomen 2y agoWhat a misleading title