All-Or-Nothing Transform

NOTE: I originally posted this on Snipplr.

Performs an all-or-nothing transform on a stream of chunks. The data can only be decrypted if every block is present to generate an HMAC for. The list of HMACs is then XOR'd against the final block from the transform, yielding the decryption key for the blocks.

Reports a hash of the encrypted chunk for storage/retrieval without needing to calculate HMAC until decryption.

Needs a lot of cleanup and some fixes. Makes a lot of assumptions, for instance, that current_block, total_blocks, and data_size only occupy 1 byte apiece. Currently doesn't strip padding after decoding, and doesn't convert original integers for current_block, total_blocks, and data_size back from bytes. Does a ton of extra work (conversions between bytes and bytearray).

NOTE: I removed code that verified the HMACs of the final block and each encrypted block to simplify the code, because you already need the correct HMACs to get the block key from the final block, and the block hashes are taken of the blocks encrypted with the block key.

NOTE 2: The incrementing counter typically XOR'd with the plaintext blocks is actually prepended (chunk()returns blocks of the format [current_block, total_blocks, data_size, data[a_block] (and for the last data block, + (padding_size * padding))].

NOTE 3: In this scheme, if you scatter the encrypted blocks, final blocks, lists of hashes of encrypted blocks and final blocks, and HMAC secret keys amongst a minimum of 4 parties, no single party can possibly decrypt the content, short of attacks on the encryption and hashing algorithms themselves, eavesdropping on other communications, impersonating another node (to acquire the other pieces illegitimately), etc.. Additionally, each node should be able to plausibly deny knowledge of the contents of their node, if they restrict their own access to the other necessary pieces.

The encrypted block server node has neither of the necessary keys to either decrypt the blocks or to derive their decryption key by generating their HMACs--even if it did, it would have no final blocks from which to recover the decryption key.

The final block server node has no encrypted blocks to decrypt, no awareness of which encrypted blocks belong to which final blocks, no HMAC secret key to derive the decryption key for the final block--and no encrypted blocks to perform an HMAC on.

The "location" server node has the regular hashes of the encrypted blocks and their corresponding final blocks (unless the file is secret). It has no HMAC secret key, nor the encrypted blocks, nor the final block or inner key. It could recover all but the HMAC secret key, so caution should be exercised with this node, for it should never come into possession of the HMAC secret key.

Finally, the one person who can recover the plaintext content should have the HMAC secret key and the hash of the list of hashes (of all blocks). To recover the plaintext, this person asks the location node for the list of hashes matching their hash. They then ask the encrypted block nodes for the blocks matching all but the last hash in the list. They perform an HMAC, using their secret key, on each of the blocks. They request the final block by its hash from the final block node, and XOR each HMAC with the final block, producing the block decryption key. Finally, they decrypt each block.

This module does not demonstrate scattering the parts of an AONT. In this example, everything resides within the local machine, in the currently running process.

NOTE 4: I seem unable to swap any blocks (excluding the last blocks) and still maintain correct decryption. However, the block key decrypts correctly, so the HMACs must be generated correctly, despite not verifying them explicitly. From my understanding of the algorithm, I should be able to swap or shuffle the blocks (as they are encrypted separately) and still decrypt them. Ideas/corrections welcome.

NOTE 5: Dependencies:

from stream import chunk
from hmac import HMAC, pad_key
from Crypto.Random import random

def bytearray_to_bytes(a_bytearray):
    return bytes([a_byte for a_byte in a_bytearray])

def encode(a_hash, hmac_key, a_cipher, data, block_size, block_key=None):
    if not block_key:
        block_key = bytes([random.randint(0, 255) for i in range(a_hash.digest_size)])

    hmac_key    = pad_key(a_hash, hmac_key)
    block_key   = pad_key(a_hash, block_key)
    encrypter   =
    final_block = bytearray(block_key)

    for a_block in chunk(data, block_size):
        a_hasher                =
        a_block                 = bytearray(a_block[0:3]) + a_block[3]
        encrypted_block         = bytearray(encrypter.encrypt(bytearray_to_bytes(a_block)))
        encrypted_block_hmac    = HMAC(a_hash, hmac_key, encrypted_block)
        final_block             = bytearray(x[0] ^ x[1] for x in zip(final_block, encrypted_block_hmac))

        yield [encrypted_block, a_hasher.digest()]

    a_hasher =

    yield [final_block, a_hasher.digest()]

def decode(a_hash, hmac_key, a_cipher, blocks, block_size):
    hmac_key    = pad_key(a_hash, hmac_key)
    block_key   = blocks[-1]
    blocks      = blocks[:-1]

    for a_block in blocks:
        block_key = bytearray(x[0] ^ x[1] for x in zip(block_key, HMAC(a_hash, hmac_key, a_block)))
    a_decrypter =

    for a_block in blocks:
        a_decrypted_block   = bytearray(a_decrypter.decrypt(bytearray_to_bytes(a_block)))
        plaintext           = a_decrypted_block[-block_size:]
        data_size           = a_decrypted_block[-block_size-1:-block_size]
        total_blocks        = a_decrypted_block[-block_size-2:-block_size-1]
        current_block       = a_decrypted_block[-block_size-3:-block_size-2]

        yield [current_block, total_blocks, data_size, plaintext]

if (__name__ == '__main__'):
    from Crypto.Hash import RIPEMD
    from Crypto.Cipher import ARC4

    from pprint import pprint as pp

    data = b"all your base are belong to us"


    blocks = [a_block for a_block in encode(RIPEMD, b'an_hmac_key', ARC4, data, 8)]


    hashes      = [a_block[1] for a_block in blocks]
    blocks      = [a_block[0] for a_block in blocks]

    pp([a_block for a_block in decode(RIPEMD, b'an_hmac_key', ARC4, blocks, 8)])