# Tag Info

76

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

74

"lucky" is not a property of the attacker. There's no "lucky" attacker nor "normal" attacker. They both have the same probability (low, very low) to guess the key. You can decrease the probability at will by increasing the length of the key (i.e. the no. of bits). You cannot really argue "what if the attacker is lucky" because "being lucky" is a posteriori ...

56

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

42

Note: This answer assumes that by "lucky" OP meant "able to remove X% of valid answers", because I believe that was intent. Of course you can't measure luck ;) And if he is very lucky, say 90% chance, that means that 1 bit is actually only 0.1 bit.So in face of a very lucky opponent, a 128 bit password has only 12.8 bit strength. Well, let's validate ...

40

TL;DR: no longer unconditionally. As of 25 September 2018, the Bitcoin miners hashed at an aggregate rate of $\approx60 \cdot10^{18}H/s$ according to this source, where one hash is two nested SHA-256; that is $\approx2^{91.6}$ SHA-256 per year. That's been bitcoin's "peak hash" so far. Here is this data redrawn in SHA-256 per year with a $\log_2$ vertical ...

36

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.

29

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

27

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

27

If we take two password strings of different length and attempt to bruteforce match them, it is obvious that the longer one will take longer to crack on average. Actually, that might be obvious to you, but it's not true. A brute force search is one where an attacker has a long list of passwords, and tries them in succession. Now, if the attacker is at all ...

25

So if at each bit he has a 50% chance, that means that 1 bit is actually only half bit. And if he is very lucky, say 90% chance, that means that 1 bit is actually only 0.1 bit.So in face of a very lucky opponent, a 128 bit password has only 12.8 bit strength. You're miscomputing how "luck" affects the number of bits. For a 50% chance, that does not ...

22

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

19

I don't think anyone has addressed the time issue. According to the Margolus-Levitin theorem the limit on the number of operations per second is $6\times10^{33}$ per Joule. The Sun's energy output is about $3.83\times10^{26}$J/sec. You would need to save up the energy output of the Sun for about 25 years to be able to then do $2^{255}$ operations in one ...

19

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

19

There's a 2013 article in Ars Technica that refutes the notion that long passwords are necessarily hard to crack. It details how security researchers Kevin Young and Josh Dustin turned to text from Wikipedia and Project Gutenberg as a seed to come up with longer and longer phrases to try in their password crackers, and managed to crack some impressively ...

18

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

17

There is no such thing as a random key. There are only randomly generated keys. What I mean by that is that randomness is not a property of the key (or message, or number, or whatever), but of the process that generates it. For example, it is not meaningful to ask whether the number 5 is random, or whether it is somehow more or less random than the number ...

16

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

16

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

16

I wrote a similar answer in the past, where the assumption was half the key is known. Since then, the bitcoin hashrate almost tripled (it's used in the estimation, as below). The estimation for half the known key would therefore be $~3.6$ seconds. But to brute force a $128$ bit key, we get this estimate: Let's assume we can test as many keys as the current ...

15

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. The round function is a simple Add-Rotate-Xor function of two 32-...

15

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

15

I'm not sure what you're trying to understand and if the other answers cover it, so I'm trying a different approach and interpret your question like this: What if an attacker guesses the right sequence of 128 bits on her first try by pure chance? That's certainly possible but so unlikely that we don't normally consider that possibility. If you want to ...

15

Birthday attacks do indeed work also for messages chosen by the attacker. For example, consider the case that I want to get a collision between a letter of recommendation and a letter that I was fired. I can prepare $2^{n/2}$ letters of the first kind and $2^{n/2}$ letters of the second kind, and then we expect there to be a collision between a message of ...

14

The brute force technique described in the question is hopeless, as pointed in this other answer. However there are much better techniques to attack RSA keys, including GNFS. Therefore 1024-bit RSA keys, even though they offer sizable security, can no longer be considered entirely safe from predictable academic efforts, or even safe at all from Three-Letter-...

14

No, it doesn't help. It doesn't hurt either; as long as you don't repeat keys, the probability of success is always the same. That is, if there are $2^n$ possible keys, and you test $\lambda$ of them, the probability you hit the right one is always $\lambda / 2^{n}$. A key generated by a high quality random number generator (or a good key derivation ...

14

Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed. Now what a brute-force attack ...

12

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

12

For your first question: The main point here (at least that comes to mind) is that of how the key is made, used, and subsequently how it is attacked. Good symmetric ciphers are designed so that the best possible attack is brute force, i.e. simply trying with each possible key, which are typically random (or as good as). With a 128-bit key you have $2^{128}$ ...

12

This is due to the Brassard et al.'s method on hash functions. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function where as the Grover's method has $\mathcal{O}(\sqrt{n})$-time. Level I: At least as hard to break as AES-128 $\mathcal{O}(\sqrt{2^{128}}) = \mathcal{O}(2^{64})$ - by Grover Level II: At least as hard to break as SHA-256 \$\...

11

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

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