297 reputation
26
bio website
location
age
visits member for 2 years, 11 months
seen Mar 30 '12 at 23:55

Mar
26
awarded  Popular Question
Jan
28
awarded  Nice Question
Dec
5
awarded  Yearling
Oct
24
awarded  Necromancer
Feb
23
comment Are derived hashes weakening the root?
This is incorrect. Knowledge of h1 or h2 only allows an adversary to verify that their guess of plaintext is correct if salt1 or salt2 respectively are published. The original question is careful to ask whether knowledge of h1 and h2 ALONE increase the chances of finding root or the plaintext.
Feb
23
comment How can one share information using the 'host-proof' paradigm?
What security assurances are given by a "host proof" application? By "to allow people to share passwords" do you mean "not to be insecure if different parties happen to choose the same password"? What functionality do you require from your "password management and sharing utility" that needs to be kept secure? In particular what is your definition of secure if passwords are shared?
Feb
22
comment Are derived hashes weakening the root?
@fgrieu: I would contend that your public function H is not preimage resistant as the relevant preimages can now be found with 2^128 work instead of the normal 2^256.
Feb
22
answered What exactly is the impact of the hidden subgroup problem on cryptography?
Feb
22
answered Are derived hashes weakening the root?
Feb
22
comment Are derived hashes weakening the root?
We seem to differ in our understanding of what preimage resistance is. After reading [Rogaway and Shrimpton's "Hash Function Basics"](www.cs.ucdavis.edu/~rogaway/papers/relates.pdf) it seems understandable that we might have different ideas of what it means. They rigorously specify three different variants, "Pre" "aPre" and "ePre". In order to save time, I would contend that no hash function that is not group preimage resistant in your definition would ever be considered "secure" and that the security property we were originally discussing can certainly be guaranteed from collision resistance.
Feb
22
comment Are derived hashes weakening the root?
Contrary to what you say, I'm sure that the security property can be derived from the preimage resistance of the hash function. If you can find "root" from the results of the hash of concatenating it with arbitrary "saltN" values faster than brute force then the hash is not preimage resistant.
Jan
24
comment Is it possible to figure out the public key from encrypted text?
Why did this get a downvote? It's completely correct and actually satisfies the constraints of the question. The above upvoted answer doesn't satisfy the constraint that Eve ONLY sees the ciphertexts.
Jan
23
comment Can ECDSA signatures be safely made “deterministic”?
As you say, the RNG is a prime target for attack. As Thomas Pornin has said, it's very difficult for an implementation to know whether their source of random numbers has been compromised. I seem to remember some devices by a Swiss firm Crypto AG being compromised in this fashion. Much better to remove the need for random numbers hence my, Pornin's and Bernstein's schemes. Note that this is the direct opposite of your conclusion.
Jan
23
comment Can ECDSA signatures be safely made “deterministic”?
This doesn't work. If a hash collision is found then the two messages have the same hash $z$. In my scheme, this results in the same $k$ and hence the signature is identical and hence the secret key is not revealed.
Jan
20
answered How to construct encrypted functions (with either public or private data)?
Jan
20
answered RSA with small exponents?
Jan
20
comment How much can we compress RSA public keys?
@fgrieu You probably want to read "On the security of multi-prime RSA" by Hinek and some of the works it references such as CompaqMultiPrimeWP.pdf. Although your scheme onlt uses 2 prime some of the calculations trading off the difference in the difficulty of ECM and NFS should be relevant. In particular, as the size of n increases, it seems that the ratio between the sizes of the factors can safely increase. I believe that for a 2048-bit modulus having one of the primes 512 bits long should be fine.
Jan
19
comment How much can we compress RSA public keys?
This would only save space while storing the public key. To use the public key to encrypt or verify signatures you'd probably be working in the Montgomery representation in which case the numbers are all the same size as the modulus and can't be compressed. If you're decrypting or signing on the smart card then you're probably exploiting the CRT and the Montgomery representation and using larger exponents so the compression is useless again. This is all rather academic as nobody would use RSA in a memory constrained system anyway! Or please enlighten me if I'm mistaken.
Jan
19
comment How much can we compress RSA public keys?
@fgrieu I seem to remember reading somewhere that the expected runtime of ECM and GNFS was roughly equal when the small factor was roughly 1/3 of the bitlength of the modulus. If we assume that the people on the $x^y+y^x$ factorization project allocate their effort optimally then we can see that their GNFS jobs often yield 50 digit factors of 150 digit numbers and the maximum factors found with ECM are about 56 digits. This lends credence to the idea that the factor size ratio should be no larger than 1:2, at least for numbers of this size.
Jan
19
comment Is it possible to figure out the public key from encrypted text?
@yydl Let's take the concrete example of RSA where n=221 and e=11 so that's a 8-bit modulus. If the plaintexts only come from the set 54, 59, 61, 63, 70, 82, 92, 125, 166, 175, 181, 185, 208 then Eve, who just sees the ciphertexts might reasonably assume that the 4-bit modulus 15 is being used. Of course as fgrieu says it's inefficient but it's the best that can be done under the constraints of the original question.