# How to determine the security in bits of a scheme?

This may be a stupid question. But how would we determine the security bit of a crypto scheme?

For example, SHA2-256 offers 128 bit security due to birthday paradox, so do they measure the security bit by calculating $\log_2$ of best-known attack?

However, some scheme is defined as $(t,\epsilon)$-secure. how should we determine the security bit? some people define the security as $\log_2(t/\epsilon)$? but should it be inconsistent as $(t,\epsilon)$ can vary.

is there a standard way of measuring the security bit of a scheme?

• The term "Security bit" usually designates a single bit which, when in a certain state, enables a security behavior (like, making a zone of memory read-only). You want the security level expressed as a number of bits, or the level of security in bits for short.
– fgrieu
Dec 15 '17 at 16:45
• "For example, SHA2-256 offers 128 bit security due to birthday paradox, so do they measure the security bit by calculating log2 $\log_2$ of best-known attack?" That's exactly right. Of course, the order of the attack may be a close estimation. There may be memory requirements in addition, and some attacks are not always applicable (HMAC is impervious to collisions in the hash functions). I'm not answering because I cannot directly answer the second part of the question. Some interesting info can be found on keylength.com and the linked to papers. Dec 17 '17 at 1:09

## 1 Answer

There isn't a single formal standard, because different types of cryptosystems have different attack strategies and cost models. For each type of cryptosystem, there usually is a standard notion of adversarial advantage: we posit a game the adversary might play, with an idealized version of the cryptosystem, or with a practical realization of the cryptosystem, and the adversary's advantage is how much more probable they are at winning the game with the real cryptosystem than with the idealized cryptosystem.

You can read more how to work with adversarial advantage in Mihir Bellare and Phil Rogaway's book, which goes into far more detail than there is space in the margin of this stackexchange note to fit. But here's a quick overview of a few examples of the variety of adversarial advantage notions you'll encounter:

• With symmetric-key authenticated encryption, the adversary is given a chance to play with devices that encrypt chosen messages and decrypt chosen ciphertexts, called oracles, and they win if either they can distinguish a random string from the ciphertext of a random message, or if they can forge a ciphertext they did not obtain from the encryption oracle that the decryption oracle accepts. This probability is usually studied as a function of the number of queries the adversary makes to the encryption and decryption oracles, how long the messages can be, etc.

The standard attack strategy is to guess the unknown key correctly and try decryption or forgery with that, but specific constructions might admit strategies with better advantage; any AE scheme worth its salt will come with a theorem about the adversary's advantage in terms of the conjectured advantage of some primitive, like a pseudorandom function family such as ChaCha.

• One-time authenticators. The adversary is just given a single message and valid authentication tag and a verification oracle, and they win if they can produce a single valid authentication tag for another message after some number of attempts. The forgery probability is usually a function of the maximum message length accepted by the verification oracle and the number of queries to the verification oracle. The standard attack strategy is to make up an authentication tag uniformly at random, and the forgery probability is $$2^{-t}$$ if its length is $$t$$ bits.

• Diffie–Hellman key agreement schemes. The adversary is given a set of public keys $$a_i \cdot \xi$$ for unknown $$a_i$$ in some group $$G$$ and for a standard $$\xi$$ in some set $$S$$ with a group action of $$G$$ on $$S$$; a set of oracles for computing $$\zeta \mapsto a_i \cdot \zeta$$ for any attacker-chosen $$\zeta \in S$$ and each unknown $$a_i$$; and a set of one-way functions $$H((a_i + a_j) \cdot \xi)$$ of shared secret $$(a_i + a_j) \cdot \xi$$ values. The adversary's goal is to compute any one of the shared secret $$(a_i + a_j) \cdot \xi$$ values.

The standard attack strategies are more complicated, and references for details in the elliptic curve setting can be found at, e.g., SafeCurves; in the finite field setting, index calculus dominates. There are qualitative differences for the elliptic curve setting and the finite field setting: for the elliptic curve setting, attacking every one of a batch of targets with Pollard's rho is cheaper than attacking an individual target; for the finite field setting, there's a high precomputation cost for index calculus, after which attacking an individual target is cheap.

How does all this translate into security levels? We take a concrete estimate of the costs of the best known attack in a sensible cost model, and consider the expected cost of an attack with nonnegligible probability of success, and then usually round to a nice power of two. For example:

• The forgery probability of Poly1305 for a single message of up to $$16\ell$$ bytes is $$8\ell/2^{106}$$, e.g. $$2^{-97}$$ for messages of up to a kilobyte or $$2^{-87}$$ for messages of up to a megabyte which presumably cost a thousand times as much to attempt as kilobyte-long messages. We loosely round this to a $$2^{128}$$ security level since (a) it is well below $$2^{-100}$$ per block and (b) it depends on the bandwidth of the legitimate user and not on the offline costs an attacker can afford spend.

• The expected cost before computing a single Curve25519 discrete logarithm is about $$2^{125}$$ elliptic curve additions—offline, so not dependent on the legitimate user's bandwidth. We loosely round this to a $$2^{128}$$ security level because one elliptic curve addition takes a lot more than eight bit operations.

There is some confusion among some cryptographers about what the best standard attacks are; some disagreement about what cost model to use, how to formalize the costs of precomputation, and how to figure batch attacks into security notions; some uncertainty about how to address loose bounds reducing the security of a composition to the security of its primitives; and so on.

Every now and then spats flare up between academics who have frank exchanges of feelings about these subjects. Sometimes this is reserved to the review processes of academic publications; sometimes it comes out in position papers and letters to the editor (1, 2); sometimes it is in preprints back and forth; sometimes it is on Twitter. Whether they ever resolve their differences on the street outside the conference venue is a question I leave to the philosophers.