5
$\begingroup$

Is there way to make encryption scheme ASIC and GPU resistant, besides using a lot of memory?

And what is there ciphers or modes of use for such purpose? Including public keys algorithms maybe too, if there is any methods for them.

Or it's only worth to defend key derivation function? (Like scrypt, but it obviously failed in the case of litecoin.)

Clarification: 'encryption scheme' is protocol and/or system using cryptography to encrypt text. It's meaning opposes single algorithm, like AES or whatever. And it should be resistant against ASIC/FPGA/GPU/crypto-hardware optimized algorithms, like brute-force, or whatever algos there is for such hardware. It should make such attack not orders faster than on standard CPU or orders more expensive.

Improve this question
$\endgroup$
10
  • $\begingroup$ What do you mean with "an encryption scheme", and please define how should it be resistant against ASIC's and GPU's (like what attacks should it be able to defeat)? $\endgroup$
    – orlp
    Jan 12, 2014 at 9:25
  • $\begingroup$ We want slow (password-based) KDFs because the only secret is low-entropy (i.e., a human-memorable password) and therefore brute-force-susceptible. Secret-key encryption schemes are a whole different ballgame: there, we have nice, strong secrets (typically 128+ bits) that make brute force infeasible (hopefully). So, we don't care much about ASIC/GPU/FPGA attacks on, say, AES. Quite the opposite: we want encryption to be as efficient as possible, and efficiency is what separates good ciphers from the bad these days. $\endgroup$
    – Reid
    Jan 12, 2014 at 9:31
  • $\begingroup$ @Reid In context of this question I am ready to sacrifice efficiency for increased security. $\endgroup$
    – catpnosis
    Jan 12, 2014 at 9:46
  • $\begingroup$ @nightcracker I added answer to your questions into my question. $\endgroup$
    – catpnosis
    Jan 12, 2014 at 9:50
  • 4
    $\begingroup$ For most primitives we can simply choose keys large enough to resist brute-force, even with ASIC. Larger keys are cheap for the defender, but exponentially expensive for the attacker. For example a 256 bit AES key is $2^{128}$ times to break as expensive as a 128 bit AES key, but only 1.4 times as expensive to use. Only a few cases we're desperate enough to use expensive operations, usually to compensate for the limits of humans (e.g. users not being willing to memorize secure passwords). $\endgroup$
    – CodesInChaos
    Jan 12, 2014 at 12:59

1 Answer 1

Reset to default
7
$\begingroup$

As pointed in this comment, using a huge random key for a sound block cipher is an excellent defense to resist ASIC/GPU attacks. Each bit added doubles the effort required. If an adversary was able to build $10^{12}$ ASICs each capable of testing $10^{12}$ keys per second, odds of finding a 128-bit key by brute force running that for a decade are less than one in $10^6$. Thus 128 bits of key are good enough to resist ASIC/GPU attacks in the foreseeable future if you discount the possibility that quantum computers will become useful cryptanalytic tools; make it 256 bits if you account for that or a number of other questionable possibilities. Use this as key for a cipher without a backdoor, on a platform with no exploitable side channel: confidentiality problem solved (but neither integrity or anonymity). Fine, but:

  • Generating a true random secret key is non-trivial; and it is impossible to distinguish from its output that some allegedly true random generator is bad (that's for many incompetently designed/implemented generators, and any competently rigged one).
  • In many applications, both sides must agree on the secret key (Public Key cryptography can help that, but I won't touch key establishment or distribution here).
  • Real platforms have side channels, accidental or deliberate.
  • Typical users have great pain remembering even a 80-bit random key (roughly equivalent to learning three 8-digits phone numbers, not including prefix).

The last issue is often dealt with exclusively by key stretching (also known as password-hashing, or Password-Based Key Derivation Function; you know when a field is immature when its name has not even settled). A PBKDF turns a weak passphrase into a wider key, using as many iterations as practical of some appropriate transformation. This is when (and only when for a proper system, with the possible exception of PK crypto as used in key establishment or distribution) ASICs/FPGAs/GPUs should be a threat.

The current state of art in key-stretching is scrypt. In order to reduce the speedup obtainable at a given cost by using ASICs/FPGAs/GPUs, scrypt strives to make best use of resources available by the legitimate key stretcher with a modern CPU:

  • considerable memory;
  • multiple cores;
  • fast operations (addition, xor, and fixed rotations) so that software performance is not too bad.

How to improve on that is the subject of active research, and the ongoing Password Hashing Competition.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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