[tahoe-dev] protecting against bugs in our own crypto code

[Ben Laurie]

zooko wrote:
> On May 5, 2008, at 10:44 PM, Ben Laurie wrote:
> 
>> Since you don't do an integrity check after decryption (which seems
>> unwise), all that needs to fail is the decryption.
> 
> Here's the history of this issue until now:
> 
> One of the earliest discussions on the newly-public tahoe-dev mailing  
> list a year ago was me arguing that an integrity check on the  
> plaintext was redundant with an integrity check on the ciphertext: [1].
> 
> This was my argument against Rob Kinninmont who (inunpublished  
> personal communication of the same time) argued that redundant  
> integrity checks were worth it.  My argument was basically that our  
> quality assurance process should ensure that the decryption code was  
> correct, and that if our quality assurance process wasn't up to that  
> task, then it probably wouldn't be up to the task of ensuring that  
> our redundant integrity check was correct either.
> 
> We went Rob's preference -- the redundant integrity checks on  
> plaintext in addition to ciphertext (and merkle trees of shares) on  
> immutable files, but planned to remove the redundant checks once we  
> had sufficient confidence in the correctness of our erasure-decoding,  
> decryption, and digital signature checking.  When we created  
> decentralized, encrypted mutable files in Tahoe v0.7 we didn't  
> include redundant checks on the plaintext of the mutable files.
> 
> With the Tahoe 1.0 release, we had learned that brute-force/guessing  
> attacks on convergent encryption were more powerful than previously  
> thought (controversial -- more below), and we removed the hash of the  
> plaintext from the immutable files, since they can be used to perform  
> such attacks. (Thanks to Brian Warner for re-explaining this to me on  
> IRC today.)
> 
> 
> Now that I've seen this problem -- how the port to FreeBSD, done  
> independently by two different people, yielded silently incorrect AES  
> decryption, I've changed my mind and decided that Rob was right.  In  
> a sense my argument was right -- the allmydata quality assurance  
> process made sure that we never deployed a version which did AES  
> incorrectly, since we had extensive unit tests which verified the AES  
> against fixed standard test vectors and other tests,

This seems to me to be where it all went wrong for you. You should have 
test vectors for the whole system, not just the components.

Presumably the reason my system survived self-test is because the 
encryption, though wrong, was correctly undone by the decryption. Test 
vectors would have detected that.

 > and as soon as
> Greg Hazel ported Tahoe to the first platform where this bug was  
> exercised (Windows using the Microsoft compiler), the very next thing  
> he did was run the pycryptopp unit tests and discover the bug.
> 
> But in a sense I wasn't right, because not everyone runs the  
> pycryptopp unit tests when installing Tahoe, and because there could  
> be other bugs which aren't caught by the unit tests but would be  
> caught by a redundant integrity check on the plaintext.

Belt and braces for something I am supposed to trust all my data to 
seems like a good idea to me.

BTW, the reason neither Ben Hyde nor I ran the unit tests is because we 
both installed cryptopp from FreeBSD's ports system, which apparently 
never runs self-tests - which has caused me problems with crypto before.

> So, I've changed my mind and think Rob was right.
> 
> 
> However, the brute-force/guessing attack on convergent encryption is  
> still an issue.  Since the last time that the topic was discussed  
> [2], I was able to come up with an example which will hopefully  
> motivate some of the doubters (although I am sure not all of them).   
> That example (thanks to some anonymous contributors on IRC for this)  
> is that when you install MySQL it by default creates a file which  
> contains some boilerplate bytes and your root password.  If you then  
> backup your entire system using convergent encryption, this enables  
> an economical brute-force/guessing/rainbow-table attack on your MySQL  
> root password as well as everyone else's MySQL root password who uses  
> the same default setting and the same convergent encryption.
> 
> Fortunately, we can have both integrity-check on the plaintext, and  
> immunity to the question of such attacks by using a MAC instead of a  
> secure hash, where the MAC key is (derived from) the encryption key.   

Why would that give you immunity to rainbow table attacks?

Presumably what would give immunity to rainbow tables is to use a random 
IV, though it would not change the brute force equation.

OTOH, I have not yet figured out why you want to use convergent 
encryption anyway? Is it to save space?

> As a bonus, we can get reduced CPU usage and smaller Capability  
> Extension Blocks compared to a secure hash of the plaintext by using  
> the modern Carter-Wegman MAC such as Poly1305-AES or VMAC-AES-128.
> 
> 
> Another improvement to our process might be to have the Tahoe tests  
> run the pycryptopp tests, as suggested by Ben Laurie, or at least to  
> add a "check if pycryptopp's AES is working" test to the Tahoe tests.
> 
> Another improvement, also suggested by Ben Laurie, would be to  
> eliminate the "default iv" feature from pycryptopp.  I'm working on a  
> new version of pycryptopp, so I'll look at that issue.
> 
> Another improvement would be for someone to contribute a reliable  
> FreeBSD box to server as a buildslave.
> 
> 
> Thanks!
> 
> Regards,
> 
> Zooko
> 
> [1] http://allmydata.org/pipermail/tahoe-dev/2007-May/000020.html
> [2] http://www.mail-archive.com/cryptography@metzdowd.com/msg08949.html
> _______________________________________________
> tahoe-dev mailing list
> tahoe-dev at allmydata.org
> http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
> 
> 


-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff