fgrieu
Reputation
36,285
99/100 score
 Feb 24 comment Difficulty to find any preimages $a$ and $b$ for given $V$ so that $H(a) \oplus H(b) = V$? @user13741: your statement requires an about to become correct. In order to reach odds of success $1/2$, over $1/6$ more than $2^{112}$ evaluations of $H$ are required, even if the adversary had arbitrarily large and fast memory; and since that's not, and such huge search (much larger than all bitcoin mining done to that day) needs to be distributed, significantly more hashing is required. Feb 24 comment How to decrypt RSA if ciphertext is less than the modulus and e=3? @Vitor: absolutely; that's why my hint starts with "if", and for proper use of RSA the odds of the condition that follows are negligible. On the other hand, a noticeable fraction of exercises on RSA with $e=3$ involve exponentiation of something below 16% of the cubic root of the modulus. Feb 24 comment How to decrypt RSA if ciphertext is less than the modulus and e=3? I can't find how the linked pages relate to solving the question (I only see how it could help prove that what's asked is infeasible). Feb 24 comment How to decrypt RSA if ciphertext is less than the modulus and e=3? Hint: if $x$ is small enough that $(x^e\bmod N)=x^e$, then you can find $x$ from $x^e\bmod N$ with the sole knowledge of $e$. Feb 23 comment Do 2DES and 3DES2 have the same effective key length? The quoted NIST document says: "The reference to 80 bits of security strength should be interpreted as a security strength of at least 80 bits, but less than 112 bits (i.e., 80 ≤ security strength < 112)." I do not read the quoted document, and any NIST (or other serious) document that I am aware of, as stating 3DES2 has an effective key length of only 80 bits. Feb 19 comment Why does the FBI ask Apple for help to decrypt an iPhone? The above link is a must-read. In particular it contains an (alleged) verbatim of the technical part of the FBI's demand. Feb 19 comment Usage of 3DES for single block Any reference for a method leaving double-key 3DES with 63-80 bit security? AFAIK, the best mildly credible attacks require $2^{88}$ RAM memory accesses and $2^{90}$ DES, and so much RAM that they are arguably still impractical. Feb 19 comment Can RSA (theoretically) be used as a block cipher? Are you willing to tolerate: 1) loss of capacity; RSAES-OAEP with SHA-256 and a 2048-bit key/blocksize can convey 1520 bit only. 2) non-deterministic result, which prevents some applications of block ciphers, like building a MAC or hash. 3) the fact that OAEP requires a MGF, like one based on SHA-256, which is based on a block cipher, that you want to avoid. Feb 19 comment Can RSA (theoretically) be used as a block cipher? In textbook RSA, encryption requires nothing secret (the public key is all that's needed). In a block cipher, encryption requires the secret key. That makes a huge difference, with important consequences. For example, when OFB, CFB, or CTR block cipher modes are used, ability to encrypt blocks at will (with the right key) implies ability to decrypt the whole message. Related: if an encryption system is deterministic and requires nothing secret for encryption, then it is insecure. Feb 19 comment Can RSA (theoretically) be used as a block cipher? Are you considering RSA with the public key made public, as in RSA? If yes, the main theoretical problem is that at least one of decryption or encryption requires nothing secret. Feb 19 comment Why does Rabin cryptosystem split the message into key blocks? Please revise the question: the Rabin cryptosystem does not split the message into blocks, and the linked slides do not suggest that. The Rabin cryptosystem is best used as the asymmetric component in a hybrid cryptosystem, enciphering a random symmetric key used to encipher the payload; that's especially if the payload + random padding is not smaller than the modulus's width, or we want a simple and strong security argument without the complexity of OAEP. Feb 18 comment Why are recomended RSA key lengths so high? "the concepts of quantum cryptography will break all myths of unbreakable security" is funny! It is mixing quantum cryptography (which attempts to make communications secure without relying on the unproven difficulty of mathematical problems) and quantum computers (which attempt to solve said problems faster than conventional computers do). The commonalities between the two are: being based on quantum physics, and yielding dubious practical achievements. Feb 18 comment How to authenticate two devices with CA? @ele lont. You are right. In easiest workaround, we only prevent the true Dev1 to work if impersonated. In "Another method" or its variant, an adversary that reads Dev1's secret key wins. Notice that in any conventional crypto solution, an adversary that reads Dev1's private key wins, so the problem in the secret key solutions is of the same nature and thus remains tolerable; we can see Dev1's secret key as a temporary private key, restricted to the initial relation with the CA. Feb 16 comment Question on 3DES keys The view that 2-keys 3DES offer only about 80-bit security is I believe discounting the issue of memory and its bandwidth. For a discussion, see this question and tentative answer. Feb 16 comment How to authenticate two devices with CA? Is question 3) assuming step 2) has already occurred, in which case it should be "How does CA know that Dev3 was not imposing as Dev1 at step 2)"? Otherwise, what's wrong with the answer: by keeping Dev1's public key at step 2), and using at step 3) a protocol with messages putatively from Dev1 incorporating a fresh challenge from CA and signed using Dev1's private key, such that the CA can verify the signature against Dev1's public key? Feb 16 comment How does hash speed vary based on string length? @Marteen Bodewes: thinking about it, you are right that there can be a significant sensitivity of the execution time of PBKDF2 w.r.t. the length of the password input; that heavily depends on its implementation. I tried to sort it out the best I could. That's complex, and I could be wrong. Feel free to correct directly in the answer (or comment). Feb 15 comment Does absence of second pre-image resistance infer absence of pre-image resistance? Also related to this answer Feb 15 comment Does absence of second pre-image resistance infer absence of pre-image resistance? If you have a book that states something like second pre-image resistance implies pre-image resistance, can you tell which, of what exact definition of that it gives? You might be interested in: Phillip Rogaway and Tom Shrimpton, Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision-Resistance., with extract in proceedings of FSE 2004. Feb 15 comment How does hash speed vary based on string length? @SLC: oups I has misread your comment; apologies. Your comment is about the time it takes to find a password by brute force (when your original question, and my answer, is about the time it takes to compute the hash knowing the password and salt). Adding 10 characters to the salt length leaves hardness of a brute force attack essentially unchanged, except if the earlier salt was common to many users, and the new one improves on that. Increasing the password length (or the parameter controlling the minimum password length) even by 1 considerably increases the hardness of a brute force attack. Feb 15 comment Unkeyed, fast, one-way PRP We do not know how to make one-way permutations of width nearly as small as a typical MAC. The question linked to by Ricky Demer explores what we have approaching that.