Tag Info

8

Not all ciphers can be broken, even by infinitely powerful adversaries. When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need as much key material as you have plaintext to encrypt. Such a key needs to be shared between the two ...

7

Well, how resistant to attack would depend on what security properties you would need from it. There are three standard assumptions we can make about a hash function: Given a hash value, it is difficult to find an image that hashes to that value; this is known as preimage resistance Given a image that hashes to a specific value, it is difficult to find ...

7

I hope I got your point and try to answer your question. Actually, if I understand you right, then what you call an attack actually means an adversary acting in a specific attack model. To clarify this, we need to review the security models for digital signature schemes and when we have discussed this we can clarify issues. Basically, we have to discuss ...

7

Computationally indistinguishable typically means that your adversary is computationally bounded and that because of this they cannot distingush between, for example, two messages. For example, say you encrypt (with proper padding) the messages $0$ and $1$ using RSA and send them to the adversary. We would not want the adversary to be able to distinguish ...

7

Basically, every time you choose a group where the required hard problem is not hard, then you will run into a problem. Even if we have a problem instance that is of size that is considered secure in the setting of asymmetric cryptography. Lets for instance implement a discrete logarithm style cryptosystem in the group $Z_n$ with addition and let $g$ be a ...

7

One line: worst means any and average means random. Lattice-based cryptosystem Let me restate. Fix security parameter n. What the reduction shows is the existence of a solver for the lattice problem on input any n-dimensional lattce using the adversary breaking a lattice-based cryptosystem with the security parameter n on the average case. Since we can ...

6

DrLecter gave a good answer, I just wanted to include another well-known example. The Pohlig-Hellman algorithm can be used to compute discrete logs in groups whose order is a smooth integer. If two parties executing a textbook Diffie-Hellman key exchange use as their modulus a prime $p$ such that $p-1$ has only small factors (is 'smooth') an eavesdropping ...

6

It is equivalent to the computational Diffie-Hellman problem; if you can one of the two problems, you can solve the other (with a polynomial number of queries to the oracle which solves the other). If you can solve the Diffie-Hellman problem, you can solve your problem: this can be seen by first noting that, with a Diffie-Hellman solver, given $g^b$, you ...

6

I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time" Using a perfectly random key which is as long as the message itself, not a pseudo-random key, cannot be broken no matter how fast the attacker's computer is. This scheme is called one-time-pad and its security is guaranteed by information theory ...

6

There is no direct inference from $P = NP$ or $P \neq NP$ to security or insecurity of any particular encryption algorithm. As far as practical consequences are concerned, the "$P = NP$" problem is severely overhyped. If $P = NP$ then any problem for which a solution can be verified in polynomial time can also be solved in polynomial time. "Polynomial time" ...

6

A fast 64-bit hash cannot be completely secure, since a $2^{32}$ brute force collision search is completely doable, and even a $2^{64}$ preimage attack could be feasible. As a MAC used for hash table keying, that doesn't really matter (unless you leak the key). Finding just a few collisions isn't a problem and gathering statistics for an attack would ...

5

Actually, it's not true that public key encryption is based on Discrete Log; the ones in common use (DH, ECDH, ECDSA) are (and even RSA can be viewed as "based on Discrete Log", at least from the standpoint of "if you can solve the Discrete Log modulo a composite, you can break RSA"). However, we do have a number of public key systems (NTRU, McEliece) which ...

5

The probability of someone 'getting lucky' with a guess at a key for a decent cryptosystem is crazily low, but yes: it is possible. However, there are methods that can 'survive' even this. For example, consider the one time pad. In this system the key and plaintext are xor'd together to form the ciphertext, and to decrypt you xor the ciphertext and key. ...

5

Intuition The intuition behind the proof is that a valid ciphertext is correctly generated and, thus, an adversary should query to the random oracles to generate random strings in the ciphertext. In addition, notice that the hash value on an unqueried string is undetermined (to the adversary) in the random oracle model. Therefore, the chance to construct a ...

5

This scheme is insecure, as anyone with the public key can generate a forgery of an arbitrary message. To do this, the forger would take the message $M$, the public key $y$, pick an arbitrary $z$, and compute $r = y^{-H(M)} g^{z} \bmod p$ and output $(r,z)$

4

Here's a nice paper I came across a while ago: Wooding, Mark (2008), "New proofs for old modes", Cryptology ePrint Archive, report 2008/121: "Abstract: We study the standard block cipher modes of operation: CBC, CFB, and OFB and analyse their security. We don't look at ECB other than briefly to note its insecurity, and we have no new results on counter ...

4

No, the signer is per definition in possession of the secret signing key and thus can always produce signatures for any message of his choice. Consequently, a notion of unforgeability is not meaningful with respect to the signer. For a signature scheme one requires unforgeability for parties who are not in possession of the secret signing key but only the ...

4

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

4

Not if the attacker is given enough time to ask for the values $F(k,x)$ for all $2^n$ values of $x$. We have $\Sigma_x F(k,x) = 0$ which is distinguishable from random.

4

Theorem. (Barring any errors, which are certainly possible): Let $A$ be any adversary attacking $F$. As long as $A$ makes fewer than $2^n$ queries, there is an adversary $B[A]$ attacking $f$, making at most twice the queries of $A$ and running in (roughly) the same time such that $\mathsf{Adv}^{\mathsf{prf}}_F(A) = \mathsf{Adv}^{\mathsf{prf}}_{f}(B[A]).$ ...

4

Yes, it is a secure PRF, as long as the attacker can make at most $2^n-1$ queries. The key lemma is purely information-theoretic in nature. From this lemma, you can prove your result using standard methods. Lemma. Let $x=(x_1,\dots,x_q),y=(y_1,\dots,y_q)$ are any sequence of $q$ $n$-bit values, where $q<2^n$ and the $x_i$'s are all distinct. Then ...

4

The equation $t'=t+n\cdot t_c$ is an estimation to put an upper limit on $t'$. It might be possible that an attacker $A'$ can use a different, more efficient algorithm. But since the attack will work with using $A$, there exists an attacker $A'$ with at most $t'$. This means it's actually not an equation, but an inequality $t' \leq t + n \cdot t_c$. And then ...

4

As correctly pointed out by Ricky Demer it is not necessarily true. However, this implication does not hold for very specific cases. In the case of random oracle gates the existence of the RO changes the functionality of the "scheme", since with RO there are RO-Gates and without there aren't. In most cases the existence of the RO does not affect the ...

3

I see no reason to expect $x-1+x^N \bmod N^2$ to be indistinguishable from $r$, at least not based upon the assumption you give. The map $f(x)= x^N \bmod N^2$ is a very different map from the map $g(x) = x-1+x^N \bmod N^2$. The range of $f$ is a subgroup of size $\varphi(N)$; that's not true of $g$ (for instance, the range of $g$ can potentially be the ...

3

Can we state that $Adv_{G0} \le Adv_{G_1}$ ? Absolutely. Let us call $S0$ the strategy that $A$ can use in game $G0$ to achieve advantage $Adv_{G0}$; we notice that $A$ can also use strategy $S0$ to achieve that exact same advantage in $G1$, and hence we see that the maximum advantage he can achieve in $G1$ must be at least as large as in $G0$ Can ...

3

For a set of $B$ elements (e.g. $B = 2^n$ for all the "blocks of $n$ bits"), there are $B!$ possible permutations. An ideal block cipher is such that an instance with an unknown key is indistinguishable from a permutation chosen at random, uniformly, in these $B!$ permutations. Since permutations don't commute in general, a "perfect" commutative block ...

3

The classic proof is contained in http://www.cs.ucdavis.edu/~rogaway/papers/sym-enc.pdf (1997), but it is not quite easy.

3

HMAC-SHA-256 is sufficient for up to 256 bit security. Confer e.g. NIST SP 800-107. This recommendation is based on the premise that collision attacks are infeasible against common uses of HMAC, and that you consequently only have to worry about primary pre-image attacks that attempt to recover the secret key (and use this for forging subsequent messages). ...

3

AES is not a one-way permutation; it is a permutation, for sure, but whoever can apply it can also apply its inverse. Crudely said, the AES decryption key is identical to the AES encryption key. A one-way permutation would be like a hash function: everybody can compute it in one direction, with no secret value, but nobody knows how to do it in the other ...

3

The standard definition of existential forgery allows the adversary to ask and obtain the signature of any message she wants, and claim success if she can exhibit (with sizable odds) any acceptable (message, signature) pair, for any message for which she did not ask signature. Update: There is also strong existential unforgeability, where the adversary ...

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