Open defuse opened 10 years ago
Here's the output of one run of the statistical test. This establishes that there is probably no simple bias (one character being more likely than another, independent of position or other characters) larger than 1 part in 10,000 (TODO: Calculate the actual probability of their being a bias and it not being detected).
Edit: In case it changes in the future, the SD_THRESHOLD was 3.5.
$ time ruby statistical_test.rb
WARNING: This might take a few hours to run...
Testing: hex
TOTAL SAMPLES: 64000000
+------+------------+------------------------+-----------------+
| char | total | sd | status |
+------+------------+------------------------+-----------------+
| 0 | 3997719 | 1.177903335026549 | PASS. |
| 1 | 4002404 | 1.2414202619043506 | PASS. |
| 2 | 3999768 | 0.11980428484268275 | PASS. |
| 3 | 4000737 | 0.38058516348731547 | PASS. |
| 4 | 4000504 | 0.2602644808651384 | PASS. |
| 5 | 4001014 | 0.5236273484072428 | PASS. |
| 6 | 3999261 | 0.38161795904630413 | PASS. |
| 7 | 4000686 | 0.35424887673310507 | PASS. |
| 8 | 4001759 | 0.9083436941305127 | PASS. |
| 9 | 3998879 | 0.5788819108131352 | PASS. |
| A | 4003030 | 1.5646852718677964 | PASS. |
| B | 3996431 | 1.843023675015236 | PASS. |
| C | 3998475 | 0.7875066137288413 | PASS. |
| D | 3998354 | 0.8499907450476544 | PASS. |
| E | 4003371 | 1.7407769146753602 | PASS. |
| F | 3997608 | 1.2352234885504187 | PASS. |
+------+------------+------------------------+-----------------+
Testing: alpha
TOTAL SAMPLES: 64000000
+------+------------+------------------------+-----------------+
| char | total | sd | status |
+------+------------+------------------------+-----------------+
| a | 1032943 | 0.6796517679038547 | PASS. |
| b | 1030529 | 1.7157262003207296 | PASS. |
| c | 1031484 | 0.7680932427173833 | PASS. |
| d | 1033325 | 1.0587049509451933 | PASS. |
| e | 1032726 | 0.4643257450767069 | PASS. |
| f | 1031536 | 0.7164943801044263 | PASS. |
| g | 1031514 | 0.738324668132985 | PASS. |
| h | 1030741 | 1.5053616065909816 | PASS. |
| i | 1032291 | 0.03268141360293132 | PASS. |
| j | 1032771 | 0.5089786069533043 | PASS. |
| k | 1033083 | 0.8185717826310469 | PASS. |
| l | 1033519 | 1.2512083999243024 | PASS. |
| m | 1032090 | 0.1667680361125374 | PASS. |
| n | 1031149 | 1.1005089922431646 | PASS. |
| o | 1032753 | 0.4911174622026654 | PASS. |
| p | 1031734 | 0.5200217878473974 | PASS. |
| q | 1033186 | 0.920777222037481 | PASS. |
| r | 1032294 | 0.03565827106137115 | PASS. |
| s | 1032628 | 0.3670817347676724 | PASS. |
| t | 1032315 | 0.056496273270449975 | PASS. |
| u | 1032132 | 0.12509203169437974 | PASS. |
| v | 1032215 | 0.04273230867754441 | PASS. |
| w | 1031510 | 0.7422938114109048 | PASS. |
| x | 1033702 | 1.4327967048891321 | PASS. |
| y | 1032314 | 0.05550398745097003 | PASS. |
| z | 1033316 | 1.0497743785698739 | PASS. |
| A | 1031840 | 0.4148394909825234 | PASS. |
| B | 1032778 | 0.515924607689664 | PASS. |
| C | 1033053 | 0.7888032080466485 | PASS. |
| D | 1031946 | 0.3096571941176493 | PASS. |
| E | 1031265 | 0.9854038371834911 | PASS. |
| F | 1030475 | 1.7693096345726467 | PASS. |
| G | 1032523 | 0.2628917237222783 | PASS. |
| H | 1030679 | 1.5668833273987381 | PASS. |
| I | 1032577 | 0.3164751579741953 | PASS. |
| J | 1032562 | 0.3015908706819961 | PASS. |
| K | 1032268 | 0.009858839754892613 | PASS. |
| L | 1032275 | 0.01680484049125222 | PASS. |
| M | 1031460 | 0.7919081023849021 | PASS. |
| N | 1031748 | 0.5061297863746782 | PASS. |
| O | 1032329 | 0.0703882747431692 | PASS. |
| P | 1031826 | 0.42873149245524256 | PASS. |
| Q | 1030892 | 1.3555264478495102 | PASS. |
| R | 1033597 | 1.328606693843738 | PASS. |
| S | 1032065 | 0.191575181599536 | PASS. |
| T | 1031384 | 0.8673218246653778 | PASS. |
| U | 1032897 | 0.6340066202077773 | PASS. |
| V | 1033057 | 0.7927723513245684 | PASS. |
| W | 1031686 | 0.5676515071824347 | PASS. |
| X | 1033254 | 0.9882526577621172 | PASS. |
| Y | 1032949 | 0.6856054828207344 | PASS. |
| Z | 1031423 | 0.8286226777056599 | PASS. |
| 0 | 1033457 | 1.189686679116546 | PASS. |
| 1 | 1032915 | 0.6518677649584163 | PASS. |
| 2 | 1032703 | 0.44150317122866817 | PASS. |
| 3 | 1032013 | 0.24317404421249306 | PASS. |
| 4 | 1033175 | 0.9098620780232017 | PASS. |
| 5 | 1031214 | 1.0360104139769681 | PASS. |
| 6 | 1030422 | 1.8219007830050837 | PASS. |
| 7 | 1033303 | 1.0368746629166345 | PASS. |
| 8 | 1033223 | 0.957491797358239 | PASS. |
| 9 | 1032967 | 0.7034666275713733 | PASS. |
+------+------------+------------------------+-----------------+
Testing: ascii
TOTAL SAMPLES: 64000000
+------+------------+------------------------+-----------------+
| char | total | sd | status |
+------+------------+------------------------+-----------------+
| ! | 680332 | 0.6324368386160351 | PASS. |
| " | 681369 | 0.6310628776206199 | PASS. |
| # | 680996 | 0.17659287361264273 | PASS. |
| $ | 680546 | 0.3716953349760696 | PASS. |
| % | 680847 | 0.004951444342286475 | PASS. |
| & | 680537 | 0.38266109914784385 | PASS. |
| ' | 679966 | 1.0783779149348545 | PASS. |
| ( | 681046 | 0.2375137856780552 | PASS. |
| ) | 680458 | 0.47891614021119555 | PASS. |
| * | 680850 | 0.0012961896183617267 | PASS. |
| + | 680617 | 0.2851876398431839 | PASS. |
| , | 681119 | 0.3264583172935574 | PASS. |
| - | 681653 | 0.9770936581521628 | PASS. |
| . | 680793 | 0.07074602937293195 | PASS. |
| / | 680691 | 0.1950246899863734 | PASS. |
| 0 | 680355 | 0.6044132190659453 | PASS. |
| 1 | 680187 | 0.8091074836057313 | PASS. |
| 2 | 680692 | 0.19380627174506515 | PASS. |
| 3 | 680881 | 0.03647477586219401 | PASS. |
| 4 | 682186 | 1.6265105807694598 | PASS. |
| 5 | 680230 | 0.7567154992294765 | PASS. |
| 6 | 680378 | 0.5763895995158556 | PASS. |
| 7 | 681319 | 0.5701419655552074 | PASS. |
| 8 | 681561 | 0.8649991799518038 | PASS. |
| 9 | 680936 | 0.10348777913414774 | PASS. |
| : | 679815 | 1.2623590693724 | PASS. |
| ; | 681399 | 0.6676154248598674 | PASS. |
| < | 680791 | 0.07318286585554845 | PASS. |
| = | 681410 | 0.681018025514258 | PASS. |
| > | 681829 | 1.1915352686224145 | PASS. |
| ? | 681196 | 0.42027652187429265 | PASS. |
| @ | 680832 | 0.02322771796191022 | PASS. |
| A | 679792 | 1.2903826889224899 | PASS. |
| B | 680098 | 0.9175467070821655 | PASS. |
| C | 682402 | 1.8896889208920415 | PASS. |
| D | 680511 | 0.41433997342185835 | PASS. |
| E | 681017 | 0.20217965668011595 | PASS. |
| F | 680580 | 0.3302691147715891 | PASS. |
| G | 680255 | 0.7262550431967703 | PASS. |
| H | 680740 | 0.13532219616226918 | PASS. |
| I | 680837 | 0.017135626755368973 | PASS. |
| J | 680311 | 0.6580236216835083 | PASS. |
| K | 681178 | 0.39834499353074415 | PASS. |
| L | 680981 | 0.15831659999301897 | PASS. |
| M | 681316 | 0.5664867108312825 | PASS. |
| N | 681740 | 1.0830960451459803 | PASS. |
| O | 679645 | 1.4694901703948025 | PASS. |
| P | 680760 | 0.11095383133610419 | PASS. |
| Q | 681530 | 0.8272282144712481 | PASS. |
| R | 682217 | 1.6642815462500156 | PASS. |
| S | 681088 | 0.2886873518130017 | PASS. |
| T | 680047 | 0.9796860373888862 | PASS. |
| U | 680628 | 0.27178503918879315 | PASS. |
| V | 680387 | 0.5654238353440812 | PASS. |
| W | 680953 | 0.12420088923638799 | PASS. |
| X | 680010 | 1.0247675123172915 | PASS. |
| Y | 680267 | 0.7116340243010713 | PASS. |
| Z | 680587 | 0.32174018708243135 | PASS. |
| [ | 680451 | 0.4874450679003533 | PASS. |
| \ | 681166 | 0.38372397463504515 | PASS. |
| ] | 681491 | 0.7797099030602263 | PASS. |
| ^ | 679987 | 1.052791131867381 | PASS. |
| _ | 680238 | 0.7469681532990105 | PASS. |
| ` | 680223 | 0.7652444269186343 | PASS. |
| a | 680034 | 0.9955254745258934 | PASS. |
| b | 682037 | 1.4449662628145306 | PASS. |
| c | 681380 | 0.6444654782750106 | PASS. |
| d | 682048 | 1.4583688634689214 | PASS. |
| e | 680222 | 0.7664628451599425 | PASS. |
| f | 681345 | 0.6018208398292219 | PASS. |
| g | 680397 | 0.5532396529309987 | PASS. |
| h | 680897 | 0.055969467723126005 | PASS. |
| i | 680528 | 0.3936268633196181 | PASS. |
| j | 680830 | 0.02566455444452672 | PASS. |
| k | 681987 | 1.3840453507491182 | PASS. |
| l | 681863 | 1.2329614888268952 | PASS. |
| m | 680862 | 0.01332482927733727 | PASS. |
| n | 680000 | 1.0369516947303739 | PASS. |
| o | 681316 | 0.5664867108312825 | PASS. |
| p | 680669 | 0.2218298912951549 | PASS. |
| q | 681545 | 0.8455044880908718 | PASS. |
| r | 680442 | 0.49841083207212755 | PASS. |
| s | 680724 | 0.15481688802320118 | PASS. |
| t | 681085 | 0.28503209708907695 | PASS. |
| u | 680563 | 0.35098222487382935 | PASS. |
| v | 680939 | 0.10714303385807249 | PASS. |
| w | 680447 | 0.4923187408655863 | PASS. |
| x | 681698 | 1.031922479011034 | PASS. |
| y | 680210 | 0.7810838640556415 | PASS. |
| z | 679905 | 1.1527014276546577 | PASS. |
| { | 680303 | 0.6677709676139743 | PASS. |
| | | 680463 | 0.4728240490046543 | PASS. |
| } | 682470 | 1.9725413613010025 | PASS. |
| ~ | 681541 | 0.8406308151256388 | PASS. |
+------+------------+------------------------+-----------------+
ALL TESTS PASS.
real 21m50.433s
user 3m57.133s
sys 21m39.817s
The statistical test on the word generator failed, but I think it's just random error. I don't think this testing methodology is that great for a "character set" of this size -- it needs a MASSIVE number of samples. Let's find a faster way to test it.
Full output here: https://gist.github.com/defuse/9936741
TOTAL SAMPLES: 100000000
STANDARD DEVIATION THRESHOLD: 3.5
+--------+------------+------------------------+-----------------+
| char | total | sd | status |
+--------+------------+------------------------+-----------------+
| aaa | 15088 | 1.4961616332378094 | PASS. |
| aaaa | 14911 | 0.04627338005967708 | PASS. |
| aaron | 14811 | 0.7728725256906801 | PASS. |
| aba | 14747 | 1.2971259053709088 | PASS. |
| ababa | 14953 | 0.3903146604748271 | PASS. |
| aback | 14911 | 0.04627338005967708 | PASS. |
...
| freak | 14838 | 0.5517031311380837 | PASS. |
| fred | 14746 | 1.3053173644284124 | PASS. |
| free | 14853 | 0.4288312452755301 | PASS. |
| freed | 14732 | 1.4199977912334623 | PASS. |
| freer | 14461 | 3.6398831958169304 | *****FAIL!***** |
| frenzy | 14971 | 0.5377609235098915 | PASS. |
| freon | 14977 | 0.5869096778549129 | PASS. |
| fresh | 14673 | 1.903293875626173 | PASS. |
| fret | 15120 | 1.7582883230779236 | PASS. |
...
| zone | 14915 | 0.07903921628969136 | PASS. |
| zoo | 14924 | 0.15276234780722353 | PASS. |
| zoom | 14947 | 0.3411659061298057 | PASS. |
| zorn | 14939 | 0.27563423366977713 | PASS. |
| zurich | 15101 | 1.6026506009853558 | PASS. |
| zzz | 14814 | 0.7482981485181694 | PASS. |
| zzzz | 14834 | 0.584468967368098 | PASS. |
+--------+------------+------------------------+-----------------+
FAILURES!
I did a 30-minute audit which lead to these fixes: 9eb2c4b13c63dbe30bd050126d1c2cb7d7752358, f2c70be5808c3b82fcc288fde37e11ed215eace8, 1788d91c700c8d9857c7a141ad44ad46be533763, c7d662a67b885825c2aedf76ef3a1c63b28d21da, 69207b0d5a2594b316f46b53dc785453494370db and issue #14.
I think I've found all the possible problems that I can... maybe it's worth paying someone else to have another look?
Do you have an estimate on how much would an audit of passgen cost?
I'm not sure. There's not much code so I'd guess about 10 hours or about $2500-$3000 for a good one. I don't think it's popular enough to warrant spending money on yet, if it starts to be more widely used I'll look at crowdfunding or something.
Do a 'formal' security audit of the code.