[Cryptography] The paranoid approach to crypto-plumbing

John Kelsey crypto.jmk at gmail.com
Wed Sep 18 00:42:47 EDT 2013

For hash functions, MACs, and signature schemes, simply concatenating hashes/MACs/signatures gives you at least the security of the stronger one.  Joux multicollisions simply tell us that concatenating two or more hashes of the same size doesn't improve their resistance to brute force collsion search much.  The only thing you have to be sure of there is that the MAC and signature functions aren't allowed access to each others' secret keys or internal random numbers.  Otherwise, MAC#1 can always take the value of MAC#2's key.  This is just

message, signature 1, signature 2

where the signatures are over the message only.  

For encryption algorithms, superencryption works fine.  You can first encrypt with AES-CBC, then encrypt with Twofish-CFB, then with CAST5 in CFB mode.  Again, assuming you are not letting the algorithms know each others' internal state or keys, if any of these algorithms are resistant to chosen plaintext attacks, then the combination will be.  This doesn't guarantee that the combination will be any stronger than the strongest of these, but it will be no weaker.  (Biham and later Wagner had some clever attacks against some chaining modes using single-DES that showed that you wouldn't always get anything stronger than one of the ciphers, but if any of these layers is strong, then the whole encryption is strong.  

An alternative approach is to construct a single super-block-cipher, say AES*Twofish*SERPENT, and use it in a standard chaining mode.  However, then you are still vulnerable to problems with your chaining mode--the CBC reaction attacks could still defeat a system that used AES*Twofish*SERPENT in CBC mode, but not AES-CBC followed by Twofish-CFB followed by SERPENT-CTR.  

For key-encryption or transport, I think it's a little more complicated.  If I need six symmetric keys and want to use three public key methods (say ECDH, NTRU, RSA) to transport the key, I've got to figure out a way to get the benefit from all these key exchange mechanisms to all six symmetric keys, in a way that I'm sure will not leak any information about any of them.  Normally we would use a KDF for this, but we don't want to trust any one crypto algorithm not to screw us over.  

I think we can get this if we assume that we can have multiple KDFs that have secrets from one another.  That is, I compute 

KDF1( key1, combined key exchange input) XOR KDF2( key2, combined key exchange input)

The reason the two KDFs need keys that are secret from each other is because otherwise, KDF1 could just duplicate KDF2 and we'd get an all-zero set of keys.  If KDF2 is strong, then KDF1 can't generate an output string with any relationship to KDF2's string when it doesn't know all the input KDF2 is getting.  

I agree with Perry that this is probably padlocking a screen door.  On the other hand, if we want to do it, we want to make sure we guard against as many bad things as possible.  In particular, it would be easy to do this in such a way that we missed chaining mode/reaction type attacks.  


More information about the cryptography mailing list