Skip to content

crypto: Speck support

Eric Biggers linux-arm-kernel linux-crypto linux-fscrypt 1 version New

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest0 of 5 patches 0 repliesNew

Patches in v1 No applies recorded yet

None of the 5 patches the cover letter announces are in this archive.

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [PATCH 0/5] crypto: Speck support

Hi all,

Quoted 20 lines · Jeffrey Walton
Quoted 20 lines

Hi Jeffrey,

I see you wrote the SPECK implementation in Crypto++, and you are treating the words as big endian.

Do you have a reference for this being the "correct" order? Unfortunately the authors of the cipher failed to mention the byte order in their paper. And they gave the test vectors as words, so the test vectors don't clarify it either.

I had assumed little endian words, but now I am having second thoughts... And to confuse things further, it seems that some implementations (including the authors own implementation for the SUPERCOP benchmark toolkit [1]) even consider the words themselves in the order (y, x) rather than the more intuitive (x, y).

[1] https://github.com/iadgov/simon-speck-supercop/blob/master/crypto_stream/speck128128ctr/ref/stream.c

In fact, even the reference code from the paper treats pt[0] as y and pt[1] as x, where 'pt' is a u64 array -- although that being said, it's not shown how the actual bytes should be translated to/from those u64 arrays.

Quoted 9 lines
Quoted 2 lines

I'd really like to avoid people having to add additional versions of SPECK later for the different byte and word orders...

Hi Eric,

Yeah, this was a point of confusion for us as well. After the sidebar conversations I am wondering about the correctness of Crypto++ implementation.

We've received another response from one of the Speck creators (Louis Wingers) that (to summarize) the intended byte order is little endian, and the intended word order is (y, x), i.e. 'y' is at a lower memory address than 'x'. Or
equivalently: the test vectors given in the original paper need to be read as byte arrays from *right-to-left*.

(y, x) is not the intuitive order, but it's not a huge deal. The more important thing is that we don't end up with multiple implementations with different byte and/or word orders.

So, barring any additional confusion, I'll send a revised version of this patchset that flips the word order. Jeff would need to flip both the byte and word orders in his implementation in Crypto++ as well.

- Eric

Quoted 93 lines

As a first step here is the official test vector for Speck-128(128) from Appendix C, p. 42 (https://eprint.iacr.org/2013/404.pdf):

    Speck128/128
    Key: 0f0e0d0c0b0a0908 0706050403020100
    Plaintext: 6c61766975716520 7469206564616d20
    Ciphertext: a65d985179783265 7860fedf5c570d18

We had some confusion over the presentation. Here is what the Simon and Speck team sent when I asked about it, what gets plugged into the algorithm, and how it gets plugged in:

<BEGIN SNIP PERSONAL EMAIL>

Quoted 50 lines · On Mon, Nov 20, 2017 at 10:50 AM, <[email protected]> wrote:

...
I'll explain the problem you have been having with our test vectors.

The key is:  0x0f0e0d0c0b0a0908 0x0706050403020100
The plaintext is:  6c61766975716520 7469206564616d20
The ciphertext is:  a65d985179783265 7860fedf5c570d18

The problem is essentially one of what goes where and we probably could have done a better job explaining things.

For the key, with two words, K=(K[1],K[0]). With three words K=(K[2],K[1],K[0]), with four words K=(K[3],K[2],K[1],K[0]).

So for the test vector you should have K[0]= 0x0706050403020100, K[1]= 0x0f0e0d0c0b0a0908 which is the opposite of what you have done.

If we put this K into ExpandKey(K,sk) then the first few round keys are:

0706050403020100
37253b31171d0309
f91d89cc90c4085c
c6b1f07852cc7689
...

For the plaintext, P=(P[1],P[0]), i.e., P[1] goes into the left word of the block cipher and P[0] goes into the right word of the block cipher. So you should have m[0]= 7469206564616d20 and m[1]= 6c61766975716520, which is again opposite of what you have. If c[0]=m[0] and c[1]=m[1], then the encrypt function should be called as
Encrypt(c+1,c+0,sk). The resulting ciphertext is (c+1,c+0).

In general, everything goes in as a byte stream (not 64-bit words). In this case, if the 16 bytes of key are 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f then we first need to turn these into two 64-bit words. The first word, K[0] is 0706050403020100 and the second word is K[1]=0f0e0d0c0b0a0908. On x86 processors, if the key bytes are in the array k[] of type uint8_t, then a simple casting should get you K[1] and K[0]. That is, K[0]=((uint64_t *)k)[0] and K[1]=((uint64_t *)k)[1]. The key expansion is run with ExpandKey(K,sk). So that was what we had in mind.

Similarly, if the plaintext "bytes" were: 20 6d 61 64 65 20 69 74 20 65 71 75 69 76 61 6c (which is ascii for " made it equival")
then we first need to turn these into two 64-bit words. The first word is pt[0]=7469206564616d20 and the second word is pt[1]= 6c61766975716520. The Encrypt routine is run as Encrypt(pt[1],pt[0],sk). The resulting ciphertext is (ct[1],ct[0]) which you would turn back into a byte stream in the reverse of what we did. For example, if ct[1]= a65d985179783265 and ct[0]= 7860fedf5c570d18, then if c[] is a byte stream (i.e., of type uint8_t), then we would have c[0]=18, c[1]=0d, c[2]=57, c[3]=5c, etc. This is easy to do on x86 with a cast.

Quoted 3 lines

Let me know if all of this is now clear.

Best regards,

<END SNIP PERSONAL EMAIL>

Finally, here is the Simon and Speck team GitHub. It is the implementation the team submitted to SUPERCOP:
https://github.com/iadgov/simon-speck-supercop . The files of interest are in crypto_stream:

* speck128128ctr/ref/stream.c
* speck128192ctr/ref/stream.c
* speck128256ctr/ref/stream.c
* speck64128ctr/ref/stream.c
* speck6496ctr/ref/stream.c

The reference implementation uses CTR mode rather then ECB mode. After the CTR -> ECB conversion (mostly trivial), and then plugging in the test vectors data (key and message), we could not arrive at the same answer as the published test vector. However, we may have been plugging things in incorrectly. We were able to arrive at test vector results after a minor modification, but it may have been the wrong thing to do (in hindsight). I'll be revisiting this shortly.

Hopefully this should get things started on sorting out the details.

Jeff