As the Wickr community continues to grow, our engineering & crypto teams are developing new tools and techniques to protect user information while continuously improving our existing security architecture.
Joël Alwen, Cryptographer
June 13, 2017
One of the core concepts that we work with is “bit security,” which refers to the order of magnitude of the amount of resources needed to break a crypto primitives’ security.
In this post, I’ll share a quick overview of the bit security of several common generic types of cryptographic primitives as well as a few specific examples used by the Wickr protocol and why they were chosen by our team.
Bit Security In A Nutshell
In its most general sense, the bit security of a primitive such as a hash function or block cipher is the order of magnitude of the amount of resources needed to break the primitives’ security. For example, AES-256 is believed to have 256-bit security, so an adversary trying to decrypt a ciphertext encrypted with a random unknown key will need to do roughly 2²⁵⁶ computation in order to recover the plaintext.
The most common bit security levels in practice are 128 and 256, and both are widely supported in the form of versatile toolboxes of well studied and carefully implemented cryptographic primitives.
In the context of a security system, the strength of the entire system is usually no better than the strength of its weakest component. The Wickr protocol (and application) makes use of several kinds of cryptographic primitives. In order to ensure that the entire protocol has 256-bit security, Wickr has chosen each of the primitives to meet this goal.
Quantifying Security
Before we can quantify the security provided by the Wickr protocol it helps to understand three common (and sometimes conflated) concepts used to quantify the level of security provided by a cryptographic algorithm and put them in relation to each other. *
BITS OF SECURITY:
In principle, a crypto primitive (or protocol) provides security against an adversary mounting some particular form of attack where the nature of the attack depends on the type of primitive being considered. Attacks are usually specified in the form of a game between an adversary and honest parties. Given such a game, the term “bits of security” generally refers to amount of resource(s) an adversary needs in order to successfully win the game.
In general, by “amount of resources”, I mean the product of the magnitudes (i.e. log base 2) of the computational work, memory and luck needed to win the security game at least once. If the game under consideration involves online interaction with honest parties (e.g. online attacks against a login protocol), then we can also include the number of attempts in the product. For example, a scheme with 128 bits of security could mean any of the following constraints on winning attack strategies are met depending on the nature of the particular security game being considered:
- At least 2¹²⁸ work is needed to succeed in one attempt with probability 1
- At least 2³² memory and 2⁶⁴ work is needed to succeed with one attempt with probability at least 1/2³²
- At least 2³² memory and 2³² work is needed to have succeeded (at least) once with probability at least 1/2³² after at least 2³² attempts.
Most often the only resource being considered is the amount of work needed. For example, this is usually the case when making statements about the bit security of a block-cipher (for the PRP security game).
Similarly, suppose H is a secure cryptographic hash function with n bits of output. It is quite common to state that “H can have at most n/2 bits of security for collision resistance due to the birthday attack”. What is meant is that the birthday attack is a generic algorithm running in about 2^n/2steps which wins the collisions finding game for any hash function H with n. However, when considering a different type of security game for H, namely “preimage resistance”, cryptographers usually expect n bits of security.
To give some perspective on these numbers: currently (June 2017), all 500 of the most powerful (known) supercomputers combined can perform approximately 2⁶³ floating point operations per second. An estimate (by AI Impacts) put the sum total of the global computing power (at most) at the end of 2015 at about 2⁷⁰ operations per second.
Providing 128 bits of security today is usually considered sufficient to keep things secure (e.g. a message stays private) for the next 2–3 decades. In practice, light weight devices (e.g. RFID tags) and applications that only require short term security often aim for closer to 80 (or even 64) bits of security to achieve better efficiency.
Having said that, hedging against improved cryptographic attacks on primitives, the advent of practical quantum computers (which could potentially halve the bits of security for most security games pertinent to non-public-key primitives) and aiming for very long term security may mean that more bits of security are desired. For example, 192 bits or even 256 bits of security are common targets.
KEY LENGTH:
Many crypto primitives make use of secret keys. The length of these keys is simply the number of bits required to represent them. For the best symmetric key primitives (e.g. AES) the key length is essentially the same as the bits of security provided by the primitive. For other classes of primitives, this is not true at all. For example, for RSA, keys of length 1024 afford around 73 bits of security whereas many Elliptic Curve Crypto primitives with keys of length 256 afford roughly 128 bits of security.
SECURITY PARAMETER:
Crypto primitives and protocols are sometimes equipped with a positive integer parameter called the “security parameter”. The idea is that number of bits of security provided by the scheme (in some implicit security game) grows in the security parameter. In fact, the terms are often used in very similar ways.
Sometimes a primitive will have more than one such parameter (e.g. the password hashing algorithm Argon2) where different parameters scale different aspects of the security guarantees. For example, Argon2 has two security parameters for scaling the amount of memory an adversary needs independently from the amount of time the adversary needs to compute Argon2.
This table contains a list some of the most common algorithms of various kinds organized according to their type and the number of bits of security they provide. Both the signature scheme (e.g. ECDSA and EdDSA) and the Diffie-Hellman key exchange protocols (e.g. ECDH and X448) inherit the number of bits from the underlying curve they use.
Cryptographic Hash Functions
The bit-security of a cryptographic hash function depends on the application for which we want to use it. This explains the discrepancy between the entries under Collision Resistance and KDFs in Table 1. The entries for KDFs for high entropy sources in Table 1 are based on the assumption that HMAC-SHA256 behaves essentially like a keyed random function. If this is the case, then security proofs for the HKDF constructions imply that HKDF-SHA256 already has 256 bits of security in the KDF security game.
Authenticated Encryption
Authenticated encryption (with associated data) is quickly becoming the standard security required of a symmetric key encryption scheme. Similar to the case of hash functions, AE security actually considers resistance to two separate attacks. The first (called “indistiguishability against chosen plaintext attacks” or IND-CPA) ensures message privacy while the second (called “integrity of cipher texts” or INT-CTXT) ensures message integrity. That is, INT-CTXT security ensures that creating a cipher text that decrypts to a valid message requires actually knowing the decryption key.
As such real world AE schemes such as AES256-GCM often target two different levels of bit-security depending on which attack is considered. In Table 1 the bit-security of AES256-GCM with respect to the IND-CPA attack is listed. The security with respect to INT-CTXT actually also depends on how long of an authentication tag is used with AES256-GCM. In practice this tag is 128-bits long (or shorter). That means that, despite the long encryption keys (256-bits) being used AES256-GCM only affords at most 128 bits of security in the INT-CTXT game.
To understand the design choice behind this gap in bit-security levels, it is helpful to consider the nature of the attacks being defended against by IND-CPA and INT-CTXT security. Put simply, while INT-CTXT usually defends against “on-line” attacks IND-CPA also defends against “off-line” attacks. As the former place much greater constraints on the time (and number of attempts) available to an attacker, it may often be reasonable to trade the added efficiency gained for the relative loss in security by targeting 128 bits of security instead of 256 bits for INT-CTXT. A bit more concretely — INT-CTXT security can be used to prevent an active man-in-the-middle adversary from transparently altering the contents of an exchange between two devices in real time by modifying/inserting new cipher texts into the message flow between the devices. In order to be successful, such attacks must usually be mounted within just a few seconds or minutes. In contrast, IND-CPA security is often used to prevent an attacker from breaking the privacy of an encrypted message even years after they obtained the ciphertext. With so much more time available the attacker could dedicate far more resources (and even new technology) to the attack and so a higher bit-security may be desired. This observation motivates the gap between the bit-securities of AES256-GCM with respect to IND-CPA and INT-CTXT.
KDFs for Low Entropy Sources
You may notice an omission in Table 1, namely Key Derivations Functions for low entropy sources (e.g. scrypt and Argon2). The reason for this is that it doesn’t quite make sense to speak of the bits of security provided by such functions. When a cryptographic key is derived deterministically from a low entropy source using a (reasonable) KDF, it will invariably be much more efficient to simply brute-force all possible inputs to the KDF than to try some other, more complicated, attack on the KDF itself.
In other words, the best attack on applications of KDFs is practically never to attack the KDF directly but rather to attack the low entropy source of data which is being fed into the KDF. As such it would be quite misleading to say that, for example “scrypt provides 128 bits of security” when it is being used to derive a key from a password which actually only has 40 bits of entropy.
The Bit-Security of the Wickr Protocol
Generally, in any application making use of several cryptographic primitives the final product is only going be as secure as its weakest link. For example, if we want to derive encryption keys for a block cipher that has 256-bit security then it makes sense to use a KDF and key agreement protocol with the same bit security. Otherwise, the bit security of the block cipher is undermined simply by attacking the key derivation process.
The Wickr protocol targets 256-bit security (for both on and off-line attacks). This choice is primarily motivated by the goal of long term security. As the protocol is used to communicate over public networks it is necessary to assume that an adversary can record traffic today and store it for later analysis, possibly years down the line. Thus, it is crucial to make the Wickr protocol as future proof as possible.
For starters, this means that the target bit security of the protocol should ensure that no attacker can muster the necessary resources to breaking security with any existing techniques in the foreseeable future (despite the progression of Moore’s law and similar trends). However, it also means that the target bit-security should hedge against improvements in cryptographic attacks on the underlying primitives.
While it is rare for primitives as well-studied as those used by Wickr to suffer unexpected catastrophic breaks at such a late stage in their development, smaller, more incremental attacks can, by no means be ruled out. So, to ensure 256-bits of security the Wickr protocol makes use of the following primitives:
- Signatures and key agreement using ECDSA and ECDH on Curve P-521
- Key derivation using HKDF-SHA256
- Encryption using AES256-GCM (used for privacy of messages. Integrity is ensured using ECDSA.)
You can learn more about Wickr’s messaging protocol and the primitives used in it here.