Handling of Monte-Carlo tests for symmetric ciphers

[atvassilev]

The MC Test for the different modes of symmetric ciphers relies on an algorithm with an initial state (e.g., key, IV, plaintext) - see for example http://csrc.nist.gov/groups/STM/cavp/documents/aes/AESAVS.pdf. The algorithm is different/specific for each mode.

Traditionally, CAVS supplied the initial value for the algorithm and the tested implementation was expected to implement the MCT algorithm, feed the initial condition in it and report the results from the execution.

The definition of the MCT is not well suited for expanding it into a series of simple test cases because the values for each test depend on the results from the previous test.

The current specification in sub_symmetric does not appear to have a handle for this type of test. A new type of test is needed for this

@jfigus if you see this differently, please chime in.

[jfigus]

We may be able to extend the sub_symmetric spec to handle MCT. We could add a new JSON field in the request that signifies MCT processing is to be performed by the DUT.

The response file from the DUT would have multiple test case responses for each test case in the original vector set. Then in the response file we could have two identifiers for each test result: tcId and tcMCTId, where tcMCId runs sequentially from 0 to 99 as defined in the AESAVS document.

[atvassilev]

Just to make sure I understand you, are you saying we define an optional type for each tcId? If the type is set and equal to MCT, then this tcId is a Monte Carlo test and the values there are the initial conditions for the corresponding to the mode MCT algorithm. If the type is not set, the corresponding test case is simple. For example,

{ "tcId": 2199, "type" : "MCT", "key": "9dc2c84a37850c11699818605f47958c", "iv": "256953b2feab2a04ae0180d8335bbed6", "pt": "2e586692e647f5028ec6fa47a55a2aab" },

Similarly, in reporting the results for this tcId, if the type is set to MCT, it contains a list of 100 results from the test, provided in an optional "resultsArray" or something like it.

"testResults": [ { "tcId": 2199, "type" : "MCT",
"resultsArray" : [ {"ct": "1b1ebd1fc45ec43037fd4844241a437f"}, {"ct": "bf43583a665fa45fdee831243a16ea8f"}, .etc. ] }, .... ] In this example I omitted the corresponding key and iv value for each test result but they can be added easily if needed.

What do you think?

[jfigus]

This looks good to me. Harold may have an opinion on this from the server implementation perspective.

[Kritner]

Hey guys, in our discussion yesterday, I believe we were leaning more toward implementing the testType within the testGroup, rather than the testCase. In addition to the "MCT" type test, there is at a minimum a "KAT", and "MMT" test type.

The reason we were leaning more toward in the test group, rather than the test case, is that the testGroups are more similar to individual "files" within the current CAVS tool tests. The MCT tests are always within their own file, as it is really a difference in "options/functionality being tested" for the running of the algorithm (similar to how differing PT lengths are always separate TestGroups and/or files.

If we were to add this property to the TestGroup, the test vector JSON could look like:

               {
                  "acvVersion": "0.2",
                  "vsId": 1,
                  "algorithm": "AES-ECB",
                  "direction": "encrypt",
                  "testGroups": [
                    {
                      "keyLen": 128,
                      "ptLen": 128,
                      "testType": "MCT"
                      "tests": [
                        {
                          "tcId": 1,
                          "key": "8d2e60365f17c7df1040d7501b4a7b5a",
                          "pt": "59b5088e6dadc3ad5f27a460872d5929",
                        }
                      ]
                    }
                  ]
                }  

Does that make sense? Any input?

More to come regarding the testResults for "MCT", as well as the difference between "KAT" and "MMT" tests...

[atvassilev]

If you look at the definition of MMT, it is nothing more than a KAT with an input message that is a multiple of the block size of the block cipher in order to test the chaining properties of the algorithm. It makes no sense to differentiate between KAT and MMT as all tests defined in the AESAVS are known answer tests. i.e. KATs.

Given this, the test type should be a property of the specific test case, not the other way around. You can extend the example I provided with the additional optional type "MMT" if you would like to differentiate this test from a generic test case.

I hope this clarifies things and let me know if you have anything further.

[Kritner]

I understand what you're saying, but I would disagree that the testType belongs on the testCase over the testGroup.

The testGroups are generating testCases based on what is being tested within the algorithm for that group. With testType being an attribute on testCase, that would mean that groups would need to generate "different" testCases based on some undefined condition; e.g. generate 15 random testCases for 128 bit keys, 128 bit plainTexts, and also add one additional test within that same group that's a MonteCarlo test - a very different piece of logic that goes into generating and validating, for a single group of tests.

Whereas if the testType were on the testGroup level, we could have as an example:

TestGroup 1 keyLen: 128 ptLen: 128 testType: "KAT"

Generate 15 test cases with random 128 bit data for the keyLen and ptLen, algorithm runs only a single time

TestGroup 2 keyLen: 128 ptLen: 128 testType: "MCT"

Generate 1 test case with a random 128 bit key and pt, running through the Monte Carlo algorithm.

This way we could control not only the testCases generated for a specific set of parameters on the group, but we could also get potentially very detailed in our test types.

As an example, "KAT" could be further broken down for AES-ECB to:

• GFSbox
• KeySbox
• Variable Key
• Variable Text

Where in the above tests, the number of tests for each "sub-KAT" type is not some arbitrary value, but rather an iteration of bit switching, number of cases depending on the length of the fields that require bit switching. Additionally, the above KATs are unchanging between new vector generations, whereas the MMTs and MCTs have a bit of randomness to them each time.

Does it not make sense to have these tests given labels on the group level? In addition to providing information on the group level on what is being tested, it will also mean all tests within the group are utilizing the algorithm in the same manner, testing for one specific thing. In comparison to having a test group that has test cases that for some, have to run the algo a single time, for others run the algo 1000 times, and are in effect checking for different functionality within the algo?

One other final minor point, is we would save a few KB by putting the label on the group over each individual case (normalization?).

[atvassilev]

Well, I understand the direction you advocate for the protocol but have the following concerns with it.

The AESAVS states that each of different types of KATs (GFSbox, etc) are simply tests cases with some keys, iv, and input message. From a DUT perspective, the differentiation between them is not useful. All a client does is execute each specified test and it does not need to care if a particular test set is GFSbox or not. I think this is how the current implementation in CAVS is - it does not differentiate between the different types of so-called KATs - and I don't see this changing going forward. Similarly, it is not useful for a client to know if a specific test is unique or the same for all clients. It is a test that a client would execute either way. Moreover, the test groups for AES and any other algorithm are well known and fixed - they are defined in the corresponding validation system document. So, they can be implicitly represented on the server during generation. To note also, these documents do not change often - just look at the dates of AESAVS. The server has all necessary context to generate the required test cases for a particular mode and key size selection. The corresponding known answers are computed at the same time and stored aside for use in validation. The validation step would be to simply compare the numbers in the incoming request and the stored reference.

Bottom line, the overhead associated with your proposal would not be justified.

[hbooth]

For clarity, there were two separate points raised in Russ’ email. One point which you have addressed had to do with what values will be found in the test type. I understand what you are saying and understand your point regarding limiting the test type values to values with a different from the client perspective. For the symmetric ciphers this seems to indicate “KnownAnswerTest” and “MonteCarloTest” as possible values.

The other point Russ raised was the location of the attribute indicating the test type (test level vs. group level). I believe his suggestion of placing the type at the group level makes sense since the processing on both server and client side would be similar for all tests of the same group. This also provides additional differentiation between groups beyond just parameter changes, and the positive It would also reduce the amount of data. The earlier suggestion that the results for tests that have multiple results would be available in an array was a good one and that should be retained.

Thoughts?

[atvassilev]

Good we are getting somewhere at least on the understanding part :) Technically speaking, there is only one attribute actually - MCT. The other is implied as it is in the current version of the spec.

I guess I am failing to see why do you have to have testGroups defined to have similar processing on both sides. Generation on the server is unique processing and does not have representation on the client. Once the generation is complete, the result is a reference file that could and should look very similar to the response received from the client. Hence, the processing on both sides should be similar even without the testGroups from Russ' proposal.

I think the differentiation makes sense on the server, primarily during generation. I think I already articulated why such differentiation is not useful for the client. Given that generation is unique to the server, it creates an untenable situation where you would like to burden the protocol with semantics that are only useful to one side. I would point again that one could store any additional context that the server may need with the reference file produced by generation and not burden the client with it. I think it is important to keep the protocol as simple as possible.

Finally, I guess I am also failing to see the savings associated with Russ' proposal. I think the representation in the example I provided is minimal in the sense it is the minimal context required to define all tests specified in AESAVS for a particular choice of key sizes and modes. This consideration in fact was one of the reasons I picked an array to include all answers for MCT - it seemed to provide the most economical way. I think Russ' proposal would actually increase the amount of data communicated between the client and the server compared to my proposal. It seems to me the only way to save beyond this would be to abstract out some of the tests, like it is done for Monte-Carlo and have the client expand them from some initial condition. This would not be desirable though as it would unnecessarily complicate the client and would cause us to deviate from the specification in the validation system document. I would say this would not be worth pursuing at this stage.

[hbooth]

there is only one attribute actually - MCT. The other is implied as it is in the current version of the spec.

Now that we have two, I don’t think a test type should be implied, and we should be explicit about it. With the addition of a test type attribute (regardless of a level) new values can be added as needed with minimal disruption to the overall specification.

I guess I am failing to see why do you have to have testGroups defined to have similar processing on both sides. Generation on the server is unique processing and does not have representation on the client.

The point I was trying to make is that for a MonteCarloTest the work done by the client is different for this type than for some other test type (we only have two at the moment, but I figure we will likely identify more). A MonteCarloTest has a specific set of actions required by the client as defined by this test type and these actions are different than for a KnownAnswerTest type. I thought the purpose of the TestGroup was to group similar tests together, and placing the test type at the group level does not pre-suppose a particular implementation on the client or the server while retaining flexibility in the overall protocol.

Finally, I guess I am also failing to see the savings associated with Russ' proposal.

I raised this point based on a prior thought that was replaced by the array suggestion. I forgot about that, and this issue does not exist.

— You are receiving this because you commented. Reply to this email directly, https://github.com/usnistgov/ACVP/issues/41#issuecomment-271644357, or https://github.com/notifications/unsubscribe-auth/AKJUd2ihSfAmfCjrfiS_qOUD9gQNrJfaks5rQ8MYgaJpZM4Lexqh.

[atvassilev]

Alright, to summarize the discussion so far we have two basic alternatives:

1. The proposal I made last night.
2. TestGroup with array for results in case of tests with more than one answer.

The pro and cons for each of the approaches are provided above. I would ask John and Barry to make a selection and we will go with it. I just hope they themselves would not split like us. If this were to happen, I am going to flip a coin and make a decision this way.

[jfigus]

Either way works, but I would lean towards option 2.

[bfussell]

Sorry for the delay on my input. I would prefer option 2 as well.

Barry

From: John Foley [mailto:notifications@github.com] Sent: Wednesday, January 11, 2017 9:48 AM To: usnistgov/ACVP ACVP@noreply.github.com Cc: Subscribed subscribed@noreply.github.com Subject: Re: [usnistgov/ACVP] Handling of Monte-Carlo tests for symmetric ciphers (#41)

Either way works, but I would lean towards option 2.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/usnistgov/ACVP/issues/41#issuecomment-271887089, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AGnx9qPchZnaXISyaMdMUwJBAZzQCn_Mks5rROuvgaJpZM4Lexqh.

[atvassilev]

Great, it is option 2 then. For the time being there will be two testGroups: one for MCT the other for regular KATs.

John could you please update the symmetric spec along these lines so the team here can proceed with the implementation?

[Kritner]

Just as a follow up - wanted to confirm preferences on testResults for a MCT type test.

Based on @atvassilev's suggestion, there are probably a few different ways to send the results back. Wanted to run a few of those options by everyone.

Results:

{
  "algorithm": "AES-ECB",
  "isSample": false,
  "testResults": [
    {
      "tcId": 1,
      "resultsArray": [
        {
          "cipherText": "2FC55577302EC4EBED45E22CC6807A9B"
        },
        {
          "cipherText": "2870ACB84310B5DFFFA5C8C2DD05C524"
        }
    }
  ]
}

The above is all we would need, though I think adding a count, or iteration to the result array could be beneficial. Additionally adding the key and plainText (or cipherText depending on operation type) would allow to better report on at what point, and on what element during the iterations through the MCT test, incorrect values were encountered - be it input or output through the iterations.

That could look something like this:

{
  "algorithm": "AES-ECB",
  "isSample": false,
  "testResults": [
    {
      "tcId": 1,
      "resultsArray": [
        {
          "count": 0,
          "key": "E23A9A0CB040DFAAEE5807BD8B516283",
          "plainText": "3E36164FB5A4094B88FED90CF5C419E7",
          "cipherText": "2FC55577302EC4EBED45E22CC6807A9B"
        },
        {
          "count": 1,
          "key": "CA4A36B4F3506A7511FDCF7F5654A7A7",
          "plainText": "2FC55577302EC4EBED45E22CC6807A9B",
          "cipherText": "2870ACB84310B5DFFFA5C8C2DD05C524"
        },
        .....
    }
  ]
}

Thoughts?

[atvassilev]

@Kritner, my understanding is we settled on a hybrid solution that combines the testGroups for MCT and KAT (essentially, all other tests) and with the resultsArray for reporting results in cases where there is more than one answer to a particular test, such as MCT. In the case of an array, I do not see value in sending the count, the array elements are indexed implicitly. The spec should say the results should be reported in order and this is what the server should assume and implement. If a client messes the results order up, they will fail. So, I think either of your proposals would be ok, except the "count".

[hbooth]

Given some discussions that implementation of the Monte Carlo algorithm itself is source of error, having more information from the client to identify the source of any implementation errors seems to be a good idea. I would lean towards your option 2, accounting for @atvassilev's comment to remove the "count".

[bfuss]

I agree with Harold. No need for the KEY/PT for normal KATs, but for MCT it may help debug the start of the failure.

[bfuss]

Here is what I am proposing for this issue:

In figure 10:

"test_groups": [ { "keyLen": 128, "ivLen": 96, "ptLen": 0, "aadLen": 128, "tagLen": 128,

• "testType": "KAT" "tests": [

And then following text following figure 10.

In general these types of requests are targeted for a standard Known Answer Test, however in some instances the DUT needs to be instructed to perform a Monte Carlo Test. This is performed using the testType keyword which has the options KAT or MCT. The results returned to the server vary depending on the testType. For KAT tests, only those fields which are new will be returned such as the ct for AES-CBC, or for AES-GCM iv, ct and tag. For MCT tests each iteration will be returned to provide as much error debugging as possible, ie pt, iv and ct. Additional JSON formatting details are available in the sub specifications. For guidance on how to perform the testType tests please refer to the CAVP validation testing requirements available on the NIST website and referenced in the sub specifications.

And the sub specs need a reference to CAVP document that provides guidance on how to perform the test and examples of each testType format.

[bfussell]

Wanted to get a quick clarification on the sub_hashmac JSON. We do want to change "type" to "testType" for SHA and CMAC as well, correct ?

Thanks !

[atvassilev]

Can this issue be closed now?

[bfussell]

I'm OK as long as symmetric ciphers use testType "MCT" or "KAT" and SHA uses "montecarlo" or "functional"

[atvassilev]

Ah, my memories come back... Didn't we agree to use AFT instead of KAT throughout all specs? I would assume SHA uses MCT for Monte Carlo and AFT for functional.

[bfussell]

You're right, I meant AFT not KAT, it's even that way in my client already for symmetric ciphers.

[atvassilev]

OK, I am closing this issue and opening two new ones: one for the symmetric spec to change KAT to AFT, another for SHA to change montecarlo to MCT and functional to AFT.

[IntelEntropyReport]

I just got the MCT working on some new silicon. It takes 20.8 hours to run, because there are 100,000 invocations of AES and all the JTAG back and forth to inject the vector and get the result takes a little less than 1 second. Why is it 100 iterations of 1000 iterations? What does so many iterations achieve? Wouldn't 10 of 10 work find and be 1000 time faster?

[livebe01]

Hi @IntelEntropyReport. See Section 6.1 of the symmetric spec for the background on the Monte Carlo tests. These tests have probably been around in some form for ~20 years. The tests are designed to be strenuous. For most algorithm implementations, I think that we'd expect that the tests could be implemented in such a way as to minimize manual effort and the strain is put on the actual implementation.