# Tag Info

## Hot answers tagged brute-force-attack

67

256-bit key cracking through exhaustive search is totally out of reach of Mankind. And it takes quite a lot of wishful thinking to even envision a 128-bit key cracking: trying one key must be reduced to the flip of a single logic gate (compared to the hundreds of thousands which are actually required); that gate must be more energy-efficient than the most ...

52

The average cost for electricity in the US is $\$0.12$per kWh. For a single server I'll use 3741 kWh annually as an estimate. That would be about$\$450$ per year for one machine. Let's say you can do $10^{14}$ decryptions per second. That is $3.15*10^{21}$ decrypts per year for one machine. You need to do (on average) $2^{255}$ decryptions in a year, so ...

47

There is some Thermodynamic Limitations. A good explanation about Thermodynamic Limitations is by Bruce Schneier in Applied Cryptography: One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of ...

25

Assume that 1 evaluation of {DES, AES} takes 10 operations, and we can perform $10^{15}$ operations per second. Trivially, that means we can evaluate $10^{14}$, or about $2^{46.5}$ {DES, AES} encryptions per second. This is a simplistic view: we are ignoring here the cost of testing whether we found the correct key, and the key schedule cost. So on our ...

17

According to this source, bitcoin mining nowadays (Nov. 2015) tops $500\cdot10^{15}$ hashes per second, where one hash is two nested SHA-256; that is over $2^{84.7}$ SHA-256 per year. I'm guessing the NSA could do much better with a fraction of its budget. Here is this data redrawn in SHA-256 per year with a $\log_2$ vertical scale, to facilitate comparison ...

16

Yes, a computationally unbounded attacker can break any public key system. One easy way to see this is to consider the KeyGen algorithm, which takes takes as input a value R (which in normal use is the output of some random number generator), and outputs a public key PK and a private key SK. Now, what a computationally unbounded adversary can do is ...

14

n is the exponent. So when n is doubled from 64 to 128 it doesn't mean that you have to try twice as many values. It means that you have to try $2^{64}$ times the amount you were already trying (as $2^{128} = 2^{2\times64} = 2 ^{64+64} = 2^{64}\times2^{64}$). It is required to only search half of the key space on average (if average is the correct term ...

12

XXTEA (also known as Corrected Block TEA) is a block cipher with $128$-bit key and block width parameterizable to $n\cdot32$ bits for $n\ge2$. It is an Unbalanced Feistel Cipher making $q=6+\lfloor52/n\rfloor$ passes over the block, with $q\cdot n$ rounds each modifying $32$ bits of the block. In Cryptanalysis of XXTEA, it is presented a chosen-plaintext ...

11

From the perspective of someone who is a non-cryptographer but runs penetration tests against, well, anything really, there is a very simplistic answer that is generally correct in the real world: Assuming the implementation of the encryption algorithm is not flawed (I know, not always a good assumption, but the common open source tools get a lot of peer ...

11

If (you suspect that) the (plaintext of the) encrypted data is ASCII text, you can check if the high bit of each decrypted byte is zero. As long as you have more than 24 bytes of data to check, the odds of that happening by chance are pretty low (given that you have a 24-bit keyspace). UTF-8 text is also pretty easy to detect, since all bytes that do have ...

10

It's not possible. The number of primes smaller than $x$ is approximately $\frac{x}{\ln x}$. Therefore the number of $512$ bit primes (approximately the length you need for $1024$ bit modulus) is approximately: $$\frac{2^{513}}{\ln 2^{513}}-\frac{2^{512}}{\ln 2^{512}} \approx 2.76×10^{151}$$ The number of RSA moduli (i.e. pair of two distinct primes) is ...

10

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 at least as much key material as you have plaintext to encrypt. Such a key needs to be shared between ...

9

Non-technical brute force method: The most cost-effective "brute-force" method I can think of is to hire a gang of mobsters to force the guy who knows the password into giving it up. For a guy with no security, a good mobster would probably cost about \$5,000, and you'd need at least 3 of them. If you are going for a high-profile guy, a good mobster would ... 9 Re-using their design might be no good idea - there are cheaper designs for sure. This new DES cracker would just need to try every possible key - like the one of the EFF already did. DES was a big standard for encryption, so some people did build such machines, right? Of course did they: COPACOBANA is able to break DES in under 9 days and costs under ... 8 The last major effort I know of for cracking keys was the Distributed.net effort. You can find the project page at http://www.distributed.net/RC5/en. In 2002, they cracked a 64-bit RC5 key using at total of 331,252 computers over 1,757 days. Their maximum throughput was "equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP ... 8 Assuming the n-bit CRC of an unknown bit string b is known, one can constructively rebuild any consecutive n bits of b from the rest of the bit string (and the definition of the CRC). Indeed, in the case described, that speeds up password search considerably. One can compute the last 32 bits of the password (likely, 4 characters) from the beginning of the ... 8 This is called ciphertext-only cryptanalysis*, and it's pretty difficult unless the cipher is quite weak. Therefore, the first priority for a cryptanalyst in such a situation is usually to try to find more information about the algorithm. Fortunately (for the cryptanalyst), as Kerckhoff's principle suggests, there are often ways to find out how the ... 8 Why can't you simply ask the person who made that file to tell you the password? No one knows how to decode an AES-encrypted file, such as password-protected WinRar files, without knowing the password. As far as we know, the only way to decode AES-encrypted files is to somehow obtain the right password, and then use that password to decrypt the file. In ... 8 I suspect that the meet-in-the-middle attack you have in mind is what is presented in this answer (or something similar). If so, then it's not actually correct to say "the only requirement is that the message be a product of 2 numbers of the same magnitude"; the message needs to be a product of two numbers of the same small magnitude. For example, the ... 8 Any protocol with long-term security becomes harder to break after the protocol execution has finished. In the Bounded-Storage Model, protocols become harder of break as [information about the randomizer that's not stored by the adversary] is lost.$\:$(This point is similar to minar's observation.) 8 The Bitcoin mining algorithm can not be simplified by exploiting any weakness in the SHA-2 hashing algorithm with the current state of the art. The problem is manyfold. From the SHA-256 point of view, there is no (partial) preimage search algorithm that applies to the full hash function. Even worse, the attacks that penetrate a fewer number of rounds have ... 8 There are multiple metrics for work or effort needed: Amount of operations it takes (one operations is, for instance, one invocation of hash function or number of modular multiplication operations) Amount of money it takes Amount of memory it takes Amount of time it takes Strength in bits Amount of operations Usually, if amount of operations is large ... 8 A key size of 80 bits is the historical limit of infeasibility; that's what was used in the 1990s as a rule of thumb. That's the reason why Skipjack used an 80-bit key, and SHA-1 offers a 160-bit output. Various people have also estimated that a 1024-bit RSA, DH or DSA key offers an "80-bit equivalent" protection (see this site). One of the most optimistic ... 8 This answer addresses Cases 1 and 2 from the question to provide a baseline, leaving Case 3 (which is the one I'm most interested in), unresolved. Case 1, Zero Increment In this case we'll consider a simple Lehmer-style LCG (a.k.a. an MCG), with a seed$s_1$, multiplier$a$and$b$bits of state and$r$bits returned. The modulus$M = 2^b$, and the ... 7 The classic way to do this is to have all parties commit to individual random values by publishing a secure hash of a suitably random-nonce-padded number. Once the commitments have been distributed, the parties open the commitments by publishing the nonce and the number. The numbers are combined in some previously agreed suitable fashion such as adding them ... 7 The interesting property for the one time pad is that every plausible plaintext (given the length constraint, i.e. of same length as the ciphertext, maybe including some padding) has a corresponding key which produces a certain ciphertext. As mentioned in the comment by CodesInChaos, this key can be retrieved by simply XORing both plaintext and ciphertext ... 7 How long are parameters used for? Usually$g$and$p$are kept static for a very long time indeed. In fact, the values to use are actually written in to standards. See here for an example. Those were values standardised ten years ago. So the answer is basically decades. The impossibility of brute force Let's suppose that I as an attacker decide I'm going ... 7 As long as you use a secure padding mode (i.e. -pkcs or -oaep, not -raw). The default padding mode for openssl rsautl is -pkcs (i.e. PKCS#1 v1.5), so you should be OK. That said, OAEP is recommended over PKCS#1 v1.5 padding, so you might want to use the -oaep switch. 7 I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time" Using a perfectly random key which is as long as the message itself, not a pseudo-random key, cannot be broken no matter how fast the attacker's computer is. This scheme is called one-time-pad and its security is guaranteed by information theory ... 7 As pointed in this comment, using a huge random key for a sound block cipher is an excellent defense to resist ASIC/GPU attacks. Each bit added doubles the effort required. If an adversary was able to build$10^{12}$ASICs each capable of testing$10^{12}\$ keys per second, odds of finding a 128-bit key by brute force running that for a decade are less than ...

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