Re: bootstrapping a secure channel

From: Allen Pulsifer (amicrypt_at_amishare.com)
Date: 08/09/04 

Date: Mon, 09 Aug 2004 15:21:43 -0400

Jean-Luc Cooke wrote:
>>In order to carry out a brute force attack, you have to have some way of
>>knowing when you have the correct value. The protocol is not vulnerable
>>to this. Feel free to set up 100 thousand computers and guess 100
>>billion tokens. It wouldn't get you anywhere.
>
> Help educate us. How is it not vulnerable to this?

Hello Jean-Luc,

A brute force attack requires an attacker to have some way of
determining whether a value is correct, and if its not, he has to have
the opportunity to try more values (usually many, many more, very
rapidly), until he finds the correct value. For example, if H = HMAC(S,
V), and an attacker knew H and V, he could repeatedly pick a value for
S, plug it into the formula to see if it worked, and keep trying more
values until he finds the right one. Part of the reason the attack
works is because he never has to try the same value of S twice. If S
contains N bits, he is guaranteed to get the correct value after 2^N
tries. He has a 50-50 chance of getting the correct value after 2^(N-1)
tries.

This protocol is not vulnerable to a brute force attack because there is
no point in the protocol where an attacker is able try a value, see if
it is correct, and then try another value. Mallory does have the
possibility of engaging in the protocol, then aborting after Step 2 if
his guess wasn't correct. When he restarts, the parties will generate
new Verification Code. Therefore, this is similar to trying to
interactively guess a 37-bit password where the password changes to a
new random value after each attempt. The system would also limit
interactive guessing by not allowing rapid and unlimited aborts and
retries. This makes a brute force attack impossible.

> Why 37bit?

At 37 bits, a man-in-the-middle attack has a 1 in 2^37 chance of
success. We felt this was sufficient for our application. In general,
the resistance to a man-in-the-middle attack is 1 in 2^(N/2), where N is
the total number of bits compared. If you don't feel 1 in 2^37 is high
enough for your application, you can use as many bits as you want.

> Why not say "15 characator computer generated password to be
> exchanged out of band is used to HMAC the public key for verification
> by the other party." ???

We don't call it a password because its not a shared secret. The 37 bit
codes are exchanged in band and compared out-of-band, similar to
comparing key hashes.

> I generate a key (x509 self-signed cert or GPG) and I send it to you.
  You do the same
> and send one to me. We meet in "meat space" and verify who we are and
> exchange SHA1 fingerprints of eachothers keys/certs.
>
> This can be done over the phone as well, if we consider it "secure".
>
> Since we're *fairly* sure no-one can produce a collision in SHA1 at
> will, this is secure. And more secure than 37bits. And since it's
> humans doing the verification, we're fairly sure it's good.
>
> How do you improve on this? Right now, I'm calling "snake oil".

What we are doing is similar, except that we compare 37 bit Verification
Codes instead of hashes. In addition, the 37 bit Verification Codes are
not subject to an offline brute force attack. We don't require a secure
  channel (private and authenticated), only one that is authenticated,
which means the users can verify each other's identify to their own
satisfaction and no one can tamper with their communication without
being detected. This last requirement is same as the requirement you
would have when comparing hashes.

Our method is better than comparing hashes because the users have less
data to compare. Comparing hashes gives you a total of 320 bits to
compare (160 for each person's key). But I doubt in practice you really
compare all of these bits over an authenticated channel. Most likely,
users will only compare the first ~20 hexadecimal digits of each hash.
This is equivalent to comparing truncated hashes. An attacker could
easily exploit this by generating a key pair where the first ~20
hexadecimal digits of the public key's hash matched yours.

Our method is also better than comparing hashes because we can make more
definite statements about its security. First, because it is not
subject to offline or brute force attacks, we don't have to worry about
increasing computer power or a well armed adversary being able to
overwhelm it. Second, you can be certain that no one is reliably and
accurately comparing 360 bits of hash. If you start making some
reasonable assuptions about how many bits users actually compare, the
security will not look so good.

In short, there is a trade off with the amount of data to compare and
the willingness and ability of users to make a complete and accurate
comparison over an authenticated channel. We felt a total of 10-15
characters total (for both keys) was pushing the limits of what users
would actually be willing to reliably do in practice. We also did not
want the method to be susceptible to offline or brute force attacks,
because it would then become more vulnerable over time or as an attacker
had more resources to throw at the attack.

We ideally would have liked a method where if the users compared N bits
(N bits total for both keys), the "security" would be 2^N. What we
found was a method where the "security" is 2^(N/2). This may be the
best that is possible. We don't know. I am certain however that
compared hashes truncated to 37 bits would offer little security, so
measured in units of "security per bit", our performance is much better
than comparing hashes.

Best Regards,

Allen Pulsifer

Relevant Pages

  • Re: bootstrapping a secure channel
    ... > new Verification Code. ... This makes a brute force attack impossible. ... > would have when comparing hashes. ... Comparing hashes gives you a total of 320 bits to ...
    (sci.crypt)
  • Re: How do i customise an account lockout message?
    ... :> A fraggle or smurf attack would be better than a brute force attack on ... :> a single user's account. ... If you had a default config, you don't have any email accounts. ... And on a network where security is not just a buzzword, ...
    (microsoft.public.security)
  • Re: Best practices for securing SSH server
    ... would recommend that you look into automatic brute force detection. ... There are a number of utilities in ports available for this purpose, ... a brute force attack like this really is unfeasible. ... via pf-- not because it gives any extra security. ...
    (freebsd-questions)
  • Re: Delphi Bugs
    ... >> Would you say that a successful brute force attack of an administrator ... >> password, leading to a hack of the OS, would be a fault of the OS's ... > gets hacked, no matter how it is done, then that's a security breach. ... agree that any hack constitutes a failure in the design. ...
    (borland.public.delphi.non-technical)
  • Re: SSH hacked?
    ... A brute force attack is not going to work. ... Moving sshd is not ... going to increase security*, ... Putting it behind knockd does, far more than your scheme because while you ...
    (Ubuntu)
Quantcast