Asynchronous and parallel algorithms in the Linux kernel

Question

In the Linux kernel configuration, I see these options:

config CRYPTO_PCRYPT
        tristate "Parallel crypto engine"
        depends on SMP
        select PADATA
        select CRYPTO_MANAGER
        select CRYPTO_AEAD
        help
          This converts an arbitrary crypto algorithm into a parallel
          algorithm that executes in kernel threads.

config CRYPTO_CRYPTD
        tristate "Software async crypto daemon"
        select CRYPTO_BLKCIPHER
        select CRYPTO_HASH
        select CRYPTO_MANAGER
        select CRYPTO_WORKQUEUE
        help
          This is a generic software asynchronous crypto daemon that
          converts an arbitrary synchronous software crypto algorithm
          into an asynchronous algorithm that executes in a kernel thread.

What is the difference between arbitrary algorithms, asynchronous algorithms, and parallel algorithms in cryptography?

Answer 1

• In synchronous execution, you wait for the task to finish before moving on to another task.
• In asynchronous execution, you can move on to another task before the previous one finishes.

These terms are not specifically related to cryptography. In general, text-book descriptions of crypto algorithms are neither synchronous not asynchronous, but the implementations of the algorithm can be either.

Consider for instance a high-level description of AES:

AES is a block cipher, so each 128 bit input block goes through the following transformations:

• KeyExpansion
• InitialRound
  • AddRoundKey
• Rounds (10, 12 or 14 rounds of repetition depending on key size)
  • SubBytes
  • ShiftRow
  • MixColumns
  • AddRoundKey
• Final Round
  • SubBytes
  • ShiftRows
  • AddRoundKey

Depending on the cipher mode used, the encryption of the blocks can be either dependent or independent. For instance, in Cipher-block chaining (CBC) mode encryption, the ciphertext from the previous block is used to transform the plaintext of the next block before the actual AES transformations. In this case, the implementation of the algorithm must be synchronous, as the output of the previous step is needed as input for the next.

On the other hand, in Electronic codebook (ECB) mode, each block is encrypted separately. This means that the implementation of the algorithm may be either synchronous as before, or asynchronous, in which case the the encryptions of the next block can begin even while the AES rounds for the previous blocks are ongoing.

In our example, the execution could proceed in separate threads of execution for each block, or pipelined, i.e. the algorithm is split up into multiple independent parts. For instance, the initial round for the next block could be performed while the round repetitions for the previous block are ongoing. Pipelining is a common technique in hardware crypto implementations.

The cryptd module is a template that takes a synchronous software crypto algorithm and converts it to an asynchronous one by executing it in a kernel thread.

The concurrent execution of the asynchronous algorithm may either be interleaved, e.g. the algorithm executes on a single CPU core, and switches back and forth between the operations on the two blocks, or parallel, e.g. the execution of the algorithm proceeds simultaneously on multiple cores, each core processing a block of their own.

The pcrypt parallel crypto template takes a crypto algorithm and converts it to process the crypto transformations in parallel.

I think that arbitrary in these cases refers only to that the architecture of the modules are general enough to be applied to any cryptographic algorithm. I believe that for the moment only AEAD algorithms are supported by pcrypt.