Hot answers tagged

7

A multi-target attack is an attack on many users of a cryptosystem at once. The attacker might be satisfied with breaking one user—for example, if there are a thousand human rights activists in a network under attack by an authoritarian state, breaking into the Signal chats of one activist may be enough to compromise the whole network. Moreover, the state'...


7

TLDR: The scheme is symmetric only, its "provable security" argument is flawed, and it is practically insecure when even a modest amount of plaintext is available to attackers. I'm commenting on the scheme in: Josep Domingo-Ferrer, A Provably Secure Additive and Multiplicative Privacy Homomorphism, published in proceedings of ISC 2002. I ignore the 1996 ...


6

Actually, a well known result is that, for any cryptosystem that relies on the hardness of the DLog problem (including ECDlog), there is no such reduction in strength if you have $k$ keys. That is, the problem of "here are $k$ keys, break any one" is essentially as hard as the problem "here is one key, break it". The proof is straight-forward; first off, ...


6

The basic baby-step-giant-step algorithm can be tweaked to make use of this information. The following algorithm takes $\Theta(\!\sqrt{k-j})$ group operations. Let $h:=c\cdot g^{-j-1}$, which equals $g^{i-j-1}$. Pick some integer $m\geq\sqrt{k-j-1}$. Initialize an empty lookup table $T$. For all $0\leq a<m$, compute $g^{ma}$ and store $T[g^{ma}]:=a$. For ...


5

This scheme suffers from a classic problem of textbook RSA which is mitigated e.g. by RSA-KEM (as outlined by kelalaka) or RSA-OAEP. When you compute $k^3\bmod N$, you'll experience that $$c=k^3\stackrel{k< 2^{256}}{\leq}\left(2^{256}\right)^3=2^{768}\ll 2^{2000}<N$$ Now remember how $x\bmod N$ works: If $x\geq N$, then you recursively compute and ...


4

If this is all you have, then I think you can't. You can easily get 1st and 3rd block. Change the 2nd ciphertext to get the desired result of 3rd block and change IV to get the desired result for first. But changing a cipher text block means you no longer have the results of the block cipher decryption. If you have however limited access to a decryption ...


4

What you describe is a little away from the RSA-KEM (KEM : Key Encapsulation Mechanism). As pointed out by SEjPM, in the comments, an AES-128 key when encrypted with the public modulus has almost 768 bits and this can be recovered by the cube-root attack. Here is the RSA-KEM; RSA-KEM mitigates the attack that you have. RSA-KEM for a single recipient with ...


4

Would it be easier to find collisions, preimages, etc? First note that if you can find preimages for a compressing function (like a hash) you can also find collisions. This means if we can't find collisions, then we also can't find preimages and thelike. Now, the scenario you are describing is called a "freestart collision attack". Freestart collisions are ...


3

In modern cryptography it is generally assumed that algorithms are public and only the key is kept private. Thus, the adversary can compute $\operatorname{Mac}(k', m)$ for any key $k'$ and message $m$. The oracle $\operatorname{Mac}_k(\cdot)$ in the experiment allows $A$ to additionally receive valid macs under the challenge-key $k$ for which it is supposed ...


3

First, some background on Quadratic Residues: A Quadratic Residue (QR) is a number $x$ such that there exists some number $y$ with $x \equiv y^2 \pmod p$ (where $p$ is the modulus we're talking about - I'll make it implicit here on out), and it doesn't matter what $y$ is, only that whether such a $y$ exists. There exists an efficient test where we can ...


3

meet-in-the-middle attacks rely on storing the results in a map Only the naive version of MitM does. The impractical memory requirement (size and accesses) of naive MitM can be greatly lowered with a relatively modest increase in other computation costs, and the calculation distributed to independent devices. The reference paper is Paul C. van Oorschot and ...


3

How is asymmetric cryptography safe under these conditions? Well, you sort of outlined (but see kelalaka's corrections) how you would use asymmetric crypto to do authentication; that is, to make sure that the message was actually sent from $A$. You ask "how does that provide privacy?". The answer, of course, is "if that's all you do, it doesn't". If we ...


2

If you use the same padding on the same messages, sent to multiple different public keys, then you have satisfied the criteria of the Håstad attack. Randomizing the padding as in OAEP means that you don't use the same padding for each message. Even better, in a modern system like RSA-KEM, there's no ‘padding’ per se, or even any ‘message’ involved directly ...


2

It does work with Silver-Pohlig-Hellman algorithm As theREALyumdub pointed out in comments that Silver-Pohlig-Hellman might be an option I did some test and it did work. Thanks for that hint. In case $t=1$ we get the results $a,b,c$ right out of the algorithm. For other $t$ the results $a,b,c$ aren't correct. Some extra work need to be done there. It does ...


2

I think what Bruce has done is to use Sign and Decrypt interchangeably, he has done same for Validate and Encrypt. I think it is because - to sign a message - Alice uses her private key. Now in terms of encryption / decryption, a private key is used to decrypt the message and a public key is used to encrypt the message. So instead of saying: Vm(Db(Eb(Sa(M))...


2

If the counter mode started at $\text{Nonce}\mathbin\|0^{32}$ instead of at $\text{Nonce}\mathbin\|0^{31}\mathbin\|1$ then one could submit an encryption query for $(0^{96},0^{128})$, i.e. the 128-bit all-zero plaintext along with the all-zero nonce. The first block of the ciphertext would then be computed as $E_K(0^{128})\oplus 0^{128}=E_K(0^{128})$ which ...


2

(too long for a comment) You can calculate $x_n$ directly by your formulas, if you know, how to calculate in a quadratic extension field of a prime field $\mathbb{F}_p$. Here is the code in python: # global parameters p = 65537 t = (p+1)/2 r = 313 s = 997 # from https://stackoverflow.com/a/9758173/99978 # modular inverse based on extended Euclidean ...


2

If now the prime value $P$ gets increased for constant $k$ (order of $g$ still $k$) does this decrease the security? No, for random choice of $g$ among $g$ with large constant order $k$. Why this? If $P \rightarrow \infty$ it would be the normal logarithm .. When $P$ grows, $g$ also grows. So we never reach the threshold where $g^a<P$. Thus we can ...


2

In cut-and-paste one part of ciphertext is replaced by another ciphertext with known (or at least, known legible) plaintext, so the resulting message has a different meaning to the receiver of the encrypted message. It should be avoided by using authenticated encryption. There is probably not a direct copy-and-paste attack on CBC in a similar way as there ...


2

Here is a nice explanation from the efail presentation, credits to Jens and Chris! This is for CBC but it looks pretty much the same for CFB. So here is CBC decryption: Now if you flip a bit in $C_1$ you can flip that same bit in $P_1$: but it will also cause $P_0$ to look like random trash after decryption. But if you know what $P_1$ was in the ...


2

Attacking CBC is much harder than ECB. In many cases there is no viable attack. Properly implemented CBC with a secure underlying block cipher is secure. There have been successful attacks against padding in CBC, though non were anywhere as simple as attacking ECB. Look at: https://en.wikipedia.org/wiki/Padding_oracle_attack https://en.wikipedia.org/wiki/...


2

If someone has a large set of values: $$B + \epsilon_0, B+\epsilon_1, B+\epsilon_2, …, B+\epsilon_n$$ One can average all these values together. If the values of $\epsilon_0, \epsilon_1, \epsilon_2, …, \epsilon_n$ are independently distributed with a mean of 0, the average of these values will be closer to $B$ (essentially reducing the size of the error ...


1

Firstly, you misunderstood what is a signature and encryption with the public key. A signature requires a hash then sign paradigm with the senders private key so that any receiver can verify the signature. The RSA paper gave the first idea to digital signatures that were insecure and the Rabin Signature released in 1979 is the fist secure signature that ...


1

The MAC under attack is built from a hash $h$ (assumed to process a hashed message by splitting it in blocks processed only once, as most hashes do), with a key split into $K_1$ and $K_2$ of equal size. It computes the MAC of a message $x$ as $$\operatorname{MAC}_{K_1\mathbin\|K_2}(x)=h(K_1\mathbin\|x\mathbin\|K_2)$$ The attack in the paper recovers $K_1$ ...


1

Read up on weak keys on Wikipedia. The weak keys are the ones that result in the left and right key halves at the output of the Permuted Choice function being either all 1's or all 0's. So you can test all possibilities for weak keys to break the OFB mode. What is more, if weak keys are used DES becomes idempotent, thus double encryption gives the ...


1

Actually, this specific attack against RSA is known as a 'cycling attack'; it works because RSA defines a permutation, and so by doing repeated encryptions a sufficient number of times, you'll always get back to where to started with eventually. However, people have analyzed this attack, and shown that (with extremely high probability) the amount of work ...


1

First before we can get into the details of the attack, we need an intuition why it works. There's a nice picture hosted on the TLSeminar page illustrating this point: which basically says that we want to modify the last byte $\color{red}\times$ of the second-to-last block so that the CBC decryption of the last block which has "$\color{blue}?$" as its ...


1

Does the attacker help this knowledge about $k$ (in case (1.) or (2.)? No; suppose you had an Oracle that could recover $a$ given $N, P, k, b, M$, then you could recover $a$ just given $N, P, k$ (that is, solve the Discrete Log problem). Because we believe that the Discrete Log problem (given appropriate choices for $N, P$) is hard, we can conclude that ...


1

If the attacker knows everything (including $m$) except for $r$, he can rewrite it to: $$g_1^r = (c + g_1 g_2 (g_1 - 1)^{-1}) ( m + g_1 g_2( g_1 - 1)^{-1})^{-1} \pmod{p}$$ He knows everything on the RHS, and so it's a simple discrete log problem. BTW: for the $\mathbb{Z}_p^*$ group, there are much faster attacks than Baby-step-Giant-step


1

For a $1$-bit message $m$ a randomly generated, fixed prime $k$ (the key) per-ciphertext randomly generated $r$ and/or $e$ C1, C2 $$C_1 : (k * r) + m$$ $$C_2 : (2 * e) + m$$ A1, A2 $$\begin{align}A_1(c_0, c_1) : c' = c_0 - m_0\\c'' = c_1 - m_1\\k = \operatorname{gcd}(c', c'') = \operatorname{gcd}(k*r_0, k*r_1)\end{align}$$ $$\begin{align}A_2(c_0) : m = ...


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