Peter N. M. Hansteen asks the question, "Does Your Email Provider Know What A "Joejob" Is?" in his blog and provides some data and discussion. He provides anecdotal evidence which seems to indicate that Google and possibly other mail service providers are either quite ignorant of history when it comes to email and spam, or are applying unsavory tactics to capture market dominance.
[Ed Note: I had to look up "joe job" to find out what it is. According to wikipedia:
A joe job is a spamming technique that sends out unsolicited e-mails using spoofed sender data. Early joe jobs aimed at tarnishing the reputation of the apparent sender or inducing the recipients to take action against them (see also e-mail spoofing), but they are now typically used by commercial spammers to conceal the true origin of their messages.
]
(Score: 1) by FrankL on Monday April 25 2016, @02:15AM
Your logic assumes it is very hard/expensive to factor 1024-bit.
Do you have any numbers to back this up?
A far better reason for this being unlikely, is that a spammer probably would go after 512-bit DKIM or 768-bit DKIM keys before factoring 1024.
Unless big mail services now ignore 1024-bit DKIM key length in their spam detection...
(Score: 1) by FrankL on Monday April 25 2016, @02:17AM
'ignore 1024-bit' should read as: 'ignore key lengths shorter than 1024-bit, e.g. due to susceptibility to being factored'
(Score: 0) by Anonymous Coward on Monday April 25 2016, @03:10AM
> Your logic assumes it is very hard/expensive to factor 1024-bit.
> Do you have any numbers to back this up?
Your logic assumes it is feasible to factor a 1024-bit key.
Do you have any numbers to back this up?
I, in fact, do have numbers to back up my claim. But your response was so snotty and disingenuous that I will let you use google to figure out how absurdly expensive it would be.
(Score: 1) by FrankL on Monday April 25 2016, @06:12AM
so you respond to my sollicitation for a cost estimate, with that it would be 'a lot more expensive than the payoff from the spam' without providing any numbers or references, then do it again with a statement that it is 'absurdly expensive' and put the burden on backing up your claim on me?
Very chique!
You might very well be right, but pulling numbers from thin air is not advancing this discussion.
The best I could find without spending too much time on searching is the "Factoring as a Service" paper by Valenta et al. that concludes that it takes 75 USD to factor 512-bit RSA. Would love to find estimates on 768 and 1024 bit RSA...
(Score: 4, Interesting) by stormwyrm on Monday April 25 2016, @08:24AM
1024-bit factoring is, as far as we know, still way out of reach. See here:
http://security.stackexchange.com/questions/4518/how-to-estimate-the-time-needed-to-crack-rsa-encryption [stackexchange.com]
http://web2.0calc.com/questions/how-long-would-it-take-to-break-a-rsa2048-key-on-one-computer-that-handles-2-4-billion-instructions-per-second#r4 [0calc.com]
Judging from the RSA Factorization challenge, given that only the 768-bit challenges have been successful so far, I think factoring a 1024-bit key is probably still impossible within the next five to ten years or so, barring an unexpected development either in mathematical discoveries or quantum computing. The fastest known factoring algorithm for integers not in some special form is the General Number Field Sieve (GNFS), which was used in 2009 to factor RSA-768. The thing is, it seems that the GNFS isn't the sort of algorithm you can just compile the code for and feed a number into. There are three parts to it: the first is polynomial parameter selection, which is generally done these days by some smart number theorists with the aid of powerful computers. This part could conceivably be fully automated but it's obviously not that easy. Work is being done these days on parameter selection for 1024-bit numbers. There's also parts called sieving and linear reduction. The sieving portion is the easiest to parallelise, though it will also need plenty of memory. The linear reduction portion is infeasible today for anything above 768 bits though, because parallelising it isn't practical and it involves the manipulation of a massive matrix that requires terabytes of fast memory. The kind of hardware needed to that kind of computation just plain doesn't exist today, at least not as an off-the shelf commodity. The RSA-768 linear reduction matrix was 192 million rows x 192 million columns, just within reach of the technology of the time. The corresponding matrix for a 1024-bit integer factorisation would be perhaps some 4 billion x 4 billion. It will probably take something like five to ten years of advances in computing power before this part becomes practical.
Doesn't mean that the NSA or some other intelligence agency couldn't do it though. They could conceivably spend several billion dollars on some crazy powerful supercomputer with the incredible quantities of memory needed that can do the linear reduction for a 1024-bit factorisation, but this estimate is just as much pulled out of thin air as the GP's numbers are.
TL;DR: At this time, factoring a 1024-bit number is not doable on the hardware that is easily available today, so giving a price estimate as you ask is meaningless.
Numquam ponenda est pluralitas sine necessitate.
(Score: 1) by FrankL on Tuesday April 26 2016, @03:12AM
Thanks, I wasn't aware that RSA-768 was first known to be factored back in 2009;
just found the paper by Kleinjung et al. ; very interesting!
Are you active in the cryptography field?
Is there a consensus among academics on the expected level of cryptography research by nation-state agencies, compared to the academic world?
...Are they expected to be somewhat ahead? (how many years?)
The only example that I can remember on this is the 1973-1975 work done by the NSA to strengthen the S-box in DES.
Of course, that's 40 years out of date today, so we'd need more recent examples to make inferences...
(Score: 2) by stormwyrm on Tuesday April 26 2016, @08:28AM
How far ahead intelligence agencies are beyond the open academic cryptographic community is difficult to estimate. We do know for instance that the NSA and IBM were already aware of differential cryptanalysis at least a decade or so before Eli Biham and Adi Shamir independently discovered it in the late 1980s: Don Coppersmith later revealed that the changes to the DES S-boxes were made to strengthen it against differential cryptanalysis when Biham and Shamir noticed that DES seemed to be so carefully tweaked to make their "new" technique all but useless against it. So in the eighties, they were at least twenty years ahead of the academic cryptographic community.
We haven't seen too many examples of the algorithms designed by the NSA. There are only a few such block ciphers known: Skipjack [wikipedia.org] and a pair of ciphers known as Simon and Speck [schneier.com]. The former was originally part of the controversial Clipper chip proposal and was declassified in 1998 [schneier.com] after they were forced to have to implement the Clipper chip algorithms in software. The latter two were published in 2013 and no one is sure why they did so. Skipjack is an interesting design, as it is an unbalanced Feistel network, similar to a design independently proposed by Bruce Schneier and Matt Blaze in 1994. The immediate heritage of Skipjack's design is said to date back to around 1980, so that would make the NSA about 14-15 years ahead of the academic cryptographic community back then.
For public key algorithms things are less certain. It's known that someone in GCHQ seems to have invented an algorithm that amounted to RSA in 1973, 4-5 years before Rivest, Shamir, and Adleman did so. The algorithm used for key exchange with the Clipper chip, known as KEA, was declassified along with Skipjack in 1998, and it is nothing weird, merely a variant of traditional Diffie-Hellman key exchange. No one knows if any of the still-classified public key and key exchange algorithms are anything really special.
I'm not really active in the cryptography field, just a programmer who has an abiding interest in cryptography and cryptanalysis. The most I've done professionally is implement a few algorithms for embedded systems, e.g. just before the AES contest ended I wound up coding Rijndael, which eventually won, for a small 8-bit microcontroller. I read Schneier's blog and follow developments in the field when I have the time.
Numquam ponenda est pluralitas sine necessitate.
(Score: 0) by Anonymous Coward on Monday April 25 2016, @12:05PM
> The best I could find without spending too much time on searching is the "Factoring as a Service" paper by Valenta et al. that concludes that it takes 75 USD to factor 512-bit RSA. Would love to find estimates on 768 and 1024 bit RSA...
Gee, smug and stupid.
Let me spell it out for you:
If it costs $75 to factor 512-bit RSA then it costs $75 x 2^256 to factor 768 bits and $75 x 2^512 to factor 1024 bits.
(Score: 1) by FrankL on Tuesday April 26 2016, @03:21AM
another user (stormwyrm) just showed that 768-bit RSA was factored in 2009.
You are implying that that would have cost more than $ 75 x 2^256 = 8.6 * 10^78 USD, disregarding the higher cost of computing resources in 2009.
So the conclusion would then be that either 512-bit RSA can be factored much cheaper than 75 USD (maybe a few dollar cents)....
OR.... that factorization does NOT scale the way you propose!
(Score: 0) by Anonymous Coward on Tuesday April 26 2016, @07:57AM
Your calculation is utterly bogus. You've presumed the cost to factor is exponential - to be precise, O(N) or O(2^D) where D=lg(N) is the size of the number N to be factored.
That hasn't been the case *ever*. Even trial factoring is quicker than that, as you only need to trial divide by primes up to sqrt(N), so the cost of that is o(sqrt(N)/ln(N)). GNFS, like QS before it, is subexponential, and by the time you're at numbers of this size, the difference is immense.
Here's a little bit of verification that your calculation is bogus - if 512 bit cost $75, then factoring 500 bits should cost 2c. Does it?
FatPhil
(Score: 4, Interesting) by TheRaven on Monday April 25 2016, @08:48AM
sudo mod me up