11
$\begingroup$

For argument's sake, let's say that I'm a bad actor who produces malware. I've infected around 10,000 computers and smartphones with my malware, which runs in the background and can be used to make someone else's machine run calculations for me.

I've gotten access to some encrypted data that I'm not supposed to have. It's heavily encrypted with an asymmetric cipher, and it will theoretically take 1,000 years to crack! However, I have an array of 10,000 computers. Assuming I can use the machines to their full extent (the users are too stupid to think that anything is wrong), could I feasibly distribute the workload of hacking this encrypted data to get through it in about 37 days? Why or why not?

$\endgroup$
  • 6
    $\begingroup$ Distributing a cryptanalytic attack is certainly something you could do in general, but whether you would have any reasonable probability of success depends entirely on the cryptosystem and the choice of attack. $\endgroup$ – Squeamish Ossifrage Nov 21 '19 at 14:36
  • 7
    $\begingroup$ Also as this seems to be homework, hint: What is 1000 years / 10,000 ? $\endgroup$ – SEJPM Nov 21 '19 at 14:37
  • 9
    $\begingroup$ I guess you could, but usually secure ciphers would take a lot longer than just 1000 years to achieve a brute force attack. $\endgroup$ – AleksanderRas Nov 21 '19 at 14:37
  • 9
    $\begingroup$ @NegativeFriction Yes, you can just run 10,000 servers in parallel. No, this won't break modern ciphers, because modern ciphers don't require "1,000 years" to break. On a fictional computer that can compute a trillion attempts per second, this would require more than an octillion years (10e27). $\endgroup$ – Stephen Touset Nov 21 '19 at 22:19
  • 3
    $\begingroup$ You're basically assuming—correctly—that brute force key search and password cracking are both examples of what's technically called embarrassingly parallel problems. As a lot of people have told you and I'll summarize, strong cryptography is designed to resist such attacks too, but password-based cryptography is a special case where there's only so much you can do to protect a user who picks a weak password. $\endgroup$ – Luis Casillas Nov 21 '19 at 22:49
25
$\begingroup$

I've gotten access to some encrypted data that I'm not supposed to have. It's heavily encrypted with an asymmetric cipher, and it will theoretically take 1,000 years to crack! However, I have my array of 10,000 computers. Assuming I can use the machines to their full extent (the users are too stupid to think that anything is wrong), could I feasibly distribute the work load of hacking this encrypted data to get through it in about 37 days? Why or why not?

The answer depends entirely on what cryptanalytic problem you're hoping to solve.

Worst case: No. For example, if you have to compute $2^{2^t} \bmod pq$ without knowing $p$ or $q$ (large random primes of sizes beyond the reach of ECM or NFS) where $t$ is very large, throwing more computers at it doesn't help (without a novel cryptanalytic breakthrough); only making the computer itself run faster—e.g., by designing an ASIC that computes it and running it at a high clock rate cooled with liquid nitrogen—will give you an answer faster.

This is because we don't know of any algorithm to compute $2^{2^t} \bmod pq$ other than starting with $x_0 = 2$ and then computing $x_i = {x_{i-1}}^2 \bmod pq$ sequentially $t$ times: except for vectorization attainable in the squaring operation, parallelism doesn't help.

Best case: Yes. For example, if you have a password hash and you want to find a password among a large space that a single computer can search in 1000 years to search, and if you have 10 000 you can afford to run, then sure, you can divide the space into about 10 000 subspaces—for instance, all those passwords starting with aaa, aab, aac, etc.—and get a factor of 10 000 speedup by searching the subspaces independently.

Actually, if you have a collection of password hashes and you're content to find one of the passwords, you can get an even better speedup than a factor of 10 000 by a multi-target attack.

In general, you are limited by Amdahl's law: if the fraction of time spent a sequential program that can be parallelized is $P$, then the best possible speedup attainable by parallelism is a factor of $S = 1/(1 - P)$; that is, if it previously took time $T$, then with parallelism it can take at best time $T/S$.

For computing $2^{2^t} \bmod pq$, $P$ is essentially 0—the problem is, as far as we know, inherently sequential (short of factoring $pq$), so $1/(1 - P) = 1$ meaning that parallelism doesn't change the time at all.

For searching among keys $k$ to find one matching a given hash $H(k)$, $P$ is essentially 1—the problem is embarrassingly parallelizable, so $1/(1 - P) = \infty$, meaning that the time can be made arbitrarily small with parallelism.

Will this matter for serious cryptography? No. Serious cryptosystems are generally chosen so that the cost of an attack is higher than you can ever afford. For example, you will never find one of any plausible number of AES-256 keys by brute force, because the cost will far exceed $2^{128}$ evaluations of AES, which you don't have the pocket change to pay for the energy to do, no matter how much you parallelize it. The same goes for finding any Curve25519 private key by the best known discrete logarithm algorithms given all the Curve25519 public keys in the world.

Note that even with Amdahl's law, trading parallelism for time doesn't necessarily reduce cost: the energy to power 365 computers for a day is about the same as the energy to power one computer for a year. In some cases—like parallel rainbow tables or distinguished points in a multi-target attack—it does reduce cost! But you're not guaranteed a cost reduction just by parallelizing a computation. In other cases—like Grover's algorithm on a (hypothetical) quantum computer—parallelizing the computation may raise the cost!

| improve this answer | |
$\endgroup$
4
$\begingroup$

could I feasibly distribute the work load of hacking this encrypted data to get through it in about 37 days? Why or why not?

It depends on a lot of details.

General case: No

In general, no. Systems are typically* designed so that the cost of the best known attacks require more resources than it is physically possible to have access to.

Assuming that the key was generated in a secure manner, then even if you had access to billions of devices cracking a single key would be infeasible.

*Some systems only need to consider adversaries of more limited capabilities and are designed to minimize costs to only those needed to defeat that limited adversary.

Special case: Maybe

If:

  • You know what system is being used
    • Including sufficient information to evaluate the system on arbitrary inputs yourself (e.g. KDF parameters)
  • And the root of secrecy in that system is only an average quality password
    • An average quality password is a lot easier to crack than the bits that constitute the key.

Then breaking into whatever you want is probably doable and parallelism will help.

  • Guess the password
  • Derive a key
  • Use the candidate key to verify the authentication tag on the cryptogram
    • If authenticated encryption was not used, then chances are good that there may be other exploitable weaknesses in the system and cracking a password is not even necessary.
  • If the tag verifies, then you found something usable as a key to decrypt the message
    • (which may be but does not have to be the original password)

32 day timeline

A 32 day timeline may or may not be reasonable, depending on:

  • The strength of the password
  • The KDF settings (iterations, etc)
  • Budget

If this is not a hypothetical...

The question cannot be "answered" as such in a direct yes or no manner due to the number of absent details. This answer assumes an abstract hypothetical problem.

| improve this answer | |
$\endgroup$
3
$\begingroup$

As indicated in the comments, it depends on how far you can parallelize the attack. If that's easy, such as splitting a key range to brute force it, then you can probably create a linear speed up. However, that attack is unlikely as generally ciphers have keys of 128 bits or over, and the initial idea that this can be cracked in 1000 years is unlikely to be true.

You can have a similar attack if you use a augmented dictionary attack on a password, if that was used. However, now you get into the issue of how to implement the attack over multiple computers as well. This is still relatively easy to do, but already harder than just splitting the key space.

Other attacks may not be as easy to parallelize however, so if you gain your maximum speed up (as you seem to do) really depends on the attack and the implementation of the attack.

| improve this answer | |
$\endgroup$
2
$\begingroup$

You say asymmetric cipher, so...

Parallel attacks dicrete logarithm based asymmetric ciphers have been done (and are a wholly different beast than e.g. brute-forcing a 128-bit symmetric cipher, or even a 256-bit one, which is outright ridiculous to think about).

If Fried and Gaudry can be trusted (and why could they not!), it should take anywhere around 109 core-years to attack a 2048-bit key, with a 1024-bit key being 16 million times easier. They also claim having done 768 bits in minutes on their cluster (which sounds plausible, too).

This may be an issue insofar as despite "at least 2048, better 3072" has been the recommendation for a decade, still 1024 isn't all uncommon or impossible to encounter. So, without knowing what key length you have (possibly as few as 1024 bits?), the answer should probably be: Yes. Possible.

Now of course, nobody uses an asymmetric cipher to encrypt anything but a symmetric cipher key, so... a few additional steps may be necessary. But in principle, yes, why not. Ten thousand cores running for 37 days is roughly a thousand core-years. They're mobile processors you say, so let's say a few hundred core-years only. That's just about within the order of magnitude of what Fried and Gaudry said it takes for 1024 bits.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Distribute yes, solve in 37 days unlikely.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Why? Please give at least some reasoning to justify your answer. $\endgroup$ – otus Nov 24 '19 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.