# Tag Info

12

By George, you're on to something. To answer the question you asked, I don't know of anyone actually attempting to recover a password this way, or it even being discussed. However, it does appear to be feasible, given enough encrypted streams. How many are enough? Well, I've started running a few simulations; preliminary results indicate that with ...

10

For symmetric algorithms (like AES or DES or RC4 -- but not for RSA or ECDSA), a key is a sequence of bits, such that any sequence of bits of the same size is a potential key. So longer keys means more possible keys. Exhaustive search is about trying all possible keys until a match is found. It is an absolute limit to the strength of an algorithm: ...

9

A distinguisher is an arbitrary algorithm. In fact, we do NOT want to formalize anything about the distinguisher (except that its output is a single bit, although we don't even really need to do this). In definitions, we require that no distinguisher should succeed with non-negligible probability. So, this should hold for any algorithm. Of course, we do ...

9

$s_i = s_{i-1}\cdot(N + 1) + 1 = s_{i-1} \cdot N + s_{i-1} + 1$ but $s_{i-1} \cdot N = 0 \pmod N$, so $s_i = s_{i-1} + 1 \pmod N$ which means you can discover the next number to be generated just looking to the current one...

8

It... depends. AES is a block cipher. It works over 128-bit blocks. For a given key, AES is a permutation of the $2^{128}$ possible values that 128-bit blocks may assume. As a purportedly secure block cipher, AES is supposed to be indistinguishable from a random permutation, i.e. a permutation selected randomly and uniformly among the $2^{128}!$ possible ...

7

If the DDH is hard in a group $G$ with generator $g$, then it is hard to decide given $(g,g^a,g^b,g^c)$ whether $ab\equiv c\pmod{ord(G)}$. If you take as $G$ the group $Z_p^*$ of order $p-1$ with $p$ being prime, then you will have $(p-1)/2$ elements being quadratic residues ($QR$) and the other half being non-quadratic residues ($QNR$). Now, we know that ...

7

Asymmetric encryption requires some mathematical structure (to enable the magic of asymmetry), and some of that structure is readily apparent to anybody. For instance, with RSA, the encrypted messages are numbers modulo $n$ (the modulus, from the public key), and thus in the range $0$ to $n-1$. This implies that values for the first byte will be quite biased ...

6

To answer your first question on key length: DES uses a 56 bit key. A brute-force attack will need a maximum complexity of $2^{56}$ to find the correct key. Now by today's standards this is not much. A complexity of $2^{90}$ or more is considered secure enough. By that standard AES with any key size – 128, 192 or 256 – is strong enough to use. As far as ...

6

I would say a distinguishing attack should count as a break. Especially so if it is practical. The reason for this is that if you can distinguish the key-stream from random, you invariably leak details about the plain-text. For example, suppose somebody turned up a few terabyte disks encrypted with VMPC under the same key. It says in the paper that after ...

6

Quoting from "On beating the hybrid argument" (by Bill Fefferman, Ronen Shaltiel, Christopher Umans and Emanuele Viola; 2012): The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor k equal to the bit-length of the ...

6

Actually, it is possible to define RSA in such a way that the RSA ciphertexts are indistinguishable from random bit strings of the same length. The method is quite simple: When you select the RSA key, you deliberately pick a modulus that is just under a power of 256; for example, if you are generating a 2048 bit key, you select a modulus between $2^{2048} ... 5 Patarin's proof isn't about distinguishing ciphertext from "random text", it's about distinguishing a Feistel cipher from a random permutation. That proof is also in the information theoretic world, which means that the Adversary is computationally unbounded, and as such can deduce everything about the cipher (the 'key', all remaining ciphertexts, etc). In ... 5 The quoted sentences means: if there is a collision among the MACs of the$2^{(n+1)/2}$messages submitted, the attacker playing the distinguishing game announces that the oracle is a random function; else announces that the oracle is CBC-MAC. This works because the messages submitted differ only in their first block, thus will never collide under CBC-MAC, ... 4 Yes and no. The only cipher that provably has no such distinguisher is the one-time pad. For practical symmetric ciphers (e.g., AES), we have no proof that no such distinguisher exists or does not exist. The best we can do is say "A bunch of really smart folks have been trying to find such a distinguisher in order to gain fame (and possibly fortune) for ... 4 There are a number of distinguishers that it it would be easy to prove are not present in a hash function. For example, I can easily prove that Skein does not have the distinguisher "the 2nd bit in the output is equal to the first bit of the output with probability 1". The proof would be a simple example of a message whose digest does not have this property ... 4 In theory, there is a simple distinguisher for encrypted data: Try all the possible keys, decrypt the stream and look if the result is something which makes sense. Of course, this will not work if you encrypted garbage (and one could say that encrypted random data is really indistinguishable from random data itself, ignoring block sizes). And practically, ... 4 Why the CFS signature is affected Let us review the structure of the CFS signature, which is strongly related to the Niederreiter PKE scheme. In the Niederreiter PKE scheme, a public key is$H \in \mathbb{F}^{n \times k}$, which is a scrambled parity-check matrix of the Goppa codes. A plaintext is a decodable error; for example, we set$S = \{\vec{e} \in \...

4

See Vitor's answer for the answer your professor was looking for. However, for any PRNG of the form $s_{i+1} = F(s_{i})$, where the attacker sees the $s_i$ values, and knows $F$, then he can distinguish it. Given a sequence of values $r_1, r_2, ...$, he can determine whether it was generated by that PRNG by checking if $r_2 = F(r_1)$; this is always true ...

3

Such reductions I know are the reductions in hardcore predicates/functions from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, the reductions in (provably-secure) PRGs/PRFs from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, and the reductions in LPN/LWE. Re: Can you be more specific? I....

3

For any $n \in \mathbf{N}$, let $X_n$ be a random variable which always equals $n$, and $Y_n$ be a random variable which equals $n$ or $n+1$ each with probability $1/2$. Then the probability ensembles $X = \{X_n\}_{n\in \mathbf{N}}$ and $Y = \{Y_n\}_{n\in \mathbf{N}}$ are not computationally indisinguishable. A possible distinguisher is an algorithm $D$ ...

3

First off, your definition is not IND-CPA: In the IND-CPA setting, the adversary has access to an encryption oracle. As you have already determined, no deterministic encryption scheme can be IND-CPA secure. I don't think IND-CPA is widely used for symmetric encryption though (although I might be wrong), semantic security might be a better option. For public ...

3

Your idea for constructing a distinguisher from a predictor is fine, assuming you know that the predictor predicts the last bit. The more general statement is: if you can predict any bit of the output, say the $i$th bit, given the first $i-1$ bits, then you can also build a distinguisher. A similar idea to what you showed also works to prove this statement....

3

I don't know of any practical attacks along these lines that pose a realistic threat in practice, on any current protocol. Let me explain. There are two standard kinds of distinguishing attacks on RC4: The first two bytes. Mantin and Shamir showed that the second byte of output from RC4 is biased. If the password was always encrypted at the very start ...

3

It may be useful to define what is meant by noise. Noise is data that is selected randomly from some distribution. @Thomas deals with comparing to random bitstrings (where each bit is equally likely 0 or 1) and notes that because not all bitstrings of an appropriate length are possible values in most asymmetric encryption functions, real ciphertexts will be ...

3

There are various adversary models, in fact it is typical to test our schemes against multiple adversaries to prove various nuances of security. The most intuitive of all is an adversary that can produce the plaintext (or a part of it) given only the ciphertext. An extension to this model, stronger than the other, is the one you mentioned, letting the ...

3

Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bitlength is polynomial in the security parameter), and thus allowing the distinguisher to decrypt? This is up to your security ...

3

If $(X \approx X')$ and $(Y \approx Y')$, then it holds that $(X \times Y) \approx (X' \times Y')$. Indeed, let us consider an adversary which is able to distinguish $(X \times Y)$ from $(X' \times Y')$ with probability $1/2+\varepsilon$; the adversary returns $0$ if he estimates that the sample comes from $(X' \times Y')$, and $1$ else. Indeed, let us ...

3

He's doing a pretty poor job of expressing a very simple idea here, which is that if there exists a distinguisher $D$ for which $Pr\lbrack D(H^{i-1})=1\rbrack$ > $Pr\lbrack D(H^{i})=1\rbrack$ (which means the advantage is negative before taking the absolute value), there also exists a distinguisher $\overline{D}$ for which $Pr\lbrack D(H^{i})=1\rbrack$ > $Pr\... 2 A longer key length means a greater search space for someone trying to brute force the key. There are$2^{128}\$ times more 256-bit keys than 128-bit keys. So, all other things being equal, a brute force search for a 256-bit key could be impractical by a factor of billions in a case where a brute force search for a 128-bit key might be practical. However, ...

2

These are called weakly pseudorandom function families.

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