Reputation
25,555
Next tag badge:
391/400 score
76/80 answers
Badges
2 32 104
Impact
~373k people reached

Apr
27
comment Is the Salsa20/ChaCha20 keystream generation one-way?
A keystream generation algorithm which key, assumed unknown and uniformly random, can realistically be found from the output keystream and input other than key, is broken by definition of key per Kerckhoffs's principles, and/or of the security objectives of a keystream generator/CSPRNG.
Apr
27
comment Rabin-Williams, blinding and size of Integer r?
It is not that blinding was not enough to stop key recovery. In the attack, blinding enabled key recovery, because of an implementation bug. That's a problem with RW signature: goof in the Jacobi, or let a multiplicative forgery due to padding creep, and the public modulus is effortlessly factored; in RSA, there are less goofs that can cause this.
Apr
27
comment How multiplicative property of RSA can be exploited
@111: Just hashing the message using e.g. SHA-1 is not quite enough protection for signature; and you can't replace the message with its hash for encryption, for then it can not be efficiently deciphered. $\;$ It remains that indeed, RSA encryption and signature schemes used in practice do not externally have the multiplicative property.
Apr
26
comment Can cycle finding techniques reduce the memory usage of the MitM attack against 2DES and 3DES?
@CodesInChaos: I did the math (it needs a check), and come to the (tentative) conclusion that the method proposed in the question, at least slightly modified to increase the iterated function width $w$ to at least $b$ (64 for DES) rather then $n+1$ (57 for DES), is a significant improvement over MitM with partition into plausible number of runs. However it is far from achieving what's in the above comment, and even the best improvements known do not seem to approach that; my guess is that somewhat you overestimate success odds or underestimate the number of DES operations required.
Apr
26
comment Why does applying 56-bit DES twice only give 57 bits of security?
@CodesInChaos: After studying (and tentatively answering) your question: indeed, distinguished points/cycle finding can help reduce memory requirement, including with known plaintext, more than obvious partitioning of the work does, even if that's still at the expense of more DES operations. I now have some better understanding of how. $\;$ Somewhat the context of the question had me totally stuck to things with cost near $2^{57}$, hence my overlook of what you had in mind. Thanks !
Apr
26
comment Can cycle finding techniques reduce the memory usage of the MitM attack against 2DES and 3DES?
It would help to name the block width of $E^{(1)}$ and $E^{(2)}$, say $b=64$ in the case of DES; and state how from these $b$ bits we determine the $n+1$ bits kept for the iterated function, which is not trivial.
Apr
26
comment Why does applying 56-bit DES twice only give 57 bits of security?
@CodesInChaos: As is, this attack is not really much work only on an hypothetical computer with at least $2^{59}$ bytes of memory (like 500 times the total RAM on the 80,000 CPUs in the current top supercomputer of the TOP500). Otherwise said, as is, it is purely theoretical. $\;$ That why I'd like to understand what you have in mind.
Apr
25
comment How to securely map an element from an smaller domain to the other element in a large domain
The previous comment makes a convincing argument that if $e$ can be guessed, and $Enc_{pk}(r \cdot e)$ known, and $Enc_{pk}$ is homomorphic, and $e^{-1}$ in the sense of the homomorphism can be computed from $e$, then $Enc_{pk}(r)$ can be successfully guessed. While this is far from the question as written (which does not mention anything like homomorphic, or multiplication by $r$, or that this is random), my conclusion is that what's asked in question and comments can't be achieved.
Apr
25
comment How to securely map an element from an smaller domain to the other element in a large domain
I have trouble relating the above comment to the question. $\;$ In particular, is the " small sized domain " of the question that of $r$, $e$, or $v$ in the comment? Is the " public encoding " of the question the " Paillier encryption " of the comment? Also, what is meant by " eliminate $e$ " in that comment? I suggest reformulation the question, incorporating the comment in a unified framework.
Apr
25
comment Non adjacent form of an integer is unique
@Vi Jay: Yes, your summary is correct. The answer now gives more details on the general method, called infinite descent , a special form of proof by contradiction. $\;$ Also I revised the proof. Formerly I used $b=(a−1)/4$ in the second case of the second proof, in order to match the first proof, but that left a gap because I assumed without proof that small $a$ had a single NAF. Now I'm first proving that $0$ has a single NAF, and in the second case of the second proof use $b=a−1$, which is simplest. $b=(a−1)/2$ also works.
Apr
24
comment Which one these alternatives using authentication and encryption will solve this multiple-user database problem?
@Ricky Demer: We also need that " different users " bit.
Apr
24
comment How to securely map an element from an smaller domain to the other element in a large domain
With the requirements as I understand them, and the addition that the encoding/mapping is a deterministic function (in addition to public), there is no solution, for precisely the reason given in mikeazo's comment.
Apr
24
comment How to securely map an element from an smaller domain to the other element in a large domain
Anything wrong with simply: each user $j$ secretly chooses a 256-bit random secret key $K_j$, then computes the 256-bit $\operatorname{HMAC-SHA-256}(K_j,x)$ where $x$ is a $s$-bit element of the small domain? $\;$ Perhaps that does not match the "public encoding" requirement, even though the method is public?
Apr
24
comment Which one these alternatives using authentication and encryption will solve this multiple-user database problem?
There's a solution to the problem even if $E_{pk_D}$ is secure, thus randomized, which is assumed in any sound application of public-key encryption. That seems to be the intend in the textbook: no mention is made of RSA; much less of textbook RSA, which would not be able to directly encipher or sign a sizable database query, sign an RSA cryptogram, or encipher a message comprising an RSA signature, assuming $k_A$ and $k_D$ have the same size. $\;$ $\;$ Additional hint: the policy is worded with "A user" rather than "Anyone".
Apr
24
comment Which one these alternatives using authentication and encryption will solve this multiple-user database problem?
Hint: assume that an answer counts as information about what was asked. $\;$ Note: one method clearly beats the other, but both have the pitfall that the length of $R$ (and of the answer) is not masked, which is information about what was asked. $\;$ Note: You should probably retype and reword the question more concisely, in particular because there is a chance that you'll find the solution doing so; at least, give credit to the textbook (the question is interesting), and verify that you have the right to repost this extract.
Apr
24
comment what is number of invertible matrix m*m on$ z_n$?
The question is in fact a duplicate of this one, which has a satisfactory solution (if not answer in the sense of the CSE website logic) in comment, and as an edit of the question.
Apr
24
comment what is number of invertible matrix m*m on$ z_n$?
@Ricky Demer: the OP gives a hint with the tag hill-cipher, which indeed uses as key an invertible $m\times m$ matrix with elements in $\mathbb Z_n$.
Apr
23
comment Why use randomness in digital signature algorithms?
@Ricky Demer: is the only difference between SUF-CMA and EUF-CMA that in SUF-CMA the adversary succeeds by producing any accepted signature that the signer did not produce, including for a message that the signer signed, when EUF-CMA excludes this as a success?
Apr
23
comment Why use randomness in digital signature algorithms?
@Maarten Bodewes: I added a quote in my answer.
Apr
23
comment Why use randomness in digital signature algorithms?
Worth noting: in "RSA-FDH: Hash the message, then apply textbook RSA", Hash is not the run-of-the-mill SHA-something; it needs to be (near) as wide as the RSA key.