Hot answers tagged

33

You could be thinking about the Merkle-Hellman knapsack cryptosystem. It was invented in 1978 and everything seemed well and good until it was completely broken six years later in 1984 by Shamir - it was a complete and total break, i.e. the cryptosystem became unusable overnight. That said I don't know if the knapsack cryptosystem was ever "popular" in the ...


33

The ISO/IEC 9899:1990 edition of the C standard contains: EXAMPLE     The following functions define a portable implementation of rand and srand. static unsigned long int next = 1; int rand(void) // RAND_MAX assumed to be 32767 { next = next * 1103515245 + 12345; return (unsigned int)(next/65536) % 32768; } void srand(unsigned int ...


26

Modern encryption can be broken in practice even when the algorithms are theoretically secure. There are a variety of ways this can happen: Side channel analysis could have played a part. The accepted answer to the linked question is excellent and provides some very good examples. Exploitation of implementation bugs could have played a part. Malware ...


24

These aren't "attacks" in and of themselves, they are simply a way to classify attacks depending on how many assumptions they make. For instance, if an attack requires plaintext-ciphertext pairs to recover the key, but they don't have to be any particular pairs, that attack is categorized as a known-plaintext attack. However if another attack required the ...


21

For example: the 5-qubit quantum computer created at MIT by using the technique of ion traps succeeded in prime-factorizing 15. Does that mean that since it succesfully managed that, that it is a all-purpose quantum computer which could be used for cryptanalysis and/or cryptographic attacks? No, not even close. Attacking e.g. RSA requires a lot more than ...


19

This is a shot in the dark, but could you be thinking of the Needham-Schroeder protocol? It was published in 1978 [1], and an attack was published as much as 18 years later, in 1996 [2]. It is not an encryption method, though, but a protocol. In fact, the original paper does not even specify an encryption method to be used, but uses encryption symbolically. ...


18

DES has not been mentioned in the previous two answers. Although it was known to be quite weak from very early on it was widely used for a couple of decades at least, until newer algorithms (3DES, AES, but also e.g. RC4) displaced it. Nowadays it can be broken in hours with dedicated hardware or with at most a few thousand dollars of cloud computing time. ...


16

Right now, the best published attack against MD5's preimage resistance (first preimage, actually, but it applies to second preimage resistance as well) finds preimages in cost $2^{123.4}$ average cost, which is slightly better than the generic attack (average cost of $2^{128}$), but still way beyond the technologically feasible. The attack rebuilds the ...


16

Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode. Can I recover that key? No. This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack. This answer on the Mathematics Stack Exchange goes into ...


13

The question asks how a collision in a hash such as SHA-1 could become a practical concern, with focus on the case of a public-key certificate à la X.509. I'll first give an example involving executable code signing. I'll assume an attacker in a position to write bootstrap code (like, the supplier of a development toolchain, or someone who compromised that ...


13

It is all pairings... this is a rather complex matter. I recommend reading Ben Lynn's PhD dissertation; it is about as nice an introductory text on pairings as you can get. The definition is rather mind-twisting: You first define divisors, which are rather formal objects. It is the free group of the curve points: for each curve point $P$, you define a ...


13

Yes, but the answer is more or less embedded in the question here; you can only say that you encrypt too much data in case the secret key and / or plaintext becomes vulnerable. Most modes of operation define how much data can be encrypted. This could mean real limits to the amount of data (approx. $2^{36}$ bytes or 64 GiB for AES-GCM) or it may be ...


11

"Constant-time" is about not leaking information through timing-based side-channels. If you assume that there is no side-channel, then, in particular, there is no side-channel attack. It is nevertheless a rather bold assumption. There is a large variety of possible side-channels, and lab demonstrations of attacks have been done exploiting, among others, ...


10

This is not correct, the private key $d_A$ must always be an integer. Your mistake is that you are doing modular division e.g. $\frac{a}{b} \text{ mod } n$ incorrectly. You cannot simply divide the integers and then reduce by the modulus. The correct way to do this is to compute the modular inverse of $b$ i.e. $b^{-1} \text{ mod } n$ and then compute $a*b^{-...


10

A TRNG is never used instead of a CSPRNG. They serve different purposes. A TRNG is used to seed a CSPRNG. A CSPRNG alone isn't enough to generate random data since it's reproducible. A hardware entropy source alone isn't enough to generate random data because all entropy sources have biases. For any purpose that's related to security or cryptography, a ...


10

In the ROCA paper the authors define an integer $M$ (which they call a primorial) as follows: $$M = \prod_{i=1}^{n} P_i = 2 * 3 * ... * P_n$$ Said another way, $M$ is the product of the first $n$ primes. What the authors observed is that the factors of a vulnerable RSA modulus $N$ have the following form: $$p = k*M + (65537^a \text{ mod } M)$$ The $65537 ...


10

What is the simplest attack is the Brute Force Attack. However, it is infeasible to brute-force even AES-128 bit, AES also supports 192, and 256-bit keys sizes. To break the AES-128 with brute force, you need to execute $2^{128}$ AES operations, today's top computers can reach $2^{63}$ around one hour. In brute-force, the number of elements in your list is ...


8

Orin Kerr & Bruce Schneier have a recent paper out titled Encryption Workarounds, where they group the techniques to indirectly attack theoretically-secure encryption. I think their break-down into abstract categories is helpful, as it's freer of the technical "how", and you can miss the forest for the trees. Think of all the possible ways to get what ...


8

There are $2^{256}$ different AES keys, the chance that you hit the one right one on first try is thus $2^{-256}=\frac1{2^{256}}$. To put this into perspective, here's a list of events that is roughly a billion times more likely to all happen (copied from Thomas Pornin's answer on Information Security SE): The computer spontaneously catches fire ...


8

TL;DR: Yes, on narrow or some ad-hoc deterministic RSA padding, which must not be used. The Desmedt and Odlyzko attack on RSA signatures [DO1985] assumes a deterministic RSA signature scheme with appendix that, for RSA key $(N,e,d)$, signs messages $M$ with signature $S=(H(M))^d\bmod N$ for some public function $H$ with $H(M)<2^k$ and $k\ll\log_2(N)$, ...


8

I once played this online game, it was an old-school MUD. You log in, chat, kill some goblins. It had a casino. You go into the casino and you bet X gold, and there was a 40% chance you win double your bet. Obviously in the long run, the casino will always win, right? But here's the thing. I knew the game was written in C++, and I knew the rand() ...


8

Blinding protects against some side channels attacks in RSA: those that target variations in timing or other side channel information as a known function of $C$ (or $C^d\bmod n$ should that end up to be available). As noted in the question, blinding is pointless against the most basic (Simple) Power Analysis attack, which determines the bits of the private ...


7

It is vulnerable to a sort of meet-in-the-middle attack since you don't really have to brute force $k_1$. Given a plaintext-ciphertext pair, $P$ and $C$, you can calculate $C' = E(k_2', P \oplus k_3')$ for candidate values $k_2'$ and $k_3'$. Then, you can determine $k_1' = C' \oplus C$. So, you only need to brute force the two keys $k_2$ and $k_3$, making ...


7

With respect to collisions, hashing twice can not increase security, because if $x$ and $x'\ne x$ collide for $H$, that is $H(x)=H(x')$, then $H(H(x))=H(H(x'))$. Otherwise said, any collision for $H$ is a collision for the double hash $H\circ H$. It is therefore trivial to exhibit collisions for $\operatorname{MD5}\circ\operatorname{MD5}$. Hence the answer ...


7

I'm happy to have a crack at this one, providing I've understood your question correctly. Firstly I wouldn't say the cipher possibly exhibits low level bias at any point. It experiences plenty of bias and I'll attempt to explain how we can use it to launch practical attacks. As I'd imagine you know, the strongest bias is found right at the start of the KSA, ...


7

A character is usually encoded as an ASCII. This means that it uses up one byte. That's a number from $0 - 255$. It can be represented as a hexadecimal $\text{0x00} - \text{0xFF}$. All your operations must be done character by character. From now on by "message", "key" and "cipher" i mean a single $0-255$ number. $$ message1 \oplus key = cipher1 \\ message2 \...


7

As far as I know your attack is the best attack known, unless something better has very recently been published. Please note that for DES as the basic cipher the chosen $A$ may not work, but you can choose another $A$ and try again Also, for a generic cipher with $k$ bit key, the complexity is $$2^{k+1}=2\times 2^k=O(2^k),$$ as $k$ increases.


7

You should read David Wagner's original paper. You can see all of his work here. He authored the 'Slide Attack', 'Advanced Slide Attacks' and a few more related to the attack. Wikipedia has a good introduction here Feistel ciphers like Simon are very vulnerable to Slide Attacks and similar. Removing the round constants from the key schedule will likley ...


7

As is, the attack seems rather pointless. But one malicious potential is that because $\bar y$ allows to successfully verify a genuine message $(m,s)$, the verifier might grow trust in it and use $\bar y$ instead of $y$ in order to verify other messages. If we assume this, practical issues could arise: That the attacker can somewhat find $(\bar m,\bar s)$ (...


7

Let $n=pq$ be an RSA modulus. Let also $e$ be the public exponent and $d = e^{-1} \bmod (p-1)(q-1)$ the matching private exponent. From $ed \equiv 1 \pmod{(p-1)(q-1)}$, there exists some integer $k$ such that $$ed = 1 + k(p-1)(q-1) = 1 + k(n-p-q+1) \iff kn-ed=k(p+q-1)-1$$ Dividing through by $dn$ yields $$\frac{k}{d}-\frac{e}{n} = \frac{k}{d}\Bigl(\...


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