In the Linux kernel configuration, I see these options:

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

        tristate "Software async crypto daemon"
        select CRYPTO_BLKCIPHER
        select CRYPTO_HASH
        select CRYPTO_MANAGER
        select CRYPTO_WORKQUEUE
          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?

  • @DevynCollierJohnson Never heard of any such distinction. You may need to go read the code to figure out what distinction the authors think exists.
    – Patrick87
    Nov 27, 2013 at 18:59

1 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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .