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-}$ ...


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 ...


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-...


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 ...


12

The LWE assumption I think we should start from the LWE assumption. Let $n$ and $q$ be integers and let $\chi$ be a distribution over $\mathbb{Z}_q$. We often take $\chi$ as a Gaussian with small variance. (We take an error $e$ from this distribution $\chi$ and assume that $|e| \ll q$.) The LWE assumption states that any efficient adversary cannot ...


11

There are some interesting examples in section 3.4.2 of Katz-Lindell book. Here is just one of them: During World War II, the British placed mines at certain locations and (intentionally) managed to let the Germans discover them. They knew that the Germans would encrypt the locations and send back to the headquarters. These encrypted messages were used by ...


9

Repeatedly encrypting the same message to the same ciphertext is full of practical attacks. Encryption is supposed to leak no information about the content of the message other than its length, and there are very real ways to exploit the information leakage you mention. Some of them have to do with the fact that plaintext domains are not always very large. ...


8

The proof for the perfect secrecy property of the one time pad is quite simple. It makes use of basic probabilities and it says that: $$Pr[M=m|C=c]=Pr[M=m]$$ for a probability distribution M$\{0,1\}^n$ for the message space and a probability space C for the ciphertext space. Proof: $$Pr[C=c]=\sum{Pr[C=c|M=m']\cdot Pr[M=m']} =\sum{Pr[K=m'\oplus c]}\cdot ...


8

Yes. Such proofs are possible for El Gamal. It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption. Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal. Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is ...


8

Well, whether it is a secure tweakable block cipher depends on how resistant (E,D) are to related key attacks; that's not a standard assumption for block ciphers. For example, this would not be a secure tweakable block cipher with 3DES; because every 8th bit is ignored, the attacker can effectively test the value of the 7 adjacent bits (except for the 7 ...


8

The lead up to the Battle of Midway also involved a chosen plaintext attack. The Americans had mostly broken the Japanese code JN-25b, and knew the Japanese were attacking "AF". They guessed that "AF" was Midway, but to be sure they had Midway send a cleartext message that their fresh water system was broken, and soon picked up a Japanese message "AF was ...


7

In your formula, $n$ appears to relate to the key space, not the message space. The message space does not intervene in the definition of IND-CPA, and that's a good thing because practical message spaces consist in messages which "make sense" in a given context. There are situations where the attacker already guesses quite a lot of the attacked message, and ...


7

Encryption using a block cypher such as AES by passing plaintext blocks directly to the encryption function is known as Electronic Code Book mode (ECB) and is not CPA secure as (as you say in your question) it is entirely deterministic and two identical plaintext blocks will result in two identical ciphertext blocks. To prevent this an initialisation ...


7

Because (I assume) $g$ is a generator, it is not a square (prove this), so its Legendre symbol is $-1$. And hence, the Legendre symbols of $g^a$ and $g^b$ leak the parities or $a$ and $b$. Hence they leak the parity of $ab$, which leaks the Legendre symbol of $g^{ab}$.


6

I read SHA1 is still a secured hashing function with no collision found as of now. You read an old text, this is not the case anymore since SHA-1 was SHAttered. In Java, we still use SHA1PRNG algorithm in SecureRandom class for the purpose of generating IV (let's say for CBC). Is it enough secured as a PRNG generating unpredictable IV for CBC? Or ...


5

Here is the proof I came up with. Please let me know if you see any problems with it... Statement to prove: If an encryption scheme is secure in the IND\$-CPA sense, then it is secure in the IND-CPA sense as well. i.e. IND\$-CPA $\Rightarrow$ IND-CPA The contrapositive is easier to prove: $\neg$IND-CPA $\Rightarrow$ $\neg$IND\$-CPA. This statement is a ...


5

Cryptography is not just about confidentiality of the message, but also confidentiality of information about the message. Given the ciphertext, an attacker should not be able to determine any information about a message without knowing the key. If you can tell that message A is equal to message B, that's a leak of information. This could be useful when ...


5

The Caesar cipher (aka Shift cipher) has, as you said, a key space of size 26. To achieve perfect secrecy, it thus can have at most 26 plaintexts and ciphertexts. With a message space of one character (and every key only used once), it would fit the definition of perfect secrecy. For the usual use with messages longer than one character, or multiple ...


5

First, on the difference between perfect security and semantic security. Both definitions concern confidentiality, so let us first define what confidentiality means. Note first that an adversary as some a priori knowledge of the message. We can capture that by e.g. having the adversary choose two messages and then flipping a fair coin to decide which one to ...


5

If an attacker can choose the points $P_i$, than this system is not semantically secure. For example, they may choose $P_2=2P_1$, and the corresponding encryption $Q_2$ would be equal to $2Q_1$. If the points are chosen at random, this system is semantically secure if decisional Diffie-Hellman assumption holds for the curve. This assumption is presumed to ...


5

I am stuck at the point where I proved that the complexity is $O(2^\rho)$ using brute-force approach. How shall I proceed? Well, a proof that assumed a specific attack strategy is of limited use, as that proof would be inapplicable if the attacker used some other strategy. Instead, what we typically do in a proof is assume that the adversary had some ...


5

The source is the paper by Goldwasser and Micali on probabilistic encryption. The definition is of primary importance even though it is rarely used to prove security of encryption. The reason for this is that indistinguishability is much easier to use. However, indistinguishability is not a good intuitive definition in the sense that it is not immediately ...


4

Not a complete answer, but since you mentioned "unmodified RSA" I feel it's relevant. Something stronger than vanilla RSA is necessary, even if it isn't semantic security. Example: What if you have a public key exponent of 3 and the symmetric key being encrypted is 16 bytes long? Using raw RSA, $m^e$ would be about $128 \times 3 = 384$ bits long and thus ...


4

I'll answer question 2, leaving the first as an exercise to the reader. I'll do this on intuitive grounds, rather than using explicit conditional probabilities. The adversary is free to compute $v_1\cdot v_2$ regardless of what we ask, therefore removing everything about that and $v_3$ does not change the problem, which reduces to: We somewhat have ...


4

No it's not. As a reminer: Semantic security is equivalent to IND-CPA. Semantic security is less commonly used, because most of the time proofs are less intuitive and more difficult. In the IND-CPA game, the attacker chooses two messages $m_0,m_1$ and sends them to the challenger. The challenger chooses a bit $b$, and sends $Enc(m_b)$ to the attacker. The ...


4

Here is a detailed blog post about the safety numbers: https://signal.org/blog/safety-number-updates/ They are unique per conversation and basically consist of hashes of your and your contact's public long-term key. You should compare them if you want to be sure that there is no man-in-the-middle.


4

Can we analyze using hypothesis testing (given two messages m1 and m2 with the same distribution and analyze whether ciphertext leaks any information about messages) or using entropy bounds? If the output of the key stream generator is indistinguishable from a random stream and uncorrelated to the plaintext, then no, you cannot. Consider the case where we ...


4

but do SSL and IPSec use different key schemes and algorithms from another to establish contexts? Well, given that, by IPsec, you mean only AH and ESP (that is, RFC4301-4303), well, the obvious answer is that IPsec doesn't mandate any way to generate keys, select algorithms, or to establish contexts. All that is assumed to be done by some other protocol (...


4

What you are doing sounds like piling on complexity of dubious value without a clear understanding of what security the components actually provide, in the hope that enough complexity will render the question moot. I would advise you discard the hare-brained scheme you've cooked up and start from something much simpler that is easier to prove theorems about....


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