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

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

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

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

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

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

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

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

6

For many signature schemes, having two signatures using the same randomness for two different hash values allows recovery of the private key. This is used in many security proofs by showing that an adversary that forges a valid signature can be coerced through replaying into producing two signatures of this form. As a consequence, an forger can be twisted ...

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

A PRP is a keyed primitive, so proving properties of a keyed hash on top of it is often possible. Reducing the security of an unkeyed hash to a keyed primitive on the other hand is rarely possible. For example keyed Skein (a hash) is provably a PRF if Threefish (a block-cipher) is a PRP: PRF, MAC, and KDF. We prove that if Threefish is a tweakable PRP ...

6

When cryptographers create algorithms, they usually provide some argument that the algorithm is secure. They need to start the argument with some set of assumptions. For example, the in public-key cryptography, they may begin with the assumption that factoring large numbers is hard. Many algorithms use use a block cipher as a building block. The arguments ...

6

I hope I got your point and try to answer your question. Actually, if I understand you right, then what you call attack can also be seen as an adversary acting in a specific attack model. Therefore I briefly review the security models for digital signature schemes. Goal of an adversary: We start by discussing the goals of an adversary beginning with the ...

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

None of the above answers seem to take into account that you apparently want to establish security with respect to the eCK model; the above answers are mostly about tools that verify some (related but different) properties. Afaik, there is current no automatic tool that can give you analysis with respect to the exact eCK model. In the symbolic setting, ...

5

I think it is still possible to use UC in this case. Recall the setup for the UC framework. We have an ideal world and a real world. There are parties $P_1,\dots,P_n$ in each world and an environment $\mathcal{Z}$ in each. In the real world we have the adversary $\mathcal{A}$ while in the ideal world, we have an ideal functionality $\mathcal{F}$ and a ...

5

Just wrapping my comment into an answer as it seems to be what you're looking for… CryptoVerif can be used for verification of security against polynomial time adversaries in the computational model. It's available via http://prosecco.gforge.inria.fr/personal/bblanche/cryptoverif/cryptoverifbin.html Related to your "it doesn't work on my computer", here's ...

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

I can highly recommend AVISPA, a tool for automated verification of cryptographic protocols. It is available as a web service, so you can upload a description of your protocol to their web server and it will give you a security analysis of it. They have detailed documentation of how to use their system and of their specification language for protocols, so ...

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

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

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

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