Hot answers tagged

17

This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed. Now, the first important thing to note is ...


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


9

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 $IND-$ notation ...


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


7

No. There is a difference between the type of a cipher and the construction of a cipher. If a cipher is of a specific type for which there are known IND-CPA secure constructions then that doesn't mean that an entirely different construction is secure. There are known attacks on stream ciphers, including "modern" stream ciphers such as RC4. A stream cipher ...


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


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

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


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

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

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

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

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

No. Indeed, as in the answer by Maarten, it depends on the security and strength of the stream cipher. However, even if the stream cipher is a secure pseudorandom generator (which is its proper modeling), encryption is not necessarily CPA-secure when XORing the pad with the plaintext. This is also explained in great detail in Katz-Lindell. In fact, it is ...


2

Here's an artificial example: Start with some secure encryption scheme with encryption function $\mathcal{E}(\cdot)$, and construct a new scheme with encryption function $\mathcal{E}'(\cdot)$, which for any input message $m$ copies the first bit, $b$, of the message, and outputs $b||\mathcal{E}(m)$, where $||$ denotes concatenation. For such a scheme, ...


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

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

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

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

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


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



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