Is there a cryptographic approach to availability

Question

Background

Cryptography can be said to provide the tools used to fulfill the goals of information security.

The three pillars of information security are confidentiality, integrity, and availability.

For confidentiality, we have ciphers. The relevant security models here consider ciphertext-only, known-plaintext, chosen-plaintext, and chosen-ciphertext scenarios (IND-KPA, IND-CPA, IND-CCA, etc). On a finer-grained level, there are attacks such as linear/differential cryptanalysis, and resistance to them.

For integrity, we have MACS and digital signatures. The relevant security models here are UUF-KMA, SUF-KMA, EUF-KMA, UUF-CMA, SUF-CMA, EUF-CMA (see link for full explanation of terms)

The question

Are there analogous security models and goals for availability?

Basic approaches to availability include redundancy in various forms, such backups and distributing content among many machines. A blockchain provides some level of availability from a cryptographic approach.

But is there any approach that defines/proves resistance against a formal consideration of an adversaries powers and goals in the same way that there is for confidentiality and integrity?

Answer 1

Flooding. Consider a node on the internet in conversation with a peer. Anyone can send packets to the node, but only the peer knows the secret key to compute authenticators for the packets so that the node will accept them.

• The maximum amount of memory on the node that an adversary on the network can waste at any given time is the number of packets in parallel that the node can process times the maximum size of a message that the node is willing to accept. Design your protocol with small limits on packet sizes and you reduce this denial of service vector.

  For example, TLS records are limited to $2^{14}$ bytes, or 16 KB. However, TLS is layered inside a TCP stream rather than a packet protocol (unless we're talking DTLS, which by the way gave us Heartbleed). So there's no way for a TLS receiver to drop a packet on the floor—forgery of a TCP segment will kill an entire TLS session. Same with SSH. Oops. Lesson: put crypto at a packet layer, not at a stream layer inside a packet layer.

• The amount of bandwidth still available to the peer is the total bandwidth going into the node minus the amount of bandwidth used by the adversary. There's nothing particularly cryptographic in here, per se—it's just a matter of network or processing capacity. And remember that a well-designed high-level denial of service flood is indistinguishable from a large number of legitimate users.

Erasure. Consider an erasure channel: if a sender sends a packet, the recipient receives it with some probability $p$, or the channel eats it with some probability $1 - p$. An erasure code, such as a Reed–Solomon code, is a method for encoding a message into $n$ packets so that any $k$ of them suffice to recover the message. This raises the probability of transmission, at the cost of bandwidth in the channel. But it also sets a lower bound on the number of packets that an adversary must block before they block a whole message—or, alternatively, sets a lower bound on the number of packets that must make it through for a message to go through, namely $k$ of $n$.

For example, Tahoe-LAFS splits files (‘messages’) into Reed–Solomon shares (‘packets’) to store on different servers. If an adversary like the world's biggest paperclip maximizer (‘capitalism’) decides to erase a storage node, you can still recover your data from the other storage nodes you stored them on. (Tahoe-LAFS also encrypts each file before erasure-coding it, and authenticates each share so the worst the adversary can do is erase a share—attempts at forgery will be detected and function like erasure.)

Proof-of-work. In the Bitcoin network, the fraction of processing power that an adversary controls determines the adversary's success probability at double-spending. Knock off a competitor, and you get a bigger fraction of processing power. (Of course, someone might notice a double-spend in a fork. So there may also be a high expected cost to attempting this attack.)

A little more broadly, the study of how much performance can be attained in a network when a certain fraction of nodes are malicious is the study of Byzantine fault tolerance. Is this ‘cryptography’, per se? I don't know—ask three Byzantine generals and you'll probably get three different answers. But it's the formal field of study for questions like this, with goals and adversaries and true love and castle-storming.

Answer 2

It's surely depends on the model and what the adversary is allowed to do. As mentioned in the other answer, if we take a somewhat restricted adversary, there are means(not purely cryptographic per say) to provide availability. However, cryptography can't do much against an adversary that is allowed to do all that it wants. Such an example could be when the adversary is in control of a communication channel, say an Ethernet cable. In this case, the adversary can just cut it in two an effectively break the communication.

On a more abstract level, we could model an insecure channel as a system with 3 interfaces: one for the sender, one for the receiver and one for the adversary. The sender wants to send a single message and sends a $write(message)$ command that adds $m$ to a multiset $B$ that is empty at the beginning.

The adversary can send a $read$ command and gets $B$, $inject(m')$ and $m'$ is added to $B$, $delete(m)$ and $m$ is removed from $B$.

The receiver sends a $read$ command and gets $B$.

Now given that the adversary is allowed to delete messages, there's really nothing we can do.

I think the contrast with confidentiality for example is that we can assume that the adversary can't read minds(at least for now...).

Answer 3

It's not just error correction codes / erasure codes that directly apply. There's also threshold schemes, most notably threshold signatures and secret sharing schemes.

Threshold signatures uses multiple keypairs from a defined group of keys, where only m of n key is necessary to sign. The values m and n could be anything, like 1 of 2, or 3 of 5 or 80 of 350, or whatever you wish.

Secret sharing schemes (like Shamir's secret sharing scheme) split the secret into multiple pieces, where you again decide the number of pieces in an m of n scheme as above.

In both schemes above, it doesn't matter if some keys or shares are lost if you still can meet the threshold.

For this to provide security against an adversary, you need to distribute your keys / shares physically and use independent communication channels, as a means to avoid a single adversary successfully destroying or censoring them all.