Crate aont[−][src]

Expand description

Rivest’s All-or-nothing-transform

use aont::{encode_sha1, decode_sha1};

// Set up message to be encoded and public parameter
let message = "0123456789abcdef0123";
let public  = "abcdeabcdeabcdeabcde";
let message_as_bytes  = message.as_bytes();

// Do the encoding (get back transformed data)
let encoded = encode_sha1(message_as_bytes, public.as_bytes());
assert_ne!(*message_as_bytes, *encoded);

// Pass encoded message and same public parameter to recover original message
let recover = decode_sha1(&*encoded, public.as_bytes());
assert_eq!(message_as_bytes, &*recover);

Operation

The AONT encodes and decodes a message by use of a public “key” P (in the normal sense of the word—not an RSA public key) and a random “key” R. It also uses a hash function E() which works on blocks of the message.

The steps taken are:

  1. outer encoding
  • Apply random key R to each block i from 1..n by XORing them with E(R,i)
  • These transformed blocks will be sent to the recipient
  1. inner encoding
  • For all blocks 1..n, calculate S as the XOR sum of E(P, transformed_block(i) + i)
  • Append block(n + 1) as S xor R
  • (Optionally, header or trailer information can include P and/or the amount of padding)
  1. inner decoding
  • For all blocks 1..n, calculate S as the XOR sum of E(P, received_block(i) + i)
  • XOR S with received_block(n+1) giving R
  1. outer decoding
  • Apply recovered random key R to each recieved block i from 1..n by XORing them with E(R,i)

Note that this is not encryption in the usual sense. If all blocks of the transformed message have been received and are placed in the right order, the outer decoding step can use the public “key” to extract the random “key” from the final block of the message. With this, the outer decoding can proceed to decode the transformed blocks.

Explanation in terms of XOR masking

In simpler terms, encoding can be understood as:

  • applying an xor mask to the file using a random parameter R
  • calculating a hash S of the transformed data using a public parameter P
  • using that hash to xor mask the value of P, which is appended to the file

In reverse:

  • the same public hash function is applied to all non-final blocks, recovering S
  • the final block is XOR-ed with S to recover R
  • The xor mask generated by R is applied to the non-final blocks to recover the original

“Encryption” Functions: Hash Functions

The simplest kind of “Encryption” function for this scheme is a standard one-way hash function such as SHA or MD5. In this case, a “block” is the same size as the output of the hash function.

Where the algorithm calls for passing in a “key” parameter, a block, or an integer, these can be handled by concatenation. For example E, P, block[i] + i could be implemented by string concatenation of:

  • the P parameter in binary form
  • the binary contents of block[i] of the message
  • the binary value of the counter i (or, the same value converted to ascii)

Equally, the three values could be XOR-ed together. The “key” parameters will be the same length as blocks, so this is straightforward. However, when converting an integer from its internal representation to something that can be XOR-ed with the block, care needs to be taken to convert it into a portable format. In particular, both the byte order and alignment must be decided.

Encryption Functions: HMAC

Hash-based Message Authentication Code (HMAC) is a technique that uses a hash function and some other token known by both the sender and receiver to authenticate a message as well as verify its integrity.

A HMAC construction can be used in place of a simple hash. There are two potential benefits of doing so:

  • it allows the use of hash functions that are known to be weak, since the security of HMAC is only a function of the size of the shared HMAC token.

  • the HMAC token can be treated as a secret key, making the message undecodable without it. However, this would no longer be an AONT.

It is still possible to use HMAC construction in either/both the inner/outer encoding without breaking the “no-encryption” status of AONT. Simply publish the HMAC token along with the public key, or include it as part of a header/trailer for the transmitted data. It’s also possible to use a random HMAC token, which can be stored alongside or as part of R.

Encryption Functions: Block Ciphers

It is also possible to use a symmetric encryption function (such as AES) to implement E(). Note that only the output of the encryption engine is used: the symmetric decryption function is never called.

Encryption routines can be used in several modes including CBC (Cipher Block Chaining) or Counter mode.

Implementation

I will implement this using a mix of high-level and low-level interfaces. The high-level interfaces will implement the AONT algorithm on messages and files. The next level down will allow for easy parameterisation of the basic algorithm, such as allowing a choice of encryption function.

At the lowest level, I’ll interact with the crypto and digest libraries. For example, I might use those libraries to find out what the block size should be (if it’s not explicitly given to us). I might also implement the two phases of the algorithm as Digest algorithms (ie implement the Digest trait for them).

Functions

decode_sha1

Decode a message using SHA-1

encode_sha1

Encode a message using SHA-1

xor_slice

XOR block of data: *dst ^= *src, returning dst