code:
.. SPDX-License-Identifier: GPL-2.0

===============================================
How to Implement a new CPUFreq Processor Driver
===============================================

Authors:

	- Dominik Brodowski  <linux@brodo.de>
	- Rafael J. Wysocki <rafael.j.wysocki@intel.com>
	- Viresh Kumar <viresh.kumar@linaro.org>

.. Contents

   1.   What To Do?
   1.1  Initialization
   1.2  Per-CPU Initialization
   1.3  verify
   1.4  target/target_index or setpolicy?
   1.5  target/target_index
   1.6  setpolicy
   1.7  get_intermediate and target_intermediate
   2.   Frequency Table Helpers

1. What To Do?
==============

So, you just got a brand-new CPU / chipset with datasheets and want to
add cpufreq support for this CPU / chipset? Great. Here are some hints
on what is necessary:

1.1 Initialization
------------------

First of all, in an __initcall level 7 (module_init()) or later
function check whether this kernel runs on the right CPU and the right
chipset. If so, register a struct cpufreq_driver with the CPUfreq core
using cpufreq_register_driver()

What shall this struct cpufreq_driver contain?

 .name - The name of this driver.

 .init - A pointer to the per-policy initialization function.

 .verify - A pointer to a "verification" function.

 .setpolicy _or_ .fast_switch _or_ .target _or_ .target_index - See
 below on the differences.

And optionally

 .flags - Hints for the cpufreq core.

 .driver_data - cpufreq driver specific data.

 .get_intermediate and target_intermediate - Used to switch to stable
 frequency while changing CPU frequency.

 .get - Returns current frequency of the CPU.

 .bios_limit - Returns HW/BIOS max frequency limitations for the CPU.

 .exit - A pointer to a per-policy cleanup function called during
 CPU_POST_DEAD phase of cpu hotplug process.

 .suspend - A pointer to a per-policy suspend function which is called
 with interrupts disabled and _after_ the governor is stopped for the
 policy.

 .resume - A pointer to a per-policy resume function which is called
 with interrupts disabled and _before_ the governor is started again.

 .ready - A pointer to a per-policy ready function which is called after
 the policy is fully initialized.

 .attr - A pointer to a NULL-terminated list of "struct freq_attr" which
 allow to export values to sysfs.

 .boost_enabled - If set, boost frequencies are enabled.

 .set_boost - A pointer to a per-policy function to enable/disable boost
 frequencies.

1.2 Per-CPU Initialization
--------------------------

Whenever a new CPU is registered with the device model, or after the
cpufreq driver registers itself, the per-policy initialization function
cpufreq_driver.init is called if no cpufreq policy existed for the CPU.
Note that the .init() and .exit() routines are called only once for the
policy and not for each CPU managed by the policy. It takes a ``struct
cpufreq_policy *policy`` as argument. What to do now?

If necessary, activate the CPUfreq support on your CPU.

Then, the driver must fill in the following values:

+-----------------------------------+--------------------------------------+
|policy->cpuinfo.min_freq _and_	    |					   |
|policy->cpuinfo.max_freq	    | the minimum and maximum frequency	   |
|				    | (in kHz) which is supported by	   |
|				    | this CPU				   |
+-----------------------------------+--------------------------------------+
|policy->cpuinfo.transition_latency | the time it takes on this CPU to	   |
|				    | switch between two frequencies in	   |
|				    | nanoseconds (if appropriate, else	   |
|				    | specify CPUFREQ_ETERNAL)		   |
+-----------------------------------+--------------------------------------+
|policy->cur			    | The current operating frequency of   |
|				    | this CPU (if appropriate)		   |
+-----------------------------------+--------------------------------------+
|policy->min,			    |					   |
|policy->max,			    |					   |
|policy->policy and, if necessary,  |					   |
|policy->governor		    | must contain the "default policy" for|
|				    | this CPU. A few moments later,       |
|				    | cpufreq_driver.verify and either     |
|				    | cpufreq_driver.setpolicy or          |
|				    | cpufreq_driver.target/target_index is|
|				    | called with these values.		   |
+-----------------------------------+--------------------------------------+
|policy->cpus			    | Update this with the masks of the	   |
|				    | (online + offline) CPUs that do DVFS |
|				    | along with this CPU (i.e.  that share|
|				    | clock/voltage rails with it).	   |
+-----------------------------------+--------------------------------------+

For setting some of these values (cpuinfo.min[max]_freq, policy->min[max]), the
frequency table helpers might be helpful. See the section 2 for more information
on them.

1.3 verify
----------

When the user decides a new policy (consisting of
"policy,governor,min,max") shall be set, this policy must be validated
so that incompatible values can be corrected. For verifying these
values cpufreq_verify_within_limits(``struct cpufreq_policy *policy``,
``unsigned int min_freq``, ``unsigned int max_freq``) function might be helpful.
See section 2 for details on frequency table helpers.

You need to make sure that at least one valid frequency (or operating
range) is within policy->min and policy->max. If necessary, increase
policy->max first, and only if this is no solution, decrease policy->min.

1.4 target or target_index or setpolicy or fast_switch?
-------------------------------------------------------

Most cpufreq drivers or even most cpu frequency scaling algorithms
only allow the CPU frequency to be set to predefined fixed values. For
these, you use the ->target(), ->target_index() or ->fast_switch()
callbacks.

Some cpufreq capable processors switch the frequency between certain
limits on their own. These shall use the ->setpolicy() callback.

1.5. target/target_index
------------------------

The target_index call has two arguments: ``struct cpufreq_policy *policy``,
and ``unsigned int`` index (into the exposed frequency table).

The CPUfreq driver must set the new frequency when called here. The
actual frequency must be determined by freq_table[index].frequency.

It should always restore to earlier frequency (i.e. policy->restore_freq) in
case of errors, even if we switched to intermediate frequency earlier.

Deprecated
----------
The target call has three arguments: ``struct cpufreq_policy *policy``,
unsigned int target_frequency, unsigned int relation.

The CPUfreq driver must set the new frequency when called here. The
actual frequency must be determined using the following rules:

- keep close to "target_freq"
- policy->min <= new_freq <= policy->max (THIS MUST BE VALID!!!)
- if relation==CPUFREQ_REL_L, try to select a new_freq higher than or equal
  target_freq. ("L for lowest, but no lower than")
- if relation==CPUFREQ_REL_H, try to select a new_freq lower than or equal
  target_freq. ("H for highest, but no higher than")

Here again the frequency table helper might assist you - see section 2
for details.

1.6. fast_switch
----------------

This function is used for frequency switching from scheduler's context.
Not all drivers are expected to implement it, as sleeping from within
this callback isn't allowed. This callback must be highly optimized to
do switching as fast as possible.

This function has two arguments: ``struct cpufreq_policy *policy`` and
``unsigned int target_frequency``.

1.7 setpolicy
-------------

The setpolicy call only takes a ``struct cpufreq_policy *policy`` as
argument. You need to set the lower limit of the in-processor or
in-chipset dynamic frequency switching to policy->min, the upper limit
to policy->max, and -if supported- select a performance-oriented
setting when policy->policy is CPUFREQ_POLICY_PERFORMANCE, and a
powersaving-oriented setting when CPUFREQ_POLICY_POWERSAVE. Also check
the reference implementation in drivers/cpufreq/longrun.c

1.8 get_intermediate and target_intermediate
--------------------------------------------

Only for drivers with target_index() and CPUFREQ_ASYNC_NOTIFICATION unset.

get_intermediate should return a stable intermediate frequency platform wants to
switch to, and target_intermediate() should set CPU to that frequency, before
jumping to the frequency corresponding to 'index'. Core will take care of
sending notifications and driver doesn't have to handle them in
target_intermediate() or target_index().

Drivers can return '0' from get_intermediate() in case they don't wish to switch
to intermediate frequency for some target frequency. In that case core will
directly call ->target_index().

NOTE: ->target_index() should restore to policy->restore_freq in case of
failures as core would send notifications for that.

2. Frequency Table Helpers
==========================

As most cpufreq processors only allow for being set to a few specific
frequencies, a "frequency table" with some functions might assist in
some work of the processor driver. Such a "frequency table" consists of
an array of struct cpufreq_frequency_table entries, with driver specific
values in "driver_data", the corresponding frequency in "frequency" and
flags set. At the end of the table, you need to add a
cpufreq_frequency_table entry with frequency set to CPUFREQ_TABLE_END.
And if you want to skip one entry in the table, set the frequency to
CPUFREQ_ENTRY_INVALID. The entries don't need to be in sorted in any
particular order, but if they are cpufreq core will do DVFS a bit
quickly for them as search for best match is faster.

The cpufreq table is verified automatically by the core if the policy contains a
valid pointer in its policy->freq_table field.

cpufreq_frequency_table_verify() assures that at least one valid
frequency is within policy->min and policy->max, and all other criteria
are met. This is helpful for the ->verify call.

cpufreq_frequency_table_target() is the corresponding frequency table
helper for the ->target stage. Just pass the values to this function,
and this function returns the of the frequency table entry which
contains the frequency the CPU shall be set to.

The following macros can be used as iterators over cpufreq_frequency_table:

cpufreq_for_each_entry(pos, table) - iterates over all entries of frequency
table.

cpufreq_for_each_valid_entry(pos, table) - iterates over all entries,
excluding CPUFREQ_ENTRY_INVALID frequencies.
Use arguments "pos" - a ``cpufreq_frequency_table *`` as a loop cursor and
"table" - the ``cpufreq_frequency_table *`` you want to iterate over.

For example::

	struct cpufreq_frequency_table *pos, *driver_freq_table;

	cpufreq_for_each_entry(pos, driver_freq_table) {
		/* Do something with pos */
		pos->frequency = ...
	}

If you need to work with the position of pos within driver_freq_table,
do not subtract the pointers, as it is quite costly. Instead, use the
macros cpufreq_for_each_entry_idx() and cpufreq_for_each_valid_entry_idx().


code:
.. SPDX-License-Identifier: GPL-2.0

==========================================
General Description of sysfs CPUFreq Stats
==========================================

information for users

Author: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com>

.. Contents

   1. Introduction
   2. Statistics Provided (with example)
   3. Configuring cpufreq-stats

1. Introduction
===============

cpufreq-stats is a driver that provides CPU frequency statistics for each CPU.
These statistics are provided in /sysfs as a bunch of read_only interfaces. This
interface (when configured) will appear in a separate directory under cpufreq
in /sysfs (<sysfs root>/devices/system/cpu/cpuX/cpufreq/stats/) for each CPU.
Various statistics will form read_only files under this directory.

This driver is designed to be independent of any particular cpufreq_driver
that may be running on your CPU. So, it will work with any cpufreq_driver.

2. Statistics Provided (with example)
=====================================

cpufreq stats provides following statistics (explained in detail below).

-  time_in_state
-  total_trans
-  trans_table

All the statistics will be from the time the stats driver has been inserted
(or the time the stats were reset) to the time when a read of a particular
statistic is done. Obviously, stats driver will not have any information
about the frequency transitions before the stats driver insertion.

::

    <mysystem>:/sys/devices/system/cpu/cpu0/cpufreq/stats # ls -l
    total 0
    drwxr-xr-x  2 root root    0 May 14 16:06 .
    drwxr-xr-x  3 root root    0 May 14 15:58 ..
    --w-------  1 root root 4096 May 14 16:06 reset
    -r--r--r--  1 root root 4096 May 14 16:06 time_in_state
    -r--r--r--  1 root root 4096 May 14 16:06 total_trans
    -r--r--r--  1 root root 4096 May 14 16:06 trans_table

- **reset**

Write-only attribute that can be used to reset the stat counters. This can be
useful for evaluating system behaviour under different governors without the
need for a reboot.

- **time_in_state**

This gives the amount of time spent in each of the frequencies supported by
this CPU. The cat output will have "<frequency> <time>" pair in each line, which
will mean this CPU spent <time> usertime units of time at <frequency>. Output
will have one line for each of the supported frequencies. usertime units here
is 10mS (similar to other time exported in /proc).

::

    <mysystem>:/sys/devices/system/cpu/cpu0/cpufreq/stats # cat time_in_state
    3600000 2089
    3400000 136
    3200000 34
    3000000 67
    2800000 172488

- **total_trans**

This gives the total number of frequency transitions on this CPU. The cat
output will have a single count which is the total number of frequency
transitions.

::

    <mysystem>:/sys/devices/system/cpu/cpu0/cpufreq/stats # cat total_trans
    20

- **trans_table**

This will give a fine grained information about all the CPU frequency
transitions. The cat output here is a two dimensional matrix, where an entry
<i,j> (row i, column j) represents the count of number of transitions from
Freq_i to Freq_j. Freq_i rows and Freq_j columns follow the sorting order in
which the driver has provided the frequency table initially to the cpufreq core
and so can be sorted (ascending or descending) or unsorted.  The output here
also contains the actual freq values for each row and column for better
readability.

If the transition table is bigger than PAGE_SIZE, reading this will
return an -EFBIG error.

::

    <mysystem>:/sys/devices/system/cpu/cpu0/cpufreq/stats # cat trans_table
    From  :    To
	    :   3600000   3400000   3200000   3000000   2800000
    3600000:         0         5         0         0         0
    3400000:         4         0         2         0         0
    3200000:         0         1         0         2         0
    3000000:         0         0         1         0         3
    2800000:         0         0         0         2         0

3. Configuring cpufreq-stats
============================

To configure cpufreq-stats in your kernel::

	Config Main Menu
		Power management options (ACPI, APM)  --->
			CPU Frequency scaling  --->
				[*] CPU Frequency scaling
				[*]   CPU frequency translation statistics

"CPU Frequency scaling" (CONFIG_CPU_FREQ) should be enabled to configure
cpufreq-stats.

"CPU frequency translation statistics" (CONFIG_CPU_FREQ_STAT) provides the
statistics which includes time_in_state, total_trans and trans_table.

Once this option is enabled and your CPU supports cpufrequency, you
will be able to see the CPU frequency statistics in /sysfs.

repo_name: angery/linux


code:
.. SPDX-License-Identifier: GPL-2.0

==============================================================================
Linux CPUFreq - CPU frequency and voltage scaling code in the Linux(TM) kernel
==============================================================================

Author: Dominik Brodowski  <linux@brodo.de>

   Clock scaling allows you to change the clock speed of the CPUs on the
   fly. This is a nice method to save battery power, because the lower
   the clock speed, the less power the CPU consumes.

.. toctree::
   :maxdepth: 1

   core
   cpu-drivers
   cpufreq-stats

Mailing List
------------
There is a CPU frequency general list where you can report bugs,
problems or submit patches. To post a message, send an email to
linux-pm@vger.kernel.org.

Links
-----
the FTP archives:
* ftp://ftp.linux.org.uk/pub/linux/cpufreq/

the CPUFreq Mailing list:
* http://vger.kernel.org/vger-lists.html#linux-pm

Clock and voltage scaling for the SA-1100:
* http://www.lartmaker.nl/projects/scaling


code:
Authenticated Encryption With Associated Data (AEAD) Algorithm Definitions
--------------------------------------------------------------------------

.. kernel-doc:: include/crypto/aead.h
   :doc: Authenticated Encryption With Associated Data (AEAD) Cipher API

.. kernel-doc:: include/crypto/aead.h
   :functions: aead_request aead_alg

Authenticated Encryption With Associated Data (AEAD) Cipher API
---------------------------------------------------------------

.. kernel-doc:: include/crypto/aead.h
   :functions: crypto_alloc_aead crypto_free_aead crypto_aead_ivsize crypto_aead_authsize crypto_aead_blocksize crypto_aead_setkey crypto_aead_setauthsize crypto_aead_encrypt crypto_aead_decrypt

Asynchronous AEAD Request Handle
--------------------------------

.. kernel-doc:: include/crypto/aead.h
   :doc: Asynchronous AEAD Request Handle

.. kernel-doc:: include/crypto/aead.h
   :functions: crypto_aead_reqsize aead_request_set_tfm aead_request_alloc aead_request_free aead_request_set_callback aead_request_set_crypt aead_request_set_ad


code:
Asymmetric Cipher Algorithm Definitions
---------------------------------------

.. kernel-doc:: include/crypto/akcipher.h
   :functions: akcipher_alg akcipher_request

Asymmetric Cipher API
---------------------

.. kernel-doc:: include/crypto/akcipher.h
   :doc: Generic Public Key API

.. kernel-doc:: include/crypto/akcipher.h
   :functions: crypto_alloc_akcipher crypto_free_akcipher crypto_akcipher_set_pub_key crypto_akcipher_set_priv_key crypto_akcipher_maxsize crypto_akcipher_encrypt crypto_akcipher_decrypt crypto_akcipher_sign crypto_akcipher_verify

Asymmetric Cipher Request Handle
--------------------------------

.. kernel-doc:: include/crypto/akcipher.h
   :functions: akcipher_request_alloc akcipher_request_free akcipher_request_set_callback akcipher_request_set_crypt


code:
Message Digest Algorithm Definitions
------------------------------------

.. kernel-doc:: include/crypto/hash.h
   :doc: Message Digest Algorithm Definitions

.. kernel-doc:: include/crypto/hash.h
   :functions: hash_alg_common ahash_alg shash_alg

Asynchronous Message Digest API
-------------------------------

.. kernel-doc:: include/crypto/hash.h
   :doc: Asynchronous Message Digest API

.. kernel-doc:: include/crypto/hash.h
   :functions: crypto_alloc_ahash crypto_free_ahash crypto_ahash_init crypto_ahash_digestsize crypto_ahash_reqtfm crypto_ahash_reqsize crypto_ahash_statesize crypto_ahash_setkey crypto_ahash_finup crypto_ahash_final crypto_ahash_digest crypto_ahash_export crypto_ahash_import

Asynchronous Hash Request Handle
--------------------------------

.. kernel-doc:: include/crypto/hash.h
   :doc: Asynchronous Hash Request Handle

.. kernel-doc:: include/crypto/hash.h
   :functions: ahash_request_set_tfm ahash_request_alloc ahash_request_free ahash_request_set_callback ahash_request_set_crypt

Synchronous Message Digest API
------------------------------

.. kernel-doc:: include/crypto/hash.h
   :doc: Synchronous Message Digest API

.. kernel-doc:: include/crypto/hash.h
   :functions: crypto_alloc_shash crypto_free_shash crypto_shash_blocksize crypto_shash_digestsize crypto_shash_descsize crypto_shash_setkey crypto_shash_digest crypto_shash_export crypto_shash_import crypto_shash_init crypto_shash_update crypto_shash_final crypto_shash_finup


code:
.. SPDX-License-Identifier: GPL-2.0

=============================
Scatterlist Cryptographic API
=============================

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

The Scatterlist Crypto API takes page vectors (scatterlists) as
arguments, and works directly on pages.  In some cases (e.g. ECB
mode ciphers), this will allow for pages to be encrypted in-place
with no copying.

One of the initial goals of this design was to readily support IPsec,
so that processing can be applied to paged skb's without the need
for linearization.

Details
=======

At the lowest level are algorithms, which register dynamically with the
API.

'Transforms' are user-instantiated objects, which maintain state, handle all
of the implementation logic (e.g. manipulating page vectors) and provide an
abstraction to the underlying algorithms.  However, at the user
level they are very simple.

Conceptually, the API layering looks like this::

  [transform api]  (user interface)
  [transform ops]  (per-type logic glue e.g. cipher.c, compress.c)
  [algorithm api]  (for registering algorithms)

The idea is to make the user interface and algorithm registration API
very simple, while hiding the core logic from both.  Many good ideas
from existing APIs such as Cryptoapi and Nettle have been adapted for this.

The API currently supports five main types of transforms: AEAD (Authenticated
Encryption with Associated Data), Block Ciphers, Ciphers, Compressors and
Hashes.

Please note that Block Ciphers is somewhat of a misnomer.  It is in fact
meant to support all ciphers including stream ciphers.  The difference
between Block Ciphers and Ciphers is that the latter operates on exactly
one block while the former can operate on an arbitrary amount of data,
subject to block size requirements (i.e., non-stream ciphers can only
process multiples of blocks).

Here's an example of how to use the API::

	#include <crypto/hash.h>
	#include <linux/err.h>
	#include <linux/scatterlist.h>

	struct scatterlist sg[2];
	char result[128];
	struct crypto_ahash *tfm;
	struct ahash_request *req;

	tfm = crypto_alloc_ahash("md5", 0, CRYPTO_ALG_ASYNC);
	if (IS_ERR(tfm))
		fail();

	/* ... set up the scatterlists ... */

	req = ahash_request_alloc(tfm, GFP_ATOMIC);
	if (!req)
		fail();

	ahash_request_set_callback(req, 0, NULL, NULL);
	ahash_request_set_crypt(req, sg, result, 2);

	if (crypto_ahash_digest(req))
		fail();

	ahash_request_free(req);
	crypto_free_ahash(tfm);

Many real examples are available in the regression test module (tcrypt.c).

Developer Notes
===============

Transforms may only be allocated in user context, and cryptographic
methods may only be called from softirq and user contexts.  For
transforms with a setkey method it too should only be called from
user context.

When using the API for ciphers, performance will be optimal if each
scatterlist contains data which is a multiple of the cipher's block
size (typically 8 bytes).  This prevents having to do any copying
across non-aligned page fragment boundaries.

Adding New Algorithms
=====================

When submitting a new algorithm for inclusion, a mandatory requirement
is that at least a few test vectors from known sources (preferably
standards) be included.

Converting existing well known code is preferred, as it is more likely
to have been reviewed and widely tested.  If submitting code from LGPL
sources, please consider changing the license to GPL (see section 3 of
the LGPL).

Algorithms submitted must also be generally patent-free (e.g. IDEA
will not be included in the mainline until around 2011), and be based
on a recognized standard and/or have been subjected to appropriate
peer review.

Also check for any RFCs which may relate to the use of specific algorithms,
as well as general application notes such as RFC2451 ("The ESP CBC-Mode
Cipher Algorithms").

It's a good idea to avoid using lots of macros and use inlined functions
instead, as gcc does a good job with inlining, while excessive use of
macros can cause compilation problems on some platforms.

Also check the TODO list at the web site listed below to see what people
might already be working on.

Bugs
====

Send bug reports to:
    linux-crypto@vger.kernel.org

Cc:
    Herbert Xu <herbert@gondor.apana.org.au>,
    David S. Miller <davem@redhat.com>

Further Information
===================

For further patches and various updates, including the current TODO
list, see:
http://gondor.apana.org.au/~herbert/crypto/

Authors
=======

- James Morris
- David S. Miller
- Herbert Xu

Credits
=======

The following people provided invaluable feedback during the development
of the API:

  - Alexey Kuznetzov
  - Rusty Russell
  - Herbert Valerio Riedel
  - Jeff Garzik
  - Michael Richardson
  - Andrew Morton
  - Ingo Oeser
  - Christoph Hellwig

Portions of this API were derived from the following projects:

  Kerneli Cryptoapi (http://www.kerneli.org/)
   - Alexander Kjeldaas
   - Herbert Valerio Riedel
   - Kyle McMartin
   - Jean-Luc Cooke
   - David Bryson
   - Clemens Fruhwirth
   - Tobias Ringstrom
   - Harald Welte

and;

  Nettle (https://www.lysator.liu.se/~nisse/nettle/)
   - Niels Möller

Original developers of the crypto algorithms:

  - Dana L. How (DES)
  - Andrew Tridgell and Steve French (MD4)
  - Colin Plumb (MD5)
  - Steve Reid (SHA1)
  - Jean-Luc Cooke (SHA256, SHA384, SHA512)
  - Kazunori Miyazawa / USAGI (HMAC)
  - Matthew Skala (Twofish)
  - Dag Arne Osvik (Serpent)
  - Brian Gladman (AES)
  - Kartikey Mahendra Bhatt (CAST6)
  - Jon Oberheide (ARC4)
  - Jouni Malinen (Michael MIC)
  - NTT(Nippon Telegraph and Telephone Corporation) (Camellia)

SHA1 algorithm contributors:
  - Jean-Francois Dive

DES algorithm contributors:
  - Raimar Falke
  - Gisle Sælensminde
  - Niels Möller

Blowfish algorithm contributors:
  - Herbert Valerio Riedel
  - Kyle McMartin

Twofish algorithm contributors:
  - Werner Koch
  - Marc Mutz

SHA256/384/512 algorithm contributors:
  - Andrew McDonald
  - Kyle McMartin
  - Herbert Valerio Riedel

AES algorithm contributors:
  - Alexander Kjeldaas
  - Herbert Valerio Riedel
  - Kyle McMartin
  - Adam J. Richter
  - Fruhwirth Clemens (i586)
  - Linus Torvalds (i586)

CAST5 algorithm contributors:
  - Kartikey Mahendra Bhatt (original developers unknown, FSF copyright).

TEA/XTEA algorithm contributors:
  - Aaron Grothe
  - Michael Ringe

Khazad algorithm contributors:
  - Aaron Grothe

Whirlpool algorithm contributors:
  - Aaron Grothe
  - Jean-Luc Cooke

Anubis algorithm contributors:
  - Aaron Grothe

Tiger algorithm contributors:
  - Aaron Grothe

VIA PadLock contributors:
  - Michal Ludvig

Camellia algorithm contributors:
  - NTT(Nippon Telegraph and Telephone Corporation) (Camellia)

Generic scatterwalk code by Adam J. Richter <adam@yggdrasil.com>

Please send any credits updates or corrections to:
Herbert Xu <herbert@gondor.apana.org.au>


code:
Key-agreement Protocol Primitives (KPP) Cipher Algorithm Definitions
--------------------------------------------------------------------

.. kernel-doc:: include/crypto/kpp.h
   :functions: kpp_request crypto_kpp kpp_alg kpp_secret

Key-agreement Protocol Primitives (KPP) Cipher API
--------------------------------------------------

.. kernel-doc:: include/crypto/kpp.h
   :doc: Generic Key-agreement Protocol Primitives API

.. kernel-doc:: include/crypto/kpp.h
   :functions: crypto_alloc_kpp crypto_free_kpp crypto_kpp_set_secret crypto_kpp_generate_public_key crypto_kpp_compute_shared_secret crypto_kpp_maxsize

Key-agreement Protocol Primitives (KPP) Cipher Request Handle
-------------------------------------------------------------

.. kernel-doc:: include/crypto/kpp.h
   :functions: kpp_request_alloc kpp_request_free kpp_request_set_callback kpp_request_set_input kpp_request_set_output

ECDH Helper Functions
---------------------

.. kernel-doc:: include/crypto/ecdh.h
   :doc: ECDH Helper Functions

.. kernel-doc:: include/crypto/ecdh.h
   :functions: ecdh crypto_ecdh_key_len crypto_ecdh_encode_key crypto_ecdh_decode_key

DH Helper Functions
-------------------

.. kernel-doc:: include/crypto/dh.h
   :doc: DH Helper Functions

.. kernel-doc:: include/crypto/dh.h
   :functions: dh crypto_dh_key_len crypto_dh_encode_key crypto_dh_decode_key


code:
Random Number Algorithm Definitions
-----------------------------------

.. kernel-doc:: include/crypto/rng.h
   :functions: rng_alg

Crypto API Random Number API
----------------------------

.. kernel-doc:: include/crypto/rng.h
   :doc: Random number generator API

.. kernel-doc:: include/crypto/rng.h
   :functions: crypto_alloc_rng crypto_rng_alg crypto_free_rng crypto_rng_generate crypto_rng_get_bytes crypto_rng_reset crypto_rng_seedsize


code:
Code Examples
=============

Code Example For Symmetric Key Cipher Operation
-----------------------------------------------

This code encrypts some data with AES-256-XTS.  For sake of example,
all inputs are random bytes, the encryption is done in-place, and it's
assumed the code is running in a context where it can sleep.

::

    static int test_skcipher(void)
    {
            struct crypto_skcipher *tfm = NULL;
            struct skcipher_request *req = NULL;
            u8 *data = NULL;
            const size_t datasize = 512; /* data size in bytes */
            struct scatterlist sg;
            DECLARE_CRYPTO_WAIT(wait);
            u8 iv[16];  /* AES-256-XTS takes a 16-byte IV */
            u8 key[64]; /* AES-256-XTS takes a 64-byte key */
            int err;

            /*
             * Allocate a tfm (a transformation object) and set the key.
             *
             * In real-world use, a tfm and key are typically used for many
             * encryption/decryption operations.  But in this example, we'll just do a
             * single encryption operation with it (which is not very efficient).
             */

            tfm = crypto_alloc_skcipher("xts(aes)", 0, 0);
            if (IS_ERR(tfm)) {
                    pr_err("Error allocating xts(aes) handle: %ld\n", PTR_ERR(tfm));
                    return PTR_ERR(tfm);
            }

            get_random_bytes(key, sizeof(key));
            err = crypto_skcipher_setkey(tfm, key, sizeof(key));
            if (err) {
                    pr_err("Error setting key: %d\n", err);
                    goto out;
            }

            /* Allocate a request object */
            req = skcipher_request_alloc(tfm, GFP_KERNEL);
            if (!req) {
                    err = -ENOMEM;
                    goto out;
            }

            /* Prepare the input data */
            data = kmalloc(datasize, GFP_KERNEL);
            if (!data) {
                    err = -ENOMEM;
                    goto out;
            }
            get_random_bytes(data, datasize);

            /* Initialize the IV */
            get_random_bytes(iv, sizeof(iv));

            /*
             * Encrypt the data in-place.
             *
             * For simplicity, in this example we wait for the request to complete
             * before proceeding, even if the underlying implementation is asynchronous.
             *
             * To decrypt instead of encrypt, just change crypto_skcipher_encrypt() to
             * crypto_skcipher_decrypt().
             */
            sg_init_one(&sg, data, datasize);
            skcipher_request_set_callback(req, CRYPTO_TFM_REQ_MAY_BACKLOG |
                                               CRYPTO_TFM_REQ_MAY_SLEEP,
                                          crypto_req_done, &wait);
            skcipher_request_set_crypt(req, &sg, &sg, datasize, iv);
            err = crypto_wait_req(crypto_skcipher_encrypt(req), &wait);
            if (err) {
                    pr_err("Error encrypting data: %d\n", err);
                    goto out;
            }

            pr_debug("Encryption was successful\n");
    out:
            crypto_free_skcipher(tfm);
            skcipher_request_free(req);
            kfree(data);
            return err;
    }

Code Example For Use of Operational State Memory With SHASH
-----------------------------------------------------------

::

    struct sdesc {
        struct shash_desc shash;
        char ctx[];
    };

    static struct sdesc *init_sdesc(struct crypto_shash *alg)
    {
        struct sdesc *sdesc;
        int size;

        size = sizeof(struct shash_desc) + crypto_shash_descsize(alg);
        sdesc = kmalloc(size, GFP_KERNEL);
        if (!sdesc)
            return ERR_PTR(-ENOMEM);
        sdesc->shash.tfm = alg;
        return sdesc;
    }

    static int calc_hash(struct crypto_shash *alg,
                 const unsigned char *data, unsigned int datalen,
                 unsigned char *digest)
    {
        struct sdesc *sdesc;
        int ret;

        sdesc = init_sdesc(alg);
        if (IS_ERR(sdesc)) {
            pr_info("can't alloc sdesc\n");
            return PTR_ERR(sdesc);
        }

        ret = crypto_shash_digest(&sdesc->shash, data, datalen, digest);
        kfree(sdesc);
        return ret;
    }

    static int test_hash(const unsigned char *data, unsigned int datalen,
                 unsigned char *digest)
    {
        struct crypto_shash *alg;
        char *hash_alg_name = "sha1-padlock-nano";
        int ret;

        alg = crypto_alloc_shash(hash_alg_name, 0, 0);
        if (IS_ERR(alg)) {
                pr_info("can't alloc alg %s\n", hash_alg_name);
                return PTR_ERR(alg);
        }
        ret = calc_hash(alg, data, datalen, digest);
        crypto_free_shash(alg);
        return ret;
    }

Code Example For Random Number Generator Usage
----------------------------------------------

::

    static int get_random_numbers(u8 *buf, unsigned int len)
    {
        struct crypto_rng *rng = NULL;
        char *drbg = "drbg_nopr_sha256"; /* Hash DRBG with SHA-256, no PR */
        int ret;

        if (!buf || !len) {
            pr_debug("No output buffer provided\n");
            return -EINVAL;
        }

        rng = crypto_alloc_rng(drbg, 0, 0);
        if (IS_ERR(rng)) {
            pr_debug("could not allocate RNG handle for %s\n", drbg);
            return PTR_ERR(rng);
        }

        ret = crypto_rng_get_bytes(rng, buf, len);
        if (ret < 0)
            pr_debug("generation of random numbers failed\n");
        else if (ret == 0)
            pr_debug("RNG returned no data");
        else
            pr_debug("RNG returned %d bytes of data\n", ret);

    out:
        crypto_free_rng(rng);
        return ret;
    }


code:
Block Cipher Algorithm Definitions
----------------------------------

.. kernel-doc:: include/linux/crypto.h
   :doc: Block Cipher Algorithm Definitions

.. kernel-doc:: include/linux/crypto.h
   :functions: crypto_alg cipher_alg compress_alg

Symmetric Key Cipher API
------------------------

.. kernel-doc:: include/crypto/skcipher.h
   :doc: Symmetric Key Cipher API

.. kernel-doc:: include/crypto/skcipher.h
   :functions: crypto_alloc_skcipher crypto_free_skcipher crypto_has_skcipher crypto_skcipher_ivsize crypto_skcipher_blocksize crypto_skcipher_setkey crypto_skcipher_reqtfm crypto_skcipher_encrypt crypto_skcipher_decrypt

Symmetric Key Cipher Request Handle
-----------------------------------

.. kernel-doc:: include/crypto/skcipher.h
   :doc: Symmetric Key Cipher Request Handle

.. kernel-doc:: include/crypto/skcipher.h
   :functions: crypto_skcipher_reqsize skcipher_request_set_tfm skcipher_request_alloc skcipher_request_free skcipher_request_set_callback skcipher_request_set_crypt

Single Block Cipher API
-----------------------

.. kernel-doc:: include/crypto/internal/cipher.h
   :doc: Single Block Cipher API

.. kernel-doc:: include/crypto/internal/cipher.h
   :functions: crypto_alloc_cipher crypto_free_cipher crypto_has_cipher crypto_cipher_blocksize crypto_cipher_setkey crypto_cipher_encrypt_one crypto_cipher_decrypt_one


code:
Programming Interface
=====================

.. class:: toc-title

	   Table of contents

.. toctree::
   :maxdepth: 2

   api-skcipher
   api-aead
   api-digest
   api-rng
   api-akcipher
   api-kpp


code:
Kernel Crypto API Architecture
==============================

Cipher algorithm types
----------------------

The kernel crypto API provides different API calls for the following
cipher types:

-  Symmetric ciphers

-  AEAD ciphers

-  Message digest, including keyed message digest

-  Random number generation

-  User space interface

Ciphers And Templates
---------------------

The kernel crypto API provides implementations of single block ciphers
and message digests. In addition, the kernel crypto API provides
numerous "templates" that can be used in conjunction with the single
block ciphers and message digests. Templates include all types of block
chaining mode, the HMAC mechanism, etc.

Single block ciphers and message digests can either be directly used by
a caller or invoked together with a template to form multi-block ciphers
or keyed message digests.

A single block cipher may even be called with multiple templates.
However, templates cannot be used without a single cipher.

See /proc/crypto and search for "name". For example:

-  aes

-  ecb(aes)

-  cmac(aes)

-  ccm(aes)

-  rfc4106(gcm(aes))

-  sha1

-  hmac(sha1)

-  authenc(hmac(sha1),cbc(aes))

In these examples, "aes" and "sha1" are the ciphers and all others are
the templates.

Synchronous And Asynchronous Operation
--------------------------------------

The kernel crypto API provides synchronous and asynchronous API
operations.

When using the synchronous API operation, the caller invokes a cipher
operation which is performed synchronously by the kernel crypto API.
That means, the caller waits until the cipher operation completes.
Therefore, the kernel crypto API calls work like regular function calls.
For synchronous operation, the set of API calls is small and
conceptually similar to any other crypto library.

Asynchronous operation is provided by the kernel crypto API which
implies that the invocation of a cipher operation will complete almost
instantly. That invocation triggers the cipher operation but it does not
signal its completion. Before invoking a cipher operation, the caller
must provide a callback function the kernel crypto API can invoke to
signal the completion of the cipher operation. Furthermore, the caller
must ensure it can handle such asynchronous events by applying
appropriate locking around its data. The kernel crypto API does not
perform any special serialization operation to protect the caller's data
integrity.

Crypto API Cipher References And Priority
-----------------------------------------

A cipher is referenced by the caller with a string. That string has the
following semantics:

::

        template(single block cipher)

where "template" and "single block cipher" is the aforementioned
template and single block cipher, respectively. If applicable,
additional templates may enclose other templates, such as

::

        template1(template2(single block cipher)))

The kernel crypto API may provide multiple implementations of a template
or a single block cipher. For example, AES on newer Intel hardware has
the following implementations: AES-NI, assembler implementation, or
straight C. Now, when using the string "aes" with the kernel crypto API,
which cipher implementation is used? The answer to that question is the
priority number assigned to each cipher implementation by the kernel
crypto API. When a caller uses the string to refer to a cipher during
initialization of a cipher handle, the kernel crypto API looks up all
implementations providing an implementation with that name and selects
the implementation with the highest priority.

Now, a caller may have the need to refer to a specific cipher
implementation and thus does not want to rely on the priority-based
selection. To accommodate this scenario, the kernel crypto API allows
the cipher implementation to register a unique name in addition to
common names. When using that unique name, a caller is therefore always
sure to refer to the intended cipher implementation.

The list of available ciphers is given in /proc/crypto. However, that
list does not specify all possible permutations of templates and
ciphers. Each block listed in /proc/crypto may contain the following
information -- if one of the components listed as follows are not
applicable to a cipher, it is not displayed:

-  name: the generic name of the cipher that is subject to the
   priority-based selection -- this name can be used by the cipher
   allocation API calls (all names listed above are examples for such
   generic names)

-  driver: the unique name of the cipher -- this name can be used by the
   cipher allocation API calls

-  module: the kernel module providing the cipher implementation (or
   "kernel" for statically linked ciphers)

-  priority: the priority value of the cipher implementation

-  refcnt: the reference count of the respective cipher (i.e. the number
   of current consumers of this cipher)

-  selftest: specification whether the self test for the cipher passed

-  type:

   -  skcipher for symmetric key ciphers

   -  cipher for single block ciphers that may be used with an
      additional template

   -  shash for synchronous message digest

   -  ahash for asynchronous message digest

   -  aead for AEAD cipher type

   -  compression for compression type transformations

   -  rng for random number generator

   -  kpp for a Key-agreement Protocol Primitive (KPP) cipher such as
      an ECDH or DH implementation

-  blocksize: blocksize of cipher in bytes

-  keysize: key size in bytes

-  ivsize: IV size in bytes

-  seedsize: required size of seed data for random number generator

-  digestsize: output size of the message digest

-  geniv: IV generator (obsolete)

Key Sizes
---------

When allocating a cipher handle, the caller only specifies the cipher
type. Symmetric ciphers, however, typically support multiple key sizes
(e.g. AES-128 vs. AES-192 vs. AES-256). These key sizes are determined
with the length of the provided key. Thus, the kernel crypto API does
not provide a separate way to select the particular symmetric cipher key
size.

Cipher Allocation Type And Masks
--------------------------------

The different cipher handle allocation functions allow the specification
of a type and mask flag. Both parameters have the following meaning (and
are therefore not covered in the subsequent sections).

The type flag specifies the type of the cipher algorithm. The caller
usually provides a 0 when the caller wants the default handling.
Otherwise, the caller may provide the following selections which match
the aforementioned cipher types:

-  CRYPTO_ALG_TYPE_CIPHER Single block cipher

-  CRYPTO_ALG_TYPE_COMPRESS Compression

-  CRYPTO_ALG_TYPE_AEAD Authenticated Encryption with Associated Data
   (MAC)

-  CRYPTO_ALG_TYPE_KPP Key-agreement Protocol Primitive (KPP) such as
   an ECDH or DH implementation

-  CRYPTO_ALG_TYPE_HASH Raw message digest

-  CRYPTO_ALG_TYPE_SHASH Synchronous multi-block hash

-  CRYPTO_ALG_TYPE_AHASH Asynchronous multi-block hash

-  CRYPTO_ALG_TYPE_RNG Random Number Generation

-  CRYPTO_ALG_TYPE_AKCIPHER Asymmetric cipher

-  CRYPTO_ALG_TYPE_PCOMPRESS Enhanced version of
   CRYPTO_ALG_TYPE_COMPRESS allowing for segmented compression /
   decompression instead of performing the operation on one segment
   only. CRYPTO_ALG_TYPE_PCOMPRESS is intended to replace
   CRYPTO_ALG_TYPE_COMPRESS once existing consumers are converted.

The mask flag restricts the type of cipher. The only allowed flag is
CRYPTO_ALG_ASYNC to restrict the cipher lookup function to
asynchronous ciphers. Usually, a caller provides a 0 for the mask flag.

When the caller provides a mask and type specification, the caller
limits the search the kernel crypto API can perform for a suitable
cipher implementation for the given cipher name. That means, even when a
caller uses a cipher name that exists during its initialization call,
the kernel crypto API may not select it due to the used type and mask
field.

Internal Structure of Kernel Crypto API
---------------------------------------

The kernel crypto API has an internal structure where a cipher
implementation may use many layers and indirections. This section shall
help to clarify how the kernel crypto API uses various components to
implement the complete cipher.

The following subsections explain the internal structure based on
existing cipher implementations. The first section addresses the most
complex scenario where all other scenarios form a logical subset.

Generic AEAD Cipher Structure
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The following ASCII art decomposes the kernel crypto API layers when
using the AEAD cipher with the automated IV generation. The shown
example is used by the IPSEC layer.

For other use cases of AEAD ciphers, the ASCII art applies as well, but
the caller may not use the AEAD cipher with a separate IV generator. In
this case, the caller must generate the IV.

The depicted example decomposes the AEAD cipher of GCM(AES) based on the
generic C implementations (gcm.c, aes-generic.c, ctr.c, ghash-generic.c,
seqiv.c). The generic implementation serves as an example showing the
complete logic of the kernel crypto API.

It is possible that some streamlined cipher implementations (like
AES-NI) provide implementations merging aspects which in the view of the
kernel crypto API cannot be decomposed into layers any more. In case of
the AES-NI implementation, the CTR mode, the GHASH implementation and
the AES cipher are all merged into one cipher implementation registered
with the kernel crypto API. In this case, the concept described by the
following ASCII art applies too. However, the decomposition of GCM into
the individual sub-components by the kernel crypto API is not done any
more.

Each block in the following ASCII art is an independent cipher instance
obtained from the kernel crypto API. Each block is accessed by the
caller or by other blocks using the API functions defined by the kernel
crypto API for the cipher implementation type.

The blocks below indicate the cipher type as well as the specific logic
implemented in the cipher.

The ASCII art picture also indicates the call structure, i.e. who calls
which component. The arrows point to the invoked block where the caller
uses the API applicable to the cipher type specified for the block.

::

    kernel crypto API                                |   IPSEC Layer
                                                     |
    +-----------+                                    |
    |           |            (1)
    |   aead    | <-----------------------------------  esp_output
    |  (seqiv)  | ---+
    +-----------+    |
                     | (2)
    +-----------+    |
    |           | <--+                (2)
    |   aead    | <-----------------------------------  esp_input
    |   (gcm)   | ------------+
    +-----------+             |
          | (3)               | (5)
          v                   v
    +-----------+       +-----------+
    |           |       |           |
    |  skcipher |       |   ahash   |
    |   (ctr)   | ---+  |  (ghash)  |
    +-----------+    |  +-----------+
                     |
    +-----------+    | (4)
    |           | <--+
    |   cipher  |
    |   (aes)   |
    +-----------+

The following call sequence is applicable when the IPSEC layer triggers
an encryption operation with the esp_output function. During
configuration, the administrator set up the use of seqiv(rfc4106(gcm(aes)))
as the cipher for ESP. The following call sequence is now depicted in
the ASCII art above:

1. esp_output() invokes crypto_aead_encrypt() to trigger an
   encryption operation of the AEAD cipher with IV generator.

   The SEQIV generates the IV.

2. Now, SEQIV uses the AEAD API function calls to invoke the associated
   AEAD cipher. In our case, during the instantiation of SEQIV, the
   cipher handle for GCM is provided to SEQIV. This means that SEQIV
   invokes AEAD cipher operations with the GCM cipher handle.

   During instantiation of the GCM handle, the CTR(AES) and GHASH
   ciphers are instantiated. The cipher handles for CTR(AES) and GHASH
   are retained for later use.

   The GCM implementation is responsible to invoke the CTR mode AES and
   the GHASH cipher in the right manner to implement the GCM
   specification.

3. The GCM AEAD cipher type implementation now invokes the SKCIPHER API
   with the instantiated CTR(AES) cipher handle.

   During instantiation of the CTR(AES) cipher, the CIPHER type
   implementation of AES is instantiated. The cipher handle for AES is
   retained.

   That means that the SKCIPHER implementation of CTR(AES) only
   implements the CTR block chaining mode. After performing the block
   chaining operation, the CIPHER implementation of AES is invoked.

4. The SKCIPHER of CTR(AES) now invokes the CIPHER API with the AES
   cipher handle to encrypt one block.

5. The GCM AEAD implementation also invokes the GHASH cipher
   implementation via the AHASH API.

When the IPSEC layer triggers the esp_input() function, the same call
sequence is followed with the only difference that the operation starts
with step (2).

Generic Block Cipher Structure
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Generic block ciphers follow the same concept as depicted with the ASCII
art picture above.

For example, CBC(AES) is implemented with cbc.c, and aes-generic.c. The
ASCII art picture above applies as well with the difference that only
step (4) is used and the SKCIPHER block chaining mode is CBC.

Generic Keyed Message Digest Structure
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Keyed message digest implementations again follow the same concept as
depicted in the ASCII art picture above.

For example, HMAC(SHA256) is implemented with hmac.c and
sha256_generic.c. The following ASCII art illustrates the
implementation:

::

    kernel crypto API            |       Caller
                                 |
    +-----------+         (1)    |
    |           | <------------------  some_function
    |   ahash   |
    |   (hmac)  | ---+
    +-----------+    |
                     | (2)
    +-----------+    |
    |           | <--+
    |   shash   |
    |  (sha256) |
    +-----------+

The following call sequence is applicable when a caller triggers an HMAC
operation:

1. The AHASH API functions are invoked by the caller. The HMAC
   implementation performs its operation as needed.

   During initialization of the HMAC cipher, the SHASH cipher type of
   SHA256 is instantiated. The cipher handle for the SHA256 instance is
   retained.

   At one time, the HMAC implementation requires a SHA256 operation
   where the SHA256 cipher handle is used.

2. The HMAC instance now invokes the SHASH API with the SHA256 cipher
   handle to calculate the message digest.


code:
.. SPDX-License-Identifier: GPL-2.0

=============================================
Asymmetric / Public-key Cryptography Key Type
=============================================

.. Contents:

  - Overview.
  - Key identification.
  - Accessing asymmetric keys.
    - Signature verification.
  - Asymmetric key subtypes.
  - Instantiation data parsers.
  - Keyring link restrictions.

Overview
========

The "asymmetric" key type is designed to be a container for the keys used in
public-key cryptography, without imposing any particular restrictions on the
form or mechanism of the cryptography or form of the key.

The asymmetric key is given a subtype that defines what sort of data is
associated with the key and provides operations to describe and destroy it.
However, no requirement is made that the key data actually be stored in the
key.

A completely in-kernel key retention and operation subtype can be defined, but
it would also be possible to provide access to cryptographic hardware (such as
a TPM) that might be used to both retain the relevant key and perform
operations using that key.  In such a case, the asymmetric key would then
merely be an interface to the TPM driver.

Also provided is the concept of a data parser.  Data parsers are responsible
for extracting information from the blobs of data passed to the instantiation
function.  The first data parser that recognises the blob gets to set the
subtype of the key and define the operations that can be done on that key.

A data parser may interpret the data blob as containing the bits representing a
key, or it may interpret it as a reference to a key held somewhere else in the
system (for example, a TPM).

Key Identification
==================

If a key is added with an empty name, the instantiation data parsers are given
the opportunity to pre-parse a key and to determine the description the key
should be given from the content of the key.

This can then be used to refer to the key, either by complete match or by
partial match.  The key type may also use other criteria to refer to a key.

The asymmetric key type's match function can then perform a wider range of
comparisons than just the straightforward comparison of the description with
the criterion string:

  1) If the criterion string is of the form "id:<hexdigits>" then the match
     function will examine a key's fingerprint to see if the hex digits given
     after the "id:" match the tail.  For instance::

	keyctl search @s asymmetric id:5acc2142

     will match a key with fingerprint::

	1A00 2040 7601 7889 DE11  882C 3823 04AD 5ACC 2142

  2) If the criterion string is of the form "<subtype>:<hexdigits>" then the
     match will match the ID as in (1), but with the added restriction that
     only keys of the specified subtype (e.g. tpm) will be matched.  For
     instance::

	keyctl search @s asymmetric tpm:5acc2142

Looking in /proc/keys, the last 8 hex digits of the key fingerprint are
displayed, along with the subtype::

	1a39e171 I-----     1 perm 3f010000     0     0 asymmetric modsign.0: DSA 5acc2142 []

Accessing Asymmetric Keys
=========================

For general access to asymmetric keys from within the kernel, the following
inclusion is required::

	#include <crypto/public_key.h>

This gives access to functions for dealing with asymmetric / public keys.
Three enums are defined there for representing public-key cryptography
algorithms::

	enum pkey_algo

digest algorithms used by those::

	enum pkey_hash_algo

and key identifier representations::

	enum pkey_id_type

Note that the key type representation types are required because key
identifiers from different standards aren't necessarily compatible.  For
instance, PGP generates key identifiers by hashing the key data plus some
PGP-specific metadata, whereas X.509 has arbitrary certificate identifiers.

The operations defined upon a key are:

  1) Signature verification.

Other operations are possible (such as encryption) with the same key data
required for verification, but not currently supported, and others
(eg. decryption and signature generation) require extra key data.

Signature Verification
----------------------

An operation is provided to perform cryptographic signature verification, using
an asymmetric key to provide or to provide access to the public key::

	int verify_signature(const struct key *key,
			     const struct public_key_signature *sig);

The caller must have already obtained the key from some source and can then use
it to check the signature.  The caller must have parsed the signature and
transferred the relevant bits to the structure pointed to by sig::

	struct public_key_signature {
		u8 *digest;
		u8 digest_size;
		enum pkey_hash_algo pkey_hash_algo : 8;
		u8 nr_mpi;
		union {
			MPI mpi[2];
			...
		};
	};

The algorithm used must be noted in sig->pkey_hash_algo, and all the MPIs that
make up the actual signature must be stored in sig->mpi[] and the count of MPIs
placed in sig->nr_mpi.

In addition, the data must have been digested by the caller and the resulting
hash must be pointed to by sig->digest and the size of the hash be placed in
sig->digest_size.

The function will return 0 upon success or -EKEYREJECTED if the signature
doesn't match.

The function may also return -ENOTSUPP if an unsupported public-key algorithm
or public-key/hash algorithm combination is specified or the key doesn't
support the operation; -EBADMSG or -ERANGE if some of the parameters have weird
data; or -ENOMEM if an allocation can't be performed.  -EINVAL can be returned
if the key argument is the wrong type or is incompletely set up.

Asymmetric Key Subtypes
=======================

Asymmetric keys have a subtype that defines the set of operations that can be
performed on that key and that determines what data is attached as the key
payload.  The payload format is entirely at the whim of the subtype.

The subtype is selected by the key data parser and the parser must initialise
the data required for it.  The asymmetric key retains a reference on the
subtype module.

The subtype definition structure can be found in::

	#include <keys/asymmetric-subtype.h>

and looks like the following::

	struct asymmetric_key_subtype {
		struct module		*owner;
		const char		*name;

		void (*describe)(const struct key *key, struct seq_file *m);
		void (*destroy)(void *payload);
		int (*query)(const struct kernel_pkey_params *params,
			     struct kernel_pkey_query *info);
		int (*eds_op)(struct kernel_pkey_params *params,
			      const void *in, void *out);
		int (*verify_signature)(const struct key *key,
					const struct public_key_signature *sig);
	};

Asymmetric keys point to this with their payload[asym_subtype] member.

The owner and name fields should be set to the owning module and the name of
the subtype.  Currently, the name is only used for print statements.

There are a number of operations defined by the subtype:

  1) describe().

     Mandatory.  This allows the subtype to display something in /proc/keys
     against the key.  For instance the name of the public key algorithm type
     could be displayed.  The key type will display the tail of the key
     identity string after this.

  2) destroy().

     Mandatory.  This should free the memory associated with the key.  The
     asymmetric key will look after freeing the fingerprint and releasing the
     reference on the subtype module.

  3) query().

     Mandatory.  This is a function for querying the capabilities of a key.

  4) eds_op().

     Optional.  This is the entry point for the encryption, decryption and
     signature creation operations (which are distinguished by the operation ID
     in the parameter struct).  The subtype may do anything it likes to
     implement an operation, including offloading to hardware.

  5) verify_signature().

     Optional.  This is the entry point for signature verification.  The
     subtype may do anything it likes to implement an operation, including
     offloading to hardware.

Instantiation Data Parsers
==========================

The asymmetric key type doesn't generally want to store or to deal with a raw
blob of data that holds the key data.  It would have to parse it and error
check it each time it wanted to use it.  Further, the contents of the blob may
have various checks that can be performed on it (eg. self-signatures, validity
dates) and may contain useful data about the key (identifiers, capabilities).

Also, the blob may represent a pointer to some hardware containing the key
rather than the key itself.

Examples of blob formats for which parsers could be implemented include:

 - OpenPGP packet stream [RFC 4880].
 - X.509 ASN.1 stream.
 - Pointer to TPM key.
 - Pointer to UEFI key.
 - PKCS#8 private key [RFC 5208].
 - PKCS#5 encrypted private key [RFC 2898].

During key instantiation each parser in the list is tried until one doesn't
return -EBADMSG.

The parser definition structure can be found in::

	#include <keys/asymmetric-parser.h>

and looks like the following::

	struct asymmetric_key_parser {
		struct module	*owner;
		const char	*name;

		int (*parse)(struct key_preparsed_payload *prep);
	};

The owner and name fields should be set to the owning module and the name of
the parser.

There is currently only a single operation defined by the parser, and it is
mandatory:

  1) parse().

     This is called to preparse the key from the key creation and update paths.
     In particular, it is called during the key creation _before_ a key is
     allocated, and as such, is permitted to provide the key's description in
     the case that the caller declines to do so.

     The caller passes a pointer to the following struct with all of the fields
     cleared, except for data, datalen and quotalen [see
     Documentation/security/keys/core.rst]::

	struct key_preparsed_payload {
		char		*description;
		void		*payload[4];
		const void	*data;
		size_t		datalen;
		size_t		quotalen;
	};

     The instantiation data is in a blob pointed to by data and is datalen in
     size.  The parse() function is not permitted to change these two values at
     all, and shouldn't change any of the other values _unless_ they are
     recognise the blob format and will not return -EBADMSG to indicate it is
     not theirs.

     If the parser is happy with the blob, it should propose a description for
     the key and attach it to ->description, ->payload[asym_subtype] should be
     set to point to the subtype to be used, ->payload[asym_crypto] should be
     set to point to the initialised data for that subtype,
     ->payload[asym_key_ids] should point to one or more hex fingerprints and
     quotalen should be updated to indicate how much quota this key should
     account for.

     When clearing up, the data attached to ->payload[asym_key_ids] and
     ->description will be kfree()'d and the data attached to
     ->payload[asm_crypto] will be passed to the subtype's ->destroy() method
     to be disposed of.  A module reference for the subtype pointed to by
     ->payload[asym_subtype] will be put.

     If the data format is not recognised, -EBADMSG should be returned.  If it
     is recognised, but the key cannot for some reason be set up, some other
     negative error code should be returned.  On success, 0 should be returned.

     The key's fingerprint string may be partially matched upon.  For a
     public-key algorithm such as RSA and DSA this will likely be a printable
     hex version of the key's fingerprint.

Functions are provided to register and unregister parsers::

	int register_asymmetric_key_parser(struct asymmetric_key_parser *parser);
	void unregister_asymmetric_key_parser(struct asymmetric_key_parser *subtype);

Parsers may not have the same name.  The names are otherwise only used for
displaying in debugging messages.

Keyring Link Restrictions
=========================

Keyrings created from userspace using add_key can be configured to check the
signature of the key being linked.  Keys without a valid signature are not
allowed to link.

Several restriction methods are available:

  1) Restrict using the kernel builtin trusted keyring

     - Option string used with KEYCTL_RESTRICT_KEYRING:
       - "builtin_trusted"

     The kernel builtin trusted keyring will be searched for the signing key.
     If the builtin trusted keyring is not configured, all links will be
     rejected.  The ca_keys kernel parameter also affects which keys are used
     for signature verification.

  2) Restrict using the kernel builtin and secondary trusted keyrings

     - Option string used with KEYCTL_RESTRICT_KEYRING:
       - "builtin_and_secondary_trusted"

     The kernel builtin and secondary trusted keyrings will be searched for the
     signing key.  If the secondary trusted keyring is not configured, this
     restriction will behave like the "builtin_trusted" option.  The ca_keys
     kernel parameter also affects which keys are used for signature
     verification.

  3) Restrict using a separate key or keyring

     - Option string used with KEYCTL_RESTRICT_KEYRING:
       - "key_or_keyring:<key or keyring serial number>[:chain]"

     Whenever a key link is requested, the link will only succeed if the key
     being linked is signed by one of the designated keys.  This key may be
     specified directly by providing a serial number for one asymmetric key, or
     a group of keys may be searched for the signing key by providing the
     serial number for a keyring.

     When the "chain" option is provided at the end of the string, the keys
     within the destination keyring will also be searched for signing keys.
     This allows for verification of certificate chains by adding each
     certificate in order (starting closest to the root) to a keyring.  For
     instance, one keyring can be populated with links to a set of root
     certificates, with a separate, restricted keyring set up for each
     certificate chain to be validated::

	# Create and populate a keyring for root certificates
	root_id=`keyctl add keyring root-certs "" @s`
	keyctl padd asymmetric "" $root_id < root1.cert
	keyctl padd asymmetric "" $root_id < root2.cert

	# Create and restrict a keyring for the certificate chain
	chain_id=`keyctl add keyring chain "" @s`
	keyctl restrict_keyring $chain_id asymmetric key_or_keyring:$root_id:chain

	# Attempt to add each certificate in the chain, starting with the
	# certificate closest to the root.
	keyctl padd asymmetric "" $chain_id < intermediateA.cert
	keyctl padd asymmetric "" $chain_id < intermediateB.cert
	keyctl padd asymmetric "" $chain_id < end-entity.cert

     If the final end-entity certificate is successfully added to the "chain"
     keyring, we can be certain that it has a valid signing chain going back to
     one of the root certificates.

     A single keyring can be used to verify a chain of signatures by
     restricting the keyring after linking the root certificate::

	# Create a keyring for the certificate chain and add the root
	chain2_id=`keyctl add keyring chain2 "" @s`
	keyctl padd asymmetric "" $chain2_id < root1.cert

	# Restrict the keyring that already has root1.cert linked.  The cert
	# will remain linked by the keyring.
	keyctl restrict_keyring $chain2_id asymmetric key_or_keyring:0:chain

	# Attempt to add each certificate in the chain, starting with the
	# certificate closest to the root.
	keyctl padd asymmetric "" $chain2_id < intermediateA.cert
	keyctl padd asymmetric "" $chain2_id < intermediateB.cert
	keyctl padd asymmetric "" $chain2_id < end-entity.cert

     If the final end-entity certificate is successfully added to the "chain2"
     keyring, we can be certain that there is a valid signing chain going back
     to the root certificate that was added before the keyring was restricted.

In all of these cases, if the signing key is found the signature of the key to
be linked will be verified using the signing key.  The requested key is added
to the keyring only if the signature is successfully verified.  -ENOKEY is
returned if the parent certificate could not be found, or -EKEYREJECTED is
returned if the signature check fails or the key is blacklisted.  Other errors
may be returned if the signature check could not be performed.


code:
.. SPDX-License-Identifier: GPL-2.0

=====================================
Asynchronous Transfers/Transforms API
=====================================

.. Contents

  1. INTRODUCTION

  2 GENEALOGY

  3 USAGE
  3.1 General format of the API
  3.2 Supported operations
  3.3 Descriptor management
  3.4 When does the operation execute?
  3.5 When does the operation complete?
  3.6 Constraints
  3.7 Example

  4 DMAENGINE DRIVER DEVELOPER NOTES
  4.1 Conformance points
  4.2 "My application needs exclusive control of hardware channels"

  5 SOURCE

1. Introduction
===============

The async_tx API provides methods for describing a chain of asynchronous
bulk memory transfers/transforms with support for inter-transactional
dependencies.  It is implemented as a dmaengine client that smooths over
the details of different hardware offload engine implementations.  Code
that is written to the API can optimize for asynchronous operation and
the API will fit the chain of operations to the available offload
resources.

2.Genealogy
===========

The API was initially designed to offload the memory copy and
xor-parity-calculations of the md-raid5 driver using the offload engines
present in the Intel(R) Xscale series of I/O processors.  It also built
on the 'dmaengine' layer developed for offloading memory copies in the
network stack using Intel(R) I/OAT engines.  The following design
features surfaced as a result:

1. implicit synchronous path: users of the API do not need to know if
   the platform they are running on has offload capabilities.  The
   operation will be offloaded when an engine is available and carried out
   in software otherwise.
2. cross channel dependency chains: the API allows a chain of dependent
   operations to be submitted, like xor->copy->xor in the raid5 case.  The
   API automatically handles cases where the transition from one operation
   to another implies a hardware channel switch.
3. dmaengine extensions to support multiple clients and operation types
   beyond 'memcpy'

3. Usage
========

3.1 General format of the API
-----------------------------

::

  struct dma_async_tx_descriptor *
  async_<operation>(<op specific parameters>, struct async_submit ctl *submit)

3.2 Supported operations
------------------------

========  ====================================================================
memcpy    memory copy between a source and a destination buffer
memset    fill a destination buffer with a byte value
xor       xor a series of source buffers and write the result to a
	  destination buffer
xor_val   xor a series of source buffers and set a flag if the
	  result is zero.  The implementation attempts to prevent
	  writes to memory
pq	  generate the p+q (raid6 syndrome) from a series of source buffers
pq_val    validate that a p and or q buffer are in sync with a given series of
	  sources
datap	  (raid6_datap_recov) recover a raid6 data block and the p block
	  from the given sources
2data	  (raid6_2data_recov) recover 2 raid6 data blocks from the given
	  sources
========  ====================================================================

3.3 Descriptor management
-------------------------

The return value is non-NULL and points to a 'descriptor' when the operation
has been queued to execute asynchronously.  Descriptors are recycled
resources, under control of the offload engine driver, to be reused as
operations complete.  When an application needs to submit a chain of
operations it must guarantee that the descriptor is not automatically recycled
before the dependency is submitted.  This requires that all descriptors be
acknowledged by the application before the offload engine driver is allowed to
recycle (or free) the descriptor.  A descriptor can be acked by one of the
following methods:

1. setting the ASYNC_TX_ACK flag if no child operations are to be submitted
2. submitting an unacknowledged descriptor as a dependency to another
   async_tx call will implicitly set the acknowledged state.
3. calling async_tx_ack() on the descriptor.

3.4 When does the operation execute?
------------------------------------

Operations do not immediately issue after return from the
async_<operation> call.  Offload engine drivers batch operations to
improve performance by reducing the number of mmio cycles needed to
manage the channel.  Once a driver-specific threshold is met the driver
automatically issues pending operations.  An application can force this
event by calling async_tx_issue_pending_all().  This operates on all
channels since the application has no knowledge of channel to operation
mapping.

3.5 When does the operation complete?
-------------------------------------

There are two methods for an application to learn about the completion
of an operation.

1. Call dma_wait_for_async_tx().  This call causes the CPU to spin while
   it polls for the completion of the operation.  It handles dependency
   chains and issuing pending operations.
2. Specify a completion callback.  The callback routine runs in tasklet
   context if the offload engine driver supports interrupts, or it is
   called in application context if the operation is carried out
   synchronously in software.  The callback can be set in the call to
   async_<operation>, or when the application needs to submit a chain of
   unknown length it can use the async_trigger_callback() routine to set a
   completion interrupt/callback at the end of the chain.

3.6 Constraints
---------------

1. Calls to async_<operation> are not permitted in IRQ context.  Other
   contexts are permitted provided constraint #2 is not violated.
2. Completion callback routines cannot submit new operations.  This
   results in recursion in the synchronous case and spin_locks being
   acquired twice in the asynchronous case.

3.7 Example
-----------

Perform a xor->copy->xor operation where each operation depends on the
result from the previous operation::

    void callback(void *param)
    {
	    struct completion *cmp = param;

	    complete(cmp);
    }

    void run_xor_copy_xor(struct page **xor_srcs,
			int xor_src_cnt,
			struct page *xor_dest,
			size_t xor_len,
			struct page *copy_src,
			struct page *copy_dest,
			size_t copy_len)
    {
	    struct dma_async_tx_descriptor *tx;
	    addr_conv_t addr_conv[xor_src_cnt];
	    struct async_submit_ctl submit;
	    addr_conv_t addr_conv[NDISKS];
	    struct completion cmp;

	    init_async_submit(&submit, ASYNC_TX_XOR_DROP_DST, NULL, NULL, NULL,
			    addr_conv);
	    tx = async_xor(xor_dest, xor_srcs, 0, xor_src_cnt, xor_len, &submit)

	    submit->depend_tx = tx;
	    tx = async_memcpy(copy_dest, copy_src, 0, 0, copy_len, &submit);

	    init_completion(&cmp);
	    init_async_submit(&submit, ASYNC_TX_XOR_DROP_DST | ASYNC_TX_ACK, tx,
			    callback, &cmp, addr_conv);
	    tx = async_xor(xor_dest, xor_srcs, 0, xor_src_cnt, xor_len, &submit);

	    async_tx_issue_pending_all();

	    wait_for_completion(&cmp);
    }

See include/linux/async_tx.h for more information on the flags.  See the
ops_run_* and ops_complete_* routines in drivers/md/raid5.c for more
implementation examples.

4. Driver Development Notes
===========================

4.1 Conformance points
----------------------

There are a few conformance points required in dmaengine drivers to
accommodate assumptions made by applications using the async_tx API:

1. Completion callbacks are expected to happen in tasklet context
2. dma_async_tx_descriptor fields are never manipulated in IRQ context
3. Use async_tx_run_dependencies() in the descriptor clean up path to
   handle submission of dependent operations

4.2 "My application needs exclusive control of hardware channels"
-----------------------------------------------------------------

Primarily this requirement arises from cases where a DMA engine driver
is being used to support device-to-memory operations.  A channel that is
performing these operations cannot, for many platform specific reasons,
be shared.  For these cases the dma_request_channel() interface is
provided.

The interface is::

  struct dma_chan *dma_request_channel(dma_cap_mask_t mask,
				       dma_filter_fn filter_fn,
				       void *filter_param);

Where dma_filter_fn is defined as::

  typedef bool (*dma_filter_fn)(struct dma_chan *chan, void *filter_param);

When the optional 'filter_fn' parameter is set to NULL
dma_request_channel simply returns the first channel that satisfies the
capability mask.  Otherwise, when the mask parameter is insufficient for
specifying the necessary channel, the filter_fn routine can be used to
disposition the available channels in the system. The filter_fn routine
is called once for each free channel in the system.  Upon seeing a
suitable channel filter_fn returns DMA_ACK which flags that channel to
be the return value from dma_request_channel.  A channel allocated via
this interface is exclusive to the caller, until dma_release_channel()
is called.

The DMA_PRIVATE capability flag is used to tag dma devices that should
not be used by the general-purpose allocator.  It can be set at
initialization time if it is known that a channel will always be
private.  Alternatively, it is set when dma_request_channel() finds an
unused "public" channel.

A couple caveats to note when implementing a driver and consumer:

1. Once a channel has been privately allocated it will no longer be
   considered by the general-purpose allocator even after a call to
   dma_release_channel().
2. Since capabilities are specified at the device level a dma_device
   with multiple channels will either have all channels public, or all
   channels private.

5. Source
---------

include/linux/dmaengine.h:
    core header file for DMA drivers and api users
drivers/dma/dmaengine.c:
    offload engine channel management routines
drivers/dma/:
    location for offload engine drivers
include/linux/async_tx.h:
    core header file for the async_tx api
crypto/async_tx/async_tx.c:
    async_tx interface to dmaengine and common code
crypto/async_tx/async_memcpy.c:
    copy offload
crypto/async_tx/async_xor.c:
    xor and xor zero sum offload


code:
.. SPDX-License-Identifier: GPL-2.0

Crypto Engine
=============

Overview
--------
The crypto engine (CE) API is a crypto queue manager.

Requirement
-----------
You must put, at the start of your transform context your_tfm_ctx, the structure
crypto_engine:

::

	struct your_tfm_ctx {
		struct crypto_engine engine;
		...
	};

The crypto engine only manages asynchronous requests in the form of
crypto_async_request. It cannot know the underlying request type and thus only
has access to the transform structure. It is not possible to access the context
using container_of. In addition, the engine knows nothing about your
structure "``struct your_tfm_ctx``". The engine assumes (requires) the placement
of the known member ``struct crypto_engine`` at the beginning.

Order of operations
-------------------
You are required to obtain a struct crypto_engine via ``crypto_engine_alloc_init()``.
Start it via ``crypto_engine_start()``. When finished with your work, shut down the
engine using ``crypto_engine_stop()`` and destroy the engine with
``crypto_engine_exit()``.

Before transferring any request, you have to fill the context enginectx by
providing functions for the following:

* ``prepare_crypt_hardware``: Called once before any prepare functions are
  called.

* ``unprepare_crypt_hardware``: Called once after all unprepare functions have
  been called.

* ``prepare_cipher_request``/``prepare_hash_request``: Called before each
  corresponding request is performed. If some processing or other preparatory
  work is required, do it here.

* ``unprepare_cipher_request``/``unprepare_hash_request``: Called after each
  request is handled. Clean up / undo what was done in the prepare function.

* ``cipher_one_request``/``hash_one_request``: Handle the current request by
  performing the operation.

Note that these functions access the crypto_async_request structure
associated with the received request. You are able to retrieve the original
request by using:

::

	container_of(areq, struct yourrequesttype_request, base);

When your driver receives a crypto_request, you must to transfer it to
the crypto engine via one of:

* crypto_transfer_aead_request_to_engine()

* crypto_transfer_akcipher_request_to_engine()

* crypto_transfer_hash_request_to_engine()

* crypto_transfer_kpp_request_to_engine()

* crypto_transfer_skcipher_request_to_engine()

At the end of the request process, a call to one of the following functions is needed:

* crypto_finalize_aead_request()

* crypto_finalize_akcipher_request()

* crypto_finalize_hash_request()

* crypto_finalize_kpp_request()

* crypto_finalize_skcipher_request()


code:
.. SPDX-License-Identifier: GPL-2.0
.. include:: <isonum.txt>

===========================================
Fast & Portable DES encryption & decryption
===========================================

.. note::

   Below is the original README file from the descore.shar package,
   converted to ReST format.

------------------------------------------------------------------------------

des - fast & portable DES encryption & decryption.

Copyright |copy| 1992  Dana L. How

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Library General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Library General Public License for more details.

You should have received a copy of the GNU Library General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

Author's address: how@isl.stanford.edu

.. README,v 1.15 1992/05/20 00:25:32 how E

==>> To compile after untarring/unsharring, just ``make`` <<==

This package was designed with the following goals:

1.	Highest possible encryption/decryption PERFORMANCE.
2.	PORTABILITY to any byte-addressable host with a 32bit unsigned C type
3.	Plug-compatible replacement for KERBEROS's low-level routines.

This second release includes a number of performance enhancements for
register-starved machines.  My discussions with Richard Outerbridge,
71755.204@compuserve.com, sparked a number of these enhancements.

To more rapidly understand the code in this package, inspect desSmallFips.i
(created by typing ``make``) BEFORE you tackle desCode.h.  The latter is set
up in a parameterized fashion so it can easily be modified by speed-daemon
hackers in pursuit of that last microsecond.  You will find it more
illuminating to inspect one specific implementation,
and then move on to the common abstract skeleton with this one in mind.

performance comparison to other available des code which i could
compile on a SPARCStation 1 (cc -O4, gcc -O2):

this code (byte-order independent):

  - 30us per encryption (options: 64k tables, no IP/FP)
  - 33us per encryption (options: 64k tables, FIPS standard bit ordering)
  - 45us per encryption (options:  2k tables, no IP/FP)
  - 48us per encryption (options:  2k tables, FIPS standard bit ordering)
  - 275us to set a new key (uses 1k of key tables)

	this has the quickest encryption/decryption routines i've seen.
	since i was interested in fast des filters rather than crypt(3)
	and password cracking, i haven't really bothered yet to speed up
	the key setting routine. also, i have no interest in re-implementing
	all the other junk in the mit kerberos des library, so i've just
	provided my routines with little stub interfaces so they can be
	used as drop-in replacements with mit's code or any of the mit-
	compatible packages below. (note that the first two timings above
	are highly variable because of cache effects).

kerberos des replacement from australia (version 1.95):

  - 53us per encryption (uses 2k of tables)
  - 96us to set a new key (uses 2.25k of key tables)

	so despite the author's inclusion of some of the performance
	improvements i had suggested to him, this package's
	encryption/decryption is still slower on the sparc and 68000.
	more specifically, 19-40% slower on the 68020 and 11-35% slower
	on the sparc,  depending on the compiler;
	in full gory detail (ALT_ECB is a libdes variant):

	===============	==============	===============	=================
	compiler   	machine		desCore	libdes	ALT_ECB	slower by
	===============	==============	===============	=================
	gcc 2.1 -O2	Sun 3/110	304  uS	369.5uS	461.8uS	 22%
	cc      -O1	Sun 3/110	336  uS	436.6uS	399.3uS	 19%
	cc      -O2	Sun 3/110	360  uS	532.4uS	505.1uS	 40%
	cc      -O4	Sun 3/110	365  uS	532.3uS	505.3uS	 38%
	gcc 2.1 -O2	Sun 4/50	 48  uS	 53.4uS	 57.5uS	 11%
	cc      -O2	Sun 4/50	 48  uS	 64.6uS	 64.7uS	 35%
	cc      -O4	Sun 4/50	 48  uS	 64.7uS	 64.9uS	 35%
	===============	==============	===============	=================

	(my time measurements are not as accurate as his).

   the comments in my first release of desCore on version 1.92:

   - 68us per encryption (uses 2k of tables)
   - 96us to set a new key (uses 2.25k of key tables)

	this is a very nice package which implements the most important
	of the optimizations which i did in my encryption routines.
	it's a bit weak on common low-level optimizations which is why
	it's 39%-106% slower.  because he was interested in fast crypt(3) and
	password-cracking applications,  he also used the same ideas to
	speed up the key-setting routines with impressive results.
	(at some point i may do the same in my package).  he also implements
	the rest of the mit des library.

	(code from eay@psych.psy.uq.oz.au via comp.sources.misc)

fast crypt(3) package from denmark:

	the des routine here is buried inside a loop to do the
	crypt function and i didn't feel like ripping it out and measuring
	performance. his code takes 26 sparc instructions to compute one
	des iteration; above, Quick (64k) takes 21 and Small (2k) takes 37.
	he claims to use 280k of tables but the iteration calculation seems
	to use only 128k.  his tables and code are machine independent.

	(code from glad@daimi.aau.dk via alt.sources or comp.sources.misc)

swedish reimplementation of Kerberos des library

  - 108us per encryption (uses 34k worth of tables)
  - 134us to set a new key (uses 32k of key tables to get this speed!)

	the tables used seem to be machine-independent;
	he seems to have included a lot of special case code
	so that, e.g., ``long`` loads can be used instead of 4 ``char`` loads
	when the machine's architecture allows it.

	(code obtained from chalmers.se:pub/des)

crack 3.3c package from england:

	as in crypt above, the des routine is buried in a loop. it's
	also very modified for crypt.  his iteration code uses 16k
	of tables and appears to be slow.

	(code obtained from aem@aber.ac.uk via alt.sources or comp.sources.misc)

``highly optimized`` and tweaked Kerberos/Athena code (byte-order dependent):

  - 165us per encryption (uses 6k worth of tables)
  - 478us to set a new key (uses <1k of key tables)

	so despite the comments in this code, it was possible to get
	faster code AND smaller tables, as well as making the tables
	machine-independent.
	(code obtained from prep.ai.mit.edu)

UC Berkeley code (depends on machine-endedness):
  -  226us per encryption
  - 10848us to set a new key

	table sizes are unclear, but they don't look very small
	(code obtained from wuarchive.wustl.edu)

motivation and history
======================

a while ago i wanted some des routines and the routines documented on sun's
man pages either didn't exist or dumped core.  i had heard of kerberos,
and knew that it used des,  so i figured i'd use its routines.  but once
i got it and looked at the code,  it really set off a lot of pet peeves -
it was too convoluted, the code had been written without taking
advantage of the regular structure of operations such as IP, E, and FP
(i.e. the author didn't sit down and think before coding),
it was excessively slow,  the author had attempted to clarify the code
by adding MORE statements to make the data movement more ``consistent``
instead of simplifying his implementation and cutting down on all data
movement (in particular, his use of L1, R1, L2, R2), and it was full of
idiotic ``tweaks`` for particular machines which failed to deliver significant
speedups but which did obfuscate everything.  so i took the test data
from his verification program and rewrote everything else.

a while later i ran across the great crypt(3) package mentioned above.
the fact that this guy was computing 2 sboxes per table lookup rather
than one (and using a MUCH larger table in the process) emboldened me to
do the same - it was a trivial change from which i had been scared away
by the larger table size.  in his case he didn't realize you don't need to keep
the working data in TWO forms, one for easy use of half the sboxes in
indexing, the other for easy use of the other half; instead you can keep
it in the form for the first half and use a simple rotate to get the other
half.  this means i have (almost) half the data manipulation and half
the table size.  in fairness though he might be encoding something particular
to crypt(3) in his tables - i didn't check.

i'm glad that i implemented it the way i did, because this C version is
portable (the ifdef's are performance enhancements) and it is faster
than versions hand-written in assembly for the sparc!

porting notes
=============

one thing i did not want to do was write an enormous mess
which depended on endedness and other machine quirks,
and which necessarily produced different code and different lookup tables
for different machines.  see the kerberos code for an example
of what i didn't want to do; all their endedness-specific ``optimizations``
obfuscate the code and in the end were slower than a simpler machine
independent approach.  however, there are always some portability
considerations of some kind, and i have included some options
for varying numbers of register variables.
perhaps some will still regard the result as a mess!

1) i assume everything is byte addressable, although i don't actually
   depend on the byte order, and that bytes are 8 bits.
   i assume word pointers can be freely cast to and from char pointers.
   note that 99% of C programs make these assumptions.
   i always use unsigned char's if the high bit could be set.
2) the typedef ``word`` means a 32 bit unsigned integral type.
   if ``unsigned long`` is not 32 bits, change the typedef in desCore.h.
   i assume sizeof(word) == 4 EVERYWHERE.

the (worst-case) cost of my NOT doing endedness-specific optimizations
in the data loading and storing code surrounding the key iterations
is less than 12%.  also, there is the added benefit that
the input and output work areas do not need to be word-aligned.

OPTIONAL performance optimizations
==================================

1) you should define one of ``i386,`` ``vax,`` ``mc68000,`` or ``sparc,``
   whichever one is closest to the capabilities of your machine.
   see the start of desCode.h to see exactly what this selection implies.
   note that if you select the wrong one, the des code will still work;
   these are just performance tweaks.
2) for those with functional ``asm`` keywords: you should change the
   ROR and ROL macros to use machine rotate instructions if you have them.
   this will save 2 instructions and a temporary per use,
   or about 32 to 40 instructions per en/decryption.

   note that gcc is smart enough to translate the ROL/R macros into
   machine rotates!

these optimizations are all rather persnickety, yet with them you should
be able to get performance equal to assembly-coding, except that:

1) with the lack of a bit rotate operator in C, rotates have to be synthesized
   from shifts.  so access to ``asm`` will speed things up if your machine
   has rotates, as explained above in (3) (not necessary if you use gcc).
2) if your machine has less than 12 32-bit registers i doubt your compiler will
   generate good code.

   ``i386`` tries to configure the code for a 386 by only declaring 3 registers
   (it appears that gcc can use ebx, esi and edi to hold register variables).
   however, if you like assembly coding, the 386 does have 7 32-bit registers,
   and if you use ALL of them, use ``scaled by 8`` address modes with displacement
   and other tricks, you can get reasonable routines for DesQuickCore... with
   about 250 instructions apiece.  For DesSmall... it will help to rearrange
   des_keymap, i.e., now the sbox # is the high part of the index and
   the 6 bits of data is the low part; it helps to exchange these.

   since i have no way to conveniently test it i have not provided my
   shoehorned 386 version.  note that with this release of desCore, gcc is able
   to put everything in registers(!), and generate about 370 instructions apiece
   for the DesQuickCore... routines!

coding notes
============

the en/decryption routines each use 6 necessary register variables,
with 4 being actively used at once during the inner iterations.
if you don't have 4 register variables get a new machine.
up to 8 more registers are used to hold constants in some configurations.

i assume that the use of a constant is more expensive than using a register:

a) additionally, i have tried to put the larger constants in registers.
   registering priority was by the following:

	- anything more than 12 bits (bad for RISC and CISC)
	- greater than 127 in value (can't use movq or byte immediate on CISC)
	- 9-127 (may not be able to use CISC shift immediate or add/sub quick),
	- 1-8 were never registered, being the cheapest constants.

b) the compiler may be too stupid to realize table and table+256 should
   be assigned to different constant registers and instead repetitively
   do the arithmetic, so i assign these to explicit ``m`` register variables
   when possible and helpful.

i assume that indexing is cheaper or equivalent to auto increment/decrement,
where the index is 7 bits unsigned or smaller.
this assumption is reversed for 68k and vax.

i assume that addresses can be cheaply formed from two registers,
or from a register and a small constant.
for the 68000, the ``two registers and small offset`` form is used sparingly.
all index scaling is done explicitly - no hidden shifts by log2(sizeof).

the code is written so that even a dumb compiler
should never need more than one hidden temporary,
increasing the chance that everything will fit in the registers.
KEEP THIS MORE SUBTLE POINT IN MIND IF YOU REWRITE ANYTHING.

(actually, there are some code fragments now which do require two temps,
but fixing it would either break the structure of the macros or
require declaring another temporary).

special efficient data format
==============================

bits are manipulated in this arrangement most of the time (S7 S5 S3 S1)::

	003130292827xxxx242322212019xxxx161514131211xxxx080706050403xxxx

(the x bits are still there, i'm just emphasizing where the S boxes are).
bits are rotated left 4 when computing S6 S4 S2 S0::

	282726252423xxxx201918171615xxxx121110090807xxxx040302010031xxxx

the rightmost two bits are usually cleared so the lower byte can be used
as an index into an sbox mapping table. the next two x'd bits are set
to various values to access different parts of the tables.

how to use the routines

datatypes:
	pointer to 8 byte area of type DesData
	used to hold keys and input/output blocks to des.

	pointer to 128 byte area of type DesKeys
	used to hold full 768-bit key.
	must be long-aligned.

DesQuickInit()
	call this before using any other routine with ``Quick`` in its name.
	it generates the special 64k table these routines need.
DesQuickDone()
	frees this table

DesMethod(m, k)
	m points to a 128byte block, k points to an 8 byte des key
	which must have odd parity (or -1 is returned) and which must
	not be a (semi-)weak key (or -2 is returned).
	normally DesMethod() returns 0.

	m is filled in from k so that when one of the routines below
	is called with m, the routine will act like standard des
	en/decryption with the key k. if you use DesMethod,
	you supply a standard 56bit key; however, if you fill in
	m yourself, you will get a 768bit key - but then it won't
	be standard.  it's 768bits not 1024 because the least significant
	two bits of each byte are not used.  note that these two bits
	will be set to magic constants which speed up the encryption/decryption
	on some machines.  and yes, each byte controls
	a specific sbox during a specific iteration.

	you really shouldn't use the 768bit format directly;  i should
	provide a routine that converts 128 6-bit bytes (specified in
	S-box mapping order or something) into the right format for you.
	this would entail some byte concatenation and rotation.

Des{Small|Quick}{Fips|Core}{Encrypt|Decrypt}(d, m, s)
	performs des on the 8 bytes at s into the 8 bytes at
	``d. (d,s: char *)``.

	uses m as a 768bit key as explained above.

	the Encrypt|Decrypt choice is obvious.

	Fips|Core determines whether a completely standard FIPS initial
	and final permutation is done; if not, then the data is loaded
	and stored in a nonstandard bit order (FIPS w/o IP/FP).

	Fips slows down Quick by 10%, Small by 9%.

	Small|Quick determines whether you use the normal routine
	or the crazy quick one which gobbles up 64k more of memory.
	Small is 50% slower then Quick, but Quick needs 32 times as much
	memory.  Quick is included for programs that do nothing but DES,
	e.g., encryption filters, etc.

Getting it to compile on your machine
=====================================

there are no machine-dependencies in the code (see porting),
except perhaps the ``now()`` macro in desTest.c.
ALL generated tables are machine independent.
you should edit the Makefile with the appropriate optimization flags
for your compiler (MAX optimization).

Speeding up kerberos (and/or its des library)
=============================================

note that i have included a kerberos-compatible interface in desUtil.c
through the functions des_key_sched() and des_ecb_encrypt().
to use these with kerberos or kerberos-compatible code put desCore.a
ahead of the kerberos-compatible library on your linker's command line.
you should not need to #include desCore.h;  just include the header
file provided with the kerberos library.

Other uses
==========

the macros in desCode.h would be very useful for putting inline des
functions in more complicated encryption routines.