121

A random oracle is described by the following model: There is a black box. In the box lives a gnome, with a big book and some dice. We can input some data into the box (an arbitrary sequence of bits). Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the ...


70

The SSH protocol has a complicated record format with an encrypted message length, variable padding, encrypt-and-MAC, etc. This complicated system, which was designed without any formal analysis relating the security of the system to the security of the building blocks, turned out to be vulnerable to an attack (paywall-free) exploiting the MAC verification ...


42

The ideal encryption scheme $E$ would be one that, for every ciphertext $C=E(K, M)$, if the key remains secret for the adversary, the probability of identifying $M$ is negligible. Since that is not possible in practice, the second most reasonable approach is to define constraints strong enough to satisfy some definition of security. The $\operatorname{IND-}$ ...


41

That New York Times article actually continues after that quote: Dr. Neumann explained that there are always ways to get around cryptography barriers and that these methods have nothing to do with breaking codes. "It's like the voting machines," he said. "You'd like to have some integrity in the electoral process and now folks are coming out of the ...


34

Disclaimer: I use Coq on daily basis... I have seen in some places that people use formal verification and/or computer-aided verification for cryptography. To my knowledge, there aren't that many places that do such a thing. First, let's define our concepts: Formal Verification: The act of proving the correctness of algorithms with respect to a certain ...


29

Your second question was about programmability. This hasn't been directly addressed yet by Thomas' answer or the comments, so I'll focus on that question only. Unfortunately I don't know of a simple primitive that is secure in the random oracle model that requires programmability, but I'll use one that is hopefully clear once I explain the background. It's ...


29

I am struggling to understand what is meant by "standard cryptographic assumption". ‘Standard assumption’ broadly means an assumption that has withstood the scrutiny of many smart cryptanalysts for a long time. Examples: We think that, for uniform random 1024-bit primes $p$ and $q$, solving $y = x^3 \bmod pq$ for uniform random $x$ is hard given $pq$ and $...


22

Bruce Schneier foresaw your skepticism and directly answered this question in "Applied Cryptography": Known-plaintext attacks and chosen-plaintext attacks are more common than you might think. It is not unheard-of for a cryptanalyst to get a plaintext message that has been encrypted or to bribe someone to encrypt a chosen message. You may not even have to ...


21

You don't want to use something like the Mersenne Twister for gambling. It is not cryptographically secure. Given a small amount of output, it is relatively straightforward to compute all future outputs. These algorithms are designed for things like Monte-Carlo simulations and things of that ilk. A better option is to select a 128-bit key at random and ...


20

Using the book as a key is relatively similar to one-time pad, insofar as the book can be considered as a random stream of characters. But that's true only to some extent: a book consists of words, with meaning, which implies that characters which may appear at position 321:42:35 are not uncorrelated with characters which appear at positions 321:42:34 and ...


19

(Notation. Sets are represented using the calligraphic font and algorithms using the straight font. Throughout, $\Sigma:=(\mathsf{K},\mathsf{S},\mathsf{V})$ denotes a signature scheme on a key-space $\mathcal{K}$, message-space $\mathcal{M}$ and signature-space $\mathcal{S}$. Since only a single key-pair is involved in the discussion, to avoid cluttering, ...


18

When choosing curves for use in elliptic curve cryptography, some have suggested using various classes of curves which avoid certain "bad" properties which would make the system vulnerable to attack. The MOV attack breaks the ECDSA on a class called supersingular curves. To avoid this, some suggested using curves from another class called anomalous curves, ...


17

Solutions to Yao's Millionaire's Problem should suffice for this computation. In that setup, there are two parties each with an input. The output reveals whose input is larger, and nothing else. So Alice and Bob just run the protocol with their respective inputs A and B.


17

It's not necessary that you encounter a situation like this in the real world to motivate the definition. There are some weaker adversaries that you would like to rule out in your security model, and CPA-security usually would encompass them all. Think for example of an encryption scheme which is intended to be used to encrypt one bit, like "yes" or "no". ...


17

Practical chosen-plaintext attacks have been discovered against modern cryptosystems like TLS/SSL. One noteworthy type of vulnerability can occur when a cryptosystem includes a compression step before encryption (which TLS used to do). This led to several well-known exploits such as CRIME and BREACH. In CRIME, the adversary attacks a visitor of a HTTPS-...


17

Are all encryption algorithms with fixed-point free permutations inherently flawed? Yes - when fixed points, or the lack of them, is knowable and detectable. This is a violation of multiple modern semantic security definitions. For example, this means that plaintexts with repeating symbols are distinguishable with high probability from plaintexts that ...


16

Are all encryption algorithms with fixed-point free permutations inherently flawed? No, they are not inherently flawed. Consider the following cipher: Let $k_0$ be a key for AES-256, and let $k_1$ be a key for a hypothetical Advanced Derangement Standard, ADS-256. To encrypt the $n^{\mathit{th}}$ message $m$, the ciphertext is $$c = m \oplus \bigl[\...


15

As the other answers already state here, game-based definitions are easier to write proofs for, but simulation-based definitions are often clearer in terms of the security guarantee that you get. The best example of this is IND-CPA (game-based definition) versus semantic security (simulation-based definition). Note that IND-CPA is really not a convincing ...


15

I hope I got your point and try to answer your question. Actually, if I understand you right, then what you call an attack actually means an adversary acting in a specific attack model. To clarify this, we need to review the security models for digital signature schemes and when we have discussed this we can clarify issues. Basically, we have to discuss ...


15

In theory. No. The inverse of a secure PRP need not be a secure PRP. Here is what we can guarantee. The inverse of a secure sPRP (strong-pseudo random permutation) is guaranteed to be a secure sPRP. Any secure sPRP is a secure PRP. Therefore, the inverse of a secure sPRP will be a secure PRP. FYI, if you are not familiar with PRP/sPRP, the difference ...


15

Reductionist security In a reductionist security proof for some cryptographic protocol $\Pi$ to some alleged hard problem $P$ means, that we can build an algorithm $\cal B$ for solving $P$ if we have access to a hypothetical algorithm $\cal A$ that efficiently breaks the security definition for the protocol $\Pi$. In general, showing a polynomial time ...


14

A random oracle is an ideal object; see this previous question for some details. What makes a random oracle convenient for proofs is the part about knowing nothing on the output for a given input if you do not try it. For instance, consider the following encryption scheme: $H$ is a random oracle which outputs $n$-bit values. The key is a $K$, a string of $k$...


14

One line: worst means any and average means random. Lattice-based cryptosystem Let me restate. Fix security parameter $n$. What the reduction shows is the existence of a solver for the lattice problem on input any $n$-dimensional lattice using the adversary breaking a lattice-based cryptosystem with the security parameter $n$ on the average case. Since ...


14

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.


14

Every cryptosystem is "provably secure" under at least one hardness assumption: the assumption that it cannot be broken. Hence, the only question which matters is whether a cryptosystem is provably secure under a well-known and well-studied assumption. This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with ...


13

There are a couple of options for protocol analysis tools. (I don't know any established tool for their design - as said by someone else, designing your own protocols is not really recommended.) If you are looking for formal methods based, symbolic tools, some well-known tools that have been applied to many protocols are ProVerif and Scyther. Given that you ...


13

When cryptographers create algorithms, they usually provide some argument that the algorithm is secure. They need to start the argument with some set of assumptions. For example, the in public-key cryptography, they may begin with the assumption that factoring large numbers is hard. Many algorithms use use a block cipher as a building block. The arguments ...


13

Computationally indistinguishable typically means that your adversary is computationally bounded and that because of this they cannot distinguish between, for example, two messages. For example, say you encrypt (with proper padding) the messages $0$ and $1$ using RSA and send them to the adversary. We would not want the adversary to be able to distinguish ...


13

A fast 64-bit hash cannot be completely secure, since a $2^{32}$ brute force collision search is completely doable, and even a $2^{64}$ preimage attack could be feasible. As a MAC used for hash table keying, that doesn't really matter (unless you leak the key). Finding just a few collisions isn't a problem and gathering statistics for an attack would ...


13

Let me try to answer your second question, and hopefully shed some light on the first one in doing so. When we encrypt a message, it's because we want to keep something about that message secret. But what is it that we actually want to protect? Let's say the message we're encrypting is AGENT DOE REPORTS 23 UNITS ON BOARD SHIP TO BASE ALPHA, DEPARTED ON ...


Only top voted, non community-wiki answers of a minimum length are eligible