Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 15 Aug 2012 20:44:23 -0500
From: "jfoug" <jfoug@....net>
To: <john-dev@...ts.openwall.com>
Subject: RE: SRP

I will start looking at this source.

However, even in this source, there are MANY specifics for base/mod values.
This large table is contained in the file t_conf.c.  There are 2 little ones
(commented out), and 16 other values.  

It appears that the proto is pretty simply:

X=sha1(salt.sha1($u.":".$p))
Then v = g^x%N    Where g and N come from that table above.

Battlenet simply set a stipulation that $u == uc username and $p == uc
password, vs using the 'raw' username and password, and sets the specific N
and g (base) values.  NOTE, the g and N in battlenet are not in the t_conf.c
data file. Here are the documented values used for SRP:

Battlenet:
$u and $p are upper case
g=47
N=11262431565328442703655954861050366992063212392960433625426011557367\
7366691719

And from the t_conf.c:

g=2  (commented out, probably as not slow enough)  (same size as battlenet)
N=12561701899515355471054647971408646824449959488872664687467144725820\
4721048803

g=2  (commented out, probably as not slow enough, 384 bits)
N=19723375778951070780917906298314948823386250192782847971568332984689\
932021510463887787616669271018911848065955312667

g=2  (smallest value not commented out), 512 bits
N=11144252439149533417835749556168991736939157778924947037200268358613\
86335004033901709779025915475090607249118160604477421541346785198972\
4116331597513345603

g=2
N=35876175598485770149892119199262299766031100593063430045837681337258\
66987674558795986563210058438648031990888122219165495541479674572706\
284902930463086781802858523087901874453288407166274630787

g=2
N=10871791351054578590720656490590697602805400869758176290664446823668\
96187793570736574549981488868217843627094867924800342887096064844227\
83673566716831998128876537749980638548991334148872415256288091843870\
1129530606139552645689583147

//oakley prime 1
g=7
N=15525180923007089351309181312584817556313340494345143132023511949029\
66239949102107258669453876591642442910007680288864229150803718918046\
34263272761303128298374438082089019628850917069131659317536746955176\
3119843371637221007210577919

g=2
N=16760943441033506134513952376435009026013552532981390455742093030980\
08658594735515315515238000139165738918647899347470390105463284808489\
79516637673776605610374669426214776197828492691384519453218253702788\
02223320568363583162691335715494191412998548952262990254076836840948\
2248290641036967659389658897350067939

// oakley prime2
g=5
N=17976931348623159077083915679378745319786029604875601170644442368419\
71802161585193689478337958649255415021805654859805036464405481992391\
00050792877003355816639229553136239076508735759914822574862575007425\
30207744771258955095793777842444242661733472762929938766870920560605\
0270810842907692932019128194467627007

// 1036-bit DR prime
g=5
N=73633510803960459580592340614718453088992337057476877219196961242207\
30400993319449915739231125812675425079864519532271929704028930638504\
85730703075899286013451337291468249027691733891486704001513279827771\
74018362916106519487472796251714810077522836342108369176406547759082\
3919364012917984605619526140821798437127

g=2
N=17520593701874158028370915808709757311559135004731036178287990173853\
33366544841483884826147664648546626630359228048030338134283071703680\
28802332669752540042735820584582207684890049393260621695533226569112\
16759726125778565962920386496090139562747608067026106900488218998719\
91953917497602225116280480886924497108570268941426816646936938460102\
8647069420217148751652732063899795068604670043

g=2
N=14869981859231282928165073536194095211524576625963800746148189668102\
44974827752411420380336514078832314731499938313197533147998565301020\
79704078742805147963931692801599841570910129390297107296048752741106\
80823117631715491705280086208133914114459075849128652220761007260502\
55271567749213905330659264908657221124284665444825474741087704974475\
79550549282158574941763934496719230174903332535928627343167549286649\
2416941152646940908101472416714421046022696100064262587

g=2
N=21766174458617435773191008891802753781907668374255538511144643224689\
88623538384095721090901308605640157139971723580726658164960647214841\
02914133641521973644771808873956554837381150726774022351017625219015\
69820740293149529620419333266262073471054548368736039519702486226506\
24886106025697180298495356112144268015766800076142998822245709041387\
39739701719270939921147517651680636147611196154762334220964427831179\
71236371647333871414335895773474667308967050807005509320424799678417\
03686792831676127227423031406754829113358247958306143957755934710196\
17714061736843785227034834953370376550067513284475105502992509244692\
88819

// 2072-bit DR prime
g=2
N=54218939133169617266167044061918053674999416641599333415160174539219\
34845902966009796023786766248081296137779934662422030250545736925626\
89251250471628358318743978285860720148446448885701001277560572526947\
61939255157449083928645845499448866574499182283776991809511712954641\
41244487770339412235658314203908468644295047744779491537946899487476\
80362212954278693335653935890352619041936727463717926744868338358149\
56836864340303776864961677852601361049369618605589931826833943267154\
13281957242613296066998310166663594408748431030206661065682224010477\
20269951530296879490444224546654729111504346660859907296364097126834\
834235287147

// 3072-bit MODP prime
g=5
N=58096059953699580627919159656392014021766122269029005337029008827797\
36177890990861472094774477339581147373410185646378328043729800750470\
09821092448786693505916437158816804754094398164451663275506750162643\
45563981931866289900712486608193612051197936939854332970361182329144\
10171876807536457391277857011849897410207519105333355801121109356897\
45942627184547139795267595944079349307162839412278051012461848823260\
24646498768504588612457842409292584262876997053125845096254195134636\
05155428017165714465363094021609290561084025893662561222573202082865\
79782186527099114508220065697817719282702453899023996917554619077064\
56858934380117144304264093386763147435711545371420315730042764287014\
33036381801705308659830751190352946025482059931306571004727362479688\
41557470259694645777028414843598912963285391839211799747263269307811\
31298864873993477969827727846158652326212896569442842168246113187097\
64535152507354116344703769998514148343807

// 4096-bit MODP prime
g=5
N=10443888814131525066796027198465295458312690609921350090225887564443\
38172022322690710444046669809783930111585737890362691860127079270495\
45451721867301692842745914600186688577976298222932119236830334623520\
43680510103091556741556974603471769463940765351572849948952848216337\
00921811716738972451834979455897010306333468590751358365138782250372\
26911796898519432244453568741552200715163863814145617842062127782267\
49950279902786734586295443917369197662990055115054461776681544462348\
82665961680796576903199116089347634947187778906528008004756692571666\
92296412256617458277670733245237100127216377684122931832490312574071\
35741410051245619659138888997534617353479700116932563167516606789508\
30027510255804846105583465055446615090444309583050775808509297040039\
68005743534225392656624089819586363158888893636412992005930845566945\
40340103914782387841898885946723362427637951381763532228455246440400\
94258962433613354036104643881925238489224010194193088911666165584229\
42466816544168892779046060826486420423771700205474433798894197466121\
46996897065215430062626045358909981257522759426087721743761073142177\
49233048217904944409836238235772306749874396760463376480215133461333\
47839568274660824258513395388388222678611803018402813675597004538553\
4758453247

// 4116-bit DR prime
g=11
N=10951211157166778028568112903923951285881685924091094949001780089679\
55253005183831872715423151551999734857184538199864469605657805519106\
71752965504405483319768745978263629725521974299473675154181526972794\
07518606702687749033402960400061140139713092570283328496790968248002\
50742691718610670812374272414086863715763724622797509437062518082383\
05605014462496277630214789052124947706021514827516368830127584715531\
60422794055576326393660668474428614221648326558746558242215778499288\
63023018366835675399949740429332468186340518172487073360822220449055\
34058256846156864525995487330361695377639385317484513208112197632746\
27403549307444874296172025850155107442985301015477068215901887335158\
80733527449780963163909830077616357506845523215289297624086914545378\
51108253422962011656326016849452390656670941816601111275452976618355\
45793212249409511773940884655967126200762400673705890369240247283750\
76210477267488679008016579588696191194060127319035195370137160936882\
40224439969917201783514453748848639690614421772002899286394128821718\
53539149915834004216827510006035966557909908155251261543943446413363\
97793791497068253936771017031980867706707490224041075826337383538651\
82549367950377193483609465580277633166426163174014828176348776585274\
6577808019633679

// 6144-bit MODP prime
g=5
N=33751521821438561184518523159967412330064897805741846548173890474429\
42990132667244520323510191916548396419435946099488106208938789376281\
40442574382044325739410830148270060902589258751610180963277323358005\
95831915976014208822304007327848132734933297885803213675261564962603\
34045722077682632250005809131096725397661997398803366366638518815521\
26562680795017262233696934279998041344678101207723564985969455323665\
27400517575471969335854905274504119509592366013711954148258884879224\
59991520345631588103477655308367699571833559858639559116999957082451\
50350175435333526975252877533325005271765695768949267349504692935961\
34095086603716860086302051544539652689091299099784588919052383463057\
78944056546068144190244239995641906052162960469734787902465431380018\
60783165269645292880627408790110351759200591921785614731990062058967\
19435014765345518490882366607110905303449152556221163232127426440691\
92113464876663569585023923130459174421561098502963689540671888076630\
82492273159842675422662594896843722239164454110159005062394192679097\
16320331208988978180868987431623710347617992356201449023892203230133\
00942146391429120134606312521963696426168359154101434423927534073569\
09977322220697587739633908763605465157552805170421605254873028981223\
11669799679447530453600399342697032714458549591285939453949034981248\
11432232236723864504251598444789078891782357633001915169656865431415\
30585475920913660145501438196851700683437001046776090411663697600809\
33413605498962382077778845599834907475953430787446201384567328530675\
27579296235488377080690082718368571835346957473168052062194454094773\
46190351771800579730226525710321965982292591948757099947097217931541\
58686515748507274224181316948797104601068212015232921691482496346854\
41369871975019060110270527448105054323981513068607360107630451228454\
92184598460460822535967624338274190600890294170448712183160209231099\
88915707117567

// 8192-bit MODP prime
g=19
N=10907481356194159294502949293597845003481551249531722117741011069661\
50168922785639028532473848836817769712164169076432969224698752674677\
66273999426578543723359615704597092233804069810050786103304731233182\
39824352794757001998609716127325405287965545028679197467769837593914\
75987142521315878719577519148811830879919426939958487087540965716419\
16746749932615622652967520917227700137759124814756378288055886108332\
71741540149751348931251160157763188902959606980116141577212825275394\
68816519319333337503114777192360412281721018955834377615480468479252\
74886732036238535559660179512280675621771357981987063432156190781325\
51537039507952712326524048949838694921744816523038034988813662105086\
47263668376514131031102336837488999775744046733651827239395353540348\
41487285463971929469432345018688418982254454064722698729216069318473\
46549419069366465761302609721932803171716964189715539541614461917590\
93719524951116705577362073481319296041201283516154269044389257727700\
28968411946028348045230620413002491387998113590802698386820596931816\
78196808509986496944169079527129049624049377757896989172073563552274\
55066183815847669135530549755439819480321732925869069136146085326382\
33462874545639807160305805163420938670870330654590319960852382451372\
96251366591282211009677354505199524042481982628138310973742616503800\
17277916975324134846574681307337017380830353680623216336949471306191\
68643824930568641338023104609645095359408937554028503729247092939511\
40283055474525849620743094381518254379029760128917493551986784206037\
22034900311364893046495761404333938686140037848030916292543273684533\
64003263763910077450237154247930247369838869289242094647894773380038\
77827414177864847701901088678797789916332186286405339826193224661548\
83011452291890252336487236086654396093853898628805813177559162076363\
15443649447750787129411984163786770172216660983120184548407807051804\
13368698083984546255869212013081856388880826994086865360451926495691\
98110353659943111802300636106509865023943661829436426563007917282050\
89442938884174888539829070774305297360535927751574961973082377321589\
47551217614678878653277071155738042645192063492158501951953648133875\
26811742474131549802130246506341207020335797706780705406945275438806\
26597851620970679570257924407538049023174103086261496878330620786968\
78681084236399719832090776247580804999882755913927872676271824428928\
09646874228263172435642368588260139161962836121481966092745325488641\
05423883929513899297933544611009032523095527687052461135912491839274\
0353154294858383359


I assure you, that 19^x % (prime 2^8192) is pretty slow.  When numbers get
this size, it is best to use a fast FFT exponentator (GMP does FFT's, but it
is very slow at them).  G.Woltman has very fast exponenation code (I did a
lot of development with it years ago), but it is VERY complex to use.

I am not quite sure how to proceed with SRP at this time.  I think I will
let this stew a little first.  The biggest issue, is figuring out just what
exponent a particular hash is using.  Some likely can be 'guessed' by length
of the base-64 hash.  Others can not, since there are multiple exponenents
or different bases.

The DR primes (above) can exponentiate about 6x faster than the others here.
They are 'almost' Mersenne type primes.  They are of the form 2^x-k where k
is 'small'. There is specialized FFT code that is much faster at doing
square-mod for these type numbers, and the mult's can be done for 'almost'
free.  This is why the largest primes known, are always Mersenne primes.

Jim.


>From: Solar Designer [mailto:solar@...nwall.com]
>
>Jim -
>
>This is very nice.  Thank you!
>
>On Tue, Aug 14, 2012 at 10:09:31AM -0500, jfoug wrote:
>> I am not sure of the leak. I have seen no 'real' hashes.
>
>Same here.  How about we target genuine SRP as released at
>http://srp.stanford.edu/download.html for now?  That would be of some
>use on its own - hopefully even of more use than targeting Blizzard's
>"custom SRP".
>
>> At this time, I am hesitant to release this, since we really do not
>> know if this is correct,
>
>Maybe you can build/install SRP, generate some test verifiers, and use
>those?  I just downloaded srp-2.1.2.tar.gz from the URL above and took a
>look.  At first glance, it appears to use SHA-1 in the verifiers.
>Specifically, I looked at the function t_makepwent() and its uses from
>base/src/passwd.c and base/pam_eps/pam_eps_passwd.c.
>
>> Some 'assumptions' I have made:
>>
>> Username data uppercased.
>>
>> Password uppercased.
>
>When we don't target Blizzard's SRP verifiers specifically, these
>assumptions will need to be removed or made optional.
>
>> Format is:
>> $WoWSRP$256_bit_hash_in_upper_case$salt_in_upcase_hex*USERNAME_UPCASE
>
>The official SRP distribution already includes some code to format
>verifiers as ASCII strings:
>
>_TYPE( void )
>t_putpwent(ent, fp)
>     const struct t_pwent * ent;
>     FILE * fp;
>{
>  cstr * strbuf = cstr_new();
>  char saltbuf[MAXB64SALTLEN];
>
>  fprintf(fp, "%s:%s:%s:%d\n", ent->name,
>	  t_tob64cstr(strbuf, ent->password.data, ent->password.len),
>	  t_tob64(saltbuf, ent->salt.data, ent->salt.len), ent->index);
>  cstr_clear_free(strbuf);
>}
>
>We can't use the colon between the encoded ent->password.data and
>ent->salt.data, but with the colon replaced by '$' the rest of the
>string format should be usable as-is.  prepare() can take care of
>extracting field[1] and field[2].
>
>Thanks again,
>
>Alexander

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ