=====================================
Filesystem-level encryption (fscrypt)
=====================================

Introduction
============

fscrypt is a library which filesystems can hook into to support
transparent encryption of files and directories.

Note: "fscrypt" in this document refers to the kernel-level portion,
implemented in ``fs/crypto/``, as opposed to the userspace tool
`fscrypt <https://github.com/google/fscrypt>`_.  This document only
covers the kernel-level portion.  For command-line examples of how to
use encryption, see the documentation for the userspace tool `fscrypt
<https://github.com/google/fscrypt>`_.  Also, it is recommended to use
the fscrypt userspace tool, or other existing userspace tools such as
`fscryptctl <https://github.com/google/fscryptctl>`_ or `Android's key
management system
<https://source.android.com/security/encryption/file-based>`_, over
using the kernel's API directly.  Using existing tools reduces the
chance of introducing your own security bugs.  (Nevertheless, for
completeness this documentation covers the kernel's API anyway.)

Unlike dm-crypt, fscrypt operates at the filesystem level rather than
at the block device level.  This allows it to encrypt different files
with different keys and to have unencrypted files on the same
filesystem.  This is useful for multi-user systems where each user's
data-at-rest needs to be cryptographically isolated from the others.
However, except for filenames, fscrypt does not encrypt filesystem
metadata.

Unlike eCryptfs, which is a stacked filesystem, fscrypt is integrated
directly into supported filesystems --- currently ext4, F2FS, and
UBIFS.  This allows encrypted files to be read and written without
caching both the decrypted and encrypted pages in the pagecache,
thereby nearly halving the memory used and bringing it in line with
unencrypted files.  Similarly, half as many dentries and inodes are
needed.  eCryptfs also limits encrypted filenames to 143 bytes,
causing application compatibility issues; fscrypt allows the full 255
bytes (NAME_MAX).  Finally, unlike eCryptfs, the fscrypt API can be
used by unprivileged users, with no need to mount anything.

fscrypt does not support encrypting files in-place.  Instead, it
supports marking an empty directory as encrypted.  Then, after
userspace provides the key, all regular files, directories, and
symbolic links created in that directory tree are transparently
encrypted.

Threat model
============

Offline attacks
---------------

Provided that userspace chooses a strong encryption key, fscrypt
protects the confidentiality of file contents and filenames in the
event of a single point-in-time permanent offline compromise of the
block device content.  fscrypt does not protect the confidentiality of
non-filename metadata, e.g. file sizes, file permissions, file
timestamps, and extended attributes.  Also, the existence and location
of holes (unallocated blocks which logically contain all zeroes) in
files is not protected.

fscrypt is not guaranteed to protect confidentiality or authenticity
if an attacker is able to manipulate the filesystem offline prior to
an authorized user later accessing the filesystem.

Online attacks
--------------

fscrypt (and storage encryption in general) can only provide limited
protection, if any at all, against online attacks.  In detail:

Side-channel attacks
~~~~~~~~~~~~~~~~~~~~

fscrypt is only resistant to side-channel attacks, such as timing or
electromagnetic attacks, to the extent that the underlying Linux
Cryptographic API algorithms or inline encryption hardware are.  If a
vulnerable algorithm is used, such as a table-based implementation of
AES, it may be possible for an attacker to mount a side channel attack
against the online system.  Side channel attacks may also be mounted
against applications consuming decrypted data.

Unauthorized file access
~~~~~~~~~~~~~~~~~~~~~~~~

After an encryption key has been added, fscrypt does not hide the
plaintext file contents or filenames from other users on the same
system.  Instead, existing access control mechanisms such as file mode
bits, POSIX ACLs, LSMs, or namespaces should be used for this purpose.

(For the reasoning behind this, understand that while the key is
added, the confidentiality of the data, from the perspective of the
system itself, is *not* protected by the mathematical properties of
encryption but rather only by the correctness of the kernel.
Therefore, any encryption-specific access control checks would merely
be enforced by kernel *code* and therefore would be largely redundant
with the wide variety of access control mechanisms already available.)

Kernel memory compromise
~~~~~~~~~~~~~~~~~~~~~~~~

An attacker who compromises the system enough to read from arbitrary
memory, e.g. by mounting a physical attack or by exploiting a kernel
security vulnerability, can compromise all encryption keys that are
currently in use.

However, fscrypt allows encryption keys to be removed from the kernel,
which may protect them from later compromise.

In more detail, the FS_IOC_REMOVE_ENCRYPTION_KEY ioctl (or the
FS_IOC_REMOVE_ENCRYPTION_KEY_ALL_USERS ioctl) can wipe a master
encryption key from kernel memory.  If it does so, it will also try to
evict all cached inodes which had been "unlocked" using the key,
thereby wiping their per-file keys and making them once again appear
"locked", i.e. in ciphertext or encrypted form.

However, these ioctls have some limitations:

- Per-file keys for in-use files will *not* be removed or wiped.
  Therefore, for maximum effect, userspace should close the relevant
  encrypted files and directories before removing a master key, as
  well as kill any processes whose working directory is in an affected
  encrypted directory.

- The kernel cannot magically wipe copies of the master key(s) that
  userspace might have as well.  Therefore, userspace must wipe all
  copies of the master key(s) it makes as well; normally this should
  be done immediately after FS_IOC_ADD_ENCRYPTION_KEY, without waiting
  for FS_IOC_REMOVE_ENCRYPTION_KEY.  Naturally, the same also applies
  to all higher levels in the key hierarchy.  Userspace should also
  follow other security precautions such as mlock()ing memory
  containing keys to prevent it from being swapped out.

- In general, decrypted contents and filenames in the kernel VFS
  caches are freed but not wiped.  Therefore, portions thereof may be
  recoverable from freed memory, even after the corresponding key(s)
  were wiped.  To partially solve this, you can set
  CONFIG_PAGE_POISONING=y in your kernel config and add page_poison=1
  to your kernel command line.  However, this has a performance cost.

- Secret keys might still exist in CPU registers, in crypto
  accelerator hardware (if used by the crypto API to implement any of
  the algorithms), or in other places not explicitly considered here.

Limitations of v1 policies
~~~~~~~~~~~~~~~~~~~~~~~~~~

v1 encryption policies have some weaknesses with respect to online
attacks:

- There is no verification that the provided master key is correct.
  Therefore, a malicious user can temporarily associate the wrong key
  with another user's encrypted files to which they have read-only
  access.  Because of filesystem caching, the wrong key will then be
  used by the other user's accesses to those files, even if the other
  user has the correct key in their own keyring.  This violates the
  meaning of "read-only access".

- A compromise of a per-file key also compromises the master key from
  which it was derived.

- Non-root users cannot securely remove encryption keys.

All the above problems are fixed with v2 encryption policies.  For
this reason among others, it is recommended to use v2 encryption
policies on all new encrypted directories.

Key hierarchy
=============

Master Keys
-----------

Each encrypted directory tree is protected by a *master key*.  Master
keys can be up to 64 bytes long, and must be at least as long as the
greater of the security strength of the contents and filenames
encryption modes being used.  For example, if any AES-256 mode is
used, the master key must be at least 256 bits, i.e. 32 bytes.  A
stricter requirement applies if the key is used by a v1 encryption
policy and AES-256-XTS is used; such keys must be 64 bytes.

To "unlock" an encrypted directory tree, userspace must provide the
appropriate master key.  There can be any number of master keys, each
of which protects any number of directory trees on any number of
filesystems.

Master keys must be real cryptographic keys, i.e. indistinguishable
from random bytestrings of the same length.  This implies that users
**must not** directly use a password as a master key, zero-pad a
shorter key, or repeat a shorter key.  Security cannot be guaranteed
if userspace makes any such error, as the cryptographic proofs and
analysis would no longer apply.

Instead, users should generate master keys either using a
cryptographically secure random number generator, or by using a KDF
(Key Derivation Function).  The kernel does not do any key stretching;
therefore, if userspace derives the key from a low-entropy secret such
as a passphrase, it is critical that a KDF designed for this purpose
be used, such as scrypt, PBKDF2, or Argon2.

Key derivation function
-----------------------

With one exception, fscrypt never uses the master key(s) for
encryption directly.  Instead, they are only used as input to a KDF
(Key Derivation Function) to derive the actual keys.

The KDF used for a particular master key differs depending on whether
the key is used for v1 encryption policies or for v2 encryption
policies.  Users **must not** use the same key for both v1 and v2
encryption policies.  (No real-world attack is currently known on this
specific case of key reuse, but its security cannot be guaranteed
since the cryptographic proofs and analysis would no longer apply.)

For v1 encryption policies, the KDF only supports deriving per-file
encryption keys.  It works by encrypting the master key with
AES-128-ECB, using the file's 16-byte nonce as the AES key.  The
resulting ciphertext is used as the derived key.  If the ciphertext is
longer than needed, then it is truncated to the needed length.

For v2 encryption policies, the KDF is HKDF-SHA512.  The master key is
passed as the "input keying material", no salt is used, and a distinct
"application-specific information string" is used for each distinct
key to be derived.  For example, when a per-file encryption key is
derived, the application-specific information string is the file's
nonce prefixed with "fscrypt\\0" and a context byte.  Different
context bytes are used for other types of derived keys.

HKDF-SHA512 is preferred to the original AES-128-ECB based KDF because
HKDF is more flexible, is nonreversible, and evenly distributes
entropy from the master key.  HKDF is also standardized and widely
used by other software, whereas the AES-128-ECB based KDF is ad-hoc.

Per-file encryption keys
------------------------

Since each master key can protect many files, it is necessary to
"tweak" the encryption of each file so that the same plaintext in two
files doesn't map to the same ciphertext, or vice versa.  In most
cases, fscrypt does this by deriving per-file keys.  When a new
encrypted inode (regular file, directory, or symlink) is created,
fscrypt randomly generates a 16-byte nonce and stores it in the
inode's encryption xattr.  Then, it uses a KDF (as described in `Key
derivation function`_) to derive the file's key from the master key
and nonce.

Key derivation was chosen over key wrapping because wrapped keys would
require larger xattrs which would be less likely to fit in-line in the
filesystem's inode table, and there didn't appear to be any
significant advantages to key wrapping.  In particular, currently
there is no requirement to support unlocking a file with multiple
alternative master keys or to support rotating master keys.  Instead,
the master keys may be wrapped in userspace, e.g. as is done by the
`fscrypt <https://github.com/google/fscrypt>`_ tool.

DIRECT_KEY policies
-------------------

The Adiantum encryption mode (see `Encryption modes and usage`_) is
suitable for both contents and filenames encryption, and it accepts
long IVs --- long enough to hold both an 8-byte logical block number
and a 16-byte per-file nonce.  Also, the overhead of each Adiantum key
is greater than that of an AES-256-XTS key.

Therefore, to improve performance and save memory, for Adiantum a
"direct key" configuration is supported.  When the user has enabled
this by setting FSCRYPT_POLICY_FLAG_DIRECT_KEY in the fscrypt policy,
per-file encryption keys are not used.  Instead, whenever any data
(contents or filenames) is encrypted, the file's 16-byte nonce is
included in the IV.  Moreover:

- For v1 encryption policies, the encryption is done directly with the
  master key.  Because of this, users **must not** use the same master
  key for any other purpose, even for other v1 policies.

- For v2 encryption policies, the encryption is done with a per-mode
  key derived using the KDF.  Users may use the same master key for
  other v2 encryption policies.

IV_INO_LBLK_64 policies
-----------------------

When FSCRYPT_POLICY_FLAG_IV_INO_LBLK_64 is set in the fscrypt policy,
the encryption keys are derived from the master key, encryption mode
number, and filesystem UUID.  This normally results in all files
protected by the same master key sharing a single contents encryption
key and a single filenames encryption key.  To still encrypt different
files' data differently, inode numbers are included in the IVs.
Consequently, shrinking the filesystem may not be allowed.

This format is optimized for use with inline encryption hardware
compliant with the UFS standard, which supports only 64 IV bits per
I/O request and may have only a small number of keyslots.

IV_INO_LBLK_32 policies
-----------------------

IV_INO_LBLK_32 policies work like IV_INO_LBLK_64, except that for
IV_INO_LBLK_32, the inode number is hashed with SipHash-2-4 (where the
SipHash key is derived from the master key) and added to the file
logical block number mod 2^32 to produce a 32-bit IV.

This format is optimized for use with inline encryption hardware
compliant with the eMMC v5.2 standard, which supports only 32 IV bits
per I/O request and may have only a small number of keyslots.  This
format results in some level of IV reuse, so it should only be used
when necessary due to hardware limitations.

Key identifiers
---------------

For master keys used for v2 encryption policies, a unique 16-byte "key
identifier" is also derived using the KDF.  This value is stored in
the clear, since it is needed to reliably identify the key itself.

Dirhash keys
------------

For directories that are indexed using a secret-keyed dirhash over the
plaintext filenames, the KDF is also used to derive a 128-bit
SipHash-2-4 key per directory in order to hash filenames.  This works
just like deriving a per-file encryption key, except that a different
KDF context is used.  Currently, only casefolded ("case-insensitive")
encrypted directories use this style of hashing.

Encryption modes and usage
==========================

fscrypt allows one encryption mode to be specified for file contents
and one encryption mode to be specified for filenames.  Different
directory trees are permitted to use different encryption modes.
Currently, the following pairs of encryption modes are supported:

- AES-256-XTS for contents and AES-256-CTS-CBC for filenames
- AES-128-CBC for contents and AES-128-CTS-CBC for filenames
- Adiantum for both contents and filenames
- AES-256-XTS for contents and AES-256-HCTR2 for filenames (v2 policies only)
- SM4-XTS for contents and SM4-CTS-CBC for filenames (v2 policies only)

If unsure, you should use the (AES-256-XTS, AES-256-CTS-CBC) pair.

AES-128-CBC was added only for low-powered embedded devices with
crypto accelerators such as CAAM or CESA that do not support XTS.  To
use AES-128-CBC, CONFIG_CRYPTO_ESSIV and CONFIG_CRYPTO_SHA256 (or
another SHA-256 implementation) must be enabled so that ESSIV can be
used.

Adiantum is a (primarily) stream cipher-based mode that is fast even
on CPUs without dedicated crypto instructions.  It's also a true
wide-block mode, unlike XTS.  It can also eliminate the need to derive
per-file encryption keys.  However, it depends on the security of two
primitives, XChaCha12 and AES-256, rather than just one.  See the
paper "Adiantum: length-preserving encryption for entry-level
processors" (https://eprint.iacr.org/2018/720.pdf) for more details.
To use Adiantum, CONFIG_CRYPTO_ADIANTUM must be enabled.  Also, fast
implementations of ChaCha and NHPoly1305 should be enabled, e.g.
CONFIG_CRYPTO_CHACHA20_NEON and CONFIG_CRYPTO_NHPOLY1305_NEON for ARM.

AES-256-HCTR2 is another true wide-block encryption mode that is intended for
use on CPUs with dedicated crypto instructions.  AES-256-HCTR2 has the property
that a bitflip in the plaintext changes the entire ciphertext.  This property
makes it desirable for filename encryption since initialization vectors are
reused within a directory.  For more details on AES-256-HCTR2, see the paper
"Length-preserving encryption with HCTR2"
(https://eprint.iacr.org/2021/1441.pdf).  To use AES-256-HCTR2,
CONFIG_CRYPTO_HCTR2 must be enabled.  Also, fast implementations of XCTR and
POLYVAL should be enabled, e.g. CRYPTO_POLYVAL_ARM64_CE and
CRYPTO_AES_ARM64_CE_BLK for ARM64.

SM4 is a Chinese block cipher that is an alternative to AES.  It has
not seen as much security review as AES, and it only has a 128-bit key
size.  It may be useful in cases where its use is mandated.
Otherwise, it should not be used.  For SM4 support to be available, it
also needs to be enabled in the kernel crypto API.

New encryption modes can be added relatively easily, without changes
to individual filesystems.  However, authenticated encryption (AE)
modes are not currently supported because of the difficulty of dealing
with ciphertext expansion.

Contents encryption
-------------------

For file contents, each filesystem block is encrypted independently.
Starting from Linux kernel 5.5, encryption of filesystems with block
size less than system's page size is supported.

Each block's IV is set to the logical block number within the file as
a little endian number, except that:

- With CBC mode encryption, ESSIV is also used.  Specifically, each IV
  is encrypted with AES-256 where the AES-256 key is the SHA-256 hash
  of the file's data encryption key.

- With `DIRECT_KEY policies`_, the file's nonce is appended to the IV.
  Currently this is only allowed with the Adiantum encryption mode.

- With `IV_INO_LBLK_64 policies`_, the logical block number is limited
  to 32 bits and is placed in bits 0-31 of the IV.  The inode number
  (which is also limited to 32 bits) is placed in bits 32-63.

- With `IV_INO_LBLK_32 policies`_, the logical block number is limited
  to 32 bits and is placed in bits 0-31 of the IV.  The inode number
  is then hashed and added mod 2^32.

Note that because file logical block numbers are included in the IVs,
filesystems must enforce that blocks are never shifted around within
encrypted files, e.g. via "collapse range" or "insert range".

Filenames encryption
--------------------

For filenames, each full filename is encrypted at once.  Because of
the requirements to retain support for efficient directory lookups and
filenames of up to 255 bytes, the same IV is used for every filename
in a directory.

However, each encrypted directory still uses a unique key, or
alternatively has the file's nonce (for `DIRECT_KEY policies`_) or
inode number (for `IV_INO_LBLK_64 policies`_) included in the IVs.
Thus, IV reuse is limited to within a single directory.

With CTS-CBC, the IV reuse means that when the plaintext filenames share a
common prefix at least as long as the cipher block size (16 bytes for AES), the
corresponding encrypted filenames will also share a common prefix.  This is
undesirable.  Adiantum and HCTR2 do not have this weakness, as they are
wide-block encryption modes.

All supported filenames encryption modes accept any plaintext length
>= 16 bytes; cipher block alignment is not required.  However,
filenames shorter than 16 bytes are NUL-padded to 16 bytes before
being encrypted.  In addition, to reduce leakage of filename lengths
via their ciphertexts, all filenames are NUL-padded to the next 4, 8,
16, or 32-byte boundary (configurable).  32 is recommended since this
provides the best confidentiality, at the cost of making directory
entries consume slightly more space.  Note that since NUL (``\0``) is
not otherwise a valid character in filenames, the padding will never
produce duplicate plaintexts.

Symbolic link targets are considered a type of filename and are
encrypted in the same way as filenames in directory entries, except
that IV reuse is not a problem as each symlink has its own inode.

User API
========

Setting an encryption policy
----------------------------

FS_IOC_SET_ENCRYPTION_POLICY
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The FS_IOC_SET_ENCRYPTION_POLICY ioctl sets an encryption policy on an
empty directory or verifies that a directory or regular file already
has the specified encryption policy.  It takes in a pointer to
struct fscrypt_policy_v1 or struct fscrypt_policy_v2, defined as
follows::

    #define FSCRYPT_POLICY_V1               0
    #define FSCRYPT_KEY_DESCRIPTOR_SIZE     8
    struct fscrypt_policy_v1 {
            __u8 version;
            __u8 contents_encryption_mode;
            __u8 filenames_encryption_mode;
            __u8 flags;
            __u8 master_key_descriptor[FSCRYPT_KEY_DESCRIPTOR_SIZE];
    };
    #define fscrypt_policy  fscrypt_policy_v1

    #define FSCRYPT_POLICY_V2               2
    #define FSCRYPT_KEY_IDENTIFIER_SIZE     16
    struct fscrypt_policy_v2 {
            __u8 version;
            __u8 contents_encryption_mode;
            __u8 filenames_encryption_mode;
            __u8 flags;
            __u8 __reserved[4];
            __u8 master_key_identifier[FSCRYPT_KEY_IDENTIFIER_SIZE];
    };

This structure must be initialized as follows:

- ``version`` must be FSCRYPT_POLICY_V1 (0) if
  struct fscrypt_policy_v1 is used or FSCRYPT_POLICY_V2 (2) if
  struct fscrypt_policy_v2 is used. (Note: we refer to the original
  policy version as "v1", though its version code is really 0.)
  For new encrypted directories, use v2 policies.

- ``contents_encryption_mode`` and ``filenames_encryption_mode`` must
  be set to constants from ``<linux/fscrypt.h>`` which identify the
  encryption modes to use.  If unsure, use FSCRYPT_MODE_AES_256_XTS
  (1) for ``contents_encryption_mode`` and FSCRYPT_MODE_AES_256_CTS
  (4) for ``filenames_encryption_mode``.

- ``flags`` contains optional flags from ``<linux/fscrypt.h>``:

  - FSCRYPT_POLICY_FLAGS_PAD_*: The amount of NUL padding to use when
    encrypting filenames.  If unsure, use FSCRYPT_POLICY_FLAGS_PAD_32
    (0x3).
  - FSCRYPT_POLICY_FLAG_DIRECT_KEY: See `DIRECT_KEY policies`_.
  - FSCRYPT_POLICY_FLAG_IV_INO_LBLK_64: See `IV_INO_LBLK_64
    policies`_.
  - FSCRYPT_POLICY_FLAG_IV_INO_LBLK_32: See `IV_INO_LBLK_32
    policies`_.

  v1 encryption policies only support the PAD_* and DIRECT_KEY flags.
  The other flags are only supported by v2 encryption policies.

  The DIRECT_KEY, IV_INO_LBLK_64, and IV_INO_LBLK_32 flags are
  mutually exclusive.

- For v2 encryption policies,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 