Difference between revisions of "Projects/Replay cache improvements"
| Line 3: | Line 3: | ||
==Background== |
==Background== |
||
| − | http://colabti.org/irclogger/irclogger_log/krbdev?date=2014-08-26 |
||
| + | MIT krb5 implements a replay cache and uses it by default. Replay caches provide a limited defense against certain kinds of active attacks against some protocols. The current replay cache implementations has severe performance limitations as well as flaws which can cause both false positives and false negatives. Many server deployments disable the replay cache as a result. |
||
| − | ==Correctness== |
||
| + | ===Synopsis of current implementation=== |
||
| − | The current implementation has the following possible issues with correctness: |
||
| + | The replay cache stores replay records which contain server and client principal names, an authenticator ciphertext hash, and an authenticator timestamp. The ciphertext hash is not part of the file format, so for backward compatibility, two records are stored for each authenticator, one of which encodes the hash, client, and server principal names in the nominal server name field. Records are generally small, but are not fixed-size because principal names vary in length. |
||
| − | * Existing race condition when creating (or replacing on corruption). {{bug|3498}} |
||
| + | When a replay cache handle is opened, we attempt to open an existing replay cache file and read in all of its current entries into an in-memory hash table. If we fail to open the file or read any of its entries, we attempt to initialize the file. If we successfully read all of the entries but detect more than 30 expired entries, we attempt to expunge the file. To initialize the file, we unlink it (ignoring errors), open it with O_CREAT|O_EXCL, and write a two-byte header containing a version number. To expunge the file, we close the file descriptor, initialize the file, then write all non-expired entries from the hash table. |
||
| − | * Possible file corruption due to lack of locking and not using O_APPEND {{bug|1671}}. Probable mechanism is two processes nearly simultaneously writing at the same file offset, which will cause overlapping writes unless O_APPEND is set. |
||
| + | For each authentication, the replay record is checked against the memory hash table for a conflict, then added to the table, then marshalled and written to the file. Based on a heuristic, we may choose to expunge the file; otherwise we fsync() it to ensure that no replay records are lost due to a system reboot. |
||
| − | * Once a replay cache handle is open, entries written by other processes will not be detected. |
||
| + | ===Correctness=== |
||
| − | * If another process does an expunge, the current process will not notice, and will continue to write entries to an unlinked file. |
||
| + | The current implementation has the following possible issues with correctness: |
||
| − | ==Performance== |
||
| + | * There is a race condition when creating a replay cache file, or replacing one after detecting corruption ({{bug|3498}}). |
||
| − | * Use of fsync() can cause performance problems. {{bug|372}} |
||
| + | * On Windows, races while expunging the replay cache can cause temporary files to be left behind, which eventually exhausts the space in the directory. |
||
| − | ==Short-term solutions== |
||
| + | * There is a possibility for file corruption due to lack of locking and not using O_APPEND ({{bug|1671}}). If two processes nearly simultaneously write at the same file offset, the writes will overlap unless O_APPEND is set. |
||
| − | * Fix the file creation race somehow |
||
| + | * Once a replay cache handle is open, entries written by other processes (or through other handles) will not be detected. Expunges performed through other handles will also not be detected, and the current handle will continue to write entries to the unlinked file. |
||
| − | * Start using O_APPEND and detect when other processes have written entries |
||
| + | ===Performance=== |
||
| − | * Detect expunges by other processes |
||
| + | The current implementation performs an fsync() on every write ({{bug|372}}). Unless the replay cache is located in a memory filesystem, this is always the limiting performance factor. |
||
| − | * Start using file locking |
||
| + | Since the current format is not in any way sorted, a newly opened reply cache handle must read all entries in the file to detect a conflict. For high-traffic situations, this is performance-limiting if fsync is not. If a single replay cache handle is used for many authentications, this problem does not apply because the replay cache implementation (incorrectly) does not read new entries. |
||
| − | ==Medium-term solutions== |
||
| + | The current replay cache implementation does not use any file locking. Although this causes correctness issues, it means that contention between processes is not performance-limiting. |
||
| − | * New file-based replay cache, possibly hash table based |
||
| + | ==Improvements== |
||
| − | * IPC-based replay cache for higher performance |
||
| + | Short-term solutions may include: |
||
| + | * Fix the file creation race somehow to avoid spurious failures, perhaps by unlinking and retrying on failure to open. |
||
| + | * Start using O_APPEND and detect when other processes have written entries. |
||
| + | * Detect expunges by other processes. |
||
| + | * Start using file locking. |
||
| + | * Stop using fsync, at least for most records. |
||
| − | + | Medium-term solutions may include: |
|
| + | * New file-based replay cache, possibly hash table based. |
||
| + | * IPC-based replay cache for higher performance. |
||
| + | Long-term solutions may include: |
||
* Revise protocols to not require replay caches for security |
* Revise protocols to not require replay caches for security |
||
| + | |||
| + | ===fsync avoidance=== |
||
| + | |||
| + | ===Hash-based file format=== |
||
| + | |||
| + | ===Transition to a new format=== |
||
| + | |||
| + | ==Other discussions== |
||
| + | |||
| + | http://colabti.org/irclogger/irclogger_log/krbdev?date=2014-08-26 |
||
| + | https://lists.anl.gov/pipermail/ietf-krb-wg/2011-November/003241.html |
||
Revision as of 11:05, 27 August 2014
Contents
Background
MIT krb5 implements a replay cache and uses it by default. Replay caches provide a limited defense against certain kinds of active attacks against some protocols. The current replay cache implementations has severe performance limitations as well as flaws which can cause both false positives and false negatives. Many server deployments disable the replay cache as a result.
Synopsis of current implementation
The replay cache stores replay records which contain server and client principal names, an authenticator ciphertext hash, and an authenticator timestamp. The ciphertext hash is not part of the file format, so for backward compatibility, two records are stored for each authenticator, one of which encodes the hash, client, and server principal names in the nominal server name field. Records are generally small, but are not fixed-size because principal names vary in length.
When a replay cache handle is opened, we attempt to open an existing replay cache file and read in all of its current entries into an in-memory hash table. If we fail to open the file or read any of its entries, we attempt to initialize the file. If we successfully read all of the entries but detect more than 30 expired entries, we attempt to expunge the file. To initialize the file, we unlink it (ignoring errors), open it with O_CREAT|O_EXCL, and write a two-byte header containing a version number. To expunge the file, we close the file descriptor, initialize the file, then write all non-expired entries from the hash table.
For each authentication, the replay record is checked against the memory hash table for a conflict, then added to the table, then marshalled and written to the file. Based on a heuristic, we may choose to expunge the file; otherwise we fsync() it to ensure that no replay records are lost due to a system reboot.
Correctness
The current implementation has the following possible issues with correctness:
- There is a race condition when creating a replay cache file, or replacing one after detecting corruption ([krbdev.mit.edu #3498]).
- On Windows, races while expunging the replay cache can cause temporary files to be left behind, which eventually exhausts the space in the directory.
- There is a possibility for file corruption due to lack of locking and not using O_APPEND ([krbdev.mit.edu #1671]). If two processes nearly simultaneously write at the same file offset, the writes will overlap unless O_APPEND is set.
- Once a replay cache handle is open, entries written by other processes (or through other handles) will not be detected. Expunges performed through other handles will also not be detected, and the current handle will continue to write entries to the unlinked file.
Performance
The current implementation performs an fsync() on every write ([krbdev.mit.edu #372]). Unless the replay cache is located in a memory filesystem, this is always the limiting performance factor.
Since the current format is not in any way sorted, a newly opened reply cache handle must read all entries in the file to detect a conflict. For high-traffic situations, this is performance-limiting if fsync is not. If a single replay cache handle is used for many authentications, this problem does not apply because the replay cache implementation (incorrectly) does not read new entries.
The current replay cache implementation does not use any file locking. Although this causes correctness issues, it means that contention between processes is not performance-limiting.
Improvements
Short-term solutions may include:
- Fix the file creation race somehow to avoid spurious failures, perhaps by unlinking and retrying on failure to open.
- Start using O_APPEND and detect when other processes have written entries.
- Detect expunges by other processes.
- Start using file locking.
- Stop using fsync, at least for most records.
Medium-term solutions may include:
- New file-based replay cache, possibly hash table based.
- IPC-based replay cache for higher performance.
Long-term solutions may include:
- Revise protocols to not require replay caches for security
fsync avoidance
Hash-based file format
Transition to a new format
Other discussions
http://colabti.org/irclogger/irclogger_log/krbdev?date=2014-08-26 https://lists.anl.gov/pipermail/ietf-krb-wg/2011-November/003241.html
