Hot answers tagged provable-security
30
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 ...
29
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). ...
14
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 ...
13
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 ...
9
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 ...
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
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 ...
5
An obstacle to proving that a book cipher is secure is that the letters in (most) books are not chosen independently at random. Thus, in principle, if two indices are chosen too close to each other, an adversary could deduce some statistical information about how the corresponding plaintext letters may be correlated.
As a toy example, suppose that an ...
5
Yes, your scheme is fine.
Nitpick: I think you mean that your goal is to generate a random number in the range $0\ldots n-1$ (not $0\ldots n$). Also, to avoid bias, you need to generate $m$ as a random number in the range $0 \ldots (\lfloor 2^{256}/n \rfloor \cdot n)-1$ (not $0\ldots \lfloor 2^{256}/n \rfloor \cdot n$).
This problem is known as secure ...
4
My impression (which is limited) is that the most researchers are pretty content with the state of security proofs, and it did not have much impact on changing the research agenda of the community. In fact, a related paper was strongly opposed by leading cryptographers. That is not to say the papers were ignored. They generated lots of discussion and maybe ...
4
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] ...
4
This looks totally weak. If you know 128 bits of known plaintext, you can infer the corresponding 128 bits of keystream. The keystream being the multiplication of the random matrix by the key (in the vector space $\mathbb{F}_2^{128}$), the key is then revealed through a basic matrix inversion.
4
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 ...
4
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 ...
4
To prove that a scheme is not secure under such a definition you usually would propose an algorithm such that the experiment described in your question outputs $1$ with probability non-negligibly larger than $1/2$.
As this looks very much like a homework problem I will not give you a solution. However constructing the algorithm is actually very simple in ...
3
The inequality is obtained by a distance argument.
Consider two points $X,Y$ on the real line. Taking another point $Z$, you have $|X-Z| + |Y-Z| \geq |X-Z+Z-Y| = |X-Y|$.
Applying this "triangle" inequality to your equality 1, we have for any $z \in \mathbb{R}$,
$\begin{array}{l}
\bigl\lvert\Pr[A(x\oplus g(U_n))=1] - z\bigr\rvert
+ \bigl\lvert ...
3
As said in the comments, your construction is not what usually is called a block cipher.
A block cipher is a pair of (deterministic) functions with just two inputs: key and plaintext or ciphertext.
Your function has an additional input, the block number.
One could name this a tweakable block cipher (i.e. $n$ is the "tweak"):
$$ Enc_k^n(P) = P \oplus H(k, ...
3
I'm not sure that I understand the question completely, as there are plenty of proofs of real-ideal simulation-based definitions that are proved in a "sequence of games" style. So, I think that the question being asked might be either of the following:
Rather than comparing proofs, perhaps the question is about definitions. Specifically: what are the main ...
3
A random oracle is an idealization of a hash function $H$: if hash functions were perfect they would be random oracles. This is why it is always easier to consider a hash function a random oracle when one proves something about a larger scheme. Those are "proofs in the random oracle model". [1]
That being said it is still possible to prove things using ...
3
As far as I know, there's no fundamental obstacle that would prevent you from implementing any crypto algorithm you want in JavaScript, whether on the server or the client side.
Compared to an optimized implementation written in C or assembly, JavaScript implementations of low level crypto primitives like block ciphers or PRNGs are likely to be slow and hard ...
3
Levin showed that combining PRG with a universal hash function, one can reduce the number of calls. Roughly speaking, we shorten a message with a universal hash function before applying the GGM construction.
That is, $y = F_{k,k'}(x) = \mathrm{GGM}_G(k,h(k',x))$, where $h$ is a universal hash function.
At TCC 2012, Jain, Pietrzak, and Tentes gave another ...
3
I'm just reading the book Advances in Elliptic Curve Cryptography, and Chapter II (by Dan Brown) is about provable security of ECDSA.
It lists some necessary conditions for the ECDSA components (group, conversion function, RNG, hash function), each with an associated forgery. For example, the group has to be resistant against discrete logarithms, as well as ...
3
Salsa20 is a stream cipher based on a pseudorandom function, not a pseudorandom permutation.
For a fixed key $k$ and nonce $n$, the mapping $PRF^{S20}_{k,n}: \{0,1\}^{64} \to \{0,1\}^{512}$, which maps a "Stream position" to "keystream block", is supposed to be a pseudorandom function. It is not supposed to be injective (i.e. a permutation, even less since ...
2
hummm... some thoughts about it:
I think that it could be secure depending on what you want to hide. The bigger and the more "real world words" you want to protect, the easier it gets to crack. Why? Because in books, in general, you'll only have letters, few numbers, and that's only. Ok, so I know your transmitting one or more words. By the size of the ...
2
Expand the equation system corresponding to the matrix multiplication:
$c_j = \sum_{i=0}^{n-1}k_{i,j}p_i$
In other words, each element of the cipher text corresponds to the sum of the cipher text elements of an OTP encryption of the input plain text. If the matrix is never reused, it should be fairly easy to go from here. You are basically using $n$ one ...
2
The randomness is not enough for IND-CCA-2. If we get a message (so $L$ bits of data plus the $y$ to reconstruct the random seed), we can modify it, say flip the first bit, and ask the decryption oracle for a decryption of the modified message (which will have the same $y$!), which we will get. Then the original message can easily be obtained: we get the ...
2
In Dolev-Yao and other formal models, the assumptions about adversary behavior are encoded via the grammar and entailment relation, and there's no mention of a specific computational definition of encryption security.
But your question is still meaningful, and can be interpreted as follows:
If my encryption scheme is CPA secure, and my protocol is ...
2
Proponents of simulation-based proofs will tell you that their notions are easier to understand and it's clearer what exactly the notion gives you. Compare Jens Groth in http://eprint.iacr.org/2002/002.pdf : his introduction (page 2) is a clearer answer to the "pros" in your question than I can come up with here.
However, if you're actually trying to ...
2
The standard approach is to break this problem into two pieces:
What information is unavoidably leaked, merely by computing the desired function? In your case, the goal is to compute $\sum_i x_i$. This sum unavoidably leaks a little bit of information about the $x_i$'s. For instance, as you correctly state, if we somehow know that all $x_i$'s are ...
1
Guillo-Quisquater scheme uses the Fiat-Shamir trick to convert a proof of knowledge into a signature. There is a paper out there about the security of such schemes in the random oracle model here which seems to give what you want.
Only top voted, non community-wiki answers of a minimum length are eligible
