| Message ID | 20170424170013.85175-6-ebiggers3@gmail.com (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
On 04/24, Eric Biggers wrote: > From: Eric Biggers <ebiggers@google.com> > > Switch f2fs directory searches to use the fscrypt_match_name() helper > function. There should be no functional change. > > Signed-off-by: Eric Biggers <ebiggers@google.com> Acked-by: Jaegeuk Kim <jaegeuk@kernel.org> > --- > fs/f2fs/dir.c | 28 ++++------------------------ > 1 file changed, 4 insertions(+), 24 deletions(-) > > diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c > index 5df3596a667a..c7ed25fb3003 100644 > --- a/fs/f2fs/dir.c > +++ b/fs/f2fs/dir.c > @@ -111,8 +111,6 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname, > struct f2fs_dir_entry *de; > unsigned long bit_pos = 0; > int max_len = 0; > - struct fscrypt_str de_name = FSTR_INIT(NULL, 0); > - struct fscrypt_str *name = &fname->disk_name; > > if (max_slots) > *max_slots = 0; > @@ -130,29 +128,11 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname, > continue; > } > > - if (de->hash_code != namehash) > - goto not_match; > - > - de_name.name = d->filename[bit_pos]; > - de_name.len = le16_to_cpu(de->name_len); > - > -#ifdef CONFIG_F2FS_FS_ENCRYPTION > - if (unlikely(!name->name)) { > - if (fname->usr_fname->name[0] == '_') { > - if (de_name.len > 32 && > - !memcmp(de_name.name + ((de_name.len - 17) & ~15), > - fname->crypto_buf.name + 8, 16)) > - goto found; > - goto not_match; > - } > - name->name = fname->crypto_buf.name; > - name->len = fname->crypto_buf.len; > - } > -#endif > - if (de_name.len == name->len && > - !memcmp(de_name.name, name->name, name->len)) > + if (de->hash_code == namehash && > + fscrypt_match_name(fname, d->filename[bit_pos], > + le16_to_cpu(de->name_len))) > goto found; > -not_match: > + > if (max_slots && max_len > *max_slots) > *max_slots = max_len; > max_len = 0; > -- > 2.12.2.816.g2cccc81164-goog -- To unsubscribe from this list: send the line "unsubscribe linux-fscrypt" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Eric, Jaegeuk, On Mon, Apr 24, 2017 at 7:00 PM, Eric Biggers <ebiggers3@gmail.com> wrote: > From: Eric Biggers <ebiggers@google.com> > > Switch f2fs directory searches to use the fscrypt_match_name() helper > function. There should be no functional change. > -#ifdef CONFIG_F2FS_FS_ENCRYPTION > - if (unlikely(!name->name)) { > - if (fname->usr_fname->name[0] == '_') { > - if (de_name.len > 32 && > - !memcmp(de_name.name + ((de_name.len - 17) & ~15), > - fname->crypto_buf.name + 8, 16)) > - goto found; > - goto not_match; > - } > - name->name = fname->crypto_buf.name; > - name->len = fname->crypto_buf.len; > - } Sorry if this is a stupid question, but why do you have to compare hashes _and_ the last few bytes of the bigname? A lookup via bigname gives you two 32bits hash values, and there I'd assume that this is sufficient for a collisions free lookup. Especially since an resumed readdir() with a 64bits cookie has to work too on your filesystem.
Hi Richard, On Tue, Apr 25, 2017 at 03:37:56PM +0200, Richard Weinberger wrote: > Eric, Jaegeuk, > > > On Mon, Apr 24, 2017 at 7:00 PM, Eric Biggers <ebiggers3@gmail.com> wrote: > > From: Eric Biggers <ebiggers@google.com> > > > > Switch f2fs directory searches to use the fscrypt_match_name() helper > > function. There should be no functional change. > > > -#ifdef CONFIG_F2FS_FS_ENCRYPTION > > - if (unlikely(!name->name)) { > > - if (fname->usr_fname->name[0] == '_') { > > - if (de_name.len > 32 && > > - !memcmp(de_name.name + ((de_name.len - 17) & ~15), > > - fname->crypto_buf.name + 8, 16)) > > - goto found; > > - goto not_match; > > - } > > - name->name = fname->crypto_buf.name; > > - name->len = fname->crypto_buf.len; > > - } > > Sorry if this is a stupid question, but why do you have to compare hashes _and_ > the last few bytes of the bigname? > A lookup via bigname gives you two 32bits hash values, and there I'd assume that > this is sufficient for a collisions free lookup. Especially since an > resumed readdir() > with a 64bits cookie has to work too on your filesystem. > Well, the problem is that hashes may not be sufficient to uniquely identify a name in all cases. f2fs uses only a 32-bit hash so it's trivial to create collisions on it, as I demonstrated. Even collisions of two 32-bit hashes, as used by ext4 and ubifs, are possible. And ext4 currently doesn't even compare the hashes during directory searches, beyond using them to find the correct directory block, since the hashes aren't stored in the directory entries. Could this mean that telldir()/seekdir() is unreliable too, probably. But for lookups of the "digested" names we aren't limited to just the 64-bit readdir position, so we can avoid duplicating the bug. Also, collisions in the digested names are very problematic since they result in undeletable files, rather than just poor performance and broken telldir()/seekdir(). - Eric -- To unsubscribe from this list: send the line "unsubscribe linux-fscrypt" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Eric, Am 25.04.2017 um 19:46 schrieb Eric Biggers: >> Sorry if this is a stupid question, but why do you have to compare hashes _and_ >> the last few bytes of the bigname? >> A lookup via bigname gives you two 32bits hash values, and there I'd assume that >> this is sufficient for a collisions free lookup. Especially since an >> resumed readdir() >> with a 64bits cookie has to work too on your filesystem. >> > > Well, the problem is that hashes may not be sufficient to uniquely identify a > name in all cases. f2fs uses only a 32-bit hash so it's trivial to create > collisions on it, as I demonstrated. Even collisions of two 32-bit hashes, as > used by ext4 and ubifs, are possible. And ext4 currently doesn't even compare > the hashes during directory searches, beyond using them to find the correct > directory block, since the hashes aren't stored in the directory entries. I agree that finding a collision in a 32bits hash is easy, but for 64bits it is *much* harder. > Could this mean that telldir()/seekdir() is unreliable too, probably. But for > lookups of the "digested" names we aren't limited to just the 64-bit readdir > position, so we can avoid duplicating the bug. Also, collisions in the digested > names are very problematic since they result in undeletable files, rather than > just poor performance and broken telldir()/seekdir(). True. Let me think whether we can add such a check to UBIFS. Thanks, //richard -- To unsubscribe from this list: send the line "unsubscribe linux-fscrypt" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Apr 25, 2017 at 09:22:16PM +0200, Richard Weinberger wrote: > Eric, > > Am 25.04.2017 um 19:46 schrieb Eric Biggers: > >> Sorry if this is a stupid question, but why do you have to compare hashes _and_ > >> the last few bytes of the bigname? > >> A lookup via bigname gives you two 32bits hash values, and there I'd assume that > >> this is sufficient for a collisions free lookup. Especially since an > >> resumed readdir() > >> with a 64bits cookie has to work too on your filesystem. > >> > > > > Well, the problem is that hashes may not be sufficient to uniquely identify a > > name in all cases. f2fs uses only a 32-bit hash so it's trivial to create > > collisions on it, as I demonstrated. Even collisions of two 32-bit hashes, as > > used by ext4 and ubifs, are possible. And ext4 currently doesn't even compare > > the hashes during directory searches, beyond using them to find the correct > > directory block, since the hashes aren't stored in the directory entries. > > I agree that finding a collision in a 32bits hash is easy, but for 64bits it > is *much* harder. That's true for accidental collisions, but malicious users might create intentional collisions. In the case of UBIFS it looks like the first 32 bits of the cookie depend solely only on the filename via key_r5_hash(), while the second 32 bits is random. So I imagine a collision in the full 64 bits could be generated by precomputing on average about 65536 filenames which collide in key_r5_hash(), then creating them all in the same directory. Eric -- To unsubscribe from this list: send the line "unsubscribe linux-fscrypt" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Eric, Am 25.04.2017 um 22:58 schrieb Eric Biggers: > On Tue, Apr 25, 2017 at 09:22:16PM +0200, Richard Weinberger wrote: >> Eric, >> >> Am 25.04.2017 um 19:46 schrieb Eric Biggers: >>>> Sorry if this is a stupid question, but why do you have to compare hashes _and_ >>>> the last few bytes of the bigname? >>>> A lookup via bigname gives you two 32bits hash values, and there I'd assume that >>>> this is sufficient for a collisions free lookup. Especially since an >>>> resumed readdir() >>>> with a 64bits cookie has to work too on your filesystem. >>>> >>> >>> Well, the problem is that hashes may not be sufficient to uniquely identify a >>> name in all cases. f2fs uses only a 32-bit hash so it's trivial to create >>> collisions on it, as I demonstrated. Even collisions of two 32-bit hashes, as >>> used by ext4 and ubifs, are possible. And ext4 currently doesn't even compare >>> the hashes during directory searches, beyond using them to find the correct >>> directory block, since the hashes aren't stored in the directory entries. >> >> I agree that finding a collision in a 32bits hash is easy, but for 64bits it >> is *much* harder. > > That's true for accidental collisions, but malicious users might create > intentional collisions. In the case of UBIFS it looks like the first 32 bits of > the cookie depend solely only on the filename via key_r5_hash(), while the > second 32 bits is random. So I imagine a collision in the full 64 bits could be > generated by precomputing on average about 65536 filenames which collide in > key_r5_hash(), then creating them all in the same directory. Correct. As I said, I'll think of a way to check the remaining bytes in the bigname case. Thanks, //richard -- To unsubscribe from this list: send the line "unsubscribe linux-fscrypt" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Apr 24, 2017 at 10:00:12AM -0700, Eric Biggers wrote: > From: Eric Biggers <ebiggers@google.com> > > Switch f2fs directory searches to use the fscrypt_match_name() helper > function. There should be no functional change. > > Signed-off-by: Eric Biggers <ebiggers@google.com> > Acked-by: Jaegeuk Kim <jaegeuk@kernel.org> Thanks, applied. - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-fscrypt" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c index 5df3596a667a..c7ed25fb3003 100644 --- a/fs/f2fs/dir.c +++ b/fs/f2fs/dir.c @@ -111,8 +111,6 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname, struct f2fs_dir_entry *de; unsigned long bit_pos = 0; int max_len = 0; - struct fscrypt_str de_name = FSTR_INIT(NULL, 0); - struct fscrypt_str *name = &fname->disk_name; if (max_slots) *max_slots = 0; @@ -130,29 +128,11 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname, continue; } - if (de->hash_code != namehash) - goto not_match; - - de_name.name = d->filename[bit_pos]; - de_name.len = le16_to_cpu(de->name_len); - -#ifdef CONFIG_F2FS_FS_ENCRYPTION - if (unlikely(!name->name)) { - if (fname->usr_fname->name[0] == '_') { - if (de_name.len > 32 && - !memcmp(de_name.name + ((de_name.len - 17) & ~15), - fname->crypto_buf.name + 8, 16)) - goto found; - goto not_match; - } - name->name = fname->crypto_buf.name; - name->len = fname->crypto_buf.len; - } -#endif - if (de_name.len == name->len && - !memcmp(de_name.name, name->name, name->len)) + if (de->hash_code == namehash && + fscrypt_match_name(fname, d->filename[bit_pos], + le16_to_cpu(de->name_len))) goto found; -not_match: + if (max_slots && max_len > *max_slots) *max_slots = max_len; max_len = 0;