On Mon, Jun 05, 2023 at 08:37:04AM -0700, Darrick J. Wong wrote:
> From: Darrick J. Wong <djwong@xxxxxxxxxx>
>
> We want to create a debugger command that will create obfuscated names
> for directory and xattr names, so hoist the name obfuscation code into a
> separate file.
>
> Signed-off-by: Darrick J. Wong <djwong@xxxxxxxxxx>
Reviewed-by: Carlos Maiolino <cmaiolino@xxxxxxxxxx>
> ---
> db/Makefile | 2
> db/metadump.c | 383 -------------------------------------------------------
> db/obfuscate.c | 389 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> db/obfuscate.h | 17 ++
> 4 files changed, 408 insertions(+), 383 deletions(-)
> create mode 100644 db/obfuscate.c
> create mode 100644 db/obfuscate.h
>
>
> diff --git a/db/Makefile b/db/Makefile
> index b2e01174571..2f95f67075d 100644
> --- a/db/Makefile
> +++ b/db/Makefile
> @@ -13,7 +13,7 @@ HFILES = addr.h agf.h agfl.h agi.h attr.h attrshort.h bit.h block.h bmap.h \
> flist.h fprint.h frag.h freesp.h hash.h help.h init.h inode.h input.h \
> io.h logformat.h malloc.h metadump.h output.h print.h quit.h sb.h \
> sig.h strvec.h text.h type.h write.h attrset.h symlink.h fsmap.h \
> - fuzz.h
> + fuzz.h obfuscate.h
> CFILES = $(HFILES:.h=.c) btdump.c btheight.c convert.c info.c namei.c \
> timelimit.c
> LSRCFILES = xfs_admin.sh xfs_ncheck.sh xfs_metadump.sh
> diff --git a/db/metadump.c b/db/metadump.c
> index 4f8b3adb163..d9a616a9296 100644
> --- a/db/metadump.c
> +++ b/db/metadump.c
> @@ -19,6 +19,7 @@
> #include "faddr.h"
> #include "field.h"
> #include "dir2.h"
> +#include "obfuscate.h"
>
> #define DEFAULT_MAX_EXT_SIZE XFS_MAX_BMBT_EXTLEN
>
> @@ -736,19 +737,6 @@ nametable_add(xfs_dahash_t hash, int namelen, unsigned char *name)
> return ent;
> }
>
> -#define is_invalid_char(c) ((c) == '/' || (c) == '\0')
> -#define rol32(x,y) (((x) << (y)) | ((x) >> (32 - (y))))
> -
> -static inline unsigned char
> -random_filename_char(void)
> -{
> - static unsigned char filename_alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
> - "abcdefghijklmnopqrstuvwxyz"
> - "0123456789-_";
> -
> - return filename_alphabet[random() % (sizeof filename_alphabet - 1)];
> -}
> -
> #define ORPHANAGE "lost+found"
> #define ORPHANAGE_LEN (sizeof (ORPHANAGE) - 1)
>
> @@ -808,375 +796,6 @@ in_lost_found(
> return slen == namelen && !memcmp(name, s, namelen);
> }
>
> -/*
> - * Given a name and its hash value, massage the name in such a way
> - * that the result is another name of equal length which shares the
> - * same hash value.
> - */
> -static void
> -obfuscate_name(
> - xfs_dahash_t hash,
> - size_t name_len,
> - unsigned char *name,
> - bool is_dirent)
> -{
> - unsigned char *oldname = NULL;
> - unsigned char *newp;
> - int i;
> - xfs_dahash_t new_hash;
> - unsigned char *first;
> - unsigned char high_bit;
> - int tries = 0;
> - bool is_ci_name = is_dirent && xfs_has_asciici(mp);
> - int shift;
> -
> - /*
> - * Our obfuscation algorithm requires at least 5-character
> - * names, so don't bother if the name is too short. We
> - * work backward from a hash value to determine the last
> - * five bytes in a name required to produce a new name
> - * with the same hash.
> - */
> - if (name_len < 5)
> - return;
> -
> - if (is_ci_name) {
> - oldname = alloca(name_len);
> - memcpy(oldname, name, name_len);
> - }
> -
> -again:
> - newp = name;
> - new_hash = 0;
> -
> - /*
> - * If we cannot generate a ci-compatible obfuscated name after 1000
> - * tries, don't bother obfuscating the name.
> - */
> - if (tries++ > 1000) {
> - memcpy(name, oldname, name_len);
> - return;
> - }
> -
> - /*
> - * The beginning of the obfuscated name can be pretty much
> - * anything, so fill it in with random characters.
> - * Accumulate its new hash value as we go.
> - */
> - for (i = 0; i < name_len - 5; i++) {
> - *newp = random_filename_char();
> - if (is_ci_name)
> - new_hash = xfs_ascii_ci_xfrm(*newp) ^
> - rol32(new_hash, 7);
> - else
> - new_hash = *newp ^ rol32(new_hash, 7);
> - newp++;
> - }
> -
> - /*
> - * Compute which five bytes need to be used at the end of
> - * the name so the hash of the obfuscated name is the same
> - * as the hash of the original. If any result in an invalid
> - * character, flip a bit and arrange for a corresponding bit
> - * in a neighboring byte to be flipped as well. For the
> - * last byte, the "neighbor" to change is the first byte
> - * we're computing here.
> - */
> - new_hash = rol32(new_hash, 3) ^ hash;
> -
> - first = newp;
> - high_bit = 0;
> - for (shift = 28; shift >= 0; shift -= 7) {
> - *newp = (new_hash >> shift & 0x7f) ^ high_bit;
> - if (is_invalid_char(*newp)) {
> - *newp ^= 1;
> - high_bit = 0x80;
> - } else
> - high_bit = 0;
> -
> - /*
> - * If ascii-ci is enabled, uppercase characters are converted
> - * to lowercase characters while computing the name hash. If
> - * any of the necessary correction bytes are uppercase, the
> - * hash of the new name will not match. Try again with a
> - * different prefix.
> - */
> - if (is_ci_name && xfs_ascii_ci_need_xfrm(*newp))
> - goto again;
> -
> - ASSERT(!is_invalid_char(*newp));
> - newp++;
> - }
> -
> - /*
> - * If we flipped a bit on the last byte, we need to fix up
> - * the matching bit in the first byte. The result will
> - * be a valid character, because we know that first byte
> - * has 0's in its upper four bits (it was produced by a
> - * 28-bit right-shift of a 32-bit unsigned value).
> - */
> - if (high_bit) {
> - *first ^= 0x10;
> -
> - if (is_ci_name && xfs_ascii_ci_need_xfrm(*first))
> - goto again;
> -
> - ASSERT(!is_invalid_char(*first));
> - }
> -}
> -
> -/*
> - * Flip a bit in each of two bytes at the end of the given name.
> - * This is used in generating a series of alternate names to be used
> - * in the event a duplicate is found.
> - *
> - * The bits flipped are selected such that they both affect the same
> - * bit in the name's computed hash value, so flipping them both will
> - * preserve the hash.
> - *
> - * The following diagram aims to show the portion of a computed
> - * hash that a given byte of a name affects.
> - *
> - * 31 28 24 21 14 8 7 3 0
> - * +-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+
> - * hash: | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
> - * +-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+
> - * last-4 ->| |<-- last-2 --->| |<--- last ---->|
> - * |<-- last-3 --->| |<-- last-1 --->| |<- last-4
> - * |<-- last-7 --->| |<-- last-5 --->|
> - * |<-- last-8 --->| |<-- last-6 --->|
> - * . . . and so on
> - *
> - * The last byte of the name directly affects the low-order byte of
> - * the hash. The next-to-last affects bits 7-14, the next one back
> - * affects bits 14-21, and so on. The effect wraps around when it
> - * goes beyond the top of the hash (as happens for byte last-4).
> - *
> - * Bits that are flipped together "overlap" on the hash value. As
> - * an example of overlap, the last two bytes both affect bit 7 in
> - * the hash. That pair of bytes (and their overlapping bits) can be
> - * used for this "flip bit" operation (it's the first pair tried,
> - * actually).
> - *
> - * A table defines overlapping pairs--the bytes involved and bits
> - * within them--that can be used this way. The byte offset is
> - * relative to a starting point within the name, which will be set
> - * to affect the bytes at the end of the name. The function is
> - * called with a "bitseq" value which indicates which bit flip is
> - * desired, and this translates directly into selecting which entry
> - * in the bit_to_flip[] table to apply.
> - *
> - * The function returns 1 if the operation was successful. It
> - * returns 0 if the result produced a character that's not valid in
> - * a name (either '/' or a '\0'). Finally, it returns -1 if the bit
> - * sequence number is beyond what is supported for a name of this
> - * length.
> - *
> - * Discussion
> - * ----------
> - * (Also see the discussion above find_alternate(), below.)
> - *
> - * In order to make this function work for any length name, the
> - * table is ordered by increasing byte offset, so that the earliest
> - * entries can apply to the shortest strings. This way all names
> - * are done consistently.
> - *
> - * When bit flips occur, they can convert printable characters
> - * into non-printable ones. In an effort to reduce the impact of
> - * this, the first bit flips are chosen to affect bytes the end of
> - * the name (and furthermore, toward the low bits of a byte). Those
> - * bytes are often non-printable anyway because of the way they are
> - * initially selected by obfuscate_name()). This is accomplished,
> - * using later table entries first.
> - *
> - * Each row in the table doubles the number of alternates that
> - * can be generated. A two-byte name is limited to using only
> - * the first row, so it's possible to generate two alternates
> - * (the original name, plus the alternate produced by flipping
> - * the one pair of bits). In a 5-byte name, the effect of the
> - * first byte overlaps the last by 4 its, and there are 8 bits
> - * to flip, allowing for 256 possible alternates.
> - *
> - * Short names (less than 5 bytes) are never even obfuscated, so for
> - * such names the relatively small number of alternates should never
> - * really be a problem.
> - *
> - * Long names (more than 6 bytes, say) are not likely to exhaust
> - * the number of available alternates. In fact, the table could
> - * probably have stopped at 8 entries, on the assumption that 256
> - * alternates should be enough for most any situation. The entries
> - * beyond those are present mostly for demonstration of how it could
> - * be populated with more entries, should it ever be necessary to do
> - * so.
> - */
> -static int
> -flip_bit(
> - size_t name_len,
> - unsigned char *name,
> - uint32_t bitseq)
> -{
> - int index;
> - size_t offset;
> - unsigned char *p0, *p1;
> - unsigned char m0, m1;
> - struct {
> - int byte; /* Offset from start within name */
> - unsigned char bit; /* Bit within that byte */
> - } bit_to_flip[][2] = { /* Sorted by second entry's byte */
> - { { 0, 0 }, { 1, 7 } }, /* Each row defines a pair */
> - { { 1, 0 }, { 2, 7 } }, /* of bytes and a bit within */
> - { { 2, 0 }, { 3, 7 } }, /* each byte. Each bit in */
> - { { 0, 4 }, { 4, 0 } }, /* a pair affects the same */
> - { { 0, 5 }, { 4, 1 } }, /* bit in the hash, so flipping */
> - { { 0, 6 }, { 4, 2 } }, /* both will change the name */
> - { { 0, 7 }, { 4, 3 } }, /* while preserving the hash. */
> - { { 3, 0 }, { 4, 7 } },
> - { { 0, 0 }, { 5, 3 } }, /* The first entry's byte offset */
> - { { 0, 1 }, { 5, 4 } }, /* must be less than the second. */
> - { { 0, 2 }, { 5, 5 } },
> - { { 0, 3 }, { 5, 6 } }, /* The table can be extended to */
> - { { 0, 4 }, { 5, 7 } }, /* an arbitrary number of entries */
> - { { 4, 0 }, { 5, 7 } }, /* but there's not much point. */
> - /* . . . */
> - };
> -
> - /* Find the first entry *not* usable for name of this length */
> -
> - for (index = 0; index < ARRAY_SIZE(bit_to_flip); index++)
> - if (bit_to_flip[index][1].byte >= name_len)
> - break;
> -
> - /*
> - * Back up to the last usable entry. If that number is
> - * smaller than the bit sequence number, inform the caller
> - * that nothing this large (or larger) will work.
> - */
> - if (bitseq > --index)
> - return -1;
> -
> - /*
> - * We will be switching bits at the end of name, with a
> - * preference for affecting the last bytes first. Compute
> - * where in the name we'll start applying the changes.
> - */
> - offset = name_len - (bit_to_flip[index][1].byte + 1);
> - index -= bitseq; /* Use later table entries first */
> -
> - p0 = name + offset + bit_to_flip[index][0].byte;
> - p1 = name + offset + bit_to_flip[index][1].byte;
> - m0 = 1 << bit_to_flip[index][0].bit;
> - m1 = 1 << bit_to_flip[index][1].bit;
> -
> - /* Only change the bytes if it produces valid characters */
> -
> - if (is_invalid_char(*p0 ^ m0) || is_invalid_char(*p1 ^ m1))
> - return 0;
> -
> - *p0 ^= m0;
> - *p1 ^= m1;
> -
> - return 1;
> -}
> -
> -/*
> - * This function generates a well-defined sequence of "alternate"
> - * names for a given name. An alternate is a name having the same
> - * length and same hash value as the original name. This is needed
> - * because the algorithm produces only one obfuscated name to use
> - * for a given original name, and it's possible that result matches
> - * a name already seen. This function checks for this, and if it
> - * occurs, finds another suitable obfuscated name to use.
> - *
> - * Each bit in the binary representation of the sequence number is
> - * used to select one possible "bit flip" operation to perform on
> - * the name. So for example:
> - * seq = 0: selects no bits to flip
> - * seq = 1: selects the 0th bit to flip
> - * seq = 2: selects the 1st bit to flip
> - * seq = 3: selects the 0th and 1st bit to flip
> - * ... and so on.
> - *
> - * The flip_bit() function takes care of the details of the bit
> - * flipping within the name. Note that the "1st bit" in this
> - * context is a bit sequence number; i.e. it doesn't necessarily
> - * mean bit 0x02 will be changed.
> - *
> - * If a valid name (one that contains no '/' or '\0' characters) is
> - * produced by this process for the given sequence number, this
> - * function returns 1. If the result is not valid, it returns 0.
> - * Returns -1 if the sequence number is beyond the the maximum for
> - * names of the given length.
> - *
> - *
> - * Discussion
> - * ----------
> - * The number of alternates available for a given name is dependent
> - * on its length. A "bit flip" involves inverting two bits in
> - * a name--the two bits being selected such that their values
> - * affect the name's hash value in the same way. Alternates are
> - * thus generated by inverting the value of pairs of such
> - * "overlapping" bits in the original name. Each byte after the
> - * first in a name adds at least one bit of overlap to work with.
> - * (See comments above flip_bit() for more discussion on this.)
> - *
> - * So the number of alternates is dependent on the number of such
> - * overlapping bits in a name. If there are N bit overlaps, there
> - * 2^N alternates for that hash value.
> - *
> - * Here are the number of overlapping bits available for generating
> - * alternates for names of specific lengths:
> - * 1 0 (must have 2 bytes to have any overlap)
> - * 2 1 One bit overlaps--so 2 possible alternates
> - * 3 2 Two bits overlap--so 4 possible alternates
> - * 4 4 Three bits overlap, so 2^3 alternates
> - * 5 8 8 bits overlap (due to wrapping), 256 alternates
> - * 6 18 2^18 alternates
> - * 7 28 2^28 alternates
> - * ...
> - * It's clear that the number of alternates grows very quickly with
> - * the length of the name. But note that the set of alternates
> - * includes invalid names. And for certain (contrived) names, the
> - * number of valid names is a fairly small fraction of the total
> - * number of alternates.
> - *
> - * The main driver for this infrastructure for coming up with
> - * alternate names is really related to names 5 (or possibly 6)
> - * bytes in length. 5-byte obfuscated names contain no randomly-
> - * generated bytes in them, and the chance of an obfuscated name
> - * matching an already-seen name is too high to just ignore. This
> - * methodical selection of alternates ensures we don't produce
> - * duplicate names unless we have exhausted our options.
> - */
> -static int
> -find_alternate(
> - size_t name_len,
> - unsigned char *name,
> - uint32_t seq)
> -{
> - uint32_t bitseq = 0;
> - uint32_t bits = seq;
> -
> - if (!seq)
> - return 1; /* alternate 0 is the original name */
> - if (name_len < 2) /* Must have 2 bytes to flip */
> - return -1;
> -
> - for (bitseq = 0; bits; bitseq++) {
> - uint32_t mask = 1 << bitseq;
> - int fb;
> -
> - if (!(bits & mask))
> - continue;
> -
> - fb = flip_bit(name_len, name, bitseq);
> - if (fb < 1)
> - return fb ? -1 : 0;
> - bits ^= mask;
> - }
> -
> - return 1;
> -}
> -
> /*
> * Look up the given name in the name table. If it is already
> * present, iterate through a well-defined sequence of alternate
> diff --git a/db/obfuscate.c b/db/obfuscate.c
> new file mode 100644
> index 00000000000..249f22b52ce
> --- /dev/null
> +++ b/db/obfuscate.c
> @@ -0,0 +1,389 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * Copyright (c) 2007, 2011 SGI
> + * All Rights Reserved.
> + */
> +#include "libxfs.h"
> +#include "init.h"
> +#include "obfuscate.h"
> +
> +static inline unsigned char
> +random_filename_char(void)
> +{
> + static unsigned char filename_alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
> + "abcdefghijklmnopqrstuvwxyz"
> + "0123456789-_";
> +
> + return filename_alphabet[random() % (sizeof filename_alphabet - 1)];
> +}
> +
> +#define rol32(x,y) (((x) << (y)) | ((x) >> (32 - (y))))
> +
> +/*
> + * Given a name and its hash value, massage the name in such a way
> + * that the result is another name of equal length which shares the
> + * same hash value.
> + */
> +void
> +obfuscate_name(
> + xfs_dahash_t hash,
> + size_t name_len,
> + unsigned char *name,
> + bool is_dirent)
> +{
> + unsigned char *oldname = NULL;
> + unsigned char *newp;
> + int i;
> + xfs_dahash_t new_hash;
> + unsigned char *first;
> + unsigned char high_bit;
> + int tries = 0;
> + bool is_ci_name = is_dirent && xfs_has_asciici(mp);
> + int shift;
> +
> + /*
> + * Our obfuscation algorithm requires at least 5-character
> + * names, so don't bother if the name is too short. We
> + * work backward from a hash value to determine the last
> + * five bytes in a name required to produce a new name
> + * with the same hash.
> + */
> + if (name_len < 5)
> + return;
> +
> + if (is_ci_name) {
> + oldname = alloca(name_len);
> + memcpy(oldname, name, name_len);
> + }
> +
> +again:
> + newp = name;
> + new_hash = 0;
> +
> + /*
> + * If we cannot generate a ci-compatible obfuscated name after 1000
> + * tries, don't bother obfuscating the name.
> + */
> + if (tries++ > 1000) {
> + memcpy(name, oldname, name_len);
> + return;
> + }
> +
> + /*
> + * The beginning of the obfuscated name can be pretty much
> + * anything, so fill it in with random characters.
> + * Accumulate its new hash value as we go.
> + */
> + for (i = 0; i < name_len - 5; i++) {
> + *newp = random_filename_char();
> + if (is_ci_name)
> + new_hash = xfs_ascii_ci_xfrm(*newp) ^
> + rol32(new_hash, 7);
> + else
> + new_hash = *newp ^ rol32(new_hash, 7);
> + newp++;
> + }
> +
> + /*
> + * Compute which five bytes need to be used at the end of
> + * the name so the hash of the obfuscated name is the same
> + * as the hash of the original. If any result in an invalid
> + * character, flip a bit and arrange for a corresponding bit
> + * in a neighboring byte to be flipped as well. For the
> + * last byte, the "neighbor" to change is the first byte
> + * we're computing here.
> + */
> + new_hash = rol32(new_hash, 3) ^ hash;
> +
> + first = newp;
> + high_bit = 0;
> + for (shift = 28; shift >= 0; shift -= 7) {
> + *newp = (new_hash >> shift & 0x7f) ^ high_bit;
> + if (is_invalid_char(*newp)) {
> + *newp ^= 1;
> + high_bit = 0x80;
> + } else
> + high_bit = 0;
> +
> + /*
> + * If ascii-ci is enabled, uppercase characters are converted
> + * to lowercase characters while computing the name hash. If
> + * any of the necessary correction bytes are uppercase, the
> + * hash of the new name will not match. Try again with a
> + * different prefix.
> + */
> + if (is_ci_name && xfs_ascii_ci_need_xfrm(*newp))
> + goto again;
> +
> + ASSERT(!is_invalid_char(*newp));
> + newp++;
> + }
> +
> + /*
> + * If we flipped a bit on the last byte, we need to fix up
> + * the matching bit in the first byte. The result will
> + * be a valid character, because we know that first byte
> + * has 0's in its upper four bits (it was produced by a
> + * 28-bit right-shift of a 32-bit unsigned value).
> + */
> + if (high_bit) {
> + *first ^= 0x10;
> +
> + if (is_ci_name && xfs_ascii_ci_need_xfrm(*first))
> + goto again;
> +
> + ASSERT(!is_invalid_char(*first));
> + }
> +}
> +
> +/*
> + * Flip a bit in each of two bytes at the end of the given name.
> + * This is used in generating a series of alternate names to be used
> + * in the event a duplicate is found.
> + *
> + * The bits flipped are selected such that they both affect the same
> + * bit in the name's computed hash value, so flipping them both will
> + * preserve the hash.
> + *
> + * The following diagram aims to show the portion of a computed
> + * hash that a given byte of a name affects.
> + *
> + * 31 28 24 21 14 8 7 3 0
> + * +-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+
> + * hash: | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
> + * +-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+
> + * last-4 ->| |<-- last-2 --->| |<--- last ---->|
> + * |<-- last-3 --->| |<-- last-1 --->| |<- last-4
> + * |<-- last-7 --->| |<-- last-5 --->|
> + * |<-- last-8 --->| |<-- last-6 --->|
> + * . . . and so on
> + *
> + * The last byte of the name directly affects the low-order byte of
> + * the hash. The next-to-last affects bits 7-14, the next one back
> + * affects bits 14-21, and so on. The effect wraps around when it
> + * goes beyond the top of the hash (as happens for byte last-4).
> + *
> + * Bits that are flipped together "overlap" on the hash value. As
> + * an example of overlap, the last two bytes both affect bit 7 in
> + * the hash. That pair of bytes (and their overlapping bits) can be
> + * used for this "flip bit" operation (it's the first pair tried,
> + * actually).
> + *
> + * A table defines overlapping pairs--the bytes involved and bits
> + * within them--that can be used this way. The byte offset is
> + * relative to a starting point within the name, which will be set
> + * to affect the bytes at the end of the name. The function is
> + * called with a "bitseq" value which indicates which bit flip is
> + * desired, and this translates directly into selecting which entry
> + * in the bit_to_flip[] table to apply.
> + *
> + * The function returns 1 if the operation was successful. It
> + * returns 0 if the result produced a character that's not valid in
> + * a name (either '/' or a '\0'). Finally, it returns -1 if the bit
> + * sequence number is beyond what is supported for a name of this
> + * length.
> + *
> + * Discussion
> + * ----------
> + * (Also see the discussion above find_alternate(), below.)
> + *
> + * In order to make this function work for any length name, the
> + * table is ordered by increasing byte offset, so that the earliest
> + * entries can apply to the shortest strings. This way all names
> + * are done consistently.
> + *
> + * When bit flips occur, they can convert printable characters
> + * into non-printable ones. In an effort to reduce the impact of
> + * this, the first bit flips are chosen to affect bytes the end of
> + * the name (and furthermore, toward the low bits of a byte). Those
> + * bytes are often non-printable anyway because of the way they are
> + * initially selected by obfuscate_name()). This is accomplished,
> + * using later table entries first.
> + *
> + * Each row in the table doubles the number of alternates that
> + * can be generated. A two-byte name is limited to using only
> + * the first row, so it's possible to generate two alternates
> + * (the original name, plus the alternate produced by flipping
> + * the one pair of bits). In a 5-byte name, the effect of the
> + * first byte overlaps the last by 4 its, and there are 8 bits
> + * to flip, allowing for 256 possible alternates.
> + *
> + * Short names (less than 5 bytes) are never even obfuscated, so for
> + * such names the relatively small number of alternates should never
> + * really be a problem.
> + *
> + * Long names (more than 6 bytes, say) are not likely to exhaust
> + * the number of available alternates. In fact, the table could
> + * probably have stopped at 8 entries, on the assumption that 256
> + * alternates should be enough for most any situation. The entries
> + * beyond those are present mostly for demonstration of how it could
> + * be populated with more entries, should it ever be necessary to do
> + * so.
> + */
> +static int
> +flip_bit(
> + size_t name_len,
> + unsigned char *name,
> + uint32_t bitseq)
> +{
> + int index;
> + size_t offset;
> + unsigned char *p0, *p1;
> + unsigned char m0, m1;
> + struct {
> + int byte; /* Offset from start within name */
> + unsigned char bit; /* Bit within that byte */
> + } bit_to_flip[][2] = { /* Sorted by second entry's byte */
> + { { 0, 0 }, { 1, 7 } }, /* Each row defines a pair */
> + { { 1, 0 }, { 2, 7 } }, /* of bytes and a bit within */
> + { { 2, 0 }, { 3, 7 } }, /* each byte. Each bit in */
> + { { 0, 4 }, { 4, 0 } }, /* a pair affects the same */
> + { { 0, 5 }, { 4, 1 } }, /* bit in the hash, so flipping */
> + { { 0, 6 }, { 4, 2 } }, /* both will change the name */
> + { { 0, 7 }, { 4, 3 } }, /* while preserving the hash. */
> + { { 3, 0 }, { 4, 7 } },
> + { { 0, 0 }, { 5, 3 } }, /* The first entry's byte offset */
> + { { 0, 1 }, { 5, 4 } }, /* must be less than the second. */
> + { { 0, 2 }, { 5, 5 } },
> + { { 0, 3 }, { 5, 6 } }, /* The table can be extended to */
> + { { 0, 4 }, { 5, 7 } }, /* an arbitrary number of entries */
> + { { 4, 0 }, { 5, 7 } }, /* but there's not much point. */
> + /* . . . */
> + };
> +
> + /* Find the first entry *not* usable for name of this length */
> +
> + for (index = 0; index < ARRAY_SIZE(bit_to_flip); index++)
> + if (bit_to_flip[index][1].byte >= name_len)
> + break;
> +
> + /*
> + * Back up to the last usable entry. If that number is
> + * smaller than the bit sequence number, inform the caller
> + * that nothing this large (or larger) will work.
> + */
> + if (bitseq > --index)
> + return -1;
> +
> + /*
> + * We will be switching bits at the end of name, with a
> + * preference for affecting the last bytes first. Compute
> + * where in the name we'll start applying the changes.
> + */
> + offset = name_len - (bit_to_flip[index][1].byte + 1);
> + index -= bitseq; /* Use later table entries first */
> +
> + p0 = name + offset + bit_to_flip[index][0].byte;
> + p1 = name + offset + bit_to_flip[index][1].byte;
> + m0 = 1 << bit_to_flip[index][0].bit;
> + m1 = 1 << bit_to_flip[index][1].bit;
> +
> + /* Only change the bytes if it produces valid characters */
> +
> + if (is_invalid_char(*p0 ^ m0) || is_invalid_char(*p1 ^ m1))
> + return 0;
> +
> + *p0 ^= m0;
> + *p1 ^= m1;
> +
> + return 1;
> +}
> +
> +/*
> + * This function generates a well-defined sequence of "alternate"
> + * names for a given name. An alternate is a name having the same
> + * length and same hash value as the original name. This is needed
> + * because the algorithm produces only one obfuscated name to use
> + * for a given original name, and it's possible that result matches
> + * a name already seen. This function checks for this, and if it
> + * occurs, finds another suitable obfuscated name to use.
> + *
> + * Each bit in the binary representation of the sequence number is
> + * used to select one possible "bit flip" operation to perform on
> + * the name. So for example:
> + * seq = 0: selects no bits to flip
> + * seq = 1: selects the 0th bit to flip
> + * seq = 2: selects the 1st bit to flip
> + * seq = 3: selects the 0th and 1st bit to flip
> + * ... and so on.
> + *
> + * The flip_bit() function takes care of the details of the bit
> + * flipping within the name. Note that the "1st bit" in this
> + * context is a bit sequence number; i.e. it doesn't necessarily
> + * mean bit 0x02 will be changed.
> + *
> + * If a valid name (one that contains no '/' or '\0' characters) is
> + * produced by this process for the given sequence number, this
> + * function returns 1. If the result is not valid, it returns 0.
> + * Returns -1 if the sequence number is beyond the the maximum for
> + * names of the given length.
> + *
> + *
> + * Discussion
> + * ----------
> + * The number of alternates available for a given name is dependent
> + * on its length. A "bit flip" involves inverting two bits in
> + * a name--the two bits being selected such that their values
> + * affect the name's hash value in the same way. Alternates are
> + * thus generated by inverting the value of pairs of such
> + * "overlapping" bits in the original name. Each byte after the
> + * first in a name adds at least one bit of overlap to work with.
> + * (See comments above flip_bit() for more discussion on this.)
> + *
> + * So the number of alternates is dependent on the number of such
> + * overlapping bits in a name. If there are N bit overlaps, there
> + * 2^N alternates for that hash value.
> + *
> + * Here are the number of overlapping bits available for generating
> + * alternates for names of specific lengths:
> + * 1 0 (must have 2 bytes to have any overlap)
> + * 2 1 One bit overlaps--so 2 possible alternates
> + * 3 2 Two bits overlap--so 4 possible alternates
> + * 4 4 Three bits overlap, so 2^3 alternates
> + * 5 8 8 bits overlap (due to wrapping), 256 alternates
> + * 6 18 2^18 alternates
> + * 7 28 2^28 alternates
> + * ...
> + * It's clear that the number of alternates grows very quickly with
> + * the length of the name. But note that the set of alternates
> + * includes invalid names. And for certain (contrived) names, the
> + * number of valid names is a fairly small fraction of the total
> + * number of alternates.
> + *
> + * The main driver for this infrastructure for coming up with
> + * alternate names is really related to names 5 (or possibly 6)
> + * bytes in length. 5-byte obfuscated names contain no randomly-
> + * generated bytes in them, and the chance of an obfuscated name
> + * matching an already-seen name is too high to just ignore. This
> + * methodical selection of alternates ensures we don't produce
> + * duplicate names unless we have exhausted our options.
> + */
> +int
> +find_alternate(
> + size_t name_len,
> + unsigned char *name,
> + uint32_t seq)
> +{
> + uint32_t bitseq = 0;
> + uint32_t bits = seq;
> +
> + if (!seq)
> + return 1; /* alternate 0 is the original name */
> + if (name_len < 2) /* Must have 2 bytes to flip */
> + return -1;
> +
> + for (bitseq = 0; bits; bitseq++) {
> + uint32_t mask = 1 << bitseq;
> + int fb;
> +
> + if (!(bits & mask))
> + continue;
> +
> + fb = flip_bit(name_len, name, bitseq);
> + if (fb < 1)
> + return fb ? -1 : 0;
> + bits ^= mask;
> + }
> +
> + return 1;
> +}
> diff --git a/db/obfuscate.h b/db/obfuscate.h
> new file mode 100644
> index 00000000000..afaaca37154
> --- /dev/null
> +++ b/db/obfuscate.h
> @@ -0,0 +1,17 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * Copyright (c) 2007, 2011 SGI
> + * All Rights Reserved.
> + */
> +#ifndef __DB_OBFUSCATE_H__
> +#define __DB_OBFUSCATE_H__
> +
> +/* Routines to obfuscate directory filenames and xattr names. */
> +
> +#define is_invalid_char(c) ((c) == '/' || (c) == '\0')
> +
> +void obfuscate_name(xfs_dahash_t hash, size_t name_len, unsigned char *name,
> + bool is_dirent);
> +int find_alternate(size_t name_len, unsigned char *name, uint32_t seq);
> +
> +#endif /* __DB_OBFUSCATE_H__ */
>
