*****************************
** GECRYPT-0.3 FILE FORMAT **
*****************************
2007-07-31  Dwayne C. Litzenberger <dlitz@dlitz.net>

** DEFINITIONS **

Let AES-CTR(K, N, M) represent the encryption (or decryption, which is
equivalent) of M using AES in counter mode using key K and nonce N.

Define the constants (represented as 128-bit big-endian integers):
    
    FILE_ID     = 0x616d1d67ca294e2eb98bc01ff0470100
    HEADER_ID   = 0x616d1d67ca294e2eb98bc01ff0470101

Let || represent the string concatenation operator.

Let S * N represent the string S repeated N times.

Let Len(X) represent the length (in octets) of X.

Let Int8(N) represent the unsigned 8-bit big-endian representation of N.

Let Int16(N) represent the unsigned 16-bit big-endian representation of N.

Let Int64(N) represent the unsigned 64-bit big-endian representation of N.


** HOW TO WRITE A GECRYPT-0.3 FILE **

1. Get from the user:
    
    - The arbitrary-length master key K_M
    - The plaintext message M
    - The 16-bit iteration count c (must be >= 10.  If the master key is a
      passphrase, c should be at least 1000.)
    - An optional, 64-bit padding size p.  The default is 0 if none is
      specified.

2. Randomly generate:

    - 128-bit salt: S
    - 64-bit nonces: N_H, N_P
    - 128-, 192-, or 256-bit payload cipher key: K_P

3. Using the password-based key derivation function PBKDF2(P, S, c, dkLen) from
RSA PKCS#5 v2.0, compute the session key (using HMAC-SHA256 as the underlying
pseudorandom function):

    K = PBKDF2(K_M, FILE_ID || S, c, 96)

4. Set the authentication key K_A to be the first 512 bits of the session key:

    K_A = K<0..63>

5. Set the header cipher key K_H to be the last 256 bits of the session key:

    K_H = K<64..95>

6. Generate the encrypted portion of the header:

    C_H = AES-CTR(K_H, N_H, HEADER_ID || N_P || Int8(Len(K_P)) || K_P)

7. Generate the header:

    HEADER = FILE_ID || S || N_H || Int16(c) || C_H

8. Initialize the payload cipher.  Since AES-CTR is a stream cipher, define an
oracle E(x) that returns the AES-CTR encryption of x using key K_P and nonce
N_P, such that no part of the keystream is re-used and no part of the keystream
is skipped over.  For example, given three octet strings a, b, and c:

    Let x = E(a)
    Let y = E(b)
    Let z = E(c)

Then,

    x || y || z == AES-CTR(K_P, N_P, a || b || c)

9. Split the plaintext into n chunks M_1, M_2, ... M_n such that the length
(in octets) of each chunk falls within the interval [1..2^16-1].

10. Generate the padding:
    
    PAD = Int8(0) * p      ; zero repeated p times

11. Split the padding into m chunks P_1, P_2, ... P_m such that the length
(in octets) of each chunk falls within the interval [1..2^16-1].

12. Generate the ciphertext:

    C_0 = HEADER
    A_0 = HMAC-SHA256(K_A, C_0)

    L_1 = Int16(Len(M_1))
    C_1 = C_0 || A_0 || E(L_1 || M_1)
    A_1 = HMAC-SHA256(K_A, C_1)
    
    L_2 = Int16(Len(M_2))
    C_2 = C_1 || A_1 || E(L_2 || M_2)
    A_2 = HMAC-SHA256(K_A, C_2)
    
    L_3 = Int16(Len(M_3))
    C_3 = C_2 || A_2 || E(L_3 || M_3)
    A_3 = HMAC-SHA256(K_A, C_3)
    
    . . .

    L_n = Int16(Len(M_n))
    C_n = C_{n-1} || A_{n-1} || E(L_n || M_n)
    A_n = HMAC-SHA256(K_A, C_n)
    
    LP_0 = Int16(0)
    CP_0 = C_n || A_n || E(LP_0)
    AP_0 = HMAC-SHA256(K_A, CP_0)

    LP_1 = Int16(Len(P_1))
    CP_1 = CP_0 || AP_0 || E(LP_1 || P_1)
    AP_1 = HMAC-SHA256(K_A, CP_1)
    
    LP_2 = Int16(Len(P_2))
    CP_2 = CP_1 || AP_1 || E(LP_2 || P_2)
    AP_2 = HMAC-SHA256(K_A, CP_2)

    . . .
    
    LP_m = Int16(Len(P_m))
    CP_m = CP_{m-1} || AP_{m-1} || E(LP_m || P_m)
    AP_m = HMAC-SHA256(K_A, CP_m)
    
    LP_{m+1} = Int16(0)
    CP_{m+1} = CP_m || AP_m || E(LP_{m+1})
    AP_{m+1} = HMAC-SHA256(K_A, CP_{m+1})

    CIPHERTEXT = CP_{m+1} || AP_{m+1}

Note: If the plaintext is empty, then n = 0, therefore:

    C_0 = HEADER
    A_0 = HMAC-SHA256(K_A, C_0)
    
    LP_0 = Int16(0)
    CP_0 = C_0 || A_0 || E(LP_0)
    AP_0 = HMAC-SHA256(K_A, CP_0)

Note: If the padding is empty (i.e. no padding is desired), then m = 0,
therefore:
    
    LP_1 = Int16(0)
    CP_1 = CP_0 || AP_0 || E(LP_1)
    AP_1 = HMAC-SHA256(K_A, CP_1)

13. Output CIPHERTEXT.


** EOF **