# Tag Info

56

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

14

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

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

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

10

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

9

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 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 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: \negIND-CPA \Rightarrow \negIND\-CPA. This statement is a ... 7 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 (... 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 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 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 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 The initial notion of semantic security from Goldwasser and Micali has been shown to be euqivalent to what we call today indistinguishability under chosen plaintext attacks (IND-CPA). Yes, that's the only security against a passive adversary and actually the weakest reasonable security notion that we use today. The authors of the second paper you link seem ... 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 I consider the SU Cryptography course on Coursera really good, up to certain level is very comprehensive. You should discuss these topics on the Coursera forum, IMHO you will be guided more precisely. You have two questions here and you should know the DEFINITIONS of the secure PRNG and semantically secure encryption. Security of the message differs between ... 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 The definition of semantic security has its origins in the definition of perfect security, where the adversary's information about the message is the same after seeing the ciphertext. Semantic security is exactly the same thing in a computational setting: the adversary's "practically available" information about the message is the same after seeing the ... 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.... 4 It's possible to have a secure encryption scheme that ignores the first half of its key, and a secure OWF that leaks the entire second half of its input. Composing them as in your question results in something profoundly insecure. 3 No. A CRL is as public as the certificate it revokes; it has to be signed to guarantee authenticity, but not encrypted. There are no optional confidentiality requirements for CRL distribution in RFC 5280. It is not even common practice to use anything other than plain http for the CRL distribution points. The whole idea with CRLs is to get them out there to ... 3 Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bitlength is polynomial in the security parameter), and thus allowing the distinguisher to decrypt? This is up to your security ... 3 Spartacus: Maybe i came out with the solution, since the cryptosystem described above is not CCA-secure, an adversary A can intercept (A,B) and compute a new ciphertext$$C = 2B\bmod N = 2^er^e \bmod N$$Since he's carring out a CCA-attack he has access to a decryption oracle and since:$$C\neq B$$the oracle output$$RSA^{-1}(C) = 2^{ed}r^{ed}\bmod N = 2r\...

3

Shift cipher or ceasar cipher attains perfect secrecy only in the special case with the assumption that $26$ keys are used in equal probability in the shift cipher, and to encrypt each symbol we use a different key which is choosen equiprobably (i.e. perfectly random) from the key space. It is easy to check all keys given a plaintext when the key is fixed ...

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