Work-item: generic test-suite for new abstract.Cipher interface

[bford]

Here's a nice small work-item that would be a great way for someone new to jump in and get started on something quickly - but I would like whoever takes it on to jump into it quickly, i.e., say today or tomorrow, and try to produce first-cut code by say this weekend.

The 'cipher' branch and a new pull request (https://github.com/DeDiS/crypto/pull/23) contains an update on the abstract.Cipher interface for general symmetric cipher functionality: please see that pull request and the checked-in documentation-comments for that interface for the details. This new Cipher interface needs a proper generic test-suite, which will take any reasonable object implementing the Cipher interface and check a bunch of invariants and properties it's supposed to have. I expect the new code to go in, say, a function defined as:

func TestCipher(newCipher func(key []byte, options ...interface{}) abstract.Cipher) { ... }

in a new file 'crypto/test/cipher.go' in the 'crypto/test' package. The function will take a Cipher constructor as a higher-order function, and use it to create ciphers to test. That package currently contains generic tests for the Group and Suite interfaces; it needs a similar, generic test for Cipher implementations.

Some of the particular tests I would like to see this TestCipher function perform are:

• Create several Cipher objects with different keys (passed to the newCipher constructor), encrypt the same short message with all of them, and verify that all the encryptions come out different.
• Decrypt all of the differently-keyed encryptions above and make sure they correctly decrypt to the original message.
• Create a suite of constant, sample plaintext messages with different lengths - e.g., 0-byte, 1-byte, "Hello World", a 1KB buffer initialized to 1,2,3,... bytes, and a 1MB buffer initialized similarly - and make a test that does an authenticated-encryption of each message with some fixed key, then does an authenticated-decryption of the same message, verifying that the decrypted plaintext comes out right and that the MAC check succeeds. (See the Cipher interface comment-documentation for how the authenticated encryption should be done.)
• Run authenticated-decryptions on each of the above encrypted messages, but using the wrong key, and verify that: (a) the MAC check fails, and (b) "close to" half of the bits differ between the incorrectly-decrypted plaintext and the original plaintext of the corresponding message. For example, check that at least 30-40% of the bits differ or something like that - or if you want to be fancy, break out your probability/statistics textbook and figure out a reasonable Chernoff-bounded w.h.p. threshold suitable for each message size.
• Simulate a single-bit-flipping adversary: given each of the correct authenticated-encryptions produced above, create an incorrect ciphertext with one bit flipped, either: (a) in the very first byte, (b) in the very last byte, (c) in a randomly-chosen byte of the ciphertext, or (d) in a randomly-chosen byte of the MAC. Then attempt to "decrypt" the corrupted ciphertext and verify not only that the MAC fails to check but that "close to half" of the bits differ from the correct MAC for that ciphertext.
• Using the Cipher as a pseudo-random number generator, produce a whole bunch of random bytes (say 1MB), then count up the number of occurrences of each byte-value in a [256]int table of counters, and verify that each counter ends up being "close enough" to N/256 where N is the total number of bytes. (Another basic statistical-randomness test.)
• Implement one or two of the other well-known statistical randomness tests in similar fashion (e.g., see: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/nissc-paper.pdf). No need to do all of them by any means; just maybe one or two of the simpler ones as sanity-checks.
• Check the stream-oriented operation invariants of the cipher.Partial call: for the largest "sample plaintext" in the message test-suite above, do an authenticated-encryption using the whole message in one cipher.Message() call, then break up the message into a bunch of much smaller pieces and do the same authenticated-encryption in multiple calls to cipher.Partial() followed by cipher.Message() to finalize the message, and check that the result (both the encrypted ciphertext and the MAC value) comes out the same.
• Check "stream cipher" operation invariants: produce two different sample messages m1 and m2 of the same size; "encrypt" both of them separately in stream-cipher mode (i.e., cipher.Partial(dst, src, nil)) into cipher texts c1 and c2, then check that (c1 XOR c2) == (m1 XOR m2). This is of course a generic weakness of stream ciphers, but I want this test in order to check that when the 'key' argument is nil, the output pseudorandom bits do not depend on the input message or on anything else.
• Multiple-message tests: starting with a given Cipher instance, perform several authenticated encryptions in a row (e.g., one using each of the sample messages in the internal test-suite); then decrypt and authenticate the corresponding list of multiple authenticated-encryptions in the same order, verifying that everything comes out right, and hence the Cipher stays "in sync" between encryption and decryption across multiple messages.
• Similarly, process multiple messages as above, but corrupt one bit of the ciphertext or the MAC of the second-to-last message, and verify that the encryption/decryption process stays in sync for all but the last two messages (but fails on the last two).
• Implement any other interesting and relevant tests you might be able to think of. :)

Thanks Bryan

[davidiw]

Initial work can be found here https://github.com/davidiw/crypto/tree/ciphertest

[samanklesaria]

Added a few more (Partial and PRNG) here https://github.com/bogiebro/crypto/tree/ciphertest

[davidiw]

Great, could you cherry pick your changes onto my new ciphertest branch? I hadn't realized you had already started coding, so I just merged my commits into a single commit. If nothing else, pull in and merge with my current branch so that you get the right tests and the fix to cipher/stream.go

Cheers, David

On Sat, Feb 7, 2015 at 11:22 AM, Sam Anklesaria notifications@github.com wrote:

Added a few more (Partial and PRNG) here https://github.com/bogiebro/crypto/tree/ciphertest

— Reply to this email directly or view it on GitHub https://github.com/DeDiS/crypto/issues/24#issuecomment-73370723.

[samanklesaria]

Whoops- didn't see this. I think everything's merged in now.

[bford]

Any update on this? Is there a branch somewhere with the current test code, even if still incomplete?

[davidiw]

Seeing as how there hasn't been pull requests on this in 2 weeks, but I want tests , I'm making a pull request with where I left off. I hope that others who have taken this task follow up and push upwards there changes soon :).

[slifland37]

I have all of David's changes in a local branch but I can't see the changes made by @bogiebro; for some reason the link you posted above isn't working anymore and I don't see the Partial or PRNG tests anywhere.

I wrote my own PRNG test and I'm trying to write the Partial tests but I'm a little confused about how cipher.Partial works. In particular, if I'm splitting up a 1MB message into 1KB chunks, does that mean I should call:

cipher.Partial(dst[:1024], src[:1024], key[:(keysize/1024)]

and then iterate through every division of the dst, src, and key? My biggest confusion is about the key specifically; as I understand it, the value returned by cipher.KeySize() depends only on the cipher itself, so it might be much smaller than a 1MB input string. Is the general approach still to subdivide the key into as many equal parts as you're dividing the input text into?

[bford]

What is 'key' supposed to mean in this context? What are you trying to test in this particular test-case? If it's an "unkeyed PRNG" test, then the 'key' argument to cipher.Partial should simply be null. If you're doing a keyed PRNG test, then you should first call cipher.Message(nil, nil, key) to absorb the key/seed material, and then call cipher.Partial(dst, src, nil) any number of times to obtain pseudorandom bits from the cipher. You have to key the cipher first, then get the output bits. Make sense?

[slifland37]

Sorry; my question was unclear, but I think your answer gives me the information I need anyway.

This is not for the PRNG test. I was trying to test the invariant that encrypting a message all at once with cipher.Message(dst, src, key) is equivalent to encrypting the message in chunks with multiple calls to cipher.Partial, where the parameters I pass to cipher.Partial are divisions of the total dst and src arrays. My question was if I'm dividing the message up into chunks like that then should I also divide the key up in a corresponding way, but now I realize that that makes no sense.

I'm assuming the correct method is to call cipher.Message(nil,nil,key) to absorb the key and then call cipher.Partial many times to absorb the message incrementally, and then once the full message is absorbed the final ciphertext should be equal to the ciphertext produced by a single call of the form cipher.Message(dst,src,key).

Is that correct?

[bford]

Actually, if you're testing for the equivalence between multiple Partial calls vs one Message calls, then that equivalence should hold for any values of any of the arguments, and you should be testing all of them: i.e., with or without dst, src, and/or key slices. In particular, Message and Partial may be called with all of dst, src, and key slices (which is used in authenticated encryption), and in that case you should be calling Partial with the same number of bytes passed in each slice argument, until you "run out of bytes" in any of the argument slices.

Ideally, you should also have a TestPartial function that takes a Cipher and three slices - dst, src, and key - all of which can be of different lengths, and checks that Message(dst, src, key) behaves the same as Message(dstpad, srcpad, keypad) where the '*pad' slices are the same as the corresponding ones but allocated to each be of size max(dst,src,len) and padded with zero bytes at the end. And from that, you should be able to test that breaking those dstpad/srcpad/keypad slices into smaller chunks and passing them to Partial in pieces also produces the same result.

Make sense?

[nikkolasg]

Is this done in https://github.com/dedis/kyber/pull/23/files ? Is it still relevant ?

[ineiti]

No idea !?! Perhaps make a list of old Bryan-issues and look if we have time Wednesday?

[jeffallen]

abstract.Cipher is gone, and the replacement is well enough tested.

[bford]

Awesome, congrats on the successful weed-whacking job and thanks for all the hard work! :)