# RNCryptor Data Format Specification Version 4.0

## Data Layout

    Byte:     |  0-2  |    3    |    4    | 5 - 20 |  21 - 36  | <-      ...     -> | n-32 - n |
    Contents: | magic | version | options |  salt  | validator | ... ciphertext ... |   HMAC   |

### Field definitions

* magic (3 bytes): "RNC"
* version (1 byte): Data format major version (0x04)
* options (1 byte): 
    * bit 0 - (boolean) uses password
    * bit 4-6 - (iff bit 0 is 1) (int) log10(pbkdf2_iterations). Bit 6 is MSB. 0 defaults to 10,000.
* salt (16 bytes)
* validator (16 bytes): used to determine if password is correct
* ciphertext (variable): Encrypted in CBC mode
* HMAC (32 bytes): HMAC-SHA512-256

All data is in network order (big-endian).

Note that the version of the RNCryptor ObjC library is not directly related to
the version of the RNCryptor file format. For example, v2.2 of the RNCryptor
ObjC library writes v3 of the file format. The versioning of an implementation
is related to its API, not the file formats it supports.

## Key Generation

RNCryptor uses either a 256-bit random key or a password. It extracts a 512-bit
pseudorandom key (PRK) from this using HKDF-Extract or PBKDF2. It then uses
HKDF-Expand to expand this key material into the IV, a validation token, the
encryption key, and the HMAC key.

## Key Validation

Using the validation token, the encryption key can be tested without validating HMAC.

## Implementation Procedure

Unless otherwise noted, all example implementations are given in an abtract,
idealized language. It includes the following constructs:

* `||` - Operator that concatenates two octet strings.
* `RandomDataOfLength(n)` - Returns `n` random octets generated by a [CSPRNG](https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator).
* `PBKDF2(PRF algorithm, password, Salt, iterations, output length)` - Returns the result of [PBKDF2 algorithm](https://tools.ietf.org/html/rfc2898).
* `AESEncrypt(key length, mode, key, iv, plaintext)` - Returns the AES encrypted ciphertext.
* `AESDecrypt(key length, mode, key, iv, plaintext)` - Returns the AES decrypted plaintext.
* `HMAC(hash function, key, data, length)` - Returns the result of the [HMAC algorithm](https://tools.ietf.org/html/rfc2104), truncated to `length` octets.
* `Split()` - Returns a list of components as defined by the format.
* `ConsistentTimeEqual(x, y)` - Compares `x` and `y` in consistent time (without shortcuts).
* `Assert(condition)` - Indicates a programming error if condition is not met.
* `KEY_MISMATCH` - Token indicating an incorrect key or password.
* `CORRUPT` - Token indicating a corrupt message.
* `SHA512` - Token indicating SHA-2 hash function with 512-bit length.
* `CBCMode` - Token indicating [cipher block chaining (CBC)](https://en.wikipedia.org/wiki/Block_cipher_modes_of_operation#Cipher-block_chaining_.28CBC.29) block cipher mode. This implicitly includes PKCS#7 padding.

## Key HKDF-expansion

Expand PRK to 96 bytes for required material using HMAC-SHA-512 + HMAC-SHA-512-256.

```
def Expand(prk[64]) =
    info = "rncryptor"
    T1 = HMAC(SHA512, prk,       info || 0x01, 512 bits)
    T2 = HMAC(SHA512, prk, T1 || info || 0x02, 256 bits)
    return T1 || T2
```

## General encryption function

Takes a 512-bit pseudorandom key (prk). Expands it into the encryption key,HMAC
key, IV, and validator. Validator is last so attacker cannot short-cut
Expand().

```
def Encrypt(prk[64], options[1], salt[16], plaintext) =
    (encryptionKey[32], hmacKey[32], iv[16], validator[16]) = Expand(prk)

    magic = "RNC" (0x52 0x4e 0x43)
    version = 0x04
    header = magic || version || options || salt || validator
    ciphertext = AESEncrypt(256 bits, CBCMode, encryptionKey, iv, plaintext)
    hmac = HMAC(SHA512, hmacKey, header || ciphertext, 256 bits)
    return header || ciphertext || hmac
```

1. Expand PRK into validator, IV, and keys
2. Construct header from version, options, salt, and validator
3. Encrypt ciphertext with AES-256
4. Compute HMAC with SHA-512-256
5. Return message with header, ciphertext, and HMAC

## General decryption function

```
def Decrypt(prk[64], options[1], salt[16], validator[16], ciphertext, hmac[32]) =
    (encryptionKey[32], hmacKey[32], iv[16], validator[16]) = Expand(prk)
    if (! ConsistentTimeEqual(expectedValidator, validator) return KEY_MISMATCH

    magic = "RNC" (0x52 0x4e 0x43)
    version = 0x04
    header = magic || version || options || salt || validator
    expectedHmac = HMAC(SHA512, hmacKey, header || ciphertext, 256 bits)

    if ! ConsistentTimeEqual(expectedHmac, hmac) return CORRUPT
    else return AESDecrypt(2556 bits, CBCMode, encryptionKey, iv, ciphertext)
```

1. Expand PRK into validator, IV, and keys
2. Verify (in constant time) that validators match. If not, the password was incorrect.
3. Construct header from version, options, salt, and validator.
4. Compute expected HMAC with SHA-512-256
5. Verify (in constant time) that HMACs match. If not, the ciphertext is corrupt.
6. Return decrypted data.

## Key-based encryption

Input is 256 random bits of source keying material (called `key`). To maintain
consistency with PBKDF2, and to improve poorly generated keys (key reuse or
non-random key selection), the actual pseudorandom key (PRK) is extracted with
HKDF and a 128-bit random salt.

```
def KeyBasedEncrypt(key[32], plaintext) =
    salt = RandomDataOfLength(16 bytes)

    // HKDF-Extract
    prk = HMAC(SHA512, salt, key, 512 bits)

    options = 0

    return Encrypt(prk, options, salt, plaintext)
```

1. Generate random salt.
2. Extract 512-bit PRK from 256-bit key + 128-bit salt via HKDF.
3. Perform generic encryption.

## Key-based Decryption

```
def KeyBasedDecrypt(key[32], message) =
    (version, options, salt, validator, ciphertext, hmac) = Split(message)

    if (version != 4) return CORRUPT
    if (option & 0x01 != 0) return CORRUPT

    // HDF-Extract
    prk = HMAC(SHA512, salt, key, 512 bits)

    return Decrypt(prk, options, salt, validator, ciphertext, hmac)
```

1. Pull apart the pieces as described in the data format.
2. Verify that the header is legal. If not, return a failure.
2. Extract 512-bit PRK from 32-bit key via HKDF.
3. Perform generic decryption.

## Password-based Encryption

```
def PasswordBasedEncrypt(password, plaintext, log10Rounds = 0) =
    Assert(password.length > 0)
    Assert(log10Rounds >= 0)
    Assert(log10Rounds <= 7)

    if (log10Rounds == 0) rounds = 10000
    else rounds = exp10(log10Rounds)

    salt = RandomDataOfLength(16 bytes)

    // PBKDF2 (standing in for HKDF-Extract)
    prk = PBKDF2(SHA1, password, salt, rounds, 512 bits)

    options = (1 << 0) | (log10Rounds << 4)

    return Encrypt(prk, options, salt, plaintext)
```

1. Password must not be empty.
2. The number of rounds must be between 10 (0 means 10,000) and 1,000,000.
3. If `log10Rounds` is zero, set `rounds` to the default value of 10,000. Otherwise, set `rounds` to `10^log10Rounds`.
4. Generate a random salt.
5. Generate the 512-bit PRK using PBKDF2 and the given number of rounds.
6. Generate options field.
7. Perform generic encryption.

## Password-based decryption

```
def PasswordBasedDecrypt(password, message) =
    (version, options, salt, validator, ciphertext, hmac) = Split(message)

    if (version != 4) return FAIL
    if (option & 0x01 != 1) return FAIL

    rounds = (options & 0x70) >> 4
    if (rounds == 0) rounds = 10000
    else rounds = exp10(rounds)

    // HDF-Extract
    prk = PBKDF2(SHA1, password, salt, rounds, 512 bits)

    return Decrypt(prk, options, salt, validator, ciphertext, hmac)
```

1. Pull apart the pieces as described in the data format.
2. Extract bits 4-6 from options. If zero, then rounds is 10,000. Otherwise, raise ten to that power and set as rounds.
3. Generate the 512-bit PRK using PBKDF2 and the given number of rounds.
4. Perform generic decryption

## Consistent-time equality checking

When comparing the computed HMAC with the expected HMAC, it is important that
your comparison be made in consistent time. Your comparison function should
compare all of the bytes of the ExpectedHMAC, even if it finds a mismatch.
Otherwise, your comparison can be subject to a timing attack, where the
attacker sends you different HMACs and times how long it takes you to return
that they are not equal. Using this, the attacker can progressively determine
each byte of the HMAC.

Here is an example consistent-time equality function in ObjC:

``` objc
- (BOOL)rnc_isEqualInConsistentTime:(NSData *)otherData {
  // The point of this routine is XOR the bytes of each data and accumulate the results with OR.
  // If any bytes are different, then the OR will accumulate some non-0 value.
  uint8_t result = otherData.length - self.length;  // Start with 0 (equal) only if our lengths are equal

  const uint8_t *myBytes = [self bytes];
  const NSUInteger myLength = [self length];
  const uint8_t *otherBytes = [otherData bytes];
  const NSUInteger otherLength = [otherData length];

  for (NSUInteger i = 0; i < otherLength; ++i) {
    // Use mod to wrap around ourselves if they are longer than we are.
    // Remember, we already broke equality if our lengths are different.
    result |= myBytes[i % myLength] ^ otherBytes[i];
  }

  return result == 0;
}
```

## Approach and Notes

RNCryptor is similar to
[draft-mcgrew-aead-aes-cbc-hmac-sha2](https://tools.ietf.org/id/draft-mcgrew-aead-aes-cbc-hmac-sha2-02.html)
AEAD_AES_256_CBC_HMAC_SHA_512 in how it produces authenticated encryption from
AES-CBC and HMAC-SHA. It differs slightly in how it generates the keys (via
HKDF rather than splitting the PRK), and it computes the IV via HKDF rather
than passing a random IV.

SHA-1 is used (rather than SHA-2) in PBKDF2 to maintain better platform
support. .NET's [Rfc2898DeriveBytes](http://msdn.microsoft.com/en-us/library/system.security.cryptography.rfc2898derivebytes(v=vs.110).aspx) 
only supports SHA1HMAC. There is no security concern in using SHA-1 here.
PBKDF2 only requires a PRF to maintain itssecurity proof, and SHA-1, even with
its known attacks, continues to be a PRF. Hopefully .NET will eventually
support SHA-2 PBKDF2 and we'll be able to drop SHA-1 as a matter of
housekeeping (minimizing the number of algorithms required).

RNCryptor relies on HKDF ([RFC 5869](https://tools.ietf.org/html/rfc5869)) to
generate random octet strings from a master 512-bit PRK.

The HMAC is truncated according to 
[RFC 2104 Section 5](https://tools.ietf.org/html/rfc2104).
Private HMACs (i.e. HMACs not directly encoded in the file format) are not
truncated.

SHA-512 is used throughout to favor CPU rather than GPU performance. Most
legitimate uses will be computed on CPU. Attackers prefer high-speed GPU
implementations.

## Changes since version 3.0

* Employs draft-mcgrew-aead-aes-cbc-hmac-sha2 and HKDF.
* Computes IV and keys from salt and master key.
* Adds validator for fast password checking
* Replaces SHA-1 and SHA-256 with SHA-512.
* Unifies key- and password-based formats.
* Adds magic to beginning to identify format