linux-kernel - Re: CONFIG_VFAT_FS

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Sat, 8 Aug 2009 14:19:22 +0200
From:	Pavel Machek <pavel@....cz>
To:	tridge@...ba.org
Cc:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Alan Cox <alan@...rguk.ukuu.org.uk>,
	James Bottomley <James.Bottomley@...senPartnership.com>,
	Martin Steigerwald <Martin@...htvoll.de>,
	Jan Engelhardt <jengelh@...ozas.de>,
	Theodore Tso <tytso@....edu>,
	Rusty Russell <rusty@...tcorp.com.au>, john.lanza@...ux.com,
	OGAWA Hirofumi <hirofumi@...l.parknet.co.jp>,
	linux-fsdevel@...r.kernel.org,
	Dave Kleikamp <shaggy@...ux.vnet.ibm.com>, corbet@....net,
	jcm@...masters.org, torvalds@...ux-foundation.org
Subject: Re: CONFIG_VFAT_FS_DUALNAMES regressions

Hi!

>  > >   - Similarly, there is a small chance that chkdsk on Windows will
>  > >     rename one file in a directory if they happen to have the same 11
>  > >     byte dummy values. The probability of this happening is
>  > >     approximately 80x lower than with the previous patch.
>  > 
>  > The "small chance" seems to be 90% for 30000 files in directory. And
>  > no, it is probably not 80x lower. Do the math.
> 
> Perhaps you could double check my math? 
> 
> The number of combinations available with the current patch is 
> 35^6 * 7 * 8 for files (for directories there are more combinations, 
> but lets ignore that for now).
> 
> That comes to 102942875000 combinations.
> 
> Now we can do the exponential birthday approximation, which is:
> 
>   p = 1.0 - exp(-(n * (n-1)) / (2 * m))
> 
> where n is the number of entries in the directory, and m is the total
> number of combinations.
> 
> That comes to about 0.0052 for 32767 files in a directory
> (ie. maximully full), or about 0.5%.
> 
> With the previous patch we had 2^30 combinations, which came to 0.393,
> or about 39%. So the new patch has about 75x lower chance of a single
> collision than the old one.
> 
> Similarly for 100 files, the old patch gave a probability of
> 4.6*10^-6, whereas the new one gives 4.8x10^-8, which is about 96x
> lower chance of a single collision. 

I guess I should apologize here. I did not do the math. It just seemed
to me that from the paradox of twins, difference should be
greater. Sorry for confusion.
									Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/