Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

dmarcchecker.app

Post reply on HN
Print view View original

401–410 of 433 posts

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

#401

Post by littlestymaar »

DarkmSparks wrote: post #400
jedwards1211 wrote: post #396

Earlier quoted context omitted.

Right, so if it costs $8 to search the space for a 16-bit key, a proper equation for the cost of cracking an n-bit key is Cost(n) = search_space(n) * $8 / search_space(16) And search_space(x) = 2^x so Cost(n) = 2^n * $2^3 / 2^16 = $2^(n - 13) Cost(32) = $2^(32 - 13) = $524288 Cost(64) = $2^(64 - 13) = $2251799813685248 So it quickly becomes astronomically expensive. If you double the number of bits n you get Cost(2n)…

Firstly, the number of prime numbers So moving from 2^16 = 65536 to 2^32 = 4294967296 Increases the size of the total potential search space from 5909 to 193635251, which is ~ 5909 x 32769 secondly, the reason it grows by only n^2, is you only need to search along the curve n = a x b - which is the "sieve" part. if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Thirdly, your stupidly high c…

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64

“The earth is flat blah blah blah”

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

#402

Post by DarkmSparks »

littlestymaar wrote: post #401
DarkmSparks wrote: post #400

Earlier quoted context omitted.

Firstly, the number of prime numbers So moving from 2^16 = 65536 to 2^32 = 4294967296 Increases the size of the total potential search space from 5909 to 193635251, which is ~ 5909 x 32769 secondly, the reason it grows by only n^2, is you only need to search along the curve n = a x b - which is the "sieve" part. if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Thirdly, your stupidly high c…

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 “The earth is flat blah blah blah”

opposing side of an argument resorting to a strawman is their implicit admission they were wrong.

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

#403

Post by ryan-c »

rstuart4133 wrote: post #394
tptacek wrote: post #384

Earlier quoted context omitted.

I really don't follow what you're trying to say here. The point is that the durable verifiable signature has no value to users, but lots of value to attackers; in other words: it only has value to attackers. People are confused because in a formal analysis, journalists getting stories from leaked mail spools are attackers; they are a thing secure messengers are designed to thwart.

> The point is that the durable verifiable signature has no value to users, Apparently I'm the exception to that rule, because I have a DKIM extension installed on Thunderbird. I use it to do what you say isn't useful - as another way to check phishing messages long after they have been sent. Until DKIM is universally enforced checking it after the fact will be useful. When DKIM is universally enforced rotating the k…

> you don't need a verifiable DKIM signature to know if the message had a valid DKIM signature when it was sent.

You seem to be trying to say that "the fact that it was delivered proves it had a valid signature when it was sent".

That presupposes that the headers indicating when it was delivered are correct, or that it was delivered at all in the first place.

I don't think you understand the attack.

I sent Thomas an email admitting to something scandalous.

A few months later, Mallory pops the server Thomas's email is stored on, and extracts his mail spool.

Mallory wants to prove to a third party that the email is authentic and not a fabrication.

I know it's real.

Thomas knows it's real.

Mallory is pretty sure it's real.

Alice, a reporter for the Daily Bugle cannot verify it is real, rather than Mallory's forgery.

I can claim it's a forgery, and point out that Mallory could have made it up and generated the signature with the published key.

Now, I may have a problem if it were a crime rather than something merely scandalous because then Bob, an FBI agent, decides to subpoena some logs and maybe prove when it was sent, but even so, logs typically don't have message content or even a hash of the message content.

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

#404

Post by alt227 »

lazide wrote: post #348
alt227 wrote: post #347

Earlier quoted context omitted.

Yep, but it will never replace email address as universal identifier until it is adopted by all. In addition to that, reports show that the majority of Asian and African users access the internet via a shared device. Therefore phone number cannot be a universal identifier there as it generally identifies a group of people rather than in indivdual. This is why google and outlook accounts with SSO are still generally t…

By what metric? In India, it is exceptionally rare for any services (gov’t and commercial) to use email address. They use mobile. One of many examples [ https://web.umang.gov.in/landing/department/aadhaar.html ] That accounts for 1.3+ billion distinct accounts in 2023 right there. [ https://uidai.gov.in/en/about-uidai/unique-identification-au... ] Do you think those folks in Asia and Africa sharing mobile devices hav…

Not really sure what you are saying here, it seems like you are a bit confused.

You were talking about phone numbers being used to access online services, and now you are posting links about the Indian governments Personal Identification number which is more akin to a National Insurance number in the UK or social security number in the US

> Do you think those folks in Asia and Africa sharing mobile devices have email accounts they can use instead?

Yes definitely. Huge numbers of people in these developing nmations share a single mobile device per family or household, yet they all have individual facebook and google accounts to communicate with the world. That is defintiely all controlled via email address, unless I have missed a feature of FAANG companies where you can sign up for accounts with a mobile phone number?

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

#405

Post by bmacho »

DarkmSparks wrote: post #400
jedwards1211 wrote: post #396

Earlier quoted context omitted.

Right, so if it costs $8 to search the space for a 16-bit key, a proper equation for the cost of cracking an n-bit key is Cost(n) = search_space(n) * $8 / search_space(16) And search_space(x) = 2^x so Cost(n) = 2^n * $2^3 / 2^16 = $2^(n - 13) Cost(32) = $2^(32 - 13) = $524288 Cost(64) = $2^(64 - 13) = $2251799813685248 So it quickly becomes astronomically expensive. If you double the number of bits n you get Cost(2n)…

Firstly, the number of prime numbers So moving from 2^16 = 65536 to 2^32 = 4294967296 Increases the size of the total potential search space from 5909 to 193635251, which is ~ 5909 x 32769 secondly, the reason it grows by only n^2, is you only need to search along the curve n = a x b - which is the "sieve" part. if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Thirdly, your stupidly high c…

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64

Can you answer

    a) If 1 apple costs you 8$ then (1)^2 apple costs you: ???
    b) If 10 apples cost you 8$ then (10)^2 apples costs you: ???
edit: between the price and the amount, usually there is a ~linear relationship. So if you can buy 2^512 something for 8$, then chances are that for 8 times the price you'll only get ~8 times more amount, and not 2^512 times more

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

#406

Post by bmacho »

littlestymaar wrote: post #397
DarkmSparks wrote: post #392

Earlier quoted context omitted.

thats linear search in gnfs the search space is number fields, so you increase the number of the number fields by the square of what came before.

Do you even read?

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64

This and the stuff they've been writing about suggest that we are observing a mind that used to know things, but suffered some serious damages/degrade over time. That's always so sad.

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

#407

Post by jedwards1211 »

DarkmSparks wrote: post #400
jedwards1211 wrote: post #396

Earlier quoted context omitted.

Right, so if it costs $8 to search the space for a 16-bit key, a proper equation for the cost of cracking an n-bit key is Cost(n) = search_space(n) * $8 / search_space(16) And search_space(x) = 2^x so Cost(n) = 2^n * $2^3 / 2^16 = $2^(n - 13) Cost(32) = $2^(32 - 13) = $524288 Cost(64) = $2^(64 - 13) = $2251799813685248 So it quickly becomes astronomically expensive. If you double the number of bits n you get Cost(2n)…

Firstly, the number of prime numbers So moving from 2^16 = 65536 to 2^32 = 4294967296 Increases the size of the total potential search space from 5909 to 193635251, which is ~ 5909 x 32769 secondly, the reason it grows by only n^2, is you only need to search along the curve n = a x b - which is the "sieve" part. if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Thirdly, your stupidly high c…

Okay I hadn't read about how many calculations it takes to cover the search space, so my equations aren't right about that.

However, you will do yourself a big favor if you take the time to understand why this is wrong:

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64

The cost per calculation is some constant C:

Cost(n calcs) = n calcs * C

Therefore,

Cost(n^2 calcs) = n^2 calcs * C

In this example, C = $8 / 2^512 = $2^-509

So Cost(2^512^2) = Cost(2^1024) = 2^1024 * $2^-509 = $2^425

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

#408

Post by jedwards1211 »

DarkmSparks wrote: post #402
littlestymaar wrote: post #401

Earlier quoted context omitted.

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 “The earth is flat blah blah blah”

opposing side of an argument resorting to a strawman is their implicit admission they were wrong.

We're trying to help you understand, and you're stubbornly refusing to swallow your pride and think about what we're saying

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

#409

Post by jedwards1211 »

DarkmSparks wrote: post #374
littlestymaar wrote: post #359

Earlier quoted context omitted.

1km² aka 1,000,000m², note how the resulting units aren't km and m but square kilometers and square meters. > What can you square then? In that case it's the number of operations (which is unitless) that must be squared and then multiplied by the cost of each operation. For instance (figures are completely made up for illustration purpose) if one individual operation costs 0.1 cent, and you have 8000 ops for the fact…

the search space is p1×p2 = cost therefore (p1^2) x (p2^2) = (p1xp2)^2 =cost^2 and gnfs search cost increases in cost by (roughly) the square of the number of bits.

The wiki article on GNFS says:

> The size of the input to the algorithm is log2 n or the number of bits in the binary representation of n. Any element of the order nc for a constant c is exponential in log n. The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input.

"Super-polynomial" means that the running time increases by more than the square.

In any case, even if the algorithm were just polynomial, the argument about squaring costs doesn't work out.

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

#410

Post by DarkmSparks »

littlestymaar wrote: post #397
DarkmSparks wrote: post #392

Earlier quoted context omitted.

thats linear search in gnfs the search space is number fields, so you increase the number of the number fields by the square of what came before.

Do you even read?

Did you? you linked https://en.wikipedia.org/wiki/General_number_field_sieve

already That gives the worst case complexity right at the top.

> 2^16

[1] 65536

> n> exp(((64/9)^(1/3)+1)(log(n)^(1/3))(log(log(n))^(2/3)))

[1] 38178499

> 38178499/65536

[1] 582 2^16 -> 2^32 ~ x 2^9

> n> exp(((64/9)^(1/3)+1)(log(n)^(1/3))(log(log(n))^(2/3)))

[1] 84794674511

> 84794674511/38178499

[1] 2221

2^32-> 2^64 ~ x 2^11

> n> exp(((64/9)^(1/3)+1)(log(n)^(1/3))(log(log(n))^(2/3)))

[1] 2.507616e+15

> 2.507616e+15/84794674511

[1] 29572

2^64 -> 2^128 ~ x 2^15

So in GNFS 2^32 -> 2^64 complexity doesn't increase 4294967296 times, worst case it increases 2221 times

_In practice_ the cost grows closer to (nbits)^2 mostly because as an "embarrassingly parallel" algorithm you get significant benefits from cached results (quickly discard entire number fields that were previously calculated).

if O(x) = 8 then O(x)^2 = 8^2

I did miss a x2 earlier because e.g. 128 bits is 128^2 (16384 rather than 29572) harder than 64 bits, not 64^2

So its (2xO(x))^2 = (2 x 8)^2 = $256

Post reply on HN