Skip to content

Algorithm Notes

Jump to bottom Edit New page
Ryan Culpepper edited this page Apr 27, 2026 · 7 revisions

Notes on various cryptographic algorithms, including links to standards. (Notes on specific implementations are out of scope.)

Properties of interest:

  • "truncation"
    • Can F(m,x...) be computed as F(n,x...) truncated to length m? (Here m < n and they represent output length parameters.) If so, "truncation is allowed"; if not, "truncation is not allowed".
    • For example, SHA384(M) is not a prefix of SHA512(M), since the digest algorithms have different initial states. (Truncation is not allowed.)
    • For example, an 8-byte GCM tag is just the prefix of a 12-byte GCM tag. (Truncation is allowed.)
    • Truncation affects the flexibility of low-level operations, and it affects the design of high-level APIs (when must the user commits to an output size?).
  • "missing = empty"
    • Is the absence of an input equivalent to a zero-length input? (Generally, yes.)
    • For example, BLAKE2 treats a missing key as a zero-length key.
  • early vs late parameters
    • When must a particular input be supplied?
    • For example, CCM decryption requires the auth tag before decryption starts, because the auth tag is used to form the initial state; but GCM decryption does not require the auth tag until the end, because GCM recomputes the tag and compares it with the given tag.

Digests

Digest Link
SHA1 SHA1-RFC
SHA2 SHA2-RFC, FIPS 180-4
SHA3, SHAKE FIPS 202
CSHAKE SP 800-185
BLAKE2 BLAKE2-RFC, BLAKE2-Site

In general, no truncation relationships between any of the digest variants (except SHAKE and CSHAKE):

  • For example, SHA512/256 is not just truncated SHA512; they have distinct initial states.
  • BLAKE2: key length < 256, missing = empty; truncation not allowed, result depends on output length and key length.
  • SHAKE and CSHAKE are XOFs: They conceptually produce an infinite bit stream, and finite truncations are taken. So SHAKE128(m,x) is a prefix of SHAKE128(n,x) where m < n, for example.
  • CSHAKE with empty info parameters is equivalent to SHAKE by definition.

The given block sizes (aka "rates") for SHA3 (eg, for HMAC) are confirmed in SHA3 IKEv2 IPsec.

Other digests:

Digest Note Link
BLAKE2X xof BLAKE2-Site
BLAKE2{BP,SP} parallel BLAKE2-Site
TupleHash xof, input=tuple of strings SP 800-185
ParallelHash xof SP 800-185
BLAKE3 xof, MAC, KDF, parallel BLAKE3-DRAFT

MACs

MAC Notes Links
HMAC truncation ok HMAC-RFC, [FIPS 198-1], SP 800-224
CMAC formerly "OMAC1" SP 800-38B
KMAC "Keccak MAC" SP 800-185 §4
GMAC "Galois MAC" SP 800-38D
UMAC "Universal MAC" UMAC-RFC
Poly1305 one-time CHACHA20-POLY1305-RFC
Blake2 BLAKE2-Site

HMAC:

  • Inputs:
    • K -- key, recommend at least Houtlen bytes; pre-hash if longer than Hblocklen bytes
    • text -- input
  • The result is Houtlen bytes. Truncation allowed (RFC has advice).

CMAC:

  • Parameters: block cipher
  • Inputs:
    • K -- key for block cipher
    • M -- input, may be empty
  • The result is blocklen bytes, may be truncated.

KMAC:

  • Inputs:
    • K -- key, may be empty (but not "approved" if shorter than security strength)
    • X -- input, may be empty
    • L -- output length in bits
    • S -- optional customization, missing = empty
  • The result depends on all inputs, including L, so truncation is not allowed.
    • In particular, KMAC{128,256} does not agree with KMAC-XOF at same sizes.

GMAC:

  • Defined as GCM with empty plaintext/ciphertext, only AAD.

Poly1305:

  • "One-time" authenticator -- that is, must not reuse key!
  • Inputs: K (32-byte key), M message
  • Output: 16-byte auth tag; spec for Chacha20-Poly1305 forbids truncation

Names and history:

  • CBC-MAC: "has security deficiencies" SP 800-38B
    • used in CCM mode
  • XCBC: improved variant of CBC-MAC, but required 3 keys
  • OMAC wikipedia
    • original (2003-02), now called "OMAC2", improved XCBC
    • refinement "OMAC1" became standardized as "CMAC (Cipher-based MAC)"

Block Ciphers

Block Cipher Modes

Mode Notes Link
ECB, CBC, CFB, OFB, CTR SP 800-38A, FIPS 81
OCB1 no AAD
OCB2 broken, AEAD
OCB3 AEAD OCB3-RFC
CCM AEAD, 2-pass SP 800-38C, CCM-RFC
EAX AEAD, 2-pass EAX-HOME
CWC (Carter-Wegman+CTR)
GCM AEAD SP 800-38D
XTS SP 800-38E
KW (Key Wrap) auth, det SP 800-38F, KEYWRAP-RFC
KWP (KW w/ Padding) auth, det SP 800-38F
SIV SIV-RFC
GCM-SIV AEAD, det, 2-pass GCMSIV-RFC

AEAD = "Authenticated Encryption with Associated Data", suggested interface described in AEAD-RFC.

  • key length in 1..255
  • nonce length: 12 recommended, but variable lengths allowed

CCM:

  • Weird, size of nonce depends on size of inputs!
  • Encrypt and decrypt require length of AD and data to be known in advance.
  • Auth tag does not allow truncation (length included in initial state).
  • Decryption recomputes auth tag; authentication just compares. That is, auth tag is not needed for decryption to begin.

GCM:

KW (Key Wrap):

  • Inputs:
    • KEK -- "key-encryption key"
    • P1...Pn -- plaintex, each Pi is 64 bits, n ≥ 2
  • Output: n+1 64-bit blocks C0..Cn

SIV:

  • Resistant to nonce misuse/reuse
  • AAD is "vector of strings"
    • When using AEAD-RFC interface, only accepts one string.
  • Uses double-sized keys (256, 384, 512), split into two parts

GCM-SIV:

  • Resistant to nonce misuse/reuse
  • Different authenticator: POLYVAL instead of GHASH (but related)
  • Both encrypt and decrypt require whole input. In particular, decrypt requires auth tag before processing.

Stream Ciphers

Cipher Links
Salsa20, Salsa20/8, Salsa20/12 SNUFFLE-HOME
XSalsa20 SNUFFLE-HOME
Chacha20-Poly1305 CHACHA20-POLY1305-RFC
XChaCha20-Poly1305 XCHACHA-DRAFT

Chacha20-Poly1305

  • 32-byte key, 12-byte nonce, 16-byte auth tag
  • Poly1305 key is generated from Chacha20 output block w/ counter=0
  • Authentication recomputes tag and compares. So auth tag allows truncation, and decryption does not require auth tag before beginning.

XChaCha20-Poly1305

  • 24-bit nonce, safer for random generation

KDFs

KDF Links
Argon2 Argon2-RFC, PHC Winner
PBKDF2 PKCS5
Concatenation (One-Step/Single-Step) SP 800-56C §4.1, SP 800-56A §5.8
Two-Step (Extract and Expand) SP 800-56C §5
HKDF HKDF-RFC, HKDF Paper
Counter, Feedback, Double-Pipeline SP 800-108

Argon2

Inputs:

  • P -- passphrase ("message string"), len < 2^32
  • S -- salt ("nonce"), len < 2^32; 16 bytes recommended for password hash
  • p -- degree of parallelism, 1 ≤ p < 2^24
  • T -- key size ("tag length"), 4 ≤ T < 2^32
  • m -- memory size, number of kibibytes, 8p ≤ m < 2^32
  • t -- number of passes, 1 ≤ t < 2^32
  • v -- version number = #x13 (previous was #x10)
  • K -- secret value, optional, len < 2^32; missing = empty
  • X -- associated data, optional, len < 2^32; missing = empty

Result depends on all inputs; in particular, result depends on T (cannot generate longer and truncate).

PHC page says min salt length is 8; RFC implies salt can be empty.

Concatenation KDF (aka One-Step KDF, aka Single-Step KDF)

(There is also a KMAC-based version, not described here.)

Inputs:

  • Z -- input ("shared secret"; doc is DH-oriented)
  • salt (depends)
    • if used with digest, no salt
    • if used with HMAC-digest, salt is used as HMAC key
      • if missing, default value is zeroes of digest block size
  • L -- output length, 1 ≤ L < 2^32
  • FixedInfo -- context info, no limits stated
    • recommendations in SP 800-56A §5.8.2, "should be included"

Truncation allowed, unless L is included in FixedInfo.

Two-Step KDF (Extract-and-Expand)

(There is also a CMAC-based version, not described here.)

Inputs:

  • Z -- input ("shared secret")
  • salt -- used as HMAC key
    • if missing, default value is zeroes of digest block size (?)
  • L -- output length
  • FixedInfo -- context info

HKDF (instance of Extract-and-Expand)

HKDF-Extract inputs:

  • input -- "IKM, input keying material"
  • salt -- optional, used as HMAC key
    • if missing, zeroes of length hashlen (digest output size) (!)

HKDF-Expand inputs:

  • prk -- "pseudorandom key", output of Extract
  • info -- optional context-specific information, can be empty
  • L -- output length in octets, L ≤ 255*hashlen

Truncation allowed, unless L is included in info.

SP 800-108 KDFs (Counter, Feedback, Double-Pipeline)

Inputs:

  • input -- input (eg, shared secret)
  • label -- identifies purpose of derived key
  • context -- eg, parties, nonce
  • L -- output length in bits

Effectively:

FixedInfo := label || #x00 || context || L

Result depends on all inputs, including L, so truncation is not allowed.

KEMs (Key Encapsulation Mechanisms)

KEM Links
RSA-KEM RSAKEM-RFC
DH-KEM DHKEM-RFC
RSASVE-KEM SP 800-227
ECDH-KEM SP 800-227
ML-KEM FIPS 203
X-Wing XWING-Draft
  • SP 800-227
    • key establishment: key transport or key agreement
    • key agreement: both parties contribute to shared secret
    • key transport: one party generates secret, sends to other
    • Definition of KEM encompasses both?
    • Can use any KEM for key agreement by running twice, once in each direction, and combining secrets with KDF.

ECDH-KEM SP 800-227 §5.1.1

  • Alice has "static" keypair (privA, pubA). Bob knows Alice's public key.
  • Bob computes (secret, ephpubB) = encapsulate(pubA).
  • Bob transmits ephpubB to Alice.
  • Alice computes secret = decapsulate(privA, ephpubB).

Encapsulation:

encapsulate(pubA) =
  let (ephprivB, ephpubB) = generate-keypair
  let secret = ECDH(ephprivB, pubA)
  return (secret, ephpubB)

Decapsulation:

decapsulate(privA, ephpubB) =
  let secret = ECDH(privA, ephpubB)
  return secret

This description does not include a hash/KDF step.

RSASVE-KEM SP 800-227 §5.1.2

  • Alice has "static" keypair (privA, pubA). Bob knows Alice's public key.
  • Bob computes (secret, enc) = encapsulate(pubA).
  • Bob transmits enc to Alice.
  • Alice computes secret = decapsulate(privA, enc).

Encapsulation:

encapsulate(pubA) =
  let secret = random(nbits)      // nbits is length of public key pubA
  let enc = RSAEP(pubA, secret)   // raw encryption, no padding
  return (secret, enc)

Decapsulation:

decapsulate(privA, enc) =
  let secret = RSADP(privA, enc)
  return secret

This description does not include a hash/KDF step.

RSA-KEM RSAKEM-RFC

Parameters: KDF, secretlen

Encapsulation:

encapsulate(pubA) =
  let Z = random(nbits)     // nbits is length of public key pubA
  let enc = RSAEP(pubA, Z)  // raw encryption, no padding
  let secret = KDF(Z, secretlen)
  return (secret, enc)

Decapsulation:

decapsulate(privA, enc) =
  let Z = RSADP(privA, enc)
  let secret = KDF(Z, secretlen)
  return secret

The application of RSA-KEM to CMS uses an additional KDF to generate a KEK, and uses the KEK to wrap a (randomly generated) CEK/DEK.

DH-KEM DHKEM-RFC

Section 4 summarizes extended KEM interface.

Parameters: KDF; DH group with DH producing secret of length dhlen

ML-KEM

KEM Pub/Enc Key Priv/Dec Key Enc Data Size Dec Data Size
ML-KEM-512 800 1632 768 32
ML-KEM-768 1184 2400 1088 32
ML-KEM-1024 1568 3168 1568 32

Public Key Cryptography

System Links
RSA PKCS1, PKCS1-v1.5
DSA FIPS 186-4
ECDSA FIPS 186-5, SEC1
ECDH SEC1
EdDSA FIPS 186-5, EdDSA-RFC
X{25519,448} ECX-RFC, SafeCurves

Variants:

Data Formats

ASN.1 Specifications

  • SEC1: OIDs, ECDomainParameters, ECPrivateKey
  • RFC 8410: OIDs for Ed25519, Ed448, X25519, and X448
  • PKCS8: PrivateKeyInfo, EncryptedPrivateKeyInfo
  • AsymKeyPackages: OneAsymmetricKey, PrivateKeyInfo v2

Password hashes

References

General RFCs:

PKCS RFCs:

  • PKCS1: RSA, RSA-OAEP, RSA-PSS
  • PKCS5: Passwords, PBKDF2
  • PKCS8: ASN1: PrivateKeyInfo, EncryptedPrivateKeyInfo

NIST Publications:

Other documents:

  • SEC1: Elliptic Curve Cryptography, ECDSA, ECDH, ECMQV
  • SEC2: Recommended Elliptic Curve Domain Parameters
  • SafeCurves
Add a custom footer
Add a custom sidebar

Clone this wiki locally