[PATCH 0/6] fscrypt: fixes for presentation of long encrypted filenames

[PATCH 0/6] fscrypt: fixes for presentation of long encrypted filenames

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

This series fixes the bugs that have been identified with how filesystems handle
presenting long encrypted filenames without the key.

Patch 1 is Jaegeuk's fix to make f2fs start checking the ciphertext portion of
the digested names.  I made one change to this patch which is that to determine
whether we should use the hash from the fscrypt_name structure rather than
compute the hash, we should check for 'disk_name.name' being NULL rather than
'hash' being nonzero, since 0 is a valid hash value.

Patch 2 fixes the bug found on Chrome OS where the wrong part of the ciphertext
was included in the digested names, causing collisions and undeletable files.

Patches 3-6 clean things up to be less insane and confusing, e.g. by introducing
a shared function for name matching and a struct to represent a digested name.

Patches 1-2 will need to be backported and I think they should be merged into
4.12 through the fscrypt tree.  The other patches are nice to have but it's not
a big deal if they need to wait for next cycle.

This patch series leaves out UBIFS; it can be changed to use the common matching
function once available, if desired.

Eric Biggers (5):
  fscrypt: avoid collisions when presenting long encrypted filenames
  fscrypt: introduce helper function for filename matching
  ext4: switch to using fscrypt_match_name()
  f2fs: switch to using fscrypt_match_name()
  ext4: clean up ext4_match() and callers

Jaegeuk Kim (1):
  f2fs: check entire encrypted bigname when finding a dentry

 fs/crypto/fname.c               |  90 +++++++++++++++++++++++++++--------
 fs/crypto/fscrypt_private.h     |   2 -
 fs/ext4/namei.c                 | 103 ++++++++++++----------------------------
 fs/f2fs/dir.c                   |  25 ++--------
 fs/f2fs/f2fs.h                  |   3 +-
 fs/f2fs/hash.c                  |   7 ++-
 fs/f2fs/inline.c                |   4 +-
 include/linux/fscrypt_notsupp.h |   9 ++++
 include/linux/fscrypt_supp.h    |  78 ++++++++++++++++++++++++++++++
 9 files changed, 202 insertions(+), 119 deletions(-)

-- 
2.12.2.816.g2cccc81164-goog


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

[PATCH 1/6] f2fs: check entire encrypted bigname when finding a dentry

[Eric Biggers]

From: Jaegeuk Kim <jaegeuk@kernel.org>

If user has no key under an encrypted dir, fscrypt gives digested dentries.
Previously, when looking up a dentry, f2fs only checks its hash value with
first 4 bytes of the digested dentry, which didn't handle hash collisions fully.
This patch enhances to check entire dentry bytes likewise ext4.

Eric reported how to reproduce this issue by:

 # seq -f "edir/abcdefghijklmnopqrstuvwxyz012345%.0f" 100000 | xargs touch
 # find edir -type f | xargs stat -c %i | sort | uniq | wc -l
100000
 # sync
 # echo 3 > /proc/sys/vm/drop_caches
 # keyctl new_session
 # find edir -type f | xargs stat -c %i | sort | uniq | wc -l
99999

Cc: <stable@vger.kernel.org>
Reported-by: Eric Biggers <ebiggers@google.com>
Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
(fixed f2fs_dentry_hash() to work even when the hash is 0)
Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 fs/f2fs/dir.c    | 37 +++++++++++++++++++++----------------
 fs/f2fs/f2fs.h   |  3 ++-
 fs/f2fs/hash.c   |  7 ++++++-
 fs/f2fs/inline.c |  4 ++--
 4 files changed, 31 insertions(+), 20 deletions(-)

diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c
index c143dffcae6e..374e4b8f9b70 100644
--- a/fs/f2fs/dir.c
+++ b/fs/f2fs/dir.c
@@ -130,19 +130,29 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname,
 			continue;
 		}
 
-		/* encrypted case */
+		if (de->hash_code != namehash)
+			goto not_match;
+
 		de_name.name = d->filename[bit_pos];
 		de_name.len = le16_to_cpu(de->name_len);
 
-		/* show encrypted name */
-		if (fname->hash) {
-			if (de->hash_code == cpu_to_le32(fname->hash))
-				goto found;
-		} else if (de_name.len == name->len &&
-			de->hash_code == namehash &&
-			!memcmp(de_name.name, name->name, name->len))
+#ifdef CONFIG_F2FS_FS_ENCRYPTION
+		if (unlikely(!name->name)) {
+			if (fname->usr_fname->name[0] == '_') {
+				if (de_name.len >= 16 &&
+					!memcmp(de_name.name + de_name.len - 16,
+						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))
 			goto found;
-
+not_match:
 		if (max_slots && max_len > *max_slots)
 			*max_slots = max_len;
 		max_len = 0;
@@ -170,12 +180,7 @@ static struct f2fs_dir_entry *find_in_level(struct inode *dir,
 	struct f2fs_dir_entry *de = NULL;
 	bool room = false;
 	int max_slots;
-	f2fs_hash_t namehash;
-
-	if(fname->hash)
-		namehash = cpu_to_le32(fname->hash);
-	else
-		namehash = f2fs_dentry_hash(&name);
+	f2fs_hash_t namehash = f2fs_dentry_hash(&name, fname);
 
 	nbucket = dir_buckets(level, F2FS_I(dir)->i_dir_level);
 	nblock = bucket_blocks(level);
@@ -527,7 +532,7 @@ int f2fs_add_regular_entry(struct inode *dir, const struct qstr *new_name,
 
 	level = 0;
 	slots = GET_DENTRY_SLOTS(new_name->len);
-	dentry_hash = f2fs_dentry_hash(new_name);
+	dentry_hash = f2fs_dentry_hash(new_name, NULL);
 
 	current_depth = F2FS_I(dir)->i_current_depth;
 	if (F2FS_I(dir)->chash == dentry_hash) {
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index 562db8989a4e..5bc232e21a6e 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -2145,7 +2145,8 @@ int sanity_check_ckpt(struct f2fs_sb_info *sbi);
 /*
  * hash.c
  */
-f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info);
+f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info,
+				struct fscrypt_name *fname);
 
 /*
  * node.c
diff --git a/fs/f2fs/hash.c b/fs/f2fs/hash.c
index 71b7206c431e..eb2e031ea887 100644
--- a/fs/f2fs/hash.c
+++ b/fs/f2fs/hash.c
@@ -70,7 +70,8 @@ static void str2hashbuf(const unsigned char *msg, size_t len,
 		*buf++ = pad;
 }
 
-f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info)
+f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info,
+				struct fscrypt_name *fname)
 {
 	__u32 hash;
 	f2fs_hash_t f2fs_hash;
@@ -79,6 +80,10 @@ f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info)
 	const unsigned char *name = name_info->name;
 	size_t len = name_info->len;
 
+	/* encrypted bigname case */
+	if (fname && !fname->disk_name.name)
+		return cpu_to_le32(fname->hash);
+
 	if (is_dot_dotdot(name_info))
 		return 0;
 
diff --git a/fs/f2fs/inline.c b/fs/f2fs/inline.c
index 0ccdefe9fdba..e4c527c4e7d0 100644
--- a/fs/f2fs/inline.c
+++ b/fs/f2fs/inline.c
@@ -298,7 +298,7 @@ struct f2fs_dir_entry *find_in_inline_dir(struct inode *dir,
 		return NULL;
 	}
 
-	namehash = f2fs_dentry_hash(&name);
+	namehash = f2fs_dentry_hash(&name, fname);
 
 	inline_dentry = inline_data_addr(ipage);
 
@@ -533,7 +533,7 @@ int f2fs_add_inline_entry(struct inode *dir, const struct qstr *new_name,
 
 	f2fs_wait_on_page_writeback(ipage, NODE, true);
 
-	name_hash = f2fs_dentry_hash(new_name);
+	name_hash = f2fs_dentry_hash(new_name, NULL);
 	make_dentry_ptr_inline(NULL, &d, dentry_blk);
 	f2fs_update_dentry(ino, mode, &d, new_name, name_hash, bit_pos);
 
-- 
2.12.2.816.g2cccc81164-goog

Re: [PATCH 1/6] f2fs: check entire encrypted bigname when finding a dentry

[Jaegeuk Kim]

Hi Eric,

This looks good to me.
I'll drop it from my tree, so please move forward through fscrypt.

Thanks,

On 04/24, Eric Biggers wrote:
> From: Jaegeuk Kim <jaegeuk@kernel.org>
> 
> If user has no key under an encrypted dir, fscrypt gives digested dentries.
> Previously, when looking up a dentry, f2fs only checks its hash value with
> first 4 bytes of the digested dentry, which didn't handle hash collisions fully.
> This patch enhances to check entire dentry bytes likewise ext4.
> 
> Eric reported how to reproduce this issue by:
> 
>  # seq -f "edir/abcdefghijklmnopqrstuvwxyz012345%.0f" 100000 | xargs touch
>  # find edir -type f | xargs stat -c %i | sort | uniq | wc -l
> 100000
>  # sync
>  # echo 3 > /proc/sys/vm/drop_caches
>  # keyctl new_session
>  # find edir -type f | xargs stat -c %i | sort | uniq | wc -l
> 99999
> 
> Cc: <stable@vger.kernel.org>
> Reported-by: Eric Biggers <ebiggers@google.com>
> Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
> (fixed f2fs_dentry_hash() to work even when the hash is 0)
> Signed-off-by: Eric Biggers <ebiggers@google.com>
> ---
>  fs/f2fs/dir.c    | 37 +++++++++++++++++++++----------------
>  fs/f2fs/f2fs.h   |  3 ++-
>  fs/f2fs/hash.c   |  7 ++++++-
>  fs/f2fs/inline.c |  4 ++--
>  4 files changed, 31 insertions(+), 20 deletions(-)
> 
> diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c
> index c143dffcae6e..374e4b8f9b70 100644
> --- a/fs/f2fs/dir.c
> +++ b/fs/f2fs/dir.c
> @@ -130,19 +130,29 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname,
>  			continue;
>  		}
>  
> -		/* encrypted case */
> +		if (de->hash_code != namehash)
> +			goto not_match;
> +
>  		de_name.name = d->filename[bit_pos];
>  		de_name.len = le16_to_cpu(de->name_len);
>  
> -		/* show encrypted name */
> -		if (fname->hash) {
> -			if (de->hash_code == cpu_to_le32(fname->hash))
> -				goto found;
> -		} else if (de_name.len == name->len &&
> -			de->hash_code == namehash &&
> -			!memcmp(de_name.name, name->name, name->len))
> +#ifdef CONFIG_F2FS_FS_ENCRYPTION
> +		if (unlikely(!name->name)) {
> +			if (fname->usr_fname->name[0] == '_') {
> +				if (de_name.len >= 16 &&
> +					!memcmp(de_name.name + de_name.len - 16,
> +						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))
>  			goto found;
> -
> +not_match:
>  		if (max_slots && max_len > *max_slots)
>  			*max_slots = max_len;
>  		max_len = 0;
> @@ -170,12 +180,7 @@ static struct f2fs_dir_entry *find_in_level(struct inode *dir,
>  	struct f2fs_dir_entry *de = NULL;
>  	bool room = false;
>  	int max_slots;
> -	f2fs_hash_t namehash;
> -
> -	if(fname->hash)
> -		namehash = cpu_to_le32(fname->hash);
> -	else
> -		namehash = f2fs_dentry_hash(&name);
> +	f2fs_hash_t namehash = f2fs_dentry_hash(&name, fname);
>  
>  	nbucket = dir_buckets(level, F2FS_I(dir)->i_dir_level);
>  	nblock = bucket_blocks(level);
> @@ -527,7 +532,7 @@ int f2fs_add_regular_entry(struct inode *dir, const struct qstr *new_name,
>  
>  	level = 0;
>  	slots = GET_DENTRY_SLOTS(new_name->len);
> -	dentry_hash = f2fs_dentry_hash(new_name);
> +	dentry_hash = f2fs_dentry_hash(new_name, NULL);
>  
>  	current_depth = F2FS_I(dir)->i_current_depth;
>  	if (F2FS_I(dir)->chash == dentry_hash) {
> diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
> index 562db8989a4e..5bc232e21a6e 100644
> --- a/fs/f2fs/f2fs.h
> +++ b/fs/f2fs/f2fs.h
> @@ -2145,7 +2145,8 @@ int sanity_check_ckpt(struct f2fs_sb_info *sbi);
>  /*
>   * hash.c
>   */
> -f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info);
> +f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info,
> +				struct fscrypt_name *fname);
>  
>  /*
>   * node.c
> diff --git a/fs/f2fs/hash.c b/fs/f2fs/hash.c
> index 71b7206c431e..eb2e031ea887 100644
> --- a/fs/f2fs/hash.c
> +++ b/fs/f2fs/hash.c
> @@ -70,7 +70,8 @@ static void str2hashbuf(const unsigned char *msg, size_t len,
>  		*buf++ = pad;
>  }
>  
> -f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info)
> +f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info,
> +				struct fscrypt_name *fname)
>  {
>  	__u32 hash;
>  	f2fs_hash_t f2fs_hash;
> @@ -79,6 +80,10 @@ f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info)
>  	const unsigned char *name = name_info->name;
>  	size_t len = name_info->len;
>  
> +	/* encrypted bigname case */
> +	if (fname && !fname->disk_name.name)
> +		return cpu_to_le32(fname->hash);
> +
>  	if (is_dot_dotdot(name_info))
>  		return 0;
>  
> diff --git a/fs/f2fs/inline.c b/fs/f2fs/inline.c
> index 0ccdefe9fdba..e4c527c4e7d0 100644
> --- a/fs/f2fs/inline.c
> +++ b/fs/f2fs/inline.c
> @@ -298,7 +298,7 @@ struct f2fs_dir_entry *find_in_inline_dir(struct inode *dir,
>  		return NULL;
>  	}
>  
> -	namehash = f2fs_dentry_hash(&name);
> +	namehash = f2fs_dentry_hash(&name, fname);
>  
>  	inline_dentry = inline_data_addr(ipage);
>  
> @@ -533,7 +533,7 @@ int f2fs_add_inline_entry(struct inode *dir, const struct qstr *new_name,
>  
>  	f2fs_wait_on_page_writeback(ipage, NODE, true);
>  
> -	name_hash = f2fs_dentry_hash(new_name);
> +	name_hash = f2fs_dentry_hash(new_name, NULL);
>  	make_dentry_ptr_inline(NULL, &d, dentry_blk);
>  	f2fs_update_dentry(ino, mode, &d, new_name, name_hash, bit_pos);
>  
> -- 
> 2.12.2.816.g2cccc81164-goog

Re: [PATCH 1/6] f2fs: check entire encrypted bigname when finding a dentry

[Eric Biggers]

Hi Jaegeuk,

On Mon, Apr 24, 2017 at 05:10:23PM -0700, Jaegeuk Kim wrote:
> Hi Eric,
> 
> This looks good to me.
> I'll drop it from my tree, so please move forward through fscrypt.
> 
> Thanks,

This is in fscrypt/master now (along with the other patches in the series), but
it's also in f2fs/dev.  Are you still planning to drop it from the f2fs tree?

- Eric

Re: [PATCH 1/6] f2fs: check entire encrypted bigname when finding a dentry

[Jaegeuk Kim]

Hi Eric,

On 05/02, Eric Biggers wrote:
> Hi Jaegeuk,
> 
> On Mon, Apr 24, 2017 at 05:10:23PM -0700, Jaegeuk Kim wrote:
> > Hi Eric,
> > 
> > This looks good to me.
> > I'll drop it from my tree, so please move forward through fscrypt.
> > 
> > Thanks,
> 
> This is in fscrypt/master now (along with the other patches in the series), but
> it's also in f2fs/dev.  Are you still planning to drop it from the f2fs tree?

Oh, yup. I dropped it.
Thank you for pointing this out.

Thanks,

> 
> - Eric

Re: [1/6] f2fs: check entire encrypted bigname when finding a dentry

[Theodore Ts'o]

On Mon, Apr 24, 2017 at 10:00:08AM -0700, Eric Biggers wrote:
> From: Jaegeuk Kim <jaegeuk@kernel.org>
> 
> If user has no key under an encrypted dir, fscrypt gives digested dentries.
> Previously, when looking up a dentry, f2fs only checks its hash value with
> first 4 bytes of the digested dentry, which didn't handle hash collisions fully.
> This patch enhances to check entire dentry bytes likewise ext4.
> 
> Eric reported how to reproduce this issue by:
> 
>  # seq -f "edir/abcdefghijklmnopqrstuvwxyz012345%.0f" 100000 | xargs touch
>  # find edir -type f | xargs stat -c %i | sort | uniq | wc -l
> 100000
>  # sync
>  # echo 3 > /proc/sys/vm/drop_caches
>  # keyctl new_session
>  # find edir -type f | xargs stat -c %i | sort | uniq | wc -l
> 99999
> 
> Cc: <stable@vger.kernel.org>
> Reported-by: Eric Biggers <ebiggers@google.com>
> Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
> (fixed f2fs_dentry_hash() to work even when the hash is 0)
> Signed-off-by: Eric Biggers <ebiggers@google.com>

Thanks, applied to the fscrypt tree.

					- Ted

[PATCH 2/6] fscrypt: avoid collisions when presenting long encrypted filenames

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

When accessing an encrypted directory without the key, userspace must
operate on filenames derived from the ciphertext names, which contain
arbitrary bytes.  Since we must support filenames as long as NAME_MAX,
we can't always just base64-encode the ciphertext, since that may make
it too long.  Currently, this is solved by presenting long names in an
abbreviated form containing any needed filesystem-specific hashes (e.g.
to identify a directory block), then the last 16 bytes of ciphertext.
This needs to be sufficient to identify the actual name on lookup.

However, there is a bug.  It seems to have been assumed that due to the
use of a CBC (ciphertext block chaining)-based encryption mode, the last
16 bytes (i.e. the AES block size) of ciphertext would depend on the
full plaintext, preventing collisions.  However, we actually use CBC
with ciphertext stealing (CTS), which handles the last two blocks
specially, causing them to appear "flipped".  Thus, it's actually the
second-to-last block which depends on the full plaintext.

This caused long filenames that differ only near the end of their
plaintexts to, when observed without the key, point to the wrong inode
and be undeletable.  For example, with ext4:

    # echo pass | e4crypt add_key -p 16 edir/
    # seq -f "edir/abcdefghijklmnopqrstuvwxyz012345%.0f" 100000 | xargs touch
    # find edir/ -type f | xargs stat -c %i | sort | uniq | wc -l
    100000
    # sync
    # echo 3 > /proc/sys/vm/drop_caches
    # keyctl new_session
    # find edir/ -type f | xargs stat -c %i | sort | uniq | wc -l
    2004
    # rm -rf edir/
    rm: cannot remove 'edir/_A7nNFi3rhkEQlJ6P,hdzluhODKOeWx5V': Structure needs cleaning
    ...

To fix this, when presenting long encrypted filenames, encode the
second-to-last block of ciphertext rather than the last 16 bytes.

Although it would be nice to solve this without depending on a specific
encryption mode, that would mean doing a cryptographic hash like SHA-256
which would be much less efficient.  This way is sufficient for now, and
it's still compatible with encryption modes like HEH which are strong
pseudorandom permutations.  Also, changing the presented names is still
allowed at any time because they are only provided to allow applications
to do things like delete encrypted directories.  They're not designed to
be used to persistently identify files --- which would be hard to do
anyway, given that they're encrypted after all.

For ease of backports, this patch only makes the minimal fix to both
ext4 and f2fs.  It leaves ubifs as-is, since ubifs doesn't compare the
ciphertext block yet.  Follow-on patches will clean things up properly
and make the filesystems use a shared helper function.

Fixes: 5de0b4d0cd15 ("ext4 crypto: simplify and speed up filename encryption")
Reported-by: Gwendal Grignou <gwendal@chromium.org>
Cc: stable@vger.kernel.org
Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 fs/crypto/fname.c | 2 +-
 fs/ext4/namei.c   | 4 ++--
 fs/f2fs/dir.c     | 4 ++--
 3 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/fs/crypto/fname.c b/fs/crypto/fname.c
index 13052b85c393..932881f27f2f 100644
--- a/fs/crypto/fname.c
+++ b/fs/crypto/fname.c
@@ -300,7 +300,7 @@ int fscrypt_fname_disk_to_usr(struct inode *inode,
 	} else {
 		memset(buf, 0, 8);
 	}
-	memcpy(buf + 8, iname->name + iname->len - 16, 16);
+	memcpy(buf + 8, iname->name + ((iname->len - 17) & ~15), 16);
 	oname->name[0] = '_';
 	oname->len = 1 + digest_encode(buf, 24, oname->name + 1);
 	return 0;
diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
index 6ad612c576fc..e6301b6933fc 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -1255,9 +1255,9 @@ static inline int ext4_match(struct ext4_filename *fname,
 	if (unlikely(!name)) {
 		if (fname->usr_fname->name[0] == '_') {
 			int ret;
-			if (de->name_len < 16)
+			if (de->name_len <= 32)
 				return 0;
-			ret = memcmp(de->name + de->name_len - 16,
+			ret = memcmp(de->name + ((de->name_len - 17) & ~15),
 				     fname->crypto_buf.name + 8, 16);
 			return (ret == 0) ? 1 : 0;
 		}
diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c
index 374e4b8f9b70..5df3596a667a 100644
--- a/fs/f2fs/dir.c
+++ b/fs/f2fs/dir.c
@@ -139,8 +139,8 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname,
 #ifdef CONFIG_F2FS_FS_ENCRYPTION
 		if (unlikely(!name->name)) {
 			if (fname->usr_fname->name[0] == '_') {
-				if (de_name.len >= 16 &&
-					!memcmp(de_name.name + de_name.len - 16,
+				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;
-- 
2.12.2.816.g2cccc81164-goog


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

Re: [2/6] fscrypt: avoid collisions when presenting long encrypted filenames

[Theodore Ts'o]

On Mon, Apr 24, 2017 at 10:00:09AM -0700, Eric Biggers wrote:
> From: Eric Biggers <ebiggers@google.com>
> 
> When accessing an encrypted directory without the key, userspace must
> operate on filenames derived from the ciphertext names, which contain
> arbitrary bytes.  Since we must support filenames as long as NAME_MAX,
> we can't always just base64-encode the ciphertext, since that may make
> it too long.  Currently, this is solved by presenting long names in an
> abbreviated form containing any needed filesystem-specific hashes (e.g.
> to identify a directory block), then the last 16 bytes of ciphertext.
> This needs to be sufficient to identify the actual name on lookup.
> 
> However, there is a bug.  It seems to have been assumed that due to the
> use of a CBC (ciphertext block chaining)-based encryption mode, the last
> 16 bytes (i.e. the AES block size) of ciphertext would depend on the
> full plaintext, preventing collisions.  However, we actually use CBC
> with ciphertext stealing (CTS), which handles the last two blocks
> specially, causing them to appear "flipped".  Thus, it's actually the
> second-to-last block which depends on the full plaintext.
> 
> This caused long filenames that differ only near the end of their
> plaintexts to, when observed without the key, point to the wrong inode
> and be undeletable.  For example, with ext4:
> 
>     # echo pass | e4crypt add_key -p 16 edir/
>     # seq -f "edir/abcdefghijklmnopqrstuvwxyz012345%.0f" 100000 | xargs touch
>     # find edir/ -type f | xargs stat -c %i | sort | uniq | wc -l
>     100000
>     # sync
>     # echo 3 > /proc/sys/vm/drop_caches
>     # keyctl new_session
>     # find edir/ -type f | xargs stat -c %i | sort | uniq | wc -l
>     2004
>     # rm -rf edir/
>     rm: cannot remove 'edir/_A7nNFi3rhkEQlJ6P,hdzluhODKOeWx5V': Structure needs cleaning
>     ...
> 
> To fix this, when presenting long encrypted filenames, encode the
> second-to-last block of ciphertext rather than the last 16 bytes.
> 
> Although it would be nice to solve this without depending on a specific
> encryption mode, that would mean doing a cryptographic hash like SHA-256
> which would be much less efficient.  This way is sufficient for now, and
> it's still compatible with encryption modes like HEH which are strong
> pseudorandom permutations.  Also, changing the presented names is still
> allowed at any time because they are only provided to allow applications
> to do things like delete encrypted directories.  They're not designed to
> be used to persistently identify files --- which would be hard to do
> anyway, given that they're encrypted after all.
> 
> For ease of backports, this patch only makes the minimal fix to both
> ext4 and f2fs.  It leaves ubifs as-is, since ubifs doesn't compare the
> ciphertext block yet.  Follow-on patches will clean things up properly
> and make the filesystems use a shared helper function.
> 
> Fixes: 5de0b4d0cd15 ("ext4 crypto: simplify and speed up filename encryption")
> Reported-by: Gwendal Grignou <gwendal@chromium.org>
> Cc: stable@vger.kernel.org
> Signed-off-by: Eric Biggers <ebiggers@google.com>

Thanks, applied.

						- Ted

[PATCH 3/6] fscrypt: introduce helper function for filename matching

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

Introduce a helper function fscrypt_match_name() which tests whether a
fscrypt_name matches a directory entry.  Also clean up the magic numbers
and document things properly.

Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 fs/crypto/fname.c               | 90 ++++++++++++++++++++++++++++++++---------
 fs/crypto/fscrypt_private.h     |  2 -
 include/linux/fscrypt_notsupp.h |  9 +++++
 include/linux/fscrypt_supp.h    | 78 +++++++++++++++++++++++++++++++++++
 4 files changed, 157 insertions(+), 22 deletions(-)

diff --git a/fs/crypto/fname.c b/fs/crypto/fname.c
index 932881f27f2f..b697c0cb8036 100644
--- a/fs/crypto/fname.c
+++ b/fs/crypto/fname.c
@@ -159,6 +159,8 @@ static int fname_decrypt(struct inode *inode,
 static const char *lookup_table =
 	"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+,";
 
+#define BASE64_CHARS(nbytes)	DIV_ROUND_UP((nbytes) * 4, 3)
+
 /**
  * digest_encode() -
  *
@@ -230,11 +232,14 @@ EXPORT_SYMBOL(fscrypt_fname_encrypted_size);
 int fscrypt_fname_alloc_buffer(const struct inode *inode,
 				u32 ilen, struct fscrypt_str *crypto_str)
 {
-	unsigned int olen = fscrypt_fname_encrypted_size(inode, ilen);
+	u32 olen = fscrypt_fname_encrypted_size(inode, ilen);
+	const u32 max_encoded_len =
+		max_t(u32, BASE64_CHARS(FSCRYPT_FNAME_MAX_UNDIGESTED_SIZE),
+		      1 + BASE64_CHARS(sizeof(struct fscrypt_digested_name)));
 
 	crypto_str->len = olen;
-	if (olen < FS_FNAME_CRYPTO_DIGEST_SIZE * 2)
-		olen = FS_FNAME_CRYPTO_DIGEST_SIZE * 2;
+	olen = max(olen, max_encoded_len);
+
 	/*
 	 * Allocated buffer can hold one more character to null-terminate the
 	 * string
@@ -266,6 +271,10 @@ EXPORT_SYMBOL(fscrypt_fname_free_buffer);
  *
  * The caller must have allocated sufficient memory for the @oname string.
  *
+ * If the key is available, we'll decrypt the disk name; otherwise, we'll encode
+ * it for presentation.  Short names are directly base64-encoded, while long
+ * names are encoded in fscrypt_digested_name format.
+ *
  * Return: 0 on success, -errno on failure
  */
 int fscrypt_fname_disk_to_usr(struct inode *inode,
@@ -274,7 +283,7 @@ int fscrypt_fname_disk_to_usr(struct inode *inode,
 			struct fscrypt_str *oname)
 {
 	const struct qstr qname = FSTR_TO_QSTR(iname);
-	char buf[24];
+	struct fscrypt_digested_name digested_name;
 
 	if (fscrypt_is_dot_dotdot(&qname)) {
 		oname->name[0] = '.';
@@ -289,20 +298,24 @@ int fscrypt_fname_disk_to_usr(struct inode *inode,
 	if (inode->i_crypt_info)
 		return fname_decrypt(inode, iname, oname);
 
-	if (iname->len <= FS_FNAME_CRYPTO_DIGEST_SIZE) {
+	if (iname->len <= FSCRYPT_FNAME_MAX_UNDIGESTED_SIZE) {
 		oname->len = digest_encode(iname->name, iname->len,
 					   oname->name);
 		return 0;
 	}
 	if (hash) {
-		memcpy(buf, &hash, 4);
-		memcpy(buf + 4, &minor_hash, 4);
+		digested_name.hash = hash;
+		digested_name.minor_hash = minor_hash;
 	} else {
-		memset(buf, 0, 8);
+		digested_name.hash = 0;
+		digested_name.minor_hash = 0;
 	}
-	memcpy(buf + 8, iname->name + ((iname->len - 17) & ~15), 16);
+	memcpy(digested_name.digest,
+	       FSCRYPT_FNAME_DIGEST(iname->name, iname->len),
+	       FSCRYPT_FNAME_DIGEST_SIZE);
 	oname->name[0] = '_';
-	oname->len = 1 + digest_encode(buf, 24, oname->name + 1);
+	oname->len = 1 + digest_encode((const char *)&digested_name,
+				       sizeof(digested_name), oname->name + 1);
 	return 0;
 }
 EXPORT_SYMBOL(fscrypt_fname_disk_to_usr);
@@ -336,10 +349,35 @@ int fscrypt_fname_usr_to_disk(struct inode *inode,
 }
 EXPORT_SYMBOL(fscrypt_fname_usr_to_disk);
 
+/**
+ * fscrypt_setup_filename() - prepare to search a possibly encrypted directory
+ * @dir: the directory that will be searched
+ * @iname: the user-provided filename being searched for
+ * @lookup: 1 if we're allowed to proceed without the key because it's
+ *	->lookup() or we're finding the dir_entry for deletion; 0 if we cannot
+ *	proceed without the key because we're going to create the dir_entry.
+ * @fname: the filename information to be filled in
+ *
+ * Given a user-provided filename @iname, this function sets @fname->disk_name
+ * to the name that would be stored in the on-disk directory entry, if possible.
+ * If the directory is unencrypted this is simply @iname.  Else, if we have the
+ * directory's encryption key, then @iname is the plaintext, so we encrypt it to
+ * get the disk_name.
+ *
+ * Else, for keyless @lookup operations, @iname is the presented ciphertext, so
+ * we decode it to get either the ciphertext disk_name (for short names) or the
+ * fscrypt_digested_name (for long names).  Non-@lookup operations will be
+ * impossible in this case, so we fail them with ENOKEY.
+ *
+ * If successful, fscrypt_free_filename() must be called later to clean up.
+ *
+ * Return: 0 on success, -errno on failure
+ */
 int fscrypt_setup_filename(struct inode *dir, const struct qstr *iname,
 			      int lookup, struct fscrypt_name *fname)
 {
-	int ret = 0, bigname = 0;
+	int ret;
+	int digested;
 
 	memset(fname, 0, sizeof(struct fscrypt_name));
 	fname->usr_fname = iname;
@@ -373,25 +411,37 @@ int fscrypt_setup_filename(struct inode *dir, const struct qstr *iname,
 	 * We don't have the key and we are doing a lookup; decode the
 	 * user-supplied name
 	 */
-	if (iname->name[0] == '_')
-		bigname = 1;
-	if ((bigname && (iname->len != 33)) || (!bigname && (iname->len > 43)))
-		return -ENOENT;
+	if (iname->name[0] == '_') {
+		if (iname->len !=
+		    1 + BASE64_CHARS(sizeof(struct fscrypt_digested_name)))
+			return -ENOENT;
+		digested = 1;
+	} else {
+		if (iname->len >
+		    BASE64_CHARS(FSCRYPT_FNAME_MAX_UNDIGESTED_SIZE))
+			return -ENOENT;
+		digested = 0;
+	}
 
-	fname->crypto_buf.name = kmalloc(32, GFP_KERNEL);
+	fname->crypto_buf.name =
+		kmalloc(max_t(size_t, FSCRYPT_FNAME_MAX_UNDIGESTED_SIZE,
+			      sizeof(struct fscrypt_digested_name)),
+			GFP_KERNEL);
 	if (fname->crypto_buf.name == NULL)
 		return -ENOMEM;
 
-	ret = digest_decode(iname->name + bigname, iname->len - bigname,
+	ret = digest_decode(iname->name + digested, iname->len - digested,
 				fname->crypto_buf.name);
 	if (ret < 0) {
 		ret = -ENOENT;
 		goto errout;
 	}
 	fname->crypto_buf.len = ret;
-	if (bigname) {
-		memcpy(&fname->hash, fname->crypto_buf.name, 4);
-		memcpy(&fname->minor_hash, fname->crypto_buf.name + 4, 4);
+	if (digested) {
+		const struct fscrypt_digested_name *n =
+			(const void *)fname->crypto_buf.name;
+		fname->hash = n->hash;
+		fname->minor_hash = n->minor_hash;
 	} else {
 		fname->disk_name.name = fname->crypto_buf.name;
 		fname->disk_name.len = fname->crypto_buf.len;
diff --git a/fs/crypto/fscrypt_private.h b/fs/crypto/fscrypt_private.h
index fdbb8af32eaf..b1fa2a0b08e9 100644
--- a/fs/crypto/fscrypt_private.h
+++ b/fs/crypto/fscrypt_private.h
@@ -13,8 +13,6 @@
 
 #include <linux/fscrypt_supp.h>
 
-#define FS_FNAME_CRYPTO_DIGEST_SIZE	32
-
 /* Encryption parameters */
 #define FS_XTS_TWEAK_SIZE		16
 #define FS_AES_128_ECB_KEY_SIZE		16
diff --git a/include/linux/fscrypt_notsupp.h b/include/linux/fscrypt_notsupp.h
index 3511ca798804..ec406aed2f2f 100644
--- a/include/linux/fscrypt_notsupp.h
+++ b/include/linux/fscrypt_notsupp.h
@@ -147,6 +147,15 @@ static inline int fscrypt_fname_usr_to_disk(struct inode *inode,
 	return -EOPNOTSUPP;
 }
 
+static inline bool fscrypt_match_name(const struct fscrypt_name *fname,
+				      const u8 *de_name, u32 de_name_len)
+{
+	/* Encryption support disabled; use standard comparison */
+	if (de_name_len != fname->disk_name.len)
+		return false;
+	return !memcmp(de_name, fname->disk_name.name, fname->disk_name.len);
+}
+
 /* bio.c */
 static inline void fscrypt_decrypt_bio_pages(struct fscrypt_ctx *ctx,
 					     struct bio *bio)
diff --git a/include/linux/fscrypt_supp.h b/include/linux/fscrypt_supp.h
index a140f47e9b27..e12c224a0d1e 100644
--- a/include/linux/fscrypt_supp.h
+++ b/include/linux/fscrypt_supp.h
@@ -57,6 +57,84 @@ extern int fscrypt_fname_disk_to_usr(struct inode *, u32, u32,
 extern int fscrypt_fname_usr_to_disk(struct inode *, const struct qstr *,
 			struct fscrypt_str *);
 
+#define FSCRYPT_FNAME_MAX_UNDIGESTED_SIZE	32
+
+/* Extracts the second-to-last ciphertext block; see explanation below */
+#define FSCRYPT_FNAME_DIGEST(name, len)	\
+	((name) + round_down((len) - FS_CRYPTO_BLOCK_SIZE - 1, \
+			     FS_CRYPTO_BLOCK_SIZE))
+
+#define FSCRYPT_FNAME_DIGEST_SIZE	FS_CRYPTO_BLOCK_SIZE
+
+/**
+ * fscrypt_digested_name - alternate identifier for an on-disk filename
+ *
+ * When userspace lists an encrypted directory without access to the key,
+ * filenames whose ciphertext is longer than FSCRYPT_FNAME_MAX_UNDIGESTED_SIZE
+ * bytes are shown in this abbreviated form (base64-encoded) rather than as the
+ * full ciphertext (base64-encoded).  This is necessary to allow supporting
+ * filenames up to NAME_MAX bytes, since base64 encoding expands the length.
+ *
+ * To make it possible for filesystems to still find the correct directory entry
+ * despite not knowing the full on-disk name, we encode any filesystem-specific
+ * 'hash' and/or 'minor_hash' which the filesystem may need for its lookups,
+ * followed by the second-to-last ciphertext block of the filename.  Due to the
+ * use of the CBC-CTS encryption mode, the second-to-last ciphertext block
+ * depends on the full plaintext.  (Note that ciphertext stealing causes the
+ * last two blocks to appear "flipped".)  This makes collisions very unlikely:
+ * just a 1 in 2^128 chance for two filenames to collide even if they share the
+ * same filesystem-specific hashes.
+ *
+ * This scheme isn't strictly immune to intentional collisions because it's
+ * basically like a CBC-MAC, which isn't secure on variable-length inputs.
+ * However, generating a CBC-MAC collision requires the ability to choose
+ * arbitrary ciphertext, which won't normally be possible with filename
+ * encryption since it would require write access to the raw disk.
+ *
+ * Taking a real cryptographic hash like SHA-256 over the full ciphertext would
+ * be better in theory but would be less efficient and more complicated to
+ * implement, especially since the filesystem would need to calculate it for
+ * each directory entry examined during a search.
+ */
+struct fscrypt_digested_name {
+	u32 hash;
+	u32 minor_hash;
+	u8 digest[FSCRYPT_FNAME_DIGEST_SIZE];
+};
+
+/**
+ * fscrypt_match_name() - test whether the given name matches a directory entry
+ * @fname: the name being searched for
+ * @de_name: the name from the directory entry
+ * @de_name_len: the length of @de_name in bytes
+ *
+ * Normally @fname->disk_name will be set, and in that case we simply compare
+ * that to the name stored in the directory entry.  The only exception is that
+ * if we don't have the key for an encrypted directory and a filename in it is
+ * very long, then we won't have the full disk_name and we'll instead need to
+ * match against the fscrypt_digested_name.
+ *
+ * Return: %true if the name matches, otherwise %false.
+ */
+static inline bool fscrypt_match_name(const struct fscrypt_name *fname,
+				      const u8 *de_name, u32 de_name_len)
+{
+	if (unlikely(!fname->disk_name.name)) {
+		const struct fscrypt_digested_name *n =
+			(const void *)fname->crypto_buf.name;
+		if (WARN_ON_ONCE(fname->usr_fname->name[0] != '_'))
+			return false;
+		if (de_name_len <= FSCRYPT_FNAME_MAX_UNDIGESTED_SIZE)
+			return false;
+		return !memcmp(FSCRYPT_FNAME_DIGEST(de_name, de_name_len),
+			       n->digest, FSCRYPT_FNAME_DIGEST_SIZE);
+	}
+
+	if (de_name_len != fname->disk_name.len)
+		return false;
+	return !memcmp(de_name, fname->disk_name.name, fname->disk_name.len);
+}
+
 /* bio.c */
 extern void fscrypt_decrypt_bio_pages(struct fscrypt_ctx *, struct bio *);
 extern void fscrypt_pullback_bio_page(struct page **, bool);
-- 
2.12.2.816.g2cccc81164-goog


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

Re: [PATCH 3/6] fscrypt: introduce helper function for filename matching

[Eric Biggers]

On Mon, Apr 24, 2017 at 10:00:10AM -0700, Eric Biggers wrote:
> +/**
> + * fscrypt_digested_name - alternate identifier for an on-disk filename
> + *
> + * When userspace lists an encrypted directory without access to the key,
> + * filenames whose ciphertext is longer than FSCRYPT_FNAME_MAX_UNDIGESTED_SIZE
> + * bytes are shown in this abbreviated form (base64-encoded) rather than as the
> + * full ciphertext (base64-encoded).  This is necessary to allow supporting
> + * filenames up to NAME_MAX bytes, since base64 encoding expands the length.
> + *
> + * To make it possible for filesystems to still find the correct directory entry
> + * despite not knowing the full on-disk name, we encode any filesystem-specific
> + * 'hash' and/or 'minor_hash' which the filesystem may need for its lookups,
> + * followed by the second-to-last ciphertext block of the filename.  Due to the
> + * use of the CBC-CTS encryption mode, the second-to-last ciphertext block
> + * depends on the full plaintext.  (Note that ciphertext stealing causes the
> + * last two blocks to appear "flipped".)  This makes collisions very unlikely:
> + * just a 1 in 2^128 chance for two filenames to collide even if they share the
> + * same filesystem-specific hashes.
> + *
> + * This scheme isn't strictly immune to intentional collisions because it's
> + * basically like a CBC-MAC, which isn't secure on variable-length inputs.
> + * However, generating a CBC-MAC collision requires the ability to choose
> + * arbitrary ciphertext, which won't normally be possible with filename
> + * encryption since it would require write access to the raw disk.
> + *
> + * Taking a real cryptographic hash like SHA-256 over the full ciphertext would
> + * be better in theory but would be less efficient and more complicated to
> + * implement, especially since the filesystem would need to calculate it for
> + * each directory entry examined during a search.
> + */

Hmm, after thinking about it more, my claim that creating intentional collisions
in digested names requires write access to the raw disk is incorrect.  Actually
it's pretty easy to create intentional collisions; it's sufficient to be able to
create filenames and view their corresponding ciphertexts.  So someone could
create undeletable files --- not necessarily the end of the world, but still
annoying.

Unfortunately, the same problem exists regardless of whether we use the
second-to-last ciphertext block, the last block, or the last two blocks; and
regardless of whether the length is encoded in the digested names.

My patches are still an improvement, of course, and for now I'll probably just
tweak the comment.  But to solve this for real I think we'd need to do one of
the following:

- Use a real cryptographic hash like SHA-256 of the ciphertext (which I think
  was actually the original design)
- Switch to an encryption mode like HEH (Hash-Encrypt-Hash) which is a
  pseudorandom permutation over the whole input
- Take some number (maybe 8 or 12) of bytes of ciphertext from each block;
  definitely a hack cryptographically, but it *might* be good enough
- Limit filenames in encrypted directories to (3*255)/4 bytes, so we can avoid
  this mess entirely

Another hack we maybe could do is remove the following sanity check in
ext4_unlink(), and in other filesystems if needed, which requires that the inode
number in a dir_entry being removed is as expected:

	retval = -EFSCORRUPTED;
	if (le32_to_cpu(de->inode) != inode->i_ino)
		goto end_unlink;

Then I think any colliding files could still be deleted; it just wouldn't happen
in the right order...

Eric

Re: [3/6] fscrypt: introduce helper function for filename matching

[Theodore Ts'o]

On Mon, Apr 24, 2017 at 10:00:10AM -0700, Eric Biggers wrote:
> From: Eric Biggers <ebiggers@google.com>
> 
> Introduce a helper function fscrypt_match_name() which tests whether a
> fscrypt_name matches a directory entry.  Also clean up the magic numbers
> and document things properly.
> 
> Signed-off-by: Eric Biggers <ebiggers@google.com>

Thanks, applied.

					- Ted

[PATCH 4/6] ext4: switch to using fscrypt_match_name()

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

Switch ext4 directory searches to use the fscrypt_match_name() helper
function.  There should be no functional change.

Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 fs/ext4/namei.c | 22 +++++-----------------
 1 file changed, 5 insertions(+), 17 deletions(-)

diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
index e6301b6933fc..6ecc3ae87a79 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -1245,29 +1245,17 @@ static void dx_insert_block(struct dx_frame *frame, u32 hash, ext4_lblk_t block)
 static inline int ext4_match(struct ext4_filename *fname,
 			     struct ext4_dir_entry_2 *de)
 {
-	const void *name = fname_name(fname);
-	u32 len = fname_len(fname);
+	struct fscrypt_name f;
 
 	if (!de->inode)
 		return 0;
 
+	f.usr_fname = fname->usr_fname;
+	f.disk_name = fname->disk_name;
 #ifdef CONFIG_EXT4_FS_ENCRYPTION
-	if (unlikely(!name)) {
-		if (fname->usr_fname->name[0] == '_') {
-			int ret;
-			if (de->name_len <= 32)
-				return 0;
-			ret = memcmp(de->name + ((de->name_len - 17) & ~15),
-				     fname->crypto_buf.name + 8, 16);
-			return (ret == 0) ? 1 : 0;
-		}
-		name = fname->crypto_buf.name;
-		len = fname->crypto_buf.len;
-	}
+	f.crypto_buf = fname->crypto_buf;
 #endif
-	if (de->name_len != len)
-		return 0;
-	return (memcmp(de->name, name, len) == 0) ? 1 : 0;
+	return fscrypt_match_name(&f, de->name, de->name_len);
 }
 
 /*
-- 
2.12.2.816.g2cccc81164-goog


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

Re: [4/6] ext4: switch to using fscrypt_match_name()

[Theodore Ts'o]

On Mon, Apr 24, 2017 at 10:00:11AM -0700, Eric Biggers wrote:
> From: Eric Biggers <ebiggers@google.com>
> 
> Switch ext4 directory searches to use the fscrypt_match_name() helper
> function.  There should be no functional change.
> 
> Signed-off-by: Eric Biggers <ebiggers@google.com>

Thanks, applied.

					- Ted

[PATCH 5/6] f2fs: switch to using fscrypt_match_name()

[Eric Biggers]

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>
---
 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


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

Re: [PATCH 5/6] f2fs: switch to using fscrypt_match_name()

[Jaegeuk Kim]

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

Re: [PATCH 5/6] f2fs: switch to using fscrypt_match_name()

[Richard Weinberger]

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.

-- 
Thanks,
//richard

Re: [PATCH 5/6] f2fs: switch to using fscrypt_match_name()

[Eric Biggers]

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

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

Re: [PATCH 5/6] f2fs: switch to using fscrypt_match_name()

[Richard Weinberger]

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

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

Re: [PATCH 5/6] f2fs: switch to using fscrypt_match_name()

[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.

Eric

Re: [PATCH 5/6] f2fs: switch to using fscrypt_match_name()

[Richard Weinberger]

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

Re: [5/6] f2fs: switch to using fscrypt_match_name()

[Theodore Ts'o]

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

[PATCH 6/6] ext4: clean up ext4_match() and callers

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

When ext4 encryption was originally merged, we were encrypting the
user-specified filename in ext4_match(), introducing a lot of additional
complexity into ext4_match() and its callers.  This has since been
changed to encrypt the filename earlier, so we can remove the gunk
that's no longer needed.  This more or less reverts ext4_search_dir()
and ext4_find_dest_de() to the way they were in the v4.0 kernel.

Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 fs/ext4/namei.c | 81 ++++++++++++++++++---------------------------------------
 1 file changed, 25 insertions(+), 56 deletions(-)

diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
index 6ecc3ae87a79..b6b8d073fdc4 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -1237,18 +1237,17 @@ static void dx_insert_block(struct dx_frame *frame, u32 hash, ext4_lblk_t block)
 }
 
 /*
- * NOTE! unlike strncmp, ext4_match returns 1 for success, 0 for failure.
+ * Test whether a directory entry matches the filename being searched for.
  *
- * `len <= EXT4_NAME_LEN' is guaranteed by caller.
- * `de != NULL' is guaranteed by caller.
+ * Return: %true if the directory entry matches, otherwise %false.
  */
-static inline int ext4_match(struct ext4_filename *fname,
-			     struct ext4_dir_entry_2 *de)
+static inline bool ext4_match(const struct ext4_filename *fname,
+			      const struct ext4_dir_entry_2 *de)
 {
 	struct fscrypt_name f;
 
 	if (!de->inode)
-		return 0;
+		return false;
 
 	f.usr_fname = fname->usr_fname;
 	f.disk_name = fname->disk_name;
@@ -1269,48 +1268,31 @@ int ext4_search_dir(struct buffer_head *bh, char *search_buf, int buf_size,
 	struct ext4_dir_entry_2 * de;
 	char * dlimit;
 	int de_len;
-	int res;
 
 	de = (struct ext4_dir_entry_2 *)search_buf;
 	dlimit = search_buf + buf_size;
 	while ((char *) de < dlimit) {
 		/* this code is executed quadratically often */
 		/* do minimal checking `by hand' */
-		if ((char *) de + de->name_len <= dlimit) {
-			res = ext4_match(fname, de);
-			if (res < 0) {
-				res = -1;
-				goto return_result;
-			}
-			if (res > 0) {
-				/* found a match - just to be sure, do
-				 * a full check */
-				if (ext4_check_dir_entry(dir, NULL, de, bh,
-						bh->b_data,
-						 bh->b_size, offset)) {
-					res = -1;
-					goto return_result;
-				}
-				*res_dir = de;
-				res = 1;
-				goto return_result;
-			}
-
+		if ((char *) de + de->name_len <= dlimit &&
+		    ext4_match(fname, de)) {
+			/* found a match - just to be sure, do
+			 * a full check */
+			if (ext4_check_dir_entry(dir, NULL, de, bh, bh->b_data,
+						 bh->b_size, offset))
+				return -1;
+			*res_dir = de;
+			return 1;
 		}
 		/* prevent looping on a bad block */
 		de_len = ext4_rec_len_from_disk(de->rec_len,
 						dir->i_sb->s_blocksize);
-		if (de_len <= 0) {
-			res = -1;
-			goto return_result;
-		}
+		if (de_len <= 0)
+			return -1;
 		offset += de_len;
 		de = (struct ext4_dir_entry_2 *) ((char *) de + de_len);
 	}
-
-	res = 0;
-return_result:
-	return res;
+	return 0;
 }
 
 static int is_dx_internal_node(struct inode *dir, ext4_lblk_t block,
@@ -1821,24 +1803,15 @@ int ext4_find_dest_de(struct inode *dir, struct inode *inode,
 	int nlen, rlen;
 	unsigned int offset = 0;
 	char *top;
-	int res;
 
 	de = (struct ext4_dir_entry_2 *)buf;
 	top = buf + buf_size - reclen;
 	while ((char *) de <= top) {
 		if (ext4_check_dir_entry(dir, NULL, de, bh,
-					 buf, buf_size, offset)) {
-			res = -EFSCORRUPTED;
-			goto return_result;
-		}
-		/* Provide crypto context and crypto buffer to ext4 match */
-		res = ext4_match(fname, de);
-		if (res < 0)
-			goto return_result;
-		if (res > 0) {
-			res = -EEXIST;
-			goto return_result;
-		}
+					 buf, buf_size, offset))
+			return -EFSCORRUPTED;
+		if (ext4_match(fname, de))
+			return -EEXIST;
 		nlen = EXT4_DIR_REC_LEN(de->name_len);
 		rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);
 		if ((de->inode ? rlen - nlen : rlen) >= reclen)
@@ -1846,15 +1819,11 @@ int ext4_find_dest_de(struct inode *dir, struct inode *inode,
 		de = (struct ext4_dir_entry_2 *)((char *)de + rlen);
 		offset += rlen;
 	}
-
 	if ((char *) de > top)
-		res = -ENOSPC;
-	else {
-		*dest_de = de;
-		res = 0;
-	}
-return_result:
-	return res;
+		return -ENOSPC;
+
+	*dest_de = de;
+	return 0;
 }
 
 int ext4_insert_dentry(struct inode *dir,
-- 
2.12.2.816.g2cccc81164-goog


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

Re: [6/6] ext4: clean up ext4_match() and callers

[Theodore Ts'o]

On Mon, Apr 24, 2017 at 10:00:13AM -0700, Eric Biggers wrote:
> From: Eric Biggers <ebiggers@google.com>
> 
> When ext4 encryption was originally merged, we were encrypting the
> user-specified filename in ext4_match(), introducing a lot of additional
> complexity into ext4_match() and its callers.  This has since been
> changed to encrypt the filename earlier, so we can remove the gunk
> that's no longer needed.  This more or less reverts ext4_search_dir()
> and ext4_find_dest_de() to the way they were in the v4.0 kernel.
> 
> Signed-off-by: Eric Biggers <ebiggers@google.com>

Thanks, applied.

						- Ted