Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S264428AbTH1WOw (ORCPT ); Thu, 28 Aug 2003 18:14:52 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S264415AbTH1WOO (ORCPT ); Thu, 28 Aug 2003 18:14:14 -0400 Received: from quechua.inka.de ([193.197.184.2]:60128 "EHLO mail.inka.de") by vger.kernel.org with ESMTP id S264423AbTH1WMJ (ORCPT ); Thu, 28 Aug 2003 18:12:09 -0400 From: Bernd Eckenfels To: linux-kernel@vger.kernel.org Subject: Re: Lockless file reading In-Reply-To: X-Newsgroups: ka.lists.linux.kernel User-Agent: tin/1.5.19-20030610 ("Darts") (UNIX) (Linux/2.4.20-xfs (i686)) Message-Id: Date: Fri, 29 Aug 2003 00:11:57 +0200 Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 25657 Lines: 379 In article you wrote: > Find those GIFs, double-check, and publish immediately. That would be > amazingly big news and would probably cause huge numbers of people to switch > from MD5 to SHA1 overnight. Why is that? For a hash with n bits there are at least 2^y / 2^n = 2^(y-n) files with the same hash, if they have size y bits. Three are even more, if you consider all files up to this size. With n=128 (md5) and y=80000 (10k file) x=2^79872 different files with the same hash, which is: 73758771305612149138757973947840453624822288693642912037251984265061\ 00114977473466610342516138996953532522212913684506495987369027376247\ 15680102183899956755293229604036298841899346896312975318416816792181\ 27163102430377376805525407677117167195273455353500937474682475767850\ 59179157052570202917558881297004500267146311552672331119254293941288\ 81200564802772472735124212232463022640846529434844027943281412745730\ 85139886962923676798297010059108583228148158547397805954834594989809\ 72953082523096457840274668781301014306803374729359559243555477575414\ 40743184860888676456545815644014580307967389124314445607714035149073\ 07589212426013390575273338209003958822345762588652779339518192543309\ 86317487722170491968583142374006999722192982951269179790768422998167\ 08449702141611939030460451116251870263862094621134152440907522456787\ 51931691226465546945055073850028999878309015830845841569473374428818\ 38069014874242916295358660843459867579762128717086485255524813917818\ 93048437497315173334429979530572030202862199229371143871214566570030\ 75727422692477487723119025817627046899875118936499627544458020896601\ 57937925093115270533258873516793039117097872784457478242527803568668\ 28631394601551771044737759212698144953003036178706026830838663271584\ 01592980859584723256093157100606730021922520778222789293516580288692\ 25264244660543124963539004344523631091601054705861145611115771926445\ 77478534613667305980110146817904878379835989090392217842151012038447\ 32903904630045111054945146422201082791203805511249222706103705145946\ 71820615624444389237027551184044272914241672227827166453175228687028\ 66938683553829374974281116729061361295584136766500184918365115021199\ 37169541145849843445053788883266574169813935549175907371700139138138\ 72502071050440159721888802465338768753780473818364722509365607509899\ 90281003295942592341570547210474186910921077818634263104420109401884\ 65729426198803625408484236068350211025109659994524663107915732813683\ 23249026269135868577867279765840583230539982435092205081214139636131\ 52716158876922016303074856693366702970999646715276255547943011782454\ 30451711340888832195663444371564861489518840602769168182051363706921\ 56348391007580137339506987160160155329372785718654816692279404095002\ 71631290709679864507500640424102364928586816669728574941400097861766\ 98623345776769276035921922328812527260139781666739266290331711100138\ 69355520506331079686339512263367217460717946825089940625062127323177\ 86653058251722203905147108918559635723363913322812633573852636358143\ 05929154109676275195321548031664387835763338445788114635589758368895\ 17974907569210022960592177775660950422645740978394883220940559863725\ 17922274955785951581660617914435597347391402963730377168547070736184\ 09409184312862027981853714218127309283218818430216375047782183166306\ 16773059670202724953584786650536914280599829953639402884772276266175\ 74429349374567546167841892184392743355864837653142407213100256586750\ 41336949647306338065403113935569936012036214119515511822780434287340\ 30928734800002296824907120604076897989376531011143837044498904591969\ 67573317525873614600338869535377596304879781797541287906717071752299\ 79432009185387838666393216748127057247821526828251843082459605902721\ 91898927046995849949526294260125716903061767423516291316259448887102\ 21455117996027263044925703914568589351096240255287529058558303698852\ 12851051794252832424631653450392428817783210001109070180912805870873\ 07386072771724226933940298630758819641696078651336928520241718916016\ 03519077021589676947417102185394484893439475195997406265182485474944\ 59178017073695377899466712572589814669494675411536769252318932662247\ 42203943726665732107904396523581039784309768624193293669453454613822\ 15749223233434417462994719818283525937442572314803099751885933759868\ 16634054700507294873752867437781563278323662445301928131033228617590\ 35430194103956670055593952506967036312263794347882662751144124966996\ 91351677629105493982971530018612054379318441420814383739436560078198\ 43138418873116377898447796602758998473352233358353697569513976917684\ 45423037648290442116492517078342243822589633273690408706974851274325\ 08132319738846084567101570415478070907066126456504167969509604493072\ 48645914957093677769177377246870165130337742440748526644770151979128\ 47211604618032267059204616591999117507548440215522308874869279619705\ 44790645926520397665781107515922450033794810695414009529069301089709\ 73157072428268136340204167242984153890552777305481674601484732441017\ 28560824403131840588191220521738725204457330809940997294315972715083\ 60725305431083136292963174671514146443703870465945021837055000033974\ 71343654123104963598692282015717496687304002201274588103720513379013\ 73625443109735850169152345779367135337891706905992705940277701946037\ 51485390147093579878750275097249158482766343355558089592208214469361\ 42276931894022033384129759100364979210001950264216905954876971408322\ 93770122779579100592816803465994717468500525380304100505203551456609\ 49222119718024454375095356130282351572692787346489597961086730476245\ 84334725114957596993473817425633275365545763431282993581470273699983\ 69757127063885542311338579547488527586375582908609448860018780419534\ 19537297554404836539225811986557499970844823045184713996979552418442\ 74406760049159007279015378851550531580664049422653169603166655301827\ 48599352193666664508497247573119948382046576805640670494290298734858\ 84417223231477087092260452907970029505261005523561715560411919810056\ 26325051985436811764833953794260944157856829720560313439000417881996\ 66649136236854393658468387755348570975402758189647533662960697427372\ 12412647608184960382793382969692900066773207105873069629313639145519\ 80713895245632909242920773336712845268455388312926807578615068583681\ 14735015718512752431993230816015076649376333137154762997959604419405\ 40830019834949523547804904348975842603471995834045489085385950422244\ 21421527056856660062948296226796218876244177325383754033674652041604\ 73794980904792158435418276687436661921442912299388028773041675317063\ 41702985744933602467081363806581646503634957766157218777471663915518\ 02627490937845991300518517420026319487215368719584336485771425750960\ 74147906392458647321632082098445775029982834370708320917720129979770\ 70455506307814353531726531033563236535836642541212334872049648262139\ 75871050354308249098506454123665816967377687075573519014546199680718\ 25504901192973448419707741143954204819897813037578850381034208321065\ 90313529679084091518649506694968971633222734828354332911155417094032\ 10171315988545986151874205830881181014135272806355975146559095444333\ 46904167367553579042699361907200322278137701375922580419478734423318\ 06121488248550399697475750553850800216488249799595528934562185651076\ 98483900622844796406822349397868990356392508055418557772495336464051\ 84315867243632263128883584334516110866716220279538827000535200550974\ 00891217955190870275336026052153821633475850086009198501611505257778\ 47933885680755163296870602837070256783151019285961820158384372038595\ 17860622613336775309534151796578569381023269452368108582507056951247\ 98793404504540912203957292887715691948144120313016926351322062639192\ 87532878209614118770056914646891704747300580355118133346576439497968\ 43441915977050748964333072943054209320237827891228838972888080894003\ 90308897490656128265393212239169918857054561600215188074809617435067\ 81432282933335020500424666690346752022172982638444273323437620748833\ 52465137449659970847203193277839245531164554835482556691810957680344\ 96966689035036985236456367028660016192169034841287219164333818992502\ 01221473697763200027508042141909843428691750233206647821600433304062\ 18891775169474513534619981893727149433699742028109319843146130300790\ 48374620733930112399742313419818337405590406519992557821007628973929\ 00113044791623585643793713735052077993606309171905986641896042192953\ 02914470680005418423614268207498056056631718569685347881208192391048\ 12736436159629914835075343477182008191330928785768860373127939973177\ 63052494277204358579240174730488245462349822120037469207659121017510\ 01218092291272699027706462817620604198339134745323293916578572282549\ 24116244533223866364856865317114967557066663536376343128567680906720\ 61764562620886039013573861476592226708854287846592304969334912469803\ 12507139147064808903612376733627058308253758999654545653079870971966\ 39352239897170601807293538529571930214655824923553210628065441410082\ 64909257175626977532187270976620686987192211027534081125067087406140\ 04272207570560217022276862167201738705591967047132029817306091706167\ 88511161829178775447774522166205835983174468078354646490355262626185\ 92707769692650015463072254012707290128020704879925204262894366607928\ 64569688539411097568820564002708260545302498646096613541573488053035\ 29464112666464799579334001389463815093626821732035568867075693046582\ 56066956011728344932544832226503455818172038856422008742254965154356\ 66307452484032159959349389526776258180342580543432325682116409135613\ 88088767367314844519622100290218802495202321475300477340729565680783\ 24011223601204141085691954438204937682332227360382936775988886545128\ 93525280821911159972971397574162898085649998565393045404760240604331\ 59456659730073515088831333039887309968528845217110079369331693213177\ 05558397796379108248708431620233189642397710829943933934005835585902\ 17513252794090844735190314941878898989170740854188417518129638056086\ 07436762139072615685935122969736651233387075068866259306433410312065\ 73504562435401771168805144280321002849860775467143169339505355458866\ 35914375988685051115119841307132244418293162454216614670787597317746\ 66702911316829023341512709925133948717354523200459998088061675060047\ 00566452526710346126651489557268627487651204778699369531585918862201\ 59394424745148402742835964929610173703136610804997257202644221090466\ 98365297814614744314991928707978437775163172405897520668685112787838\ 76745065718227414525009485074009755851181719599276687557225114880046\ 03173249464073454779191764341396098872621419423704644007522244100096\ 27738372944337782228361617675552100763578393891200653283263519950059\ 32714093086973120414639660768933627220032232042053664212501154040067\ 41174802564325712314623332216263370677113891935181869723499560650683\ 86380815056042861307598414035089442567526704536760404967820726566472\ 34670879286692361894969928723752609821775353401149541579651197092514\ 39298884447458964811457837922247753902245800878298397829819244600259\ 60945304748005444929411694097677373095316194496470938817202711690246\ 79164873737588149815425937970573045094656554393364961182798975769812\ 79063271606896233814472483059102258115803176451232829617731169473560\ 56583472626947527000930777640604734587567158760154364347063261832083\ 30385996594589042026405412914351169274159744595075192817784749916345\ 62470152751910309001973543268287070146028018506822943624359351696941\ 89166494104952290716061467283074936182290043354342490250743196513357\ 17212673549917050251415008968860641379683205051131693384563804473690\ 89903250787076735030486079965562026803790996240143092356323469108949\ 07845535789793689147065546557522839031958055488735322364364131104340\ 87166908595780193040642500443843720507588834041902825237277938594405\ 15509518379205857942740777802594442587952768392559677020956217589081\ 33581899255243337125974255338488475972519745646623282832498001302879\ 97096502521398591719712234914109280948285965958478557415471893042412\ 37475503214912860261669526560018289994451491775859964901871011582605\ 60397222346597960243475095118473975946655966278677300109917282300025\ 91196061133760791076031926996915150405486810283942043845416405992441\ 04234755865756841005862837001581295460756719973524643902069661443476\ 62959323040510506366321536923369435204548433728840037610657060117916\ 95218686643134430952095557859827160438074418388249761882170083975363\ 49979442098222565355493523403865857324728074954237197296535659279741\ 76818946685603045371134466487089332172645850146950210739544416499959\ 11699854986965051039658459578956685582448600003884615796462271186448\ 17152459906468747763647302588605751100068841061137998158161515420480\ 22318750114714645614691409738870229881884135960615681233518827274646\ 97655884831524317196513396138604061144709084173127050169960969426206\ 52655647298123938967996892262704749484308663243367637233409236395877\ 16158838490461567162279329710757545371095127926752344490557461174904\ 98350296783037094146290240832642344526951036992128964662104823342328\ 54326936859341427510045192855933515626979981579879097216743613480412\ 84130111347086326278853018443938104571356527897125855276423431718226\ 89948184483964355088191096584486312766049989136785882316252089805747\ 91742304600477823361721935335348605132172666045313701386462122287056\ 68758394818039394561931249752372359921860235500907703617657471112468\ 36477879522500385199108709199684161073878090521604160929658824487302\ 08189162141752889696881176598927266776983392249528725466796126147755\ 84837319880970278900349346884424939463657023804336647859408884059715\ 87012385007902709564185245198547735808691732425755879909338114582324\ 96496038851490551258638486060560640779848053453363726807356342381429\ 06674320609564946079226292351275912040951590375532791423187152515437\ 23852827475892552409562375800889091489173683224781236872060328011056\ 48781494027495854853889407259647716580473257070974609155548989153057\ 01770396652955542660500535945575049924043963937672274745980419440159\ 73418948752580407334724228608155102768772518992593039260939482902676\ 68501092440834712572791048398198968952196157492831517190068185690130\ 54317743725067865519433837861089656827013210893936524514466555291774\ 10118234887021100028017166818373039407738256677074456585169768128673\ 31216559786733796846363998574307817534685493308372883174988103338379\ 77555499797541822977140710754411379683506825653833835598576632482517\ 06897089238260684742063540778170332874744726525838301125226609661605\ 75675563264013373771866481097747281315582164490082018932862351602307\ 75895597782979091503504290038602647497360256570951098586836413102875\ 05985508624511969413092808738775819236922993770908434526013048298335\ 63019052110438767283756977888399786317944181262208218736332067033822\ 80782661106911795601344763359694750182233827973870280096262437147106\ 21345220816897690852045590174605218233496926136141353580378360441714\ 28438525233992119663994156239594488313118082243243369528158085152773\ 57113378544700236891699113941209103476577008555151150115939550291435\ 84311784078501339810706274047644249675445910838212985742593658736726\ 05590639634037920190032975704406638099883233645741951743468840995139\ 43095512100364094192434566607233069670007691516971518451704593177588\ 61282246970125199204660143691272485688286787069963298843415512939777\ 64698968031194340606574494573123788121878504563898097114591153445491\ 29114045251097051865489399353650136868661016594913875104276448322279\ 38508327655772735551923801839886882663244185808346800338063200999436\ 16634873166641664790809023885607426914349049558044907612956164113179\ 41293084012994951583428416228171274647443699568963003542273548716725\ 17543291905739230393954548707021174633513110455440690091273680401298\ 12811462097001540223298427500619842282324231271218044540375197467894\ 28787621198614457986071126897232495087089840730512905845441161761976\ 66601236384032968167285587365409796297465633367726141545996988226883\ 94404671657814361092082070588158359501103729598165458354758606730331\ 06290923381456909223490297830648362593407596156948828105259159998540\ 44681640786318943172502512008752140731673485710162423305221273151554\ 14015776177271915335460332199341190875273337813209488648738342833559\ 09991792529769222004989099471330675361053443603329769538381697759223\ 41487298533047095302388789420693497992006089184803515480781920674919\ 09075112364663390621356691339916840245607264564259595373510560189888\ 83101152955043503694233791483780253651442819969176278483653883495740\ 57348801797457787746560339910935082336178277998340420138860067492161\ 80813845520161575668483836859059768645273848264199471732826240207283\ 38944009476728508602225488515628992665747699225194127625115010282470\ 11255421483010324323934269992453569693406756352625863659617370205694\ 46730077567953286193905468530935524416186408220535319273409812154850\ 66824640573392916854142528081849040648607925797094385311506922861842\ 29144703260429506651941695600111589700081612805239764675960599037895\ 85277505278580936871197464961945900796506521050743626513365790652639\ 56267995795043841000443373363843188371190067977723895217943323322350\ 07131769451445041372122674930206828784929068233225437967059745018449\ 24032625385535746044191547305282331530150508122071323064899819715044\ 74449341068915282166440199819997121493518122097904841256853371980242\ 48686646703791404029568587332628302419928168479892841143897873463368\ 91001511064038809491058043208641187299641201395772810244836614652387\ 82450681130790331970820232940957236616253594577206591272486713707415\ 46948035707641090744852030891472775930637435026651131633879270089970\ 44303247964187045852327022149531568482844729534374639100547599878437\ 44909519052859764561719309116739679668953213767053177134351858393487\ 62085012809637892432061609006747375297605894263669573918014684415911\ 77903552657797646888181858087038285788571519109995872900507911395336\ 80048417655055459938566880542365695507252330830042280914049463078624\ 33569004674540996019078694725685882888530273965971773466249177582671\ 42332603208213018856233359235015599937114645865169765977699011678178\ 65491574334292488980604052665130357287858832893782241288755784638960\ 64397859346154929859372879633696613249742905340795597385119890246889\ 08688700640311194450755763678975202118000072107423667977807786843802\ 46174591520518486946282593854915117798362423931239232306806408129269\ 34708055912784899835082772799444653961132222086104558970432767747437\ 88633596584638516429917747859701245255267497057587911651007806899367\ 83605388585832329612519332348998714112329223819072111733578428201610\ 89626170510883461035298725572775800706131604421628258178566484068261\ 12405337928043939969536697946870334885024960249216783531029555972097\ 84824503847059549111252017217901866557048983055500910349584743702027\ 02270184957931102654283893318223648235659233326009586692028246496989\ 60710329892077654990141054083454257677162385124341509709606214608731\ 38194953833855587315682647117056971213294828892548510635009164117322\ 69780817879546310416971723639232724179897303295326084797910865848021\ 71103436912274354278556604836788582218736050493567224034486228435752\ 75772545021730137777109249271305862854606379162479556321716369747012\ 71058026509724749532545806263542358710308420248483382469723776037376\ 69597983214319566329384729274790976182741310687825587124747694271202\ 28994119273457226536530124689674046719121694781331975885866944397414\ 80646928865900476175693828843742554200741632048619852118186250519076\ 96565875277089012694058827876101297079720952161195398523023828552657\ 02759085017247705446867703237841506390589295997796632748329114874936\ 18403281978323594239953480189136997128462682656651813935559548642366\ 91344303935616433794560077739844540045026897632503760550277165908180\ 44396002251991670687351585740943555336338404437656999031317379460574\ 33644039340780171677598011917530775848363921450425665793612984955814\ 46229638868178745565157046098390502162983892266194312085128770307885\ 03935195697010019173631562502099772732135285257616457457496713081114\ 27698087930936134900937786460750887725990966034866935651522844738350\ 67836613842467245269685348426064212529884648042396191418842320783973\ 75995845907852205274837621277373785446822230566103387366537283783471\ 14733090624177806365035413997882073568160227884766259995743233063926\ 04323525627951228768897375175821617018283853002830565486213078784078\ 55148910934828741195385502504757742265796083683664577440469374407863\ 13164696065151429326584359520661070954626038065790919987475229950740\ 98216024048599560662121214665212267608906887699061900342360030929097\ 47880445733354436868505653643898815979415719223075312881714224290123\ 41103905501102814618080271895011309165724524105825798203841299390522\ 77992971203468621022598279406809300700081197021715469489274684846553\ 77079370486851280632467450720757578010346887352264309727206549952369\ 84430678997862148905029984576703819937255833785743720341765540435032\ 96646736240918734453057541699910818180971797288574782433416947290678\ 37280856433367250804218572773292211981900395475951298227991332978940\ 27393755102812354289041266547584803540291969245091496543899626015439\ 20544328434478996976635560702205616427714866475845230636742677201248\ 54833564014964014561785203285877295747933756675009893281551897328021\ 59418768491468356922541194834374009854217058462894766713723976242506\ 33501980447527984054506287725044344865461692582424535946790342675202\ 19477924778192351335239273036438409900357736968995545750602630916862\ 07145824980908319494765273379305286696173544270167015094012422019461\ 10110887380826756316024097822574773598557194695478247372939507966203\ 29705858302812528783680908061271781318308853066172524646574009812058\ 15491577412033628444516865373536840299843225279750680250512209287726\ 70397253246630246078780479868717275510620978044054573646725585953242\ 24758324770955832253706182177378996095677809200493210148738421043729\ 74274161518014481783974080854045256838062599340760051731497627412507\ 47265737662102660719976929447755810323498446434442537511040265468910\ 43510141536688577299258638010109977110563868273874430671291803629871\ 60935608539042562755537099055435404432514293203203439433284377871436\ 57994132148348689166418229564255038075101142940868371859796958043423\ 95574667099069464561787497638061471023478899430045148689551367991881\ 21566086064763654052446414731052255138606247622016854079994875327395\ 48336043017691288701099997564691519979028704748160129306878648076267\ 78807483332466167739993336059393439458713795495027130913477137163967\ 33212638853761959999943498955186589302026949447117881641750014115955\ 94467826370160249803549647393175426177149199867597218424686918372730\ 78980944010070138138080752013831258280466907055392611875371510020251\ 51800106836557368069728552452932087455607278280099606979325749370959\ 32140319187190721617428623235849046666769248377704247592637495100653\ 16908459137057163937207803590262164206824274693991636821189334048631\ 18357431296069511882893876953799136574175178784539883682427570859050\ 23638256014536405998794647819608013589296597158733008320056824712260\ 63549827856575391246729828051534769056050117993691741808160658338919\ 44097905646550003580396419617760070019081705875625972878012366674679\ 89292342512250048487425437546815015357199615226915228311396456047784\ 77865786121932224656620803395855540010187517792883116941453865099079\ 74150833888842573806312810859398218917803622873821251271610417946046\ 11112073413623443045273514117087181250817162098103623756234695368183\ 13329645002476824195759384817251427574077359703488481671707390563123\ 29489572243615805666703488202767581029534591772098940413043218935233\ 90863085401224517659534671566110922764069066448030558833184012635309\ 67680593942113177332551690381005762329396768070186525893092140568792\ 80842586082843501854057032456535635578215444814064662533030013057318\ 31828990009857758497553071226979016224998850520128961978321074633694\ 72596920941676631197534864178982171496812717822255063769725399908483\ 22022524322928978677204857120686863585204689473401131106177840652358\ 37371614145085538055371518912620992897032714169143489868354092566936\ 48812775003327275943150768750860164679671172857179015820811479158914\ 84122397219348846942722048529334135862982966040930598883092702070297\ 01021054310366548846285483053033629752307019066118768758621856563205\ 61077991767594949026864421630980354592182135940618795388702995460780\ 15244528568453393510567298824950473694304626782827092561451548697001\ 58655671621640122290190060058355755003380914495159377600243284934348\ 30830232919737374256470494422199465871651077565986045910787485717984\ 28640454849863473825645873938305511859807699766243416400243821342352\ 03754512014015085697869209666106500847867745391449969654486637962121\ 96099816021654477490828443488872228300302385780318236684548929433912\ 93263596581118329352900643557103898820061908796437986587441214584341\ 11988752772398357121525143168135648985355335801715938044069098157455\ 59287951656187194689448537276786455279919640158591032349477352564508\ 41323717085310676425390779501257241835410944478913727273009603729220\ 56811212360534469226325897656316758584230613651821772025561754082913\ 7151881915423973881943439830877204381696 files. Greetings Bernd -- eckes privat - http://www.eckes.org/ Project Freefire - http://www.freefire.org/ - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/