linux-ext4 - fscrypt: Howto resolve hash collisions?

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-next>] [day] [month] [year] [list]

Date:   Wed, 5 Oct 2016 16:00:36 +0200
From:   Richard Weinberger <richard@....at>
To:     linux-fsdevel <linux-fsdevel@...r.kernel.org>,
        linux-ext4@...r.kernel.org
Cc:     Theodore Ts'o <tytso@....edu>, Eric Biggers <ebiggers@...gle.com>,
        David Gstir <david@...ma-star.at>
Subject: fscrypt: Howto resolve hash collisions?

Hi!

UBIFS uses the r5 hash algorithm for filenames and is able to resolve hash collisions.
Unless I miss something it is not possible to resolve hash collisions for bignames
in fscrypto.

UBIFS does in readdir():
fscrypt_fname_disk_to_usr(dir, key_hash_flash(c, &dent->key), 0, &nm.disk_name, &fstr);

Hence, it feeds its filename hash to fscrypto and when no key is present fscrypto
encodes that hash into a bigname starting with "_".
minor_hash is not set because UBIFS's hash has only 32bits.

Upon lookup UBIFS does:
fscrypt_setup_filename(dir, &dentry->d_name, 1, &nm);

For small names nm will contain the decoded name, UBIFS will compute the r5 hash,
does a lookup and compares whether the found directory entry matches the name.
It not, it will resolve the collision.
On the other hand, with bignames, nm will only contain hash and minor_hash.
UBIFS can do a lookup based on the hash value but it has no way to detect nor resolve
the collision since no name is present.

What do I miss? Are ext4 and f2fs not able to resolve hash collisions and therefore
nobody noticed?

Thanks,
//richard
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html