[tahoe-dev] Bulk encryption for 100 year cryptography

[David-Sarah Hopwood]

Samuel Neves wrote:
> During the last few months, the 100 year cryptography project saw a
> gradual convergence from postquantum/lattice/subset-sum based digital
> signatures to hash-based signatures. The argument there is that since we
> are using a hash function H anyway to hash the input, the strength of
> the digital signatures is ultimately always dependent on H. Thus,  a
> H-based digital signature algorithm 'just makes sense'.
> 
> Hashing itself has been made more future-resilient by combining two
> different hash functions by Comb4P. This function would be our above
> mentioned H.
> 
> In all of this, encryption seems to be left out of the fun. Instead,
> plans are to mix AES (in counter mode) and Salsa20. Why? My suggestion
> here is to also use H for this as well. This can be done is two
> different ways: by a Feistel network construction (suggested by Zooko)
> or counter mode (not unlike Salsa20's mode of operation).
> 
> If I remember correctly, we need a 4-round Feistel network with a
> perfect round function to achieve provable "strong" pseudorandom
> permutation status. However, since we intend to encipher things in
> counter mode (at least it would seem to, from the AES and Salsa20
> usage), we would use this Feistel network in counter mode.
> 
> The alternative is to cut the middleman: we hash a secret key K and a
> counter CTR and XOR it with our plaintext --- C = H(K||CTR) ^ P. This is
> roughly how Salsa20 works, and seems to be secure as long as H is secure.
> 
> This would make all cryptographic primitives in the 100 year
> cryptography project dependent on H, which itself amasses the strengths
> of more than one hash function to achieve future-resilience.

We require IND-CPA security for the cipher (since integrity is achieved
independently of encryption). The IND-CPA security of a hash in CTR mode
is dependent on the PRF property of the hash. This means that the Comb4P
combiner is not needed for this application; XOR is a robust combiner for
independently-keyed PRFs (i.e. C = H1(K1 || CTR) ^ H2(K2 || CTR) ^ P,
where K1 and K2 are derived using a secure KDF).

The argument against using a hash in CTR mode as a cipher, is that the
design criteria for a hash normally focus on other properties than the
PRF property, such as collision-resistance. Since collision-resistance
typically requires more rounds, this may make the hash unnecessarily more
costly than a cipher with comparable security. Or if a hash and a cipher
have the same overall cost, then the hash might to be less secure when
used as a PRF, all else being equal, because its design is not focussed
on achieving the PRF property.

Also note that the argument for using hash-based signatures is primarily
that it would remove a dependency on any public-key trapdoor function.
Trapdoor one-way functions are fundamentally more difficult to construct,
and potentially more susceptible to new analysis techniques within the
next 100 years [*], than plain one-way functions or second-preimage-
resistant hashes. This argument doesn't really apply to the cipher,
which already uses only symmetric crypto.


[*] I'm personally more worried about new cryptanalysis than I am by
    quantum computers.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
URL: <http://allmydata.org/pipermail/tahoe-dev/attachments/20100622/224934f1/attachment.pgp>