DOS Exploit

[Tostino]

Hey, just wanted to let you know I've gotten reports from users of my library: Nbvcxz that are getting a DOS every so often by specifically crafted passwords.

I found a tool created by a government contractor used for issuing a DOS against programs using libraries containing the vulnerable (to combination explosion) algorithms from the original zxcvbn implementation:

• https://github.com/twosixlabs/acsploit
• acsploit GoSimpleLLC/nbvcxz#60

I've solved this by implementing a maxLength type configuration...but that isn't totally done yet as I feel like I still need to have it do dictionary checks against the full-length password without any transformations. Working on finishing that feature and putting out a release. I just wanted to mention it to you, since this is also often run server-side rather than client-side.

[formigarafa]

Thank you again, @Tostino.

Confirmed here, too. Polynomial time O(n^c) growth based on number of l33t chars.

[1] pry("main")> $ Zxcvbn

From: /Users/raf/projects/fortito/zxcvbn-rb/lib/zxcvbn.rb:11
Module name: Zxcvbn
Number of lines: 32

module Zxcvbn
  def self.test(password, user_inputs = [])
    OpenStruct.new(Zxcvbn.zxcvbn(password, user_inputs)) # rubocop:disable Style/OpenStructUse
  end
end
[2] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" }
=> 2.9144049999886192
[3] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 2 }
=> 10.000117999996291

I wonder if dropbox/zxcvbn will do anything about that or if they will just leave it because it would only hurt the user-side. Also, they don't seem to be keen to any updates for a while now.

[formigarafa]

It seems the problem is, like you mentioned, very targeted on l33t chars and only affecting that particular part of the code.

[1] pry("main")> Zxcvbn.test("4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/"); ""
                                user     system      total        real
dictionary_match            0.004260   0.000359   0.004619 (  0.004616)
reverse_dictionary_match    0.004523   0.000495   0.005018 (  0.005047)
l33t_match                  2.148309   0.006459   2.154768 (  2.158053)
spatial_match               0.000251   0.000002   0.000253 (  0.000252)
repeat_match                0.491250   0.001083   0.492333 (  0.493077)
sequence_match              0.000026   0.000001   0.000027 (  0.000026)
regex_match                 0.000004   0.000000   0.000004 (  0.000005)
date_match                  0.000308   0.000001   0.000309 (  0.000308)
=> ""
[2] pry("main")> Zxcvbn.test("4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 2); ""
                                user     system      total        real
dictionary_match            0.016808   0.000127   0.016935 (  0.016936)
reverse_dictionary_match    0.018455   0.000213   0.018668 (  0.018722)
l33t_match                  9.509296   0.015470   9.524766 (  9.529493)
spatial_match               0.000581   0.000006   0.000587 (  0.000587)
repeat_match                0.504709   0.000589   0.505298 (  0.505639)
sequence_match              0.000051   0.000001   0.000052 (  0.000051)
regex_match                 0.000004   0.000001   0.000005 (  0.000006)
date_match                  0.000579   0.000000   0.000579 (  0.000579)
=> ""
[3] pry("main")> Zxcvbn.test("4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 3); ""
                                user     system      total        real
dictionary_match            0.042509   0.000547   0.043056 (  0.043102)
reverse_dictionary_match    0.042408   0.000205   0.042613 (  0.042680)
l33t_match                 23.473630   0.048149  23.521779 ( 23.541887)
spatial_match               0.000898   0.000008   0.000906 (  0.000912)
repeat_match                0.500314   0.000498   0.500812 (  0.501139)
sequence_match              0.000071   0.000001   0.000072 (  0.000070)
regex_match                 0.000006   0.000000   0.000006 (  0.000005)
date_match                  0.001074   0.000001   0.001075 (  0.001075)
=> ""

[Tostino]

I opened an issue on the main Dropbox repo[1], because it is an issue for people who have integrated it into their node.js applications. Just because they intended for client side use originally does not mean it stayed there.

1. Possible DOS when run server side dropbox/zxcvbn#326

[formigarafa]

Making some improvements, the times now look linear O(n) which is not perfect but at least not polynomial O(n^c).
Before:

[1] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 1 }
=> 2.598794999998063
[2] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 2 }
=> 9.800470000016503
[3] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 5 }
=> 72.18200199998682
[4] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 10 }
# gave up waiting for it to finish

After:

[1] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 1 }
=> 1.2851360000204295
[2] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 2 }
=> 2.4588430000003427
[3] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 5 }
=> 5.383558000001358
[4] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 10 }
=> 10.556158999999752
[7] pry("main")> Benchmark.realtime { Zxcvbn.test "4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 100 }
=> 167.7868679999956

[formigarafa]

@Tostino, I saw your comment on dropbox/zxcvbn#326 and I believe I did something similar to what you mentioned.
I limited the size of the substring of the password being checked to the size of the longest password for each dictionary.
I did not extensively test it yet, but it is looking good so far.

[Tostino]

Good call, that is a nice dynamic way to ensure we do the least amount of work possible while ensuring we don't miss potential matches. I'll give that a shot.