Hot answers tagged

10

This isn't really a "hard" answer, but an attempt to give some intuition or motivation. One can interpret indistinguishability as an overapproximation of the most common notions of security: Any system that is broken in a more practical way will also fail to meet indistinguishability, that is, all practically important security requirements are in fact ...


10

The usual approach to prove IND-CPA security is to construct a logical argumentation called "reduction". In this argumentation you first start with the assumption that certain computational problem is hard (for example, the Decisional Diffie-Hellman assumption), and then you proceed to demonstrate that if your crypto scheme were insecure with respect to IND-...


9

Katz & Lindell mention in their book "Introduction to Modern Cryptography: Principles and Protocols" an example of an IND-CPA attack from World War II. Navy cryptanalysts suspected that Japanese ciphertexts containing the fragment "AF" where referring to the Midway island. Then, they told officials at Midway to send unencrypted messages reporting they ...


5

Well, to start off with, we have: $$k_1 m_1 + k_2 - n_1 p = c_1$$ $$k_1 m_2 + k_2 - n_2 p = c_2$$ $$k_1 m_3 + k_2 - n_3 p = c_3$$ Where we know $m_1, c_1, m_2, c_2, m_3, c_3$, and we don't know $k_1, k_2, p, n_1, n_2, n_3$. I chose to use explicit unknown integers $n_1, n_2, n_3$, rather than modulo an unknown $p$, as it makes it easier to justify the ...


5

The first remark is that the cryptosystems are used with independent keys. This is important, otherwise it is usually very hard to prove anything. The simple solution Now, the simple solution is, as is mentioned in the comment and the linked question, is to secret-share your message into two shares and encrypt each share separately. The final ciphertext ...


5

Suppose you do CTR mode as: $E(k,nonce+1) \oplus m_1$, $E(k,nonce+2) \oplus m_2$, $E(k,nonce+3) \oplus m_3$, etc. The wikipedia page is talking about a non-random nonce, with a specific example of a packet counter. So suppose $nonce$ is a packet counter and in each packet you encrypt several blocks. You might end up with the following: In packet #$p$: ...


4

The property you are probably looking for is whether the MACs are PRF. With HMAC it depends on the pseudo-randomness of the hash function used. If the hash is a PRF then the HMAC is as well. However, that is not required for MAC security of HMAC, so it's not necessarily true even with a secure HMAC. See New Proofs for NMAC and HMAC: Security without ...


4

If you have a stream, $s$, of $n$ bits that is computationally indistinguishable from random, then any truncation of that $n$ bit string must also be indistinguishable from random. The proof of this is straightforward. If $s$ was computationally indistinguishable from random, but some truncation of $s$ was not then we could distinguish the larger sequence ...


4

To decrypt, you basically take the $g^y$ component and raise it to the secret key, obtaining $g^{yx}$. Now, if this value is equal to the second component of the ciphertext, you can see that $M$ must be 0, since $g^{yx} = h^y$; otherwise, $M$ is 1. Regarding the proof: yes, it would be very similar to ElGamal, since you have to construct the challenge ...


4

Although your scheme is secure - especially with a random key of 32 bytes or higher - it won't offer any benefit over HMAC. It's therefore not recommended to use such a scheme. Also note that `bcrypt has been designed for key stretching which is deliberately not efficient. You have ample entropy in your key so there is no need for key stretching.


3

As CodesInChaos notes in the comments, having more ciphertext–plaintext pairs doesn't help with brute force guessing attacks. Well, that is, except for the minor issue of unicity. Basically, to narrow the results of your brute force attack down to a single key, you do need to have enough ciphertext–plaintext pairs that the length of the known plaintext ...


3

Ask a CPA-query with a known $m$ and get back $c_0,c_1'$. Compute $c_1'' = c_1' \oplus m$. Then, compute $F^{-1}_r(c_1'')$ and this will be $k$. Now you know the key. Of course, this attack assumes that you can invert $F$, but nothing in the definition says you cannot (and in practice you often can).


3

You need to allow queries before the attacker outputs $m_0,m_1$ since maybe the queries help the attacker choose $m_0,m_1$ that are "easier" for it to attack. You need to allow queries after the attacker receives back the challenge ciphertext $c=E_k(m_b)$ since knowing $c$ may make it possible to generate a plaintext whose encryption helps to know what $c$ ...


3

IND-CPA is equivalent to semantic security under CPA.


3

The idea behind these models is to model an adversaries capabilities. To get reliable security the worst case for a capability is modelled. Let's start with chosen plaintext attacks (CPA): In this game the adversary is given access to an encryption oracle. This models the case where an attacker knows (parts of) the message. For example, the British knew ...


3

As SEJPM said in his comment: one proceeds by contrapositive, first suppose that such an adversary with an unfair advantage exists and use that adversary to break a well known assumption, e.g.: the adversary can be used to factorise a large composite integer (as defined in RSA). As of today, we have no efficient algorithm to factorise large composite ...


3

Tape is a basic concept from Turing machines. The random tape is the tape with random bits on it.


3

The question is how much is this schema secure? Not significantly more secure than sha256(m + k) is and may be less secure. An attacker who could arrange a collision for that would trivially also get a collision for the bcrypt hash of that, regardless of the salt value. While SHA-256 is collision resistant, there are MACs that have better bounds, like ...


2

It can be proved, mathematically, that your (2), (3), and (4) are all equivalent under chosen plaintext attack. That is, if you can do any of those things then you can also do the other two! It should be obvious that (2) implies both (3) and (4): if you can decrypt a message then you know which message it is, and also you know it's not random noise. The ...


2

First determine the permutation domain. If $L_2 > L_1$, then the cipher is broken by $\lceil log_2 (L_2) \rceil$ pairs of plaintext/ciphertect. The security improvement is small, as the attacker only needs to use $\lceil log_2 (L_2) \rceil - \lceil log_2 (L_1) \rceil$ additional pairs to find the key.


2

"What prevents an attacker from just sending the received ciphertext to the recipient who will think that this is the legitimate message?" Nothing. $\:$ (In that case, the recipient will be correct.) Why "in the definition" is the attacker "only allowed to send another" message? If he knows before seeing the ciphertext that it will be an encryption of ...


2

I will think more about a proof/counterexample for #1, but here is a counterexample for #2. Let $\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec}$ refer to a CPA-secure encryption scheme with message space $\{0,1\}^\lambda$, and define the following modified scheme: $\mathsf{KeyGen}'$: run $sk \gets \mathsf{KeyGen}$ and sample $m^* \gets \{0,1\}^\lambda$. The ...


2

Insecure, since an attacker A is not only given the ciphertext $c$, but also the key $r$ with which the message was encrypted. Thus, it can easily decrypt the ciphertext. Correct, there is no encryption here. I would say that it's not IND-CPA secure, since it's deterministic. Is that true? And how can I prove/determine whether it's IND-COA secure?...


2

This scheme does not have indistinguishable encryptions since the encryption function does not use the key, so an adversary can run the decryption function in the same way as the intended recipient. This scheme is not CPA-secure because it is deterministic (so it does not even have indistinguishable encryptions for multiple messages). To show that it has ...


2

Cryptograph Network Security by William Stallings is pretty decent read I had to read in my crypto class. Each encryption method is different, the way you can test its effectiveness as a encryption method is by what they call avalanche effects , where by changing one bit in decryption it changes a lot of other bits throughout the process. Also I recommend ...


2

Does this attack work? Yes, it works. However, "textbook" McEliece was never claimed to be IND-CPA. In fact, it was already published in 2008 by Nojima et. al. in "Semantic Security for the McEliece Cryptosystem without Random Oracles" (PDF). They also propose a mitigation in the paper, which is to simply front-pad the message with sufficiently many ...


2

Sure. one-way permutation ​ + ​ strong hard-core functions $\to$ pseudorandom generator $\to$ stream cipher The keystream is concatenation of the strong hard-core function's values at the iterates of the one-way permutation on the key. ​ ( k,f(k),f(f(k)),f(f(f(k))),... )


2

A one-way permutation is just a one-way function in which the function is a permutation (id est, a bijective function). Every OWP is a OWF, the converse is not true. IND-CPA security is a security notion specifically related to encryption schemes. OWF and OWP are not encryption schemes, hence they cannot be said "IND-CPA secure"; however, one can construct ...


1

The Game described in #1 is equivalent to IND-CPA security according the CRYPTUTOR wiki from UIUC (The section on modifications). This may explain why Mikero had trouble coming up with a counter example.


1

"You can prove that for every polynomial time attacker that uses the encryption oracle after receiving the challenge cyphertext, you can construct another polynomial attacker that also breaks the encryption scheme only querying the oracle before receiving the challenge cyphertext." Actually, that is not true in general; you need to make further assumptions ...



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