Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Security Audit #7

Open
defuse opened this issue Mar 31, 2014 · 6 comments
Open

Security Audit #7

defuse opened this issue Mar 31, 2014 · 6 comments

Comments

@defuse
Copy link
Owner

defuse commented Mar 31, 2014

Do a 'formal' security audit of the code.
@defuse
Copy link
Owner Author

defuse commented Apr 1, 2014

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

@defuse
Copy link
Owner Author

defuse commented Apr 2, 2014

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!

@defuse
Copy link
Owner Author

defuse commented Apr 21, 2014

I did a 30-minute audit which lead to these fixes: 9eb2c4b, f2c70be, 1788d91, c7d662a, 69207b0 and issue #14.

@defuse
Copy link
Owner Author

defuse commented Apr 21, 2014

I think I've found all the possible problems that I can... maybe it's worth paying someone else to have another look?

@peteygao
Copy link

Do you have an estimate on how much would an audit of passgen cost?

@defuse
Copy link
Owner Author

defuse commented Oct 24, 2014

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@peteygao @defuse