Re: [Encfs-users] vfat and file case

[Valient G. <va...@gm...>]

Interesting question.  It would certainly be possible to implement a
base-32 encoding, although filenames would be twice as long.  But I
also suspect that you're very unlikely to actually run into a conflict
in practice.  It may strain my rusty math skills to check that, but
it's good practice.

The smallest base-64 encoding is 14 characters if you use the default
of block-encoded filenames (or 24 chars for AES).  That results in
64^14 possible names, and since 26/64 of the letters are lowercase
(lets just call lower case the set we want to avoid), then there are
1-(1-26/64)^14 = 99.93% of the names that contain at least one lower
case letter..  Sounds bad, but 64^14 is a huge space.

Or breaking it down by number of lowercase letters,
comb(14,0)*38^14 = 13090925539866773438464 of names have no lowercase letters..
... or generally  numlower(N) = comb(14,N)*26^N*38^(14-N)  have
exactly N lowercase letters

Each of the cases with 1 letter collide with 1 of 64^14 other names
(the name which is exactly the same except for the one lowercase
letter switched to uppercase).  The cases with 2 collide with 3 in
64^14..
or generally collisions(n) = sum(x=1,n, comb(n,x)) = 2^n - 1

So... what is the chance that one particular name will collide with
another name?
If we take a random name and compute the expected number of collisions
as the weighted average:
sum(n=0, 14,  numlower(n) * collisions(n) ) / (64^14) = 118.3

In other words, there are on average 118 other names that would
collide with our randomly selected name - out of 64^14 possible.   A
slight leap here - consider the total space to be 118.3 times smaller
then 64^14 (folding duplicates together), then the birthday paradox
(http://en.wikipedia.org/wiki/Birthday_paradox) tells us that we'd
have to have on the order of 450 billion files before we'd have a 50%
chance of having a single collision.

The chance of being hit by lightning is stated to be around 1 in
280000 (http://www.lightningsafety.com/nlsi_pls/probability.html).  To
have that same chance of having a name collision in your filesystem,
you'd need around 1 billion files.

That's just looking at files of minimum length 14.. It gets even less
likely when you look at longer files..  So collisions are possible,
but very unlikely.

Valient


On Wed, Apr 23, 2008 at 2:14 PM, Thomas Harning <har...@gm...> wrote:
> Just wondering... has there been any looking into how vfat and its case
>  insensitivity affects the file-name encryption of encfs?  It would seem
>  that one would need to use a binary encoding that doesn't put any
>  meaning to upper/lowercase (which would make the filenames quite a bit
>  longer encoded in the end...).
>
>  I pose this since I use a vfat thumb drive that I want be able to pass
>  between machines, but also have an encrypted volume for machines w/
>  encfs.
>
>
>
>  I think I recall seeing an encfs project that lets you view encfs
>  folders in windows... but I suppose you'd run into this problem for
>  sure there.
>
>  W/ MacFUSE... OSX usually is setup w/ a case insensitive filesystem and
>  IIRR most things break if you set it otherwise... wouldn't this too
>  cause a problem w/ encfs?
>
>  -------------------------------------------------------------------------
>  This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
>  Don't miss this year's exciting event. There's still time to save $100.
>  Use priority code J8TL2D2.
>  http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
>  _______________________________________________
>  Encfs-users mailing list
>  Enc...@li...
>  https://lists.sourceforge.net/lists/listinfo/encfs-users
>