# Tag Info

## Hot answers tagged provable-security

47

A random oracle is described by the following model: There is a black box. In the box lives a gnome, with a big book and some dice. We can input some data into the box (an arbitrary sequence of bits). Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the ...

36

There are a variety of reasons why AES is more widely used: AES is a standard. AES has been vetted by cryptanalysts more extensively than Camellia. As a result, we can have greater confidence in the security of AES than in Camellia. Therefore, on the merits, there may be good reasons to choose AES over Camellia. AES is a government standard (FIPS). ...

22

As a bonus feature, AES has hardware support in Intel processors which implement the AES instruction set, with AMD support coming soon in their Bulldozer based processors. The AES instructions set consists of six instructions. Four instructions, namely AESENC, AESENCLAST, AESDEC, AESDECLAST, are provided for data encryption and decryption (the ...

17

Actually the article you link to does not says that a balanced Feistel cipher is less secure than an unbalanced one; it says that the security of an unbalanced Feistel cipher is more easily proven, given enough rounds. Luby and Rackoff have shown in 1988 that a balanced Feistel scheme with only 4 rounds is "perfectly" secure as long as the round functions ...

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

10

Using the book as a key is relatively similar to one-time pad, insofar as the book can be considered as a random stream of characters. But that's true only to some extent: a book consists of words, with meaning, which implies that characters which may appear at position 321:42:35 are not uncorrelated with characters which appear at positions 321:42:34 and ...

10

A random oracle is an ideal object; see this previous question for some details. What makes a random oracle convenient for proofs is the part about knowing nothing on the output for a given input if you do not try it. For instance, consider the following encryption scheme: $H$ is a random oracle which outputs $n$-bit values. The key is a $K$, a string of ...

9

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

8

Summary. This scheme is insecure. It can be cryptanalyzed using standard methods from the cryptanalytic literature. It also has poor performance. Your algorithm. To summarize your scheme, in your algorithm a one-bit message $m \in GF(2)$ is encrypted by picking a random quadratic polynomial $p(x_1,\dots,x_{128})$ in $GF(2)[x_1,\dots,x_{128}]$, setting $c ... 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 ... 7 In step 2, the adversary outputs two messages. One of these will be selected at random for encryption. You can think of the adversary sending these messages to a "challenger" that also has oracle access (or is the oracle itself). It doesn't really matter who is running the challenge since the challenger doesn't have any "intelligence." All the challenger ... 7 There are a couple of options for protocol analysis tools. (I don't know any established tool for their design - as said by someone else, designing your own protocols is not really recommended.) If you are looking for formal methods based, symbolic tools, some well-known tools that have been applied to many protocols are ProVerif and Scyther. Given that you ... 7 Does matching all the test vectors mean my implementations are valid mathematically? Basically the comments got it, but test vectors are designed to attempt to hit lots of cases, but with high probability will not catch every single mistake. Should you do it? Definitely. Does it mean everything is perfect? No. Is implementing mathematics correctly ... 7 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 ... 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 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 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 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 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 ... 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's actually quite simple. Given your adversary$A$against ind you construct an adversary$A'$against ind$ by simply forwarding the queries and answers. (This may seem stupid but please bear with me.) Consider now, the difference between the advantage of $A$ and $A'$: \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] ... 6 Your second question was about programmability. This hasn't been directly addressed yet by Thomas' answer or the comments, so I'll focus on that question only. Unfortunately I don't know of a simple primitive that is secure in the random oracle model that requires programmability, but I'll use one that is hopefully clear once I explain the background. It's ... 6 This is not a "block cipher" because a block cipher is a key-dependent permutation of the space of blocks of a given size. Here, you handle data by blocks, but the "encryption" part is done by XORing with a value$H(k+n)$which depends on the key$k$and on the "block number"$n$. So you do not have one permutation (for a given key), but a lot of them. ... 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 You have the math right, but you seem to have mis-interpreted the formulas. So, let me try to walk you through it. The "advantage" of an attack is the difference$|\Pr[Exp(0)=1] - \Pr[Exp(1)=1]|\$. The advantage is a measure of how effective the attack is. If the advantage is large (significantly greater than 0), the attack is successful (and the function ...

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

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