Hot answers tagged

70

I'll try to take a stab at this. From Apple's iOS Security Guide, we learn that The metadata of all files in the file system is encrypted with a random key, which is created when iOS is first installed or when the device is wiped by a user. The file system key is stored in Effaceable Storage. Since it’s stored on the device, this key is not used to ...


68

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 ...


60

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 ...


54

First, you do not break RSA through brute force. RSA is an asymmetric encryption algorithm, with a public/private key pair. The public key has a strong internal structure, and unravelling it yields access to the private key (basically, the main component of the public key is the modulus, which is a big composite integer, and the private key is equivalent to ...


50

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 ...


33

Brute force on OTP will give you all sorts of messages which are meaningful and not meaningful. For example, you have a 4-character encrypted text: weaw. Now brute-forcing will give you all sorts of meaningful and not meaningful messages like: erwe hell road .... Now, which one was the real message? That would be difficult, rather impossible to guess.


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 ...


20

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 ...


20

What you are missing is the fact that every resulting message is equally possible. There is no way to verify that any of the resulting messages was indeed the message that was sent. If you have $P_1P_2P_3P_4 \oplus K_1K_2K_3K_4 = C_1C_2C_3C_4$ where each $P$, $K$ and $C$ are one bit, then $C_1C_2C_3C_4$ can have any value possible. Now assume your brute ...


18

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 here,...


14

The encryption key isn't derived only from the passcode; it's also derived from a number of cryptographic keys etched directly into the CPU's silicon. These keys are impossible to read out in software—there are only instructions to encrypt and decrypt with them—and have been made purposefully difficult to extract by inspecting the hardware. Without the ...


13

First you have to understand why it is possible to do exhaustive key searches on other systems. Suppose you have a plaintext of length n, ciphertext of the same length n, and a key of length k (all in bits). Then by trying all possible keys we obtain at most 2k candidate plain texts. If the system has some kind of validation or message integrity built into ...


12

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 ...


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

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 ...


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 ...


10

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 ...


9

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 ...


9

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 ...


9

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 ...


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 10,...


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

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

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 ...



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