# Tag Info

11

In theory. No. The inverse of a secure PRP need not be a secure PRP. Here is what we can guarantee. The inverse of a secure sPRP (strong-pseudo random permutation) is guaranteed to be a secure sPRP. Any secure sPRP is a secure PRP. Therefore, the inverse of a secure sPRP will be a secure PRP. FYI, if you are not familiar with PRP/sPRP, the difference ...

8

The generic model for a MAC is the following: the attacker is given access to a block box which implements the $S$ function with a key $k$ that the attacker does not know of. The attacker is allowed to make $q$ requests to the box on messages that he can choose arbitrarily. The goal of the attacker is to make a forgery, i.e. produce values $m$ and $t$ such ...

8

That sounds like an overly succinct description of the 'Find then Guess' (FTG) notion of security, described in the paper "A Concrete Security Treatment of Symmetric Enryption". And you are correct, there is something the test is missing: the two 'challenge' plaintexts must be the same length ($|m_0| = |m_1|$). Also, the description is so succinct I can't ...

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

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

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

If such a network had only a single round, then you might have a valid concern. This is why there needs to be least three rounds, so that every bit from L can potentially affect every other bit from L (via R from the second round). It isn't a structural flaw, because multiple rounds are assumed. Changing this round structure would mean that it was no longer ...

7

No, this is not a structural weakness of Feistel networks. For instance, we know it can't hurt diffusion properties. Actually, we know that it's not a structural weakness. How do we know that? Because we have a proof of security for Feistel networks (under certain conditions and assumptions). Those proofs imply that there is not a structural weakness in ...

7

An Ideal Cipher with $k$-bit keys and a $b$-bit blocksize is a family of $2^k$ permutations on the set $\{0,1\}^b$ indexed by the set $\{0,1\}^k$, selected uniformly at random from the set of all such families of permutations. See e.g. http://eprint.iacr.org/2005/210.pdf. The IC model is primarily useful for proofs where you need to assume that the ...

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

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

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

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

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

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

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

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.

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