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:
- outer encoding
- Apply random key
R
to each blocki
from1..n
by XORing them withE(R,i)
- These transformed blocks will be sent to the recipient
- inner encoding
- For all blocks
1..n
, calculateS
as the XOR sum ofE(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)
- inner decoding
- For all blocks
1..n
, calculateS
as the XOR sum ofE(P, received_block(i) + i)
- XOR S with received_block(n+1) giving R
- outer decoding
- Apply recovered random key
R
to each recieved blocki
from1..n
by XORing them withE(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 parameterP
- 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 a message using SHA-1
Encode a message using SHA-1
XOR block of data: *dst ^= *src, returning dst