[PATCH] fscrypt: use 32 bytes of encrypted filename

[PATCH] fscrypt: use 32 bytes of encrypted filename

[Gwendal Grignou]

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.

The drawback is the scrambled filenames change after applying the patch.
Consider an encrypted directory with:

ls -il
total 8
1177380 -rw-r--r--. 1 root root 0 Apr 18 12:10
system@framework@boot-telephony-common.art.crc
1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
system@framework@boot-telephony-common.oat.crc

Once the key is invalidated, without the patch, ls -li produces:
1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
_a1Psh01n8FdhC8s9pUywlAyFzlz7n6C3
1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
_wJS,0akq14ehC8s9pUywlAyFzlz7n6C3

Both files show with the same inode.

After the patch, the names are different, but the inode information is
now correct:
ls -li
1177380 -rw-r--r--. 1 root root 0 Apr 18 12:10
_a1Psh01n8FtxbeglW8BqhuthSUxMqh6cFKwz2nSJDXCIXMXOvfqLcD
1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
_wJS,0akq14eJcuQks7f2Vsg,zE0Jdz98FKwz2nSJDXCIXMXOvfqLcD

Tested only on ext4.

Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
---
Script to reproduce the error:

BASE_DIR="~/"
DIR="${BASE_DIR}/tmp"
# Create directory.
mkdir -p "${DIR}"
echo foobar | e4crypt add_key "${DIR}"
# Fill directory.
cd "${DIR}"
touch system@framework@boot-telephony-common.oat.crc
touch system@framework@boot-telephony-common.art.crc
cd ..
# Check files have different inode.
ls -il "${DIR}"
# Invalidate key
KEY="$(keyctl show | grep $(e4crypt get_policy "${DIR}" | cut -d ':' -f 2) | sed -ne 's/\(.*\) --al.*/\1/p')"
sync
keyctl invalidate "${KEY}"
echo 3 > /proc/sys/vm/drop_caches
# Once the key is invalidated, both files have the same inode:
ls -il "${DIR}"
if [ $(ls -i1 "${DIR}" | cut -d ' ' -f 1 | uniq | wc -l) -eq 1 ] ; then
  echo same inode!
fi
# if we try to remove the directory, we will get an error
# : Structure needs cleaning
# rm -rf "${DIR}"

 fs/crypto/fname.c | 20 +++++++++++++-------
 fs/ext4/namei.c   |  4 ++--
 2 files changed, 15 insertions(+), 9 deletions(-)

diff --git a/fs/crypto/fname.c b/fs/crypto/fname.c
index 80bb956e14e5..71ddc3eaa62d 100644
--- a/fs/crypto/fname.c
+++ b/fs/crypto/fname.c
@@ -274,7 +274,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[FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64)];
 
 	if (fscrypt_is_dot_dotdot(&qname)) {
 		oname->name[0] = '.';
@@ -295,14 +295,19 @@ int fscrypt_fname_disk_to_usr(struct inode *inode,
 		return 0;
 	}
 	if (hash) {
-		memcpy(buf, &hash, 4);
-		memcpy(buf + 4, &minor_hash, 4);
+		memcpy(buf, &hash, sizeof(u32));
+		memcpy(buf + 4, &minor_hash, sizeof(u32));
 	} else {
 		memset(buf, 0, 8);
 	}
-	memcpy(buf + 8, iname->name + iname->len - 16, 16);
+	memcpy(buf + sizeof(u64),
+	       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 + digest_encode(
+			buf,
+			FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64),
+			oname->name + 1);
 	return 0;
 }
 EXPORT_SYMBOL(fscrypt_fname_disk_to_usr);
@@ -375,10 +380,11 @@ int fscrypt_setup_filename(struct inode *dir, const struct qstr *iname,
 	 */
 	if (iname->name[0] == '_')
 		bigname = 1;
-	if ((bigname && (iname->len != 33)) || (!bigname && (iname->len > 43)))
+	if ((bigname && iname->len != 55) || (!bigname && (iname->len > 43)))
 		return -ENOENT;
 
-	fname->crypto_buf.name = kmalloc(32, GFP_KERNEL);
+	fname->crypto_buf.name = kmalloc(
+			FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64), GFP_KERNEL);
 	if (fname->crypto_buf.name == NULL)
 		return -ENOMEM;
 
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;
-			ret = memcmp(de->name + de->name_len - 16,
-				     fname->crypto_buf.name + 8, 16);
+			ret = memcmp(de->name + de->name_len - 32,
+				     fname->crypto_buf.name + 8, 32);
 			return (ret == 0) ? 1 : 0;
 		}
 		name = fname->crypto_buf.name;
-- 
2.12.2.816.g2cccc81164-goog

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

[Andreas Dilger]

[-- Attachment #1: Type: text/plain, Size: 6314 bytes --]

On Apr 18, 2017, at 3:06 PM, Gwendal Grignou <gwendal@chromium.org> wrote:
> Subject: [PATCH] fscrypt: use 32 bytes of encrypted filename

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

What is missing from the patch summary is: use the encrypted filename for
_what_?

> 
> It happens when two file names share the first 16k bytes and both have

"16k bytes" for the file names?  Presumably you don't mean "16KB", but
rather "16n" or "multiple of 16 bytes" would be more clear.

> length withn 16 * n + 13 and 16 * n + 16.
> 
> Instead use 32 bytes to build the filenames from encrypted data when
> directory is scrambled.
> 
> The drawback is the scrambled filenames change after applying the patch.
> Consider an encrypted directory with:
> 
> ls -il
> total 8
> 1177380 -rw-r--r--. 1 root root 0 Apr 18 12:10
> system@framework@boot-telephony-common.art.crc
> 1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
> system@framework@boot-telephony-common.oat.crc
> 
> Once the key is invalidated, without the patch, ls -li produces:
> 1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
> _a1Psh01n8FdhC8s9pUywlAyFzlz7n6C3
> 1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
> _wJS,0akq14ehC8s9pUywlAyFzlz7n6C3
> 
> Both files show with the same inode.
> 
> After the patch, the names are different, but the inode information is
> now correct:
> ls -li
> 1177380 -rw-r--r--. 1 root root 0 Apr 18 12:10
> _a1Psh01n8FtxbeglW8BqhuthSUxMqh6cFKwz2nSJDXCIXMXOvfqLcD
> 1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
> _wJS,0akq14eJcuQks7f2Vsg,zE0Jdz98FKwz2nSJDXCIXMXOvfqLcD

It isn't clear to me what the difference is here.  In the first case
(without patch) the last 21 characters of the filename are the same,
but the first 11 characters are still different, so it isn't clear why
that isn't enough to distinguish the files, and why checking the whole
filename isn't enough to properly determine the inode number?

In the second case (with patch) the last 22 characters are also the same.

> Tested only on ext4.
> 
> Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
> ---
> Script to reproduce the error:
> 
> BASE_DIR="~/"
> DIR="${BASE_DIR}/tmp"
> # Create directory.
> mkdir -p "${DIR}"
> echo foobar | e4crypt add_key "${DIR}"
> # Fill directory.
> cd "${DIR}"
> touch system@framework@boot-telephony-common.oat.crc
> touch system@framework@boot-telephony-common.art.crc
> cd ..
> # Check files have different inode.
> ls -il "${DIR}"
> # Invalidate key
> KEY="$(keyctl show | grep $(e4crypt get_policy "${DIR}" | cut -d ':' -f 2) | sed -ne 's/\(.*\) --al.*/\1/p')"
> sync
> keyctl invalidate "${KEY}"
> echo 3 > /proc/sys/vm/drop_caches
> # Once the key is invalidated, both files have the same inode:
> ls -il "${DIR}"
> if [ $(ls -i1 "${DIR}" | cut -d ' ' -f 1 | uniq | wc -l) -eq 1 ] ; then
>  echo same inode!
> fi
> # if we try to remove the directory, we will get an error
> # : Structure needs cleaning
> # rm -rf "${DIR}"
> 
> fs/crypto/fname.c | 20 +++++++++++++-------
> fs/ext4/namei.c   |  4 ++--
> 2 files changed, 15 insertions(+), 9 deletions(-)
> 
> diff --git a/fs/crypto/fname.c b/fs/crypto/fname.c
> index 80bb956e14e5..71ddc3eaa62d 100644
> --- a/fs/crypto/fname.c
> +++ b/fs/crypto/fname.c
> @@ -274,7 +274,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[FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64)];
> 
> 	if (fscrypt_is_dot_dotdot(&qname)) {
> 		oname->name[0] = '.';
> @@ -295,14 +295,19 @@ int fscrypt_fname_disk_to_usr(struct inode *inode,
> 		return 0;
> 	}
> 	if (hash) {
> -		memcpy(buf, &hash, 4);
> -		memcpy(buf + 4, &minor_hash, 4);
> +		memcpy(buf, &hash, sizeof(u32));
> +		memcpy(buf + 4, &minor_hash, sizeof(u32));

Should "4" be replaced with something here?  sizeof(u32), or something else?

> 	} else {
> 		memset(buf, 0, 8);

Likewise, should "8" be replaced with sizeof(u64) as it is with other changes?

> 	}
> -	memcpy(buf + 8, iname->name + iname->len - 16, 16);
> +	memcpy(buf + sizeof(u64),
> +	       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 + digest_encode(
> +			buf,
> +			FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64),
> +			oname->name + 1);
> 	return 0;
> }
> EXPORT_SYMBOL(fscrypt_fname_disk_to_usr);
> @@ -375,10 +380,11 @@ int fscrypt_setup_filename(struct inode *dir, const struct qstr *iname,
> 	 */
> 	if (iname->name[0] == '_')
> 		bigname = 1;
> -	if ((bigname && (iname->len != 33)) || (!bigname && (iname->len > 43)))
> +	if ((bigname && iname->len != 55) || (!bigname && (iname->len > 43)))

The "55" constant is no better than "33" in terms of clarity, nor is "43".
Having a (computed) constant for this would be more helpful, for example

   2 * sizeof(buf) + 1

or whatever.

> 		return -ENOENT;
> 
> -	fname->crypto_buf.name = kmalloc(32, GFP_KERNEL);
> +	fname->crypto_buf.name = kmalloc(
> +			FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64), GFP_KERNEL);
> 	if (fname->crypto_buf.name == NULL)
> 		return -ENOMEM;
> 
> 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;
> -			ret = memcmp(de->name + de->name_len - 16,
> -				     fname->crypto_buf.name + 8, 16);
> +			ret = memcmp(de->name + de->name_len - 32,
> +				     fname->crypto_buf.name + 8, 32);
> 			return (ret == 0) ? 1 : 0;

This could just be:

			return (ret == 0);

> 		}
> 		name = fname->crypto_buf.name;
>                 len = fname->crypto_buf.len;
>         }
> #endif
>         if (de->name_len != len)
>                 return 0;
>         return (memcmp(de->name, name, len) == 0) ? 1 : 0;


And similarly:

	return (memcmp(de->name, name, len) == 0);


Cheers, Andreas






[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

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

[Richard Weinberger]

On Tue, Apr 18, 2017 at 11:06 PM, Gwendal Grignou <gwendal@chromium.org> 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.
>
> The drawback is the scrambled filenames change after applying the patch.
> Consider an encrypted directory with:
>
> ls -il
> total 8
> 1177380 -rw-r--r--. 1 root root 0 Apr 18 12:10
> system@framework@boot-telephony-common.art.crc
> 1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
> system@framework@boot-telephony-common.oat.crc
>
> Once the key is invalidated, without the patch, ls -li produces:
> 1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
> _a1Psh01n8FdhC8s9pUywlAyFzlz7n6C3
> 1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
> _wJS,0akq14ehC8s9pUywlAyFzlz7n6C3
>
> Both files show with the same inode.
>
> After the patch, the names are different, but the inode information is
> now correct:
> ls -li
> 1177380 -rw-r--r--. 1 root root 0 Apr 18 12:10
> _a1Psh01n8FtxbeglW8BqhuthSUxMqh6cFKwz2nSJDXCIXMXOvfqLcD
> 1177379 -rw-r--r--. 1 root root 0 Apr 18 12:10
> _wJS,0akq14eJcuQks7f2Vsg,zE0Jdz98FKwz2nSJDXCIXMXOvfqLcD
>
> Tested only on ext4.

I hope you classify this patch as RFC then.
We'll have problems when you just develop and test for ext4. :-)

> Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
> ---
> Script to reproduce the error:
>
> BASE_DIR="~/"
> DIR="${BASE_DIR}/tmp"
> # Create directory.
> mkdir -p "${DIR}"
> echo foobar | e4crypt add_key "${DIR}"
> # Fill directory.
> cd "${DIR}"
> touch system@framework@boot-telephony-common.oat.crc
> touch system@framework@boot-telephony-common.art.crc
> cd ..
> # Check files have different inode.
> ls -il "${DIR}"
> # Invalidate key
> KEY="$(keyctl show | grep $(e4crypt get_policy "${DIR}" | cut -d ':' -f 2) | sed -ne 's/\(.*\) --al.*/\1/p')"
> sync
> keyctl invalidate "${KEY}"
> echo 3 > /proc/sys/vm/drop_caches
> # Once the key is invalidated, both files have the same inode:
> ls -il "${DIR}"
> if [ $(ls -i1 "${DIR}" | cut -d ' ' -f 1 | uniq | wc -l) -eq 1 ] ; then
>   echo same inode!
> fi
> # if we try to remove the directory, we will get an error
> # : Structure needs cleaning
> # rm -rf "${DIR}"
>
>  fs/crypto/fname.c | 20 +++++++++++++-------
>  fs/ext4/namei.c   |  4 ++--
>  2 files changed, 15 insertions(+), 9 deletions(-)
>
> diff --git a/fs/crypto/fname.c b/fs/crypto/fname.c
> index 80bb956e14e5..71ddc3eaa62d 100644
> --- a/fs/crypto/fname.c
> +++ b/fs/crypto/fname.c
> @@ -274,7 +274,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[FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64)];
>
>         if (fscrypt_is_dot_dotdot(&qname)) {
>                 oname->name[0] = '.';
> @@ -295,14 +295,19 @@ int fscrypt_fname_disk_to_usr(struct inode *inode,
>                 return 0;
>         }
>         if (hash) {
> -               memcpy(buf, &hash, 4);
> -               memcpy(buf + 4, &minor_hash, 4);
> +               memcpy(buf, &hash, sizeof(u32));
> +               memcpy(buf + 4, &minor_hash, sizeof(u32));
>         } else {
>                 memset(buf, 0, 8);
>         }
> -       memcpy(buf + 8, iname->name + iname->len - 16, 16);
> +       memcpy(buf + sizeof(u64),
> +              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 + digest_encode(
> +                       buf,
> +                       FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64),
> +                       oname->name + 1);
>         return 0;
>  }
>  EXPORT_SYMBOL(fscrypt_fname_disk_to_usr);
> @@ -375,10 +380,11 @@ int fscrypt_setup_filename(struct inode *dir, const struct qstr *iname,
>          */
>         if (iname->name[0] == '_')
>                 bigname = 1;
> -       if ((bigname && (iname->len != 33)) || (!bigname && (iname->len > 43)))
> +       if ((bigname && iname->len != 55) || (!bigname && (iname->len > 43)))
>                 return -ENOENT;
>
> -       fname->crypto_buf.name = kmalloc(32, GFP_KERNEL);
> +       fname->crypto_buf.name = kmalloc(
> +                       FS_FNAME_CRYPTO_DIGEST_SIZE + sizeof(u64), GFP_KERNEL);
>         if (fname->crypto_buf.name == NULL)
>                 return -ENOMEM;
>
> 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;
> -                       ret = memcmp(de->name + de->name_len - 16,
> -                                    fname->crypto_buf.name + 8, 16);
> +                       ret = memcmp(de->name + de->name_len - 32,
> +                                    fname->crypto_buf.name + 8, 32);
>                         return (ret == 0) ? 1 : 0;
>                 }
>                 name = fname->crypto_buf.name;

Can the code still be able to read filenames which have been encrypted
using the "old" scheme?

-- 
Thanks,
//richard

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

[Richard Weinberger]

On Wed, Apr 19, 2017 at 3:37 PM, Richard Weinberger
<richard.weinberger@gmail.com> wrote:
> Can the code still be able to read filenames which have been encrypted
> using the "old" scheme?

Bah, typing is hard.
Should be read: Will the code still be able to read ...

-- 
Thanks,
//richard

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

[Eric Biggers]

Hi Richard,

On Wed, Apr 19, 2017 at 03:37:42PM +0200, Richard Weinberger wrote:
> >
> > Tested only on ext4.
> 
> I hope you classify this patch as RFC then.
> We'll have problems when you just develop and test for ext4. :-)
> 

It's a little difficult for people to test stuff on UBIFS without a turn-key
solution like kvm-xfstests where they can just run something like
'kvm-xfstests -c ext4,f2fs,ubifs -g encrypt'.

I did post patches to add UBIFS support to xfstests and kvm-xfstests a few
months ago; maybe you're interested in taking them over and working to get them
merged?

> > 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;
> > -                       ret = memcmp(de->name + de->name_len - 16,
> > -                                    fname->crypto_buf.name + 8, 16);
> > +                       ret = memcmp(de->name + de->name_len - 32,
> > +                                    fname->crypto_buf.name + 8, 32);
> >                         return (ret == 0) ? 1 : 0;
> >                 }
> >                 name = fname->crypto_buf.name;
> 
> Can the code still be able to read filenames which have been encrypted
> using the "old" scheme?
> 

The patch only changes the presentation of long encrypted filenames when
accessed without the key.  It doesn't change how filenames are encrypted.

- Eric

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

[Richard Weinberger]

Eric,

Am 19.04.2017 um 19:09 schrieb Eric Biggers:
> Hi Richard,
> 
> On Wed, Apr 19, 2017 at 03:37:42PM +0200, Richard Weinberger wrote:
>>>
>>> Tested only on ext4.
>>
>> I hope you classify this patch as RFC then.
>> We'll have problems when you just develop and test for ext4. :-)
>>
> 
> It's a little difficult for people to test stuff on UBIFS without a turn-key
> solution like kvm-xfstests where they can just run something like
> 'kvm-xfstests -c ext4,f2fs,ubifs -g encrypt'.
> 
> I did post patches to add UBIFS support to xfstests and kvm-xfstests a few
> months ago; maybe you're interested in taking them over and working to get them
> merged?

I assigned this talk already to David.
He can tell what the status is.

>>> 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;
>>> -                       ret = memcmp(de->name + de->name_len - 16,
>>> -                                    fname->crypto_buf.name + 8, 16);
>>> +                       ret = memcmp(de->name + de->name_len - 32,
>>> +                                    fname->crypto_buf.name + 8, 32);
>>>                         return (ret == 0) ? 1 : 0;
>>>                 }
>>>                 name = fname->crypto_buf.name;
>>
>> Can the code still be able to read filenames which have been encrypted
>> using the "old" scheme?
>>
> 
> The patch only changes the presentation of long encrypted filenames when
> accessed without the key.  It doesn't change how filenames are encrypted.

Thanks for pointing this out.

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

[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: [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;
-
+not_match:
 		if (max_slots && max_len > *max_slots)
 			*max_slots = max_len;
 		max_len = 0;
-- 
2.11.0

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

[David Oberhollenzer]

On 04/19/2017 07:12 PM, Richard Weinberger wrote:
> Eric,
> 
> Am 19.04.2017 um 19:09 schrieb Eric Biggers:
>> Hi Richard,
>>
>> On Wed, Apr 19, 2017 at 03:37:42PM +0200, Richard Weinberger wrote:
>>>>
>>>> Tested only on ext4.
>>>
>>> I hope you classify this patch as RFC then.
>>> We'll have problems when you just develop and test for ext4. :-)
>>>
>>
>> It's a little difficult for people to test stuff on UBIFS without a turn-key
>> solution like kvm-xfstests where they can just run something like
>> 'kvm-xfstests -c ext4,f2fs,ubifs -g encrypt'.
>>
>> I did post patches to add UBIFS support to xfstests and kvm-xfstests a few
>> months ago; maybe you're interested in taking them over and working to get them
>> merged?
> 
> I assigned this talk already to David.
> He can tell what the status is.
> 
What I have right now is mostly similar to the previous patch for
xfstests-dev that was submitted to the mailing list. I haven't looked
into the xfstests-bld patch yet.


To sumarize what happend so far:

A while ago, I took a look at Erics xfstest patches and the similar
patch series from Dongsheng Yang. Based on those, I got the xfstests
running with UBIFS on nandsim inside a VM with fairly little changes.
AFAIR there were two tests failing, one of them being generic/129,
apparently because it exhausts the space on one of the UBI volumes, and
another one for which a fix was provided.

My work on the xfstests-dev patch was preempted by other projects, but I
briefly got back to it when an O_TMPFILE regression was reported on the
mtd mailing list. This should have been caught by generic/004 but
wasn't because the UBIFS error message didn't match the grep pattern
run on dmesg.

Other such cases may exist.

Today, after rebasing/porting my local changes to upstream xfstets-dev,
I ran the tests against on both Richards UBIFS tree and Linus' tree. On
both kernels I'm now getting 5 failing tests out of 94 (with one of
them being generic/129 again).


Further work on some of the test scripts is required.


David

Re: [f2fs-dev] [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

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: [f2fs-dev] [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

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

[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

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

[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