# Tag Info

19

Modern security has moved beyond looking just at passive attacks (in which the attacker is just a passive eavesdropper seeking to learn what was said); attackers are generally considered to be able and willing to pull off active attacks of various types (in which the attacker can modify or forge messages to achieve some goal). One-time pads are extremely ...

17

Preimage resistance is about the most basic property of a hash function which can be thought. It means: For a given $h$ in the output space of the hash function, it is hard to find any message $x$ with $H(x) = h$. (Note that the it is hard here and in the next definitions is not formally defined, but can be formalized by looking at families of hash ...

14

It fails to be a cryptographically-strong PRNG because it is predictable: given some outputs, you can predict the next outputs. For instance, if you observe the outputs at offsets 0, 1, and 4096, you can predict what the output will be at offset 4097. What it's missing: it's not that it's missing some little tweak (just change line 7 to use addition ...

13

AES is deemed secure because: Its building blocks and design principles are fully specified. It was selected as part of an open competition. It has sustained 15 years of attempted cryptanalysis from many smart people, in a high-exposure situation, and it came out relatively unscathed. Another reason, which is not as good but felt important by many people:...

13

Randomness is not a property of strings of bits (or characters of any sort). Rather it is a property of the process that generates those strings. However, it is convenient to conflate the string with the thing that produced the string, and thus to speak about strings being “random” or “not random”. The string 00000, for example, is random if it was the ...

13

That's not the same kind of key. Symmetric keys are bunch of bits, such that any sequence of bits of the right size is a possible keys. Such keys are subject to brute force attacks, with cost $2^n$ for a $n$-bit key. 128 bits are way beyond that which is brute-forceable today (and tomorrow as well). If a block cipher is "perfect" then enumerating all ...

10

Perfect Secrecy (or information-theoretic secure) means that the ciphertext conveys no information about the content of the plaintext. In effect this means that, no matter how much ciphertext you have, it does not convey anything about what the plaintext and key were. It can be proved that any such scheme must use at least as much key material as there is ...

10

If you sample a random element, then you sample it according to some distribution. Uniformly then means that you sample from the uniform distribution, i.e., you sample it from a set where drawing each element is equally probable. Let us assume you have a set of 4 elements, then sampling uniformly at random from this set, every element is drawn with ...

8

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

8

The paper says that the parameters are $r ≈ 2^{\sqrt \eta}$ and $q ≈ 2^{\eta^3}$. Note that these values are expressed as functions of $\eta$, not $N$. With regard to the parameters, it is common practice to describe them using the asymptotic notation. $\omega(\cdot), \Theta(\cdot)$ and $\tilde O(\cdot)$ are instances of this notation. $\omega(g(n))$ ...

6

The two primary techniques I'm familiar with is structuring a cryptographic primitive as a sequence of games and the universally composable security framework. Sequence of Games The idea here is to represent a protocol/primitive as a game played between an attacker and a challenger. You define a bad event and show through the game that the event happens ...

6

Randomness is the information loss of any causal relationship between events. The universe needn't be a clockwork universe for the assumption of pervasive causality - if events are "sticky" and accrue localised causality in the same way that a molecular cloud accretes into stars and planets. The underlying cause of the speed of light might also be the prime ...

6

This lecture (PDF) has the solution in section 3. Here's my informal explanation of the proof: We have an unpredictable PRG $G$. We want to show that $G$ is secure, or in other words indistinguishable from $R$ (I'll use = to mean indistinguishable whenever referring to two distributions for the remainder of the proof). Using the notation that $G_k R_{n-... 6 A three-round Feistel network is a good example of a realistic construction that is a secure "weak" PRP, but not a "strong" PRP. A Feistel network uses the permutation$P_f(L, R) = R, (L\oplus f(R))$, where$f$is an element of a pseudorandom function family. This PRP will be keyed with three keys$k_1, k_2, k_3$, which will be used to key a PRF$F$... 5 To be concise, true randomness boils down to the selected data being causally unrelated. That is, if each piece of data is the result of no common cause, then there is no relation by which the rest of the data can be predicted or inferred. So being unpredictable is a consequence of being truly random, but it is the lack of causal relationship that is the ... 5 Suppose Alice has$x$and Bob has$y$in your scenario, and let$\pi =(\pi_A, \pi_B)$be the protocol machines for Alice & Bob respectively. Here is how you would formally define security of the protocol against a corrupt Alice. Define the following algorithms / random variables:${\sf Real}(\pi, y,\mathcal{A},1^k)$: Internally simulate an instance ... 5 A collision attack is the ability to find two inputs that produce the same result, but that result is not known ahead of time. In a typical case (e.g., the attack on MD5) only a relatively small number of specific inputs are known to produce collisions. Collision resistance obviously means that a collision attack is difficult (for some definition of "... 5 By a generic attack we also understand an attack that with minimal corrections would apply to every block cipher. For example, suppose you have a (plaintext,ciphertext) pair and test keys by exhaustive search: you apply the keyed cipher$E_K$to plaintext$P$for every$K$and check if you get ciphertext$C$in response. Quite often, the ciphertext bits ... 5 Without the specific reference I can't be sure this is what you are talking about, but generally a "long message" attack is a way to defeat second preimage resistance with less complexity than expected. It uses a time-space tradeoff to find a second preimage with complexity$2^{n/2}$for a$n$-bit hash function (normally you would expect$2^n\$). In the ...

5

Your explanation is "broken in the academically sense" - there is a theoretical way to break the algorithm better than brute force. AES is broken in this way. There's also "broken in the practical sense", which means you can break an cipher in real applications or protocols. AES is still save in this sense, because you still need too much compution power and ...

5

fkraiem's answer is correct, but more context is required, in my opinion. The one-time pad (the theoretical device) has not been broken. But real-world systems based on the one-time pad have failed in practice. Systems based on one-time pads have failed in the past because key material has been reused, either by mistake or because the sender had ran out of ...

5

In a lot of cases OTP will be completely impractical. If instead of a truly random pad you use a pseudo random pad, you will have something a lot more practical. But it is no longer OTP, and the security proofs about OTP means nothing in that case. I think this is the essence of the Bruce Schneier quote you mention. If we for a moment ignore the impractical ...

5

Informally, CCA2 does not permit any kind of modification of ciphertexts, while RCCA permits some alteration as long as it does not alter the original message. For example, think of a publicly randomizable encryption scheme, that is, a scheme that permits to alter the original randomness used during encryption. CCA2 would consider these ciphertexts as ...

5

The operation does not have to be the same. For example, with Paillier, we multiply ciphertexts to get the addition of the plaintexts. That said, I think what the 2nd quotation is saying is that the operation that is passed to the oracle is the desired operation in the plaintext domain. The oracle knows how to translate that operation into something that, ...

5

There is actually a field of study regarding provably secure block ciphers. The seminal paper was "How to construct pseudorandom permutations from pseudorandom functions" (1988) by Luby and Rackoff. Their paper used pseudorandom round functions in a Feistel construction, and proved that 4 rounds were sufficient to make the resulting block cipher a ...

5

In order for information-theoretic security to imply computational security, you need to require that the simulator run in time that is polynomial in the running time of the real adversary. This is the standard definition, specifically to avoid protocols such as you presented in your question. So, the answer is: If you allow the simulator to be unbounded ...

4

Often the hash (iterated and salted mostly) of a password is saved in a database, instead of the password. If a user logs in, the hash is computed and compared against the stored hash value. This way a user that can see the database of hashes does not see the password directly, but this property depends crucially on the hash being resistant to a pre-image ...

4

The encryption scheme in the experiment you describe does not have to be fixed-length. We simply require that the two messages the adversary sends to its oracle have the same length. The restriction is on the adversary, not on the encryption algorithm. So why do we put this requirement on the adversary? The reason is that in every practical encryption ...

4

Does anyone have a reliable source for this? Well, you are asking about the definition of a CSPRNG, and whether this second criteria is a necessary part. Well, it comes down the to exact definition of the term 'CSPRNG'. If we define a CSPRNG as something that generates output which is indistinguishable from random (your first criteria), then a CSPRNG ...

4

Advantage and success probability are just words. Their meaning is in practice decided by how the speakers of the language use the words. You have observed that people use the terms advantage and probability in this way. One could probably argue that this is confusing or illogical or something like that, but such is language. About dividing by two: remember,...

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