If for authentication a user can own either A OR B public key instead of just one specific key is that equivalent to halving the key space. i.e. it it theoretically twice as easy to brute force and only equivalent to a 128 bit key?
migrated from stackoverflow.com Jan 16 '12 at 16:30
Yes, having two valid keys in effect halves the size of the keyspace — from 2256 to 2255 possible keys per each valid one.
Not to 2128 keys, which is what a 128-bit keylength would get you.
Remember that the number of possible keys grows exponentially with the number of bits per key. (Adding one bit doubles the size of the keyspace, since the added bit has two possible values: 0 or 1.) A 256-bit keyspace has 2256 possible keys, which is a huge number. Even if you had literally billions of valid keys instead of just one, it wouldn't make finding one of them by brute force any less impossible.
I don't believe it's quite as simple as Ilmari is making it out to be, although his end result that "it doesn't really damage the security" is quite correct.
It is easy to see that Ilmari's answer is actually a worse case; the attacker manages to run the same attack on both keys simultaneously, with negligible cost over running the attack over one key. It is easy to see the attacker cannot do better than increasing the probability of success by 2x over a time period versus attacking a single key (because if he could do better, he could use that to improve his single key attack)
It is also see that, in a best case scenario, an attacker might not be able to get any advantage at all over him picking one of the keys, and just attacking that one.
So, which is it (or is it somewhere between the two)? Well, that rather depends on the crypto primitive involved.
If we're talking about RSA, well, the best known attack against that (assuming good padding, and reasonably large prime factors) would be to factor the modulus using NFS. Now, NFS processing is quite specific to the actual modulus being factored; there is no known way to use the same NFS processing to factor two different numbers simultaneously. Hence, if the keys are RSA public keys, it's actually the best case (meaning having a second public key of the same size doesn't appear to help the attacker at all).
If we're talking about an Elliptic Curve-based public key operation (and assuming both public keys are on the same curve), well, it's rather more mixed. The best attack would essentially be finding a value $k$ such that either $kG = M_1$ or $kG = M_2$ (where $M_1$, $M_2$ are elliptic curve points from the public key); it strikes me as likely that a single search (such as one based on BigStep-LittleStep) would be able to take some advantage of having two potential targets (although it isn't clear to me exactly how much).