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

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
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
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.
Jan
19
comment How much can we compress RSA public keys?
Is the goal to reduce the number of bits that need to be made public in order to publish the public key for a given RSA-like scheme or is the goal to reduce the number of bits that must be securely stored to allow one to regenerate one's own public key from scratch?
Jan
19
comment How much can we compress RSA public keys?
I don't follow this. In what interval are we expecting to find just one prime? For 1536 bit numbers, roughly .1% are primes.
Oct
16
comment How to practically find solutions to a discrete logarithm?
This thread on mersenneforum is required reading. The author of a similar article in that thread is apparently "auditing a security protocol". The modulus is a "safe prime" which possibly represents a valuable real-world problem instance. The parameters are the ones posted here.
Oct
16
comment Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
It's unlikely you'll find anything that shows there's no connection between solving the DLP for primes and factoring because they're very different problems with no obvious connection. You could similarly fruitlessly search for citations stating that an efficient solution to the TSP would not lead to a fast factoring algorithm or DLP solutions.
Oct
16
comment An Elliptic curve cryptography implementation which can be terminated
Yes there are the problems you mention and the fact that n has to be hard to factor makes the signatures etc ridiculously large and slow. It was an idea for a particular implementation where it had to be ECC-based and security during operation was not terribly important but insecurity after termination was important. If there's a better way of getting this functionality then that would be interesting. Unfortunately I can't think of another way to generate an elliptic curve with some secret backdoor that would allow the rapid calculation of logarithms.
Oct
15
comment An Elliptic curve cryptography implementation which can be terminated
Ok. Thomas makes a good point. How about we choose curves where logs are easy to find? If the curves over $Z_p$, $Z_q$ etc are anomalous then the ECDLP can be solved in essentially linear time. This means that the factors can be chosen sufficiently large so that n can't be factored easily.
Oct
15
comment An Elliptic curve cryptography implementation which can be terminated
I know it's not a field but it behaves like one for most purposes. If one could not ignore this fact then elliptic curve factorization would be much faster. That being said - with this scheme you have more information than just knowing $n$ is composite. I want to know whether that introduces a flaw.
Oct
15
comment Does AES have any fixed-points?
Probability Distributions Related to Random Mappings by Bernard Harris from 1960 might be useful.