Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

[Eric Biggers]

+Cc linux-f2fs-devel@lists.sourceforge.net
+Cc linux-mtd@lists.infradead.org (for ubifs)

Hi Gwendal,

On Tue, Apr 18, 2017 at 02:06:42PM -0700, Gwendal Grignou wrote:
> If we use only 16 bytes, due to how CBC works, if the names have the
> same beginning, their last ciphertext block (16 bytes) may be identical.
> 
> It happens when two file names share the first 16k bytes and both have
> length withn 16 * n + 13 and 16 * n + 16.
> 
> Instead use 32 bytes to build the filenames from encrypted data when
> directory is scrambled.

Just some background for people who may be unfamiliar with what's going on here
(and it may be useful to include some of this in the patch description):

When accessing files without access to the key, userspace needs to operate on a
filename derived from the ciphertext filename, which contains arbitrary bytes. 

But since it's supported to use filenames up to FILENAME_MAX (255 bytes) in
length when using encryption, we can't always base-64 encode the filename, since
that may make it too long.

The way this is solved currently is that for filenames with ciphertext length
greater than 32 bytes, the filesystem provides an 8-byte "cookie" (split into
'hash' and 'minor_hash'), which along with the last 16 bytes of the filename
ciphertext is base-64 encoded into a fixed-length name.  The filesystem returns
this on readdir.  Then, when a lookup is done, the filesystem translates this
info back into a specific directory entry.

Since ext4 directory entries do not contain a hash field, ext4 relies only on
the 16 bytes of ciphertext to distinguish collisions within a directory block.
Unfortunately, this is broken because with the encryption mode used for
filenames (CTS), the ciphertext of the last 16-byte block depends only on the
plaintext up to and including the *second to last* block, not up to the last
block.  This causes long filenames that differ just near the end to collide.

We could fix this by using the second to last block of ciphertext rather than
the last one.  However, using the last *two* blocks as you're proposing should
be fine too.

Of course we could also hash the filename's ciphertext with SHA-256 or
something, but it's nice to take advantage of the encryption mode, and not have
to do yet another hash.

I am not too worried about changing the way encrypted filenames are presented,
since applications are not supposed to rely on this.  (Though we probably should
be doing something to catch broken applications, like encoding the filenames
slightly differently after each reboot...)

Strangely, f2fs and ubifs do not use the bytes from the filename at all when
trying to find a specific directory entry in this case.  So this patch doesn't
really affect them.  This seems unreliable; perhaps we should introduce a
function like "fscrypt_name_matches()" which all the filesystems could call?
Can any of the f2fs and ubifs developers explain why they don't look at any
bytes from the filename?

Anyway, a couple nits on this patch:

> +	oname->len = 1 + digest_encode(
> +			buf,
> +			FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64),
> +			oname->name + 1);
>  	return 0;
>  }

Use 'sizeof(buf)'

>  
> diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
> index c4a389a6027b..14b2a2335a32 100644
> --- a/fs/ext4/namei.c
> +++ b/fs/ext4/namei.c
> @@ -1257,8 +1257,8 @@ static inline int ext4_match(struct ext4_filename *fname,
>  			int ret;

>  			if (de->name_len < 16)
>  				return 0;

de->name_len < 32

(or replace 32 with FS_FNAME_CRYPTO_DIGEST_SIZE, here and below)

- Eric

Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

[Eric Biggers]

On Tue, Apr 18, 2017 at 04:01:36PM -0700, Eric Biggers wrote:
> 
> Strangely, f2fs and ubifs do not use the bytes from the filename at all when
> trying to find a specific directory entry in this case.  So this patch doesn't
> really affect them.  This seems unreliable; perhaps we should introduce a
> function like "fscrypt_name_matches()" which all the filesystems could call?
> Can any of the f2fs and ubifs developers explain why they don't look at any
> bytes from the filename?
> 

Just to give some ideas, here's an untested patch which does this and also
updates F2FS to start checking the filename.  UBIFS seemed more difficult so I
didn't touch it yet.

Of course, this would need to be split into a few different patches if we
actually wanted to go with it.

---

diff --git a/fs/crypto/fname.c b/fs/crypto/fname.c
index 37b49894c762..1fc19a265924 100644
--- a/fs/crypto/fname.c
+++ b/fs/crypto/fname.c
@@ -160,12 +160,14 @@ static const char *lookup_table =
 	"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+,";
 
 /**
- * digest_encode() -
+ * base64_encode() -
  *
- * Encodes the input digest using characters from the set [a-zA-Z0-9_+].
- * The encoded string is roughly 4/3 times the size of the input string.
+ * Encode the input data using characters from the set [A-Za-z0-9+,].
+ *
+ * Return: the length of the encoded string.  This will be 4/3 times the size of
+ *	   the input string, rounded up.
  */
-static int digest_encode(const char *src, int len, char *dst)
+static int base64_encode(const char *src, int len, char *dst)
 {
 	int i = 0, bits = 0, ac = 0;
 	char *cp = dst;
@@ -185,7 +187,9 @@ static int digest_encode(const char *src, int len, char *dst)
 	return cp - dst;
 }
 
-static int digest_decode(const char *src, int len, char *dst)
+#define BASE64_CHARS(nbytes)	DIV_ROUND_UP((nbytes) * 4, 3)
+
+static int base64_decode(const char *src, int len, char *dst)
 {
 	int i = 0, bits = 0, ac = 0;
 	const char *p;
@@ -274,7 +278,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];
+	char buf[8 + FS_FNAME_CRYPTO_DIGEST_SIZE];
 
 	if (fscrypt_is_dot_dotdot(&qname)) {
 		oname->name[0] = '.';
@@ -289,20 +293,35 @@ int fscrypt_fname_disk_to_usr(struct inode *inode,
 	if (inode->i_crypt_info)
 		return fname_decrypt(inode, iname, oname);
 
+	/* Key is unavailable.  Encode the name without decrypting it. */
+
 	if (iname->len <= FS_FNAME_CRYPTO_DIGEST_SIZE) {
-		oname->len = digest_encode(iname->name, iname->len,
+		/* Short name: base64-encode the ciphertext directly */
+		oname->len = base64_encode(iname->name, iname->len,
 					   oname->name);
 		return 0;
 	}
+
+	/*
+	 * Long name.  We can't simply base64-encode the full ciphertext, since
+	 * the resulting length may exceed NAME_MAX.  Instead, base64-encode a
+	 * filesystem-provided cookie ('hash' and 'minor_hash') followed by the
+	 * last two ciphertext blocks.  It's assumed this is sufficient to
+	 * identify the directory entry on ->lookup().  It's not actually
+	 * guaranteed, but with CBC or CBC-CTS mode encryption, it's good enough
+	 * since the unused blocks will affect the used ones.
+	 */
+
 	if (hash) {
 		memcpy(buf, &hash, 4);
 		memcpy(buf + 4, &minor_hash, 4);
 	} else {
 		memset(buf, 0, 8);
 	}
-	memcpy(buf + 8, iname->name + iname->len - 16, 16);
+	memcpy(buf + 8, iname->name + iname->len - FS_FNAME_CRYPTO_DIGEST_SIZE,
+	       FS_FNAME_CRYPTO_DIGEST_SIZE);
 	oname->name[0] = '_';
-	oname->len = 1 + digest_encode(buf, 24, oname->name + 1);
+	oname->len = 1 + base64_encode(buf, sizeof(buf), oname->name + 1);
 	return 0;
 }
 EXPORT_SYMBOL(fscrypt_fname_disk_to_usr);
@@ -373,17 +392,21 @@ 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] == '_')
+	if (iname->name[0] == '_') {
 		bigname = 1;
-	if ((bigname && (iname->len != 33)) || (!bigname && (iname->len > 43)))
+		if (iname->len !=
+		    BASE64_CHARS(1 + 8 + FS_FNAME_CRYPTO_DIGEST_SIZE))
+			return -ENOENT;
+	} else if (iname->len > BASE64_CHARS(FS_FNAME_CRYPTO_DIGEST_SIZE))
 		return -ENOENT;
 
-	fname->crypto_buf.name = kmalloc(32, GFP_KERNEL);
+	fname->crypto_buf.name = kmalloc(8 + FS_FNAME_CRYPTO_DIGEST_SIZE,
+					 GFP_KERNEL);
 	if (fname->crypto_buf.name == NULL)
 		return -ENOMEM;
 
-	ret = digest_decode(iname->name + bigname, iname->len - bigname,
-				fname->crypto_buf.name);
+	ret = base64_decode(iname->name + bigname, iname->len - bigname,
+			    fname->crypto_buf.name);
 	if (ret < 0) {
 		ret = -ENOENT;
 		goto errout;
diff --git a/fs/crypto/fscrypt_private.h b/fs/crypto/fscrypt_private.h
index e39696e64494..f1f15b84e02f 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/fs/ext4/namei.c b/fs/ext4/namei.c
index 07e5e1405771..d1618835de12 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -1237,37 +1237,23 @@ 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.
+ * Determine whether the filename being looked up matches the given dir_entry.
  *
- * `len <= EXT4_NAME_LEN' is guaranteed by caller.
- * `de != NULL' is guaranteed by caller.
+ * Return: true if the 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)
 {
-	const void *name = fname_name(fname);
-	u32 len = fname_len(fname);
+	const struct fscrypt_str *crypto_buf = NULL;
 
 	if (!de->inode)
 		return 0;
 
 #ifdef CONFIG_EXT4_FS_ENCRYPTION
-	if (unlikely(!name)) {
-		if (fname->usr_fname->name[0] == '_') {
-			int ret;
-			if (de->name_len < 16)
-				return 0;
-			ret = memcmp(de->name + de->name_len - 16,
-				     fname->crypto_buf.name + 8, 16);
-			return (ret == 0) ? 1 : 0;
-		}
-		name = fname->crypto_buf.name;
-		len = fname->crypto_buf.len;
-	}
+	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_dirent(fname->usr_fname, &fname->disk_name,
+				    crypto_buf, de->name, de->name_len);
 }
 
 /*
@@ -1289,12 +1275,7 @@ int ext4_search_dir(struct buffer_head *bh, char *search_buf, int buf_size,
 		/* 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) {
+			if (ext4_match(fname, de)) {
 				/* found a match - just to be sure, do
 				 * a full check */
 				if (ext4_check_dir_entry(dir, NULL, de, bh,
@@ -1843,11 +1824,7 @@ int ext4_find_dest_de(struct inode *dir, struct inode *inode,
 			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) {
+		if (ext4_match(fname, de)) {
 			res = -EEXIST;
 			goto return_result;
 		}
diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c
index 8d5c62b07b28..07b80d78a9f6 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,17 +128,10 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname,
 			continue;
 		}
 
-		/* encrypted case */
-		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))
+		if ((fname->hash == 0 ||
+		     fname->hash == le32_to_cpu(de->hash_code)) &&
+		    fscrypt_name_matches(fname, d->filename[bit_pos],
+					 le16_to_cpu(de->name_len)))
 			goto found;
 
 		if (max_slots && max_len > *max_slots)
diff --git a/include/linux/fscrypt_notsupp.h b/include/linux/fscrypt_notsupp.h
index 3511ca798804..4034976bea93 100644
--- a/include/linux/fscrypt_notsupp.h
+++ b/include/linux/fscrypt_notsupp.h
@@ -147,6 +147,24 @@ static inline int fscrypt_fname_usr_to_disk(struct inode *inode,
 	return -EOPNOTSUPP;
 }
 
+static inline bool fscrypt_match_dirent(const struct qstr *usr_fname,
+					const struct fscrypt_str *disk_name,
+					const struct fscrypt_str *crypto_buf,
+					const char *de_name, u32 de_name_len)
+{
+	/* Encryption support disabled; use standard comparison. */
+	if (de_name_len != disk_name->len)
+		return false;
+	return !memcmp(de_name, disk_name->name, disk_name->len);
+}
+
+static inline bool fscrypt_name_matches(const struct fscrypt_name *fname,
+					const char *de_name, u32 de_name_len)
+{
+	return fscrypt_match_dirent(fname->usr_fname, &fname->disk_name,
+				    &fname->crypto_buf, de_name, de_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..e3c9aa7209a1 100644
--- a/include/linux/fscrypt_supp.h
+++ b/include/linux/fscrypt_supp.h
@@ -57,6 +57,63 @@ 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 *);
 
+/*
+ * Number of bytes of ciphertext from the end of the filename which the
+ * filesystem includes when encoding long encrypted filenames for presentation
+ * to userspace without the key.
+ */
+#define FS_FNAME_CRYPTO_DIGEST_SIZE	(2 * FS_CRYPTO_BLOCK_SIZE)
+
+/**
+ * fscrypt_match_dirent() - does the directory entry match the name being looked up?
+ *
+ * This is like fscrypt_name_matches(), but for filesystems which don't use the
+ * fscrypt_name structure.  (We probably should make all filesystems do the same
+ * thing...)
+ */
+static inline bool fscrypt_match_dirent(const struct qstr *usr_fname,
+					const struct fscrypt_str *disk_name,
+					const struct fscrypt_str *crypto_buf,
+					const char *de_name, u32 de_name_len)
+{
+	if (unlikely(!disk_name->name)) {
+		if (WARN_ON_ONCE(usr_fname->name[0] != '_'))
+			return false;
+		if (de_name_len < FS_FNAME_CRYPTO_DIGEST_SIZE)
+			return false;
+		return !memcmp(de_name + de_name_len - FS_FNAME_CRYPTO_DIGEST_SIZE,
+			       crypto_buf->name + 8,
+			       FS_FNAME_CRYPTO_DIGEST_SIZE);
+	}
+
+	if (de_name_len != disk_name->len)
+		return false;
+	return !memcmp(de_name, disk_name->name, disk_name->len);
+}
+
+/**
+ * fscrypt_name_matches() - does the directory entry match the name being looked up?
+ * @fname: the name being looked up
+ * @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 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 the
+ * filename presented to userspace will only have the last
+ * FS_FNAME_CRYPTO_DIGEST_SIZE bytes of ciphertext encoded in it, so we can only
+ * compare that portion.  Note that despite this limit, due to the use of
+ * CBC-CTS encryption there should not be any collisions.
+ *
+ * Return: true if the name matches, otherwise false.
+ */
+static inline bool fscrypt_name_matches(const struct fscrypt_name *fname,
+					const char *de_name, u32 de_name_len)
+{
+	return fscrypt_match_dirent(fname->usr_fname, &fname->disk_name,
+				    &fname->crypto_buf, de_name, de_name_len);
+}
+
 /* bio.c */
 extern void fscrypt_decrypt_bio_pages(struct fscrypt_ctx *, struct bio *);
 extern void fscrypt_pullback_bio_page(struct page **, bool);

Re: [f2fs-dev] [PATCH] fscrypt: use 32 bytes of encrypted filename

[Jaegeuk Kim]

Hi Eric,

On 04/18, Eric Biggers wrote:
> On Tue, Apr 18, 2017 at 04:01:36PM -0700, Eric Biggers wrote:
> > 
> > Strangely, f2fs and ubifs do not use the bytes from the filename at all when
> > trying to find a specific directory entry in this case.  So this patch doesn't
> > really affect them.  This seems unreliable; perhaps we should introduce a
> > function like "fscrypt_name_matches()" which all the filesystems could call?
> > Can any of the f2fs and ubifs developers explain why they don't look at any
> > bytes from the filename?
> > 

The fscrypt_setup_filename sets fname->hash in the bigname case, but doesn't
give fname->disk_name. If it's not such the bigname case, we check its name
since fname->hash is zero.

> Just to give some ideas, here's an untested patch which does this and also
> updates F2FS to start checking the filename.  UBIFS seemed more difficult so I
> didn't touch it yet.
> 
> Of course, this would need to be split into a few different patches if we
> actually wanted to go with it.
> 
> ---

...

> diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c
> index 8d5c62b07b28..07b80d78a9f6 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,17 +128,10 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname,
>  			continue;
>  		}
>  
> -		/* encrypted case */
> -		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))
> +		if ((fname->hash == 0 ||
> +		     fname->hash == le32_to_cpu(de->hash_code)) &&
> +		    fscrypt_name_matches(fname, d->filename[bit_pos],
> +					 le16_to_cpu(de->name_len)))

BTW, this slips checking namehash?

Thanks,

>  			goto found;
>  
>  		if (max_slots && max_len > *max_slots)
> diff --git a/include/linux/fscrypt_notsupp.h b/include/linux/fscrypt_notsupp.h
> index 3511ca798804..4034976bea93 100644
> --- a/include/linux/fscrypt_notsupp.h
> +++ b/include/linux/fscrypt_notsupp.h
> @@ -147,6 +147,24 @@ static inline int fscrypt_fname_usr_to_disk(struct inode *inode,
>  	return -EOPNOTSUPP;
>  }
>  
> +static inline bool fscrypt_match_dirent(const struct qstr *usr_fname,
> +					const struct fscrypt_str *disk_name,
> +					const struct fscrypt_str *crypto_buf,
> +					const char *de_name, u32 de_name_len)
> +{
> +	/* Encryption support disabled; use standard comparison. */
> +	if (de_name_len != disk_name->len)
> +		return false;
> +	return !memcmp(de_name, disk_name->name, disk_name->len);
> +}
> +
> +static inline bool fscrypt_name_matches(const struct fscrypt_name *fname,
> +					const char *de_name, u32 de_name_len)
> +{
> +	return fscrypt_match_dirent(fname->usr_fname, &fname->disk_name,
> +				    &fname->crypto_buf, de_name, de_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..e3c9aa7209a1 100644
> --- a/include/linux/fscrypt_supp.h
> +++ b/include/linux/fscrypt_supp.h
> @@ -57,6 +57,63 @@ 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 *);
>  
> +/*
> + * Number of bytes of ciphertext from the end of the filename which the
> + * filesystem includes when encoding long encrypted filenames for presentation
> + * to userspace without the key.
> + */
> +#define FS_FNAME_CRYPTO_DIGEST_SIZE	(2 * FS_CRYPTO_BLOCK_SIZE)
> +
> +/**
> + * fscrypt_match_dirent() - does the directory entry match the name being looked up?
> + *
> + * This is like fscrypt_name_matches(), but for filesystems which don't use the
> + * fscrypt_name structure.  (We probably should make all filesystems do the same
> + * thing...)
> + */
> +static inline bool fscrypt_match_dirent(const struct qstr *usr_fname,
> +					const struct fscrypt_str *disk_name,
> +					const struct fscrypt_str *crypto_buf,
> +					const char *de_name, u32 de_name_len)
> +{
> +	if (unlikely(!disk_name->name)) {
> +		if (WARN_ON_ONCE(usr_fname->name[0] != '_'))
> +			return false;
> +		if (de_name_len < FS_FNAME_CRYPTO_DIGEST_SIZE)
> +			return false;
> +		return !memcmp(de_name + de_name_len - FS_FNAME_CRYPTO_DIGEST_SIZE,
> +			       crypto_buf->name + 8,
> +			       FS_FNAME_CRYPTO_DIGEST_SIZE);
> +	}
> +
> +	if (de_name_len != disk_name->len)
> +		return false;
> +	return !memcmp(de_name, disk_name->name, disk_name->len);
> +}
> +
> +/**
> + * fscrypt_name_matches() - does the directory entry match the name being looked up?
> + * @fname: the name being looked up
> + * @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 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 the
> + * filename presented to userspace will only have the last
> + * FS_FNAME_CRYPTO_DIGEST_SIZE bytes of ciphertext encoded in it, so we can only
> + * compare that portion.  Note that despite this limit, due to the use of
> + * CBC-CTS encryption there should not be any collisions.
> + *
> + * Return: true if the name matches, otherwise false.
> + */
> +static inline bool fscrypt_name_matches(const struct fscrypt_name *fname,
> +					const char *de_name, u32 de_name_len)
> +{
> +	return fscrypt_match_dirent(fname->usr_fname, &fname->disk_name,
> +				    &fname->crypto_buf, de_name, de_name_len);
> +}
> +
>  /* bio.c */
>  extern void fscrypt_decrypt_bio_pages(struct fscrypt_ctx *, struct bio *);
>  extern void fscrypt_pullback_bio_page(struct page **, bool);
> 
> ------------------------------------------------------------------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> _______________________________________________
> Linux-f2fs-devel mailing list
> Linux-f2fs-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

Re: [f2fs-dev] [PATCH] fscrypt: use 32 bytes of encrypted filename

[Eric Biggers]

On Tue, Apr 18, 2017 at 06:42:09PM -0700, Jaegeuk Kim wrote:
> Hi Eric,
> 
> On 04/18, Eric Biggers wrote:
> > On Tue, Apr 18, 2017 at 04:01:36PM -0700, Eric Biggers wrote:
> > > 
> > > Strangely, f2fs and ubifs do not use the bytes from the filename at all when
> > > trying to find a specific directory entry in this case.  So this patch doesn't
> > > really affect them.  This seems unreliable; perhaps we should introduce a
> > > function like "fscrypt_name_matches()" which all the filesystems could call?
> > > Can any of the f2fs and ubifs developers explain why they don't look at any
> > > bytes from the filename?
> > > 
> 
> The fscrypt_setup_filename sets fname->hash in the bigname case, but doesn't
> give fname->disk_name. If it's not such the bigname case, we check its name
> since fname->hash is zero.
> 

Yes, that's what it does now.  The question is, in the "bigname" case why
doesn't f2fs check the 16 bytes of ciphertext in fname->crypto_buf too?  f2fs
doesn't even use 'minor_hash'; it can't possibly be the case that there are
never any collisions of a 32-bit hash in a directory, can it?

I actually tested it, and it definitely happens if you put a lot of files in an
encrypted directory on f2fs.  An example with 100000 files:

# 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

So when I tried accessing the encrypted directory without the key, two dentries
showed the same inode, due to a hash collision.

Actually, checking the last 16 bytes of ciphertext currently wouldn't even help
for those filenames since it's all the same, as they share a long common prefix:

# ls -1  edir | head -n 4
_++09VCAAAAgsQQf6Q5YgLgoO4f3PPSfb
_++1UWDAAAAgsQQf6Q5YgLgoO4f3PPSfb
_++2HAAAAAAgsQQf6Q5YgLgoO4f3PPSfb
_++4UxBAAAAgsQQf6Q5YgLgoO4f3PPSfb

But that's the bug, since the last two AES blocks are swapped when using
ciphertext stealing.  We should at least be using the second-to-last block in
which case we'd see:

# ls -1  edir | head -n 4
_++09VCAAAAw9VONwQEXOVv3RR,kOAKwB
_++1UWDAAAAAHDi7c3QZxbiltjOo1m0,F
_++2HAAAAAAAfd1Vx0oC31SmhzYpaYfwz
_++4UxBAAAAwZxcWjzORdAef50FB9sKY4

(In either case there are still a few A's at the beginning since f2fs doesn't
set 'minor_hash'.  That's okay, but only if collisions are ruled out by other
means.)

> > -		/* encrypted case */
> > -		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))
> > +		if ((fname->hash == 0 ||
> > +		     fname->hash == le32_to_cpu(de->hash_code)) &&
> > +		    fscrypt_name_matches(fname, d->filename[bit_pos],
> > +					 le16_to_cpu(de->name_len)))
> 
> BTW, this slips checking namehash?
> 

Yes that's a mistake.  Actually it seems that 'namehash' is the same as
'fname->hash' when 'fname->hash' is nonzero, so the code should just be:

	if (de->hash_code == namehash &&
	    fscrypt_name_matches(fname, d->filename[bit_pos],
				 le16_to_cpu(de->name_len)))
		goto found;

- Eric

Re: [f2fs-dev] [PATCH] fscrypt: use 32 bytes of encrypted filename

[Jaegeuk Kim]

On 04/18, Eric Biggers wrote:
> On Tue, Apr 18, 2017 at 06:42:09PM -0700, Jaegeuk Kim wrote:
> > Hi Eric,
> > 
> > On 04/18, Eric Biggers wrote:
> > > On Tue, Apr 18, 2017 at 04:01:36PM -0700, Eric Biggers wrote:
> > > > 
> > > > Strangely, f2fs and ubifs do not use the bytes from the filename at all when
> > > > trying to find a specific directory entry in this case.  So this patch doesn't
> > > > really affect them.  This seems unreliable; perhaps we should introduce a
> > > > function like "fscrypt_name_matches()" which all the filesystems could call?
> > > > Can any of the f2fs and ubifs developers explain why they don't look at any
> > > > bytes from the filename?
> > > > 
> > 
> > The fscrypt_setup_filename sets fname->hash in the bigname case, but doesn't
> > give fname->disk_name. If it's not such the bigname case, we check its name
> > since fname->hash is zero.
> > 
> 
> Yes, that's what it does now.  The question is, in the "bigname" case why
> doesn't f2fs check the 16 bytes of ciphertext in fname->crypto_buf too?  f2fs
> doesn't even use 'minor_hash'; it can't possibly be the case that there are
> never any collisions of a 32-bit hash in a directory, can it?
> 
> I actually tested it, and it definitely happens if you put a lot of files in an
> encrypted directory on f2fs.  An example with 100000 files:
> 
> # 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
> 
> So when I tried accessing the encrypted directory without the key, two dentries
> showed the same inode, due to a hash collision.

Thank you for sharing more details. I could reproduce this issue and reach out
to what you mentioned. In order to resolve this, I wrote a patch for f2fs first
to act like ext4 for easy backports. Then, I expect a global fscrypt function
is easily able to clean them up.

Thanks,

>From 63ca24a64fb1625dac9740a2183fd8966388e185 Mon Sep 17 00:00:00 2001
From: Jaegeuk Kim <jaegeuk@kernel.org>
Date: Wed, 19 Apr 2017 10:49:21 -0700
Subject: [PATCH] f2fs: check entire encrypted bigname when finding a dentry

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>
---
 fs/f2fs/dir.c | 28 +++++++++++++++++++---------
 1 file changed, 19 insertions(+), 9 deletions(-)

diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c
index c143dffcae6e..007c3b4adc85 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;

Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

[Eric Biggers]

Hi Jaegeuk,

On Wed, Apr 19, 2017 at 01:44:48PM -0700, Jaegeuk Kim wrote:
> 
> Thank you for sharing more details. I could reproduce this issue and reach out
> to what you mentioned. In order to resolve this, I wrote a patch for f2fs first
> to act like ext4 for easy backports. Then, I expect a global fscrypt function
> is easily able to clean them up.
[...]
> @@ -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:

I agree with this approach, but I don't think it's ever the case that
fname->usr_fname->name[0] != '_'.  (Yes, ext4 checks it, but I think it's
unneeded there too.)  And if it was, it doesn't make sense to modify the 'name'
that is passed in.

In any case, I guess that unless there are other ideas we can do these patches:

1.) f2fs patch to start checking the name, as above
2.) patch to start encoding last 32 bytes of the name (or second-to-last CTS
    block, I haven't decided yet) rather than last 16 bytes, changing
    fs/crypto/, fs/ext4/, and fs/f2fs/
3.) cleanup patches to introduce helper function and switch ext4 and f2fs to it

(1) and (2) will be backported.

UBIFS can be changed to use the helper function later if needed.  It's not as
important for it to be backported there since UBIFS does the "double hashing",
and UBIFS encryption was just added in 4.10 anyway.

I can try to put together the full series when I have time.  It probably would
make sense for it to go through the fscrypt tree, given the dependencies.

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] fscrypt: use 32 bytes of encrypted filename

[Gwendal Grignou]

>
> In any case, I guess that unless there are other ideas we can do these patches:
>
> 1.) f2fs patch to start checking the name, as above
> 2.) patch to start encoding last 32 bytes of the name (or second-to-last CTS
>     block, I haven't decided yet) rather than last 16 bytes, changing
>     fs/crypto/, fs/ext4/, and fs/f2fs/

Using second-to-last CTS block is CTS-CBC specific. If we use another
method to encode filename (I am thinking of HEH,
http://www.mail-archive.com/linux-crypto@vger.kernel.org/msg21826.html)
that may not work anymore.
We don't have to use the last 32 bytes: using for instance the last 24
should be good enough, the escape rate will be 1/2^64 instead 1/2^128.

Gwendal.

> 3.) cleanup patches to introduce helper function and switch ext4 and f2fs to it
>
> (1) and (2) will be backported.
>
> UBIFS can be changed to use the helper function later if needed.  It's not as
> important for it to be backported there since UBIFS does the "double hashing",
> and UBIFS encryption was just added in 4.10 anyway.
>
> I can try to put together the full series when I have time.  It probably would
> make sense for it to go through the fscrypt tree, given the dependencies.
>
> Eric

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

Re: [f2fs-dev] [PATCH] fscrypt: use 32 bytes of encrypted filename

[Eric Biggers]

Hi Gwendal,

On Fri, Apr 21, 2017 at 10:21:16AM -0700, Gwendal Grignou wrote:
> >
> > In any case, I guess that unless there are other ideas we can do these patches:
> >
> > 1.) f2fs patch to start checking the name, as above
> > 2.) patch to start encoding last 32 bytes of the name (or second-to-last CTS
> >     block, I haven't decided yet) rather than last 16 bytes, changing
> >     fs/crypto/, fs/ext4/, and fs/f2fs/
> 
> Using second-to-last CTS block is CTS-CBC specific. If we use another
> method to encode filename (I am thinking of HEH,
> http://www.mail-archive.com/linux-crypto@vger.kernel.org/msg21826.html)
> that may not work anymore.
> We don't have to use the last 32 bytes: using for instance the last 24
> should be good enough, the escape rate will be 1/2^64 instead 1/2^128.
> 

The thing is, even using the last N bytes is depending on the encryption
algorithm.  The only way to make it work for arbitrary algorithms would be to
use a cryptographic hash like SHA-256 --- which actually seems to have been the
original design, but apparently it got changed at some point.  (I guess so that
hashes wouldn't have to be computed in so many places, and taking advantage of
the encryption should be sufficient.)

HEH is not a problem because it's a strong pseudorandom permutation, so any
choice of bytes from the ciphertext is equally good for it.

We can always change this later if different algorithms are added, or even make
different algorithms choose different bytes.

So I think I'm leaning towards making it use the second-to-last block, rather
than the last 32 bytes.

Eric

Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

[Jaegeuk Kim]

Hi Eric,

On 04/21, Eric Biggers wrote:
> Hi Jaegeuk,
> 
> On Wed, Apr 19, 2017 at 01:44:48PM -0700, Jaegeuk Kim wrote:
> > 
> > Thank you for sharing more details. I could reproduce this issue and reach out
> > to what you mentioned. In order to resolve this, I wrote a patch for f2fs first
> > to act like ext4 for easy backports. Then, I expect a global fscrypt function
> > is easily able to clean them up.
> [...]
> > @@ -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:
> 
> I agree with this approach, but I don't think it's ever the case that
> fname->usr_fname->name[0] != '_'.  (Yes, ext4 checks it, but I think it's
> unneeded there too.)  And if it was, it doesn't make sense to modify the 'name'
> that is passed in.

Agreed, and actually I tried to sync ext4 as much as possible for further work
like 2.) and 3.) below. ;)

> In any case, I guess that unless there are other ideas we can do these patches:
> 
> 1.) f2fs patch to start checking the name, as above
> 2.) patch to start encoding last 32 bytes of the name (or second-to-last CTS
>     block, I haven't decided yet) rather than last 16 bytes, changing
>     fs/crypto/, fs/ext4/, and fs/f2fs/
> 3.) cleanup patches to introduce helper function and switch ext4 and f2fs to it

IMO, it'd better to do 3.) followed by 2.), since 2.) already needs to change
fs/crypto which does not give much backporting effort.

> (1) and (2) will be backported.
> 
> UBIFS can be changed to use the helper function later if needed.  It's not as
> important for it to be backported there since UBIFS does the "double hashing",
> and UBIFS encryption was just added in 4.10 anyway.
> 
> I can try to put together the full series when I have time.  It probably would
> make sense for it to go through the fscrypt tree, given the dependencies.

I found one issue in my patch and modified it in f2fs tree [1]. Given next merge
window probable starting next week, let me upstream this modified one first
through f2fs. Then, you can see it in 4.12-rc1 two weeks later, so fscrypt
patches can be easily integrated after then. If you have any concern, I'm also
okay to push this patch through fscrypt. Let me know.

[1] https://git.kernel.org/pub/scm/linux/kernel/git/jaegeuk/f2fs.git/commit/?h=dev-test&id=1585cfbbb269be6a112e0629a52123c0f9eaf4fa

Thanks,

> 
> Eric

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

Re: [f2fs-dev] [PATCH] fscrypt: use 32 bytes of encrypted filename

[Eric Biggers]

Hi Jaegeuk,

On Fri, Apr 21, 2017 at 10:35:03AM -0700, Jaegeuk Kim wrote:
> 
> > In any case, I guess that unless there are other ideas we can do these patches:
> > 
> > 1.) f2fs patch to start checking the name, as above
> > 2.) patch to start encoding last 32 bytes of the name (or second-to-last CTS
> >     block, I haven't decided yet) rather than last 16 bytes, changing
> >     fs/crypto/, fs/ext4/, and fs/f2fs/
> > 3.) cleanup patches to introduce helper function and switch ext4 and f2fs to it
> 
> IMO, it'd better to do 3.) followed by 2.), since 2.) already needs to change
> fs/crypto which does not give much backporting effort.
> 

That would be ideal, but unfortunately the main users of filesystem encryption
are using old kernel versions which don't have fs/crypto/, usually 4.4 at
latest.  So it would be nice for it to be easier to backport the "use different
bytes from the encrypted filename" change to 4.4-stable, as I've been doing for
some of the other filesystem encryption fixes.  And people do need it, it seems,
as it causes real problems like undeletable files; Gwendal is even already
trying to merge a fix into some Chrome OS kernel.

> 
> I found one issue in my patch and modified it in f2fs tree [1]. Given next merge
> window probable starting next week, let me upstream this modified one first
> through f2fs. Then, you can see it in 4.12-rc1 two weeks later, so fscrypt
> patches can be easily integrated after then. If you have any concern, I'm also
> okay to push this patch through fscrypt. Let me know.
> 
> [1] https://git.kernel.org/pub/scm/linux/kernel/git/jaegeuk/f2fs.git/commit/?h=dev-test&id=1585cfbbb269be6a112e0629a52123c0f9eaf4fa
> 

I think the series through fscrypt makes more sense, though if I don't have it
ready soon please go ahead and take the f2fs portion through the f2fs tree.

Thanks!

- Eric

Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

[Gwendal Grignou]

On Tue, Apr 18, 2017 at 5:10 PM, Eric Biggers <ebiggers3@gmail.com> wrote:
> On Tue, Apr 18, 2017 at 04:01:36PM -0700, Eric Biggers wrote:
>>
>> Strangely, f2fs and ubifs do not use the bytes from the filename at all when
>> trying to find a specific directory entry in this case.  So this patch doesn't
>> really affect them.  This seems unreliable; perhaps we should introduce a
>> function like "fscrypt_name_matches()" which all the filesystems could call?
>> Can any of the f2fs and ubifs developers explain why they don't look at any
>> bytes from the filename?
>>
>
> Just to give some ideas, here's an untested patch which does this and also
> updates F2FS to start checking the filename.  UBIFS seemed more difficult so I
> didn't touch it yet.
Verified your better patch - modified to work on 4.9 - is working with ext4,
More comment inline.
>
> Of course, this would need to be split into a few different patches if we
> actually wanted to go with it.
>
> ---
>
> diff --git a/fs/crypto/fname.c b/fs/crypto/fname.c
> index 37b49894c762..1fc19a265924 100644
> --- a/fs/crypto/fname.c
> +++ b/fs/crypto/fname.c
> @@ -160,12 +160,14 @@ static const char *lookup_table =
>         "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+,";
>
>  /**
> - * digest_encode() -
> + * base64_encode() -
I noticed there are another implementation of base64 in the kernel,
ceph_armor (although it uses the regular '/' instead of ',' for the
64th character).
Looking at RFC 3548 (https://tools.ietf.org/html/rfc3548#page-6) "Base
64 Encoding with URL and Filename Safe Alphabet", the 63th and 64th
character should be '-_' instead of '+,'.
Rename base64_filename_encode to be precise.

>   *
> - * Encodes the input digest using characters from the set [a-zA-Z0-9_+].
> - * The encoded string is roughly 4/3 times the size of the input string.
> + * Encode the input data using characters from the set [A-Za-z0-9+,].
> + *
> + * Return: the length of the encoded string.  This will be 4/3 times the size of
> + *        the input string, rounded up.
>   */
> -static int digest_encode(const char *src, int len, char *dst)
> +static int base64_encode(const char *src, int len, char *dst)
>  {
>         int i = 0, bits = 0, ac = 0;
>         char *cp = dst;
> @@ -185,7 +187,9 @@ static int digest_encode(const char *src, int len, char *dst)
>         return cp - dst;
>  }
>
> -static int digest_decode(const char *src, int len, char *dst)
> +#define BASE64_CHARS(nbytes)   DIV_ROUND_UP((nbytes) * 4, 3)
> +
> +static int base64_decode(const char *src, int len, char *dst)
>  {
>         int i = 0, bits = 0, ac = 0;
>         const char *p;
> @@ -274,7 +278,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];
> +       char buf[8 + FS_FNAME_CRYPTO_DIGEST_SIZE];
Given buf is now internal to fscrypto, we should define a structure:
struct fscrypto_bigname {
   u32 hash;
   u32 minor_hash;
   u8   digest[FS_FNAME_CRYPTO_DIGEST_SIZE];
}
>
>         if (fscrypt_is_dot_dotdot(&qname)) {
>                 oname->name[0] = '.';
> @@ -289,20 +293,35 @@ int fscrypt_fname_disk_to_usr(struct inode *inode,
>         if (inode->i_crypt_info)
>                 return fname_decrypt(inode, iname, oname);
>
> +       /* Key is unavailable.  Encode the name without decrypting it. */
> +
>         if (iname->len <= FS_FNAME_CRYPTO_DIGEST_SIZE) {
> -               oname->len = digest_encode(iname->name, iname->len,
> +               /* Short name: base64-encode the ciphertext directly */
> +               oname->len = base64_encode(iname->name, iname->len,
>                                            oname->name);
>                 return 0;
>         }
> +
> +       /*
> +        * Long name.  We can't simply base64-encode the full ciphertext, since
> +        * the resulting length may exceed NAME_MAX.  Instead, base64-encode a
> +        * filesystem-provided cookie ('hash' and 'minor_hash') followed by the
> +        * last two ciphertext blocks.  It's assumed this is sufficient to
> +        * identify the directory entry on ->lookup().  It's not actually
> +        * guaranteed, but with CBC or CBC-CTS mode encryption, it's good enough
> +        * since the unused blocks will affect the used ones.
> +        */
> +
>         if (hash) {
>                 memcpy(buf, &hash, 4);
>                 memcpy(buf + 4, &minor_hash, 4);
>         } else {
>                 memset(buf, 0, 8);
>         }
> -       memcpy(buf + 8, iname->name + iname->len - 16, 16);
> +       memcpy(buf + 8, iname->name + iname->len - FS_FNAME_CRYPTO_DIGEST_SIZE,
> +              FS_FNAME_CRYPTO_DIGEST_SIZE);
>         oname->name[0] = '_';
> -       oname->len = 1 + digest_encode(buf, 24, oname->name + 1);
> +       oname->len = 1 + base64_encode(buf, sizeof(buf), oname->name + 1);
>         return 0;
>  }
>  EXPORT_SYMBOL(fscrypt_fname_disk_to_usr);
> @@ -373,17 +392,21 @@ 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] == '_')
> +       if (iname->name[0] == '_') {
>                 bigname = 1;
> -       if ((bigname && (iname->len != 33)) || (!bigname && (iname->len > 43)))
> +               if (iname->len !=
> +                   BASE64_CHARS(1 + 8 + FS_FNAME_CRYPTO_DIGEST_SIZE))
becomes 1 + sizeof(struct fscrypto_bigname)
> +                       return -ENOENT;
> +       } else if (iname->len > BASE64_CHARS(FS_FNAME_CRYPTO_DIGEST_SIZE))
>                 return -ENOENT;
>
> -       fname->crypto_buf.name = kmalloc(32, GFP_KERNEL);
> +       fname->crypto_buf.name = kmalloc(8 + FS_FNAME_CRYPTO_DIGEST_SIZE,
max(32, sizeof(struct fscrypto_bigname)) to be precise,
> +                                        GFP_KERNEL);
>         if (fname->crypto_buf.name == NULL)
>                 return -ENOMEM;
>
> -       ret = digest_decode(iname->name + bigname, iname->len - bigname,
> -                               fname->crypto_buf.name);
> +       ret = base64_decode(iname->name + bigname, iname->len - bigname,
> +                           fname->crypto_buf.name);
>         if (ret < 0) {
>                 ret = -ENOENT;
>                 goto errout;
> diff --git a/fs/crypto/fscrypt_private.h b/fs/crypto/fscrypt_private.h
> index e39696e64494..f1f15b84e02f 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/fs/ext4/namei.c b/fs/ext4/namei.c
> index 07e5e1405771..d1618835de12 100644
> --- a/fs/ext4/namei.c
> +++ b/fs/ext4/namei.c
> @@ -1237,37 +1237,23 @@ 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.
> + * Determine whether the filename being looked up matches the given dir_entry.
>   *
> - * `len <= EXT4_NAME_LEN' is guaranteed by caller.
> - * `de != NULL' is guaranteed by caller.
> + * Return: true if the 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)
>  {
> -       const void *name = fname_name(fname);
> -       u32 len = fname_len(fname);
> +       const struct fscrypt_str *crypto_buf = NULL;
>
>         if (!de->inode)
>                 return 0;
>
>  #ifdef CONFIG_EXT4_FS_ENCRYPTION
> -       if (unlikely(!name)) {
> -               if (fname->usr_fname->name[0] == '_') {
> -                       int ret;
> -                       if (de->name_len < 16)
> -                               return 0;
> -                       ret = memcmp(de->name + de->name_len - 16,
> -                                    fname->crypto_buf.name + 8, 16);
> -                       return (ret == 0) ? 1 : 0;
> -               }
> -               name = fname->crypto_buf.name;
> -               len = fname->crypto_buf.len;
> -       }
> +       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_dirent(fname->usr_fname, &fname->disk_name,
> +                                   crypto_buf, de->name, de->name_len);
>  }
>
>  /*
> @@ -1289,12 +1275,7 @@ int ext4_search_dir(struct buffer_head *bh, char *search_buf, int buf_size,
>                 /* 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) {
> +                       if (ext4_match(fname, de)) {
>                                 /* found a match - just to be sure, do
>                                  * a full check */
>                                 if (ext4_check_dir_entry(dir, NULL, de, bh,
> @@ -1843,11 +1824,7 @@ int ext4_find_dest_de(struct inode *dir, struct inode *inode,
>                         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) {
> +               if (ext4_match(fname, de)) {
>                         res = -EEXIST;
>                         goto return_result;
>                 }
> diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c
> index 8d5c62b07b28..07b80d78a9f6 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,17 +128,10 @@ struct f2fs_dir_entry *find_target_dentry(struct fscrypt_name *fname,
>                         continue;
>                 }
>
> -               /* encrypted case */
> -               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))
> +               if ((fname->hash == 0 ||
> +                    fname->hash == le32_to_cpu(de->hash_code)) &&
> +                   fscrypt_name_matches(fname, d->filename[bit_pos],
> +                                        le16_to_cpu(de->name_len)))
>                         goto found;
>
>                 if (max_slots && max_len > *max_slots)
> diff --git a/include/linux/fscrypt_notsupp.h b/include/linux/fscrypt_notsupp.h
> index 3511ca798804..4034976bea93 100644
> --- a/include/linux/fscrypt_notsupp.h
> +++ b/include/linux/fscrypt_notsupp.h
> @@ -147,6 +147,24 @@ static inline int fscrypt_fname_usr_to_disk(struct inode *inode,
>         return -EOPNOTSUPP;
>  }
>
> +static inline bool fscrypt_match_dirent(const struct qstr *usr_fname,
> +                                       const struct fscrypt_str *disk_name,
> +                                       const struct fscrypt_str *crypto_buf,
> +                                       const char *de_name, u32 de_name_len)
> +{
> +       /* Encryption support disabled; use standard comparison. */
> +       if (de_name_len != disk_name->len)
> +               return false;
> +       return !memcmp(de_name, disk_name->name, disk_name->len);
> +}
> +
> +static inline bool fscrypt_name_matches(const struct fscrypt_name *fname,
> +                                       const char *de_name, u32 de_name_len)
> +{
> +       return fscrypt_match_dirent(fname->usr_fname, &fname->disk_name,
> +                                   &fname->crypto_buf, de_name, de_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..e3c9aa7209a1 100644
> --- a/include/linux/fscrypt_supp.h
> +++ b/include/linux/fscrypt_supp.h
> @@ -57,6 +57,63 @@ 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 *);
>
> +/*
> + * Number of bytes of ciphertext from the end of the filename which the
> + * filesystem includes when encoding long encrypted filenames for presentation
> + * to userspace without the key.
> + */
> +#define FS_FNAME_CRYPTO_DIGEST_SIZE    (2 * FS_CRYPTO_BLOCK_SIZE)
> +
> +/**
> + * fscrypt_match_dirent() - does the directory entry match the name being looked up?
> + *
> + * This is like fscrypt_name_matches(), but for filesystems which don't use the
> + * fscrypt_name structure.  (We probably should make all filesystems do the same
> + * thing...)
> + */
> +static inline bool fscrypt_match_dirent(const struct qstr *usr_fname,
> +                                       const struct fscrypt_str *disk_name,
> +                                       const struct fscrypt_str *crypto_buf,
> +                                       const char *de_name, u32 de_name_len)
> +{
> +       if (unlikely(!disk_name->name)) {
> +               if (WARN_ON_ONCE(usr_fname->name[0] != '_'))
> +                       return false;
> +               if (de_name_len < FS_FNAME_CRYPTO_DIGEST_SIZE)
> +                       return false;
> +               return !memcmp(de_name + de_name_len - FS_FNAME_CRYPTO_DIGEST_SIZE,
> +                              crypto_buf->name + 8,/buf[
> +                              FS_FNAME_CRYPTO_DIGEST_SIZE);
> +       }
> +
> +       if (de_name_len != disk_name->len)
> +               return false;
> +       return !memcmp(de_name, disk_name->name, disk_name->len);
> +}
> +
> +/**
> + * fscrypt_name_matches() - does the directory entry match the name being looked up?
> + * @fname: the name being looked up
> + * @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 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 the
> + * filename presented to userspace will only have the last
> + * FS_FNAME_CRYPTO_DIGEST_SIZE bytes of ciphertext encoded in it, so we can only
> + * compare that portion.  Note that despite this limit, due to the use of
> + * CBC-CTS encryption there should not be any collisions.
> + *
> + * Return: true if the name matches, otherwise false.
> + */
> +static inline bool fscrypt_name_matches(const struct fscrypt_name *fname,
> +                                       const char *de_name, u32 de_name_len)
> +{
> +       return fscrypt_match_dirent(fname->usr_fname, &fname->disk_name,
> +                                   &fname->crypto_buf, de_name, de_name_len);
> +}
> +
>  /* bio.c */
>  extern void fscrypt_decrypt_bio_pages(struct fscrypt_ctx *, struct bio *);
>  extern void fscrypt_pullback_bio_page(struct page **, bool);

Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

[Richard Weinberger]

Eric,

On Wed, Apr 19, 2017 at 1:01 AM, Eric Biggers <ebiggers3@gmail.com> wrote:
> +Cc linux-f2fs-devel@lists.sourceforge.net
> +Cc linux-mtd@lists.infradead.org (for ubifs)
>
> Hi Gwendal,
>
> On Tue, Apr 18, 2017 at 02:06:42PM -0700, Gwendal Grignou wrote:
>> If we use only 16 bytes, due to how CBC works, if the names have the
>> same beginning, their last ciphertext block (16 bytes) may be identical.
>>
>> It happens when two file names share the first 16k bytes and both have
>> length withn 16 * n + 13 and 16 * n + 16.
>>
>> Instead use 32 bytes to build the filenames from encrypted data when
>> directory is scrambled.
>
> Just some background for people who may be unfamiliar with what's going on here
> (and it may be useful to include some of this in the patch description):
>
> When accessing files without access to the key, userspace needs to operate on a
> filename derived from the ciphertext filename, which contains arbitrary bytes.
>
> But since it's supported to use filenames up to FILENAME_MAX (255 bytes) in
> length when using encryption, we can't always base-64 encode the filename, since
> that may make it too long.
>
> The way this is solved currently is that for filenames with ciphertext length
> greater than 32 bytes, the filesystem provides an 8-byte "cookie" (split into
> 'hash' and 'minor_hash'), which along with the last 16 bytes of the filename
> ciphertext is base-64 encoded into a fixed-length name.  The filesystem returns
> this on readdir.  Then, when a lookup is done, the filesystem translates this
> info back into a specific directory entry.
>
> Since ext4 directory entries do not contain a hash field, ext4 relies only on
> the 16 bytes of ciphertext to distinguish collisions within a directory block.
> Unfortunately, this is broken because with the encryption mode used for
> filenames (CTS), the ciphertext of the last 16-byte block depends only on the
> plaintext up to and including the *second to last* block, not up to the last
> block.  This causes long filenames that differ just near the end to collide.
>
> We could fix this by using the second to last block of ciphertext rather than
> the last one.  However, using the last *two* blocks as you're proposing should
> be fine too.
>
> Of course we could also hash the filename's ciphertext with SHA-256 or
> something, but it's nice to take advantage of the encryption mode, and not have
> to do yet another hash.
>
> I am not too worried about changing the way encrypted filenames are presented,
> since applications are not supposed to rely on this.  (Though we probably should
> be doing something to catch broken applications, like encoding the filenames
> slightly differently after each reboot...)
>
> Strangely, f2fs and ubifs do not use the bytes from the filename at all when
> trying to find a specific directory entry in this case.  So this patch doesn't
> really affect them.  This seems unreliable; perhaps we should introduce a
> function like "fscrypt_name_matches()" which all the filesystems could call?
> Can any of the f2fs and ubifs developers explain why they don't look at any
> bytes from the filename?

Not sure if I understand you correctly, but for long filenames UBIFS
does a lookup
by hash/cookie, not by filename.

-- 
Thanks,
//richard

Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

[Eric Biggers]

On Wed, Apr 19, 2017 at 03:40:13PM +0200, Richard Weinberger wrote:
> > Strangely, f2fs and ubifs do not use the bytes from the filename at all when
> > trying to find a specific directory entry in this case.  So this patch doesn't
> > really affect them.  This seems unreliable; perhaps we should introduce a
> > function like "fscrypt_name_matches()" which all the filesystems could call?
> > Can any of the f2fs and ubifs developers explain why they don't look at any
> > bytes from the filename?
> 
> Not sure if I understand you correctly, but for long filenames UBIFS
> does a lookup
> by hash/cookie, not by filename.
> 

Well, like I said to Jaegeuk for F2FS, that's what the code does, but _why_?
Like F2FS, it's probably not the case that the hash is sufficient to reliably
identify a directory entry.  Granted, UBIFS does it a lot better than F2FS since
UBIFS uses two 32-bit hashes rather than just one, but it seems the second hash
may be neither necessary nor sufficient to identify a specific directory entry,
and it should be looking at the bytes of ciphertext from the filename instead,
like what ext4 does.  (Provided that is fixed to account for how CTS mode
encryption works.)

- Eric

Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

[Richard Weinberger]

Am 19.04.2017 um 19:16 schrieb Eric Biggers:
> On Wed, Apr 19, 2017 at 03:40:13PM +0200, Richard Weinberger wrote:
>>> Strangely, f2fs and ubifs do not use the bytes from the filename at all when
>>> trying to find a specific directory entry in this case.  So this patch doesn't
>>> really affect them.  This seems unreliable; perhaps we should introduce a
>>> function like "fscrypt_name_matches()" which all the filesystems could call?
>>> Can any of the f2fs and ubifs developers explain why they don't look at any
>>> bytes from the filename?
>>
>> Not sure if I understand you correctly, but for long filenames UBIFS
>> does a lookup
>> by hash/cookie, not by filename.
>>
> 
> Well, like I said to Jaegeuk for F2FS, that's what the code does, but _why_?
> Like F2FS, it's probably not the case that the hash is sufficient to reliably
> identify a directory entry.  Granted, UBIFS does it a lot better than F2FS since
> UBIFS uses two 32-bit hashes rather than just one, but it seems the second hash
> may be neither necessary nor sufficient to identify a specific directory entry,
> and it should be looking at the bytes of ciphertext from the filename instead,
> like what ext4 does.  (Provided that is fixed to account for how CTS mode
> encryption works.)

Let me dig into this, maybe I made a boo boo.
The idea was looking up by the filename hash and resolving
possible collisions using the secondary hash.

Thanks,
//richard

Re: [PATCH] fscrypt: use 32 bytes of encrypted filename

[Richard Weinberger]

Eric,

On Wed, Apr 19, 2017 at 7:21 PM, Richard Weinberger <richard@nod.at> wrote:
>> Well, like I said to Jaegeuk for F2FS, that's what the code does, but _why_?
>> Like F2FS, it's probably not the case that the hash is sufficient to reliably
>> identify a directory entry.  Granted, UBIFS does it a lot better than F2FS since
>> UBIFS uses two 32-bit hashes rather than just one, but it seems the second hash
>> may be neither necessary nor sufficient to identify a specific directory entry,
>> and it should be looking at the bytes of ciphertext from the filename instead,
>> like what ext4 does.  (Provided that is fixed to account for how CTS mode
>> encryption works.)
>
> Let me dig into this, maybe I made a boo boo.
> The idea was looking up by the filename hash and resolving
> possible collisions using the secondary hash.

In ubifs_lookup() we handle two cases:
1. lookup of a bigname, both fscrypt_name->hash and ->minor_hash are valid.
    ->hash is r5(diskname) and ->minor_hash is the secondary hash, AKA cookie.
   UBIFS fed this hashes in ubifs_readdir() to fscrypt.
2. lookup of a non-bigname, in this case we compute r5(diskname) and
use the diskname
    itself for lookups.

So, in case 1 we avoid collisions by using a 64bit key and in case 2 by using
the 32bit key plus a linear search and memcmp() of diskname.

-- 
Thanks,
//richard