Re: bootstrapping a secure channel
From: Jean-Luc Cooke (jlcooke_at_engsoc.org)
Date: 10 Aug 2004 16:24:52 GMT
Allen Pulsifer <email@example.com> wrote:
> David Wagner wrote:
> > Below I show one standard attempt at a solution, if we may assume
> > that Alice and Bob recognize each others voices.
> > First, Alice and Bob's devices do a Diffie-Hellman exchange over a
> > group of prime order (checking each other's exponents to make sure
> > they are non-trivial). Then, their devices compute a SHA-256 hash of
> > their interaction concatenated with the derived key, and shows this
> > to them along with the alleged identity of their counterpart. Alice,
> > the initiator, says "the first 128 bits showing up on my screen are
> > <such-and-such>". Bob, the recipient, checks these for validity and
> > confirms that he is hearing Alice's voice, then says "the last 128 bits
> > of my hash are <whatever>". Alice checks that this is valid and that she
> > is hearing Bob's voice. If this exchange is not completed in a timely
> > fashion, one must abort. The security of this rests on an assumption
> > that the attacker cannot do 2^64 hash operations in real time.
> > Question: Is this attempt secure? I do not see any obvious attacks,
> > but that is certainly no guarantee.
> > Caveat: It may be possible to optimize the above, but one must exercise
> > caution: some natural optimizations turn out to be insecure.
> > http://www.cs.berkeley.edu/~daw/my-posts/maninmiddle
> > There is another standard approach to this kind of problem, if we instead
> > assume that Alice and Bob share only a low-entropy secret (but do not
> > necessarily recognize each others voice). I expect schemes like EKE,
> > SRP, etc. will suffice to build a key exchange protocol secure against
> > offline dictionary attack in this scenario.
> > One natural question is what the original poster had in mind, and how
> > it relates to these standard schemes.
> Hello Prof. Wagner,
Are you a prof now David, or still waiting for clearence of your
> We did not like the first method (comparing hashes) primarily because of
> the amount of data Alice and Bob have to compare. We felt users would
> not be willing in practice to compare a total of 256 bits (and that new
> users would be overwhelmed to see that many random digits pop up on
> their screens). We wanted to limit the amount of data the humans had to
> compare to something on the order of 10 to 15 characters.
- David suggest a 128bit hash verify on each side, not 256.
- 15 base64 chars (upper, lower case and digits) is 90 bits
+ the security of this is 45 bits. Well within the realm of a
collision search in real-time on today's computers. Your
system is not secure.
> We did not like the second method because it requires a pre-existing
> shared secret. Sharing this secret would require a secure channel, and
> we did not want to require a secure channel in order to bootstrap a
> secure channel (this seems to defeat the purpose).
> We were unable to find an existing method that met our criteria, so we
> created our own. The method we came up with satisfies all of our
> criteria. It requires the users to verify each other's identity and
> compare 15 character strings. If the strings match, the probability of
> a successful impersonation or man-in-the-middle attack is 1 in 2^37.
> The method is documented (not ad hoc) and we we can make definite
> statements about its security. It is not subject to offline or brute
> force attacks, and therefore it does not matter how much computational
> power an attacker has, or how much time elapses between the key exchange
> and when the users compare strings.
- Oh! 37 bits... right I forget that crazy number. If it's a
hash-based system like Wagner proposed, you have < 19bits security.
Not good at all.
> We're hoping eventually that some other people take a look at our
> protocol and either point out any security flaws we missed, or confirm
> that our analysis looks correct.