1. 2
    Suggestions for all-or-nothing transform with stream ciphers ☶ ask cryptography
    ciprian_craciun avatar authored by ciprian_craciun 1 month ago | 1 comment

(For those that don’t know about AONT (all-or-nothing transform): this is a very nice and useful construct, which basically implies that one needs the entire ciphertext in order to recover any of the plaintext. It is used in RSA as OAEP. Practical example: damaging only a small part of the ciphertext renders everything unusable.)

So, I’ve found many mentions about AONT constructs that work with block ciphers; however I haven’t found any constructs that use a stream cipher. Thus, has anyone stumbled upon such a construct using stream ciphers?

Granted, a stream cipher can always be converted into a block cipher, and in fact many stream ciphers are actually based block ciphers (like Salsa20). However many cryptographic libraries offer only a “stream API”, and thus why I’m searching for such a construct.

  1.  

  2. 2
    ciprian_craciun avatar ciprian_craciun 1 month ago | link

    (I’m writing this as a reply, so it can be discussed independent of the other threads that might pop-up.)

    Although I’m not a cryptographer or security engineer, I thought of the following scheme and would like to ask for feedback:

    • m – the message to be AONT-ed; (perhaps padded to hide the length;)
    • s – generate a random salt (of n bytes);
    • E(k, d) / D(k, e) – let these be encryption / decryption functions from a stream cipher; (let’s assume these don’t require a nonce, because if the key is random, the nonce can be constant;)
    • H(x) – let it be a hash function (of n bytes);
    • e = E(s, m); sx = s^H(e); o = e || sx – the output is o; namely apply encryption over m with the key s; take the hash of this and XOR’it with s; let the output be the encrypted part (e) concatenated with the XOR’ed salt (sx);
    • to reverse, just split the encrypted part form the XOR’ed salt (e || sx = o), compute the hash of the encrypted part (eh = H(e)), de-XOR the salt (s = sx^eh), and finally apply the decryption with the salt (m = D(s, e))

    Now, this construct isn’t actually encryption (since everything one needs to know is part of the output). However I do believe it’s a AONT construct, because if one changes even a single bit of the output (swap, remove, add), that would propagate to the salt (via hashing) which in turn would propagate to the decryption, thus resulting in completely mangled output.

    Then I think this can be extended to any authenticated-encryption scheme that uses nonces (like for example anything based on Salsa20/XSalsa20) by just XOR-ing the nonce with the hash of the output of the encryption.