| blob | 3eff77f549bdb9b99e4f37d4ce74da4a51286d98 |
1 ext4 crypto: simplify and speed up filename encryption
3 Avoid using SHA-1 when calculating the user-visible filename when the
4 encryption key is available, and avoid decrypting lots of filenames
5 when searching for a directory entry in a directory block.
7 Change-Id: If4655f144784978ba0305b597bfa1c8d7bb69e63
8 Signed-off-by: Theodore Ts'o <tytso@mit.edu>
9 ---
10 fs/ext4/crypto_fname.c | 268 +++++++++++++++++++++++++------------------------
11 fs/ext4/dir.c | 2 +-
12 fs/ext4/ext4.h | 9 +-
13 fs/ext4/namei.c | 72 ++-----------
14 fs/ext4/symlink.c | 2 +-
15 5 files changed, 149 insertions(+), 204 deletions(-)
17 diff --git a/fs/ext4/crypto_fname.c b/fs/ext4/crypto_fname.c
18 index ca2f594..7a877e6 100644
19 --- a/fs/ext4/crypto_fname.c
20 +++ b/fs/ext4/crypto_fname.c
21 @@ -198,106 +198,57 @@ static int ext4_fname_decrypt(struct ext4_fname_crypto_ctx *ctx,
22 return oname->len;
23 }
25 +static const char *lookup_table =
26 + "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+,";
27 +
28 /**
29 * ext4_fname_encode_digest() -
30 *
31 * Encodes the input digest using characters from the set [a-zA-Z0-9_+].
32 * The encoded string is roughly 4/3 times the size of the input string.
33 */
34 -int ext4_fname_encode_digest(char *dst, char *src, u32 len)
35 +static int digest_encode(const char *src, int len, char *dst)
36 {
37 - static const char *lookup_table =
38 - "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_+";
39 - u32 current_chunk, num_chunks, i;
40 - char tmp_buf[3];
41 - u32 c0, c1, c2, c3;
42 -
43 - current_chunk = 0;
44 - num_chunks = len/3;
45 - for (i = 0; i < num_chunks; i++) {
46 - c0 = src[3*i] & 0x3f;
47 - c1 = (((src[3*i]>>6)&0x3) | ((src[3*i+1] & 0xf)<<2)) & 0x3f;
48 - c2 = (((src[3*i+1]>>4)&0xf) | ((src[3*i+2] & 0x3)<<4)) & 0x3f;
49 - c3 = (src[3*i+2]>>2) & 0x3f;
50 - dst[4*i] = lookup_table[c0];
51 - dst[4*i+1] = lookup_table[c1];
52 - dst[4*i+2] = lookup_table[c2];
53 - dst[4*i+3] = lookup_table[c3];
54 - }
55 - if (i*3 < len) {
56 - memset(tmp_buf, 0, 3);
57 - memcpy(tmp_buf, &src[3*i], len-3*i);
58 - c0 = tmp_buf[0] & 0x3f;
59 - c1 = (((tmp_buf[0]>>6)&0x3) | ((tmp_buf[1] & 0xf)<<2)) & 0x3f;
60 - c2 = (((tmp_buf[1]>>4)&0xf) | ((tmp_buf[2] & 0x3)<<4)) & 0x3f;
61 - c3 = (tmp_buf[2]>>2) & 0x3f;
62 - dst[4*i] = lookup_table[c0];
63 - dst[4*i+1] = lookup_table[c1];
64 - dst[4*i+2] = lookup_table[c2];
65 - dst[4*i+3] = lookup_table[c3];
66 + int i = 0, bits = 0, ac = 0;
67 + char *cp = dst;
68 +
69 + while (i < len) {
70 + ac += (((unsigned char) src[i]) << bits);
71 + bits += 8;
72 + do {
73 + *cp++ = lookup_table[ac & 0x3f];
74 + ac >>= 6;
75 + bits -= 6;
76 + } while (bits >= 6);
77 i++;
78 }
79 - return (i * 4);
80 + if (bits)
81 + *cp++ = lookup_table[ac & 0x3f];
82 + return cp - dst;
83 }
85 -/**
86 - * ext4_fname_hash() -
87 - *
88 - * This function computes the hash of the input filename, and sets the output
89 - * buffer to the *encoded* digest. It returns the length of the digest as its
90 - * return value. Errors are returned as negative numbers. We trust the caller
91 - * to allocate sufficient memory to oname string.
92 - */
93 -static int ext4_fname_hash(struct ext4_fname_crypto_ctx *ctx,
94 - const struct ext4_str *iname,
95 - struct ext4_str *oname)
96 +static int digest_decode(const char *src, int len, char *dst)
97 {
98 - struct scatterlist sg;
99 - struct hash_desc desc = {
100 - .tfm = (struct crypto_hash *)ctx->htfm,
101 - .flags = CRYPTO_TFM_REQ_MAY_SLEEP
102 - };
103 - int res = 0;
104 -
105 - if (iname->len <= EXT4_FNAME_CRYPTO_DIGEST_SIZE) {
106 - res = ext4_fname_encode_digest(oname->name, iname->name,
107 - iname->len);
108 - oname->len = res;
109 - return res;
110 - }
111 -
112 - sg_init_one(&sg, iname->name, iname->len);
113 - res = crypto_hash_init(&desc);
114 - if (res) {
115 - printk(KERN_ERR
116 - "%s: Error initializing crypto hash; res = [%d]\n",
117 - __func__, res);
118 - goto out;
119 - }
120 - res = crypto_hash_update(&desc, &sg, iname->len);
121 - if (res) {
122 - printk(KERN_ERR
123 - "%s: Error updating crypto hash; res = [%d]\n",
124 - __func__, res);
125 - goto out;
126 - }
127 - res = crypto_hash_final(&desc,
128 - &oname->name[EXT4_FNAME_CRYPTO_DIGEST_SIZE]);
129 - if (res) {
130 - printk(KERN_ERR
131 - "%s: Error finalizing crypto hash; res = [%d]\n",
132 - __func__, res);
133 - goto out;
134 + int i = 0, bits = 0, ac = 0;
135 + const char *p;
136 + char *cp = dst;
137 +
138 + while (i < len) {
139 + p = strchr(lookup_table, src[i]);
140 + if (p == NULL || src[i] == 0)
141 + return -2;
142 + ac += (p - lookup_table) << bits;
143 + bits += 6;
144 + if (bits >= 8) {
145 + *cp++ = ac & 0xff;
146 + ac >>= 8;
147 + bits -= 8;
148 + }
149 + i++;
150 }
151 - /* Encode the digest as a printable string--this will increase the
152 - * size of the digest */
153 - oname->name[0] = 'I';
154 - res = ext4_fname_encode_digest(oname->name+1,
155 - &oname->name[EXT4_FNAME_CRYPTO_DIGEST_SIZE],
156 - EXT4_FNAME_CRYPTO_DIGEST_SIZE) + 1;
157 - oname->len = res;
158 -out:
159 - return res;
160 + if (ac)
161 + return -1;
162 + return cp - dst;
163 }
165 /**
166 @@ -571,9 +522,13 @@ void ext4_fname_crypto_free_buffer(struct ext4_str *crypto_str)
167 * ext4_fname_disk_to_usr() - converts a filename from disk space to user space
168 */
169 int _ext4_fname_disk_to_usr(struct ext4_fname_crypto_ctx *ctx,
170 - const struct ext4_str *iname,
171 - struct ext4_str *oname)
172 + struct dx_hash_info *hinfo,
173 + const struct ext4_str *iname,
174 + struct ext4_str *oname)
175 {
176 + char buf[24];
177 + int ret;
178 +
179 if (ctx == NULL)
180 return -EIO;
181 if (iname->len < 3) {
182 @@ -587,18 +542,33 @@ int _ext4_fname_disk_to_usr(struct ext4_fname_crypto_ctx *ctx,
183 }
184 if (ctx->has_valid_key)
185 return ext4_fname_decrypt(ctx, iname, oname);
186 - else
187 - return ext4_fname_hash(ctx, iname, oname);
188 +
189 + if (iname->len <= EXT4_FNAME_CRYPTO_DIGEST_SIZE) {
190 + ret = digest_encode(iname->name, iname->len, oname->name);
191 + oname->len = ret;
192 + return ret;
193 + }
194 + if (hinfo) {
195 + memcpy(buf, &hinfo->hash, 4);
196 + memcpy(buf+4, &hinfo->minor_hash, 4);
197 + } else
198 + memset(buf, 0, 8);
199 + memcpy(buf + 8, iname->name + iname->len - 16, 16);
200 + oname->name[0] = '_';
201 + ret = digest_encode(buf, 24, oname->name+1);
202 + oname->len = ret + 1;
203 + return ret + 1;
204 }
206 int ext4_fname_disk_to_usr(struct ext4_fname_crypto_ctx *ctx,
207 + struct dx_hash_info *hinfo,
208 const struct ext4_dir_entry_2 *de,
209 struct ext4_str *oname)
210 {
211 struct ext4_str iname = {.name = (unsigned char *) de->name,
212 .len = de->name_len };
214 - return _ext4_fname_disk_to_usr(ctx, &iname, oname);
215 + return _ext4_fname_disk_to_usr(ctx, hinfo, &iname, oname);
216 }
219 @@ -640,10 +610,11 @@ int ext4_fname_usr_to_hash(struct ext4_fname_crypto_ctx *ctx,
220 const struct qstr *iname,
221 struct dx_hash_info *hinfo)
222 {
223 - struct ext4_str tmp, tmp2;
224 + struct ext4_str tmp;
225 int ret = 0;
226 + char buf[EXT4_FNAME_CRYPTO_DIGEST_SIZE+1];
228 - if (!ctx || !ctx->has_valid_key ||
229 + if (!ctx ||
230 ((iname->name[0] == '.') &&
231 ((iname->len == 1) ||
232 ((iname->name[1] == '.') && (iname->len == 2))))) {
233 @@ -651,59 +622,90 @@ int ext4_fname_usr_to_hash(struct ext4_fname_crypto_ctx *ctx,
234 return 0;
235 }
237 + if (!ctx->has_valid_key && iname->name[0] == '_') {
238 + if (iname->len != 33)
239 + return -ENOENT;
240 + ret = digest_decode(iname->name+1, iname->len, buf);
241 + if (ret != 24)
242 + return -ENOENT;
243 + memcpy(&hinfo->hash, buf, 4);
244 + memcpy(&hinfo->minor_hash, buf + 4, 4);
245 + return 0;
246 + }
247 +
248 + if (!ctx->has_valid_key && iname->name[0] != '_') {
249 + if (iname->len > 43)
250 + return -ENOENT;
251 + ret = digest_decode(iname->name, iname->len, buf);
252 + ext4fs_dirhash(buf, ret, hinfo);
253 + return 0;
254 + }
255 +
256 /* First encrypt the plaintext name */
257 ret = ext4_fname_crypto_alloc_buffer(ctx, iname->len, &tmp);
258 if (ret < 0)
259 return ret;
261 ret = ext4_fname_encrypt(ctx, iname, &tmp);
262 - if (ret < 0)
263 - goto out;
264 -
265 - tmp2.len = (4 * ((EXT4_FNAME_CRYPTO_DIGEST_SIZE + 2) / 3)) + 1;
266 - tmp2.name = kmalloc(tmp2.len + 1, GFP_KERNEL);
267 - if (tmp2.name == NULL) {
268 - ret = -ENOMEM;
269 - goto out;
270 + if (ret >= 0) {
271 + ext4fs_dirhash(tmp.name, tmp.len, hinfo);
272 + ret = 0;
273 }
275 - ret = ext4_fname_hash(ctx, &tmp, &tmp2);
276 - if (ret > 0)
277 - ext4fs_dirhash(tmp2.name, tmp2.len, hinfo);
278 - ext4_fname_crypto_free_buffer(&tmp2);
279 -out:
280 ext4_fname_crypto_free_buffer(&tmp);
281 return ret;
282 }
284 -/**
285 - * ext4_fname_disk_to_htree() - converts a filename from disk space to htree-access string
286 - */
287 -int ext4_fname_disk_to_hash(struct ext4_fname_crypto_ctx *ctx,
288 - const struct ext4_dir_entry_2 *de,
289 - struct dx_hash_info *hinfo)
290 +int ext4_fname_match(struct ext4_fname_crypto_ctx *ctx, struct ext4_str *cstr,
291 + int len, const char * const name,
292 + struct ext4_dir_entry_2 *de)
293 {
294 - struct ext4_str iname = {.name = (unsigned char *) de->name,
295 - .len = de->name_len};
296 - struct ext4_str tmp;
297 - int ret;
298 + int ret = -ENOENT;
299 + int bigname = (*name == '_');
301 - if (!ctx ||
302 - ((iname.name[0] == '.') &&
303 - ((iname.len == 1) ||
304 - ((iname.name[1] == '.') && (iname.len == 2))))) {
305 - ext4fs_dirhash(iname.name, iname.len, hinfo);
306 - return 0;
307 + if (ctx->has_valid_key) {
308 + if (cstr->name == NULL) {
309 + struct qstr istr;
310 +
311 + ret = ext4_fname_crypto_alloc_buffer(ctx, len, cstr);
312 + if (ret < 0)
313 + goto errout;
314 + istr.name = name;
315 + istr.len = len;
316 + ret = ext4_fname_encrypt(ctx, &istr, cstr);
317 + if (ret < 0)
318 + goto errout;
319 + }
320 + } else {
321 + if (cstr->name == NULL) {
322 + cstr->name = kmalloc(32, GFP_KERNEL);
323 + if (cstr->name == NULL)
324 + return -ENOMEM;
325 + if ((bigname && (len != 33)) ||
326 + (!bigname && (len > 43)))
327 + goto errout;
328 + ret = digest_decode(name+bigname, len-bigname,
329 + cstr->name);
330 + if (ret < 0) {
331 + ret = -ENOENT;
332 + goto errout;
333 + }
334 + cstr->len = ret;
335 + }
336 + if (bigname) {
337 + if (de->name_len < 16)
338 + return 0;
339 + ret = memcmp(de->name + de->name_len - 16,
340 + cstr->name + 8, 16);
341 + return (ret == 0) ? 1 : 0;
342 + }
343 }
344 -
345 - tmp.len = (4 * ((EXT4_FNAME_CRYPTO_DIGEST_SIZE + 2) / 3)) + 1;
346 - tmp.name = kmalloc(tmp.len + 1, GFP_KERNEL);
347 - if (tmp.name == NULL)
348 - return -ENOMEM;
349 -
350 - ret = ext4_fname_hash(ctx, &iname, &tmp);
351 - if (ret > 0)
352 - ext4fs_dirhash(tmp.name, tmp.len, hinfo);
353 - ext4_fname_crypto_free_buffer(&tmp);
354 + if (de->name_len != cstr->len)
355 + return 0;
356 + ret = memcmp(de->name, cstr->name, cstr->len);
357 + return (ret == 0) ? 1 : 0;
358 +errout:
359 + kfree(cstr->name);
360 + cstr->name = NULL;
361 return ret;
362 }
363 diff --git a/fs/ext4/dir.c b/fs/ext4/dir.c
364 index 61db51a5..5665d82 100644
365 --- a/fs/ext4/dir.c
366 +++ b/fs/ext4/dir.c
367 @@ -249,7 +249,7 @@ static int ext4_readdir(struct file *file, struct dir_context *ctx)
368 } else {
369 /* Directory is encrypted */
370 err = ext4_fname_disk_to_usr(enc_ctx,
371 - de, &fname_crypto_str);
372 + NULL, de, &fname_crypto_str);
373 if (err < 0)
374 goto errout;
375 if (!dir_emit(ctx,
376 diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
377 index 0179654f..dfb1138 100644
378 --- a/fs/ext4/ext4.h
379 +++ b/fs/ext4/ext4.h
380 @@ -2093,9 +2093,11 @@ u32 ext4_fname_crypto_round_up(u32 size, u32 blksize);
381 int ext4_fname_crypto_alloc_buffer(struct ext4_fname_crypto_ctx *ctx,
382 u32 ilen, struct ext4_str *crypto_str);
383 int _ext4_fname_disk_to_usr(struct ext4_fname_crypto_ctx *ctx,
384 + struct dx_hash_info *hinfo,
385 const struct ext4_str *iname,
386 struct ext4_str *oname);
387 int ext4_fname_disk_to_usr(struct ext4_fname_crypto_ctx *ctx,
388 + struct dx_hash_info *hinfo,
389 const struct ext4_dir_entry_2 *de,
390 struct ext4_str *oname);
391 int ext4_fname_usr_to_disk(struct ext4_fname_crypto_ctx *ctx,
392 @@ -2104,11 +2106,12 @@ int ext4_fname_usr_to_disk(struct ext4_fname_crypto_ctx *ctx,
393 int ext4_fname_usr_to_hash(struct ext4_fname_crypto_ctx *ctx,
394 const struct qstr *iname,
395 struct dx_hash_info *hinfo);
396 -int ext4_fname_disk_to_hash(struct ext4_fname_crypto_ctx *ctx,
397 - const struct ext4_dir_entry_2 *de,
398 - struct dx_hash_info *hinfo);
399 int ext4_fname_crypto_namelen_on_disk(struct ext4_fname_crypto_ctx *ctx,
400 u32 namelen);
401 +int ext4_fname_match(struct ext4_fname_crypto_ctx *ctx, struct ext4_str *cstr,
402 + int len, const char * const name,
403 + struct ext4_dir_entry_2 *de);
404 +
406 #ifdef CONFIG_EXT4_FS_ENCRYPTION
407 void ext4_put_fname_crypto_ctx(struct ext4_fname_crypto_ctx **ctx);
408 diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
409 index 4f87127..5ea7371 100644
410 --- a/fs/ext4/namei.c
411 +++ b/fs/ext4/namei.c
412 @@ -640,7 +640,7 @@ static struct stats dx_show_leaf(struct inode *dir,
413 ext4_put_fname_crypto_ctx(&ctx);
414 ctx = NULL;
415 }
416 - res = ext4_fname_disk_to_usr(ctx, de,
417 + res = ext4_fname_disk_to_usr(ctx, NULL, de,
418 &fname_crypto_str);
419 if (res < 0) {
420 printk(KERN_WARNING "Error "
421 @@ -653,15 +653,8 @@ static struct stats dx_show_leaf(struct inode *dir,
422 name = fname_crypto_str.name;
423 len = fname_crypto_str.len;
424 }
425 - res = ext4_fname_disk_to_hash(ctx, de,
426 - &h);
427 - if (res < 0) {
428 - printk(KERN_WARNING "Error "
429 - "converting filename "
430 - "from disk to htree"
431 - "\n");
432 - h.hash = 0xDEADBEEF;
433 - }
434 + ext4fs_dirhash(de->name, de->name_len,
435 + &h);
436 printk("%*.s:(E)%x.%u ", len, name,
437 h.hash, (unsigned) ((char *) de
438 - base));
439 @@ -1008,15 +1001,7 @@ static int htree_dirblock_to_tree(struct file *dir_file,
440 /* silently ignore the rest of the block */
441 break;
442 }
443 -#ifdef CONFIG_EXT4_FS_ENCRYPTION
444 - err = ext4_fname_disk_to_hash(ctx, de, hinfo);
445 - if (err < 0) {
446 - count = err;
447 - goto errout;
448 - }
449 -#else
450 ext4fs_dirhash(de->name, de->name_len, hinfo);
451 -#endif
452 if ((hinfo->hash < start_hash) ||
453 ((hinfo->hash == start_hash) &&
454 (hinfo->minor_hash < start_minor_hash)))
455 @@ -1032,7 +1017,7 @@ static int htree_dirblock_to_tree(struct file *dir_file,
456 &tmp_str);
457 } else {
458 /* Directory is encrypted */
459 - err = ext4_fname_disk_to_usr(ctx, de,
460 + err = ext4_fname_disk_to_usr(ctx, hinfo, de,
461 &fname_crypto_str);
462 if (err < 0) {
463 count = err;
464 @@ -1193,26 +1178,10 @@ static int dx_make_map(struct inode *dir, struct ext4_dir_entry_2 *de,
465 int count = 0;
466 char *base = (char *) de;
467 struct dx_hash_info h = *hinfo;
468 -#ifdef CONFIG_EXT4_FS_ENCRYPTION
469 - struct ext4_fname_crypto_ctx *ctx = NULL;
470 - int err;
471 -
472 - ctx = ext4_get_fname_crypto_ctx(dir, EXT4_NAME_LEN);
473 - if (IS_ERR(ctx))
474 - return PTR_ERR(ctx);
475 -#endif
477 while ((char *) de < base + blocksize) {
478 if (de->name_len && de->inode) {
479 -#ifdef CONFIG_EXT4_FS_ENCRYPTION
480 - err = ext4_fname_disk_to_hash(ctx, de, &h);
481 - if (err < 0) {
482 - ext4_put_fname_crypto_ctx(&ctx);
483 - return err;
484 - }
485 -#else
486 ext4fs_dirhash(de->name, de->name_len, &h);
487 -#endif
488 map_tail--;
489 map_tail->hash = h.hash;
490 map_tail->offs = ((char *) de - base)>>2;
491 @@ -1223,9 +1192,6 @@ static int dx_make_map(struct inode *dir, struct ext4_dir_entry_2 *de,
492 /* XXX: do we need to check rec_len == 0 case? -Chris */
493 de = ext4_next_entry(de, blocksize);
494 }
495 -#ifdef CONFIG_EXT4_FS_ENCRYPTION
496 - ext4_put_fname_crypto_ctx(&ctx);
497 -#endif
498 return count;
499 }
501 @@ -1287,16 +1253,8 @@ static inline int ext4_match(struct ext4_fname_crypto_ctx *ctx,
502 return 0;
504 #ifdef CONFIG_EXT4_FS_ENCRYPTION
505 - if (ctx) {
506 - /* Directory is encrypted */
507 - res = ext4_fname_disk_to_usr(ctx, de, fname_crypto_str);
508 - if (res < 0)
509 - return res;
510 - if (len != res)
511 - return 0;
512 - res = memcmp(name, fname_crypto_str->name, len);
513 - return (res == 0) ? 1 : 0;
514 - }
515 + if (ctx)
516 + return ext4_fname_match(ctx, fname_crypto_str, len, name, de);
517 #endif
518 if (len != de->name_len)
519 return 0;
520 @@ -1324,16 +1282,6 @@ int search_dir(struct buffer_head *bh, char *search_buf, int buf_size,
521 if (IS_ERR(ctx))
522 return -1;
524 - if (ctx != NULL) {
525 - /* Allocate buffer to hold maximum name length */
526 - res = ext4_fname_crypto_alloc_buffer(ctx, EXT4_NAME_LEN,
527 - &fname_crypto_str);
528 - if (res < 0) {
529 - ext4_put_fname_crypto_ctx(&ctx);
530 - return -1;
531 - }
532 - }
533 -
534 de = (struct ext4_dir_entry_2 *)search_buf;
535 dlimit = search_buf + buf_size;
536 while ((char *) de < dlimit) {
537 @@ -1872,14 +1820,6 @@ int ext4_find_dest_de(struct inode *dir, struct inode *inode,
538 return res;
539 }
540 reclen = EXT4_DIR_REC_LEN(res);
541 -
542 - /* Allocate buffer to hold maximum name length */
543 - res = ext4_fname_crypto_alloc_buffer(ctx, EXT4_NAME_LEN,
544 - &fname_crypto_str);
545 - if (res < 0) {
546 - ext4_put_fname_crypto_ctx(&ctx);
547 - return -1;
548 - }
549 }
551 de = (struct ext4_dir_entry_2 *)buf;
552 diff --git a/fs/ext4/symlink.c b/fs/ext4/symlink.c
553 index 136ca0e..ce2ed28 100644
554 --- a/fs/ext4/symlink.c
555 +++ b/fs/ext4/symlink.c
556 @@ -74,7 +74,7 @@ static void *ext4_follow_link(struct dentry *dentry, struct nameidata *nd)
557 goto errout;
558 }
559 pstr.name = paddr;
560 - res = _ext4_fname_disk_to_usr(ctx, &cstr, &pstr);
561 + res = _ext4_fname_disk_to_usr(ctx, NULL, &cstr, &pstr);
562 if (res < 0)
563 goto errout;
564 /* Null-terminate the name */